There's another option: let the clients do the compression. I.e. a client would sign & encrypt a message "I applied messages 0..1001 and got document X". Then this can be a starting point, perhaps after it's signed by multiple clients.
That introduces a communication overhead, but is still likely to be orders of magnitude cheaper than homomorphic encryption
vhcr
Now you need a consensus algorithm.
josephg
You don’t. Instead of sending the resulting state after compressing, you can compress a chunk of operations which get merged in a block by the client.
That introduces a communication overhead, but is still likely to be orders of magnitude cheaper than homomorphic encryption