5 ms·

What's your opinion of ChainPad's algorithm? Are there any obvious downsides?

espadrine 10y ago
Intention preservation. Convergence, they get from the blockchain. So everyone eventually reaches the same content. But that content may delete a whole paragraph you just wrote, or duplicate it, or do any number of monstrous things, while your wifi was flaky. Make this test: open a document in two tabs, write "my test", go offline, write "is done" at the end in one, and delete "my" in the other, go online, wait for synchronization. You may see: "my test is donetestmy test i". Intention not preserved. (Just to be clear: this isn't just a problem for offline; network latency is dangerous.) So local changes (not yet sent to others) are rebased with an OT-style algorithm, although a seemingly faulty one. (OT is brutal to implement.) But it gets worse: > If a Patch is rooted in a previous state of the document which is not the Authoritative Document, the patch is stored in case it might be part of a fork of the patch-chain which proves longer than the chain which the engine currently is aware of. A blockchain is a type of Merkle tree. When the tree has two children, only the longest chain matters. So, you lose your work if someone forks the chain you were on and makes a ton of edits. Admittedly, you wouldn't give edit access to an untrusted party anyway. But that merely makes the security guarantees of the blockchain irrelevant! Reaching convergence is easy: you simply need total order. Use a Lamport timestamp and encrypt patches with your private key, and you get the same guarantees for a fraction of the cost and complexity of chainpad. If you want intention preservation too, there has been great efforts in OT to ensure the operations you make are applied in their intended way, so no deletion or duplication of content. (CRDT actually gets it for free, along with peer-to-peer, lucky them.) End-to-end encryption is not incompatible with either OT or CRDT; just encrypt your patches locally, and others can decrypt them with your public key. (It's probably much, much easier to implement with CRDT though, just because peer-to-peer OT is not trivial.) (Having read this, it probably comes across as more aggressive than planned. I am actually fairly impressed by chainpad: it is a fun and ambitious project. But I wouldn't trust it with data I don't want to lose.)
- KirinDave 10y ago
  Wow, the performance is worse than I thought in this.
- williamstein 10y ago
  I've spent a lot of time implementing realtime sync algorithms too, and I strongly agree with your comment above. I hope the CryptPad devs haven't gone too far down the rabbit hole of the CS literature, instead of reasoning carefully from first principles.

Intention preservation. Convergence, they get from the blockchain. So everyone eventually reaches the same content. But that content may delete a whole paragraph you just wrote, or duplicate it, or do any number of monstrous things, while your wifi was flaky. Make this test: open a document in two tabs, write "my test", go offline, write "is done" at the end in one, and delete "my" in the other, go online, wait for synchronization. You may see: "my test is donetestmy test i". Intention not preserved. (Just to be clear: this isn't just a problem for offline; network latency is dangerous.) So local changes (not yet sent to others) are rebased with an OT-style algorithm, although a seemingly faulty one. (OT is brutal to implement.) But it gets worse: > If a Patch is rooted in a previous state of the document which is not the Authoritative Document, the patch is stored in case it might be part of a fork of the patch-chain which proves longer than the chain which the engine currently is aware of. A blockchain is a type of Merkle tree. When the tree has two children, only the longest chain matters. So, you lose your work if someone forks the chain you were on and makes a ton of edits. Admittedly, you wouldn't give edit access to an untrusted party anyway. But that merely makes the security guarantees of the blockchain irrelevant! Reaching convergence is easy: you simply need total order. Use a Lamport timestamp and encrypt patches with your private key, and you get the same guarantees for a fraction of the cost and complexity of chainpad. If you want intention preservation too, there has been great efforts in OT to ensure the operations you make are applied in their intended way, so no deletion or duplication of content. (CRDT actually gets it for free, along with peer-to-peer, lucky them.) End-to-end encryption is not incompatible with either OT or CRDT; just encrypt your patches locally, and others can decrypt them with your public key. (It's probably much, much easier to implement with CRDT though, just because peer-to-peer OT is not trivial.) (Having read this, it probably comes across as more aggressive than planned. I am actually fairly impressed by chainpad: it is a fun and ambitious project. But I wouldn't trust it with data I don't want to lose.)

KirinDave 10y ago
Wow, the performance is worse than I thought in this.
williamstein 10y ago
I've spent a lot of time implementing realtime sync algorithms too, and I strongly agree with your comment above. I hope the CryptPad devs haven't gone too far down the rabbit hole of the CS literature, instead of reasoning carefully from first principles.