Module simplex 

Simple and fast BFT agreement inspired by Simplex Consensus.

Inspired by Simplex Consensus, simplex provides simple and fast BFT agreement with network-speed view (i.e. block time) latency and optimal finalization latency in a partially synchronous setting.

Features

• Wicked Fast Block Times (2 Network Hops)
• Optimal Finalization Latency (3 Network Hops)
• Externalized Uptime and Fault Proofs
• Require Certification Before Finalization
• Decoupled Block Broadcast and Sync
• Lazy Message Verification
• Application-Defined Block Format
• Pluggable Hashing and Cryptography
• Embedded VRF (via scheme::bls12381_threshold::vrf)

Design

Protocol Description

Genesis

Genesis (view 0) is implicitly finalized. There is no finalization certificate for genesis; the digest returned by Automaton::genesis serves as the initial finalized state. Voting begins at view 1, with the first proposal referencing genesis as its parent.

Specification for View v

Upon entering view v:

• Determine leader l for view v
• Set timer for leader proposal t_l = 2Δ and advance t_a = 3Δ
  • If leader l has not been active in last r views, set t_l to 0.
• If leader l, broadcast notarize(c,v)
  • If can’t propose container in view v because missing notarization/nullification for a previous view v_m, request v_m

Upon receiving first notarize(c,v) from l:

• Cancel t_l
• If the container’s parent c_parent is finalized (or both notarized and certified) at v_parent and we have nullifications for all views between v and v_parent, verify c and broadcast notarize(c,v)
  • If verification of c fails, immediately broadcast nullify(v)

Upon receiving 2f+1 notarize(c,v):

• Cancel t_a
• Mark c as notarized
• Broadcast notarization(c,v) (even if we have not verified c)
• Attempt to certify c (see Certification)
  • On success: broadcast finalize(c,v) (if have not broadcast nullify(v)) and enter v+1
  • On failure: broadcast nullify(v)

Upon receiving 2f+1 nullify(v):

• Broadcast nullification(v)
• Enter v+1

Upon receiving 2f+1 finalize(c,v):

• Mark c as finalized (and recursively finalize its parents)
• Broadcast finalization(c,v) (even if we have not verified c)

Upon t_l or t_a firing:

• Broadcast nullify(v)
• Every t_r after nullify(v) broadcast that we are still in view v:
  • Rebroadcast nullify(v) and either notarization(v-1) or nullification(v-1)

When 2f+1 votes of a given type (notarize(c,v), nullify(v), or finalize(c,v)) have been have been collected from unique participants, a certificate (notarization(c,v), nullification(v), or finalization(c,v)) can be assembled. These certificates serve as a standalone proof of consensus progress that downstream systems can ingest without executing the protocol.

Joining Consensus

As soon as 2f+1 nullifies or finalizes are observed for some view v, the Voter will enter v+1. Notarizations advance the view if-and-only-if the application certifies them. This means that a new participant joining consensus will immediately jump ahead on the previous view’s nullification or finalization and begin participating in consensus at the current view.

Deviations from Simplex Consensus

• Fetch missing notarizations/nullifications as needed rather than assuming each proposal contains a set of all notarizations/nullifications for all historical blocks.
• Introduce distinct messages for notarize and nullify rather than referring to both as a vote for either a “block” or a “dummy block”, respectively.
• Introduce a “leader timeout” to trigger early view transitions for unresponsive leaders.
• Skip “leader timeout” and “notarization timeout” if a designated leader hasn’t participated in some number of views (again to trigger early view transition for an unresponsive leader).
• Introduce message rebroadcast to continue making progress if messages from a given view are dropped (only way to ensure messages are reliably delivered is with a heavyweight reliable broadcast protocol).
• Immediately broadcast nullify(v) if the leader’s proposal fails verification (rather than waiting for a timeout to fire).
• Upon seeing notarization(c,v), instead of moving to the view v+1 immediately, request certification from the application (see Certification). Only move to view v+1 and broadcast finalize(c,v) if certification succeeds, otherwise broadcast nullify(v) and refuse to build upon c.

