5 ms·

> Now, however, the server can no longer understand the changes you send. If you want to see your friend’s latest changes, you’ll need to both be online at the

> Now, however, the server can no longer understand the changes you send. If you want to see your friend’s latest changes, you’ll need to both be online at the same time. What? No, the server sends you the changes you've not seen yet, you decrypt and merge them, and so you get the latest version of the document. Right? The homomorphic encryption is a fascinating topic, but it's almost never an answer if you need anything resembling reasonable performance and/or reasonable bandwidth. I've seen a paper that ingeniuously uses homomorphic encryption to implement arbitrary algorithmic computations, totally secret, by encoding a (custom-crafted) CPU together with RAM and then running "tick a clock" algorithm on them. And it works, so you can borrow some AWS huge instance and run you super-important calculations there — at 1 Hz. I am not kidding, it's literally 1 virtual CPU instruction per second. Well, if you are okay with such speed and costs, you either have very small data — at which point just run your computation locally, or you're really, really rich — at which point just buy your own goddamn hardware and, again, run it locally.

zawaideh 1y ago
If the server can't operate on the content, it can't merge it into the CRDT documents. Which means it would need to sending and receiving the entire state of the CRDT with each change. If the friend is online then sending operations is possible, because they can be decrypted and merged.
- Joker_vD 1y ago
  I... still can't make heads or tails out of this description. Let me restate how I understand the scheme in TFA: there are two people, editing on the same document using CRDTs. When one person makes an edit, they push an encrypted CRDT to the sync server. Periodically, each of them pulls edits made by the other from the sync server, apply them to their own copy, and push the (encrypted) result back. Because of CRDT's properties, they both end up with the same document. This scheme doesn't require them two people to be on-line simultaneously — all updates are mediated via the sync server, after all. So, where am I wrong?
  - eightys3v3n 1y ago
    I think the difference in understanding is that the article implies, as I understand it, that the server is applying the changes to the document when it receives a change message, not the clients. If the clients were applying the changes then we don't need Homomorphic encryption in the first place. The server would just store a log of all changes; cleaning it up once it was sure everyone played the changes if that is possible. Without Homomorphic encryption, the server must store all changes since some full snapshot and a full snapshot of the document. Where as with it, the server only ever stores the most recent copy of the document. This could be done to reduce the time required for a client to catch up once it comes online (because it would need to replay all changes that have happened since it last connected to achieve the conflict free modification). But the article also mentions something about keeping the latest version quickly accessible.
    - Joker_vD 1y ago
      Article literally starts with One way to solve this is end-to-end encryption. You and your friend agree on a secret key, known only to each other. You each use that key to encrypt your changes before sending them, decrypt them upon receipt, and no one in the middle is able to listen in. Because the document is a CRDT, you can each still get the latest document without the sync server merging the updates. That is indeed a solution, but then for some reason claims that this schemes requires both parties to be on-line simultaneously. No, it doesn't, unless this scheme is (tacitly) supposed to be directly peer-to-peer which I find unlikely: if it were P2P, there would be no need for "the sync server" in the first place, and the description clearly states that in this scheme it doesn't do anything with document updates except for relaying them.
      - jakelazaroff 1y ago
        Hi, author here! The scenario was meant to be high level — I guess I should have gotten more into the various architectures and tradeoffs, but the article is already pretty long. The way I see it there are a couple of ways this can shake out: 1. If you have a sync server that only relays the updates between peers, then you can of course have it work asynchronously — just store the encrypted updates and send them when a peer comes back online. The problem is that there's no way for the server to compress any of the updates; if a peer is offline for an extended period of time, they might need to download a ton of data. 2. If your sync server can merge updates, it can send compressed updates to each peer when it comes online. The downside, of course, is that the server can see everything. Ink & Switch's Keyhive (which I link to at the end) proposes a method for each peer to independently agree on how updates should be compressed [1] which attempts to solve the problems with #1. [1] https://github.com/inkandswitch/keyhive/blob/main/design/sedimentree.md https://github.com/inkandswitch/keyhive/blob/main/design/sed...
