PaperlayerView exact revision on arXiv

Source-linked AI summary

Cadence: Extreme Pipelining with Multiple Concurrent Proposers

Kushal Babel, Fatima Elsheimy, Lioba Heimbach, Mohammad Mussadiq Jalalzai, Tobias Klenze, Jovan Komatovic, Jason Milionis, Mike Setrin, Victor Shoup

arXiv:2607.02275v2cs.DC

TL;DR

Real-time financial markets place requirements on blockchain consensus, whose conventional interface Cadence departs from. Cadence separates per-slot agreement from slot scheduling and instantiates both in an independently pipelined MCP protocol. After GST, Chorus finalizes in two voting rounds; simulation reports 269 ms average end-to-end latency and 217 ms to speculative finality at a 100 ms block interval.

  • Problem

    Real-time financial markets place requirements on blockchain consensus, while Cadence’s consensus interface departs from conventional blockchain assumptions such as chained blocks and committed execution state.

    Source: §1 · p. 1, §6 · p. 19

  • Method

    Cadence separates within-slot agreement from across-slot scheduling, running one slot-consensus instance per slot alongside an orchestrator.

    Source: §1 · p. 4, §3 · p. 6

  • Results

    After GST, Chorus finalizes in two voting rounds; simulation reports 269 ms average end-to-end latency and 217 ms to speculative finality at a 100 ms block interval.

    Source: §1 · p. 4, How Fast is the Fast Path? · p. 12

  • Takeaways & Limitations

    The framework treats slot consensus and slot scheduling as largely independent concerns joined by a small amount of glue.

    Source: §3 · p. 6

    Proposer choice for transaction submission and the fee mechanism that would price that choice are outside scope.

    Source: §6 · p. 20

Abstract

from arXiv · show

We present Cadence, a Byzantine fault-tolerant multi-proposer consensus protocol with arbitrarily low block intervals, optimal resilience, and optimal fast-path latency. Cadence divides time into equally spaced slots, one block per slot, each finalized in its own consensus instance. Blocks do not build directly on their predecessor, so instances run independently and none waits for an earlier block to finish or propagate; we call this extreme pipelining, decoupling the block interval from network latency. Cadence also removes the single-leader monopoly over transaction inclusion and ordering: under multiple concurrent proposers (MCP), several validators propose for each block, and it guarantees that, under synchrony, a transaction a correct proposer includes cannot be censored or deferred (short-term censorship resistance), and that no proposer can craft its proposal in reaction to the others' (hiding). To realize extreme pipelining, we introduce a general framework that turns any one-shot consensus meeting our slot-consensus specification into a multi-shot protocol. We instantiate it for MCP with two protocols of our own: Chorus, a slot consensus whose fast path finalizes a block in an optimal three rounds, with speculative finality one round earlier, and Conductor, an orchestrator that opens slots at an even cadence, more slowly under asynchrony to keep open slots bounded. To our knowledge, Cadence is the first MCP protocol to provide short-term censorship resistance and hiding at the fast-path latency of single-leader consensus. We prove safety, liveness, censorship resistance, and hiding under partial synchrony with optimal resilience (n = 3f+1). In simulation over Monad's 200 validators with five proposers per slot, finalization averages 219 ms (167 ms to speculative finality); at a 100 ms block interval a transaction waits on average 50 ms to enter a proposal.

1 Introduction

Cadence combines multiple concurrent proposers with independent, regularly scheduled slot consensuses, aiming to reduce latency while preventing proposer monopoly. Its Chorus and Conductor components instantiate a modular framework for extreme pipelining.

Our protocol

  • Cadence combines Chorus, a per-slot MCP consensus, with Conductor, which schedules slots; it targets n = 3f + 1 resilience and partial synchrony.Each slot contributes one block in slot order, with proposals from concurrent proposers.Source: §1 · pp. 2, 4

Idea 3: a three-round fast path that tolerates offline proposers

  • A slot’s fast path finalizes in three communication rounds, even with offline proposers; speculative finality arrives one round earlier and is revertible only under provable equivocation.Partial dissemination or equivocation instead triggers a slower fallback path.Source: §1 · pp. 2–3

Requirement 1: no proposer monopoly

  • Short-term censorship resistance and hiding protect correct proposers’ contributions and prevent faulty proposers from reacting to others’ proposals.Cadence threshold-encrypts proposals and releases decryption shares at the deadline.Source: §1 · pp. 1–2

Idea 1: extreme pipelining

  • Extreme pipelining makes each slot an independent single-shot consensus, allowing block intervals below network delay without a stalled slot holding up others.Slots do not need a certificate or artifact from earlier slots to start.Source: §1 · pp. 2–3

Idea 2: deadlines rather than start times

  • Conductor uses synchronized-clock deadlines rather than shared start times, so the slowest proposer need not set the pace for proposal dissemination.Under asynchrony, fixed-size windows throttle slot openings to keep open slots bounded.Source: §1 · p. 3

