“VB & Lamport’s 99% Fault Tolerant Consensus” explained by “DEATH NOTE”

VB uploaded “99% ” ,and now ,this is occupying brain resources of the top runners of Ethereum. They left 51% runners far behind when they published Plasma.
And this time,they are leaving 99% people far behind.(Recent Post)
I’m left behind either….

I want to get relaxed to talk about “99%”. This system has strange tx and consensus which is totally different from these of blockchain like Bitcoin, and supports new ways to make secure consensus.

[NOTICE] this page is on an education purpose in my math club. I refuse any profit purpose.

DEATH NOTE

In Tokyo, a high-school student named Light Yagami（月＝KIRA） finds a “Death Note”, a mysterious notebook which can kill anyone as long as the user knows both the target’s name and face.(wiki)

Why could he use this soon? Because the first page was “How To Use” explanation. It describes the rules. And the next page is Lamport’s Paper. It also describes how to make a consensus.

He took a look at Lamport’s Paper, and found a theorem.

There’s famous “Byzantine General Problem”Generals have to have a consensus “attack” or “retreat”,or nodes may die. There can be liars among them.

“””THEOREM 1. For any m, Algorithm OM (m ) satisfies conditions IC1 and IC2 if there are more than 3m generals and at most m traitors.”””

OM means the consensus algorithm which doesn’t use digital signature.
And this means,a consensus without signatures can accomplish 33% Fault Tolerant at most.
Simple explanation is this picture below.
These nodes have to have a consensus “attack” or “retreat”,or let one node die.

We can turn the problem of “a consensus among 3 nodes” to the problem of “commander and 2 lieutenant” consensus. They are same because the problem is whether or not they lie, not nodes’ choices . They can’t have a consensus if any liar. And this implies that 1/3 are liars, network cannot have a consensus without signatures.

Light(月) quit to read. And he thought blockchain is 50% Fault Tolerant because it’s using signature,but at most 50%, which is a widely recognized wrong idea.

Anyway, he started 51% attacks by using DEATH NOTE ,after he had known that this note also can operate people as he describes.

After his massacre of cryptos by 51% attacks, world was confused.

V could finally detect him to a certain extend,because he knew that blockchain is not maximum 50% Fault Tolerant and using signature for message(tx) makes PoXX totally different.

In Lamport’s paper, a consensus with signature can reach near 100% Fault Tolerant, if nodes broadcast back packets with their sign every time like this↓.

[NOTICE] “attack:0:1” means that “attack” message which was signed by node0 and node1.

“””THEOREM 4. For any m and d, if there are at most m traitors and the subgraph of loyal generals has diameter d,
then Algorithm SM(m + d -1) (with the above modification) solves the Byzantine Generals Problem.
”””

Holly Crap!!!??
Why are we using blockchain??
The answer is simple. This consensus is totally high cost and blockchain is relatively low cost. Most remarkable feature is that message(tx?) is signed by all relay nodes,which obviously make both of traceability and stress.

If we use this in a network of 30,000 nodes , it needs to wait 10,000 times as long time as that of 3 nodes network, and also needs exponential amount of signed messages which is said to be uncountable.This has bad scalability, simply because as well, this is a synchronous system, and blockchain is not.(I will explain this with CAP Theorem at last of this page)

Anyway V trapped Light（月） in a currency network in which every packet is signed.

Since then, Japan Police officers started to gather to V. And finally, he show himself in a rich hotel what he call HQ.

And he started to talk about his masterplan at “HQ”.
He thinks adding one more role to network consensus enhances that method which he did against Light（月） last time, and also written in Lamport’s paper.
He adds “observer” which is independent from validators.

First of all,at the last of Lamport’s algorithm, a node should finalize the “last message” and make sure no more message.

(3) For each i: When Lieutenant i will receive no more messages, he obeys the order choice( Vi).

He proposed introducing time-out to finalize it.
Then pls take a look at V’s plan. We see they can have a finalized consensus {x,y,z} on time-clock T+2D