- ath92 1y ago
  Generally, this is not really true. The point of CRDTs is that as long as all parties receive all messages (in any order), they should be able to recreate the same state. So instead of merging changes on the server, all you need is some way of knowing which messages you haven’t received yet. Importantly this does not require the server to be able to actually read those messages. All it needs is some metadata (basically just an id per message), and when reconnecting, it needs to send all the not-yet-received messages to the client, so it’s probably useful to keep track of which client has received which messages, to prevent having to figure that out every time a client connects.
  - charcircuit 1y ago
    If it takes 1 seconds per merge as per the article it sounds like a poor user experience for when new people join they have to wait hundreds or thousands of seconds to get to the doc.
    - ctde 1y ago
      it was 0.5 ns .. 1s was the FHE case
  - josephg 1y ago
    You’re talking past each other. These are both valid descriptions of CRDTs - just different types of CRDTs. Generally there’s two categories of CRDTs: state based and operation based CRDTs. State based CRDTs are like a variable with is set to a new value each time it changes. (Think couchdb if you’ve used it). In that case, yes, you generally do update the whole value each time. Operation based CRDTs - used in things like text editing - are more complex, but like the parent said, deal with editing events. So long as a peer eventually gets all the events, they can merge them together into the resulting document state. CRDTs have a correctness criteria that the same set of operations always merges into the same document, on all peers, regardless of the order you get the messages. Anyway, I think the parent comment is right here. If you want efficient E2E encryption, using an operation based crdt is probably a better choice.
- clawlor 1y ago
  There are variants of CRDTs where each change is only a state delta, or each change is described in terms of operations performed, which don't require sending the entire state for each change.
- blamestross 1y ago
  > Which means it would need to sending and receiving the entire state of the CRDT with each change. > If the friend is online then sending operations is possible, because they can be decrypted and merged. Or the user's client can flatten un-acked changes and tell the server to store that instead. It can just allways flatten until it hears back from a peer. The entire scenario is over-contrived. I wish they had just shown it off instead of making the lie of a justification.
killerstorm 1y ago
It's very common for CS and cryptography-adjacent papers to describe something impractical. Even more impractical than what you described - e.g. complexity of an attack is reduced from 2^250 to 2^230. The purpose of these papers is to map out what's possible, etc, which might at some point help with actual R&D.

zawaideh 1y ago

If the server can't operate on the content, it can't merge it into the CRDT documents. Which means it would need to sending and receiving the entire state of the CRDT with each change. If the friend is online then sending operations is possible, because they can be decrypted and merged.

