Background
Contemporary BFT (Byzantine Fault Tolerant) consensus protocols predominantly utilize leader-selection methods. This approach, however, has notable limitations: Firstly, it results in unbalanced bandwidth usage. The leader node must broadcast its block to the remaining n-1 validator nodes, demanding significant bandwidth. Contrastingly, these validator nodes only need to send less data-intensive messages, either broadcasting (as in PBFT protocols) or sending (as in HotStuff protocols). Consequently, the leader node faces considerable bandwidth strain, limiting the overall throughput of the consensus protocol. Meanwhile, the bandwidth capacity of other validator nodes remains underutilized. Secondly, leader-selection methods presuppose (semi-)synchronous network environments where messages sent by a sender are guaranteed to reach a receiver within a specific time frame. This assumption becomes problematic in globally dispersed blockchain networks, rendering the timely delivery of messages across all geographically distributed nodes impractical.
Inspiration
In 2015-2016, the Honey Badger (HB) BFT protocol emerged as a practical solution to these challenges. HB-BFT addresses these issues effectively: 1) Each node produces and broadcasts its own sub-block, ensuring optimal bandwidth utilization, especially in the Reliable Broadcast (RBC) phase. 2) To accommodate the asynchronous nature of network environments, HB-BFT incorporates the Asynchronous Binary Agreement (ABA) sub-protocol, introducing randomness to avoid "FLP impossiblity" probelm. It also employs the Asynchronous Common Subset (ACS) strategy for selecting a minimum of $2f+1$ sub-blocks from $2f+1$ nodes to achieve consensus. This innovative paradigm shift in BFT protocol design enhances scalability and security beyond the capabilities of traditional (semi-)synchronous BFT protocols.
Problems
Yet, Honey Badger BFT (HBBFT) and its derivatives are not without their flaws: 1) An HBBFT epoch consists of two distinct phases: $n$ concurrent Reliable Broadcast (RBC) instances, which are bandwidth-intensive, and $n$ concurrent Asynchronous Binary Agreement (ABA) instances, which are more bandwidth-efficient but time-consuming. For HBBFT to progress to the next epoch, it must fully complete the current one. This leads to a dichotomy within each epoch, oscillating between a bandwidth-heavy phase and a more efficient but slower phase. Consequently, this results in underutilized bandwidth during the ABA phase.
2) A significant challenge arises in the RBC (or Consistent Broadcast, CBC) phase, characterized by its $O(n^3*m)$ communication complexity, where '$m$' denotes the size of a sub-block shard and '$n$' ($n=3f+1$) the total number of nodes. Each epoch involves each node broadcasting its sub-block of size '$M$' (with $m=3*M/n$), assuming $2f+1$ sub-blocks are confirmed per epoch, resulting in a block size of $(2f+1)*M=(2f+1)*n*m/3$. While scaling up either '$n$' or '$m$' could enhance HBBFT’s scalability by increasing the block size per epoch, the $O(n^3*m)$ communication complexity makes this impractical.
3) The time-intensive nature of the n parallel ABA instances significantly hampers throughput. To achieve higher throughput, increasing the block size per epoch seems logical, but this exacerbates the communication complexity issue inherent in the RBC phase.
What it does
We propose three significant enhancements:
1) Utilizing a concurrent operational mechanism from Dumbo_NG (2022 CCS conference), we integrate three parallel-running strategies. First, broadcast instances (RBC or CBC) operate concurrently. Second, stages 1 and 2 of HBBFT run in parallel. Furthermore, Dumbo_NG introduces a novel ABA protocol (from the 2022 PODC conference paper) reducing the traditional ABA's time consumption. This amalgamation significantly decreases HBBFT protocol latency.
2) We have proposed a mechanism to lower communication complexity from $O(n^3*m)$ to $O(n^2*m)$ in asynchronous BFT protocols. To this end, we employing Verifiable Information Dispersal (VID) twice and separate the roles of consensus nodes in block dispersal and retrieval.
(i) VID uses erasure-coding encode (ECen) to divide a message $M$ into $n$ pieces, where any $k (k<n)$ pieces can reconstruct $M$ through erasure-coding decode (ECde). Each node encodes $M$ into $n$ shards (each $3*M/n$ in size) and sends each shard to a corresponding node, thus broadcasting $M$ at a total cost of $3M$, compared to $n*M$ in traditional methods. As every node broadcasts $M$, total bandwidth for $n$ pieces of $M$ is $3M*n (i.e., O(n^2*m))$, a significant reduction from the traditional $3M*n^2 (O(n^2*m))$. However, each node still needs to reconstruct the complete block of each epoch, which maintains a recovery cost of $O(n^3*m)$.
(ii) Our innovation lies in the second use of VID and a decoupling strategy. We introduce a new group of computation nodes (nc nodes) responsible for block recovery each epoch. The connection between consensus and computation nodes is via VID. When a consensus node completes an RBC or CBC instance for $M$, it only possesses a shard "$m$" of $M$. This shard with $m$ size is input into ECen, producing $n_c$ smaller shards, which are then distributed to corresponding computation nodes. Each consensus node, receiving $n$ shards per epoch, will only need $3m*n$ bandwidth to broadcast these shards, and collectively, $n$ consensus nodes only use a total of $3m*n^2$ bandwidth.
How We Built It: Detailed Implementation of the Consensus Protocol
Our consensus protocol is viewed from the perspective of a consensus $node_i$, one of $n$ consensus nodes, each uniquely identified. The protocol integrates four sub-protocols: Consistency Broadcast (CBC), Strong Provable Broadcast (SPB), Leader Selection (LS), and Speed Validated Agreement (SVA). Drawing on Dumbo_NG's parallel-running strategy, our protocol enables concurrent operation.
CBC Instance Execution: 1) Each consensus $node_i$ generates a batch of transactions ($M_i$), simulating its transaction pool content. 2) $Node_i$ encodes $M_i$ into $n$ shards $m_j$ ($j$ ranges from 0 to n-1) using the erasure coding encoding algorithm (ECen). It then inputs these shards into a Merkle tree formulation function, producing a Merkle tree and a proof (Merkle tree branch) for each shard $m_j$. $Node_i$ sends a message $(i, ($'CBC_SEND'$, roothash, branch, m_j, i_1))$ to $Node_j$, where 'CBC_SEND' is the message tag, $roothash$ is the Merkle tree's root hash, and $i_1$ denotes the first CBC instance of $node_i$. 3) When $node_i$ receives a 'CBC_SEND' message from $node_j$ $(j, ($'CBC_SEND'$, roothash, branch, m_i, j_1))$, it first checks if it has already received the message. It then verifies the branch's (proof) validity using a dedicated function. If valid, $node_i$ signs the message using ecdsa_sign() to generate a signature $Sig_i[j_1]$ and sends $(i, ($'CBC_ECHO'$, j_1, Sig_i[j_1], roothash))$ back to $node_j$. 4) Receiving a 'CBC_ECHO' message for its $i_1-th$ CBC instance from $node_j$, $node_i$ checks the message's validity using ecdsa_vrfy($PK[j]$, $roothash$, $Sig_j[i_1]$). If valid, it stores the $Sig_j[i_1]$ in a set $cbc.echo.sshares[i_1]$. Once $node_i$ accumulates $2f+1$ valid signatures in $cbc.echo.sshares[i_1]$, it generates a new transaction batch and repeats steps 1) and 2). The difference in step 2) is that 'CBC_SEND' now includes "$cbc.echo.sshares[i_1]$", leading $node_i$ to send $(i, ($'CBC_SEND'$, roothash, branch, m_j, cbc.echo.sshares[i_1], i_2)$ to $node_j$ for its $2th$ CBC instance.
Strong Provable Broadcast (SPB) Instance:
1) Each consensus $node_i$ at epoch $k$ creates a dictionary $D[i_k]$ with $n$ key-value pairs. Initially, each pair $D[i_k][j]$ (key: consensus $node j$'s id) has an empty tuple as a value. On receiving a 'CBC_SEND' message containing $node j$'s valid $cbc.echo.sshares.[j_s]$ at epcoh $k$, $node_i$ adds $j_s$ to $D[i_k][j]$. When $2f+1$ tuples in $D[i_k]$ are non-empty, $node_i$ sends $(i, ($'SPB_STORE'$, D[i_k]))$ to every consensus node.
2) Upon receiving $(j, ($'SPB_STORE'$, D[j_k]))$ from $node_j$, $node_i$ verifies $D[j_k]$'s validity, checking if $D[j_k]$ has $2f+1$ non-empty tuples representing CBC instances. If $D[j_k]$ is valid, implying $node_i$ received all cbc_echo_sshares, it signs $j_k$ using ecdsa_sign($SK[i]$) to create a signature share ($Sigs.i1$) and sends $(i, ($'SPB_STORED'$, Sigs.i1, j))$ to $node_j$.
3) $Node_i$, receiving 'SPB_STORED' for epoch $k$ from $node_j$, checks its validity using ecdsa_vrfy($PK[j]$, $i_k$, $Sigs.j1$). Valid messages are stored in $SPB.stage1.sshares.[i_k]$. Once 2f+1 valid shares are collected and stored in $SPB.stage1.sshares.[i_k]$, $node_i$ sends $(i, ($'SPB_LOCK'$, SPB.stage1.sshares.[i_k]))$ to every consensus node.
4) $Node_i$, receiving $(j, ($'SPB_LOCK'$, SPB.stage1.sshares.[j_k]))$, verifies the signatures in $SPB.stage1.sshares.[j_k]$ using ecdsa_vrfy. If valid, it signs $hash(j_k, SPB.stage1.sshares.[j_k])$ with ecdsa_sign($SK[i]$), creating $Sigs.i2$, and sends $(i, ($'SPB_LOCKED'$, Sigs.i2, j_k))$ to $node_j$.
5) On receiving a 'SPB_LOCKED' message for epoch $k$ from $node_j$, $node_i$ checks its validity with ecdsa_vrfy($PK[j], hash(i_k, SPB.stage1.sshares.[i_k]), Sigs.j2$). Valid messages are stored in $SPB.stage2.sshares.[i_k]$. If 2f+1 valid shares are collected, $node_i$ initiates the LEADER_ELECTION instance.
LEADER_ELECTION Instance:
1) Consensus $node_i$ generates a threshold signature share $tss_i[k0]$ for epoch $k$ at round $0$ by signing $hash(k, 0)$ using def encrypt() and sends $(i, ($'ELECTION'$, tss_i[k0], k, 0))$ to every consensus node.
2) When $node_i$ receives a message $(j, ($'ELECTION'$, tss_j[k0], k, 0))$ from $node_j$, it validates $tss_j[k0]$ with def verify_ciphertext(). If valid, $tss_j[k0]$ is added to $TSset_i[k0]$. Once $TSset_i[k0]$ has $f+1$ valid shares, $node_i$ combines them with def combine_shares() to form a threshold signature $TS[k0]$, converted to an integer $L$ via $int(TS[k0])$%$n$. $L$, ranging from $0$ to $n-1$, is the elected node's id. $Node_i$ then proceeds to the SPEED VALIDATED AGREEMENT instance.
SPEED VALIDATED AGREEMENT Instance:
The specifics of SPEED VALIDATED AGREEMENT are derived from here.
Challenges Encountered:
I've verified that my protocol adheres to the key properties (agreement, totality, liveness) required by atomic broadcast protocol. The most tricky part for me is to fully implement the complete consensus protocol. I have finished the most rudimentary version of CBC protocol, Leader_selection protocol in Rust. However, I still do not achieve the Rust version of SPB protocol, SPEED VALIDATED AGREEMENT protocol and Dumbo_NG protocol, which also only has python version from here Another part is that I need to implement the retrival process operated by computation node group. I need to finish the code parts in Rust.
Accomplishments that we're proud of
We've achieved two key advancements in consensus protocols: 1) Enhanced scalability, with communication complexity reduced from $O(n^3*m)$ to $O(n^2*m)$. 2) Optimized bandwidth utilization across nodes, enabled by concurrent broadcast instances and Dumbo_NG framework, enhancing network throughput and reducing latency.
Insights Gained:
Our protocol integrates three core internal strategies to enhance performance while maintaining security and decentralization. These include communication complexity reduction, hardware optimization, and parallel sub-protocol execution. Distinct from external approaches like layer 2 and sharding, our internal solutions offer potential synergy with these methods for a more robust consensus protocol.
Future Directions for Scalable Asynchronous BFT Protocol:
Research Focus: 1) Refining transaction propagation to surpass the inefficiency of gossip protocols. We're designing a new protocol to ensure transaction inclusion in the blockchain by reaching only 3/2 of the consensus nodes on average. 2) Exploring zero-knowledge proofs and multi-party computation for efficient block recovery, aiming to minimize computational costs.
Code Development: 1) Completion of sub-protocols within the consensus framework. 2) Integration of these sub-protocols through a central control mechanism. 3) Rigorous testing of the overall consensus protocol.
Log in or sign up for Devpost to join the conversation.