In practice

  • In simulation with 200 Monad validators and five proposers per slot, at a 100 ms block interval end-to-end latency averaged about 269 ms, or 217 ms to speculative finality.The framework is modular: either the orchestrator or slot consensus can be replaced independently.Source: §1 · pp. 3–4

2 Multiple Concurrent Proposers (MCP): Problem Definition

The MCP problem concerns maintaining a growing, consistent ledger when several proposers contribute to each slot. Its guarantees address ledger consistency and progress, proposer censorship and reaction, and steady slot scheduling.

2.1 Setting

  • MCP slots have multiple proposers whose contributions should appear in the block, while validators maintain a consistent, growing ledger despite Byzantine faults and asynchrony.The setting assumes n = 3f + 1 validators, partial synchrony, and synchronized clocks; each slot has fixed proposers and a deadline.Source: §2.1 · p. 4

2.2 Guarantees

  • The guarantees are safety and liveness, short-term censorship resistance, hiding, and eventual stability, with censorship resistance and stability required after a grace period following GST.Safety means honest ledgers remain prefix-consistent; liveness means every slot eventually contributes a block.Source: §2.2 · p. 5
  • Censorship resistance ensures honest proposers’ contributions are not silenced, while hiding prevents faulty proposers from peeking and reacting; eventual stability requires deadlines to become regularly spaced.The grace period means censorship resistance need not hold for slots starting soon after GST.Source: §2.2 · pp. 5–6

3 Our Extreme-Pipelining Framework

The framework separates consensus within each slot from scheduling across slots, then composes one orchestrator with an independent consensus instance per slot. Because slots need no predecessor’s progress to start, the framework decouples block cadence from individual consensus latency while preserving ordered ledgers.

3 Our Extreme-Pipelining Framework

  • The framework composes a slot-consensus primitive for within-slot agreement with an orchestrator for scheduling, and any valid pair composes into an MCP protocol.The framework is also applicable to slot-based consensus beyond MCP.Source: §3 · p. 6, §3.1 · p. 6

3.1 Slot Consensus

  • Slot consensus gathers proposers’ proposals and produces one finalized block while providing agreement, termination, proposal inclusion, and hiding guarantees.Inclusion covers honest proposers that submit by the slot’s starting time after GST; hiding prevents a faulty proposer from learning honest proposals and then crafting an included response.Source: §3.1 · p. 6

3.2 Orchestrator

  • The orchestrator schedules deadlines and block intervals; its boundedness limits each correct validator’s underway slots, while recovery requires τ-spaced deadlines learned at least ∆ in advance.The advance notice gives honest proposers time to submit by the slot’s starting time.Source: §3.2 · p. 7, Interface & Guarantees · p. 7

Interface & Guarantees.

  • During asynchrony, withholding new deadlines when completion notifications stop keeps the number of running slot instances bounded.Bounding concurrent slots is necessary but not sufficient for bounded per-validator memory; per-instance memory must also be bounded, which is beyond this section’s scope.Source: Interface & Guarantees · pp. 7–8

3.3 Putting the Pieces Together

  • Validators start each slot’s consensus at its start time or when they learn its deadline, record finalized blocks, notify the orchestrator, and append buffered blocks in slot-number order.Out-of-order finalization therefore still yields a contiguous ledger sequence.Source: §3.3 · p. 8

Extreme Pipelining.

  • Slots can open every τ under favorable network conditions without waiting for an earlier slot’s artifact, certificate, or event, decoupling block cadence from per-slot consensus latency.The orchestrator may throttle slot creation to preserve boundedness, but completion notifications are not required to open a new slot.Source: Extreme Pipelining · pp. 8–9
  • Slot-by-slot agreement and ordered appends preserve consistent ledgers, while termination plus completion-driven scheduling lets slots continue contributing blocks.After GST plus the grace period, recovery restores τ-spaced deadlines; proposal inclusion and advance deadline notice together ensure on-time honest proposals reach the ledger.Source: Interface & Guarantees · p. 8, Extreme Pipelining · pp. 9–10

4 Chorus: Our Slot Consensus

This section presents Chorus’s concurrent-proposer slot consensus, its interwoven fast and fallback paths, and parallel proposal recovery. It sketches guarantees for agreement, termination, proposal inclusion, and hiding under stated conditions, and characterizes when speculative finality can be reverted.

The Object of Agreement.

  • Chorus agrees on a meta-block: one certified Merkle root or empty entry per proposer, with certificates establishing availability and negative entries justifying exclusion.Proposals are encrypted, erasure-coded, and committed by Merkle roots; deterministic encoding gives all correct validators the same verdict on a root, while its certificate ensures recoverability.Source: The Object of Agreement · pp. 10–11

