Support consensus engines without a single proposer.

[afck]

We would like to implement a consensus engine based on Honey Badger for the POA Network, and we are wondering whether:

• you would be open to merging it into master once it is functional,
• the current Engine trait is suitable for this kind of algorithm, and if not,
• you would be open to merging some refactorings to make Parity support it.

In Honey Badger, in each round/epoch, every node proposes a subset of transactions from its mempool, and the algorithm reaches agreement on a union of some of those subsets. The main differences compared to the existing Engine implementations are:

• There is no single block proposer. Instead, every node learns about the next agreed batch, which may contain the transactions proposed by the node itself, as well as transactions the node doesn't even have in its mempool.
• The engine will need to deterministically produce a new block from the batch: process all of its valid transactions and sign the result. This means that some of the Miner/TransactionQueue/transaction-pool functionality — prioritizing transactions and picking the ones to propose — needs to happen before each consensus round, while other Miner functionality — producing a new block and processing the transactions — needs to happen after the consensus round has produced an output.
• For performance, Honey Badger relies on low-latency, high-bandwidth targeted validator-to-validator messages, so the validators will probably need to establish a separate set of connections to each other.
• We would introduce our general Honey Badger implementation as a dependency.

[rphmeier]

First of all, congratulations on the HBBFT implementation in Rust! I wanted to do one myself in my spare time but never managed to get around to doing it. We would definitely be open to including it in Parity and accepting any and all contributions necessary to making it work.

HoneyBadgerBFT and similar algorithms were a part of the motivation for the Engine/Machine split in the architecture of Parity, where engines define exactly what properties of the state machine they need for their operation.

Although there is no actual "proposer" for HoneyBadgerBFT, there are a couple things to consider:

The EVM requires an author value to be accessible. The EthereumMachine provided by Parity operates only on blocks which contain an author field. Refactoring Parity to use blocks without an author field would be a significant chunk of work. I'd recommend just having your block validity function require that author be zeroed or something (since this is almost equally efficient as not having it at all w/ RLP encoding)

HoneyBadgerBFT as described in the paper allows nodes participating in the consensus to come to an agreement, but proving that agreement has been reached to non-consensus nodes requires some form of justification. This is the "seal" type in the EthereumMachine's block type. There are a few options for generating this seal:

• provide an entire transcript of messages in the view of a single replica, which proves all common coin instances and threshold decryption shares. this is infeasible space-wise
• provide a list of any 2f + 1 signatures on the block header, adding an extra step to HBBFT to multicast these signatures
• provide a 2f + 1 threshold signature on the block header, adding an extra step to HBBFT to multicast the signature shares, anybody witnessing 2f + 1 valid shares can construct the threshold signature.

Note that the first two options can lead to different valid seals being created (even if no authorities are byzantine) since they aren't a result of polynomial interpolation, which would require significant refactoring in Parity to ensure that the blockchain is based on the "bare" hash of the header and not the hash with the seal included. This change would be necessary to support tendermint or other PBFT derivates faithfully in Parity as well.

[rphmeier]

Also: I think these kinds of internal-communication-heavy consensus play really nicely with the futures model.

This feature would be orthogonal with #8664 which intends to make block production an asynchronous process within the engine, providing only a stream of network messages and a sink for output messages.

[afck]

Thanks, but don't congratulate us too early: hbbft isn't quite done yet. (Encryption of the proposed transactions is still missing; common coin is under way.)

Yes, we were thinking of using 2f + 1 (or just f + 1?) signatures as the seal (in an extra message round, which could happen in parallel with the Honey Badger epoch for the next block, I guess), but a threshold signature would make more sense: and Honey Badger uses threshold signatures anyway, so we should have the necessary tools available.

a stream of network messages and a sink for output messages

Could these even be targeted, or broadcast-only? Or should we use separate direct connections anyway if we need low-latency and high-bandwith channels?

[rphmeier]

It would probably multicast too all authorities (defined by engine), which is the network requirement for HoneyBadger AFAIK, although we could probably make more complex routing as necessary.

You're right that only f + 1 are necessary since the agreement has already resolved (under a basic honest-majority assumption). 2f + 1 is necessary if you construct a justification from PBFT-style Commit messages but not here.

Although for accountable safety (for e.g. PoS slashing) you might want to use 2f + 1 anyway, since then reversion of a finalized block has to overlap in at least f + 1 authorities. This isn't as conducive to threshold signatures though.

[afck]

You're right, maybe 2f + 1 is safer. Honey Badger requires that many honest nodes anyway, so if we fail to collect that many signatures it's better to stop immediately rather than accept a block singned by fewer than that.

all authorities (defined by engine), which is the network requirement for HoneyBadger AFAIK

Most messages are broadcast, but not all: Crucially, the biggest ones are targeted, i.e. sent from a validator to a single other validator. Honey Badger only achieves a high throughput and low latency if that kind of communication is high-bandwidth (broadcasting all of them would waste a lot of bandwidth) and low-latency (if they are routed via several hops, the block rate would be much lower), so I still think it might be necessary to create a separate set of direct connections.