[killerstorm]

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.

It works fine.