How Fast is the Fast Path?

  • Under synchrony, when each proposer is correct or silent, Chorus finalizes in two voting rounds and permits speculative finalization after one round.Speculative finalization can be reverted only if a validator equivocated by sending conflicting votes for the same proposer; partial dissemination or equivocation forces fallback.Source: How Fast is the Fast Path? · p. 12

Description.

  • When the fast path fails, validators use no-fast-vote quorums to rule out fast commitment, then submit well-formed fast or fallback meta-blocks to per-slot agreement.Fallback entries use f + 1 matching fallback-yes votes for a root, an equivocation proof for conflicting roots, or f + 1 fallback-no votes for exclusion.Source: Description · pp. 13–14

4.4 From Meta-Blocks to Proposals (and Hence Blocks).

  • After agreement, validators recover the same proposal vector, never lose a correct proposer’s certified proposal, and deterministically merge valid, deduplicated transactions into the same block.For a positive root, validators reconstruct and re-encode the ciphertext to check it matches the root, decrypting it if valid and discarding it otherwise.Source: §4.4 · p. 15, Recovery Procedure · p. 15

Proposal Recovery Adds No Latency.

  • Proposal recovery adds no latency: fast-path blocks retain one-round speculative and two-round full finalization, while fallback recovery completes before fallback finalization.At the deadline, first-round votes carry chunks and slot decryption shares; those shares open every ciphertext for the slot. For fallback entries certified by f + 1 fallback-yes votes, chunk rebroadcast lets validators decode one ∆ later, before finalization.Source: Proposal Recovery Adds No Latency · pp. 15–16

4.5 Proof Sketch

  • Chorus prevents correct validators from finalizing different entries: quorum intersection rules out conflicting fast certificates and a fast-path/fallback split, while fallback agreement ensures a common decision.A fast quorum of 2f + 1 votes precludes the 2f + 1 no-fast-vote certificate needed to form a fallback meta-block.Source: §4.5 · p. 16
  • Every correct validator eventually proposes a fast or fallback meta-block, so fallback consensus termination ensures that the slot is finalized.Validators adopt a received fast meta-block; otherwise, they collect 2f + 1 fallback bundles and build a fallback meta-block.Source: §4.5 · p. 16
  • A timely honest proposal during synchrony is included: correct validators vote yes on its root, preventing exclusion on either the fast or fallback path.On fallback, validators reconstruct and re-encode the proposal; recovery then ensures it appears in the slot’s block.Source: §4.5 · pp. 16–17
  • Proposals are revealed only at the deadline, leaving too little time for an adversary to craft a competing proposal that can still be included.Source: §4.5 · p. 17
  • A different fallback decision can contradict speculative finality only through equivocation: conflicting roots or inclusion versus exclusion require overlapping votes that contradict each other.The proof uses quorum overlap because (2f + 1) + (f + 1) > n = 3f + 1; validators casting contradictory votes are equivocating.Source: §4.5 · p. 17

5 Conductor: Our Orchestrator

Conductor schedules slots in fixed-size windows, agreeing on each new window’s first deadline from validator proposals while keeping block production free of per-slot coordination. It throttles slot openings when finalization stalls, but resumes a gap-free τ-cadence after the network stabilizes.

5.1 Protocol Description

  • Conductor fixes each window’s deadlines in advance, and opens its successor only after the earlier windows and first p slots of the current window are complete.This makes the decision to open a window the orchestrator’s only per-window coordination.Source: §5 · p. 17, slots · p. 17, §5.1 · p. 17

slots:

  • A validator proposes the next window’s first deadline from its completion time: preserve the τ-cadence if it is keeping up, or use the current time to leave a catch-up gap if lagging.The remaining deadlines in that window are spaced τ apart.Source: slots · p. 18, Figure 11 · p. 18
  • Validators agree on the next first deadline by taking the median of a common ACS vector of 2f + 1 proposed deadlines, keeping it between the honest proposals’ extremes.At most f entries are Byzantine, so they cannot move the median outside that range.Source: slots · p. 18, Figure 12 · p. 18

5.2 Proof Sketch

  • At most 2W −p slots are underway at once, because a new window waits for earlier windows and the first p slots of the current window to complete.This bounds open slots even when finalization stalls.Source: §5.2 · p. 19, slots · p. 19
  • Once the network stabilizes, the schedule returns to gap-free τ-spaced deadlines if the first p slots, Chorus, and ACS fit within a window: Tp + ℓChorus + ℓacs ≤ Wτ.From the first good window onward, the schedule remains smooth.Source: §5.2 · p. 19, Figure 13 · p. 19

6 Deploying Cadence as Part of a Blockchain

Cadence’s consensus commits encrypted proposal digests without parent links or execution, so it does not directly provide the usual blockchain interface. The deployment approach constructs valid proposals against a shared settled state, translates committed proposals deterministically into execution blocks, and certifies history and state separately.