Architecture

All logic is split into four components: the Batcher, the Voter, the Resolver, and the Application (provided by the user). The Batcher is responsible for collecting messages from peers and lazily verifying them when a quorum is met. The Voter is responsible for directing participation in the current view. The Resolver is responsible for fetching artifacts from previous views required to verify proposed blocks in the latest view. Lastly, the Application is responsible for proposing new blocks and indicating whether some block is valid.

To drive great performance, all interactions between Batcher, Voter, Resolver, and Application are non-blocking. This means that, for example, the Voter can continue processing messages while the Application verifies a proposed block or the Resolver fetches a notarization.

                           +------------+          +++++++++++++++
                           |            +--------->+             +
                           |  Batcher   |          +    Peers    +
                           |            |<---------+             +
                           +-------+----+          +++++++++++++++
                               |   ^
                               |   |
                               |   |
                               |   |
                               v   |
+---------------+           +---------+            +++++++++++++++
|               |<----------+         +----------->+             +
|  Application  |           |  Voter  |            +    Peers    +
|               +---------->|         |<-----------+             +
+---------------+           +--+------+            +++++++++++++++
                               |   ^
                               |   |
                               |   |
                               |   |
                               v   |
                           +-------+----+          +++++++++++++++
                           |            +--------->+             +
                           |  Resolver  |          +    Peers    +
                           |            |<---------+             +
                           +------------+          +++++++++++++++

Batched Verification

Unlike other consensus constructions that verify all incoming messages received from peers, for schemes where Scheme::is_batchable() returns true (such as scheme::ed25519, scheme::bls12381_multisig and scheme::bls12381_threshold), simplex lazily verifies messages (only when a quorum is met), enabling efficient batch verification. For schemes where is_batchable() returns false (such as scheme::secp256r1), signatures are verified eagerly as they arrive since there is no batching benefit.

If an invalid signature is detected, the Batcher will perform repeated bisections over collected messages to find the offending message (and block the peer(s) that sent it via commonware_p2p::Blocker).

If using a p2p implementation that is not authenticated, it is not safe to employ this optimization as any attacking peer could simply reconnect from a different address. We recommend commonware_p2p::authenticated.

Fetching Missing Certificates

Instead of trying to fetch all possible certificates above the floor, we only attempt to fetch nullifications for all views from the floor (last certified notarization or finalization) to the current view. This technique, however, is not sufficient to guarantee progress.

Consider the case where f honest participants have seen a finalization for a given view v (and nullifications only from v to the current view c) but the remaining f+1 honest participants have not (they have exclusively seen nullifications from some view o < v to c). Neither partition of participants will vote for the other’s proposals.

To ensure progress is eventually made, leaders with nullified proposals directly broadcast the best finalization certificate they are aware of to ensure all honest participants eventually consider the same proposal ancestry valid.

While a more aggressive recovery mechanism could be employed, like requiring all participants to broadcast their highest finalization certificate after nullification, it would impose significant overhead under normal network conditions (whereas the approach described incurs no overhead under normal network conditions). Recall, honest participants already broadcast observed certificates to all other participants in each view (and misaligned participants should only ever be observed following severe network degradation).

Pluggable Hashing and Cryptography

Hashing is abstracted via the commonware_cryptography::Hasher trait and cryptography is abstracted via the commonware_cryptography::certificate::Scheme trait, allowing deployments to employ approaches that best match their requirements (or to provide their own without modifying any consensus logic). The following schemes are supported out-of-the-box:

scheme::ed25519

commonware_cryptography::ed25519 signatures are “High-speed high-security signatures” with 32 byte public keys and 64 byte signatures. While they are well-supported by commercial HSMs and offer efficient batch verification, the signatures are not aggregatable (and certificates grow linearly with the quorum size).

scheme::bls12381_multisig

commonware_cryptography::bls12381 is a “digital signature scheme with aggregation properties”. Unlike commonware_cryptography::ed25519, signatures from multiple participants (say the signers in a certificate) can be aggregated into a single signature (reducing bandwidth usage per broadcast). That being said, commonware_cryptography::bls12381 is much slower to verify than commonware_cryptography::ed25519 and isn’t supported by most HSMs (a standardization effort expired in 2022).

