Expand description
Simplex-like BFT agreement with an embedded VRF and succinct consensus certificates.
Inspired by Simplex Consensus, threshold-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. Unlike Simplex Consensus, however, threshold-simplex
employs threshold
cryptography (specifically BLS12-381 threshold signatures with a 2f+1
of 3f+1
quorum) to generate both
a bias-resistant beacon (for leader election and post-facto execution randomness) and succinct consensus certificates
(any certificate can be verified with just the static public key of the consensus instance) for each view
with zero message overhead (natively integrated).
If you wish to deploy Simplex Consensus but can’t employ threshold signatures, see Simplex.
§Features
- Wicked Fast Block Times (2 Network Hops)
- Optimal Finalization Latency (3 Network Hops)
- Externalized Uptime and Fault Proofs
- Decoupled Block Broadcast and Sync
- Flexible Block Format
- Embedded VRF for Leader Election and Post-Facto Execution Randomness
- Succinct Consensus Certificates for Notarization, Nullification, and Finality
§Design
§Architecture
All logic is split into two components: the Voter
and the Resolver
(and the user of threshold-simplex
provides Application
). The Voter
is responsible for participating in the latest view and the
Resolver
is responsible for fetching artifacts from previous views required to verify proposed
blocks in the latest view.
To provide great performance, all interactions between 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
verifies a notarization.
+---------------+ +---------+ +++++++++++++++
| |<----------+ +----------->+ +
| Application | | Voter | + Peers +
| +---------->| |<-----------+ +
+---------------+ +--+------+ +++++++++++++++
| ^
| |
| |
| |
v |
+-------+----+ +++++++++++++++
| +--------->+ +
| Resolver | + Peers +
| |<---------+ +
+------------+ +++++++++++++++
Application is usually a single object that implements the Automaton
, Relay
, Committer
,
and ThresholdSupervisor
traits.
§Joining Consensus
As soon as 2f+1
notarizes, nullifies, or finalizes are observed for some view v
, the Voter
will
enter v+1
. This means that a new participant joining consensus will immediately jump ahead to the
latest view and begin participating in consensus (assuming it can verify blocks).
§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 Journal
.
Before sending a message, the Journal
sync is invoked to prevent inadvertent Byzantine behavior
on restart (especially in the case of unclean shutdown).
§Protocol Description
§Specification for View v
Upon entering view v
:
- Determine leader
l
for viewv
- Set timer for leader proposal
t_l = 2Δ
and advancet_a = 3Δ
- If leader
l
has not been active in lastr
views, sett_l
to 0.
- If leader
- If leader
l
, broadcast(part(v), notarize(c,v))
- If can’t propose container in view
v
because missing notarization/nullification for a previous viewv_m
, requestv_m
- If can’t propose container in view
Upon receiving first (part(v), notarize(c,v))
from l
:
- Cancel
t_l
- If the container’s parent
c_parent
is notarized atv_parent
and we have nullifications for all views betweenv
andv_parent
, verifyc
and broadcast(part(v), notarize(c,v))
Upon receiving 2f+1
(part(v), notarize(c,v))
:
- Cancel
t_a
- Mark
c
as notarized - Broadcast
(seed(v), notarization(c,v))
(even if we have not verifiedc
) - If have not broadcast
(part(v), nullify(v))
, broadcastfinalize(c,v)
- Enter
v+1
Upon receiving 2f+1
(part(v), nullify(v))
:
- Broadcast
(seed(v), nullification(v))
- If observe
>= f+1
notarize(c,v)
for somec
, requestnotarization(c_parent, v_parent)
and any missingnullification(*)
betweenv_parent
andv
. Ifc_parent
is than last finalized, broadcast last finalization instead.
- If observe
- Enter
v+1
Upon receiving 2f+1
finalize(c,v)
:
- Mark
c
as finalized (and recursively finalize its parents) - Broadcast
(seed(v), finalization(c,v))
(even if we have not verifiedc
)
Upon t_l
or t_a
firing:
- Broadcast
(part(v), nullify(v))
- Every
t_r
after(part(v), nullify(v))
broadcast that we are still in viewv
:- Rebroadcast
(part(v), nullify(v))
and either(seed(v-1), notarization(v-1))
or(seed(v-1), nullification(v-1))
- Rebroadcast
§Embedded VRF
When broadcasting any notarize(c,v)
or nullify(v)
message, a participant must also include a part(v)
message (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 part(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 Consensus Certificates
All broadcast consensus messages (notarize(c,v)
, nullify(v)
, finalize(c,v)
) contain 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).
§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
andnullify
rather than referring to both as avote
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).
Structs§
- Config
- Configuration for the consensus engine.
- Context
- Context is a collection of metadata from consensus about a given payload.
- Engine
- Instance of
threshold-simplex
consensus engine. - Prover
- Encode and decode proofs of activity.
Constants§
- CONFLICTING_
FINALIZE - Finalize a payload that conflicts with a previous finalize.
- CONFLICTING_
NOTARIZE - Notarize a payload that conflicts with a previous notarize.
- FINALIZE
- Finalize a payload at a given view.
- NOTARIZE
- Notarize a payload at a given view.
- NULLIFY_
AND_ FINALIZE - Nullify and finalize in the same view.
Type Aliases§
- View
- View is a monotonically increasing counter that represents the current focus of consensus.