6 Deploying Cadence as Part of a Blockchain

  • Cadence commits proposal digests without executing transactions or linking slots to parents, requiring additional mechanisms to recover ordinary blockchain behavior.Proposers also build without seeing the current executed state or other proposals in their slot.Source: §6 · pp. 19–20

6.1 Proposal Construction and Validity

  • Because execution trails consensus and proposers cannot see peers’ proposals, proposals are built under state, peer, and temporal uncertainty.The temporal blind spot also includes proposals from recent slots.Source: §6.1 · p. 20
  • A shared settled state can serve as the validity reference; translation reapplies that check so transactions invalid against the reference stay out of execution blocks.A proposer can also check its own recent proposals, which are not yet visible to others.Source: §6.1 · p. 20
  • An execution-certificate ticket ties a proposal to the executed state at slot s −ξ, preventing valid proposals from advancing more than ξ slots beyond certified execution.Tickets cannot be checked at voting time, so translation filters proposals with missing or invalid tickets.Source: §6.1 · p. 20

6.2 Translation: From Meta-Block to Execution Block

  • Translation deterministically merges committed proposals over a fixed translated prefix, removing invalid transactions, deduplicating survivors, and ordering them, for example by priority fee.Consensus commits the per-proposer entries; translation turns them into the execution block.Source: §6.2 · pp. 20–21, §6 · p. 20

6.3 Certifying State and History

  • Prefix certificates separately attest committed history and executed state, restoring the coverage that a traditional block certificate provides together.Chain certificates attest committed slots; execution certificates attest committed and executed slots and the resulting state root.Source: §6.3 · p. 21

7 Practical Considerations

Cadence’s deployment considerations address accountability when the fast path fails, latency choices, economic ticks, and privacy trade-offs. Several mechanisms have explicit scope conditions: accountability attribution depends on synchrony and at most f/2 Byzantine validators, while transaction submission choices and fee pricing are outside the deployment discussion’s scope.

7.1 Accountability

  • Fallback accountability can identify partial dissemination with transferable signed evidence when at most f/2 validators are Byzantine and, for attributing a fallback to a proposer, after GST.A single fallback is not itself grounds to act under asynchrony, when even a correct proposer can miss the fast path.Source: §7.1 · p. 22

7.2 Latency, Scheduling, and Economic Ticks

  • An honest proposer can disseminate as late as δ before the deadline when its actual delay is δ < ∆, trading fresher transactions against the risk of triggering fallback through partial delivery.The accountability mechanism leaves evidence of partial dissemination.Source: §7.2 · p. 22, §7.1 · p. 22
  • Early voting can reduce finalization latency when every proposer’s entry is positive, while decryption shares remain withheld until the deadline to preserve hiding.The latency saving depends on how much margin proposers leave before the deadline.Source: §7.2 · p. 23
  • Economic cycles can make on-chain activity tick more finely, but do not reduce end-to-end latency because transactions are still finalized once per slot.Chorus could support cycles by dividing each proposer’s proposal into K parts with separate deadlines.Source: §7.2 · p. 23

7.3 Transaction Privacy

  • Proposal hiding leaves a user’s submitted transaction visible to its chosen proposer, so submitting to more proposers improves inclusion and censorship resistance but increases leak or front-running exposure.Client-side encryption can remove this trade-off, but does not replace MCP’s short-term censorship resistance or proposal encryption’s protection between competing proposers.Source: §7.3 · p. 23

8 Latency Evaluation

A simulation calibrated to Monad’s 200 globally distributed validators estimates Cadence’s fast-path latency with five concurrent proposers per slot. Average full-finalization latency is 219 ms, while speculative-finalization latency is 167 ms; at a 100 ms block interval, average inclusion latency is 50 ms.

8 Latency Evaluation

  • 219 ms to full finality and 167 ms to speculative finalization; with 50 ms inclusion latency at τ = 100 ms, end-to-end latency averages 269 ms and 217 ms, respectively.With early voting, end-to-end latency averages 241 ms to full finality and 187 ms to speculative finalization.Source: §8 · p. 23
  • The estimates use a simulation calibrated to RIPE Atlas round-trip measurements across 83 city-ASN groups, with five concurrent proposers per slot.Proposer lead time averages 104 ms, set so 99% of trials deliver chunks to at least 90% of validators before the deadline.Source: §8 · p. 24
  • Simulated propagation delays dominate the reported end-to-end latency; local processing and bandwidth-induced queueing are omitted, with queueing estimated at no more than a few milliseconds.The latency estimate concerns the fast path, where each proposer is correct or fully silent.Source: §8 · p. 24

9 Related Work

Prior pipelining approaches reduce proposal intervals to the network-delay bound, while Cadence’s independent, non-chained instances achieve sub-∆ intervals. Related MCP designs pursue censorship resistance through different mechanisms, but Chorus combines short-term censorship resistance with optimal three-round good-case latency.

