Articles and materials (open source) : Github

Terminology:

  • Validator: Validator of the block
  • Proposer: One of the block verifiers chosen to block
  • Round: Indicates the number of rounds of consensus. In a round, the Proposer starts with a block proposal and ends with a block submission.
  • Proposal: New block generation Proposal
  • Sequence: indicates the Sequence number of the proposal. The current sequence number is greater than the previous one; The block height is the proposed serial number.
  • Backlog: Store future consensus messages
  • Round State: Indicates the consensus messages of a specific sequence and Round, including pre-prepare, prepare, and COMMIT messages.
  • Consensus Proof: Block signature used to prove that the block has been processed by Consensus
  • Snapshot: Validator voting status in the previous period

Consensus

A Proposer must continuously generate block prorosal for consensus in every round.

The Istanbul BFT consists of three phases of understanding: pre-prepare, PREPARE, and COMMIT.

Fault-tolerant mechanism: N = 3F +1; N indicates the verification node, and F indicates the error node.

A validator will be selected as a proposer before each round in a loop. Then the proposer will make a new block proposal and broadcast the pre-prepare message. Once the pre-prepare message is received, the Validators will enter the pre-Prepared phase and broadcast the Prepare message. This step is to ensure that validators run in the same sequence and in the same round. When the Prepare message of 2F+1 is received, validators enters Prepared and broadcasts the COMMIT message. This step is to notify the other nodes to accept the proposed block and insert the block into the chain. Finally, the Validator waits for the 2F + 1 COMMIT message to enter the COMMITTED state, and then inserts the block into the chain.

Note: Blocks in Istanbul are final, not forked, and any valid block must be somewhere in the main chain.

To prevent the failed node from generating entirely different chains from the main chain, each validator appends 2F + 1 received COMMIT signatures to the extraData field in the header and then inserts them into the chain, so the blocks are self-validating and can support light clients as well. However, dynamic extraData can cause problems with block hashing. Because the same block from different validators can have different sets of COMMIT signatures, the same block can also have different block hashes. To solve this problem, we calculate the block hash by excluding the COMMIT signature part. Therefore, we can still maintain block/block hash consistency and put consensus proof in the bulk.

Consensus states

Istanbul BFT is a state machine replication algorithm. Each validator maintains a copy of the state machine for block consistency.

States:

  • NEW ROUND: Proposer sends a new block proposal. The Validator waits for the pre-prepare message.
  • PRE-PREPARED: The validator receives the pre-PREPARE message and broadcasts the PREPARE message. It then waits for 2F + 1 PREFARE or COMMIT messages.
  • PREPARED: The validator has received 2F + 1 PREPARE messages and broadcasts a COMMIT message. It then waits for the 2F + 1 COMMIT message.
  • COMMITTED: The validator has received 2F + 1 COMMIT messages and is able to insert the proposed block into the blockchain.
  • FINAL COMMITTED: The new block has been successfully inserted into the blockchain and the Validator is ready for the next round.
  • ROUND CHANGE: the validator is waiting for 2F + 1 ROUND CHANGE messages on the same suggested number of rounds.

State transitions

  • NEW ROUND -> PRE-PREPARED:
    • Proposer collects deals from TXPool
    • A Proposer generates a block proposal and broadcasts it to the verifier. Then it enters the pre-prepared state.
    • Each validator enters pre-prepared after receiving a pre-prepare message with the following conditions:
      • Block proposals come from valid sponsors.
      • He effective
      • The sequence and round of block proposals match the status of the Validator
    • ValidatorradioPREPAREMessage to other Validators
  • PRE-PREPARED -> PREPARED:
    • The Validator receives 2F + 1 valid PREPARE messages to enter the PREPARED state. A valid message meets the following conditions:
      • Matches sequence and round
      • Matching block hash
      • The message is from known Validators
  • COMMITTED -> FINAL COMMITTED:
    • The Validator puts 2F+1 submitted signatures into the extraData and attempts to chain the blocks
    • After the Validator is successfully inserted, the Validator enters the FINAL COMMITTED state.
  • FINAL COMMITTED -> NEW ROUND:
    • The validator selects a new proposer and starts a new Round Timer.

