EBFT, an egalitarian BFT consensus framework, which enjoys the same level of simplicity as Nakamoto Consensus (NC), and meanwhile has finality as classic BFT protocols. To this end, EBFT combines the best of the two worlds from NC and BFT: the longest rule from NC and quorum voting from classic BFT. EBFT consists of two protocols: EBFT-Syn (in synchrony network) and EBFT-PSyn (in partial synchrony network). Due to the extreme simplicity, EBFT can be implemented atop any Nakamoto-style blockchains within modification of hundreds of lines of code.
The EBFT algorithm includes two protocols: EBFT-Syn in synchronous network and EBFT-PSyn in partially synchronous network. Both of them adhere to the Longest Certified Chain Rule (LCCR) for voting and proposing blocks. However, while EBFT-Syn commits blocks using 3Δ, EBFT-PSyn commits blocks through uniqueness announcement. Now we introduce some need preliminaries
Block. Block is a tuple
Vote. A vote 𝑣 of block 𝐵 is a tuple <ℎ, 𝑝𝑘, 𝜎>, where ℎ is the hash of the block 𝐵; 𝑝𝑘 is the node's public key; 𝜎 is a signature created by the node. If there is a set of 𝑓 + 1 (or 2f+1) signatures on a block B, then the quorum certificate (QC) of block B in EBFT-Syn (or EBFT-PSyn) is formed. When a node has a QC for a block, the block is certified. Each node keeps track of all signatures for all blocks and keeps updating certified blocks.
Block Tree. Blocks are chained by a sequence of hash references and certificates. A block 𝐵 is called a descendant of another block 𝐵′ if 𝐵 extends a chain including 𝐵′. Conversely, block 𝐵′ is an ancestor of block 𝐵. Two (distinct) blocks 𝐵 and 𝐵′ conflict if neither is a descendant of the other. Because of the possibility of conflicting blocks, each node maintains a block tree (referred to as 𝑏𝑙𝑜𝑐𝑘𝑇𝑟𝑒𝑒) of received blocks. In addition, certified blocks are ranked by their heights, and a certified block with the biggest height in the local 𝑏𝑙𝑜𝑐𝑘𝑇𝑟𝑒𝑒 is referred to as the highest certified block.
EBFT-Syn is a synchronous BFT protocol, in which the minority of nodes (f nodes out of 2f+1 nodes) are Byzantine, i.e., not following the protocol. In synchronous networks, there is a known upper bound Δ for all messages to be successfully delivered. EBFT-Syn includes three simple rules:
Block proposing. Nodes participate in the cryptographic lottery (as any PoW and PoS blockchains) to win the chance of producing blocks, which extend the longest path in the certified block tree.
Block voting. An honest node vote for a valid block that extend the longest path, and broadcast its vote and received block to other nodes. Meanwhile, it sets a 3Δ timer for this block (See our paper for why choosing a 3Δ timer). If a block is certified, it will be added to the block tree.
Block committing. If a timer of a block expires, and the node does not receive any blocks conflicting with this block, the node will commit this block and all uncommitted ancestor blocks.
EBFT-PSyn is a partially synchronous BFT protocol, in which one-third of nodes (f nodes out of 3f+1 nodes) are Byzantine. EBFT-PSyn use the same block proposing rule as EBFT-Syn.
Block voting. Like EBFT-Syn, an honest node vote for a valid block B that extend the longest path, and broadcast its vote and received block to other nodes. However, there are two type of votes decided by the parent block. If B's parent block is uniquely certified, the node can send a commit votes (comVote). Otherwise, it sends a witness vote (witVote). Note that for each block, a node only votes once, but a node can vote for multiple blocks at the same height. A block is certified with no less than 2𝑓 + 1 (regardless of the vote types).
Block committing. If a block has no less than 2𝑓 + 1 comVotes, it will commit all non-committed ancestor blocks of this block, excluding this block.