9.1 Pipelining

  • Independent, non-chained single-shot instances let Cadence achieve sub-∆ block intervals, below the network-delay floor of chained pipelining.Chained quorum-certificate pipelines reach 2∆, while optimistic designs reach ∆ by proposing before prior proposals are quorum-certified.Source: §9.1 · p. 24
  • Shoal++, Raptr, and Gatling also reach sub-∆ intervals by staggering multiple instances, whereas Cadence runs one sequence of independent single-shot slots.Constellation’s short economic ticks complement extreme pipelining, but its underlying consensus remains bounded by network delay.Source: §9.1 · p. 24

9.2 Multiple Concurrent Proposers

  • Chorus is the first MCP design reported to combine short-term censorship resistance for every post-GST block after a grace period with optimal three-round good-case latency.Prior work pursued censorship resistance through different mechanisms; only Garimidi et al. [1] incorporated hiding into their protocol design.Source: §9.2 · p. 24
  • Prefix Consensus has comparable good-case latency but permits up to f adversarially chosen slots without censorship resistance, unlike Chorus’s bounded post-GST grace period.In Chorus, the adversary cannot choose later slots to fall outside the censorship-resistance guarantee.Source: §9.2 · p. 24
  • Constellation and AMP add two communication rounds by separating proposal dissemination from agreement; DAG protocols do not target the required strict short-term censorship guarantee.Constellation’s attesters constrain leader inclusion; AMP guarantees bounded inclusion for payloads attested by all correct validators at one height.Source: §9.2 · pp. 24–25

Organization of the Appendix

The appendix formalizes the MCP problem and the entities, inputs, logs, and guarantees used to state it. It defines fixed slot metadata and proposal vectors, then specifies the protocol interface and correctness properties.

Organization of the Appendix

A.1 Preliminaries

  • Each slot has a positive integer number, a fixed deadline, and a fixed set of designated proposers; protocol timing adapts by skipping slots rather than moving deadlines.In the extreme-pipelining framework, consecutive deadlines are a known interval τ apart, and the first slot starts at time 0.Source: §A.1 · p. 27
  • A proposal vector maps each slot proposer to its own proposal or ⊥, and serves as the consensus-level representation of a block.An application can deterministically order transactions and discard invalid ones when transforming the vector into a block.Source: §A.1 · p. 27

A.2 Interface

  • For each slot, designated proposers supply proposals and validators maintain append-only local logs as the protocol output.Correct validators initialize their logs as empty.Source: §A.2 · p. 28

B Our Extreme-Pipelining Framework: Formal Exposition

The extreme-pipelining framework composes abstract slot-consensus instances with an orchestrator that opens slots, while preserving ordered logs despite concurrent, out-of-order finalization. Its guarantees derive from the two components’ specifications, including bounded concurrency and recovery conditions.

B Our Extreme-Pipelining Framework: Formal Exposition

  • Cadence instantiates the framework with Chorus as slot consensus and Conductor as orchestrator; the framework itself composes these abstract components.The framework’s properties, including Byzantine resilience, are inherited from the component specifications rather than hard-coded into the composition.Source: B Our Extreme-Pipelining Framework:… · p. 30, §B.2 · p. 33

B.1 Building Blocks: Slot Consensus & Orchestrator

  • Slot consensus accepts participation signals and designated proposers’ proposals, then finalizes one proposal vector for its slot.Its guarantees include agreement, termination, slot safety, proposal inclusion, hiding, and quiescence; correct proposals submitted by the slot’s starting time are included under synchrony.Source: §B.1 · p. 30
  • The orchestrator has no explicit skip output: a slot never opened is skipped, equivalent in the fixed-deadline model to pushing its deadline back.Deadlines are read-only and τ-spaced, so skipping intervening slots permits opening one whose fixed deadline matches the desired later time.Source: §B.1 · p. 30
  • The orchestrator opens slots in total, unique, increasing order and never before their start times; B-boundedness limits pending slots and R-recovery requires timely opening without skipping after stabilization.B-boundedness also bounds active slot-consensus instances, which the framework uses as a proxy for memory consumption.Source: §B.1 · pp. 31–32
  • R-recovery requires slots starting at least R after GST to be opened at their starting times, because late opening can forfeit proposal inclusion.The passage explains that Byzantine validators may then suppress correct proposers’ proposals, potentially leaving an empty finalized vector.Source: §B.1 · p. 32

B.2 Composing the Building Blocks

  • On opening a slot, the framework starts its consensus instance and submits a proposal if the validator is designated; finalization triggers completion notification and abandonment.A finalized vector is buffered until all smaller-numbered slots are either skipped or finalized and appended, preserving slot order in the log.Source: §B.2 · p. 33
  • The framework can use other resilience thresholds, single-leader slot consensus, or linear-communication consensus by changing its components without changing the composition.The paper’s instantiation uses n = 3f + 1 validators, but the framework itself imposes no such constraint.Source: §B.2 · pp. 33–34

