Honey Badger Byzantine Fault Tolerant (BFT) consensus algorithm

Welcome to a Rust library of the Honey Badger Byzantine Fault Tolerant (BFT) consensus algorithm. The research and protocols for this algorithm are explained in detail in "The Honey Badger of BFT Protocols" by Miller et al., 2016.

An official security audit has been completed on hbbft by Jean-Philippe Aumasson.

Following is an overview of HoneyBadger BFT and basic instructions for getting started.

Note: This library is a work in progress and parts of the algorithm are still in development.

What is Honey Badger?

The Honey Badger consensus algorithm allows nodes in a distributed, potentially asynchronous environment to achieve agreement on transactions. The agreement process does not require a leader node, tolerates corrupted nodes, and makes progress in adverse network conditions. Example use cases are decentralized databases and blockchains.

Honey Badger is Byzantine Fault Tolerant. The protocol can reach consensus with a number of failed nodes f (including complete takeover by an attacker), as long as the total number N of nodes is greater than 3 * f.

Honey Badger is asynchronous. It does not make timing assumptions about message delivery. An adversary can control network scheduling and delay messages without impacting consensus.

How does it work?

Honey Badger is a modular library composed of several independent algorithms. To reach consensus, Honey Badger proceeds in epochs. In each epoch, participating nodes broadcast a set of encrypted data transactions to one another and agree on the contents of those transactions.

In an optimal networking environment, output includes data sent from each node. In an adverse environment, the output is an agreed upon subset of data. Either way, the resulting output contains a batch of transactions which is guaranteed to be consistent across all nodes.

In addition to validators, the algorithms support observers: These don't actively participate, and don't need to be trusted, but they receive the output as well, and are able to verify it under the assumption that more than two thirds of the validators are correct.

Please see the following posts for more details:

• POA Network: Building Honey Badger BFT

• POA Network: How Honey Badger BFT Consensus Works

• POA Network: Honey Badger BFT and Threshold Cryptography

Algorithms

• Honey Badger: Each node inputs transactions. The protocol outputs a sequence of batches of transactions.

• Dynamic Honey Badger: A modified Honey Badger where nodes can dynamically add and remove other nodes to/from the network.

• Queueing Honey Badger: Works exactly like Dynamic Honey Badger, but includes a built in transaction queue.

• Subset: Each node inputs data. The nodes agree on a subset of suggested data.

• Broadcast: A proposer node inputs data and every node receives this output.

• Binary Agreement: Each node inputs a binary value. The nodes agree on a value that was input by at least one correct node.

• Threshold Sign: Each node inputs the same data to be signed, and outputs the unique valid signature matching the public master key. It is used as a pseudorandom value in the Binary Agreement protocol.

• Threshold Decryption: Each node inputs the same ciphertext, encrypted to the public master key, and outputs the decrypted data.

• Synchronous Key Generation A dealerless algorithm that generates keys for threshold encryption and signing. Unlike the other algorithms, this one is completely synchronous and should run on top of Honey Badger (or another consensus algorithm)

External crates developed for this library

• Threshold Crypto: A threshold cryptosystem for collaborative message decryption and signature creation.

Getting Started

This library requires a distributed network environment to function. Details on network requirements TBD.

Note: Additional examples are currently in progress.

Build

Requires Rust 1.36 or higher and cargo: installation instructions. The library is tested against the stable release channel.

$ cargo build [--release]

Testing

$ cargo test --release

See the tests README for more information on our testing toolkit.

Example Network Simulation

A basic example is included to run a network simulation.

$ cargo run --example simulation --release

Heading	Definition
Epoch	Epoch number. In each epoch, transactions are processed in a batch by simulated nodes (default is 10 nodes) on a network. The batch is always output in one piece, with all transactions at once.
Min Time	Time in simulated milliseconds until the first correct (i.e. not faulty) node outputs the batch.
Max Time	Time in simulated milliseconds until the last correct node outputs the batch.
Txs	Number of transactions processed in the epoch.
Msgs/Node	Average number of messages handled by a node. The counter is cumulative and includes the number of messages handled in the current epoch and all previous epochs.
Size/Node	Average message size (in converted bytes) handled by a node. This is cumulative and includes message size for the current epoch and all previous epochs.

Options

Set different parameters to simulate different transaction and network conditions.

Flag	Description
-h, --help	Show help options
--version	Show the version of hbbft
-n <n>, --nodes <n>	The total number of nodes [default: 10]
-f <f>, --faulty <f>	The number of faulty nodes [default: 0]
-t <txs>, --txs <txs>	The number of transactions to process [default: 1000]
-b <b>, --batch <b>	The batch size, i.e. txs per epoch [default: 100]
-l <lag>, --lag <lag>	The network lag between sending and receiving [default: 100]
--bw <bw>	The bandwidth, in kbit/s [default: 2000]
--cpu <cpu>	The CPU speed, in percent of this machine's [default: 100]
--tx-size <size>	The size of a transaction, in bytes [default: 10]

Examples:

# view options
$ cargo run --example simulation --release -- -h

# simulate a network with 12 nodes, 2 of which are faulty
$ cargo run --example simulation --release -- -n 12 -f 2

# increase batch size to 500 transactions per epoch
$ cargo run --example simulation --release -- -b 500

Protocol Modifications

Our implementation modifies the protocols described in "The Honey Badger of BFT Protocols" in several ways:

• We use a pairing elliptic curve library to implement pairing-based cryptography using a Barrento-Lynn-Scott (BLS12-381) curve.
• We add a Terminate message to the Binary Agreement algorithm. Termination occurs following output, preventing the algorithm from running (or staying in memory) indefinitely. (#53)
• We add a Conf message to the Binary Agreement algorithm. An additional message phase prevents an attack if an adversary controls a network scheduler and a node. (#37)
• We return additional information from the Subset and Honey Badger algorithms that specifies which node input which data. This allows for identification of potentially malicious nodes.
• We include a Distributed Key Generation (DKG) protocol which does not require a trusted dealer; nodes collectively generate a secret key. This addresses the problem of single point of failure. See Distributed Key Generation in the Wild.

Algorithm naming conventions

We have simplified algorithm naming conventions from the original paper.

Algorithm Name	Original Name
Honey Badger	HoneyBadgerBFT
Subset	Asynchronous Common Subset (ACS)
Broadcast	Reliable Broadcast (RBC)
Binary Agreement	Asynchronous Binary Byzantine Agreement (ABA)

References

• The Honey Badger of BFT Protocols

• Honey Badger Video

• Other language implementations

  • Python

  • Go

  • Erlang

  • Rust - unfinished implementation

Honey Badger Visualization

Contributing

See the CONTRIBUTING document for contribution, testing and pull request protocol.

License

Licensed under either of:

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.