Quantum Cadence: Post-Quantum Consensus with Multiple Concurrent Proposers

1 Introduction

• Post-quantum certificates are impractical to broadcast because signatures are larger and known aggregation schemes produce much larger, slower aggregates than BLS.Chorus sends certificates for every proposer, so without aggregation each certificate would contain 2f + 1 large signatures.Source: §1 · p. 1
• Quantum Cadence avoids certificates by having each validator count quorums in the messages it receives, while retaining Cadence’s slot consensus under the Conductor.Simply removing certificates from Chorus does not work; Quantum Chorus changes the parts that rely on them.Source: §1 · pp. 1–2
• Quantum Chorus keeps Chorus’s dissemination-plus-two-vote fast path and replaces its certified-input fallback with Coda, a signature-free Byzantine agreement for multiple proposers.The fast path finalizes in three communication rounds, with speculative finality one round earlier, even when some proposers are offline.Source: §1 · p. 2
• Safety and liveness require no signatures, while post-quantum signatures are added for accountability; proofs of finality for outside parties are out of scope.The paper outlines certificate-free, signature-free changes to the Conductor but leaves its full specification and analysis to a later version.Source: §1 · p. 2
• With 200 validators, Quantum Chorus has latency comparable to Chorus and scales better as the number of proposers increases.In the simulation, with 20 proposers, validators finalized a slot about 200 ms after a proposer’s broadcast and reached speculative finality about 50 ms earlier.Source: §1 · p. 2

2 Background: Cadence and Chorus

• Each slot finalizes one block by independently running single-shot consensus, allowing slots to overlap without waiting for earlier blocks.The Conductor schedules slots and bounds the number that remain open.Source: §2 · p. 2
• At the deadline, validators vote per proposer on a valid proposal root or the empty value; each agreed entry selects that proposal or excludes it.Proposals are erasure-coded into n chunks, and any f + 1 chunks suffice to decode; the block includes selected proposals whose chunks are valid encodings.Source: §2 · p. 2
• The fast path takes three communication rounds—dissemination and two voting rounds—and validators finalize when they receive 2f + 1 matching fast votes.A validator may speculatively finalize one round earlier after assembling the fast meta-block; that speculation is reverted only if a validator equivocated.Source: §2 · p. 3
• If the fast path fails, a fallback uses a second voting round and validated Byzantine agreement to decide a certified meta-block before commit votes finalize the slot.The fallback may take over when a proposal reached only some correct validators by the deadline.Source: §2 · p. 3
• For slots starting at least GST + G, Chorus includes every correct proposer’s proposal, a property Quantum Chorus retains alongside agreement, termination, and speculative finality.Source: §2 · p. 3

3 Model

• The system has n = 3f + 1 validators, at most f Byzantine, communicating over authenticated point-to-point channels without assuming reliability.A broadcast or point-to-point send is retransmitted until explicitly abandoned; a forever-alive message from a correct validator eventually reaches every correct recipient.Source: §3 · p. 3
• A correct validator may crash temporarily and recover with persistent memory intact, while volatile state and unstored received messages are lost.The model assumes crashes do not abandon ongoing broadcasts, whose retransmission resumes after recovery.Source: §3 · p. 3
• After the unknown GST, message delays are bounded by ∆, and correct validators remain online from GST onward with synchronized clocks.Crashes occur only before GST and every crashed validator recovers before GST.Source: §3 · pp. 3–4
• Agreement, proposal inclusion, termination, and halting rely on authenticated channels and collision-resistant hashing; signatures support accountability.Each validator holds a key pair for a post-quantum signature scheme.Source: §3 · p. 4
• A slot is timely when its start time D − ∆ is at least GST and every correct validator begins participating by then.The paper expects the Quantum Cadence Conductor to ensure this for slots starting at least GST + G.Source: §3 · p. 4

4.1 Protocol Description

