Consensus in simple words or "does decentralization play dice?"

What is the consensus protocol? Suppose we have a distributed system, consisting of independent actors (i.e. "decentralized"). Consensus protocol is used to get an answer to the core question: "How to update the state of the system? Who has the right to do it?"…

… and there are only three options available to achieve a consensus:

1. Anybody. The industry calls this option DAG – directed acyclic graph.

• High resistance to network failures
• Fast, unlimited number of participants
• An absence of the notion of the "current state of the system" as a whole: each participant has its own view on the state of affairs.

2. Participants must agree on each update: a family of Byzantine-fault tolerant (BFT) protocols coming from the last century and telecommunications industry.

• Low resistance to network failures
• Slow, very restricted number of participants (time required to reach the agreement growth polynomially or exponentially with the number of participants)
• There is a notion of the current state of the system at any moment of time (so-called "finality")

Frankly speaking dPoS consensus protocols (used in the family of Graphene-based blockchains, i.e. BitShares, Steem, Golos and recently EOS) with very strict number of participants (called there "witnesses"), which can update the global state of a system also belong to this group: such witnesses need to agree upon the order of the blocks. The dramatic speed of dPoS consensus does not contradict what was said above: it is achieved only by significantly compromising with decentralization.

3. Some "objective randomness" randomly points participant who can update the state at some point in time.

• Moderate resistance to network failures
• Moderate speed, independent or with sub-linear dependence on the number of participants.
• Quasi-finality: some recent historical state can be considered as final with some calculable (or nearly-calculable) probability.

Seems like the golden ratio! But wait, here is the problem: how we'll achieve a common view on the randomness in a system with independent agents/actors? If there were some "random" deterministic process that can be reproduced by all of the participants, it would not be random in fact by the very definition of "randomness" (which, basically, cannot be reproduced). And vice versa, a truly random process will give different (i.e. random) results for each participant…

Adam Back was the person who proposed a very elegant solution to this problem: instead of getting some common randomness we should use some random process that will give different random numbers to all of the participants, and we'll define some criteria by which only one (or very few) participants will be selected. How to achieve that? Let's use radioactive decay as a sample random process: each of the participants will take some small radioactive probe of a given size and will calculate the number alpha-particles each second; the one who will get the lowest number wins. It's a kind of dice, so the participant with the smallest number wins.

But here is another problem: how to prove that you really had the smallest number and not cheated with the size of the probe (by making it smaller) or just generating "0" out of thin air without counting at all? That's where the elegance of Adam Back's solution comes to place: he invented a process (called hashcash) where each of the participants can't cheat with their "dice". Those who are familiar with cryptography know about the existence of "hash functions", which can be easily computed one way and require really big effort to compute the other way. And if we ask all of the participants to find some number where hash can be smaller than some pre-defined value, (1) all of them will spend a lot of time doing that, (2) the one who finds the answer first will be doing that by a chance, which is strictly proportional to the number of his efforts/economic spending, (3) it can be easily proved that there is no cheating since it's really simple to re-check the result of the hash function once the solution is found. And this protocol became the famous Proof of Work used in bitcoin!

But wait, can we re-do the trick and find some other type of randomness, suitable for selection of player in multi-agent system, but without doing a lot of unnecessary computations? Past years have shown that it is not an easy task… At this moment there are no other succinct, provably secure and resistant in the presence of adversaries protocol for the distributed randomness (collective coin flipping) on the market … yet. And here our story of Prometheus protocol begins - we will unveil it in the following articles.