[aleqs]

Very cool project!

> We've developed a unique (AFAIK) solution to the consistency problem, every contract must define a "merge" operation for the contract's associated state. This operation must be commutative, meaning that you can merge multiple states in any order and you'll get the same end result.

Where can I learn more about this? How is this different from CRDTs/CmRDTs?

[sanity]

> Very cool project!

Thank you!

> Where can I learn more about this?

If you don't mind watching a video I gave this talk back in March that should be fairly comprehensive: https://youtu.be/3SxNBz1VTE0?si=R4ifrsfEUJfvjDPx

If you would prefer an article I recommend: https://freenet.org/about/news/summary-delta-sync/

> How is this different from CRDTs/CmRDTs?

It's very closely related, you can view Freenet contract state as a CmRDT, where the details of the merge operation are specified in the webassembly contract.

[aleqs]

Thanks!

[dave1010uk]

It looks a lot like a CvRDT (i.e. a state-based CRDT).

They describe it as a commutative monoid, which means it has associativity and commutativity. CvRDTs also need idempotence, so they can handle duplicate data. Either they are idempotent too (which would make it semilattice-like), or the network protocol handles the deduplication outside of the data itself.

Letting the payload/application define the merge operation is clever. I assume it would mean contracts could opt in to idempotency if it doesn't already exist.

The other bit Freenet has added is doing all this with DHT routing and subscriptions, rather than a more basic peer mesh. This is very different to a blockchain and means it probably isn't suited for anything transactional.

[sanity]

This is broadly correct.

> CvRDTs also need idempotence, so they can handle duplicate data. Either they are idempotent too (which would make it semilattice-like), or the network protocol handles the deduplication outside of the data itself.

Freenet's summary/delta synchronization mechanism implicitly disregards duplicate updates. The idea is that a peer A creates a "summary" of a contract's state which is sent to the other peer B which then creates a "delta", which contains anything in B's state that isn't in A's state. The delta is then sent from B to A bringing A's state up-to-date. Thus the contract defines a custom synchronization mechanism for its state which can be very efficient.

These summaries and deltas are just arbitrary bytes as far as the framework is concerned, their meaning is entirely up to the contract.

> The other bit Freenet has added is doing all this with DHT routing and subscriptions, rather than a more basic peer mesh. This is very different to a blockchain and means it probably isn't suited for anything transactional.

That's correct, Freenet doesn't guarantee a global consensus although in practice contract states will converge within a few seconds. This is good enough for applications like group chat and social networks but for a cryptocurrency you still need to solve the double-spend and global ordering problems.

[dtj1123]

I'm also curious about this. I don't understand how deletion and modification can be made commutative operations in a way that makes sense

[Groxx]

tombstones are sorta the default answer here (i.e. at simplest, you keep all data forever so you can merge correctly, but you hide anything where you've seen a tombstone after it).

but "makes sense" and ways to optimize that can change massively with context. e.g. for a chat app, as soon as you see "deleted message X", you can reasonably drop X and all past and future changes to X because they won't be shown by anyone (don't even need to sync them). if you do that with "deleted chars 87..93" in a text editor, past-edits that you receive in the future might affect the behavior (it might add chars before those, changing what that range means), so you can't simply forget those chars (e.g. an easy option is to replay all events that occur after an event syncs, but that means retaining all events forever). the semantics you choose and what you do with the data affect your outcomes a lot.

tbh this is one of the reasons I like the idea of a WASM-defined algorithm. no one algorithm will be "best" for all data, and the storage/computation/transmission savings can be extreme.

[sanity]

Exactly, well put.

[cassonmars]

For a basic CRDT set, merge rules have to have some kind of temporality basis in the messages such that commutativity is preserved. usually it's a timestamp, sometimes it's an unforgeable value like a hash, e.g. A: { "prev_hash": null, "content": "foobar" } B: { "prev_hash": "<hash of A>", "content": "foobarbaz" } C: { "prev_hash": "<hash of B>", "content": "foobaz" }

and when played out of order, it's guaranteed to resolve to foobaz eventually or immediately, depending on when messages are received

when you encounter the scenario of a fork, there's usually a fork resolution rule, e.g. D: { "prev_hash": "<hash of B>", "content": "foobazbar" }

to resolve C vs D, sort lexicographically, choose direction of sort order and pick first

When you have non-continuous data due to messages dropping, e.g. you have B and perhaps an E that builds on C, you can either use the same lexicographic rule, or make the hash basis a combination of timestamp and hash, so you get temporality and lineage.

As for deletes, you have either the single set approach of simply making the message content empty and that _is_ the delete, or you have the 2-phase sets, where there exists an add set and a delete set.

Quite a few ways to approach it, but commutativity can be readily preserved.

[sanity]

It depends on the nature of the data, for example in our group chat app River[1] it stores the most recent messages - deleting the oldest to make room for the newest as necessary. Banning a user will remove them from the members list along with their messages, and recently banned users are stored in a banned list (like a tombstone).

So there is no one approach to this, rather you design the approach based on the application, and since contracts are just webassembly they are extremely flexible.

[1] https://github.com/freenet/river