Round change flow

  • Three conditions will trigger a ROUND CHANGE
    • The Round change timer expires. Procedure
    • invalidPREPREPAREThe message
    • Block insertion failed
  • When the validator notices that one of the above conditions applies, it broadcasts a ROUND CHANGE message along with the suggested ROUND number and waits for ROUND CHANGE messages from the other validators. You are advised to set round Number based on the following conditions:
    • If the validator has received a ROUND CHANGE message from its peers, it selects the maximum ROUND number with F + 1 ROUND CHANGE messages.
    • Otherwise, it selects 1 + the current round number as the suggested number of rounds.
  • Every time the validator receives F + 1 ROUND CHANGE messages on the same suggested number of rounds, it compares the received messages to one of its own. If the number received is large, the validator will again broadcast a ROUND CHANGE message using the number received.
  • After receiving 2F + 1 Round CHANGE messages on the same suggested round number, the verifier exits the Round CHANGE loop, calculates NEW proposers, and enters the NEW round state.
  • Another condition for the validator to jump out of the Round Change loop is that it receives the validated block through peer synchronization.

Proposer selection

We currently support two strategies: round robin and sticky proposer.

  • Round robin: In a round-robin setting, the proposer will make changes in each block and Round change
  • A Sticky proposer: In a Sticky proposer, the proposal changes only if there is one round of changes.

Validator list voting

We use a verifier voting mechanism similar to Clique’s and copy most of Clique’s EIP. Each EPOCH transaction resets the validator vote, which means that if the authorization or deauthorization vote is still in progress, the voting process is terminated.

For all transaction blocks:

  • A Proposer can cast a vote to suggest changes to the list of proposers.
  • Only one verifier is retained for each target beneficiary’s latest proposal.
  • As the chain progresses, votes are counted in real time (allowing simultaneous motions).
  • Their proposals,VALIDATOR_LIMIT shall take effect immediately after reaching the majority consensus.
  • Invalid proposals are not penalized by simple client implementation.
  • For a proposal to take effect, all pending votes (yea and nay) on the proposal must be waived and begin with a Clean state

Future message and backlog

In an asynchronous network environment, messages can be received that cannot be processed in the future in the current state. For example, a validator can receive a COMMIT message on a NEW ROUND. We refer to such messages as “future messages”. When the validator receives a future message, it puts it in its to-do list and tries to process it as soon as possible.

Optimization

To speed up the consensus process, validators that receive a 2F + 1 COMMIT message before receiving a 2F + 1 PREFARE message jump to the COMMITTED state, so they don’t have to wait for further PREPARE messages.

Constants

We define the following constants:

  • EPOCH_LENGTH: Checks and resets the number of blocks after the pending vote.
    • Recommendation 30000 keeps Testnet similar to the major network ethash era.
  • REQUEST_TIMEOUT: Each agreed timeout before the round change is made in milliseconds.
  • BLOCK_PERIOD: The minimum timestamp difference (seconds) between two contiguous blocks.
  • PROPOSER_POLICY: The proposer selects the round robin policy. The default policy is round robin.
  • ISTANBUL_DIGESTFixed: the magic number, 0 mixDigest in bigger x63746963616c2062797a616e74696e65206661756c7420746f6c6572616e6365 used in Istanbul block recognition.
  • DEFAULT_DIFFICULTY: Default block difficulty, set to 0x0000000000000001.
  • EXTRA_VANITY: A fixed number of extra data prefix bytes are reserved for the proposer.
    • It is recommended to retain the current additional data capacity and/or the 32 bytes used.
  • NONCE_AUTH: Magic nonce Number 0xFFFFFFFFFFFFFF Votes to add a validator.
  • NONCE_DROP: Magic Nonce Number 0x0000000000000000 Votes to remove a validator
  • UNCLE_HASH: Always Keccak256 (RLP ([])) makes no sense as an uncle outside of PoW.
  • PREPREPARE_MSG_CODE: Fixed number 0. PREPREPARE Message code.
  • COMMIT_MSG_CODE: Fixed number 1. Message code of the COMMIT message.
  • ROUND_CHANGE_MSG_CODE: Fixed number 2. Message code of a ROUND CHANGE message.