• The fast path finalizes a meta-block after matching fast entries for every proposer are supported by 2f + 1 path votes, without attaching certificates.Validators locally corroborate fast-entry claims with matching deadline votes; Fig. 1 describes the common timely-slot case as finalizing by D + 2∆.Source: §4.1 · pp. 4, 6, Figure 1 · p. 6
• If the fast path does not settle the slot, validators adopt entries from clean sets and submit their meta-blocks to Coda, which provides per-proposer strong unanimity.A clean set contains 2f + 1 accepted entries whose fast entries agree; adoption checks roots against reconstructed proposals before the fallback consensus.Source: §4.1 · pp. 7–8

4.2 Guarantees

• Quantum Chorus guarantees agreement; in timely slots, finalized blocks include all correct proposers’ proposals, and every correct validator eventually finalizes if all start participating.If speculative finalization differs from a correct validator’s final block, faulty-validator misbehavior can be proven.Source: §4.2 · p. 9
• Every correct validator eventually halts if all start participating, and if all have finalized by T, all halt by max(T, GST) + ∆.Dissemination, Vote, and PathVote messages each carry exactly one signature; correct validators initiate at most one Vote, PathVote, and Finalized broadcast.Source: §4.2 · p. 10
• With at most ⌊f/2⌋ Byzantine validators, failure to finalize by D + 2∆ yields proposer equivocation evidence or ⌊f/2⌋+1 signed negative votes for a proposer.The evidence is either two differently rooted Chunk messages signed by that proposer, or a Chunk plus negative Vote messages from different validators. Fewer than f+1 negative entries alone cannot prove blame, but the protocol guarantees the stated threshold under the ⌊f/2⌋ fault bound.Source: §4.2 · p. 10
• Coda’s first leaderless view decides within two message delays when all correct validators’ inputs coincide, so failure to decide quickly exposes disagreement traceable to a proposer or equivocating validator.This supplies a way to trace the disagreement underlying fallback evidence.Source: §4.2 · p. 10
• With Coda fallback, failure to finalize by D+4∆ in a timely slot yields evidence of a proposer’s fallback entry or validator equivocation.The evidence is either 2f + 1 PathVote messages from different validators with fallback entries for that proposer, or two Vote messages signed by the same validator with differing entries for that proposer, held by two correct validators.Source: §4.2 · p. 10

5 Coda: Our Fallback Consensus

• Coda implements the fallback agreement Quantum Chorus needs, with strong unanimity and obligation for each proposer and bounded persistent memory.For a fixed number of proposers, memory is constant in the number of validators when no proposer equivocated before Coda started, and at most linear otherwise; it does not grow with the number of views.Source: §5 · p. 10

5.1 Protocol Description

• The leaderless first view can decide within two message delays when all correct validators start after GST with the same meta-block.In the described late-proposal setting, it can finalize by D + 4∆ rather than D + 7∆; differing inputs, asynchrony, or Byzantine votes may prevent a view-1 decision.Source: §5 · pp. 10–11
• In view 1, validators vote for their own inputs; later, a leader proposes its guard, and validators vote only after the proposal is justified by prior-view echoes.Two voting rounds decide a meta-block once 2f + 1 vote-2 messages carry the same non-none lock.Source: §5.1 · pp. 11–13
• After a 5∆ timeout, validators use accepted vote-2 messages to echo safe values per proposer, then enter the next view when 2f + 1 echoes agree for every proposer.Conflicting locks cannot appear in an accepted set; without a lock, the echoed entry comes from guards shared by f + 1 messages, or is empty.Source: §5.1 · p. 13

5.2 Guarantees

• Coda guarantees agreement, termination when all correct validators start and continue participating, strong unanimity, and obligation, with the latter two properties defined per proposer.Agreement, strong unanimity, and obligation hold under arbitrary timing and when correct validators stop participating; termination requires every correct validator to start and none to stop. Under the stated participation convention, the first qualifying view with a correct leader decides within 5∆ of its first correct entry.Source: §5.2 · p. 14
• For each view, correct validators initiate at most 3 + (c + 1)k broadcasts, yielding O(ckn^2) messages and O(ck) persistent-memory words per validator.When c = O(1), the bounds become O(kn^2) messages and O(k) memory; c is the largest number of distinct inputs correct validators provide for any proposer.Source: §5.2 · p. 14

