September 7, 2018

Scaling Consensus for Enterprise: Explaining the IBFT Algorithm

Consensus algorithms are one of the core innovations of blockchain, and yet also one of the most confusing. Satoshi Nakamoto created a version of Proof of Work (PoW) that was implemented as a means for simultaneously securing and validating Bitcoin transactions. The blockchain community has built on that core vision to create an alphabet soup of Proof of Stake (PoS), Proof of Authority (PoA), PBFT (Practical Byzantine Fault Tolerant), and many others that are all designed to build consensus in a distributed system, creating the single source of truth that makes blockchain so valuable.

IBFT (Istanbul Byzantine Fault Tolerant) is a consensus mechanism which is an alternative to Proof of Work in an Ethereum network. Like other algorithms, IBFT, and provides added benefits for enterprises, including settlement finality. IBFT was first implemented in Geth by Amis Technologies, and soon after implemented in Quorum.

Before getting into the operation of the IBFT consensus mechanism, it is worth mentioning when and why one would want to use IBFT. In a public blockchain, the short answer is likely that you probably would not. But when it comes to consortium or private blockchains, IBFT starts to look quite appealing.

The PoW algorithm is famously costly, in both hardware and electricity. This cost is intentional, to prevent anyone from easily taking over the network, and thus PoW is very suitable for situations with full decentralization where anyone (including attackers) can participate. Nodes in the consortium/private chains used by enterprises, however, are intrinsically more trusted than those in a public chain. As such, the PoW consensus mechanism may be overly burdensome, and other mechanisms may provide “enough” trust to run a distributed system.

Proof of Stake, likewise, may be less relevant for enterprises, because paying for gas is less important in a permissioned network. Since nodes do not (necessarily) need to maintain currency in the network, PoS would introduce extraneous requirements.

Considering these tradeoffs, Proof of Authority (PoA) emerges as a possible best solution, utilizing a system whereby nodes in the network are allocated the privilege of producing new blocks for the chain using a round-robin or other arbitrary system.

IBFT is one of the many flavours of PoA and provides the following benefits:

  • Immediate block finality. There’s only 1 block proposed at a given chain height. The single chain thus removes forking, uncle blocks, and the risk that a transaction may be “undone” once on the chain at a later time.
  • Reduced time between blocks. The effort needed to construct and validate blocks is significantly reduced (in particular with respect to PoW), greatly increasing the throughput of the chain.
  • High data integrity and fault tolerance. IBFT uses a group of validators to ensure the integrity of each block being proposed. A super-majority (~66%) of these validators are required to sign the block prior to insertion to the chain, making block forgery very difficult. The ‘leadership’ of the group also rotates over time — ensuring a faulty node cannot exert long term influence over the chain.
  • Operationally flexible. The group of validators can be modified in time, ensuring the group contains only full-trusted nodes.

Here we provided an overview of IBFT, in mostly non-technical terms. For some of the original proposals of IBFT, you can review the EIPs on GitHub:

For the rest of this article, we’ll explore IBFT’s more technical considerations, discussing many of the concepts found in the EIPs and that we have learned through our own research.

Note: IBFT code can also be found in a go-ethereum pull request #16385.

Operation

The IBFT consensus mechanism comprises the following components:

  1. PBFT inspired group consensus model.
  2. A process by which members can be added/removed from the validating group.

IBFT requires the Block Header to be (subtly) reworked to support all facets of the capability.

Group Consensus Model

Overview

IBFT uses a pool of validating nodes (Validators) operating on an Ethereum network to determine if a proposed block is suitable for addition to the chain.

One node of the Validators is arbitrarily selected as the Proposer and is responsible for constructing a block at the block-interval and sharing said block with the group. If a super-majority of the Validators deem the block to be valid it is added to the blockchain.

At the completion of the consensus round, the Validators may select a new Proposer which will be responsible for providing the candidate Block at the next block interval.

The consensus mechanism is a synchronised state machine which is responsible for ensuring all Validators append the same block to the chain at the same height.

If a block fails to insert, the Proposer is changed, and the process starts anew.

To ensure only one block can be appended to the state machine, IBFT prevents changing the proposed block once a super-majority of validators have agreed to its insertion (but not performed said work), this process is referred to as ‘Block Locking’.

The IBFT consensus mechanism offers system stability provided less than 1/3 of the validating nodes are behaving incorrectly (either due to being compromised or due to faulty code). I.e. to tolerate F faulty nodes the validation group must contain at least 3F + 1 nodes (more than this does not increase system integrity).

Note: Herein F implies the number of faulty nodes tolerated by the system.

