Algorithmic Trust Anyone?

The crypto ecosystem is based on the following idea: it is possible to build « algorithmic » trust, resulting from a known and immutable algorithm (immutable at least for a reasonable amount of time). Better even if the algorithm is simple and cheap to implement.

The current “proof-of-work” engines behind major crypto-implementations (i.e. bitcoin and ethereum) satisfy almost those constraints. They are still very costly though, as they should — a trusted third-party draws its legitimacy from having something to lose. The alternative of a “proof-of-stake” consensus is building steam, with the hope of solving the cost issue. Someone claiming to be worthy of trust isn’t losing time and money anymore, he or she has skin in the game in the form of the currency or asset being mined. Is this possible? Yes, in principle. Let’s convince ourselves with the following game that will ravish parents in the assembly.

It is snack time, dad has prepared a succulent apple pie, but he is kind of fed up with his two children fighting over the biggest slice. He offers the following idea: one cuts the pie in two, the other gets to chose the slice he wants.

The children are the only ones involved in the process, none of them can cry foul against a dad easily suspected of partiality. Consensus is straighforward: whoever cuts first has a vested interest in respecting a 50/50 partition. That is the only way to meet one’s objective of getting the largest slice (or conversely not getting stuck with the smallest).

Can this algorithm be extended to 3 kids? Yes, absolutely. We need to note first that it takes 3 cuts to divide a pie in 3. If the kids are labelled #1, #2, and #3, they cut the pie one after the other, then pick a slice one after the other (in the same order).

#1 can cut anywhere, the first cut is irrelevant. Next comes #2, but we will come back to his case. #3 finds himself in front of a pie with two slices formed, he knows that no matter what he will be the last one to chose, there cannot be any doubt that he will be left with the smallest slice if there is one (this, by the way, indicates that the sequences for cutting and choosing do matter).

It is relatively simple to see that #3 faces the following decision tree:

• If the smallest of the slices in front of him is smaller than 1/3 of the pie, his interest is to cut a third slice equal to this smallest one. The pie has subsequently 3 slices, 2 of which are equal (and smaller than 1/3 of the pie)
• If the smallest slice is larger than 1/3, his interest is to cut the remainder of the pie in two equal parts.

In both cases #3 has no way to extract a slice larger than 1/3 of the pie. #2 may not have respected his part of the contract, yet #3 cannot benefit from it.

What about #2? Is it possible for him to get away with more than 1/3 of the pie? The answer is no. #1 and #3 hold together the way to sanction him: #3 has the power to “cut as a last resort”, and #1 will be the first to choose. Whatever #2 does, after #3 has analysed his decision tree, after #1 has chosen, all that is left is a plate with two equal slices of less than 1/3.

Let’s note here that this method works only if the pie is whole to start with: cutting an incomplete pie in 3 parts requires only 2 cuts.

What about 4 kids? Or any number of participants for that matter? Applying the same idea leads to the conclusion that the algorithm can be generalized. In essence, a participant is held in check by all the others who can cut or choose after him.

As it happens, this algorithm satisfies the constraints set out earlier: it is known, immutable (and independent of the number of participants), simple and very cheap to implement. It is an elegant “proof of stake” (with a variable stake , unknown at the onset of the game).

The purpose behind this (amusing?) exercise is more than just provide help to anxious parents (although I confess I use it regularly). Without any claim to universality, it does serve as a reminder of the major challenges behind a reasonably solid proof-of-stake trust engine:

• Rule enforcement: in the case above, dad is here to enforce the rules. In the case of a crypto-protocol, participants must be held to strict rules, known to all. In a digital world where a knife can be coded to cut only once, this doesn’t seem overly difficult.
• Task specific: the children have limited latitude — they can measure, cut and choose, nothing more. Given this limited set of actions, the algorithm is precisely tailored to the task. To the point that if the pie is not whole, it just doesn’t work anymore. A crypto algorithm shouldn’t have much difficulty fitting in: it is meant to accomplish a very specific task, certify a block.
• Transparency: in the case of a 4pm snack, all the children are present simultaneously, but in general that is not strictly necessary. Even if they are not in the same room at the same time, if rules are obeyed, the result is the same. More important is their access to information: a participant cannot perform his duty if he doesn’t have a full picture of the pie. In the case of 3 kids for example, it is very clear that #3 cannot sanction #2 if he doesn’t have access to the pie. Here again a crypto protocol would fare fairly well: a blockchain by definition incorporates its entire history, bringing full transparency to all (ignoring the time concurrency problems of blocks not yet certified, see next point also).
• Consensus propagation: in a version where all the children are around a table, consensus is reached fairly quickly. One can see however that the story is very different if physical presence is not required and even more if information about the state of the pie is not instantaneously disseminated. Synchronicity is indeed a significant requirement. Whether or not it is possible makes a massive difference.
• Robustness: this is the real weakness of this algorithm. If several of the kids collude, the consensus is worthless. If for example #1 and #2 are accomplices, #2 will cut a minuscule slice, #3 will reproduce this slice, and (#1 + #2) will in the end share almost the entire pie. #2 has no reason to act this way if he cannot claim his share of the loot (however #2 acting this way doesn’t necessarily mean that he colluded with someone).

Of all those elements, synchronicity and collusion are by far the trickiest. Indeed a result dating back to 1985 (“LFP Impossibility”) demonstrated that consensus was impossible to reach in the presence of faulty processes in an asynchronous setting. As for collusion, intriguingly it is receiving little attention from crypto-enthusiasts although it is already a known weakness of bitcoin and other blockchains…