Message Passing for Heterogeneous Paxos

[isheff]

This issue may well be combined with our existing ledger projects.

Ultimately, our Heterogeneous Paxos implementation will need to send messages (1b, 2a, etc).

• How do we format these?
• How do we disseminate them?
  • While Gossip is efficient in terms of per-node bandwidth and connections, just sending UDP packets to all destinations might be faster, although we'd have to be clever about filling in messages that some recipients missed.
• what, if any, signature aggregation do we use?
  • trees of signature aggregation have in the past been fruitfully combined with gossip trees.

[isheff]

Schemes like Kauri (SOSP 2021) use combination signature-aggregation/gossip trees.

[isheff]

HotStuff effectively does all-to-all communication with O(n) overhead by sending everything through a leader which aggregates signatures.

[isheff]

It currently seems likely that DKG will be a bottleneck on the number of validators before all-to-all messaging in consensus becomes impractical. We may be able to delay on message-aggregating cleverness for a while.

[isheff]

We may be able to usefully combine some consensus messages here with mempool messages, like Tusk does.

[isheff]

Similarly, we may want to take into account message pipelining when formatting these messages.

[isheff]

We may want to leave message content, aside from the layer containing transactions fairly abstract (mostly messages carry signatures, timestamps, and references to other messages), the way it is in Heterogeneous Paxos Reference Implementation.

We don't want, for instance, the Mempool and the Consensus layer to both send independent messages to a quorum of validators at the same time, when they could just send one message.

Perhaps each orderer / validator should (internally) maintain a "messaging service," which signs, broadcasts, receives, and validates messages as efficiently as possible, and then distributes internal "logical messages" to components of the orderer / validator.