Joker_vD 1y ago
I... still can't make heads or tails out of this description. Let me restate how I understand the scheme in TFA: there are two people, editing on the same document using CRDTs. When one person makes an edit, they push an encrypted CRDT to the sync server. Periodically, each of them pulls edits made by the other from the sync server, apply them to their own copy, and push the (encrypted) result back. Because of CRDT's properties, they both end up with the same document. This scheme doesn't require them two people to be on-line simultaneously — all updates are mediated via the sync server, after all. So, where am I wrong?
- eightys3v3n 1y ago
  I think the difference in understanding is that the article implies, as I understand it, that the server is applying the changes to the document when it receives a change message, not the clients. If the clients were applying the changes then we don't need Homomorphic encryption in the first place. The server would just store a log of all changes; cleaning it up once it was sure everyone played the changes if that is possible. Without Homomorphic encryption, the server must store all changes since some full snapshot and a full snapshot of the document. Where as with it, the server only ever stores the most recent copy of the document. This could be done to reduce the time required for a client to catch up once it comes online (because it would need to replay all changes that have happened since it last connected to achieve the conflict free modification). But the article also mentions something about keeping the latest version quickly accessible.
  - Joker_vD 1y ago
    Article literally starts with One way to solve this is end-to-end encryption. You and your friend agree on a secret key, known only to each other. You each use that key to encrypt your changes before sending them, decrypt them upon receipt, and no one in the middle is able to listen in. Because the document is a CRDT, you can each still get the latest document without the sync server merging the updates. That is indeed a solution, but then for some reason claims that this schemes requires both parties to be on-line simultaneously. No, it doesn't, unless this scheme is (tacitly) supposed to be directly peer-to-peer which I find unlikely: if it were P2P, there would be no need for "the sync server" in the first place, and the description clearly states that in this scheme it doesn't do anything with document updates except for relaying them.
    - jakelazaroff 1y ago
      Hi, author here! The scenario was meant to be high level — I guess I should have gotten more into the various architectures and tradeoffs, but the article is already pretty long. The way I see it there are a couple of ways this can shake out: 1. If you have a sync server that only relays the updates between peers, then you can of course have it work asynchronously — just store the encrypted updates and send them when a peer comes back online. The problem is that there's no way for the server to compress any of the updates; if a peer is offline for an extended period of time, they might need to download a ton of data. 2. If your sync server can merge updates, it can send compressed updates to each peer when it comes online. The downside, of course, is that the server can see everything. Ink & Switch's Keyhive (which I link to at the end) proposes a method for each peer to independently agree on how updates should be compressed [1] which attempts to solve the problems with #1. [1] https://github.com/inkandswitch/keyhive/blob/main/design/sedimentree.md https://github.com/inkandswitch/keyhive/blob/main/design/sed...
ath92 1y ago
Generally, this is not really true. The point of CRDTs is that as long as all parties receive all messages (in any order), they should be able to recreate the same state. So instead of merging changes on the server, all you need is some way of knowing which messages you haven’t received yet. Importantly this does not require the server to be able to actually read those messages. All it needs is some metadata (basically just an id per message), and when reconnecting, it needs to send all the not-yet-received messages to the client, so it’s probably useful to keep track of which client has received which messages, to prevent having to figure that out every time a client connects.
- charcircuit 1y ago
  If it takes 1 seconds per merge as per the article it sounds like a poor user experience for when new people join they have to wait hundreds or thousands of seconds to get to the doc.
  - ctde 1y ago
    it was 0.5 ns .. 1s was the FHE case
- josephg 1y ago
  You’re talking past each other. These are both valid descriptions of CRDTs - just different types of CRDTs. Generally there’s two categories of CRDTs: state based and operation based CRDTs. State based CRDTs are like a variable with is set to a new value each time it changes. (Think couchdb if you’ve used it). In that case, yes, you generally do update the whole value each time. Operation based CRDTs - used in things like text editing - are more complex, but like the parent said, deal with editing events. So long as a peer eventually gets all the events, they can merge them together into the resulting document state. CRDTs have a correctness criteria that the same set of operations always merges into the same document, on all peers, regardless of the order you get the messages. Anyway, I think the parent comment is right here. If you want efficient E2E encryption, using an operation based crdt is probably a better choice.
clawlor 1y ago
There are variants of CRDTs where each change is only a state delta, or each change is described in terms of operations performed, which don't require sending the entire state for each change.
blamestross 1y ago
> Which means it would need to sending and receiving the entire state of the CRDT with each change. > If the friend is online then sending operations is possible, because they can be decrypted and merged. Or the user's client can flatten un-acked changes and tell the server to store that instead. It can just allways flatten until it hears back from a peer. The entire scenario is over-contrived. I wish they had just shown it off instead of making the lie of a justification.

killerstorm 1y ago

It's very common for CS and cryptography-adjacent papers to describe something impractical. Even more impractical than what you described - e.g. complexity of an attack is reduced from 2^250 to 2^230. The purpose of these papers is to map out what's possible, etc, which might at some point help with actual R&D.