Tracking issue for the consensus research

[junha1]

Simperby's consensus MUST be implemented as a simple, safe, and live BFT algorithm.

Conditions

Here are some conditions and relaxations (compared to ordinary blockchain consensuses)

1. No need for slashing conditions. (No strong accountability needed)
2. Instant (one-block) finalization.
3. On-demand block production. (No empty blocks)
4. Consensus-level yes-or-no choice (This becomes trivial for an asynchronous consensus, as voting for 'reject' equals to the case in the asynchrony, where a node pretends that he's missing the block proposal (which, in fact, he dislikes) because of the network asynchrony.)
5. Fair chances of block-proposing right are NOT required. (stable leader is OK, and actually desired)
6. BFT threshold 1/3 is allowed to become smaller.
7. Synchrony assumptions is also OK to take.
8. There MUST be a support for the light client verification. (i.e., it must be based on cryptography, not some live observation protocol)

Tracked issues

• Make a summary for those leaderless BFTs #7
• Check how PBFT can be safe without lock mechanism #6
• Research tendermint-rs #5

[byeongjee]

NOTE: This is deprecated

After discussion with @junha1 , we have come up with a slight variation of Tendermint suitable for our use cases. I'm looking forward to comments and suggestions.

We propose Calmdermint (the name is subject to change), an optimized version of Tendermint which supports early termination of voting phases before timeout expirations and on-demand leader replacement. Thanks to the early termination feature, a long timeout interval, possibly a week, can be adopted, while providing reasonable performance under practical conditions. Thus, nodes can be kept offline for the most of time, preventing unnecessary network congestion and blowup of the chain size, but can make progress as soon as sufficient number of them decide to make progress. The algorithm is guaranteed to be safe when the portion of byzantine nodes is less than 1/3, and it is also guaranteed to be sufficiently fast and make progress (under some fairness assumptions) when the portion of byzantine nodes is less than 1/9. Note that the success of this algorithm heavily depends on the reliability of the leader, but it is practically offset by the stableness of the leader.

The following changes will be made to Tendermint consensus algorithm.

AS-IS

• The prevote phase is finished if
  • (1a) the node sees prevote messages from more than 2/3 nodes, and
  • (1b) the timeout is exceeded
• The precommit phase is finished if
  • (2a) the node sees precommit messages from more than 2/3 nodes, and
  • (2b) the timeout is exceeded
• The leader is changed for each height and round in round-robin fashion

TO-BE

For the sake of simplicity, we assume there are total $9f + 1$ nodes where at most $f$ of them are byzantine. (This can be easily generalized to nodes with nonuniform voting powers where the byzantine voting power is less than 1/9.)

• The prevote phase is finished if
  • the conditions (1a) and (1b) are met, or
  • the node sees $8f + 1$ prevotes either to the proposal or to nil (early termination condition $a$)
• In the case of early termination of prevote,
  • If $7f + 1$ (or more) of the $8f+1$ prevotes are to the proposal, the node precommits to the proposal
  • Otherwise, the node precommits to nil
• The precommit phase is finished if
  • the conditions (2a) and (2b) are met, or
  • the node sees $6f + 1$ precommits to the proposal (early termination condition $b$)
• The leader does not change as long as the round succeeds. If the round fails, the predesignated next leader starts a new round with a transaction setting itself as a new leader.

Rough explanation for the early termination logic

Suppose that a proposal is broadcasted by a leader. Assuming all non-byzantine nodes are willing to prevote (either to the proposal or to nil) before timeout is expired, the early termination condition $a$ is met because ther are at least $8f + 1$ non-byzantine nodes. If the early timeout condition $a$ is met and $7f + 1$ of the collected prevotes are to the proposal, it is guaranteed that at least $6f +1$ non-byzantine nodes prevoted to the proposal, since the number of prevotes from byzantine nodes is at most $f$. The early termination condition $b$ should be met as well because there are $6f + 1$ non-byzantine nodes willing to precommit to the proposal.

Note that the new fault threshold is $1/9$ . Let's see why it is the case. Suppose that $x$ of total nodes is byzantine (we can assume that $0 < x < 1/3$) and a proposal is broadcasted. Then, a node can wait for at most $1-x$ prevotes. Waiting for more than $1-x$ prevotes is not guaranted to terminate because $x$ byzantine nodes may not prevote. Next, given a collection of $1-x$ prevotes, if all good nodes agree on the proposal, we can expect to find $1 - 2x$ prevotes to the proposal because $x$ of the $1-x$ prevotes may have come from byzantine nodes. Similarly, given $1-2x$ prevotes to the proposal, one can assume that there are at least $1-3x$ non-byzantine nodes prevoted to the proposal (Note that the previous argument does not ensure that the $1-2x$ prevotes to the proposals are from non-byzantine nodes). Assuming all prevoted non-byzantine nodes precommit to what they have prevoted, $1 - 3x > 2/3$ (which is reduced to $x < 1/9$) holds since Tendermint requires more than $2/3$ precommits to ensure safety.

One weakness of this algorithm is that the proposal phase is not subject to early termination. One might infer from this that a byzantine leader may severely degrade the performance of the entire system by not proposing a block when it is expected to do so, but the risk is offset by the adoption of on-demand leader replacement. Once the leader role is assigned to a responsible node, it will serve the role for a long time, as long as it pleases other nodes. If the leader is unsatisfactory, it can always be replaced, though it might require waiting for a possibly long — but certainly realizable — timeout condition.

The bottom line is that we have introduced the safe threshold for early termination by weakening the fault threshold of the consensus, which is acceptable in our use cases.

[byeongjee]

Summary

After further revision, we come up with Vetomint, which is a variation of Tendermint consensus algorithm that supports preference-based voting on the consensus layer. Unlike Tendermint which requires validators to decide on a block based soley on its validity, participants of a Vetomint consensus system may choose to accept or reject a block based on their preferences. This allows flexibility on the choice of agendas that can be handled by the blockchain system. We have revised the early termination feature of the consensus algorithm to achieve the goal without performance loss, which is critical in our use case where the timeout interval is significant. Vetomint guarantees safety and liveness under less than 1/6 byzantine voting power and an assumption that innocent nodes will eventually agree on a proposal in a unanimous manner.

Limitations of Tendermint

Although Tendermint adopts a voting-like procedure to achieve byzantine fault tolerance, it is not designed to support decision-making with preferences. That is, Tendermint requires a shared, deterministic oracle between all innocent participants to determine whether a proposal is acceptable or not, and the preference of each node has nothing to do with this process. This is the case for typical blockchain systems, where whether a proposal block is valid or not is determined soley by the current state of the blockchain and the content of the block. In such systems, validators play the role of "validator", not a participant of a democratic system.

However, in reality, we need votes in order to make a unified decision over multiple possible preferences, which cannot be done in Tendermint. For example, a presidential election has no notion of correctness; it is a matter of preference.

Note that one may implement a governance protocol on top of the consensus layer, but it brings extra complexity to the system, especially in our simple use case where voters and validators are indistinguishable.

Improvement

The main obstacle with using Tendermint for preference-based voting is that the prevote step of Tendermint may fall into a deadlock-like state, a stuck state that can be resolved only through waiting for a timeout expiration, if votes are split. For example, if half of the validators prevote to a proposal while the other half prevote to nil (i.e. they used veto), nothing but timeout rules can make progress. This is especially problematic for us because we want to adopt a long timeout interval, to reduce traffic and allow nodes to be kept offline for the most of time.

Augmenting the Tendermint protocol with an early termination rule requires lowering the byzantine threshold. This is because there must be a buffer threshold between 2/3 and 1 so that a node can early terminate a prevote step if it receives prevote messages exceeding the buffer threshold. Note that 2/3 should not be used for the threshold for early termination, because it allows a single byzantine node to disturb the consensus on an unanimously agreed proposal. We discovered that 5/6 is the desired threshold.

The pseudocode of the algorithm can be found here.
vetomint.pdf

[junha1]

We completed the research about our consensus protocol