We also define each of the following constants:

  • BLOCK_NUMBER: Block height in the chain, where the height of the generated block is 0.
  • N: Indicates the number of authorized authenticators.
  • F: The number of error validators allowed.
  • VALIDATOR_INDEX: Index of block validators in the sorted list of current authorization validators.
  • VALIDATOR_LIMIT: The number of verifiers that pass authorization or cancel authorization proposals.
    • It has to be the minimum (N / 2) + 1 to get a majority consensus on the chain.

Block header

We didn’t invent a new size for BFT Istanbul. Instead, we follow Clique to readjust the ethash header field as follows:

  • Secondary: Suggest changing the address of the validator list.

    • Should normally be filled in with zeros and only be modified when voting.
    • However, arbitrary values (even meaningless ones, such as voting for a non-verifier) are allowed to avoid additional complexity in the implementation of the voting mechanism.

  • Nonce: Proposer’s proposal for an account defined by the beneficiary domain.

    • It should be NONCE_DROP that recommends removing the authorized beneficiary as an existing verifier.
    • It should be NONCE_AUTH who recommends authorizing the beneficiary as the new verifier.
    • Must be filled with zero, NONCE_DROP or NONCE_AUTH

  • MixHash: fixed magic block identification number 0 x63746963616c2062797a616e74696e65206661756c7420746f6c6572616e6365 used in Istanbul

  • OmmersHash: It has to be UNCLE_HASH because uncle is meaningless outside of PoW.

  • Timestamp: Must be at least the parent timestamp + BLOCK_PERIOD

  • Difficulty: 0x0000000000000001 must be entered.

  • ExtraData: combination field of signer and RLP encoded Istanbul extraData, where Istanbul extraData contains a list of validators, proposer seal and commit seal. The additional data for Istanbul is defined as follows:

     type IstanbulExtra struct {
 	Validators    []common.Address 	//Validator addresses
 	Seal          []byte			//Proposer seal 65 bytes
 	CommittedSeal [][]byte			//Committed seal, 65 * len(Validators) bytes
 }
Copy the code

    ExtraData will therefore adopt EXTRA_VANITY | ISTANBUL_EXTRA among them in the form of | said used to separate the vanity and Istanbul additional data index of fixed (not the actual character delimiter).

    • The first EXTRA_VANITY byte (fixed) can contain vanity data for any proposer.
    • ISTANBUL_EXTRA byte is the rlp-encoded IstanbulExtra data calculated from RLP (IstanbulExtra), where RLP () is the RLP encoding function and IstanbulExtra is the IstanbulExtra data.
      • Validators: list of validators, which must be sorted in ascending order.
      • Seal: Indicates the header SEAL signature of the proposer.
      • CommittedSeal: a list of submitted signatures as proof of consensus

Block hash, proposer seal, and committed seals

The Istanbul block hash is different from the ethash block hash for the following reasons:

  1. The proposer needs to seal the proposer in the extraData to prove that the block is signed by the selected proposer.
  2. The verifier needs to include 2F + 1 submitted seals as consensus proof in extraData to prove that the block is consensus.

The computation is still similar to the ethash block hash computation, but we need to process the extraData. We calculate the fields as follows:

Proposer seal calculation