B.3 Proof

The framework’s proof establishes safety, liveness, censorship resistance, hiding, and bounded concurrency from its component properties. The paper then specifies Chorus as Cadence’s slot-consensus protocol and describes the cryptographic primitives it uses.

B.3 Proof

  • The framework satisfies safety and R-liveness, with liveness following from slot termination, orchestrator recovery, and ordered resolution of earlier slots.The proof also establishes R-censorship resistance through timely opening and slot-level proposal inclusion, and hiding by composing the hiding guarantees of each slot instance.Source: §B.3 · pp. 34–35
  • The framework satisfies B-bounded concurrency because a validator participates in a slot instance only while its slot is open and incomplete.This transfers the orchestrator’s B-boundedness guarantee to the number of active consensus instances.Source: §B.3 · pp. 35–36

C Chorus: Our Slot Consensus for Cadence

C.1 Cryptographic Primitives

  • Chorus uses Merkle trees for chunk commitments, signatures for authentication and aggregation, and erasure coding so any f + 1 fragments reconstruct ciphertext.Its simulation models several hash functions as distinct random oracles; implementations should use domain-separated hashing and unambiguous input encodings.Source: §C.1 · p. 36

C.2 Proposal Encryption and Slot-Key Release

This section describes how Cadence hides slot proposals through encryption and deadline-based slot-key release, then uses Chorus to gather votes and commit a meta-block. It covers Chorus’s fast path and its fallback path when fast commitment fails.

C.2 Proposal Encryption and Slot-Key Release

  • Validators release shares for the slot identity at its deadline, reconstructing one slot key that can open any well-formed proposal ciphertext for that slot.Extraction shares depend on the identity, not an individual proposal ciphertext; after reconstruction, decapsulation is an ordinary non-threshold operation.Source: §C.2 · pp. 36–38

C.3 Protocol

  • Chorus has three phases: proposal dissemination, deadline voting by validators, and meta-block commitment through parallel fast-path and fallback modules.The fallback module gathers per-proposer evidence, runs multi-valued validated Byzantine agreement, and commits its output after a final round of commit votes.Source: §C.3 · p. 39

Dissemination & Voting

  • A validator’s deadline vote records a signed positive or negative entry per proposer, supplies chunks for positive entries, and releases its slot decryption share.A 2f + 1 FastQC for a positive entry certifies that at least f + 1 honest validators hold chunks, supporting data availability. If partial dissemination prevents a FastQC for any proposer, validators use the fallback path; the MVBA output is confirmed with a final round of fallback commit votes.Source: Dissemination & Voting · pp. 40, 42
  • After collecting 2f + 1 fast commit votes carrying the same entries entries(B), a validator aggregates their signatures into a CommitQC; upon receiving a valid fast CommitQC, it rebroadcasts it and finalizes recovered proposals.Source: Dissemination & Voting · p. 43
  • After the deadline and Δ, a validator not on the fast commit path broadcasts a fallback vote; 2f + 1 fallback votes certify that the slot’s fast path can no longer commit.Each vote includes a FastQC when available, otherwise the proposer’s fallback signed entry.Source: Dissemination & Voting · p. 44
  • Fallback meta-blocks select each proposer’s strongest available evidence—FastQC, EquivCert, or FallbackQC—and a counting argument ensures one exists for every proposer.An EquivCert pins a proposer to two contradictory signed roots, certifying exclusion when Byzantine chunk splitting prevents a FallbackQC; otherwise, non-conflicting signed entries over a root or ⊥ yield f + 1 matching entries.Source: Dissemination & Voting · pp. 42, 44
  • Validators propose valid meta-blocks to the slot’s MVBA at most once; it decides one valid block consistently, with termination conditional on correct participation and no premature abandonment.MVBA also guarantees integrity and quiescence; validators abandon their invocation after finalizing the slot.Source: Dissemination & Voting · p. 44
  • A fallback commit certificate finalizes the decided meta-block and certifies data availability because 2f + 1 signers rebroadcast distinct assigned chunks before voting.Validators wait for their assigned chunks for positive FallbackQC-backed entries, rebroadcast them, and then vote; they recover and commit proposals on receiving the certificate. A fast CommitQC can still finalize a slot after MVBA begins.Source: Dissemination & Voting · pp. 44–45

Data Availability.

The data-availability module verifies and reconstructs proposals from disseminated chunks, then supports their recovery at commit time. Its checks make accepted or rejected roots consistent across correct validators.

