# Parity + hbbft

[Parity](https://github.com/paritytech/parity-ethereum) is an Ethereum client written in [Rust](https://www.rust-lang.org/). The [hbbft](https://github.com/poanetwork/hbbft) crate implements the [Honey Badger BFT](https://eprint.iacr.org/2016/199.pdf) consensus algorithm.

Parity already supports alternative consensus algorithms like [Aura](https://wiki.parity.io/Aura). Let's add support for Honey Badger BFT.

## Required changes and additions

#### Consensus

In Parity, hbbft will be used to reach consensus on a set of transactions _before_ a block is produced from those transactions.
* Whenever [a new block is due](#Initiating-block-creation), each validator proposes a list of transactions from their queue. If there are `N` validators and the expected number of transactions per block is `B`, this is a random selection of `B / N` out of the first (highest-priority) `B` pending transactions. In addition, they propose a timestamp for the new block and a contribution to the [random value](#Randomness).
* They reach consensus on the set of proposed transactions: this is the union of all (or most of) the individual lists proposed by the validators.
* Each validator computes the block from that list, by executing the transactions (discarding invalid ones, stopping at the gas limit), adding a transaction for the random value and setting the block's timestamp to the median of the proposed timestamp values. Since at this point consensus on the input for block production has already been reached, they all create identical blocks.
* They collaboratively sign that block using [threshold signatures](https://docs.rs/hbbft/0.1.0/hbbft/threshold_sign/index.html). (That's one additional round of message exchange for the signature shares.)
* The threshold signature is used as the block's seal. The block is now finalized, and can be appended to the blockchain and propagated.

#### Randomness

Hbbft can provide secure random numbers: The validators' proposals are encrypted and remain so until after consensus has been reached; if each node includes a random number with their proposal, everyone has to commit to their number before knowing the others'. Unless ⅓ of the validators collude, the xor of those numbers will be random and cannot be known in advance.
These random numbers can e.g. be used to seed an on-chain PRNG contract in each block. That, in turn, allows e.g. [PoS contracts](#Governance-contracts) to select new validator sets.

#### Fault reports

Hbbft will report if it detects misbehavior of another node: If a validator violates the protocol, other validators will notify the caller. Parity should forward these reports to the governance contracts and/or the user.

### Block validation

Parity needs to accept blocks as valid if they are sealed with a valid threshold signature. The signature matches the current validator set's master key: Accordingly, Parity needs to keep track of validator set changes so that it knows the correct current key for each block. For that, we can either:
* let hbbft handle key generation, and provide Parity with a signature of the new public master key by the old one (or include the new master key in the last block that was signed by the old one), or
* run key generation in a smart contract, so that Parity can follow the process and compute the new public master key.

### Initiating block creation

After each block, we push a new contribution to Honey Badger (and thus initiate creating the next block) as soon as we either have enough (details TBD) pending transactions in the queue, or [`Honey Badger::received_proposals`](https://github.com/poanetwork/hbbft/pull/354) returns _≥ ⅓ N_ (i.e. other validators have pending transactions). In addition, there could be some timeout to set a maximum block time.

In theory, to increase throughput, production of the next block could be started as soon as the _transactions_ for the previous block have been determined, even if it has not been computed and sealed yet.

### Governance contracts

Both Aura and hbbft require a well-defined, small (double-digit?) set of validators, so they are well-suited for a _permissioned_ setting like [Proof of Authority](https://github.com/poanetwork/poa-network-consensus-contracts). Using [Proof of Stake contracts](https://github.com/poanetwork/posdao-contracts) that periodically select a subset of validators from some set of staking pools, they can be used in a permissionless setting, too. Both kinds of contracts require some additional logic in Parity:
* It needs to request the list of validators to learn about changes, and then use hbbft to enact these changes.
* It needs to report to the contracts if another validator violated the protocol.

### Validator set changes

Changing the set of validators takes several blocks, because hbbft requires a set of threshold keys for the new validators before they can take over running the consensus process. Key generation needs to be performed "on-chain": hbbft already contains a [`DynamicHoneyBadger`](https://github.com/poanetwork/hbbft/blob/d4a7b19adb7021efcefdf735f6dd2c45cce0a1d2/src/dynamic_honey_badger/dynamic_honey_badger.rs#L28) reference implementation that can dynamically change its validator set and performs key generation automatically and without the user's intervention. We might need tighter control over that process, though, and run key generation inside an actual smart contract instead.

#### How validator set changes work in hbbft

`DynamicHoneyBadger` implements [a voting system](https://github.com/poanetwork/hbbft/blob/15f731370686f5456425c2e319225bf3b4d447c0/src/dynamic_honey_badger/votes.rs#L19) to propose and agree on changes. Once there are [enough votes](https://github.com/poanetwork/hbbft/blob/15f731370686f5456425c2e319225bf3b4d447c0/src/dynamic_honey_badger/dynamic_honey_badger.rs#L364) for a new validator set, each node [creates a new `SyncKeyGen`](https://github.com/poanetwork/hbbft/blob/15f731370686f5456425c2e319225bf3b4d447c0/src/dynamic_honey_badger/dynamic_honey_badger.rs#L417), with its own ID and BLS secret key (unchanged) and the _new_ set of validator IDs, together with those validators' public BLS keys. In those nodes that are _future_ validators, the constructor will return a `Part` message which they [send to the _existing_ validators](https://github.com/poanetwork/hbbft/blob/15f731370686f5456425c2e319225bf3b4d447c0/src/dynamic_honey_badger/dynamic_honey_badger.rs#L421) for inclusion in a batch (i.e. in the "blockchain").

Whenever a node finds a `Part` or `Ack` message in a batch (i.e. there's consensus on the order of those messages), it passes it into its `SyncKeyGen`, and again sends any new key gen messages to the existing validators for inclusion.

After each batch `n` we check whether [key generation has been completed](https://github.com/poanetwork/hbbft/blob/15f731370686f5456425c2e319225bf3b4d447c0/src/dynamic_honey_badger/dynamic_honey_badger.rs#L357). Then we [generate the new `NetworkInfo`](https://github.com/poanetwork/hbbft/blob/15f731370686f5456425c2e319225bf3b4d447c0/src/dynamic_honey_badger/dynamic_honey_badger.rs#L360) and [restart `HoneyBadger`](https://github.com/poanetwork/hbbft/blob/15f731370686f5456425c2e319225bf3b4d447c0/src/dynamic_honey_badger/dynamic_honey_badger.rs#L362) with it, beginning with batch `n + 1`.

### Networking

Hbbft nodes need to exchange low-latency high-bandwidth targeted (i.e. not gossip or multicast) messages to be efficient. These will need to be direct (or two- or three-hop) connections.

That networking functionality can either be integrated in Parity itself, or live in a separate crate (see e.g. [Hydrabadger](https://github.com/poanetwork/hydrabadger)).

In either case, we need to make sure that when the validator set is about to change, the new validators establish connections to each other.

### Network startup

The compiled [governance contracts](#Governance-contracts) must be added to the chain spec, so they are available starting from the genesis block.

To configure the initial set of validators, the public master key needs to be specified in the chain spec, and the initial validators need to have their corresponding key shares. These need to be created either by a trusted dealer or in a DKG process that needs to happen outside of the network.
Alternatively: Start with a single validator, and start a new epoch immediately?