Home Coins NEO (NEO) On the difficulty of drawing proofs on byzantine consensus | by Vitor...

On the difficulty of drawing proofs on byzantine consensus | by Vitor Nazário Coelho | Neo Smart Economy | Oct, 2020


Vitor Nazário Coelho

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:

Exponential growth of discretized MILP models for dBFT 2.0

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.



Source link

- Advertisement -
Mr Bitcointe
Mr Bitcointehttps://www.bitcointe.com/
“Fact You Need To Know About Cryptocurrency - The first Bitcoin purchase was for pizza.” ― Mohsin Jameel
472FansLike
76FollowersFollow
4,567FollowersFollow
5,261FollowersFollow
1,553FollowersFollow
2,230SubscribersSubscribe
USD - United States Dollar
EUR
1.19
GBP
1.34
CHF
1.10
NOK
0.11
JPY
0.01
CAD
0.77
AUD
0.74

Most Popular

Cypherpunk Holdings becomes 9th largest public holder of Bitcoin

Cypherpunk Holdings (CSE:HODL), a privacy-focused Canadian investment company, has upped its stake in Bitcoin (BTC). The company disclosed Thursday that it has added 72.979...

BANANO Chess Tournament (50k BANANO Prize Pool!) | by Banano | Banano | Nov, 2020

BANANO is a DAG-based cryptocurrency with easy-to-use apps, distributed entirely for free through airdrops, faucets, and games. All happening in a fun, community-driven,...

Tendermint & Lunie: Extended Support for the Cosmos Hub | by Brian Luk | Nov, 2020

We were surprised and saddened to hear that Lunie plans on sunsetting their hosted services at the end of November. For those of...
bitcoin
Bitcoin (BTC) $ 17,155.61
ethereum
Ethereum (ETH) $ 519.97
ripple
XRP (XRP) $ 0.533716
tether
Tether (USDT) $ 1.00
bitcoin-cash
Bitcoin Cash (BCH) $ 270.53
bitcoin-cash-sv
Bitcoin SV (BSV) $ 164.25
litecoin
Litecoin (LTC) $ 70.88
eos
EOS (EOS) $ 2.93
binancecoin
Binance Coin (BNB) $ 28.14
okb
OKB (OKB) $ 5.39
tezos
Tezos (XTZ) $ 2.24
leo-token
LEO Token (LEO) $ 1.33
cardano
Cardano (ADA) $ 0.137782
monero
Monero (XMR) $ 119.50
stellar
Stellar (XLM) $ 0.167394
chainlink
Chainlink (LINK) $ 12.64
huobi-token
Huobi Token (HT) $ 4.08
tron
TRON (TRX) $ 0.029306
usd-coin
USD Coin (USDC) $ 1.00
dash
Dash (DASH) $ 92.19
neo
NEO (NEO) $ 17.17
iota
IOTA (MIOTA) $ 0.302462
nem
NEM (XEM) $ 0.159123
zcash
Zcash (ZEC) $ 70.14
maker
Maker (MKR) $ 527.59
paxos-standard
Paxos Standard (PAX) $ 1.01
ethereum-classic
Ethereum Classic (ETC) $ 6.09
vechain
VeChain (VET) $ 0.014361
true-usd
TrueUSD (TUSD) $ 1.00
ftx-token
FTX Token (FTT) $ 3.92
kucoin-shares
KuCoin Shares (KCS) $ 0.784560
waves
Waves (WAVES) $ 6.02