Data Availability.

  • Validators verify proposer signatures and Merkle proofs, then confirm a root by decoding and re-encoding after f + 1 valid chunks arrive.A mismatch marks the root invalid; assigned chunks received by the deadline also let validators record a positive entry.Source: Data Availability · p. 45
  • Validators release slot decryption shares with their votes; f + 1 valid shares decrypt a reconstructed proposal or mark its root invalid.Reconstructing encrypted proposal chunks alone does not reveal the proposal.Source: Data Availability · p. 45
  • At commit, recovery waits until every positive entry is recovered or marked invalid, and returns proposals once that condition holds.FastQC and FallbackQC paths each provide enough honest chunks for decoding; deterministic re-encode checks give correct validators the same verdict and ciphertext.Source: Data Availability · p. 45

C.4 Proof

This section establishes Chorus’s slot-consensus properties in Cadence, distinguishing termination, which requires Δ-synchronized participation guaranteed by Conductor, from quiescence, hiding, slot safety, agreement, and proposal inclusion, which hold unconditionally. Under Δ-synchronized participation, Chorus’s termination bound is max(t, GST) + 5Δ + ℓMVBA.

Proof

  • Chorus satisfies quiescence, hiding, and slot safety unconditionally.The stated exception to unconditional properties is termination, not these three properties.Source: §C.4 · pp. 45, 48

Agreement

  • Chorus agreement follows because any two commitment proofs carry the same entries, and deterministic recovery maps those entries to the same proposal vector.The proof establishes matching entries across fast and fallback commitment proofs, then shows that validators resolving the same entries recover the same vector.Source: §C.4 · pp. 48–49

Proposal inclusion

  • If a correct proposer disseminates its proposal at s.deadline − ∆ with s.deadline − ∆ ≥ GST, every valid meta-block includes its positive proposal entry, which Chorus recovers.The proof applies to both fast and fallback evidence; a correct proposer’s proposal is therefore included in the finalized proposal vector.Source: §C.4 · pp. 49–50

Termination

  • With ∆-synchronized participation, if one correct validator finalizes at time t, every correct validator finalizes by max(t, GST) + ∆.In Cadence, ∆-synchronized participation means correct validators start participating in a slot within ∆; Conductor’s totality guarantee provides this condition.Source: §C.4 · p. 50
  • If all correct validators start by t, participation is ∆-synchronized, and none stops before T = max(t, GST) + 4∆ + ℓMVBA, Chorus finalizes for all by T.This termination bound is stated for Chorus running within Cadence.Source: §C.4 · p. 51

Termination proof

  • After M + 3∆, all correct validators propose to MVBA and hold required fallback chunks; MVBA decision, commit certificates, and recovery then yield finalization by T = M + 4∆ + ℓMVBA.Here M = max(t, GST), and the proof assumes no correct validator finalizes by T − ∆; otherwise totality gives finalization by T.Source: §C.4 · p. 51

Termination

  • Every correct validator finalizes by max(t, GST) + 5∆ + ℓMVBA when participation is ∆-synchronized and Chorus runs within Cadence.The bound follows by combining totality if any correct validator finalizes by max(t, GST) + 4∆ + ℓMVBA, and termination otherwise.Source: §C.4 · p. 52

Correctness of Chorus

  • Chorus correctly implements slot consensus within Cadence under ∆-synchronized participation; quiescence, hiding, slot safety, agreement, and proposal inclusion hold unconditionally.Termination is the property that requires both stated assumptions.Source: §C.4 · p. 52

D Conductor: Our Window-Based Orchestrator for Cadence

Conductor orchestrates Cadence by scheduling slots in windows and opening a new window only after enough earlier slots complete. Agreement on a core set (ACS) aligns validators on the next window’s starting slot, while readiness conditions support recovery after asynchrony.

Agreement on a Core Set (ACS).

  • ACS lets validators agree on a set containing at least n − f submitted proposals, with agreement, validity, integrity, termination, and totality properties.Only its timing properties, ℓ-termination and ∆-totality, depend on the stated assumptions.Source: Agreement on a Core Set (ACS) · pp. 52–53

D Conductor: Our Window-Based Orchestrator for Cadence

Agreement on a Core Set (ACS).

  • Conductor’s W and readiness threshold p must satisfy four timing inequalities so window work fits its span and recovery can resume consecutive windows after synchrony.The assumptions relate ACS and Chorus termination, slot spacing τ, and Chorus totality latency.Source: Agreement on a Core Set (ACS) · p. 53

D.1 Protocol

  • At startup, validators open the first W slots at τ-spaced times; thereafter, a slot is complete when its proposal vector is finalized.Conductor’s ACS interface starts participation upon proposing and stops it upon abandonment.Source: Agreement on a Core Set (ACS) · p. 53