State Machine

States

  1. Awaiting Proposal. Validator is waiting for a new block to be supplied by the current proposer. If the validator is the proposer for this round, they prepare the proposed block and transmit it in a pre-prepare message.
  2. Preparing. Has received a (valid) proposed block and notified validator-peers; is now waiting for validator-peers to notify their acceptance of the block.
  3. Ready. Has received validator-peer’s acceptance of block, and is waiting for them to be a in a similar position. At this stage the proposed block has been ‘locked-in’, and cannot be replaced until an attempt at insertion has been conducted.
  4. Round Change. The round timed out before consensus was reached or the block failed to insert. Wait for all validators to agree on the next round number.

Transitions

  1. Awaiting Proposal → Preparing. On reception of a new block (Preprepare message) from the proposer (i.e. the block is valid in its content, as is its proposed chain insertion point).
  2. Awaiting Proposal → Round Change. The received proposal was not a valid block according to a given set of rules (e.g. invalid proposer, incorrect round numbering).
  3. Preparing → Ready. On reception of 2F+1 notifications (Preparemessage) from validator-peers indicating the proposed block is suitable for insertion.
  4. Ready → Awaiting Proposal. On reception of 2F+1 notifications (Commit message) from validator-peers indicating they are ready to append the block to the chain. On transition, the process of appending the block to the chain is performed (success).
  5. Ready → Round Change. As per Ready->Awaiting Proposal, however, block insertion has failed.
  6. Round Change → Awaiting Proposal. 2F+1 of validators agree on the next round number to be used.

Note: All transitions into “RoundChange” result in the Validator transmitting a “RoundChange” message to its validator-peers.

Block Locking

IBFT mandates that forks shall not be created. To this end, once a block has been agreed upon by a majority (i.e. on entry to the Ready state) it becomes “locked in”.

This means no other blocks will be considered for insertion until an attempt to add this block to the chain has been attempted. Thus either the block is inserted successfully (once sufficient commit messages are received, either in this or subsequent rounds), or the block fails insertion, is discarded, and a new block is proposed at the current chain height.

Validation Group Membership

The members of the validation group may change over time through a voting mechanism. Members can be added or removed through a majority (Floor(N/2) + 1) vote; each vote is captured in the Block Header.

Each node in the network (including non-validating nodes) is responsible for tracking the vote tally for each validator to determine the current Validatorsand ensure signatures on mined blocks fall within the expected group.

Given each vote is contained in the Block Header, only the Proposer for a given round is able to cast a vote. Thus it is important, if nodes are to be added/removed in a timely fashion, that the Proposer role be updated on a regular basis.

Once a node reaches majority votes, they immediately join/leave the validator group.

IBFT recognises a Voting Epoch, which defines a point at which all votes which have not yet reached a majority are removed, forcing the voting tally to be restarted. This implies when tallying votes, Validators need only start at the most recent epoch. By default, the Voting Epoch occurs every 30,000 blocks.

Votes define a change of state (i.e. candidates get voted in, validators get voted out), not voting for a given node implies the Validator does not wish the node to change state (an explicit vote is not required to maintain the status quo).

Block Header Refactor

To support IBFT in Ethereum a number of changes must be made to the block headers. These changes include:

  • beneficiary: identifies the node for which a vote is being cast.
  • nonce: specifies the vote “direction” — AUTH or DROP.
  • mixHash: afixed magic number, identifying this block as being IBFT validated.
  • ommersHash: must be the hash of an empty set, as there are no ommer blocks when operating under IBFT.
  • timestamp: must be at least the parent block’s timestamp + block interval.
  • difficulty: must be filled with 0x0000000000000001.
  • extraData: contains IBFT specific data including List of Validator Addresses, ProposerSeal (identifies the proposer), CommittingSeals (list of the validators which reported ‘commit’ on this block).

As the list of CommittingSeals for each validator is (potentially) different, it is important that the block hash not include this information — i.e. even though two blocks have different CommittingSeals fields, they represent the same information (i.e. transactions etc. are identical).

Conclusion

In closing, IBFT is a Byzantine fault tolerant solution offering immediate transaction finality which reduces the required infrastructure that PoW demands.

While unlikely to be ever used on Ethereum mainnet (with the much wider, unknown set of participating actors), it offers substantial benefit when used on a private chain where the validator pool is trusted and held accountable; it provides an ideal solution for a chain with a fixed cadence and a predictable transaction processing rate.

The processes explored in this article give confidence that a network employing IBFT will be tolerant of Byzantine nodes and can be recovered should those nodes be seen to be exerting over control on the network.