Expand description
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.
If your application would benefit from succinct consensus certificates or a bias-resistant VRF, see Threshold 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
§Design
§Architecture
All logic is split into three components: the Voter
, the Resolver
, and the Application
(provided by the user).
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 Supervisor
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
, broadcastnotarize(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 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 broadcastnotarize(c,v)
Upon receiving 2f+1
notarize(c,v)
:
- Cancel
t_a
- Mark
c
as notarized - Broadcast
notarization(c,v)
(even if we have not verifiedc
) - If have not broadcast
nullify(v)
, broadcastfinalize(c,v)
- Enter
v+1
Upon receiving 2f+1
nullify(v)
:
- Broadcast
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
finalization(c,v)
(even if we have not verifiedc
)
Upon t_l
or t_a
firing:
- Broadcast
nullify(v)
- Every
t_r
afternullify(v)
broadcast that we are still in viewv
:- Rebroadcast
nullify(v)
and eithernotarization(v-1)
ornullification(v-1)
- Rebroadcast
§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).