Please make sure you understand that this consensus is among all nodes including dishonest nodes. The consensus “{x,y,w}” is including “w” which byzantine node sent.
This is necessary because dishonest byzantine node is not always malicious,they can be just out of order. Not every node is perfect.

Anyway, V introduced time-out to make a consensus securer.

In Vitalik’s page, this pattern is referred as a problem.

Suppose that a commander and some subset of `k` (malicious) validators produce a message `v : i[1] : .... : i[k]`, and broadcast it directly to some “victims” just before time `T + k * D`. The victims see the message as being “on time”, but when they rebroadcast it, it only reaches all honest consensus-participating nodes after `T + k * D`, and so all honest consensus-participating nodes reject it.

So Observer1 cannot sync the consensus even if he is a good node.
This seems to be difficult to understand why this is problem,because “Colluding nodes” can’t earn profits by this operation.
But the problem is that it’s easy to disturb the network with no risk & no cost.

Then V got obliged to fix this point.

VB goes on

But we can plug this hole. We require `D` to be a bound on two times network latency plus clock disparity. We then put a different timeout on observers: an observer accepts `v : i[1] : .... : i[k]`before time `T + (k - 0.5) * D`. Now, suppose an observer sees a message an accepts it. They will be able to broadcast it to an honest node before time `T + k * D`, and the honest node will issue the message with their signature attached, which will reach all other observers before time `T + (k + 0.5) * D`, the timeout for messages with `k+1` signatures.

This can make a consensus.
`Message v : i[1] : .... : i[k]` still cannot reach the Observer2 directly because of the time-out, but Observer2 can get it with one more sign if any honest node has this before the time-out.

To make such a condition,
(1) Observers do not sign,and just relays broadcast they accepted, D/2 earlier.

[NOTICE] in the pic above,Observer1 sends `v : i[1] : .... : i[k]` without his signature. Validators (including Honest Nodes) sign.

(2)Time-clock(time-out) should be divided to 2 pattern, for the sake of enabling the two roles of broadcasting ,no signing Observers and signing Nodes.

Then it seems that observers can sync each other ,and nodes can get information from observers like that way.
In principle, Fault Tolerant rate can reach near 100% when a network is big enough. If m is number of liar nodes,

Algorithm SM(m + d -1) solves the Byzantine Generals Problem.

Network consensus will get similar to this when there are many validators and latency is long enough that broadcast reaches every node.

CAP Theorem

There’s a limitation called CAP Theorem. These 3 below can’t coexist.
(1) Consistency: Every read receives the most recent write or an error

(2)Availability: Every request receives a (non-error) response — without guarantee that it contains the most recent write

(3)Partition tolerance: The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes

The fact that blockchain lacks of Cosistency(1) , is against our images of BC or Ethereum,called “common database” or “world computer”. But obviously P2P network doesn’t guarantee the newest data, you know.

But why is blockchain though to be useful and said to be a breakthrough?
Because lack of Consistency(1) is easily avoid in actual usage, in which people don’t demand the very newest data at second level. People compromise when this has consistency in 30 minutes and responds at most 30 minutes old data.
This called “Eventual Consistency”.

[SPECIAL NOTE] Lightening Network ,Plasma, and all of other off-chain scaling are chasing “Eventual Consistency” , pushing down apparent consistency(2) and get free from CAP limitation.

“99%” has strong consistency which can sacrifice Partition tolerance and maybe unable to endure network splits, as VB admits some cases are considerable.

>>>The 99% tolerance will not work simply because in the case of a network split it will lead to 100 different baby networks — very bad!
VB: Agree, hence why I described the hybrid mechanism, which can survive either a network split or >33% malicious, as long as both do not happen at the same time.

In my imagination, this seems to be cut out for limited scale consensuses like PoS, DPoS or PoA. I don’t know. I’ll keep on eye on posts.

Like what you read? Give Leona Hioki (日置 玲於奈 ) a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.