5.3 Differences from Forget-IT

• Compared with Forget-IT [1], Coda adds a leaderless first view and uses one amplified echo phase per proposer, with empty treated as an ordinary value.The changes provide strong unanimity and obligation per proposer, but a validator may echo multiple values per proposer, so messages and persistent memory can grow with the number of input values; Coda’s first correct-leader view after GST decides within 5∆ of its first entry.Source: §5.3 · p. 16

6 Integration with the Conductor

• The Conductor’s ACS and slot-completion rules need changes, but this version only outlines them and does not fully specify or analyze them.For crash-prone validators and unreliable channels, further retransmission changes are left to a later version.Source: §6 · p. 16
• A signature-free ACS can disseminate each proposal with reliable broadcast and use one binary agreement per validator to decide membership in the set.Coda can implement those binary agreements using one proposer and values 0 and 1.Source: §6 · p. 16
• A validator completes a slot when it halts, using the halting bound of max(T, H, GST) + 2∆ once all correct validators have started by T.It opens a window when it halts in the ACS instance that sets that window’s first deadline.Source: §6 · p. 16
• Validators retransmit cumulative FinalizedUpTo messages; f + 1 consistent chain reports let a validator fetch and finalize a prefix, while 2f + 1 allow it to halt there.The proposal expects the Conductor’s bounded-open-slot and timely-slot guarantees to carry over, but does not analyze them fully.Source: §6 · pp. 16–17

7 Evaluation

• The simulations use 200 equal-stake validators with 1 Gbps links and 5, 20, or 100 proposers, measure only the fast path without faults or message loss, and omit local computation.Each run measures the middle of three overlapping slots and averages 200 trials.Source: §7 · pp. 17–18
• With 20 proposers, speculative finality arrives about 50 ms before full finality, at 145–155 ms on average depending on signature size.The reported figure measures latency from proposer broadcast until a validator finalizes the slot.Source: §7 · p. 17
• Quantum Chorus scales better with proposer count because each vote carries one signature, whereas Chorus carries a signature or certificate for every proposer.With few proposers, large post-quantum signatures make Quantum Chorus use more upload than Chorus.Source: §7 · p. 17
• With 1 Gbps links, 5000-byte signatures add at most 16 ms to Quantum Chorus latency versus no signatures; Chorus leads by up to 19 ms at 5 or 20 proposers, while Quantum Chorus leads by up to 18 ms at 100.Source: §7 · p. 17

8 Related Work

• Under partial synchrony, deterministic Byzantine consensus is solvable; Quantum Chorus and Coda are deterministic protocols.The cited impossibility result concerns deterministic consensus under asynchrony, even with only one possible crash.Source: §8 · p. 18
• Signature-free partial-synchrony protocols trade latency and design choices: Forget-IT reaches three message delays, while Simple-IT allows pipelining with four.Coda builds on Forget-IT and uses Bracha-style amplification for view-change echoes.Source: §8 · p. 18
• Post-quantum alternatives either retain larger, slower aggregate certificates or avoid certificate messages; DQS uses local weak and strong certificates, and Quantumglow adopts that approach.Leader-mediated certificate dissemination in HotStuff-style protocols typically adds message delays compared with all-to-all voting.Source: §8 · p. 18

Use of AI Tools

• The authors take responsibility for the paper’s content despite using large language models to help draft and revise parts of the text and simulator.They describe the protocols and main ideas as their own.Source: Use of AI Tools · p. 18

• The appendix proves the lemmas of Section 4.Source: A Proofs for Quantum Chorus · p. 20

Core Properties

