Is commutativity a crippling limitation?

[theoreticalbts]

In the Freenet Manual here it says that "Contracts also outline how to merge two valid states...The contract defines a commutative monoid..." I don't understand monoids well enough to understand this sentence. But to me at least, this comment in the code is clearer, it says "state delta updates are commutative...the order in which...updates are applied should not affect the final state."

Commutativity seems like a massively important design decision that puts some pretty big limits on what kinds of contracts you can design.

For example, suppose you have a contract for publishing blog posts. For simplicity, let's assume all posts are kept in the state, and must be signed by a key. So far this works fine with commutativity: Basically the state is the union of all posts.

But what if you want to write a slightly fancier blog contract that allows you to revoke a posting key's privileges [1]? For example if Alice gives Bob posting privileges on Monday, Bob posts on Tuesday, Alice revokes Bob's key on Wednesday, and Bob posts again on Thursday. Then:

• Nodes that receive the updates in time order will have state showing Bob made 1 post (his second post will be rejected).
• Nodes that receive Thursday's update before Wednesday's will have state showing Bob made 2 posts (his second post will be accepted as it occurred before his key was revoked).

In general, if you reference current state when checking whether an update is allowed, you can get into this kind of situation. It seems like this kind of dynamic validity checking is forbidden [4] in Freenet, which in turn means a whole lot of useful applications are impossible to implement.

This sure seems like a very bad developer footgun: You come up with some reasonable-sounding feature (e.g. "key revocation"), the SDK doesn't stop you from implementing it, it sort-of-works on the live network with actual users... and only after it's been live for a while do you discover the numerous user reports of "well-it-sort-of-works-but-sort-of-doesn't" issues are caused by you accidentally making a fundamentally non-commutative feature, and can only really be solved by removing the feature (which can cause some bad problems, like making users very unhappy, completely breaking the value proposition of your app, etc.)

What commutativity means for contracts needs to be a lot more emphasized in the documentation. Especially if contract authors are expected to "make their contracts commutative" when commutativity violations lurk in the shadows of shiny attractive features, and there's no tooling to enforce that you don't accidentally write non-commutative contracts.

[1] There are legitimate technical / UX reasons you might want to do this: Transferring posting privileges between machines without needing to transfer or share keys, dealing with lost/compromised keys, or hot/cold setups.

[2] Implicitly I assume that, in addition to the set of posts, the fancier blog contract's state contains a list [3] of keys currently authorized to post. You would write to this key list in response to some special "add key" or "revoke key" update, and you would read from it to determine whether a post is allowed.

[3] You might not want to literally implement it as a list, a set / dictionary / some other data structure might be better for efficiency / scalability.

[4] Originally I wrote "architecturally forbidden" but the above-mentioned code comment further states "noncompliant behavior, such as failing to obey the commutativity rule, may result in the contract being deprioritized or removed from the p2p network." I take "MAY" here to mean that it's possible to write a non-commutative contract, and it's possible that non-commutative contract might "sort-of-work".

[ple1n]

IMHO, commutativity means that, with delta a, b and c applied in any order, you are guaranteed to get set {a, b, c} as a result.

To establish causal order, let's put hashes and make a chain of blocks, with the same set of blocks applied, it's guaranteed to get { head: blockN } as the resultant state.

In case of divergence, it just outputs { heads: [blockN, blockN'] }, because you can not further agree on a state without a consensus mechanism. You just treat this 'unresolved' thing as the contract state and it's fine.

No one prevents you from implementing a blockchain inside one or more contracts tho.

[sanity]

@theoreticalbts Good questions.

But what if you want to write a slightly fancier blog contract that allows you to revoke a posting key's privileges [1]? For example if Alice gives Bob posting privileges on Monday, Bob posts on Tuesday, Alice revokes Bob's key on Wednesday, and Bob posts again on Thursday. Then:

Nodes that receive the updates in time order will have state showing Bob made 1 post (his second post will be rejected). Nodes that receive Thursday's update before Wednesday's will have state showing Bob made 2 posts (his second post will be accepted as it occurred before his key was revoked).

The way you'd handle this is that the contract state would be something like:

struct Posts {
  permissions : Permissions, // Can be updated by blog owner
  posts : Vec<Post>,            // Limited to posts authorized in permissions
}

struct Permissions {
  version : u64,
  active_permissions : Vec<Permission>,
  owner_signature : Signature, // Authorizes this set of Permissions
}

struct Permission {
  author : PublicKey,
  authorized_from : DateTime,
  authorized_until : Option<DateTime>,
}

Now the contract will authorize posts by the author within the specified date range, and will remove any that aren't. The blog owner can modify the permissions at will allowing them to retroactively remove posts if they want to.

An abusive poster might forge timestamps on their posts so might make more sense to remove them completely than just limiting them to older posts, although this could be avoided by requiring posts be timestamped using a reliable timestamping service.

Does that address the problem you're raising?

What commutativity means for contracts needs to be a lot more emphasized in the documentation. Especially if contract authors are expected to "make their contracts commutative" when commutativity violations lurk in the shadows of shiny attractive features, and there's no tooling to enforce that you don't accidentally write non-commutative contracts.

I agree that this needs to be explained better - the current interface is designed to be very low-level for flexibility, but in time we will layer abstractions and conventions on top of it that will simplify things for contract developers.

[iduartgomez]

Good discussion.

In general, or in practice, all contracts/applications can behave in a commutative way in in a distributed network, as they need be by design and limitations imposed by the nature of such networks. The problem may be that in order to achieve this, you may need to layer on top a consensus mechanism, add watermarking and/or out of time event handling, etc. I don't think this is a fundamental limitation, at least for most applications out there, but is a floor on the complexity of developing such applications, whereas in a centralized server structure those kind of problems are easier to solve, or have been solved for the general case in a way which is transparent to most developers.

Whenever this kind of behavior is desired, it will require more complex implementations on top of the basic system to resolve commutativity, and indeed developers should be aware of this. The idea is though, that in the future, we will provide enough building blocks (essentially contracts/delegates or combinations of both) that can be reused by most app devs so they don't have to think too hard about this. A good working example of this will be the anti-flood token mechanism which is being worked on and used for the messaging app which will be soon merged in the main branch.

As we work out more building blocks and apps using them we will polish the building blocks and certain patterns will be made available as contracts for people to re-use hopefully. Agreed all this must be emphasized better though.