Formal mathematical proofs on Byzantine inspired consensus dates back 1982 (“The Byzantine Generals Problem”, Lamport, Shostak & Pease). Insights directly applied to distributed consensus over a working prototype were first presented around 1999 (“Practical Byzantine Fault”, Castro & Liskov) and have suffered rebates and corrections few years later, around 2002 (“Proactive Byzantine Fault Tolerance and Proactive Recovery”, Castro & Liskov).
Now, on 2020, we still struggle to formally specify large-scale operational conditions for pBFT inspired mechanisms for Blockchain.
With our background on the field of Combinatorial Optimization Problems (“Optframe: a computational framework for combinatorial optimization problems”, Coelho et al.), we have being moving one step forward. But how far did we go?
A Mixed-Integer Programing Model has been recently announced by our team (NeoResearch) throughout a didactic example that discretizes NEO dBFT consensus. Facing NP-Hard problems is a task that requires the acceptance of imperfect results. However and hopefully, some minimization/maximization problems can still give hope to be optimally solved for testing consensus liveness and finality.
As far as we went with this model https://github.com/NeoResearch/milp_bft_failures_attacks/blob/master/dbft2.0/dbft2.0_Byz_Liveness.py, we noticed the following exponential behavior on the difficulty of the problem:
Besides trying to solve this relatively “small scale” problem, we still face the challenge of solving those questions for a generic case. In addition, the proposed mathematical formulas still can miss assumptions, avoiding or exaggerating on constraints.
What is the real difficulty? Below we are going to highlight crucial points that decisions makers, researchers and developers need to double think when drawing novel consensus mechanisms:
- Define the limitations in which malicious nodes can affect the network;
- On the other hand, introduce basic assumptions in which honest nodes are going to necessary follow.
Only based on these two points, the challenge can be set. On the mathematical model we need to define two sets of nodes: R_BYZ and R_OK, where the first one represents all byzantine nodes, and the later the honest ones.
A basic precaution when defining honest nodes behavior is:
Specify constraints that R_OK should follow is not a trivial task because it should not interfere on the free will of the global state (this point is of a delicate perspective because constraints can not force any convergence);
Usually, NP-Hard problems involves trillions of solving possibilities. Similarly, finding a specific atom among the whole universe can be seen as analogous as the difficulty of proofing optimality for some cases. But this does not scare us because we know that solving this problem might be an answer to one of the most peculiar question of our century: “Is P = NP”? Thus, let’s move carefully and compromise only with the tools that we currently posses.
In this sense, we would like to highlight, in our recent article “A MILP model for a Byzantine Fault Tolerant Blockchain Consensus”, online at https://www.mdpi.com/1999-5903/12/11/185, the recent achievement in developing this MILP model for dBFT 2.0, which is the basins for the development of dBFT 3.0, in which the specification can be found here https://github.com/NeoResearch/dbft3-specification.
Neo has established as a solid platform in which proposals for a core mechanism, such as its consensus, can not be done randomly and biased by peculiar modern mechanisms reported by the literature. Why would we pick an unproved asynchronous consensus as our core mechanism? Why to risk that if basic assumptions are not satisfied?
These trivial questions motivated us to keep simple. Thus, in order to keep designing improvements based on the most simplistic consensus that PBFT presents to be, we propose simple advances. For this reason, a trivial fallback primary is being now explored for dBFT 3.0 and discussions are starting to take place here https://github.com/neo-project/neo/issues/2029.