3 ms·

Here's a sample document: https://extensions.standardnotes.org/collab/doc/741ec80a-3667-46d4-b94d-6621fc2bf265#key=5e2b16147d1b344628b0e1eeb57219c97b4099d918ae6

by mobitar 10y ago

Here's a sample document: https://extensions.standardnotes.org/collab/doc/741ec80a-3667-46d4-b94d-6621fc2bf265#key=5e2b16147d1b344628b0e1eeb57219c97b4099d918ae63549685dbe00a2ea548 https://extensions.standardnotes.org/collab/doc/741ec80a-366... Source is available here: https://github.com/standardnotes/collab-editor https://github.com/standardnotes/collab-editor The editor relies on an impressive client-side library called ChainPad, which uses blockchains as inspiration for determining the authoritative document after conflicts or many simultaneous edits. Typically operational transformation algorithms and systems to manage conflicts are handled by the server, precluding the possibility for end-to-end encryption. However, ChainPad runs completely on the client-side, and is oblivious to the underlying text, thus allowing us to encrypt text client-side before broadcasting to other participants and the broadcast server. This is the first major effort I've seen for a real time client-side collaboration algorithm, and its use of a blockchain type structure is ingenious. More info on ChainPad here: https://github.com/xwiki-contrib/chainpad https://github.com/xwiki-contrib/chainpad

josephg 10y ago
Thanks for the explanation. Looks like its not just E2E encrypted but distributed as well. Very cool work! However, you shouldn't need a blockchain to make a fully encrypted realtime collaborative editor. Here the blockchain is needed to make OT work properly because OT relies on a global ordering of operations. But algorithmically you can get around that either using CRDTs or modifying OT with a purge() function. (This lets you move between any valid linearisation of history, so you can transform by rewriting your history to look like the remote client before accepting their operation.) I've been messing around with OT stuff for a few years. Feel free to pick my brain if you have any questions - I'm looking forward to seeing where you go with it! (Grab my email from a commit on github)
- simplify 10y ago
  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
- mobitar 10y ago
  Interesting, will keep that in mind, thanks.
- teraflop 10y ago
  Based on the design document for ChainPad, it seems like it would be more accurate to describe it as a fancy CRDT as opposed to a blockchain. It doesn't include mining or any of Bitcoin's incentive mechanisms, so it doesn't inherit either Bitcoin's security benefits or its scalability/efficiency shortcomings.
  - skrebbel 10y ago
    Isn't "blockchain" just a fancy CDRT too? :)
    - KirinDave 10y ago
      No! Blockchains guarantee total ordering of events, but CRDTs are designed so that ordering doesn't matter and so long as all updates reach all nodes in the system (in any order) everyone agrees on the result. In some cases (e.g., a monotonically growing list) you can use both. But the way a blockchain handles conflict and the way CRDTs handle conflict is quite different.
      - skrebbel 10y ago
        Thanks for clearing that up. I thought the distributed nature of blockchain implied something unordered but clearly I was wrong :-)
        KirinDave 10y ago
        For things like not letting you overspend an account, blockchains are better (CRDTs exist to do this but have some undesirable properties). There exist a startlingly low number of cases where a CRDT expressing strong eventual consistency doesn't cut it, though.
- KirinDave 10y ago
  I asked about this in another thread. It seems like all the blockchain does in this scenario is allow colliding edits to be detected for a fast retry. In an environment with slow network I don't see how this would work well. If that's the case, something like treedoc[1] is prescribed and it renders the blockchain part of this irrelevant unless we're concerned about sourcing edits (which treedoc or a similar CRDT would be entirely amenable to and even appreciate). I was sort of hoping that there was something I didn't understand about the algorithm that helped here. Also, what is "OT stuff"?
  - davidbanham 10y ago
    Operational Transform stuff. It's what makes Google Wave chooch and is also the heart of sharejs.
    - KirinDave 10y ago
      Thanks. Yeah I finally realized that's what people were talking about. I don't entirely understand the appeal in 2017, it seems like it gives worse performance, worse guarantees, and is more complex than the equivalent CRDT.
eps 10y ago
> Here's a sample document Looks broken on Mobile Safari. "Viewing URL" and "Editing URL" are both empty, there's a blank two-line textarea and that's about it.

by mobitar 10y ago

josephg 10y ago

Thanks for the explanation. Looks like its not just E2E encrypted but distributed as well. Very cool work! However, you shouldn't need a blockchain to make a fully encrypted realtime collaborative editor. Here the blockchain is needed to make OT work properly because OT relies on a global ordering of operations. But algorithmically you can get around that either using CRDTs or modifying OT with a purge() function. (This lets you move between any valid linearisation of history, so you can transform by rewriting your history to look like the remote client before accepting their operation.) I've been messing around with OT stuff for a few years. Feel free to pick my brain if you have any questions - I'm looking forward to seeing where you go with it! (Grab my email from a commit on github)

simplify 10y ago
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
mobitar 10y ago
Interesting, will keep that in mind, thanks.
teraflop 10y ago
Based on the design document for ChainPad, it seems like it would be more accurate to describe it as a fancy CRDT as opposed to a blockchain. It doesn't include mining or any of Bitcoin's incentive mechanisms, so it doesn't inherit either Bitcoin's security benefits or its scalability/efficiency shortcomings.
- skrebbel 10y ago
  Isn't "blockchain" just a fancy CDRT too? :)
  - KirinDave 10y ago
    No! Blockchains guarantee total ordering of events, but CRDTs are designed so that ordering doesn't matter and so long as all updates reach all nodes in the system (in any order) everyone agrees on the result. In some cases (e.g., a monotonically growing list) you can use both. But the way a blockchain handles conflict and the way CRDTs handle conflict is quite different.
    - skrebbel 10y ago
      Thanks for clearing that up. I thought the distributed nature of blockchain implied something unordered but clearly I was wrong :-)
      - KirinDave 10y ago
        For things like not letting you overspend an account, blockchains are better (CRDTs exist to do this but have some undesirable properties). There exist a startlingly low number of cases where a CRDT expressing strong eventual consistency doesn't cut it, though.
KirinDave 10y ago
I asked about this in another thread. It seems like all the blockchain does in this scenario is allow colliding edits to be detected for a fast retry. In an environment with slow network I don't see how this would work well. If that's the case, something like treedoc[1] is prescribed and it renders the blockchain part of this irrelevant unless we're concerned about sourcing edits (which treedoc or a similar CRDT would be entirely amenable to and even appreciate). I was sort of hoping that there was something I didn't understand about the algorithm that helped here. Also, what is "OT stuff"?
- davidbanham 10y ago
  Operational Transform stuff. It's what makes Google Wave chooch and is also the heart of sharejs.
  - KirinDave 10y ago
    Thanks. Yeah I finally realized that's what people were talking about. I don't entirely understand the appeal in 2017, it seems like it gives worse performance, worse guarantees, and is more complex than the equivalent CRDT.

eps 10y ago

> Here's a sample document Looks broken on Mobile Safari. "Viewing URL" and "Editing URL" are both empty, there's a blank two-line textarea and that's about it.