At the time of the proposer seal calculation, the committed seal is still unknown, so we calculate the seal against those unknown seals. The calculation is as follows:

  • Proposer seal: SignECDSA(Keccak256(RLP(Header)), PrivateKey)
  • PrivateKey(Proposer’s private key
  • Header: Same as ethash header, only extradata is different
  • extraData: vanity | RLP(IstanbulExtra)In IstanbulExtra.CommittedSealand Seal is an empty array.
Block hash calculation

When calculating the block hash, we need to exclude submitted seals because the data is dynamic between different validators. Therefore, we make CommittedSeal an empty array when we compute the hash. The calculation is as follows:

  • Header: Same as ethash header, only extradata is different
  • extraData: vanity | RLP(IstanbulExtra)In IstanbulExtra.CommittedSealand Seal is an empty array.
Consensus proof

Before inserting a block into the blockchain, each validator needs to collect 2F + 1 submitted seals from other validators to constitute a proof of consensus. Once it receives enough submission seals, it fills the CommittedSeal in IstanbulExtra, recalculates the extraData, and then inserts the block into the blockchain. Note that since submitted seals may vary from source to source, we exclude this section when calculating block hashes, as described in the previous section.

Committed seal calculation:

Committed SEAL is computed by the COMMIT_MSG_CODE message code of each signed hash’s validator and its private key. The calculation is as follows:

  • Committed seal: SignECDSA(Keccak256(CONCAT(Hash, COMMIT_MSG_CODE)), PrivateKey).
  • CONCAT(Hash, COMMIT_MSG_CODE): Connects block hash andCOMMIT_MSG_CODE bytes.
  • PrivateKey: The private key of the signer.

Block locking mechanism

Locking mechanism is introduced to address security issues. In general, when a proposer locks at a certain height H with block B, it can only propose B for height H. On the other hand, when the validator is locked, it can only vote for height H on B.

Lock

Lock Lock (B, H) contains a block and its height, which means that all of its validators are currently locked at some block B and height H. Below, we also use + for more and – for less. For example, a + 2/3 validator represents more than two-thirds of the validators, while a -1/3 validator represents less than one-third of the validators.

Lock and unlock

  • Lock: The validator is locked when it receives a “2F + 1” “PREPARE” message on block “B” of height “H”.
  • Unlock: The validator unlocks at height “H” and blocks block “B” if it fails to insert block “B” into the block chain.

Protocol (+ 2/3 validators are locked with Lock(B,H))

  • PRE-PREPARE:

    • Proposer:

      • In case 1, the proposer is locked: preprepare is broadcasted on B and the proposer enters PREPARED state.

      • Case 2, proposer is not locked: pre-prepare is broadcasted on block B’.

    • Validator:

      • Case 1, pre-prepare is received on an existing block: ignored.
        • Note: It will eventually result in a round change and the proposer will get the old block through synchronization.
      • In case 2, the validator is locked:
        • Case 2.1, pre-prepare received on B: Broadcast PREPARE on B
        • In case 2.2, receive pre-prepare: broadcast ROUND CHANGE on B’.
      • In case 3, the validator is not locked:
        • Case 3.1, receive pre-prepare on B: broadcast PREPARE on B
        • Case 3.2, receive pre-prepare on B’ : broadcast PREPARE on B’.
          • Note: Since +2/3 is locked in B and this will result in a comprehensive change, this consensus round will eventually make a comprehensive change.

  • PREPARE:

    • In case 1, the validator is locked:
      • In case 1.1, receive PREPARE on B: broadcast COMMIT on B and enter PREPARED state.
        • Note: This should not happen; it should skip this step and type PREPARED in the pre-prepare phase.
      • Case 1.2, received PREPARE: ignored on B’.
        • Note: there should not be a +1/3 PREPARE on B’, because +2/3 is locked on B. So a consensus round on B’ will cause the round to change. The validator cannot broadcast ROUND CHANGE directly here because the PREPARE message could be from a failed node.
    • In case 2, the validator is not locked:
      • Case 2.1, PREPARE received on B: wait for 2F + 1 PREPARE message on B
        • Note: Before receiving a 2F + 1 PREPARE message, it is likely to receive a 2F + 1 COMMIT message because +2/3 of the validators are locked at B. In this case, it jumps directly to the COMMITTED state.
      • Case 2.2, PREPARE received on B’ : wait for 2F + 1 PREPARE message on B’.
        • Note: This consensus will eventually get into round change since + 2/3 validators are locked on B and which would lead to round change.

  • COMMIT:

    • Verifier must be locked:
      • In case 1, the COMMIT: wait for 2F + 1 COMMIT message is received on B.
      • Case 2, B’ receives COMMIT: should not occur.

Locking cases

  • Round change:
    • Case 1, + 2/3 are locked:
      • If the proposer is locked, then B is recommended.
      • Otherwise it will put out B prime, but that will lead to another round of change.
      • Conclusion: In the end B will be committed by the honest verifier.
    • Case 2, + 1/3 to 2/3 are locked:
      • If the proposer is locked, then B is recommended.
      • Otherwise it’s going to factor out B prime. However, since + 1/3 is locked at B, no validator can receive 2F +1 PREPARE on B’, which means no validator can be locked at B’. In addition, those + 1/3 lock validators will not respond to B’ and eventually lead to overall changes.
      • Conclusion: In the end B will be committed by the honest verifier.
    • Case 3, A third - are locked:
      • If the proposal is locked, then B is recommended.
      • Otherwise it’s going to factor out B prime. If the +2/3 agree on B’, those locked -1/3 will get B’ by synchronization and move to the next height. Otherwise, there will be another round of changes.
      • Conclusion: It can be B or another block B’ that finally commits.
  • Round change caused by insert failure:
    • It would be one of those round of changes.
      • If the block is actually bad (cannot be inserted into the blockchain), the final +2/3 validator will unlock block B at H and attempt to suggest a new block B’.
      • If the block is good (it can be inserted into the blockchain), then it is still one of the above circular change cases.
  • -1/3 validators successfully insert block, but other validators successfully trigger loop changes, which means + 1/3 is still locked in lock (B, H)
    • Case 1, the proposer has inserted B: the proposer will propose B’ at H’, but + 1/3 is locked at B, so B’ will not pass consensus, which will eventually lead to a round change. Other validators will perform consensus on B or obtain B through synchronization.
    • In case 2, the proposer did not insert B:
      • Case 2.1, proposer is locked: proposer proposes B.
      • Case 2.2, proposer is not locked: proposer will propose B’ at H. The rest are the same as in case 1 above.
  • +1/3 validator successfully inserts block, -2/3 attempts to trigger round change at H
    • Case 1, the proposer has inserted B: the proposer will ‘propose B’ at H, but will not pass consensus until +1/3 has obtained B through synchronization.
    • In case 2, the proposer did not insert B:
      • Case 2.1, proposer is locked: proposer proposes B.
      • Case 2.2, proposer is not locked: proposer proposes B’ at H. The rest are the same as in case 1 above.
  • +2/3 validator successfully inserts block, -1/3 attempts to trigger circle change at H
    • Case 1, the proposer has inserted B: the proposer will ‘propose B’ at H, which may lead to a successful consensus. And then those minus 1/3 have to be synchronized to get to B.
    • In case 2, the proposer did not insert B:
      • Case 2.1, proposer is locked: proposer proposes B.
      • Case 2.2, proposer is not locked: proposer suggests B’ at H. Since +2/3 already has B at H, this round is going to change the round.

Gossip network

Traditionally, verifiers need to be tightly connected to achieve stable consensus results, which means that all verifiers need to be directly connected to each other; However, in the actual network environment, it is difficult to achieve a stable and constant P2P connection. To address this, THE Istanbul BFT has implemented the gossip network to overcome this restriction. In a gossip network environment, all validators need only a weak connection, which means that any two validators will be connected when they are connected directly or when there are one or more validators connected between them. Consensus messages are relayed between validators.