Implement VRF+BFT Consensus Algorithm

[tnasu]

Description

Replaces the Tendermint BFT with the VRF BFT algorithm. Tendermint's implementation of PoS only uses Proposer and Validators as election probabilities.

Stories

The details of each item should be written in their respective story or task tickets. This ticket is just a summary and its pointer. Please add stories and tasks as needed.

Design Policy

The proposals outlined below are specific to LINK Network v2 and ultimately any differences from the original Tendermint should be compiled into a public Wiki page.

• Election:
  • Random Election using Stake Amount as Discrete Distribution #22 Categorical distribution and Electing one producer and validator to use a binomial distribution #23 Binomial distribution have been proposed for random selection using VRF.
  • Report PoC of Election Algorithm PoC #30: For performance, stake conformance, and Byzantine tolerance, we decide to adopt the former.
• Reward: Proposal: Fair election and reward for validators #28, Change the consensus reward method  #35
  • It's better to take the lead on the Korean side as it's a decision related to expanding the scope of usage of our blockchain.
• Violation of Rules: Design for Various Rule Violation #39
  • The list of cases, and their penalties.
• Recovery:
  • Recovery Design with VRF #31: BFT-assumption violation is a common problem of PoS nature. We accept the Byzantine agreement and recover by VRF.
• Conformity:
  • Benchmark (processing time, memory usage) Report PoC of Election Algorithm PoC #30
  • Legitimacy of reward (t-test to verify the voting power whether it's proportional to the amount of stake) Report PoC of Election Algorithm PoC #30
  • BFT-assumption violation simulation (liveness and soundness of consensus) Report PoC of Election Algorithm PoC #30
• Genesis Round:
  • How to determine the first Proposer and Validators.
• Codename:
  • Nicknames that are easier to call and remain impressive (hopefully reflect key algorithm, such as "Raft").

Implementation

The VRF election may be divided into the following several points.

• Basic functionality: in crypto/vrf
  • Add VRF proof and output in proposal block #7: Introduce VRF capability into Tendermint. done Make it possible to call a VRF API implemented in Algorand's libsodium #1 Investigate Ed25519 Key Format Compatibility between Tendermint and libsodium #2.
  • Implements random election feature #32: Prepare election (random sampling) function.
  • Make VRF Interface and introduce additional library #40: Make VRF interface.
• Proposer Election: in PrivValidators, Modify the next Proposer to be selected based on VRF #3
  • Add VRF proof and output in proposal block #7: generate the next VRF hash and proof and put on the block.
  • Add functions to generate VRF Proof to PrivValidator-derived classes #6: replace the current round-robin election with one based on VRF.
• ValidatorSet Election: Election of ValidatorSet based on VRF #33
  • In addition to the Proposer in the initial release, should a ValidatorSet be elected by VRF. Review requirements.
  • If we do this, investigate whether it's possible to modify the ValidatorSet selection on the Cosmos side.
• Proposer/Validators Verification: Verify the Legitimacy of Proposer/ValidatorSet by VRF #34
  • Replace the block verifying to the VRF version.
• Rewarding:
  • It may need to do something with Cosmos SDK dealing with Stake.

Build CI environments

• CI environment: WIP on Add code coverage to CI #21, Random Election using Stake Amount as Discrete Distribution #22, and Report PoC of Election Algorithm PoC #30

Test

• Functional test
  • n-th Proposer does select the expected (n+1)-th Proposer and Validators.
  • the selected Proposer and Validators do play their respective role.
  • block generation does continue without a stall.
• Crash fault and recovery test
  • the system does recover normally in case the selected Proposer doesn't respond.
  • the system does work normally in case the number of selected non-failure Validators equals the quorum.
  • block generation for the round fails and the system does recover normally in case the number of selected non-failure Validators less than the quorum.
• Byzantine fault and recovery test
  • the Validators or P2P network do detect and recover correctly in case an unexpected Proposer worked.
  • the P2P network does detect and recover correctly in case an unexpected Validator worked.
• Performance test (practical evaluation)
  • compare with Tendermint's PoS and VRF consensus (it probably be slow due to increased computational complexity).
  • measure the performance against the number of Candidates (Nodes) and Validators.

Public Document

• New block format
• Concrete sequence chart or flow chart
• Fault recovery procedures

[zemyblue]

We need to implement how to process the penalty about voting violation via VRF consensus algorithm.

And we need a name that will simply call the new consensus algorithm. "VRF+BFT Consensus Algorithm" is too long.

[zemyblue]

Reward think #35 is more appropriate.