TRIVIAL
In a comment on last week’s dev update, @Antifragile linked a recent paper: “Byzantine Agreement, Made Trivial” from Silvio Micali, one of the authors of Algorand.
This paper describes a way to obtain Synchronous Binary Byzantine agreement without the need for a Common Coin. They replace it with a “Concrete Coin” which is a function that will behave like a Common Coin probabilistically often (~ 2/3 of the times).
They then split the decision process into rounds composed of three steps so that imperfect Concrete Coin is enough for reaching binary consensus.
The paper in itself presents, as advertised a rather trivial algorithm; partly because creating a Concrete Coin in a synchronous setting is indeed very easy, and partly because the three steps algorithm needed to converge with a weaker coin is also quite straightforward in a synchronous setting where we can simply wait to hear every node’s voice at each step.
For our asynchronous usecase, it is slightly less trivial, but we think it is possible and actually less difficult than getting a fully asynchronous Distributed Key Generation scheme to work for our decentralized use case. On a side note, we would like to thank @mav for his contributions to the DKG discussions.
We have spent some of the last few days devising an asynchronous Concrete Coin that we call: “gradient leadership based Concrete Coin”. We think that it exhibits all the properties needed for a Concrete Coin, but we removed all the synchrony assumptions from the process of obtaining it. We are in the process of formulating our suggestion precisely in our RFC, with associated mathematical proofs.
We are now tackling the second main challenge of mapping the ideas from “Byzantine Agreement, Made Trivial” to asynchronous consensus: integrating the Concrete Coin in the main protocol in place of a Common Coin.
We only started focusing our energy on this recently but are already seeing some promising leads.
While all this progress is being made on the algorithmic front, we are also continuing with our efforts of producing an RFC to explain the complete idea as clearly as possible, along with visual illustrations that should help convey our points more easily.
If and when we find a fully proven solution for the second challenge explained above, we will focus all our efforts into finalising the wording for the RFC and share it with the community.
We refer to this new adaptation of BOA as: Total Record of Incidents Via Interconnected Agreement Lattice (TRIVIAL) as an acknowledgement to the paper: “Byzantine Agreement, Made Trivial” that gave us the idea of trying to solve the problem without the need for a Common Coin.