Snark: Eventual Consistent Consensus

Eventual consistency states that eventually all items will be consistent across a network. We have so far established that using zk-SNARKs we can prove how something happened, but not necessarily what happened.

Let’s consider Node A with transaction tx1, tx2, tx4 and Node B with tx1, tx2, tx3. If Node A applies tx1, tx2, and tx4 to state S1A it arrives at zk ZK124, and Node B applies tx1, tx2, and tx3 to state S1B it arrives at zk ZK123. The systems can be considered out of sync, however, as long as there isn’t a conflicting state (detailed later), then S1A will eventually receive tx3 and S1B will eventually receive tx4, and they will both be in ZK1234. This is eventual consistency.

In a honest environment the above is great to ensure parallel processing, since each node can simply process it’s own transactions with the assumption of eventually reaching mutual consistency.

So what happens when bad actor A sends tx10a with balance transfer from A to B to Node A and tx10b with balance transfer from A to C to Node B? We arrive in a conflicted state. Eventually tx10a arrives at B and tx10b at A, both feel their result is the most correct, so how is this resolved?

A few solutions are available, standard consensus protocol, Proof-of-Work, Byzantine (2/3+1), or a random consensus protocol where a judge is elected.

Option 1: PoW, every time we have a new state transition zk we attempt to mine it, if we successfully mine it, we broadcast it out to the rest, this will then need to contain the same transactions which were used to achieve the state transition, and essentially we are back at a block, not a block for a chain, but simply a block to agree on the zk. This also has the overhead that it needs to happen on every event. We want to design a solution where the overhead of consensus is only called when needed. If the system is performing correctly, there is no need to disrupt the flow.

Option 2: Nodes vote on the respective zk’s, as soon as one achieve 2/3+1 majority it becomes the primary. Elegant solution, but a slow process.

Option 3: Random node is elected to decide which block is more accurate, could also end up having different results and lead to a new conflicting state, calling in a new judge, until an arbitrator is found.

The problem with eventual consistency, is that at any given point in time, the nodes might not be in agreed consensus, they will eventually get there, but how do you arbitrate at any given point in time, without having the specific knowledge of that time?

At first design, we consider time. If we could incorporate time we could select the first of the two events. This seems like an easy solution, we incorporate time in the signing process and we take the event that was first processed by whichever Node. While this might resolve the issue 99.99% of events, a pure conflict possibility does still exist.

We could simply ignore it, wait for tx10a or tx10b to propagate through the entire system and see which one gains majority, but this increases Time To Finality.

We could discard both.

The question we are trying to solve, is which one to apply first. Should we hold up the whole system while we decide? Ideally, we could remove the conflicting transactions (and any connected transactions), continue processing in an eventually consistent manner, and then start conflict resolution on the malicious event.

https://snark.network