Ensure, in a generic way, consensus about Vuex state

[taoeffect]

Problem

See #811 for an introduction to this problem.

Solution

Research methods for clients to come to consensus about what the Vuex state should be. Then do a full resync automatically if a client notices it's out of consensus.

Some inspiring non-solutions:

• https://replicache.dev/
• https://docs.kinto-storage.org/en/latest/
• https://github.com/automerge/automerge

Some possible real solutions:

• CONSENSUS_V1: In each message, have a vote on hashes representing the Vuex state of a particular message (starting with the very first). When there are votes from a quorum of at least 3 different users, each client checks the tally and the hash (representing the state at the start of the most recent round of voting) with the most votes is considered the correct state. Any clients with a different hash for that point in time will do a full resync from the latest checkpoint (#354).

  "votes": {
    "hash1": ["user1"],
    "hash2": ["user2"]
  }

  • 1v1: The above shows a 1v1 situation. In a 1v1 situation, nothing happens, everyone proceeds as normal. The loser of this one must resync (see below).
  • 2v0: If you are about to send a different hash, that means you must resync (and reset, i.e. re-register any contracts, etc, maybe via a page refresh) the chain, before sending it. If you've resynced, and still have a different hash, the chain is deadlocked for you at that point. There is no point in sending a message to people who disagree with you about the state.
  • 2v1: This state can legitimately occur after a 1v1 has occurred. From that point on, the majority hash is taken as the correct hash, and everyone who disagrees must perform a resync. If they still disagree after that point, they cannot participate anymore. Potential recourses include the recovery page (#761) where you can upload your version of events to a different instance of the group, while simultaneously kicking out the two dissenters.
  • 3v0: The most common scenario. This resets the state to be voted against to the state as it exists after the processing of this message, and voting begins anew.

There's also the challenge of ensuring the same serialization of the Vuex state across platforms since JSON hashing is non-deterministic. We can create our own custom transformation function that uses alphabetical ordering of keys (loop through keys, sort them, then create a string out of them plus their value, concatenate all these strings, and pass through a hash function).

Random links

• Paxos vs Raft

Edit: promising solution

This page outlines a way for consensus to be achieved over state snapshots (#354): https://gitlab.okturtles.org/okturtles/group-income-simple/-/wikis/State-Snapshots-and-Consensus

[taoeffect]

We can create our own custom transformation function that uses alphabetical ordering of keys (loop through keys, sort them, then create a string out of them plus their value, concatenate all these strings, and pass through a hash function).

In order to keep the resulting string the same across as many future platforms as possible, we need to also take into consideration that "math keeps changing". What this means in practice is that we should take special care for encoding certain types, especially doubles. For example, different languages might use different levels of precision for storing decimal values. To be safe therefore, we should consider storing only the two decimals (rounded to the second decimal), and consider any potential consequences of doing this.

Note that the storage method will need to be consistent, so decisions about whether 13 is stored as 13 or 13.00 need to be made as well, and stuck to.

[taoeffect]

Note that the storage method will need to be consistent, so decisions about whether 13 is stored as 13 or 13.00 need to be made as well, and stuck to.

Another possibility is to eliminate the use of number entirely and store all number values as string. This will allow arbitrary decimal places and should work across all platforms.

EDIT: There are several problems with that:

1. That might break some of the bindings we have in the UI which expect the Vuex data to contain numbers... (e.g. sliders, pie charts, etc...) so care would have to be taken to use this approach.
2. It doesn't address the root problem, which is that math calculations can result in different values past a certain number of decimal places, leading to consensus breakage. So we must limit math operations to a smallish number of decimal places by rounding using either toFixed or toPrecision

[taoeffect]

A potential concern with the entire idea of having consensus over the entire contract state is that it will require different implementations to store contract data in the same exact way.

That would represent a break from our current more flexible approach that gives implementations more leeway in how they store and process data.

In some sense, if we want in-protocol consensus, we may have to switch away from our ad-hoc data-driven contracts to something much stricter and more VM-like, or we would have to specify ourselves as part of the protocol exactly how state must be stored.

See related issue #475.