Agreement on a Core Set (ACS).

  • A validator proposes the next window’s earliest eligible slot once every earlier window and the first p slots of the current window are complete.If the schedule is lagging, the estimated start is pushed forward to leave a gap for backlog to drain.Source: Agreement on a Core Set (ACS) · pp. 53–54
  • Validators use ACS to agree on the next window’s start, taking the median of decided estimates so at most f faulty values cannot move it beyond the honest estimates.The chosen start schedules W slots; validators abandon the ACS instance only after it decides.Source: Agreement on a Core Set (ACS) · p. 54

D.2 Proof

The proofs establish Conductor’s scheduling, synchronization, recovery, and correctness guarantees in Cadence, including eventual window entry and a gap-free schedule after GST under stated parameter constraints. They also set up stronger totality when Conductor runs with Chorus and explain how timing guarantees bootstrap across windows without circular dependence.

Window Structure

  • Consecutive windows cover non-overlapping ranges of W slots, and any slot assigned a window by two correct validators is assigned the same window by both.For later windows, the ACS-decided slot advances by at least W from the previous window’s decided slot.Source: §D.2 · p. 56

Integrity and Monotonicity

  • Conductor satisfies integrity and monotonicity unconditionally: it opens each slot at most once and not before its starting time, and schedules lower-numbered slots first.The proof derives scheduling order from increasing slot order within windows and validators’ increasing order of window entry.Source: §D.2 · p. 57

Boundedness

  • Conductor satisfies (2W − p)-boundedness unconditionally, limiting each correct validator to at most 2W − p opened but uncompleted slots.The readiness rule allows at most W − p earlier slots to remain incomplete before adding the next window’s W slots.Source: §D.2 · p. 58

Totality

  • If a correct validator opens slot s at time t, every correct validator opens it by max(t, GST) + Δ_tot when Conductor runs with Chorus in Cadence.This Δ_tot-totality bound is stronger than eventual agreement on openings and is needed for the recovery proof.Source: §D.2 · p. 58
  • The totality proof uses strong induction over windows, bundling synchronization of each window’s entry, openings, completions, and proposals to the next ACS instance.The stated induction rationale is that Chorus’s totality latency and synchronization tolerance are both Δ_tot, allowing synchronization to carry across windows without degradation.Source: §D.2 · pp. 58–59

D.2 Proof

  • For every window, correct validators’ entry, openings, completions, and proposals are synchronized; ACS proposals occur within max(t, GST) + ∆tot.Proposal synchronization applies to ACS[ω] for ω ≥2; entry synchronization has the same bound.Source: §D.2 · pp. 59–60
  • If a correct validator opens or completes a slot at time t, every correct validator does so by max(t, GST) + ∆tot.Conductor’s totality result gives this bound for openings; completion synchronization inherits the same bound.Source: §D.2 · p. 61
  • Every correct validator eventually enters every window, and enters each by max(T1(ω), GST) + ∆tot + ℓ.The entry-time bound relies on the ACS termination assumptions established through proposal synchronization and no premature abandonment.Source: §D.2 · pp. 61–62
  • The timing guarantees require (p −1)τ + Φoc + ℓ≤Wτ, (p −1)τ + Φoc ≤(W −1)τ, ∆< ℓ, and ∆tot + ℓ≤(p −1)τ.Here Φoc = ℓchorus + ∆tot; the constraints ensure the work for a window fits its Wτ span.Source: §D.2 · p. 62
  • When all correct validators enter a post-GST window ω by Tp(ω), the next window starts with the consecutive slot number and is entered by T1(ω + 1).The next window’s first slot number is slot(ω, W).number + 1.Source: §D.2 · p. 63
  • From the second post-GST window onward, consecutive windows have no gaps and every slot opens at its starting time, s.deadline −∆.This holds for every window after the smallest post-GST window.Source: §D.2 · pp. 63–64
  • The first post-GST window starts by GST + Wτ, bounding when correct validators propose to its ACS.The proof bounds the starting time of each validator’s proposed slot by GST + Wτ.Source: §D.2 · p. 64
  • The cited passage reports Lemma 16’s recovery result: when Conductor (Algorithm 7) is run within Cadence (Algorithm 1), it satisfies (2Wτ)-recovery.Source: §D.2 · p. 64
  • Conductor is correct within Cadence with boundedness B = 2W − p and recovery R = 2Wτ.Integrity, monotonicity, and boundedness hold unconditionally; totality and recovery hold when Conductor runs within Cadence.Source: §D.2 · p. 65
  • Within Cadence, Conductor’s totality makes participation in every slot consensus instance ∆-synchronized, so Chorus is a correct slot consensus implementation.A correct validator starts participating in a slot instance exactly when it opens that slot.Source: §D.2 · p. 65
  • The protocols’ timing guarantees bootstrap without circularity: synchronized window-1 openings anchor alternating window-by-window guarantees for Chorus finalizations and Conductor participation.Each window uses guarantees already established for earlier windows, then applies Chorus’s conditional totality to obtain synchronized completions.Source: §D.2 · p. 65

Related papers

Loading 2607.02275v2…