• A halting-gadget finalization repeats a finalization by a correct validator on the fast or fallback path.It follows from the gadget requiring f + 1 Finalized messages, including at least one from a correct validator that finalized earlier.Source: §A.1 · p. 20
• Quantum Chorus satisfies agreement: correct validators never finalize conflicting blocks for a slot.The proof compares meta-block entries across fast/fast, fallback/fallback, and mixed-path finalizations, using quorum intersection and fallback agreement.Source: §A.1 · p. 20
• If correct validators speculatively finalize different blocks, at least one faulty validator’s misbehavior can be proven.Source: §A.1 · p. 20

A. PROOFS FOR QUANTUM CHORUS

• A conflicting speculative finalization can be shown to expose a faulty validator’s signed votes that disagree with the speculative value.The proof uses the 2f + 1 matching votes held by the speculating validator and f + 1 non-matching votes held by a correct validator; their overlap identifies a validator that signed both.Source: A. PROOFS FOR QUANTUM CHORUS · pp. 21–22
• When a slot is timely, every finalized block contains the proposals of all correct proposers.The proof relies on correct validators receiving each proposer’s valid chunk by the deadline and adopting its Merkle root.Source: A. PROOFS FOR QUANTUM CHORUS · p. 22
• If every correct validator starts participating, every correct validator eventually finalizes a block for the slot.If no correct validator halts, the proof shows that correct validators eventually input meta-blocks to the fallback consensus, whose termination completes finalization.Source: A. PROOFS FOR QUANTUM CHORUS · pp. 22–23
• If every correct validator starts participating, every correct validator eventually halts.If all correct validators have finalized by T, they all halt by max(T, GST) + ∆.Source: A. PROOFS FOR QUANTUM CHORUS · p. 23

A.2 Complexity

• Each correct validator sends exactly one signature with every Chunk, Vote, or PathVote message.Vote and PathVote signatures cover the sender’s entire entry vector; chunks also carry a proposer-signed header.Source: §A.2 · p. 23
• Each correct validator initiates at most one Vote, one PathVote, and one Finalized broadcast; each proposer initiates at most one Chunk send per validator, retransmissions aside.Source: §A.2 · p. 23

A.3 Accountability

• With at most ⌊f/2⌋ Byzantine validators, failure to finalize by D+2∆ yields either conflicting proposer-signed chunk roots or a proposer-signed chunk plus ⌊f/2⌋+1 negative votes.The negative votes are from different validators and concern the same proposer.Source: §A.3 · p. 24
• Under the ⌊f/2⌋-fault bound, a correct fallback entry implies correct validators hold a proposer-signed chunk, which combines with either conflicting roots or enough negative votes to expose misbehavior.The fallback entry means fewer than 2f + 1 negative votes were observed; the proof then derives one of the two evidence forms.Source: §A.3 · p. 24
• With up to f Byzantine validators, a timely slot that has not finalized by D+4∆ yields either a fallback-entry quorum or two conflicting votes signed by one validator.The fallback quorum consists of 2f + 1 PathVotes from different validators for one proposer; the alternative is held jointly by two correct validators.Source: §A.3 · p. 24
• If correct validators have not finalized by D+4∆, their inputs to Coda cannot all be identical, leading to fallback entries or conflicting votes.When all correct validators input the same meta-block, they finalize by D+4∆; differing fast entries are ruled out by intersecting vote quorums.Source: §A.3 · p. 25

B Proofs for Coda

• The appendix is devoted to proofs of Coda’s guarantees.Its stated scope is the guarantees presented in Section 5.2.Source: B Proofs for Coda · p. 25
• The proofs concern Coda, with their model and conventions taken from Section 5.1.The passage identifies Section 5.1 as the basis for both.Source: B Proofs for Coda · p. 25
• Section 5.2’s stated guarantees are established under the assumptions and conventions of Section 5.1.Source: B Proofs for Coda · p. 25

Agreement