scheme::secp256r1

commonware_cryptography::secp256r1 signatures use the NIST P-256 elliptic curve (also known as prime256v1), which is widely supported by commercial HSMs and hardware security modules. Unlike commonware_cryptography::ed25519, Secp256r1 does not benefit from batch verification, so signatures are verified individually. Certificates grow linearly with quorum size (similar to ed25519).

scheme::bls12381_threshold

scheme::bls12381_threshold employs threshold cryptography (BLS12-381 threshold signatures with a 2f+1 of 3f+1 quorum) to generate succinct consensus certificates (verifiable with just the static public key). This scheme requires instantiating the shared secret via commonware_cryptography::bls12381::dkg and resharing whenever participants change.

Two (non-attributable) variants are provided:

• scheme::bls12381_threshold::standard: Certificates contain only a vote signature.

• scheme::bls12381_threshold::vrf: Certificates contain a vote signature and a view signature (i.e. a seed that can be used as a VRF). This variant can be configured for random leader election (via elector::Random) and/or incorporate this randomness into execution.

Embedded VRF (scheme::bls12381_threshold::vrf)

Every notarize(c,v) or nullify(v) message includes an attestation(v) (a partial signature over the view v). After 2f+1 notarize(c,v) or nullify(v) messages are collected from unique participants, seed(v) can be recovered. Because attestation(v) is only over the view v, the seed derived for a given view v is the same regardless of whether or not a block was notarized in said view v.

Because the value of seed(v) cannot be known prior to message broadcast by any participant (including the leader) in view v and cannot be manipulated by any participant (deterministic for any 2f+1 signers at a given view v), it can be used both as a beacon for leader election (where seed(v) determines the leader for v+1) and a source of randomness in execution (where seed(v) is used as a seed in v).

Succinct Certificates

All broadcast consensus messages (notarize(c,v), nullify(v), finalize(c,v)) contain attestations (partial signatures) for a static public key (derived from a group polynomial that can be recomputed during reconfiguration using dkg). As soon as 2f+1 messages are collected, a threshold signature over notarization(c,v), nullification(v), and finalization(c,v) can be recovered, respectively. Because the public key is static, any of these certificates can be verified by an external process without following the consensus instance and/or tracking the current set of participants (as is typically required to operate a lite client).

These threshold signatures over notarization(c,v), nullification(v), and finalization(c,v) (i.e. the consensus certificates) can be used to secure interoperability between different consensus instances and user interactions with an infrastructure provider (where any data served can be proven to derive from some finalized block of some consensus instance with a known static public key).

Certification

After a payload is notarized, the application can optionally delay or prevent finalization via the CertifiableAutomaton::certify method. By default, certify returns true for all payloads, meaning finalization proceeds immediately after notarization.

Customizing certify is useful for systems that employ erasure coding, where participants may want to wait until they have received enough shards to reconstruct and validate the full block before voting to finalize.

If certify returns true, the participant broadcasts a finalize vote for the payload and enters the next view. If certify returns false, the participant broadcasts nullify for the view instead (treating it as an immediate timeout), and will refuse to build upon the proposal or notarize proposals that build upon it. Thus, a payload can only be finalized if a quorum of participants certify it.

The decision returned by certify must be deterministic and consistent across all honest participants to ensure liveness.

Persistence

The Voter caches all data required to participate in consensus to avoid any disk reads on on the critical path. To enable recovery, the Voter writes valid messages it receives from consensus and messages it generates to a write-ahead log (WAL) implemented by commonware_storage::journal::segmented::variable::Journal. Before sending a message, the Journal sync is invoked to prevent inadvertent Byzantine behavior on restart (especially in the case of unclean shutdown).

Re-exports

pub use config::Config;

Modules

config

elector

Leader election strategies for simplex consensus.

scheme

Signing scheme implementations for simplex.

types

Types used in crate::simplex.

Structs

Engine

Instance of simplex consensus engine.