• Correct validators’ views only increase, and each broadcasts at most one vote of each kind per view, with its vote-2 message matching its lock and guard.These per-view constraints support the agreement proof’s quorum-intersection arguments.Source: §B.1 · pp. 25–26
• A decision in the earliest deciding view has a correct-voter residue that every quorum of vote-2 messages in that view must include.At least f + 1 correct validators broadcast vote-2 for the decided meta-block, and every set of 2f + 1 vote-2 messages intersects that set.Source: §B.1 · p. 27
• After the earliest decision, correct validators’ echoes and later vote-1 messages preserve its meta-block and proposer values.The agreement proof shows that entries into later views set guards to the decided meta-block, which constrains subsequent votes and echoes.Source: §B.1 · p. 27
• Coda satisfies agreement: no correct validators decide different meta-blocks.The proof propagates the value decided in the earliest deciding view through later echoes, guards, and votes.Source: §B.1 · p. 28

Termination

• Under the stated termination assumptions, some correct validator eventually enters every view.The proof uses eventual message delivery and post-GST timer progress to drive correct validators out of any purported last view.Source: §B.1 · pp. 28, 30

View progression

• For every post-GST view V, no correct validator echoes before τ(V)+5∆, and all correct validators are in V by τ(V)+2∆.The echo delay also implies τ(V+1)≥τ(V)+5∆.Source: §B.1 · p. 30

Termination

• By τ(V⋆)+5∆, every correct validator decides when all correct validators start by GST and none stops, where V⋆ is the first post-GST view above 1 with a correct leader.The correct leader’s proposal is justified by T+3∆, correct validators broadcast vote-2 by T+4∆, and the quorum is received by T+5∆, where T=τ(V⋆).Source: §B.1 · p. 31

Late starts

• If correct validators start at different times but none stops, termination still holds using T0=max(GST,Tstart) and the first later view above 1 with a correct leader.Here Tstart is the last correct validator’s start time; the decision bound remains τ(V⋆)+5∆.Source: §B.1 · pp. 31–32

Strong unanimity

• If all correct validators input the same value for proposer pj, every decided meta-block preserves that value in its pj entry.Correct echoes, vote-1 messages, and view guards retain the unanimous entry, which supports the strong-unanimity property.Source: §B.1 · pp. 32–33

Obligation

• Every nonempty proposer value in a decided meta-block was input for that proposer by some correct validator.The obligation invariant restricts correct validators’ messages and guards to empty or values input by a correct validator.Source: §B.1 · pp. 33–34

B.2 Complexity

• For each view and proposer, a correct validator broadcasts at most |Pj| + 1 distinct echoes, initiating each at most once.The admissible values are those in Pj plus empty; the validator retains its record while the view can still require echoes.Source: §B.2 · p. 34
• Each correct validator initiates at most 3 + (c + 1)k broadcasts per view; systemwide, retransmissions aside, this is O(ckn^2), or O(kn^2) when c=O(1).The per-validator bound counts prepare, vote-1, vote-2, and echo broadcasts.Source: §B.2 · p. 34
• Each correct validator stores O(ck) persistent-memory words for Coda, or O(k) when c=O(1).The bound includes variables for at most two views and tracking live broadcasts.Source: §B.2 · p. 34

B.3 Evaluating the View-Change Rule

• After 5∆ in view V, validators can determine the view-change rule's echoes from accepted-message counts instead of enumerating qualifying sets.The counts distinguish messages without locks, messages sharing a lock, and guard entries for each proposer.Source: §B.3 · p. 35
• A shared lock ℓ triggers an echo of its entry when at least one message has that lock and |Lℓ| + |U| ≥ 2f + 1.Here U contains accepted vote-2 messages without locks, and Lℓ those with lock ℓ.Source: §B.3 · p. 35
• Without locks, an entry v is echoed when |U| ≥ 2f + 1 and at least f + 1 messages in U carry v for proposer pj.The f + 1 matching messages plus f further messages form a qualifying set.Source: §B.3 · p. 35
• Without locks, empty is echoed when the capped counts sum to at least 2f + 1: Σ_w min(cj(w), f) ≥ 2f + 1.This corresponds to having enough messages while no entry reaches f + 1 in a qualifying set.Source: §B.3 · p. 35