1 Introduction↩︎

Blockchains increasingly host real-time financial markets, and serving them well places three requirements on the consensus layer. We motivate each, then present our design.

Requirement 1: no proposer monopoly. Currently, most deployed protocols use a rotating leader schedule, where there is a uniquely identified entity (the leader) with the short-lived outsized ability to control the inclusion, exclusion and ordering of transactions.² Recent proposals have emerged to induce competition among the parties that contribute to a block, in what are called multiple concurrent proposer (MCP) designs. There, a proposer schedule rotates the role over time, much as a leader schedule does, but names a more diverse, small set of validators per block who are allowed to simultaneously make their proposals. A combination arising from these different simultaneous proposals ends up forming the final block. To this end, a number of properties form axes along which such designs can be evaluated: Short-term censorship resistance [1] guarantees that a correct proposer’s proposal is included in the block it contributes to, not dropped or deferred to a later block; so a transaction that reaches a correct proposer is included without delay, as long as the proposer has space for it. Hiding [1] keeps each proposal concealed from the other proposers until it is too late for them to react with a proposal of their own. In this way, a proposer cannot condition their proposal’s contents on the other ones, and proposals are truly simultaneous.³

Requirement 2: low latency. On-chain applications such as trading demand low latency. A transaction passes through several stages, each adding latency: the time to reach a proposer, the wait to enter a proposal (on average half the block interval), the propagation of that proposal across the network, the consensus voting rounds needed to reach finality (whether speculative or full), and finally the execution that produces the result the application observes.

Requirement 3: short economic ticks. An economic tick is the shortest time to inclusion of a transaction in any proposal. Since transactions might provide—among others—price updates, finer granularity in transaction inclusion enables more frequent state updating; for example, it might allow reducing arbitrage profits in decentralized exchanges. [2]

Most recent MCP designs [1], [3] run a separate proposal-and-aggregation phase before the consensus: each proposal is first attested by a quorum, and these attestations limit the discretion of a single leader who assembles the block for an off-the-shelf consensus. This added phase costs two extra communication rounds, sacrificing the desideratum of low latency. Our proposal aims to avoid that cost by incorporating the multiple proposers directly into the consensus.

1.0.0.1 Our protocol.

We present Cadence, an MCP Byzantine fault-tolerant protocol that runs among \(n = 3f + 1\) validators, up to \(f\) of which may be Byzantine, under partial synchrony. Using synchronized clocks, Cadence divides time into slots, each contributing exactly one block to the ledger in order of their slots, and combines two components, illustrated in 1: Chorus, a single-shot MCP consensus run for each slot, and Conductor, which schedules the slots, normally at a regular interval \(\tau\) (the block interval). Within a slot, multiple proposers contribute concurrently, as in any MCP protocol; Cadence additionally produces blocks concurrently across slots, each decided by its own independent single-shot consensus with no chaining between them, so the slots overlap. We call the latter extreme pipelining. The protocol also provides short-term censorship resistance and hiding, the latter by threshold-encrypting each proposal and releasing the decryption shares at the deadline. On the fast path, it finalizes a slot in an optimal three communication rounds, even when some proposers are offline. A slot reaches speculative finality one round earlier, revertible only under provable equivocation. We target blockchains with asynchronous execution [4], where validators commit to digests of proposals, each a list of transactions; invalid proposals and transactions are discarded deterministically afterward, when the committed data is turned into an execution block, the ordered list of transactions to be executed.

Together, these features let Cadence meet all three requirements. Its multiple concurrent proposers remove the single-proposer monopoly, and short-term censorship resistance and hiding keep any one proposer from suppressing a transaction or reacting to the others’ proposals (Requirement 1). For low latency (Requirement 2), Cadence shortens several of the stages a transaction passes through: having many proposers means one is likely near each user, shortening the hop to a proposer; its arbitrarily low block intervals shorten the wait to enter a proposal; and its fast path reaches (speculative) finality with optimal latency. Execution results are certified separately from the main protocol, as soon as they are available (6.3). Those same low block intervals keep economic ticks short, since transactions enter proposals frequently (Requirement 3).

1.0.0.2 Key ideas.

Five ideas underlie our design.

Idea 1: extreme pipelining. We make every slot an independent single-shot consensus instance, scheduled by Conductor using synchronized clocks. Slots do not chain⁴: no certificate or artifact from an earlier slot is needed for a slot to start, and every opened slot finalizes exactly one block. The usual way to shrink the block interval is pipelining, overlapping the consensus of consecutive blocks; but traditional pipelining chains each block to its predecessor, so the next cannot begin until the previous proposal has propagated, leaving the interval floored at the network delay \(\Delta\). Removing this dependency on the previous block lets the block interval drop below \(\Delta\), and because block production normally does not wait on any slot to finish, a slow or stalled slot does not hold up the rest. Traditional pipelining complicates protocols, in particular with multiple proposers.⁵ Extreme pipelining, however, makes the per-slot consensus simpler: each Chorus instance is single-shot rather than multi-shot, reasoning about only one block at a time.

Idea 2: deadlines rather than start times. Waiting for all proposers would let the slowest one set the pace. In most major proof-of-stake blockchains, stake concentrates in a few mutually well-connected regions, with a long tail of distant validators; with many concurrent proposers, at least one is likely to be drawn from that tail. In Cadence, rather than coordinating on when proposers start, validators rely on a synchronized clock to fix, for each slot, a common deadline by which its proposals must have arrived: a fixed point in time, the same for every validator and, under steady operation, known in advance. Each proposer chooses its own broadcast time to meet this deadline, according to its own network conditions: later when the network is fast, earlier when it detects delays. A shared start time would require a common timeout that accommodates the slowest proposer. A shared deadline instead fixes when proposals must arrive, so that the slowest proposer no longer sets the pace for proposal dissemination.

Idea 3: a three-round fast path that tolerates offline proposers. The simplest fast path would finalize a slot only when all of its proposers are online and correct. But in that case, a single missing proposer would make the fast path unavailable. Instead, in our protocol, validators judge each proposer separately at the deadline, voting yes or no on whether its proposal arrived. Once a quorum forms for each proposer, one way or the other, validators cast commit votes, and a quorum of commit votes finalizes the slot, two rounds after the deadline. This is the good case, where every proposer is either online and correct, or offline. Neither voting round uses a timeout, so a slot finalizes as fast as its votes propagate. The fast path is unavailable if some proposal reaches only some correct validators but not others (partial dissemination) or if a proposer sends conflicting proposals (equivocation). In that case, Chorus finalizes through a slower fallback path, which relies on an off-the-shelf agreement protocol.

Idea 4: agreement on digests, proposal dissemination in parallel. Following DispersedSimplex [5], validators agree on Merkle roots of encodings of the proposals, not on the proposals themselves. Traditionally, consensus disseminates the data before voting on it, which adds latency, in particular for large payloads. Because asynchronous execution lets validators vote on digests rather than on the payload, dissemination can instead run in parallel with consensus. A committed Merkle root comes with an explicit guarantee: its data can be recovered, or, if invalid, deterministically rejected by all honest validators.

Idea 5: bounding open slots under asynchrony. Conductor opens slots at a regular cadence, one every \(\tau\), without waiting to see how the open ones fare; since each slot runs independently, many can be open at once. Under asynchrony, slot production must be throttled when finalization stalls, or the open slots would accumulate without bound; Conductor therefore groups slots into fixed-size windows and opens a new window only once enough slots of the earlier windows have finalized, keeping the number of open slots bounded (boundedness). Once the network stabilizes, it returns to a steady cadence, with consecutive deadlines spaced \(\tau\) apart and known at least \(\Delta\) in advance (recovery).

1.0.0.3 A generic framework.

Underlying Chorus and Conductor is our generic extreme-pipelining framework that composes any slot consensus, responsible for everything within a slot, with any orchestrator, responsible for scheduling the slots. The design is modular: either component can be swapped out without affecting the other. For example, instantiating the orchestrator with one that sets the block interval \(\tau\) adaptively does not affect the slot consensus. Conversely, instantiating the slot consensus with a \(5f{+}1\) protocol reduces the fast-path latency at the cost of resilience, while leaving the slot scheduling unchanged. The framework is not specific to MCP, though our correctness proof is specific to it: we show that any conforming pair solves the MCP problem (11).

1.0.0.4 In practice.

We intend Cadence as a deployable protocol, not only a theoretical one: we show how to deploy it as part of a blockchain (6) and work through several further practical considerations (7). We also evaluate its network latency in simulation, using estimated delays between Monad mainnet’s \(200\) globally distributed validators, with five proposers per slot: at a block interval of \(100\) ms, the end-to-end latency, the sum of the inclusion and finalization latencies, averages about \(269\) ms, or \(217\) ms to speculative finality (8).

1.0.0.5 Contributions.

Our contributions are: (i) the extreme-pipelining framework, comprising the slot-consensus and orchestrator abstractions and a proof that any pair of conforming instantiations solves the MCP problem; (ii) Cadence, our instantiation of the framework, combining Chorus, an MCP slot consensus with a three-round fast path at optimal resilience, with Conductor, an orchestrator that schedules the slots at a regular cadence in normal operation and slows block production under asynchrony; and (iii) the practical considerations for deploying Cadence as a real blockchain rather than a purely theoretical protocol.

1.0.0.6 Paper organization.

The rest of this paper is organized as follows. We present the problem and our design informally: the MCP problem (2), our extreme-pipelining framework (3) and its components in Cadence: Chorus(4) and Conductor(5). We then discuss deploying Cadence as part of a blockchain (6) and further practical considerations (7), evaluate its latency (8), and review related work (9). The appendix gives the formal treatment: the formal problem definition (10), the Cadence framework and its correctness (11), Chorus(12), and Conductor(13).

2 Multiple Concurrent Proposers (MCP): Problem Definition↩︎

We begin with a description of the problem we aim to solve.

2.1 Setting↩︎

We consider a set of \(n\) validators, each of which maintains its own append-only ledger: an ordered sequence of blocks, where each block bundles transactions submitted by end users. The goal is for these ledgers to remain mutually consistent and to keep growing, so that, to the end users, they appear as a single, ever-growing ledger. We work in the standard Byzantine setting with \(n = 3f + 1\) validators, of which up to \(f > 0\) may be faulty and behave arbitrarily (Byzantine), while the rest are correct (or honest). We assume partial synchrony: the network may behave asynchronously, delaying messages arbitrarily, up to some unknown moment called the global stabilization time (\(\mathrm{GST}\)), after which it stabilizes and delivers messages within a known bound \(\Delta\). Throughout, \(\delta \leq \Delta\) denotes the actual network delay after \(\mathrm{GST}\). We further assume that validators have synchronized clocks, giving a global notion of time shared by all validators. Finally, we assume that every correct validator begins executing at global time \(0\).

Each block belongs to a slot: slots are numbered by the positive integers, validators process them in increasing order, and each slot contributes exactly one block to the ledger. A slot also has two associated attributes:

The defining feature of the MCP problem, and what sets it apart from classical single-leader blockchains, is precisely that a slot may have several proposers at once, rather than one: each proposer contributes its own proposal, and the slot’s block should reflect the contributions of all of them. The validators must keep agreeing on, and extending, a ledger of such blocks despite the Byzantine faults and network asynchrony.

2.2 Guarantees↩︎

Our MCP protocol must provide the following guarantees, closely following those introduced by Garimidi et al. [1]. Two of them — censorship resistance and eventual stability — take effect only once the network has stabilized: there is a grace period \(\mathcal{G}\) such that both hold from time \(\mathrm{GST} + \mathcal{G}\) onwards.

• Safety. The ledgers of any two honest validators are always consistent, i.e., at any point in time, one is a prefix of the other, so the ledgers never fork.

• Liveness. Every slot eventually contributes a block to every honest validator’s ledger, so no slot stalls forever and the ledgers keep growing.

• Short-term censorship resistance. An honest proposer’s proposal cannot be suppressed after the grace period: for every slot whose starting time is at least \(\mathrm{GST} + \mathcal{G}\), the proposals of all honest proposers become part of that slot’s block. Note that this notion is stronger than the usual notion of censorship resistance, which only requires that proposed transactions are eventually included in the ledger.⁷

• Hiding. A faulty proposer cannot tailor its proposal to the honest proposers’ proposals for the same slot: an honest proposer’s proposal stays concealed until it is too late for a faulty proposer to build a new proposal and still have it included in that slot’s block.

• Eventual stability. From time \(\mathrm{GST} + \mathcal{G}\) onwards, the slots come “without gaps”: successive slots follow one another promptly, with no undue gaps between their deadlines.

2 illustrates the problem together with these five guarantees.

The first two guarantees, safety and liveness, are the classical guarantees expected of any blockchain protocol: the validators’ ledgers must remain consistent, and they must keep growing. The other two, short-term censorship resistance and hiding, are specific to the economic nature of blockchains. Recall that the main goal of having several concurrent proposers is economic in the first place: the right to propose is spread across many parties precisely so that no single party controls what enters a block and profits from that control. This entails that no honest proposer can be silenced even for a single block (otherwise its contribution could simply be dropped). Furthermore, no faulty proposer can peek at others’ proposals before committing to its own (otherwise it could profit by reacting to what it sees). Censorship resistance guarantees the former, and hiding the latter. One timing aspect worth emphasizing: censorship resistance is required to hold not immediately at \(\mathrm{GST}\), but only after a grace period \(\mathcal{G}\) following it. In other words, slots whose starting time is within the grace period need not enjoy censorship resistance.

This grace period is not incidental : our formal definitions (10) parametrize the guarantees by its length, and the shorter the \(\mathcal{G}\) a protocol achieves, the sooner its guarantees kick in after network asynchrony — a direct measure of the protocol’s quality.

Hiding, in turn, rules out the adverse selection this peeking would otherwise enable: a Byzantine proposer that could see an honest proposal would react to the transactions it carries only when doing so is profitable, capturing the gains for itself and leaving their senders the losses. Since the adversary never sees an honest proposal in time, it cannot react selectively in this way. We note that our hiding property slightly relaxes that of Garimidi et al. [1] while still capturing its purpose: there, a proposal must remain concealed until the ledger up to and including its slot is irrevocably committed; we require concealment only until it is too late for a faulty proposer to react to the honest proposal.

The last guarantee, eventual stability, concerns the slot schedule and is particularly applicable when performing extreme pipelining across slots. Intuitively, after the grace period \(\mathcal{G}\), the proposals for slots should be created at a steady pace: there should be no undue gaps between slots, which gives the protocol a steady high-frequency “economic tick”. In Cadence, we make this intuition concrete by requiring that the slot deadlines eventually become \(\tau\)-spaced, for a fixed duration \(\tau\): from some point on, the deadlines of consecutive slots are separated by exactly \(\tau\).

3 Our Extreme-Pipelining Framework↩︎

We now describe our extreme-pipelining framework,⁸ which allows for producing blocks at an arbitrarily high rate, no matter how long any individual block takes to propagate or finalize.

The framework rests on splitting the problem into two largely independent concerns, each addressed by its own abstract building block. The first concern is what happens within a single slot: how the proposers of a slot get their proposals into that slot’s block, and how all validators come to agree on that block. The second concern is what happens across slots: how fast the slots follow one another (how we set their deadlines), and how many slots validators may have underway at once. We capture the first concern in a primitive we call slot consensus, and the second in a primitive we call the orchestrator. The framework itself is then little more than the glue that wires these two primitives together: it runs a single orchestrator and one instance of slot consensus per slot. This decomposition keeps the design modular and general: each primitive can be designed, analyzed, and swapped out on its own, and any valid pair of primitives composes into a correct MCP protocol. Cadence, our concrete MCP protocol, is this framework instantiated with concrete protocols for the two primitives: Chorus as the slot consensus and Conductor as the orchestrator.

3.1 Slot Consensus↩︎

At its core, slot consensus is a one-shot consensus primitive, responsible for a single slot: it has all honest validators agree on a single finalized block for the slot. It is also where the MCP-specific work occurs: slot consensus gathers the slot proposers’ proposals and enforces the two economic guarantees for that slot.

3.1.1 Interface & Guarantees.↩︎

The interface of slot consensus is simple: the slot’s proposers \(\mathsf{propose}\) their proposals as input, and each validator may eventually \(\mathsf{finalize}\) a block for the slot as output. Roughly speaking, slot consensus is required to satisfy the following four guarantees:

These four guarantees should already look familiar: they mirror, at the level of a single slot, every global MCP guarantee except eventual stability, and they are precisely what we will later rely on to argue that our framework solves the MCP problem. 3 collects the interface and the guarantees of slot consensus in one place.

3.2 Orchestrator↩︎

While slot consensus looks at one slot in isolation, the orchestrator spans all of them. Its responsibility is to schedule the slots, that is, to determine their deadlines, and thereby the block interval. A smaller block interval means transactions wait less time before a slot is available to carry them, so the orchestrator directly governs how quickly a transaction can be picked up for inclusion. The slots are all the orchestrator knows about: proposals, blocks and other consensus-specific abstractions are entirely outside its view.

3.2.1 Interface & Guarantees.↩︎

Like slot consensus before it, the orchestrator exposes a simple interface. As input, a validator notifies the orchestrator that a slot is \(\mathsf{complete}\), meaning that the validator’s work within that slot is done; in our framework, as we show in 3.3, this happens once the slot’s block is finalized. As output, the orchestrator \(\mathsf{schedules}\) new slots: it comes back to the validator with the deadlines of new slots. With the interface in place, we can state the two properties that the orchestrator must satisfy:

4 collects the interface and the guarantees of the orchestrator in one place.

The two properties of the orchestrator address two different regimes of the network. Boundedness is what protects the entire framework during an outage. While the network is asynchronous, slot consensus instances may be unable to finalize, since finalization requires timely message delivery [6]; in our framework, where a validator reports a slot complete exactly when its block is finalized, this means that the complete notifications dry up. If the orchestrator nevertheless kept opening fresh slots, the number of underway slots — scheduled, but not yet complete — would grow without bound for as long as the outage lasted, and with it the number of concurrently running slot consensus instances and the memory and computation each validator must devote to them. Boundedness rules this out: deprived of complete notifications, the orchestrator withholds the deadlines of new slots, so that no matter how long the network stays asynchronous, at most a bounded number of slot consensus instances ever run at once. Why do we care about bounding the number of concurrently running consensus instances at all?

The reason is memory: a bounded number of concurrent slots is necessary — though not sufficient — for bounded per-validator memory; one must also bound the memory each slot consensus instance uses (which in turn requires a primitive such as abortable broadcast [7]), and we return to it in 11.1.2.1. This lies beyond our scope.

Recovery, in contrast, is what the orchestrator owes once the network has stabilized, and its two halves serve two different ends. The first half, the steady \(\tau\)-spaced schedule, is precisely what establishes the MCP eventual stability property: eventual stability concerns the schedule rather than any individual slot, and the schedule is entirely the orchestrator’s doing — by no longer throttling and spacing the deadlines by exactly \(\tau\), the orchestrator has the slots advance at the steady, “gap-free” cadence that eventual stability demands. The second half, that every correct validator learns each deadline at least \(\Delta\) in advance, plays a quieter but equally important role: it ensures that a proposer knows the deadline already by the slot’s starting time, leaving it enough time to submit its proposal — exactly what the proposal inclusion of slot consensus presupposes.

3.3 Putting the Pieces Together↩︎

Our framework composes these two primitives in the natural way; 5 illustrates the interaction. Each validator runs its local instance of the orchestrator, which drives the protocol forward by setting each slot’s deadline. At each slot’s starting time (\(\Delta\) time before its deadline), or as soon as it learns the slot’s deadline, if later, the validator begins participating in that slot’s consensus instance and, if it is one of the slot’s proposers, submits its proposal to that instance. Whenever a slot consensus instance finalizes a block, the validator records the block, notifies the orchestrator that the slot is complete (which may in turn let the orchestrator schedule further slots), and eventually appends the block to its ledger. Since slots may be finalized out of order, blocks are buffered and appended in slot-number order, so that each validator’s ledger grows as a clean, contiguous sequence with no slot missing.

3.3.1 Extreme Pipelining.↩︎

With the entire framework in place, we can now explain how it achieves the extreme pipelining it is named after: a fixed block interval of \(\tau\), regardless of how long consensus on any individual slot takes. The key lies in both building blocks: the slots and their blocks are independent by construction (one slot consensus instance per slot), and the orchestrator is free to schedule them independently, constrained only by boundedness (it may keep opening new slots as long as the number of underway slots stays within the bound). To appreciate this freedom, let us explain why it was out of reach for earlier designs. In traditional BFT protocols, consecutive slots are chained to one another: a slot must wait for its predecessor to make enough progress before it can begin. In unpipelined protocols, such as PBFT [8], basic HotStuff [9], and SBFT [10], this chaining is the strictest possible: the next slot begins only after the current slot’s block is fully finalized. Pipelined protocols, such as pipelined HotStuff [9], FastHotStuff [11], and MonadBFT [12], loosen this coupling, but do not remove it: the next slot begins earlier, once the current one produces a quorum certificate, yet it still requires that certificate as input. In both cases, each slot passes a baton to the next, and the protocol can only advance as fast as the baton travels. Our framework drops this dependency altogether: under favorable network conditions, a new slot opens every \(\tau\) time, dictated solely by the global clock, and nothing from any earlier slot — no artifact, no certificate, no event — is needed for it to start. Indeed, nothing in the orchestrator’s interface ties a slot to its predecessor’s progress: complete notifications may throttle the pace (boundedness), but they are never required as input for a new slot to open. The slots no longer wait for one another; they simply follow the schedule. The block interval thus becomes decoupled from the per-slot consensus latency: slots can be scheduled arbitrarily close together, and hence blocks can be produced at an arbitrarily high rate, no matter how long any individual slot takes to certify or finalize.

3.3.2 Proof Sketch.↩︎

Let us now explain why our framework solves the MCP problem as defined in 2, walking through its guarantees one by one. Safety follows from the agreement property of slot consensus, applied slot by slot. Agreement ensures that, for every slot, honest validators never finalize conflicting blocks; and since every validator appends the finalized blocks to its ledger in slot-number order, any two honest ledgers contain the same blocks in the same order, one being a prefix of the other. In short, if no single slot can produce disagreement, the ledgers have no way to diverge. Liveness follows from an alternation between the two primitives. Consider the slots currently underway. By the termination of slot consensus, every honest validator eventually finalizes a block for each of them and, having done so, reports these slots as complete to the orchestrator. Once these completions arrive, the orchestrator’s boundedness no longer stands in the way: the orchestrator schedules new slots, whose consensus instances again eventually terminate, and so on forever. Hence, every slot is eventually scheduled and eventually contributes a block to every honest validator’s ledger: no slot stalls forever, and the ledgers keep growing.

Hiding requires no work at all: the hiding of each individual slot consensus instance is precisely the global hiding property, read across all slots. Censorship resistance, in contrast, needs the two primitives to cooperate. After the grace period \(\mathcal{G}\) following \(\mathrm{GST}\), the recovery property of the orchestrator guarantees that every honest validator learns each upcoming deadline at least \(\Delta\) in advance, that is, by the slot’s starting time. Every honest proposer therefore has enough time to submit its proposal by the starting time, and from there the proposal inclusion property of slot consensus takes over: the on-time proposal makes it into the slot’s finalized block, and hence into the ledger.

Eventual stability is exactly the first half of the recovery property: once the network stabilizes (from time \(\mathrm{GST} + \mathcal{G}\) onward), the orchestrator spaces consecutive deadlines by exactly \(\tau\), so the slots advance at the steady cadence that eventual stability demands. Finally, one practical concern remains; it is not an MCP guarantee, but, as discussed, a prerequisite for feasibility: the number of slot consensus instances a validator must attend to at any point in time. This is where boundedness of the orchestrator comes in: at any moment, each honest validator has only a bounded number of slots underway, hence only a bounded number of slot consensus instances to run, keeping its memory and computation in check no matter how the network behaves.

4 Chorus: Our Slot Consensus↩︎

We now present Chorus, the slot consensus protocol we use in Cadence. We describe Chorus through two modes of operation. The first, the fast path, handles the good case: it is essentially a classical single-leader consensus generalized to accommodate several proposers at once, finalizing a block quickly whenever the network is synchronous and the proposers behave. The second, the fallback path, takes over when the fast path fails to finalize, ensuring that the slot reaches agreement nonetheless. Note that the split into a fast and a fallback path is only expository: the two are interwoven into a single protocol (and not two modes that the protocol toggles between).

4.1 Preliminaries↩︎

Before presenting the protocol itself, we settle two preliminaries: the cryptographic primitives Chorus builds on, and what its validators actually agree upon (which, as we will see, is not blocks of transactions).

4.1.1 Cryptography.↩︎

Chorus relies on a handful of standard cryptographic primitives, which we use as follows.

4.1.2 The Object of Agreement.↩︎

We now turn to the following question: what Chorus’s validators actually agree on. The answer is not a block, but short digests of the proposals. Much as a single-leader protocol can agree on a hash of the leader’s block rather than on the block itself, Chorus has its validators agree on a digest of each proposal rather than on the proposal itself. Concretely, each proposal goes through three steps before agreement (6): it is first encrypted; then erasure-coded into \(n\) chunks; and finally committed to by a single Merkle root, the digest the validators agree on. Recall from 1 (Idea 4) that committing to these digests rather than to the full proposals is exactly what lets dissemination run in parallel with consensus, following AVID [13], DispersedSimplex [5], and Deterministic RaptorCast [14]. Each proposal is disseminated as erasure-coded chunks committed by a Merkle root, and the deterministic encoding gives consistency, meaning all correct validators reach the same verdict on a root, either all recovering the same proposal or all rejecting it as invalidly encoded. Consistency is a property of the encoding alone. Availability, that the proposal behind a root can be recovered, is achieved once Chorus certifies the root, since the certificate guarantees that enough honest validators hold their chunks for the data to be reconstructible. Any erasure-coded dissemination scheme providing consistency composes with Chorus in this way. Chorus builds its object of agreement on Deterministic RaptorCast [14], whose deterministic encoding makes a root’s verdict unique (consistency), while Chorus’s certificates over these roots establish that the committed data is recoverable (availability). Both are established for Chorus in 12. With several proposers in a slot, this object of agreement grows into a vector of such roots: one entry per proposer, each committing to that proposer’s proposal, or to a designated empty value when the proposer contributes nothing.

Crucially, an entry is never agreed upon on its own: it always comes with a certificate.

We call this vector of certified entries a meta-block (7): one entry per proposer, each a Merkle root or the empty value \(\bot\). A meta-block includes a proposer’s proposal when its entry is positive — the root commits to the proposal — and excludes it when the entry is negative. From here on, then, Chorus’s goal is simply to agree on a meta-block’s entries — the Merkle roots and \(\bot\) values themselves, not the certificates that justify them. The fast path and the fallback path are two mechanisms for doing exactly that, and we describe both purely as procedures for agreeing on the aforementioned entries. How the finalized entries are turned into the slot’s block is described in 4.4.

4.2 Fast Path↩︎

The fast path of Chorus follows the familiar structure of single-leader consensus, in which a leader disseminates its proposal and the validators then run two voting rounds before finalizing. Chorus keeps this template and departs from it in only one respect: a slot has several proposers, so all of them act as leaders at once, each disseminating a proposal of its own.

4.2.1 Description.↩︎

Before dissemination, each proposer encrypts its proposal using the threshold encryption scheme, producing a ciphertext that can be decrypted only once \(f+1\) validators release their decryption shares for the slot. The proposer then disseminates this encrypted proposal using the chunked encoding of 6, sending each validator that validator’s chunk together with a Merkle proof against the root and the proposer’s signature over the slot number, its own identity, and the root. The root commits to the encrypted proposal rather than the plaintext one. An honest proposer disseminates by the slot’s starting time \(D_s- \Delta\), so that under synchrony its chunks reach every validator before the deadline.

The first voting round opens at the slot’s deadline, and in it each validator casts one vote per proposer \(p_j\): if it has received a valid chunk from \(p_j\), carrying \(p_j\)’s Merkle root \(r_j\), it broadcasts a positive vote \[\langle \mathrm{\small yes}, s, p_j, r_j, \sigma \rangle,\] where \(\sigma\) is its signature on \(\langle \mathrm{\small yes}, s, p_j, r_j \rangle\), so that \(2f+1\) such votes can later be combined into a single certificate on \(r_j\). Importantly, a validator also attaches to each positive vote the chunk it received; it does so to support the fallback path, as we explain in 4.3. If, instead, no valid chunk from \(p_j\) arrived by the deadline,⁹ the validator broadcasts a signed negative vote \[\langle \mathrm{\small no}, s, p_j, \sigma \rangle,\] where \(\sigma\) is now its signature on \(\langle \mathrm{\small no}, s, p_j \rangle\). Crucially, as already noted in 4.1, these shares are tied to the slot itself rather than to any individual proposal, so \(f+1\) of them suffice to decrypt every proposal of the slot.

Once a validator has gathered, for every proposer, a quorum of \(2f+1\) matching votes, that is, \(2f+1\) yes votes on the same root or \(2f+1\) no votes, it assembles a fast meta-block: for each proposer it records either the root \(r_j\) with its certificate of \(2f+1\) yes votes, or, when the quorum is negative, a negative entry with a certificate of \(2f+1\) no votes. (When such a quorum fails to form for some proposer, the fallback path takes over, as we describe in 4.3.) These certificates are exactly the certificates that the entries carry. A \(2f+1\) yes certificate is a proof of availability: at least \(f+1\) of its signers are honest, and each signed only after receiving and verifying its chunk, so at least \(f+1\) honest validators hold their chunks, enough to recover the data behind \(r_j\) and, as discussed above, to either reconstruct the proposal in full or unanimously deem it invalid (see 4.4). A \(2f+1\) no certificate, in turn, justifies excluding the proposer, since at least \(f+1\) honest validators saw no valid chunk by the deadline. Each validator that has assembled a fast meta-block casts a single fast vote on it as a whole, broadcasting the meta-block along with the vote. As soon as it collects \(2f+1\) fast votes on the same fast meta-block, it finalizes its entries. 8 traces this communication pattern for a slot with two proposers.

4.2.2 How Fast is the Fast Path?↩︎

As we emphasized in 1, latency is a first-order concern, so we want the fast path to finalize as quickly as possible. Under favorable conditions it does: provided the slot occurs after \(\mathrm{GST}\), the fast path finalizes in just two voting rounds, by time \[D + 2\delta,\] where \(D\) is the slot’s deadline and \(\delta \leq \Delta\) is the actual message delay. This is optimal: no protocol can finalize in fewer rounds [15]. In addition, Chorus offers a faster but weaker notion of finalization, which applications and users can choose instead of the regular one when they prefer lower latency over the strongest guarantee. A validator need not wait for both voting rounds: following prior work [12], it may speculatively finalize the entries after a single round of voting, as soon as it constructs the fast meta-block. A speculative finalization may ultimately be reverted, but, as we show once the fallback path is in place, only if some validator equivocated, disseminating conflicting votes for the same proposer; such deliberate misbehavior is exceedingly rare in practice and can always be detected and punished.

The fast path succeeds whenever the network is synchronous and every proposer is either correct (sending the same Merkle root to all correct validators) or fully silent (sending nothing to any): all correct validators then vote the same way on each proposer (all yes, or all no), a quorum forms, and the slot commits on the fast path. Only partial dissemination or equivocation splits a proposer’s votes and forces the fallback. By casting explicit no votes rather than staying silent, validators keep the slot on the fast path even when a proposer is fully offline.

4.3 Fallback Path↩︎

We now turn to the fallback path, which validators follow when the fast path fails.

4.3.1 Description.↩︎

At the end of the first voting round, once the yes and no votes have been disseminated, a correct validator that can assemble a fast meta-block (as in 4.2) simply issues its fast vote carrying it; as we saw, this happens whenever the network is synchronous and every proposer is correct or silent. A validator that cannot assemble a fast meta-block instead takes the fallback path, in three steps.

4.3.1.1 First, it announces that it is abandoning the fast path.

It broadcasts a signed no-fast-vote message, but only after a timeout has elapsed and it has heard first-round votes from at least \(2f+1\) validators: by then it has given the fast path enough time and still cannot assemble a fast meta-block, so it times out on it. It is a signed statement that the validator will not cast a fast vote. By quorum intersection, a \(2f+1\) no-fast-vote quorum and the \(2f+1\) fast votes a fast-path commit needs cannot both form; so once \(2f+1\) no-fast-votes exist, the fast path can no longer commit, and it is safe to enter the fallback path instead.

4.3.1.2 Second, it votes on each proposer separately.

For a proposer \(p_j\), it checks whether it has collected at least \(f+1\) yes votes on the same Merkle root:

4.3.1.3 Third, it finalizes through a black-box agreement run at the end.

In this second post-deadline round, the validator waits for \(2f+1\) messages. Each is either a fast vote, which carries a fast meta-block, or a bundle of fallback votes, namely the per-proposer fallback-yes/fallback-no votes together with the sender’s single no-fast-vote. Whichever way the round goes, the validator ends it by submitting a single meta-block as its proposal to the slot’s fallback agreement (see 9). Here Chorus relies on an off-the-shelf agreement primitive: for each slot, Chorus runs a single instance of such a consensus protocol and treats it purely as a black box. Any protocol will do, as long as it guarantees agreement (no two correct validators decide differently), termination (every correct validator eventually decides), and external validity (its decision always satisfies a fixed, predetermined predicate). Which meta-block the validator submits depends on the messages it gathered this round:

The proposed meta-block is either fast or fallback. The external validity predicate we use in the fallback agreement is therefore that the agreement may decide only a well-formed fast or fallback meta-block for that slot. The slot is then finalized by whatever meta-block the fallback agreement decides. 9 traces the whole fallback path end to end.

4.4 From Meta-Blocks to Proposals (and Hence Blocks)↩︎

We have now seen both paths, but neither actually outputs a block of transactions: each finalizes only the entries of a meta-block, and an entry is just a digest (a Merkle root) of a proposal, not the proposal itself. Producing the slot’s block from these entries therefore takes two steps. First, every correct validator must recover the proposals that the positive entries point to. Second, it merges these recovered proposals into the slot’s block by a deterministic transformation: discarding invalid proposals, deduplicating transactions, and ordering the rest. This second step is a purely local computation that yields the same block at every correct validator, so the real work lies in the recovery, on which we now focus.

The recovery must ensure that, from a meta-block \(B\) whose entries are finalized, every correct validator eventually obtains the same proposal vector, one entry per proposer, each either that proposer’s recovered proposal or \(\bot\) (10), subject to the following two guarantees:

Both follow from how a single positive entry of \(B\), committing to a root \(r\), is recovered.

4.4.1 Recovery Procedure.↩︎

If \(B\) is a fast meta-block, then such an entry carries a \(2f+1\) yes certificate (see 4.2), and a validator casts a yes vote only while holding the chunk it received for \(r\); hence, at least \(f+1\) correct validators hold their chunk for \(r\). These honest validators re-disseminate their chunks, so every correct validator eventually collects \(f+1\) chunks committed under \(r\). Collecting them does not by itself guarantee a recoverable proposal, since a faulty proposer may have committed chunks that do not form a valid erasure encoding; this shows up in one of two ways. If the validator cannot decode the chunks at all, the encoding is certainly invalid and it discards the proposal. Otherwise it decodes a candidate ciphertext \(\mathcal{D}\) (the root commits to the ciphertext, not the plaintext), but a successful decode still does not guarantee a consistent encoding: the validator re-encodes \(\mathcal{D}\) and checks that this reproduces exactly \(r\). If it does, the encoding is valid and the validator decrypts \(\mathcal{D}\) with the slot’s \(f+1\) decryption shares (released at the slot’s deadline) to obtain the plaintext proposal.¹¹ If the re-encoding yields any other root, the encoding is invalid and the validator discards the proposal.

If instead \(B\) is a fallback meta-block, such an entry carries an \(f+1\) fallback-yes certificate (see 4.3). At least one of its signers is honest, and an honest validator casts fallback-yes only after reconstructing the proposal and checking that it re-encodes to \(r\); as part of casting that vote (4.3) it sends each validator its assigned chunk, and the validators re-broadcast their chunks, so every correct validator obtains the \(f+1\) chunks needed to reconstruct the encrypted proposal \(\mathcal{D}\) behind \(r\). Recovery then proceeds exactly as in the fast case: re-encode \(\mathcal{D}\) to check it against \(r\) and, if it matches, decrypt it into the plaintext proposal, otherwise discarding it as invalid.

In both cases, once the root is certified, the certificate guarantees that \(f+1\) honest validators hold their chunks, so every correct validator can collect \(f+1\) chunks and reconstruct the data. This is the availability of 4.1.2, achieved through Chorus’s certificate over the disseminated root. Whether \(B\) is fast or fallback, recovery provides both guarantees:

4.4.2 Proposal Recovery Adds No Latency.↩︎

Proposal recovery runs in parallel with voting, so it adds no latency. The latency claims of 4.2 (speculative finalization after one round, full finalization after two) are about the fast path and were stated for the meta-block; they carry over to the full block of transactions. On the fast path, every first-round positive vote already carries the sender’s chunk, and every validator bundles its slot decryption share into the same first-round message, so a validator that assembles a fast meta-block at the end of the first round holds, behind each positive entry, \(2f+1\) chunks (more than the \(f+1\) needed to reconstruct the ciphertext) and \(2f+1\) decryption shares (more than the \(f+1\) needed to decrypt it), and recovers the proposal with no further communication. The fallback path adds no extra latency from recovery either. A positive entry certified by \(2f+1\) yes votes is recovered exactly as on the fast path. For one certified by \(f+1\) fallback-yes votes, a fallback-yes voter sent each validator its assigned chunk when voting (4.3), so every correct validator holds its chunk for \(r\); once the fallback meta-block forms, each broadcasts that chunk, and one \(\Delta\) later every correct validator can decode the proposal, before the fallback path finalizes. Hiding adds no latency either: the slot’s \(f+1\) decryption shares are released at the deadline, bundled with the first-round votes, and open every ciphertext for the slot, so a validator decrypts a proposal as soon as it has decoded it.

4.5 Proof Sketch↩︎

Finally, we sketch why Chorus satisfies the four properties of slot consensus (see 3).

4.5.0.1 Agreement.

We must show that no two correct validators finalize different blocks. By recovery’s consistency guarantee (i), agreeing on the same entries yields the same block, so it suffices to show that no two correct validators finalize different entries. On the fast path this is immediate: each entry carries a certificate of \(2f+1\) signatures, so, by quorum intersection, no proposer can have two conflicting certified entries. On the fallback path it follows from the fallback agreement, whose agreement property makes all correct validators decide the same meta-block, and hence the same entries. It remains to rule out a split in which one validator finalizes on the fast path and another finalizes different entries on the fallback path. But if any validator finalizes on the fast path, it holds a quorum of \(2f+1\) fast votes, and, by quorum intersection, no \(2f+1\) no-fast-vote certificate can then exist; hence no fallback meta-block can be formed, and the fast-path entries are the only ones anyone can finalize.

4.5.0.2 Termination.

Every correct validator eventually finalizes, and it suffices to show that every correct validator proposes a meta-block to the fallback agreement. We distinguish two cases. If some correct validator assembles a fast meta-block at the end of the first round (and broadcasts its fast vote), then every correct validator eventually receives it, adopts the (unique) fast meta-block, and proposes it. Otherwise, every correct validator eventually collects \(2f+1\) fallback bundles, builds a fallback meta-block, and proposes that. In either case all correct validators propose to the consensus, so, by its termination, it decides a meta-block, by which the slot is finalized.

4.5.0.3 Proposal Inclusion.

Consider an honest proposer that submits its proposal on time (\(\Delta\) time before the slot’s deadline), while the network is synchronous, and let the proposal commit to root \(r\). Every correct validator then receives a valid chunk by the deadline and votes yes on root \(r\), so no correct validator votes no for this proposer. A fast meta-block can therefore only record \(r\) for this proposer, never excluding the proposal. The fallback path includes it just as well: every correct validator holds \(f+1\) yes votes on \(r\), reconstructs the proposal, and re-encodes it successfully (an honest proposal is correctly encoded), so it sends a fallback-yes on \(r\) and never a fallback-no. So no \(f+1\) fallback-no votes can ever form against it either. In both cases, then, the finalized entry for this proposer certifies the proposal under root \(r\) rather than excluding it; by recovery’s guarantee (ii), every correct validator therefore recovers the proposal into the slot’s block, which ensures proposal inclusion.

4.5.0.4 Hiding.

Proposals are revealed only at the deadline, by which point it is too late for the adversary to craft a competing proposal and still have it included, so it cannot make its own proposal depend on the honest proposers’ proposals for the slot.

4.5.0.5 Safety of speculative finalization.

We claimed in 4.2 that a speculatively finalized block can be reverted only if some validator equivocated; here is why. Suppose a correct validator speculatively finalizes the fast meta-block \(B\), but the fallback consensus ultimately decides a different meta-block \(B'\), so that the two assign some proposer \(p_j\) a different proposal in the slot’s block. Since \(B\) is a fast meta-block, it backs \(p_j\)’s entry with a first-round quorum: \(2f+1\) yes votes on one root \(r\), or \(2f+1\) no votes. There are two ways \(B'\) can disagree:

5 Conductor: Our Orchestrator↩︎

This section introduces Conductor, the orchestrator Cadence employs. It fixes each window’s deadlines in advance, so block production needs no per-slot coordination; its one real decision is when to open the next window, which it makes by having the validators agree, once per window and off the critical path, on the next window’s first deadline, from which its remaining deadlines follow \(\tau\) apart, where \(\tau\) is the block interval.

5.1 Protocol Description↩︎

In order to bound the number of open slots, Conductor groups slots into windows of \(W\) consecutive slots: window \(1\) is slots \(1, \ldots, W\), window \(2\) is slots \(W + 1, \ldots, 2W\), and so on. It schedules these windows one at a time, and the schedule of each depends on the progress of the earlier ones: window \(1\) is scheduled at genesis (global time \(0\)), and window \(\omega + 1\) is scheduled only once correct validators report that every slot of windows \(1, \ldots, \omega - 1\) and the first \(p\) slots of window \(\omega\) are complete. This is what keeps the number of open slots bounded as window \(\omega+1\) is withheld until the first \(p\) slots of window \(\omega\) are complete. Recall the two parameters of Conductor: the window size \(W\) and the threshold \(p \in \{0, \dots, W-1\}\).

We now describe the protocol from the perspective of a single correct validator \(p_i\); recall that the validators’ clocks are synchronized, so they all share a single global timeline. At genesis, \(p_i\) schedules window \(1\) by issuing its slots’ \(\tau\)-spaced deadlines: slot \(1\) at \(\Delta\) (so its starting time is \(\Delta - \Delta = 0\)), slot \(2\) at \(\Delta + \tau\), and so on up to slot \(W\) at \(\Delta + (W-1)\tau\). From then on, the only input that drives Conductor is the completion of slots. (In Cadence, as discussed in 3.3, \(p_i\) marks a slot complete once it has finalized that slot’s block.)

5.1.0.1 Scheduling the next window.

This is the crucial and most technical part of Conductor. We explain it for the transition from window \(1\) to window \(2\); every later transition, from a window \(\omega\) to \(\omega + 1\), works the same way (up to one minor change that we flag below).

As soon as \(p_i\) has completed all of the first \(p\) slots, it reads the current time \(\mathcal{T}\) and computes a proposed deadline for the first slot of window \(2\); the remaining slots of window \(2\) are then simply \(\tau\)-spaced after it, so this single deadline fixes the whole window. This is only \(p_i\)’s own proposal. Since correct validators complete the first \(p\) slots at different times, they compute different proposed deadlines and then reconcile them into a single agreed deadline through a sub-protocol described below; we first explain how \(p_i\) forms its proposal. Validator \(p_i\) forms its proposed deadline as follows (see 11):

These two cases capture exactly what Conductor wants to achieve: it preserves the steady \(\tau\)-cadence whenever the system is “healthy” (Conductor’s recovery property, which yields the eventual stability of Cadence), and stretches the schedule when it is not (Conductor’s boundedness property, which caps the slots in flight for each validator in Cadence).

Note that different correct validators may complete the first \(p\) slots at slightly different times, and so arrive at different proposed deadlines for window \(2\); they must nonetheless agree on a single one. To this end, the validators feed their proposed deadlines into this off-the-shelf ACS primitive, which outputs a common vector of \(2f+1\) proposed deadlines — at least \(f+1\) of them from honest validators — and guarantees agreement (all correct validators obtain the same vector) and termination (every correct validator eventually obtains one). Each validator then takes the median of the vector’s entries as the agreed deadline of slot \(W+1\), and opens window \(2\) accordingly. Taking the median is what tames Byzantine influence: among \(2f+1\) values of which at most \(f\) are Byzantine, the median is guaranteed to lie between the smallest and the largest honest proposed deadline, so faulty validators can never drag the deadline outside the range the honest ones proposed (12).

Every later window is handled the same way, with the one change flagged above: \(p_i\) must also wait for all earlier windows to be complete (a requirement that is vacuous for the transition from window \(1\) to window \(2\)). Concretely, once window \(\omega\)’s prerequisites are met — the slots of all earlier windows and the first \(p\) slots of window \(\omega\) are complete — validator \(p_i\) runs the same two-case computation (now against window \(\omega\)’s last deadline) and agrees on it through ACS and the median. This finally yields the bound promised above: when window \(\omega+1\) opens, only the unfinished part of window \(\omega\) and the fresh window \(\omega+1\) can be in flight, so at most \((W - p) + W = 2W - p\) slots are underway at any time.

5.2 Proof Sketch↩︎

We now argue that Conductor achieves the two properties specified in 3.2.

5.2.0.1 Boundedness.

We already did the counting at the end of the previous subsection: a correct validator opens window \(\omega+1\) only once every slot of windows \(1, \ldots, \omega-1\) and the first \(p\) slots of window \(\omega\) are complete, so at most \(2W - p\) slots are ever underway at once.

5.2.0.2 Recovery.

Recovery asks that, within a bounded grace period after the network stabilizes, the schedule “heals”: deadlines become \(\tau\)-spaced again, with no gaps, and every correct validator learns each deadline at least \(\Delta\) in advance. We sketch why this happens within bounded time after \(\mathrm{GST}\).

Everything hinges on one question: once the network is running smoothly (after \(\mathrm{GST}\)), does such a “good” window leave enough time to schedule its successor before its own cadence ends? A window lasts \(W\tau\), and within it two things must happen (13). To begin, the first \(p\) slots must complete. Chorus finalizes a slot within some latency \(\ell_{\mathrm{\small Chorus}}\) after \(\mathrm{GST}\), so every correct validator finalizes all of the first \(p\) slots by time \(\mathcal{T}_p + \ell_{\mathrm{\small Chorus}}\) — the \(p\)-th slot’s deadline \(\mathcal{T}_p\) plus that latency — and by then all of them have proposed to the window’s ACS instance. Second, since every correct validator has proposed, the ACS decides within a further \(\ell_{\mathrm{\small acs}}\) time, fixing the next window’s first deadline. We pick the parameters so that this whole pipeline fits inside the window, i.e., \(\mathcal{T}_p + \ell_{\mathrm{\small Chorus}} + \ell_{\mathrm{\small acs}} \le W\tau\). Thus, in a good window, every correct validator opens the first \(p\) slots (outputs their deadlines) by \(\mathcal{T}_p\) and they all settle the next window’s deadline by \(\mathcal{T}_p + \ell_{\mathrm{\small Chorus}} + \ell_{\mathrm{\small acs}} \le W\tau\) — with no gap and well ahead of time. This is exactly what we needed: from the first good window onward, the schedule stays “smooth” forever.

6 Deploying Cadence as Part of a Blockchain↩︎

Cadence is a consensus protocol, but in the context of a blockchain it provides a different interface than blockchains usually expect from their consensus layer, departing in three ways at once: consensus commits only a digest of each proposer’s encrypted proposal, not the transactions it contains, and without executing them; these digests carry no reference to a parent; and each proposer builds its proposal without seeing the current executed state or the other proposals its own will be merged with. This gives up machinery a blockchain normally relies on: linking blocks into a chain, committing to executed state, and validating transactions before they are included. We show how to recover each, so that the result behaves like an ordinary blockchain: 6.1 builds valid proposals under this uncertainty, 6.2 turns the committed entries into an execution block, and 6.3 certifies the resulting history and state. All of this is what it takes to behave like an ordinary blockchain; the further consequences and refinements of running with multiple proposers, which a deployment may want but does not need for that, we collect in 7.

Users submit each transaction to one or more of a slot’s proposers rather than to a single leader. We treat which proposers a user submits to, and the fee mechanism that would price this choice, as outside our scope.

We now follow one slot. A proposer selects transactions and assembles a proposal, validating each against a settled view of the executed state. It encrypts and erasure-codes the proposal and disseminates the chunks. The slot then commits the entries of a meta-block, one per proposer: the digest of its proposal if included, or empty if not. In parallel with consensus, the proposals behind the committed digests are recovered from their chunks and decrypted, and a deterministic step we call translation turns the committed meta-block into the slot’s execution block, the ordered list of transactions to execute. Execution runs asynchronously, trailing consensus by up to \(\xi\) slots, the execution lag, and the resulting state, together with the committed prefix, is certified for external verifiers.

6.1 Proposal Construction and Validity↩︎

A proposer builds its proposal under two kinds of uncertainty. First, execution is asynchronous [4], [16]: it trails consensus, so the proposer does not know the state its transactions will execute against. Second, it cannot see the proposals of the other proposers in its slot (the peer blind spot, from running multiple proposers) and those of recent slots due to extreme pipelining (the temporal blind spot).

A traditional blockchain validates each transaction before including it (i.e., synchronous execution), against the exact state the block builds upon. Cadence has no such state to give a proposer, so an implementation may instead fix a common reference for validity, such as the executed state after slot \(s-\xi\), a settled state that all validators share. A transaction is admitted only if it is valid against this reference; one already invalid against it, for instance with a reused nonce, is rejected. Because the reference is shared, the decision is the same for everyone: an honest proposer applies it when building, and translation applies it deterministically (6.2), so a transaction invalid against this reference is kept out of the execution block, even one a faulty proposer includes. A proposer also validates against its own recent proposals. Others cannot see them yet, in the temporal blind spot, but it can, so it builds on its own not-yet-settled transactions. By the time the slot is translated (6.2), these are revealed, and translation re-applies the same check.

Since the state reference is stale by \(\xi\) slots, a transaction admitted against it could be unpayable by the time it executes. To address this, a reserve-balance scheme [17] adapted to the multi-proposer setting can be used.

To prove that it validated its proposal against the right reference, a proposer attaches an execution certificate for slot \(s-\xi\) to its proposal, its ticket. This certificate pins the executed state it validated against (6.3). A proposer can form it only once \(2f+1\) validators certify that they have executed slot \(s-\xi\), so it cannot make a valid proposal while execution lags more than \(\xi\) slots behind: there is then no ticket to attach. This keeps proposals within \(\xi\) slots of certified execution, preventing fresh proposals from running too far ahead of it. This bounds proposal validity, not how many slot instances may be open at once; keeping that number bounded is instead Conductor’s role. A proposer that falls behind cannot form a ticket and contributes nothing, though its slot is still opened even when it ends up empty. Because proposals are encrypted and votes are cast on the encrypted proposals, the ticket cannot be checked at voting time: validators may vote on and finalize a proposal whose ticket is missing or invalid, even forcing the slot onto the fallback path. Translation then filters such a proposal out when assembling the execution block(6.2), so its transactions never execute, and it is itself evidence of misbehavior.

6.2 Translation: From Meta-Block to Execution Block↩︎

The consensus commitment fixes which proposals belong to slot \(s\), but not yet a block of transactions to run. Translation produces the execution block, and it must be deterministic: from the same committed data, every validator must compute the same execution block. Translation runs serially across slots: to translate slot \(s\), that slot must be committed, the proposals behind its committed digests must have been recovered and decrypted, and slots \(1\) through \(s-1\) must already be translated. Although the slots’ consensus instances run in parallel, translation therefore builds each execution block on a fixed prefix. Over that prefix, and against the certified executed state at slot \(s-\xi\), it merges the slot’s proposals into the execution block. Consensus thus agrees on the entries alone, and the execution block is what they deterministically yield.

The merge runs in stages. Translation first removes every invalid inclusion, leaving only valid transactions. It then deduplicates them, keeping a single copy of each. Validity already keeps a proposer from re-including a transaction it carried itself or one settled before the blind spot, so any surviving duplication is across proposers: building blind, several may each carry the same transaction, within a slot (the peer blind spot) or across recent slots (the temporal one). It finally orders what remains, for example by priority fee. Execution then runs each execution block asynchronously, once it is available.

However widely a transaction is duplicated, only one copy executes; the rest cost only bandwidth and block space. A deployment can shrink that residual: keeping the proposer set semi-stable, rotated slowly rather than replaced each slot, lets a proposer skip its own recent inclusions, and a transaction-fee mechanism can charge more for each additional inclusion while letting a user choose which proposers may carry a transaction, so a user pays for more inclusions only when it wants them for censorship resistance.

6.3 Certifying State and History↩︎

Validators that follow every slot already hold the committed history and, in time, the executed state. Other parties do not: light clients, bridges, and validators catching up after asynchrony or newly joining need to verify both from a small proof, rather than by replaying the chain. In a traditional blockchain every block carries a pointer to its parent, so the certificate finalizing slot \(s\) implicitly certifies the entire chain back to genesis, and each block commits to its executed state. Under extreme pipelining, neither holds. Because slots run concurrently, the proposer of slot \(s\), when it proposes, cannot in general know the outcome of slot \(s-1\): that slot may not yet have terminated, and even its proposals may not yet have been received. A slot therefore cannot point to its predecessor, and the certificate finalizing it certifies only that slot, carrying no executed state. We recover both with a mechanism that runs off the critical path, so the core protocol never waits on it.

A prefix certificate aggregates \(2f+1\) validator signatures¹² attesting a predicate over a prefix of committed slots; since at least \(f+1\) of the signers are correct, the predicate holds. We instantiate it twice. A chain certificate attests that slots \(1, \dots, s\) are all committed; an execution certificate attests that slots \(1, \dots, s-\xi\) have all been committed and executed, with its \(2f+1\) signers agreeing on the resulting state root at slot \(s-\xi\). The execution certificate is a certificate on the Ethereum-style header that execution outputs, which carries the executed-state root and, through its parent hash, the committed prefix up to that slot; either certificate can also certify the recursive hash that links the committed blocks back to genesis, giving recursive verification of the whole prefix. A proposer attaches the slot-\((s-\xi)\) execution certificate to its proposal as its ticket (6.1). Either certificate may also be used for other purposes, such as external verification by light clients or bridges. Together, the two recover what a traditional block certificate covers at once: the committed history and the executed state.

To form these prefix certificates, a validator signs the corresponding attestation once it has observed the relevant slots committed (and, for an execution certificate, executed); \(2f+1\) such signatures make up the certificate. The proof trails finalization slightly and is fetched separately rather than carried in the slot’s commit.

7 Practical Considerations↩︎

This section collects consequences and refinements of Cadence’s design that matter for deployment but are not required to follow the core protocol. We discuss how a proposer that breaks the fast path can be held accountable (§7.1), questions of latency, scheduling, and economic ticks (§7.2), and transaction privacy (§7.3).

7.1 Accountability↩︎

As we specified in §4.2, Chorus enjoys a fast path that finalizes a slot after only two voting rounds. That same section also tells us when this fast path is available: it triggers precisely when every proposer is either correct, disseminating its proposal to all correct validators, or fully silent, disseminating it to none. The difficulty lies in the intermediate case. A proposer that partially disseminates, delivering its proposal to some correct validators but not all, splits the validators’ views, and such a split can derail the fast path, forcing Chorus onto the slower fallback path (§4.3).¹³

If we must pay this latency, we would at least like to know which proposer caused it. We therefore equip Chorus with an accountability mechanism: whenever a proposer forces the fallback path, we single it out and hold it responsible for its partial dissemination, leaving correct validators a transferable proof of which proposer broke the fast path. This guarantee comes neither for free nor always: it holds only when the number of Byzantine validators is at most \(f/2\).¹⁴ Under this assumption (and after GST, since detecting a missed fast path is ultimately a matter of liveness), every fallback leaves correct validators holding enough signed evidence to reliably name every proposer that partially disseminated. Let us see why.

7.1.0.1 First-round votes & fast meta-blocks.

Recall the votes of the first round. At the deadline, each validator casts, for every proposer \(p\), a signed positive vote if it received \(p\)’s proposal in time, and a signed negative vote otherwise. A fast meta-block can be assembled only when, for every proposer, these votes converge: \(p\) must gather either a quorum of \(2f+1\) positive votes, or a quorum of \(2f+1\) negative votes. When neither quorum forms for some proposer, the fast path cannot proceed, and the slot falls back to the slower path.

7.1.0.2 From a split vote to a blamed proposer.

Now suppose at most \(f/2\) validators are Byzantine, and consider a correct validator that fails to build the fast meta-block. After GST, under synchrony, this validator hears from every validator except the (at most \(f/2\)) faulty ones, that is, from \(n - f/2 = 2f+1+f/2\) validators, and hence collects at least that many votes for each proposer. Failing to build the meta-block means that, for some proposer \(p\), neither quorum has formed: among the votes it holds for \(p\), fewer than \(2f+1\) are positive and fewer than \(2f+1\) are negative. Thus \(p\) drew at most \(2f\) positive votes and at most \(2f\) negative votes; and since the two counts together sum to at least \(2f+1+f/2\), each of them is, in turn, at least \(f/2+1\).

This split is precisely the fingerprint of partial dissemination, and, crucially, one we can prove. Among the \(f/2+1\) positive votes, at most \(f/2\) can come from Byzantine validators, so at least one comes from a correct validator: one that genuinely received \(p\)’s proposal by the deadline, witnessing that \(p\) did disseminate to someone.¹⁵ Among the \(f/2+1\) negative votes, by the very same counting, at least one comes from a correct validator that genuinely did not receive it, witnessing that \(p\) did not disseminate to everyone. Because all votes are signed, these two witnesses together form a transferable certificate: anyone, knowing that at most \(f/2\) validators are faulty, can read off from \(f/2+1\) signed positive and \(f/2+1\) signed negative votes that some correct validator received \(p\)’s proposal while some other correct validator did not. That is exactly partial dissemination, so correct validators can hold \(p\) accountable.

The split-vote certificate is always a sound, transferable proof that \(p\) partially disseminated; what depends on synchrony is only reading a fallback as \(p\)’s fault, since under asynchrony even a correct proposer can miss the fast path. A single fallback is therefore no cause to act, but a proposer that provably and repeatedly partially disseminates can be penalized.

7.2 Latency, Scheduling, and Economic Ticks↩︎

7.2.0.1 Proposal timing.

An honest proposer disseminates its chunks early enough that, under synchrony, every chunk reaches every validator before the deadline. The worst-case message delay \(\Delta\) is a conservative bound; a well-connected proposer reaches all validators within a smaller delay \(\delta < \Delta\) of its own, so it can disseminate as late as \(\delta\) before the deadline and still have its chunks arrive in time. Disseminating later lets a proposal include fresher transactions and so improves end-to-end latency for users, so each proposer sets its own dissemination time according to its connectivity. Disseminating too late—while potentially lucrative for rational proposers [18], [19]—risks reaching only some validators in time, which can push the slot onto the slower fallback path; our accountability mechanism (§7.1) deters this by leaving evidence of partial dissemination. A proposer that is entirely silent, by contrast, forces no fallback and leaves no such split-vote evidence: every validator simply records a negative entry and votes against it. Such a proposer needs no dedicated liveness incentive, since forgoing its proposal reward is penalty enough.

7.2.0.2 Early voting.

By default, a validator broadcasts its proposal vote at the slot deadline. As an optional optimization, which we call early voting, a validator may vote earlier in slot \(s\) once every entry for \(s\) is positive. So that this does not weaken hiding, a validator releases its decryption share only at the deadline, decoupled from its vote, so proposals are revealed no earlier than before. Recovering the proposals does not delay finalization: their chunks are disseminated together with the votes, so reconstruction needs no extra round, and only decryption waits for the shares released at the deadline. In our experiments, gathering the \(f+1\) shares completes around the time a slot is speculatively finalized, well before it is fully finalized, so a slot’s proposals are recovered in time even when its votes were cast early.

Early voting reduces finalization latency. A slot can finalize as soon as its proposals have arrived and gathered commit votes, rather than waiting for the deadline. How much it saves depends on all of the slot’s proposers together: a vote can be cast early only once every entry is positive, so the more conservatively they disseminate, leaving a margin before the deadline, the further ahead the slot can finalize.

7.2.0.3 Cycles.

Some blockchains decouple the on-chain economic tick from the consensus tick with cycles: on-chain activity advances in shorter cycles while consensus still runs once per slot, as in Constellation [3]. Cycles let activity such as auctions and oracle updates tick at the finer granularity, but they do not lower end-to-end latency, since a transaction is still finalized only once per slot. They are thus no substitute for extreme pipelining, which lowers the block interval itself. Their one advantage is message complexity, since consensus does not run more often. Chorus could support cycles as a straightforward extension: each slot carries \(K\) cycles, each proposer disseminates one part of its proposal before each cycle’s deadline, and a validator casts a single proposal vote per slot, positive for a proposer only if it received that proposer’s assigned chunk of every part in time. The positive vote then carries the combined Merkle root over the proposer’s \(K\) parts, so \(2f+1\) such votes certify its whole proposal exactly as without cycles.

7.3 Transaction Privacy↩︎

Hiding conceals each proposal from everyone until the deadline, but a proposer a user submits to sees the transaction in plaintext. So a user trades off how many proposers to submit to: more improve inclusion and censorship resistance, while fewer reduce the chance that one of them leaks or front-runs the transaction. Client-side transaction encryption, where the user encrypts the transaction before submitting it, as in encrypted mempools [20]–[22], removes this trade-off, since the user can submit to many proposers without revealing the contents to any of them. It does not replace MCP: on its own it gives no short-term censorship resistance [23], since a proposer can censor a ciphertext without reading it. Nor does it replace proposal encryption: in a practical deployment, where proposers compete (say, for transaction fees), hiding protects each proposer’s payload from its rivals, which transaction encryption does not. The two can compose. For either scheme, both the timing of share release and the decryption threshold (\(f+1\) or more) are protocol choices that trade off latency and availability against the strength of hiding.

8 Latency Evaluation↩︎

We estimate Cadence’s fast-path network latency, the common case in which every proposer is correct or fully silent, on the \(200\) stake-weighted, globally distributed validators of Monad mainnet. We define end-to-end latency as the time from when a transaction reaches a proposer until it is finalized. It has two parts: the finalization latency, the time from the transaction entering a proposal until it is finalized, and the inclusion latency, the wait until it enters a proposal. The finalization latency is, on average, \(219\) ms to full finality and \(167\) ms to speculative finalization after a single voting round. The inclusion latency is, on average, half a block interval, so, for example, \(50\) ms for a block interval of \(\tau= 100\) ms. Composing the two, the end-to-end latency averages \(269\) ms to full finality and \(217\) ms to speculative finalization. The early-voting optimization (7.2.0.2) improves these figures by about \(30\) ms: the finalization latency drops to \(191\) ms (full) and \(137\) ms (speculative), and the end-to-end latency to \(241\) ms and \(187\) ms. In the early-voting case, a slot’s decryption shares arrive on average \(5\) ms after its speculative finalization, well before full finalization. The user-to-proposer hop these figures omit tends to be smaller in MCP than in single-leader protocols, since a user is more likely to have a nearby proposer, which improves overall latency.

We obtain these figures from a simulation calibrated to RIPE Atlas round-trip measurements among the 83 (city, ASN) groups in which these validators run as of June 2026, with five concurrent proposers per slot. We set each proposer’s lead time, the interval by which it broadcasts ahead of the deadline, so that in \(99\%\) of trials at least \(90\%\) of validators receive its chunk before the deadline. Across proposers, this lead time averages \(104\) ms.

The simulated propagation delays are the dominant part of this end-to-end latency. The contributions it omits are small: local processing at validators, where execution and most validity checks occur asynchronously ([subsection:uncertainty]), and the bandwidth-induced queueing delay, which is at most a few milliseconds.¹⁶

9 Related Work↩︎

9.1 Pipelining↩︎

Motivated by the goal of driving inter-proposal time down, much of the community’s effort has centered on pipelining. Protocols such as the HotStuff family [9], [24], [25], MonadBFT [12], and Jolteon [26] accomplish this by chaining proposals through quorum certificates (QCs): a leader is free to issue its next proposal as soon as it collects a QC for the previous one, which brings the inter-proposal time down to \(2\Delta\). Pushing this idea further, optimistic designs such as Moonshot [27] and Hydrangea++ [28] assume consecutive honest leaders and let a leader propose even before the prior proposal has been quorum-certified, bringing the inter-proposal time down to the network delay \(\Delta\) itself, though not below it. We go below this bound with extreme pipelining, which achieves sub-\(\Delta\) block intervals by running independent, non-chained single-shot consensus instances rather than chaining proposals at all.

A similar line of work reaches sub-\(\Delta\) intervals by staggering several multi-shot consensus instances in time and merging their outputs into one log: Shoal++ [29] interleaves three DAG protocols one message delay apart, Raptr [30] generalizes this to \(K\) instances offset by \(2/K\) message delays, and, concurrently with our work, Gatling [31] casts it as parallel composition over any atomic broadcast protocol. Where we run one sequence of independent single-shot slots, these interleave several instances to the same effect.

Constellation [3] introduces cycles, arbitrarily short economic ticks; complementary to extreme pipelining, they shorten the economic tick, while their underlying consensus produces blocks at a rate bounded by the network delay. We discuss cycles, and how they can be incorporated into Cadence, in 7.2.0.3.

9.2 Multiple Concurrent Proposers↩︎

Garimidi et al. [1] set out the goals of multiple concurrent proposers, including censorship resistance and hiding; these goals have since been pursued, through different mechanisms, by Prefix Consensus [32], Constellation [3], and AMP [33]. All of these designs provide some notion of censorship resistance. Only Garimidi et al. [1] incorporate hiding into their protocol design, though AMP notes that hiding is orthogonal to its core protocol and could be added. To our knowledge, Chorus is the first MCP design to offer both short-term censorship resistance (for every block after GST plus a grace period) and an optimal three-round good-case latency.

9.2.0.1 Prefix Consensus.

Prefix Consensus [32], a leaderless multi-proposer SMR, achieves good-case latency comparable to that of our fast path, while guaranteeing \(f\)-censorship-resistance: after \(\mathrm{GST}\), there may be up to \(f\) slots for which censorship resistance does not hold. Crucially, and in contrast to our work, these \(f\) slots are adversarially chosen; they need not be the first \(f\) slots after \(\mathrm{GST}\), but may be placed at any point. In Chorus, by contrast, censorship resistance holds for all slots beyond a bounded interval following \(\mathrm{GST}\): only slots falling within this bounded grace period may lack censorship resistance, while every subsequent slot is guaranteed it, and the adversary can do nothing to violate it.

9.2.0.2 Constellation.

Constellation [3] is a multiple-proposer protocol layered on Solana’s Alpenglow [34]. Proposers disseminate their transactions to a layer of attesters whose attestations constrain which proposals the leader must include, giving it selective censorship resistance. Because this inclusion layer sits on top of Alpenglow’s consensus, finalization takes two more communication rounds than the consensus alone.

9.2.0.3 AMP.

AMP [33] is a multiple-proposer layer on the Tendermint consensus algorithm. Like Constellation, it separates dissemination from agreement, which costs two extra communication rounds: proposers broadcast transaction payloads, and validators agree only on their identifiers, carried in vote extensions that constrain which payloads the leader must include. Its central guarantee is bounded inclusion: a payload attested by all correct validators at one height is forced into the block at the next. AMP inherits Tendermint’s safety and liveness and its \(f < n/3\) threshold.

9.2.0.4 DAG-based protocols.

DAG-based protocols [35]–[38] are aimed at high throughput (and, in recent designs, low latency) rather than at the guarantees we require, and although several provide some notion of censorship resistance, they do not target the strict short-term censorship-resistance guarantee we require. Since every validator proposes each round, they are multiple-concurrent-proposer in a broad sense, but as Garimidi et al. [1] observe, amending them to provide short-term censorship resistance is not straightforward, as it appears to require giving up the optimistic responsiveness, which lets them commit at network speed in the good case (synchrony and an honest leader).

Acknowledgments↩︎

We thank Andrei Constantinescu, Andrea Canidio, and Babak Poorebrahim Gilkalaye for helpful discussions and feedback.

Organization of the Appendix↩︎

This appendix gives the formal treatment underlying the body. It restates the MCP problem precisely (10), defines our extreme-pipelining framework and proves that it solves MCP given conforming building blocks (11), and then instantiates the two building blocks: Chorus(12) and Conductor, together with its boundedness and recovery guarantees (13).

10 Multiple Concurrent Proposers (MCP): Formal Problem Definition↩︎

This section gives a precise, formal statement of the MCP problem that 2 introduced informally.

10.1 Preliminaries↩︎

The MCP problem involves several abstract entities; we begin by introducing each of them precisely.

10.1.1 Slots.↩︎

Each slot \(s\) carries three fields:

We emphasize that all three fields are read-only: a slot’s number, deadline, and proposers are fixed and never change. This is a deliberate, minor departure from 2, where we described the deadline as something the protocol determines. Treating deadlines as given — rather than as a protocol output — keeps the problem statement clean: otherwise the MCP problem definition would have to carry extra guarantees about how deadlines are produced. The protocol still adapts its timing not by moving deadlines but by skipping slots, as we make precise below.

For each \(i \in \mathbb{N}_{\geq 1}\), there exists exactly one slot \(s\) with \(s.\mathsf{number}= i\). Moreover, deadlines respect the slot order: for any two slots \(s_1, s_2\) with \(s_1.\mathsf{number}< s_2.\mathsf{number}\), we have \(s_1.\mathsf{deadline}\leq s_2.\mathsf{deadline}\). (For our extreme-pipelining framework, we additionally assume that consecutive deadlines are a fixed, known interval \(\tau\) apart, with \(\tau > 0\): that is, \(s.\mathsf{deadline}= s'.\mathsf{deadline}+ \tau\) for every slot \(s\) with \(s.\mathsf{number}> 1\), where \(s'\) is the slot with \(s'.\mathsf{number}= s.\mathsf{number}- 1\).) We sometimes refer to the starting time of a slot \(s\), by which we mean \(s.\mathsf{deadline}- \Delta\). Moreover, we require the first slot (the slot \(s\) with \(s.\mathsf{number}= 1\)) to have a deadline of at least \(\Delta\), so its starting time is non-negative; and since deadlines only grow with the slot number, every slot then has a non-negative starting time. (For our extreme-pipelining framework, we assume that the starting time of the first slot is \(0\).)

10.1.2 Proposals & Proposal Vectors.↩︎

A proposal \(P\) carries three fields:

We also introduce proposal vectors, which bundle one proposal per proposer of a slot. Concretely, a proposal vector \(V\) carries:

We impose one constraint on the aforementioned mapping: whenever \(V[p] \neq \bot\), the proposal \(V[p]\) must be \(p\)’s own proposal for that slot, i.e., \(V[p].\mathsf{slot}= V.\mathsf{slot}\) and \(V[p].\mathsf{proposer}= p\). Two proposal vectors are identical if and only if their slots are identical and their mappings are identical: \(V_1 = V_2\) exactly when \(V_1.\mathsf{slot}= V_2.\mathsf{slot}\) and \(V_1[p] = V_2[p]\) for every proposer \(p \in V_1.\mathsf{slot}.\mathsf{proposers}\). For our purposes a proposal vector is interchangeable with a block: a block can be obtained from a proposal vector by a fixed, deterministic transformation (ordering the proposals’ transactions, discarding invalid ones, and so on). Since this transformation is an application-level concern, irrelevant to consensus, and since proposal vectors make our later definitions cleaner, we phrase everything in terms of proposal vectors.

10.1.3 Logs.↩︎

A log is a (possibly empty) ordered list of proposal vectors with strictly increasing slot numbers: if \(V_1\) precedes \(V_2\) in the log, then \(V_1.\mathsf{slot}.\mathsf{number}< V_2.\mathsf{slot}.\mathsf{number}\). For a log \(\mathcal{L}\), we write \(\mathcal{L}.\mathsf{length}\) to denote its number of proposal vectors, and \(\mathcal{L}[i]\) for its \(i\)-th proposal vector, where \(i \in [1, \mathcal{L}.\mathsf{length}]\). Notably, a log need not contain a proposal vector for every slot: some slots may be “skipped”, contributing no proposal vector to the log. In particular, \(\mathcal{L}.\mathsf{length}\) may be strictly less than \(\mathcal{L}[\mathcal{L}.\mathsf{length}].\mathsf{slot}.\mathsf{number}\). (Permitting such skips is the formal counterpart of the informal view in 2, where no slot is skipped and the schedule instead simply spaces consecutive slot deadlines apart in time. These two views — skipping slots here versus spacing deadlines there — are equivalent reformulations of the same underlying ledger, and we make the correspondence between them precise in 11.1.) For a proposal vector \(V\) and a log \(\mathcal{L}\), we write “\(V \in \mathcal{L}\)” to denote that \(V\) appears in \(\mathcal{L}\). Furthermore, we say that two logs \(\mathcal{L}_1\) and \(\mathcal{L}_2\) are consistent if and only if \(\mathcal{L}_1[i] = \mathcal{L}_2[i]\), for every \(i \in [1, \min(\mathcal{L}_1.\mathsf{length}, \mathcal{L}_2.\mathsf{length})]\); otherwise, they are inconsistent. (Any log is consistent with the empty log.)

10.2 Interface↩︎

The interface of the MCP problem is simple:

10.3 Guarantees↩︎

We now specify the correctness properties that any MCP protocol must satisfy, defining each in turn. The MCP problem inherits the standard guarantees of consensus — safety and liveness — and adds two more on top: censorship resistance and hiding.

10.3.1 Safety.↩︎

As in any consensus protocol, the foundational property is safety: the logs of all correct validators must be mutually consistent at all times.

10.3.2 Liveness.↩︎

As noted in 10.1, logs may inherently skip slots: not every slot need contribute a proposal vector to a validator’s local log. However, liveness requires that this skipping cannot persist indefinitely after \(\mathrm{GST}\): there exists a post-\(\mathrm{GST}\) grace period after which every slot contributes a proposal vector to the local log of every correct validator. This precisely corresponds to the eventual stability guarantee we described informally in 2.

We underline that the parameter \(\ell\) is not a fixed universal constant but rather a measure of the quality of a protocol: it captures how quickly a protocol resumes producing proposal vectors after \(\mathrm{GST}\), and we naturally prefer protocols that achieve a smaller \(\ell\). Accordingly, \(\ell\) need not be a constant and may depend on the parameters of the model and the execution, such as \(n\), \(f\), \(\Delta\), and \(\mathrm{GST}\). For instance, a protocol whose grace period grows the longer the network remains asynchronous (e.g., under a linear or exponential backoff) is captured by an \(\ell\) that increases with \(\mathrm{GST}\).

10.3.3 Short-Term Censorship Resistance.↩︎

Liveness ensures that slots are not skipped indefinitely after \(\mathrm{GST}\), but says nothing about the content of the finalized proposal vectors: a protocol that always finalizes empty proposal vectors (assigning \(\bot\) to every proposer) is live yet useless. We therefore additionally require censorship resistance: the proposal of a correct proposer for a slot cannot be suppressed by Byzantine validators, but must be included in the proposal vector finalized for that slot. Concretely, there exists a grace period \(c\) such that, for every slot \(s\) whose starting time is at least \(c\) after \(\mathrm{GST}\), the proposal vector finalized for \(s\) includes the proposals of all correct proposers of \(s\).

As with the parameter \(\ell\) of \(\ell\)-liveness, the parameter \(c\) measures the quality of a protocol: it bounds how quickly the proposals of correct proposers are included after \(\mathrm{GST}\) (smaller is preferable), and may likewise depend on the model and execution parameters. We clarify the relationship between liveness and censorship resistance once more. The two differ in what they assume about the proposers of a slot. Liveness guarantees that, after the grace period, every slot eventually contributes a proposal vector to the log, regardless of whether its proposers are correct or faulty. Censorship resistance, in contrast, concerns the content of that proposal vector, and only constrains slots that have at least one correct proposer (since it speaks about proposals held by correct proposers). The two properties are thus complementary: liveness ensures that a slot contributes a proposal vector, while censorship resistance, for a slot with a correct proposer, ensures that the proposer’s proposal is included by that slot.

10.3.4 Hiding.↩︎

In defining the hiding property, the intuition we want to capture is that faulty proposers cannot submit proposals that depend on the contents of proposals submitted by honest proposers. However, there are some nuances that need to be addressed:

To formalize the above, we make a simulation-based definition. This definition is in the spirit of Universal Composability (UC) [39], but we do not require the full machinery of the UC framework. Just as in the UC framework, we have a “real world” and an “ideal world”. In the real world, validators interact with the actual protocol. In the ideal world, there is an ideal functionality \(\mathcal{F}\) and a simulator (a.k.a.ideal-world adversary) \(\mathcal{S}\). Both worlds are driven by an environment \(\mathcal{Z}\) — an arbitrary efficient (i.e., probabilistic polynomial-time) entity that supplies the inputs to the honest validators and observes their outputs. The environment also plays the role of the adversary: in the real world it directly controls the faulty validators, whereas in the ideal world those faulty validators are instead controlled by the simulator \(\mathcal{S}\), with which \(\mathcal{Z}\) may interact. We assume static corruption: the set of faulty validators is fixed before the execution begins. The environment’s goal is to tell the two worlds apart. In the ideal world, all inputs from and outputs to honest validators pass directly between \(\mathcal{Z}\) and \(\mathcal{F}\), while inputs from and outputs to faulty validators pass between \(\mathcal{S}\) and \(\mathcal{F}\). Critically, the interface seen by the environment is the same in both worlds. It thus suffices to define the ideal functionality \(\mathcal{F}\) corresponding to our hiding property, which we do next. We describe \(\mathcal{F}\) for a single slot; the full functionality applies it to every slot.

Having specified \(\mathcal{F}\), we now state our hiding property: a protocol is hiding precisely when its real-world execution cannot be told apart from this ideal world.

11 Our Extreme-Pipelining Framework: Formal Exposition↩︎

We now give the formal account of the extreme-pipelining framework, the framework we introduced informally in 3. Recall that Cadence, our concrete MCP protocol, is the specific instantiation of the extreme-pipelining framework obtained by taking Chorus as the slot consensus and Conductor as the orchestrator.

11.1 Building Blocks: Slot Consensus & Orchestrator↩︎

We now formally define the two abstract building blocks on which our extreme-pipelining framework relies: slot consensus and the orchestrator, introduced informally in 3.1 and 3.2, respectively.

11.1.1 Slot Consensus.↩︎

The slot consensus primitive is specified formally in [mod:slotconsensus]; each of its instances is parameterized by a slot \(s\). The interface reflects the two roles a validator plays: a participant in the consensus process and, for designated slots, a proposer. On the participation side, validators explicitly signal when they start and stop contributing to an instance; between these two events we say that the validator is actively contributing. (We track this explicitly — though consensus protocols usually leave it implicit — because our analysis of the extreme-pipelining framework aims to bound how many instances a correct validator actively contributes to at any one time.) On the proposer side, designated validators additionally submit their proposals. Together, these participation signals and proposals form a validator’s inputs to the instance, while its sole output is a finalization: a validator may finalize a single proposal vector for slot \(s\).

The slot consensus primitive guarantees five correctness properties. Agreement and termination are the usual safety and liveness: correct validators never finalize conflicting proposal vectors, and if all correct validators start participating, then every correct validator eventually finalizes. Importantly, agreement constrains each validator individually as well: no correct validator finalizes two different proposal vectors, even on separate occasions. Slot safety requires that the finalized proposal vector \(V\) carry the correct slot identifier \(s\). (Slot safety is the one property we omitted from the informal overview in 3.1, as it is a self-evident condition that reveals nothing conceptually interesting about the primitive.) Proposal inclusion guarantees that every proposal submitted by a correct proposer by the slot’s starting time appears in \(V\) (under synchrony). Hiding, finally, is the slot-level counterpart of the MCP hiding guarantee (4), specialized to the instance’s slot \(s\).

11.1.2 Orchestrator.↩︎

[mod:orchestrator952] provides the orchestrator’s full specification. Validators supply a single input: upon completing their work on a slot \(s\), a validator notifies the orchestrator by completing \(s\). The orchestrator, in turn, produces a single output: for an upcoming slot \(s'\), it may instruct a validator to open \(s'\); there is no separate “skip” output. Instead, we informally say that a slot a validator never opens is skipped. It is worth reconciling this interface with the informal overview (3.2), where we described the orchestrator’s job as determining the deadlines of slots. In the formal model, by contrast, slots — and all information about them, including their deadlines — are fixed and read-only (10.1). The two views are equivalent: instead of delaying a slot’s deadline, as the informal orchestrator would, the formal orchestrator simply skips the intervening slots and opens the slot whose (fixed) deadline already coincides with the desired, later time. Skipping slots is thus the formal counterpart of pushing deadlines back. Throughout the rest of the paper, we adopt the \(\tau\)-spaced deadline structure foreshadowed in 10.1: consecutive slots’ deadlines are a fixed, known interval \(\tau\) apart.

The orchestrator must satisfy five correctness properties. The first three establish the correctness baseline. Totality ensures that an opening propagates to all correct validators: if any correct validator opens a slot \(s\), then every correct validator eventually opens \(s\) as well. Integrity ensures that no correct validator opens the same slot more than once, and that no slot is opened before its starting time (though it may be opened after that time). Monotonicity ensures that validators open slots in strictly increasing order. Let us underline a stronger consequence of these three properties together: whenever a correct validator \(p_i\) opens a slot \(s\), every correct validator opens exactly the same set of slots with number at most \(s.\mathsf{number}\). To see this, consider any slot \(s'\) with \(s'.\mathsf{number}\leq s.\mathsf{number}\). First, note that \(s'\) can be opened at most once (due to the integrity property). If \(p_i\) opens \(s'\), then by totality every correct validator opens \(s'\) as well. Otherwise, \(p_i\) skips \(s'\); that is, it opens \(s\) without ever opening \(s'\) (here, \(s'.\mathsf{number}< s.\mathsf{number}\)). We argue that then no correct validator opens \(s'\) either: suppose some correct validator \(p_j\) did: by totality, \(p_i\) would open \(s'\) too, and by monotonicity — as \(s'.\mathsf{number}< s.\mathsf{number}\) — it would have to do so before opening \(s\), which is impossible, since \(p_i\) opened \(s\) without ever opening \(s'\). In both cases, \(p_i\) and every other correct validator agree on whether \(s'\) is opened, which establishes the claim.

The remaining two properties are the most involved and the most distinctive: rather than establishing a correctness baseline, as the three above do, they measure the quality of an orchestrator. The first, \(\mathcal{B}\)-boundedness, bounds how many slots may be simultaneously open but not yet completed at any given time; the second, \(\mathcal{R}\)-recovery, bounds how long after network stabilization it takes before the orchestrator opens all upcoming slots on time. We motivate \(\mathcal{B}\)-boundedness before stating it, since the reason to bound the open slots is memory.

11.1.2.1 Memory consumption in our framework.

In our extreme-pipelining framework (as we detail in 11.2), a validator opens a fresh slot consensus instance for every slot it does not skip, so the more slots stay open, the more memory it must devote to them; we therefore want to keep each validator’s memory bounded. Formally reasoning about memory, however, is delicate. To make a memory bound meaningful, one must work in a model with an unreliable network: under a reliable network, undelivered messages must be buffered until delivery, which is fundamentally at odds with bounding memory. Yet adopting an unreliable network would introduce considerable additional machinery (retransmission, garbage collection, checkpointing, and similar mechanisms), whose techniques are, at least in theory, standard and largely orthogonal to our contribution. As memory management is not where we innovate, we retain the reliable-network assumption throughout, and consequently do not reason about memory consumption directly. Instead, we capture the same concern through a clean abstraction: the number of slot consensus instances in which a validator is actively participating at any given time, namely those it has started but not yet abandoned. Bounding this number bounds the resources a validator devotes to ongoing instances, and thus serves as our proxy for memory. We call this property bounded concurrency. Reassuringly, it is not a guarantee we need to establish on its own: a validator participates in a slot’s consensus instance exactly while that slot is open but not yet completed, so bounded concurrency follows directly from the \(\mathcal{B}\)-boundedness property we define next — and with the very same bound \(\mathcal{B}\).

11.1.2.2 \(\mathcal{B}\)-Boundedness.

This property limits how far ahead a validator may open slots without completing earlier ones: at any point in time, only the last \(\mathcal{B}\) slots opened (by slot number) may still be pending completion, while all previously opened slots must already have been completed. In the context of our extreme-pipelining framework, since completing a slot means its proposal vector has been finalized, \(\mathcal{B}\)-boundedness implies that every correct validator has already finalized all but the last \(\mathcal{B}\) opened slots, yielding a complete log prefix that trails the frontier by at most \(\mathcal{B}\) slots. Here, \(\mathcal{B} \in \mathbb{N}_{\geq 0} \cup \{\infty\}\): a finite \(\mathcal{B}\) bounds the number of simultaneously open slots, whereas \(\mathcal{B} = \infty\) imposes no such bound and thus captures orchestrators that open slots arbitrarily far ahead without completing earlier ones. We underline once more that \(\mathcal{B}\) measures the quality of a protocol (smaller is preferable) and need not be a constant: it may depend on the model and execution parameters, such as \(n\), \(f\), \(\Delta\), and \(\mathrm{GST}\).

11.1.2.3 \(\mathcal{R}\)-Recovery.

This property captures what we require once the network stabilizes after a period of asynchrony. Two demands must be met jointly. First, validators must stop skipping slots: once the network recovers, all upcoming slots are opened rather than skipped. Second, and more subtly, validators must open upcoming slots “on time”, namely at exactly their starting time. Opening a slot on time is a natural expectation: validators may have time-sensitive work to perform upon opening, making the precise timing of this event crucial. To see why this matters, we illustrate with the concrete example of our extreme-pipelining framework. There, the proposal-inclusion property of slot consensus guarantees that every proposal submitted by a correct proposer at the slot’s starting time appears in the finalized proposal vector. If the slot is opened late, the proposer misses the starting time, proposal inclusion no longer applies, and Byzantine validators may suppress correct proposers’ proposals entirely. This would cause slot consensus to finalize a proposal vector devoid of any correct proposer’s proposals — potentially an empty one — which, in the blockchain setting we target, leaves the application state unchanged and is therefore no more useful than a skipped slot, yet far costlier to produce. An orchestrator that merely guarantees eventual opening, without the timing condition, would therefore be insufficient. Combining both demands, we say the orchestrator satisfies \(\mathcal{R}\)-recovery if both conditions hold for every slot whose starting time is at least \(\mathcal{R}\) after \(\mathrm{GST}\). Unlike \(\mathcal{B}\), \(\mathcal{R}\) must be finite; but, like \(\mathcal{B}\), it captures protocol quality (smaller is preferable) and may be any function of the model and execution parameters.

11.2 Composing the Building Blocks↩︎

We now describe how the slot consensus and the orchestrator compose into the extreme-pipelining framework. Each correct validator maintains a single orchestrator instance \(\mathcal{O}\) and one slot consensus instance \(\mathcal{S}[s]\) per slot \(s\), and the framework is simply the glue that wires these components together. Throughout, \(\mathcal{O}\) is assumed to achieve \(\mathcal{B}\)-boundedness and \(\mathcal{R}\)-recovery for some \(\mathcal{B} \in \mathbb{N}_{\geq 0} \cup \{\infty\}\) and some time duration \(\mathcal{R}\). The pseudocode is given in 14, traced from the perspective of a correct validator \(p_i\), with a complementary visual overview in 15.

11.2.0.1 Protocol description.

Upon starting, \(p_i\) begins executing \(\mathcal{O}\) (line [line:start-orch]), which drives the protocol forward by deciding, for each slot \(s\), whether to open it; recall that the orchestrator has no explicit skip output, so a slot it never opens is implicitly skipped. When \(\mathcal{O}\) opens slot \(s\) (line [line:upon-open]), \(p_i\) records \(s\) as opened and starts participating in \(\mathcal{S}[s]\) (lines [line:opened-update]–[line:participate]); if \(p_i\) is a designated proposer (i.e., \(p_i \in s.\mathsf{proposers}\)), it additionally submits its proposal \(P_s\) for slot \(s\) to \(\mathcal{S}[s]\) (lines [line:proposer-check]–[line:propose]). Whereas opening is signaled explicitly by \(\mathcal{O}\), skipping is not: when \(p_i\) opens \(s\), it records every smaller-numbered slot it has not opened as skipped (line [line:implicit-skip]). For a skipped slot, no consensus instance is spawned and no proposal vector is produced.

Crucially, multiple slot consensus instances may run concurrently and may finalize out of order. Upon \(\mathcal{S}[s]\) finalizing a proposal vector \(V\), for some slot \(s\) (line [line:upon-finalize]), \(p_i\) places \(V\) in a pending set (line [line:pending-add]), notifies \(\mathcal{O}\) that slot \(s\) has been completed (line [line:complete]), and stops participating in \(\mathcal{S}[s]\) (line [line:abandon]). Pending proposal vectors are then appended to \(p_i\)’s local log in slot-number order: a pending proposal vector \(V'\) is appended (line [line:append]) as soon as every slot with a strictly smaller number than \(V'.\mathsf{slot}.\mathsf{number}\) has already been resolved, that is, either recorded as skipped or finalized and appended to \(\mathit{log}_i\) (line [line:func-ready-to-append-return]). This ordering condition ensures that \(\mathit{log}_i\) is indeed a log in the sense of 10.1: proposal vectors appear in strictly increasing order of slot number.

11.2.0.2 On the generality of the framework.

We wish to highlight that extreme pipelining is intentionally presented as a generic framework, not merely as a vehicle for our specific instantiation. The framework is deliberately minimal: it prescribes nothing more than the interaction between a slot consensus instance and an orchestrator, leaving both components entirely abstract and subject only to the properties stated in [mod:slotconsensus] [mod:orchestrator952]. As a direct consequence, every property of the framework, including its resilience to Byzantine faults, is inherited from the properties of the underlying components rather than hard-coded into the framework itself. In this paper, we indeed focus on the standard Byzantine fault model with \(n = 3f + 1\) validators. However, the framework imposes no such constraint: to obtain a different protocol, it suffices to supply a slot consensus and an orchestrator satisfying the respective module specifications, and the correctness of the resulting protocol follows immediately from their properties, with no additional argument needed. This flexibility extends well beyond the resilience threshold. For instance, one may target a different threshold, or trade resilience for another guarantee such as improved performance, simply by instantiating the two components accordingly. One may also depart from the multiple-concurrent-proposers setting entirely: instantiating the slot consensus with a single designated proposer per slot recovers a classical “single-leader” blockchain. Likewise, one is free to plug in a linear-communication slot consensus, and nothing else changes. In every case, the framework itself is untouched; only the two plugged-in components change.

11.3 Proof↩︎

In this subsection, we prove that the extreme-pipelining framework introduced above, composed of the slot consensus and the orchestrator, solves the MCP problem.

11.3.0.1 Safety.

We first establish that the safety property is satisfied.

11.3.0.2 Liveness.

Next, we prove that the extreme-pipelining framework satisfies liveness.

As noted earlier, safety and liveness are standard properties, not specific to the MCP problem. The fact that the extreme-pipelining framework satisfies both underscores its applicability beyond the MCP setting. We now turn to the MCP-specific properties.

11.3.0.3 Censorship resistance.

We next prove the censorship resistance property.

11.3.0.4 Hiding.

Next, we prove hiding, which reduces to the hiding of each slot consensus instance.

11.3.0.5 Bounded concurrency.

Recall from 11.1.2.1 that we do not reason about memory directly, but use the number of slot consensus instances a validator actively participates in as a proxy for its memory consumption. This number stays bounded:

12 Chorus: Our Slot Consensus for Cadence↩︎

This section presents Chorus, the protocol that instantiates the slot-consensus primitive of Cadence. We introduced Chorus informally, and in some detail, in 4; here we give its full specification.

12.1 Cryptographic Primitives↩︎

Chorus builds on several standard cryptographic primitives, whose notation we fix here.

12.1.0.1 Hash function.

We assume a collision-resistant cryptographic hash function \[H : \{0,1\}^* \rightarrow \{0,1\}^\lambda .\]

12.1.0.2 Digital signatures.

Each validator \(p_i\) holds a signing keypair \((sk_i,pk_i)\). We use the following operations:

A set of signatures \(\{\sigma_i\}_{i \in \mathcal{I}}\) on a common message \(m\) can be aggregated into a short multi-signature \(\Sigma\) verifiable against \(\{pk_i\}_{i \in \mathcal{I}}\).

12.1.0.3 Erasure coding.

The encrypted proposal is erasure-coded to enable distributed availability. Throughout the section, we rely on the following operations:

12.1.0.4 Merkle trees.

Merkle trees are used to commit to encoded payload chunks. We assume the following interface:

12.1.0.5 Random-oracle convention.

For the simulation argument in §12.2, we model several hash functions as distinct random oracles, including the identity hash \(H_{\mathsf{id}}\), the pad-derivation hash \(H_{\mathsf{pad}}\), and the Merkle hash \(H_{\mathsf{Merkle}}\). The simulator programs \(H_{\mathsf{pad}}\); it does not program \(H_{\mathsf{Merkle}}\), but it inspects the adversary’s Merkle-oracle queries to recover the leaves committed by a submitted Merkle root. In an implementation, all such functions should be realized through a standard domain-separated hash API, using unambiguous encodings of all inputs. Untagged calls to a raw hash function, or ad hoc concatenation of values before hashing, should be avoided. The Merkle hash domain should be separate from the identity-hash and pad-derivation domains; ideally, the Merkle implementation should also distinguish leaf hashing from internal-node hashing.

12.2 Proposal Encryption and Slot-Key Release↩︎

This subsection describes the cryptographic mechanism used to hide proposal contents until the slot’s deadline. The important point is that the threshold operation is not proposal-specific decryption. Instead, validators release shares of the slot secret key: the identity secret key for an identity derived from the slot \(s\), with standard domain separation for the protocol instance. Once this slot key is reconstructed, anyone can open any well-formed proposal ciphertext for that slot.

12.2.0.1 Identity-based KEM with distributed extraction.

We use an identity-based key encapsulation mechanism (IB-KEM) whose private-key extraction algorithm is implemented by a distributed private-key generator. The ordinary IB-KEM syntax is \[(\mathit{mpk},\mathit{msk}) \leftarrow \mathsf{Setup}(1^\lambda), \qquad \mathit{sk}_{\mathit{id}} \leftarrow \mathsf{Extract}(\mathit{msk},\mathit{id}),\] \[(Z,C_{\mathsf{kem}}) \leftarrow \mathsf{Encap}(\mathit{mpk},\mathit{id}), \qquad Z \leftarrow \mathsf{Decap}(\mathit{sk}_{\mathit{id}},\mathit{id},C_{\mathsf{kem}}).\] Here, \(Z\) is the KEM’s raw key and \(C_{\mathsf{kem}}\) is the public encapsulation. The raw key need not itself be a bit string; in the pairing-based instantiation below it is a target-group element. Bit strings used by the protocol are derived by hashing \(Z\) with appropriate domain separation.

The distributed version replaces only \(\mathsf{Extract}\). A \((t,n)\)-distributed extraction mechanism consists of algorithms \[(\mathit{mpk},\mathit{vk},\mathit{st}_1,\ldots,\mathit{st}_n) \leftarrow \mathsf{DSetup}(1^\lambda,n,t),\] \[\sigma_i \leftarrow \mathsf{ShareExtract}(\mathit{st}_i,\mathit{id}), \qquad b \leftarrow \mathsf{VerifyShare}(\mathit{mpk},\mathit{vk},\mathit{id},i,\sigma_i),\] \[\mathit{sk}_{\mathit{id}} \leftarrow \mathsf{CombineExtract}(\mathit{mpk},\mathit{vk},\mathit{id},\{(i,\sigma_i)\}_{i\in I}), \qquad |I|\ge t .\] After combining extraction shares to obtain \(\mathit{sk}_{\mathit{id}}\), decapsulation is the ordinary non-threshold operation. Thus extraction shares depend only on the identity \(\mathit{id}\), not on any particular proposal ciphertext. Correctness requires that honestly generated and verified shares combine to the same \(\mathit{sk}_{\mathit{id}}\) as the ideal extraction algorithm. Robustness requires that adversarial shares that pass verification contribute correctly, so that any verified qualified set either combines to the unique correct slot key or is rejected.

The security property we need is weaker than full KEM key indistinguishability. We require unpredictability: before enough valid extraction shares have been released for an identity \(\mathit{id}\), no efficient adversary corrupting fewer than the threshold number of extraction servers can compute the raw key \(Z\) belonging to a fresh encapsulation under \(\mathit{id}\), except with negligible probability. Equivalently, if a later layer derives a pad as a random-oracle value \(H(Z,\ldots)\), then any adversary that learns this pad before release must have queried the random oracle at the hidden point involving \(Z\).

A concrete instantiation is obtained from the Boneh–Franklin/BLS pairing construction. Let \(G\) be a generator, let \(a\) be the master secret, and let the master public key contain \(aG\). For identity \(\mathit{id}\), let \(Q_{\mathit{id}}=H_{\mathsf{id}}(\mathit{id})\) and \(\mathit{sk}_{\mathit{id}}=aQ_{\mathit{id}}\). A distributed private-key generator can Shamir-share \(a\): server \(i\) returns the verified extraction share \(\sigma_i=a_iQ_{\mathit{id}}\), and interpolation reconstructs \(aQ_{\mathit{id}}\). Encapsulation chooses \(r\) at random, publishes \(C_{\mathsf{kem}}=U=rG\), and computes \[Z=e(Q_{\mathit{id}},aG)^r .\] Decapsulation with the reconstructed identity secret key computes \[Z=e(\mathit{sk}_{\mathit{id}},U)=e(aQ_{\mathit{id}},rG).\] Unpredictability of this raw key follows, in the random-oracle model for the identity hash, from the standard computational-BDH assumption and the usual Boneh–Franklin proof strategy. The protocol never uses the target-group element \(Z\) directly as a symmetric key; it hashes \(Z\) with appropriate domain separation.

12.2.0.2 Encrypting proposals.

For a slot \(s\), let \(\mathit{id}_s\) be the canonical encoding of \(s\) as an IB-KEM identity. A proposer \(P\) encapsulates to this identity, obtaining \[(Z,C_{\mathsf{kem}}) \leftarrow \mathsf{Encap}(\mathit{mpk},\mathit{id}_s).\] It then derives a pad from the raw key, the slot, the proposer identity, and any additional public context bound to this encryption: \[K = H_{\mathsf{pad}}(Z,s,P,\mathsf{ctx}).\] The inputs \(Z\), \(s\), and \(P\) are essential. The value \(\mathsf{ctx}\) denotes any remaining public context for this encryption, and may include \(C_{\mathsf{kem}}\), protocol-version information, and deployment or chain identifiers. If the proposal payload is \(M\), the encrypted payload is the xor mask \[C_{\mathsf{pay}} = K \oplus M,\] where \(H_{\mathsf{pad}}\) is viewed as a hash-to-bytes or XOF-style oracle whose output is expanded as needed to match the payload length. We deliberately use this xor-with-random-oracle form, rather than an authenticated symmetric encryption scheme, because it gives the simulator the equivocation needed in the hiding proof: an honestly generated ciphertext can initially be a random bit string and later be made to open to the ideal-world proposal by programming \(H_{\mathsf{pad}}\) at the appropriate point.

The object encoded for data availability contains at least \((C_{\mathsf{kem}},C_{\mathsf{pay}})\) and the necessary public context. This object is erasure-coded, the fragments are committed by a Merkle tree, and the proposer signs the resulting Merkle root. Thus the submitted encrypted proposal is fixed by a signed Merkle root, not by a plaintext. A proposal is considered submitted before the deadline only if at least one honest validator receives, before \(s.\mathsf{deadline}\), a valid signature by the claimed proposer on the corresponding Merkle root. Signature unforgeability ensures that, except with negligible probability, the adversary cannot create a submitted proposal that appears to come from an honest proposer.

12.2.0.3 Releasing the slot key.

At the slot’s deadline, validators publish extraction shares \[\sigma_i \leftarrow \mathsf{ShareExtract}(\mathit{st}_i,\mathit{id}_s)\] for the slot identity. Once enough verified shares have been collected, anyone computes \[\mathit{sk}_{\mathit{id}_s} \leftarrow \mathsf{CombineExtract}(\mathit{mpk},\mathit{vk},\mathit{id}_s,\{(i,\sigma_i)\}_{i\in I}).\] The same reconstructed slot key opens all well-formed proposal encapsulations for slot \(s\): for each decoded proposal ciphertext, parties compute \[Z \leftarrow \mathsf{Decap}(\mathit{sk}_{\mathit{id}_s},\mathit{id}_s,C_{\mathsf{kem}}), \qquad M = C_{\mathsf{pay}} \oplus H_{\mathsf{pad}}(Z,s,P,\mathsf{ctx}).\] The released values are therefore extraction shares for the slot identity, not decryption shares tied to individual proposals.

12.2.0.4 Simulation argument.

We sketch why this realizes the hiding property (4). The proof is best viewed as an ordering argument at the deadline of a fixed slot \(s\); no infinitesimal notion of time is needed. At the deadline transition, corrupt proposals that were already submitted are fixed first. Only after those corrupt inputs have been determined does the simulator obtain the honest proposals from the ideal functionality.

Before the deadline, the simulator handles honest proposers as follows. For each honest proposer, it chooses the public KEM encapsulation as in the real protocol, but it chooses the encrypted payload \(C_{\mathsf{pay}}\) as a uniformly random bit string of the appropriate length. It erasure-codes the resulting encrypted object, computes the Merkle root, signs the root as the honest proposer, and delivers fragments as prescribed by the protocol. At this point the simulator does not yet know the honest plaintext proposal.

At the deadline transition, the simulator first identifies the corrupt submissions. A corrupt submission is eligible only if some honest validator received, before \(s.\mathsf{deadline}\), a valid signature on a Merkle root under the verification key of the claimed corrupt proposer. The simulator then walks back from this root through the transcript of queries to the Merkle random oracle \(H_{\mathsf{Merkle}}\). It must recover all leaves under the signed root. These leaves must be valid erasure-code fragments and must form a complete codeword encoding a well-formed encrypted proposal. If any leaves are missing, if the leaves do not form a codeword, or if the decoded object is malformed, the simulator does not treat the root as a properly submitted proposal. The simulator uses the Merkle oracle only in this inspection mode; unlike \(H_{\mathsf{pad}}\), it is not programmed.

For each well-formed corrupt ciphertext submitted by a corrupt proposer \(P'\), the simulator obtains the released slot key \(\mathit{sk}_{\mathit{id}_s}\), decapsulates \(C_{\mathsf{kem}}\), and obtains the raw key \(Z\). It then considers the pad-oracle point \[q=(Z,s,P',\mathsf{ctx}).\] If \(H_{\mathsf{pad}}(q)\) has already been defined, the simulator uses that existing value. If it has not been defined, the simulator programs it to a fresh random string. In either case it sets \[M' = C_{\mathsf{pay}} \oplus H_{\mathsf{pad}}(q)\] and submits this \(M'\) to the ideal functionality as the corrupt proposer’s input for slot \(s\). This is the only possible behavior consistent with the already fixed ciphertext and the random-oracle transcript: if the adversary queried the point, the answer is fixed; if it did not, a fresh random answer has exactly the distribution of a random oracle answer.

Only after all such corrupt inputs have been submitted does the simulator receive the honest proposals from the ideal functionality. For each honest proposer \(P\), the simulator now knows both the previously fixed random ciphertext \(C_{\mathsf{pay}}\) and the desired plaintext \(M\). It programs the corresponding pad-oracle point by setting \[H_{\mathsf{pad}}(Z,s,P,\mathsf{ctx}) := C_{\mathsf{pay}} \oplus M .\] This makes the already disseminated encrypted payload decrypt to the honest proposal supplied by the ideal functionality.

The simulation can fail only if the simulator is forced to program an oracle point that was already defined inconsistently, or if the adversary creates an ambiguity in what was submitted. For corrupt proposals, the simulator explicitly avoids inconsistency by using any existing pad-oracle value. For honest proposals, unpredictability of the IB-KEM raw key prevents the adversary from querying the honest pad-oracle point before the release transition, except with negligible probability; the deadline transition is ordered so that there is no intervening adversarial oracle query between release of the slot key and the simulator’s programming of honest points. Including the proposer identity in the pad-oracle input separates honest-proposer points from corrupt-proposer points, and signature unforgeability prevents the adversary from submitting roots under honest proposer identities. Finally, the Merkle/random-oracle and erasure-code checks ensure that a signed root determines a unique well-formed encrypted proposal; otherwise the root is treated as malformed. Conditioned on the complement of these bad events, the simulated transcript is distributed as in the real protocol, while corrupt proposals are fixed before honest proposal contents are revealed.

12.3 Protocol↩︎

We now present the Chorus protocol. It is given as several algorithms, split across the subsubsections below only to separate its concerns; they form a single protocol and should be read as one. The Chorus protocol proceeds in three phases: proposers disseminate their proposals (Phase I), validators broadcast a single proposal vote at the slot’s deadline (or when they enter the slot, if later) (Phase II), and a meta-block’s entries are committed either via the fast path or via the fallback path (Phase III). 16 implements Phase I and runs at proposers only. 17 implements Phase II at every validator. Phase III is implemented by two modules running in parallel: 18 aggregates proposal votes into \(\mathsf{FastQC}\)s and runs the two-round fast commit on a fast meta-block, while 19 drives the fallback path when a fast meta-block cannot be formed: it harvests the strongest available evidence per proposer into a fallback meta-block, feeds it to a multi-valued validated Byzantine agreement (MVBA, [mod:mvba]) — a primitive in which validators agree on a single externally-valid value among those they propose — and commits the entries of the MVBA output. Cutting across all phases, the data-availability module (20) provides chunk validation, ciphertext reconstruction, decryption, and proposal recovery. Modules communicate through the shared local state declared in their “Local variables” blocks (e.g., \(\mathit{Ev}(j)\) and \(\mathit{pathVote}\) are shared between the fast-path and fallback-path modules). Throughout the pseudocode, we say that \(p_i\) is actively participating in \(s\) if it has invoked the slot-consensus input \(\mathsf{participate}()\) but has not yet invoked \(\mathsf{abandon}()\).

12.3.1 Dissemination & Voting↩︎

Each slot \(s\) is bounded by a deadline \(s.\mathsf{deadline}\). Each honest proposer in \(s.\mathsf{proposers}\) (1) constructs a proposal, (2) encrypts it, (3) erasure-codes the ciphertext into chunks (one per validator), and (4) disseminates them by time \(s.\mathsf{deadline}- \Delta\) (in the style of AVID [13] and DispersedSimplex [5])¹⁷. Under synchrony, every honest validator receives a chunk from every honest proposer by the deadline. Validators record which chunks arrived in time and, at the deadline (or when they enter the slot, if later), broadcast a proposal vote: a single message containing a signed positive or negative entry per proposer.

12.3.1.1 Proposal.

A proposal by proposer \(p_j\) in slot \(s\) is \[P = \langle s, j, \mathit{Payload}, \sigma \rangle,\] where \(s\) is the slot, \(j\) is the proposer index, \(\mathit{Payload}\) is the proposal’s transaction payload, and \(\sigma\) is \(p_j\)’s signature over \(\langle s, j, H(\mathit{Payload}) \rangle\). The triple \(\langle s, j, \mathit{Payload}\rangle\) is exactly a proposal in the sense of the problem definition (10.1); we simply spell out its fields here rather than carry it as a single object.

To preserve hiding, the proposer does not disseminate \(P\) directly: it encrypts \(P\) to produce an encrypted proposal \(EP\), decryptable only once \(f+1\) validators have released their decryption shares for the slot (after the deadline). We disseminate \(EP\) in place of \(P\).

12.3.1.2 Chunks.

To distribute the dissemination load, the proposer erasure-codes the encrypted proposal \(EP\) into \(n\) fragments \(d_1, \ldots, d_n\) (one per validator) and builds a Merkle tree over the leaves \(H(1, d_1), \ldots, H(n, d_n)\), yielding a root \(\rho\). The reconstruction threshold is chosen so that any \(f+1\) fragments suffice to reconstruct \(EP\). The proposer forms a chunk header common to all recipients, \[\mathit{ChunkHeader} = \langle s, j, \rho, \sigma \rangle,\] where \(\sigma\) is \(p_j\)’s signature over \((s, j, \rho)\), and sends a chunk \[\langle \mathrm{\small Chunk}, \mathit{ChunkHeader}, r, d_r, \pi_r \rangle\] to each validator \(p_r\), where \(\pi_r\) is a Merkle proof for \(H(r, d_r)\) under root \(\rho\). We refer to this message as the chunk assigned to \(p_r\).

12.3.1.3 Entries.

Each validator \(p_i\) collects incoming chunks until the slot’s deadline \(s.\mathsf{deadline}\). For each proposer \(p_j\), \(p_i\) records an entry \[E = \langle s, j, \rho_{\!\bot}\rangle,\] where \(\rho_{\!\bot}\in \mathsf{MerkleRoot} \cup \{\bot\}\) is the Merkle root of the chunk assigned to \(p_i\) that it received from \(p_j\) (a positive entry), or \(\bot\) if no valid chunk arrived by the deadline (a negative entry). Validators vote on entries by signing them.

12.3.1.4 Proposal vote.

At the deadline \(s.\mathsf{deadline}\) (or when \(p_i\) enters the slot, if later), each validator \(p_i\) reports what it received for the slot by broadcasting a single proposal vote. This message does three things at once: it carries \(p_i\)’s signed positive/negative entry for each proposer, supplies the chunks backing the positive entries, and releases \(p_i\)’s decryption share for the slot. Concretely: \[\langle \mathrm{\small Vote}, s, \mathit{SignedEntries}, \mathit{Chunks}, \mathit{DecryptShare} \rangle,\] where \(\mathit{SignedEntries}\) contains a signed entry \(\langle E, \sigma\rangle\) per proposer in \(s.\mathsf{proposers}\) (with \(p_i\)’s signature \(\sigma\) on \(\langle\mathrm{\small vote}, E\rangle\)), \(\mathit{Chunks}\) contains the chunk messages \(p_i\) received and validated for each positive entry, and \(\mathit{DecryptShare}\) is \(p_i\)’s share toward decrypting slot-\(s\) proposals.

12.3.1.5 \(\mathsf{FastQC}\).

A fast-path quorum certificate (\(\mathsf{FastQC}\)) for an entry \(E\) aggregates \(2f+1\) signatures over \(\langle\mathrm{\small vote}, E\rangle\): \[\mathsf{FastQC}= \langle \mathrm{\small vote}, E, \Sigma \rangle.\] A \(\mathsf{FastQC}\) for a positive entry \(E = \langle s, j, \rho\rangle\) certifies that \(2f+1\) validators received and validated a chunk from \(p_j\) under root \(\rho\), so at least \(f+1\) honest validators hold chunks; this is what guarantees data availability for \(p_j\)’s proposal.

12.3.2 Fast Path.↩︎

The fast path commits the slot in two voting rounds after the deadline, without needing a leader to drive progress, provided a \(\mathsf{FastQC}\) can be formed for every proposer (a fast meta-block). Recall that a \(\mathsf{FastQC}\) aggregates \(2f+1\) votes on the same entry. If a proposer disseminates early enough, every honest validator receives its assigned chunk before the deadline and records the same positive entry, so \(2f+1\) matching positive votes are cast. If a proposer does not propose at all, every honest validator records a negative entry, so \(2f+1\) negative votes are cast. If instead a proposer disseminates too late, only some validators receive a chunk before the deadline (partial dissemination): these vote positively and the rest negatively, so there may be neither \(2f+1\) positive nor \(2f+1\) negative votes, and no \(\mathsf{FastQC}\) forms. In that case, validators take the fallback path.

12.3.2.1 Fast meta-block.

A fast meta-block for slot \(s\) is \[B = \langle CE_{j_1}, \ldots, CE_{j_k} \rangle,\] where each \(CE_j\) is a \(\mathsf{FastQC}\) for proposer \(p_j\in s.\mathsf{proposers}\). We write \(\mathsf{entries}(B)\) for the sequence of entries \(E\) embedded in the \(\mathsf{FastQC}\)s.

12.3.2.2 Fast commit vote and certificate.

Once a validator \(p_i\) has a fast meta-block\(B\), it broadcasts a fast commit vote \[\langle \mathrm{\small CommitVote}, s, \mathsf{entries}(B), \sigma_i \rangle,\] where \(\sigma_i\) signs \(\langle \mathrm{\small Commit}, s, \mathsf{entries}(B)\rangle\). A \((2f{+}1)\)-aggregate of such votes forms a fast commit certificate \[\mathsf{CommitQC}= \langle \mathrm{\small Commit}, s, \mathsf{entries}(B), \Sigma \rangle,\] which finalizes the entries \(\mathsf{entries}(B)\): any validator that holds the \(\mathsf{CommitQC}\) recovers the underlying proposals via \(\hyperref[alg:da]{Alg~\ref*{alg:da}}.\mathsf{recoverProposals}(\mathsf{entries}(B))\) and commits them. The commit fixes the entries, not the certificates that \(B\) carries: across validators a slot’s entries agree, whereas the certificates justifying them may differ.

12.3.2.3 Speculative commit.

Once a validator has \(\mathsf{FastQC}\)s for every proposer, it can speculatively commit the proposal vector before waiting for the \(\mathsf{CommitQC}\).

12.3.3 Fallback Path.↩︎

If a \(\mathsf{FastQC}\) fails to form for some proposer, validators cannot assemble a fast meta-block and the fast path stalls. A \(\mathsf{FastQC}\) fails to form when the votes split between positive and negative, so that neither a positive nor a negative quorum forms (partial dissemination). This can result from the proposer disseminating too late or to too few validators, or from network asynchrony. A \(\mathsf{FastQC}\) can also fail to form under equivocation, when the proposer sends different proposals so that no single entry gathers a quorum. From time \(s.\mathsf{deadline}+ \Delta\) onwards, each validator that has received at least \(2f+1\) proposal votes but has not been able to form a fast meta-block casts a fallback vote in place of a fast commit vote; the two are mutually exclusive, so each validator casts at most one. On the fallback path, the validator builds a fallback meta-block by collecting, and where necessary contributing to, per-proposer evidence: a \(\mathsf{FastQC}\) when one exists, otherwise a \(\mathsf{FallbackQC}\) (a weaker certificate that the validators help assemble in this phase), or, in adversarial cases, an \(\mathsf{EquivCert}\) that pins a proposer to equivocation. It then feeds the fallback meta-block to a Multi-Value Byzantine Agreement (MVBA) primitive. The meta-block output by the MVBA is the meta-block committed by the slot consensus.

12.3.3.1 Fallback signed entries & \(\mathsf{FallbackQC}\).

A fallback signed entry from validator \(p_r\) for proposer \(p_j\) is \[\langle E, \sigma_v\rangle \text{ (negative, } E.\rho_{\!\bot}= \bot\text{)} \quad \text{or} \quad \langle E, \sigma_v, \sigma_p\rangle \text{ (positive, } E.\rho_{\!\bot}= \rho\text{)},\] where \(\sigma_v\) is \(p_r\)’s signature over \(\langle\mathrm{\small fb}, E\rangle\) and, for the positive case, \(\sigma_p\) is the proposer’s signature on \(\langle s, j, \rho\rangle\) carried over from the chunk header. A validator constructs its own fallback signed entry for each proposer for which it holds no evidence yet: it sets \(\rho_{\!\bot}\gets \rho\) if it has accumulated \(f+1\) valid fast-path positive votes for the same root \(\rho\) and the data is locally available (\(\hyperref[alg:da]{Alg~\ref*{alg:da}}.\mathsf{isDecoded}(\rho)\) returns true), and \(\rho_{\!\bot}\gets \bot\) otherwise.

A fallback-path quorum certificate (\(\mathsf{FallbackQC}\)) for entry \(E\) aggregates \(f+1\) signatures over \(\langle\mathrm{\small fb}, E\rangle\): \[\mathsf{FallbackQC}= \langle \mathrm{\small fb}, E, \Sigma \rangle.\] The \(\mathrm{\small vote}\)/\(\mathrm{\small fb}\) tags domain-separate the universal proposal-vote signatures from the fallback-only signatures.

12.3.3.2 \(\mathsf{EquivCert}\).

An equivocation certificate for proposer \(p_j\) is \[\mathsf{EquivCert}= \langle \mathrm{\small equiv}, s, j, \rho_1, \sigma_{p,1}, \rho_2, \sigma_{p,2} \rangle,\] where \(\rho_1 \neq \rho_2\) and each \(\sigma_{p,k}\) is \(p_j\)’s signature over \(\langle s, j, \rho_k\rangle\). The \(\mathsf{EquivCert}\) exists for liveness: a Byzantine proposer can split its chunks across multiple Merkle roots so that no single fallback signed entry attracts \(f+1\) matching votes, leaving a \(\mathsf{FallbackQC}\) unformable; pinning the proposer to two contradictory signed roots still certifies its exclusion.

12.3.3.3 Fallback vote message.

Once time has reached \(s.\mathsf{deadline}+ \Delta\) and \(p_r\) has received at least \(2f+1\) proposal votes (the inputs needed to assemble the message), and provided it has not entered the fast commit path, \(p_r\) broadcasts a fallback vote: \[\langle \mathrm{\small FallbackVote}, s, \sigma_r, \mathit{Ev}_{j_1}, \ldots, \mathit{Ev}_{j_k} \rangle,\] where \(\sigma_r = \mathsf{Sign}_r(\langle\mathrm{\small fallback}, s\rangle)\) is \(p_r\)’s commitment to entering the fallback path, and each \(\mathit{Ev}_j\) is the strongest evidence \(p_r\) holds for \(p_j\), by precedence \(\mathsf{FastQC}\succ \mathsf{EquivCert}\succ \mathsf{FallbackQC}\succ\) fallback signed entry (the last being \(p_r\)’s own signed entry when no higher-tier evidence is available).

12.3.3.4 Fallback certificate.

Once \(2f+1\) fallback votes are collected, their \(\sigma_r\) fields aggregate into a fallback certificate \[\mathsf{FBCert}_s= \langle \mathrm{\small fallback}, s, \Sigma \rangle,\] certifying that the fast path can no longer commit slot \(s\).

12.3.3.5 Fallback meta-block.

From \(2f+1\) fallback votes, each validator builds a fallback meta-block \[B = \langle CE_{j_1}, \ldots, CE_{j_k}, \mathsf{FBCert}_s\rangle,\] where each \(CE_j\) is a certified entry for \(p_j\): a \(\mathsf{FastQC}\), \(\mathsf{FallbackQC}\), or \(\mathsf{EquivCert}\) (the latter two assembled from the signed entries collected in fallback votes, when no \(\mathsf{FastQC}\) is available). Extending the convention from 12.3.2, \(\mathsf{entries}(B)\) contributes the embedded \(E\) for a \(\mathsf{FastQC}\) or \(\mathsf{FallbackQC}\), and the negative entry \(\langle s, j, \bot\rangle\) for an \(\mathsf{EquivCert}\) for \(p_j\) (equivocation excludes the proposer); \(\mathsf{FBCert}_s\) is not part of \(\mathsf{entries}(B)\). We call a meta-blockvalid if it is either a fast meta-block or a fallback meta-block in this sense.

12.3.3.6 Invocation to the MVBA primitive.

The validator then proposes its meta-block \(B\) to \(\mathsf{MVBA}[s]\), the slot’s multi-valued Byzantine agreement instance, invoking it at most once; \(B\) is valid by construction. The MVBA we use ([mod:mvba]) is standard but for one twist: it agrees not on a meta-block directly but on a certificate for one — a compact, publicly verifiable token, recognized by the function \(\mathsf{Certifies}\), that attests to a meta-block.

When the MVBA outputs a meta-block\(B'\), the validator recovers the underlying proposals by calling \(\mathsf{recoverProposals}(\mathsf{entries}(B'))\) on the DA module and commits them. Even after invoking the MVBA, a validator still finalizes on the fast path if a \(\mathsf{CommitQC}\) arrives; whenever it finalizes, by either path, it broadcasts the commitment proof and concludes all activity for the slot, including its MVBA invocation.

12.3.4 Data Availability.↩︎

The data-availability (DA) module is responsible for recovering the proposals originally embedded by each proposer in chunks.

12.3.4.1 Chunk reception.

On receiving a chunk, the DA module verifies the proposer’s signature and the chunk’s Merkle proof against its root \(\rho\). Two things then follow. First, if the chunk is the one assigned to this validator, the module rebroadcasts it and notifies the voting module, so the validator can record a positive entry for \(\rho\) before the deadline. Second, once \(f+1\) valid chunks for the same root \(\rho\) accumulate, the module decodes them into a candidate encrypted proposal \(c\) and re-encodes \(c\), comparing the resulting root against \(\rho\): if they match, \(c\) is confirmed; otherwise \(\rho\) is marked invalid, catching a proposer that disseminated inconsistent chunks under one root.

12.3.4.2 Decryption.

Because proposals are disseminated encrypted to preserve hiding, reconstructing \(c\) does not yet reveal the proposal. Each validator releases a decryption share for the slot together with its vote; once the module holds \(f+1\) valid shares, it decrypts \(c\) into the proposal, or marks \(\rho\) invalid if decryption fails.

12.3.4.3 Proposal recovery.

At commit time (speculative or formal), a validator calls \(\mathsf{recoverProposals}(\mathsf{entries}(B))\) on the DA module. The call blocks until every positive entry \(\langle s, j, \rho\rangle \in \mathsf{entries}(B)\) has either been recovered to a proposal or marked invalid, then returns the recovered proposals (ordering their transactions into a block is a subsequent, application-level step). Both commit routes guarantee that this call eventually returns: a \(\mathsf{FastQC}\) for a positive entry implies that \(f+1\) honest validators contributed chunks (enough to decode by erasure coding); a \(\mathsf{FallbackQC}\) for a positive entry implies that at least one honest validator has already decoded the proposal locally and re-disseminates the chunks (Alg 19). These two facts are the formal counterpart of the availability of §4.1.2. Its companion consistency corresponds to the determinism of the re-encode-and-compare check in tryIngestChunk (Alg 20, line [line:da-reencode]), where the verdict on a root, whether to accept and decode it or mark it invalid, depends only on the chunks committed under it and not on which \(f+1\) a validator happens to collect. Every correct validator therefore reaches the same verdict, and on acceptance decodes the same ciphertext.

12.4 Proof↩︎

This subsection proves that, when run within Cadence, Chorus realizes the slot-consensus primitive (see [mod:slotconsensus]). We do so by establishing each of its properties — agreement, termination, slot safety, proposal inclusion, and hiding — in turn.

12.4.0.1 Hiding.

We begin with the hiding property.

12.4.0.2 Slot safety.

Next, we prove the slot safety property.

12.4.0.3 Agreement.

We now prove that Chorus satisfies agreement: no two correct validators finalize different proposal vectors. A validator finalizes only when it holds a commitment proof for a meta-block — a fast commit certificate \(\mathsf{CommitQC}\) or the certificate the MVBA decides ([mod:mvba]) — whereupon it triggers \(\mathsf{finalize}\): in the fast path on a valid \(\mathsf{CommitQC}\) (18, line [line:fast-finalize]), and in the fallback path on the MVBA’s decision (19, lines [line:fb-finalize1] and [line:fb-finalize2]) or on a received commit message (19, line [line:fb-finalize3]). We argue in two steps: any two meta-blocks backed by a commitment proof carry the same entries, and the same entries yield the same proposal vector at every correct validator.

We are ready to prove the agreement property of Chorus.

12.4.0.4 Proposal inclusion.

We now prove the proposal inclusion property. We first show that an on-time honest proposer can never be excluded: in any certified meta-block, its entry is the positive entry carrying its proposal’s root.

With the proposer’s entry pinned down by [prop:honest-positive-entry], we can now establish proposal inclusion.

12.4.0.5 Termination.

We first establish totality: once one correct validator finalizes, every correct validator finalizes within \(2\Delta\) (assuming synchrony). Totality serves a dual purpose — it is the key step in Chorus’s own termination, and Conductor relies on it in its own right (14) — so we record it as a standalone property.

With totality in hand, we bound when every correct validator finalizes assuming no correct validator stops participating.

We are finally ready to establish Chorus’s termination.

13 Conductor: Our Window-Based Orchestrator for Cadence↩︎

In this section, we present Conductor, a protocol that serves as the orchestrator primitive within Cadence. Recall that we described Conductor informally in 5.

13.1 Protocol↩︎

Here, we introduce Conductor(21). Before presenting it, we describe the building block it relies on, agreement on a core set (ACS).

13.1.1 Agreement on a Core Set (ACS).↩︎

The full specification of ACS is given in [mod:acs]. In a nutshell, each of the \(n\) validators submits a proposal, and ACS outputs a single set, agreed upon by all correct validators, that contains at least \(n - f\) of the submitted proposals.

13.1.2 Protocol Description.↩︎

21 gives Conductor‘s pseudocode, written from the perspective of a single correct validator \(p_i\); recall that validators’ clocks are synchronized, so they share one global timeline. As described informally in 5, Conductor groups slots into windows of \(W\) consecutive slots and schedules them one at a time, opening a window only once enough of the earlier ones have completed. Window \(1\) consists of slots \(1, \ldots, W\), and each subsequent window again spans \(W\) consecutive slots. Unlike in the informal description, however, consecutive windows need not be adjacent: a window’s first slot is chosen dynamically and may lie strictly beyond the previous window’s last slot, leaving a gap of intervening slots that are simply never opened. (This stems from the slight difference in the problem definition between the two parts: here, slots have fixed, read-only deadlines, whereas in the informal part the protocol determines them. The orchestrator therefore cannot freely place the next deadline; it can only select an existing slot whose fixed deadline matches, skipping the intervening ones.) Throughout, \(p_i\) tracks the window it is currently scheduling in \(\mathit{current\_window}_i\) (initially \(1\), line [line:current95window95init]), the slots it has opened in \(\mathit{opened}_i\), the slots reported complete in \(\mathit{completed}_i\), the last (highest-numbered) slot of each window in \(\mathit{last}_i\), and the windows for which it has already submitted an ACS proposal in \(\mathit{proposed}_i\).

Parameters & constants. Conductor takes two tunable parameters: the window size \(W \in \mathbb{N}_{\geq 1}\) and the readiness threshold \(p \in \{0, \dots, W-1\}\), which controls how much of a window must complete before the next one is opened. Its timing further involves several constants: \(\ell\), the termination latency of the underlying ACS primitive (line [line:acs-instances]); \(\ell_{\mathrm{\small chorus}}\), the termination latency of Chorus, the slot-consensus protocol whose finalizations complete Conductor’s slots within Cadence; \(\Delta_{\mathsf{tot}}= 2\Delta\) ([prop:chorus-totality]), the totality latency of Chorus— the time within which one correct validator’s completion of a slot propagates to all correct validators; \(\Delta\), the post-\(\mathrm{GST}\) bound on message delays; and \(\tau\), the spacing between consecutive slot deadlines. From these we derive the open-to-complete delay \(\Phi_{oc} = \ell_{\mathrm{\small chorus}} + \Delta_{\mathsf{tot}}\), which bounds the time between a correct validator opening a slot and completing it ([prop:conductor-open-to-complete]). For Conductor to achieve its recovery property, \(W\) and \(p\) must be chosen so that the following four assumptions hold (lines [line:assumption-one]–[line:assumption-four]):

Intuitively, they ensure that all the work tied to a window — proposing to the next ACS instance, deciding, and completing the window’s slots — fits within its time span of \(W\tau\), so that, once the network is synchronous, one window follows the next with no gaps. These assumptions are crucial for recovery, as we show in 13.2.

Startup. Upon starting (line [line:conductor-startup]), \(p_i\) enters window \(1\) (line [line:enter95window951]) and schedules the opening of its \(W\) slots in increasing order (lines [line:startup-foreach]–[line:startup-opened-update]), recording slot \(W\) as that window’s last slot (line [line:startup-last]). Opening is asynchronous: \(\mathsf{schedule\_opening}(s)\) waits until the slot’s starting time \(s.\mathsf{deadline}- \Delta\) — or fires at once if it has already passed — and then outputs \(\mathsf{open}(s)\) (lines [line:conductor-wait-for-open]–[line:trigger-open]). Since deadlines are \(\tau\)-spaced, window \(1\)’s slots thus open at times \(0, \tau, \ldots, (W-1)\tau\).

Completions. After startup, the only input to Conductor is the completion of slots: upon \(\mathsf{completed}(s)\) (line [line:upon-completed]), \(p_i\) adds \(s\) to \(\mathit{completed}_i\) (line [line:completed-update]). Within Cadence, \(p_i\) completes a slot precisely when it finalizes that slot’s proposal vector.

Estimating the next window’s deadline. Conductor opens window \(\mathit{current\_window}_i + 1\) only once enough of the current schedule has completed, as captured by \(\mathsf{ready\_for\_next\_window}()\) (line [line:ready-check]): writing \(s_1 < \cdots < s_k\) for the opened slots, it returns \(\mathsf{true}\) once all but at most the last \(W - p\) of them are complete — equivalently, once every slot of the earlier windows and the first \(p\) slots of the current window are done. When this first holds for the next window (line [line:ready]), \(p_i\) estimates that window’s first slot: it reads the current time \(t_{\mathit{cur}}\) (line [line:ready-time]) and lets \(s^\star\) be the earliest slot whose starting time has not yet passed (line [line:sstar-compute]); if that slot still falls within the current window, it advances \(s^\star\) to the first slot beyond it (lines [line:sstar-guard]–[line:sstar-update]). These two cases are exactly the estimate of 11: when the system is keeping up, \(s^\star\) is the slot immediately after the current window, so the cadence continues with no gap; when it is lagging, \(s^\star\) is pushed to \(t_{\mathit{cur}}\), leaving a gap for the backlog to drain. Validator \(p_i\) then proposes \(s^\star\) to the next window’s agreement instance \(\mathcal{ACS}[\mathit{current\_window}_i + 1]\) (line [line:acs-propose]) and records that it has done so (line [line:proposed-update]), so that it proposes at most once per window.

Agreeing on and opening the next window. Different correct validators may complete the first \(p\) slots at different times and thus estimate different first slots for the next window, so they agree on one through ACS. Once \(\mathcal{ACS}[\mathit{current\_window}_i + 1]\) decides and \(p_i\) is ready (line [line:acs-decide]), \(p_i\) advances to the next window (lines [line:window-increment]–[line:enter95window95omega]) and takes its first slot \(s^\star\) to be the median of the decided estimates (line [line:median-compute]); since at most \(f\) of the \(2f+1\) decided values are faulty, the median lies between the smallest and largest honest estimate, bounding Byzantine influence. It then schedules the opening of the window’s \(W\) slots \(s^\star, \ldots, s^\star + W - 1\) in increasing order (lines [line:open-foreach]–[line:acs-opened-update]) and records \(s^\star + W - 1\) as the window’s last slot (line [line:last-update]). Because \(p_i\) opens a fresh window only when at most the last \(W - p\) slots of the current one remain incomplete (line [line:ready-check]), at most \((W - p) + W = 2W - p\) slots are ever in flight — precisely Conductor’s boundedness.

13.2 Proof↩︎

This section proves that, when run within Cadence, Conductor satisfies the orchestrator specification of [mod:orchestrator952]. Before proving the individual properties, we first establish a number of structural facts about Conductor’s windows; these underpin the entire subsequent analysis of the specific orchestrator properties.

13.2.0.1 Structural facts about windows.

We first establish that windows are entered at most once and in strictly increasing order.

For every correct validator \(p_i\) and every window \(\omega \in \mathbb{N}_{\geq 1}\) that \(p_i\) enters, we define the following set of slots: \[\mathsf{slots}_i(\omega) \mathrel{\vcenter{:}}= \{ s \in \mathsf{Slot}: p_i \text{ schedules the opening of } s \text{ upon entering window } \omega \}.\] Concretely, \(\mathsf{slots}_i(1)\) consists of the \(W\) slots scheduled to be opened at startup (lines [line:startup-foreach]–[line:startup-opened-update]). For \(\omega \geq 2\), \(\mathsf{slots}_i(\omega)\) consists of the \(W\) slots scheduled to be opened in the loop at lines [line:open-foreach]–[line:acs-opened-update].

Throughout the rest of the proof, we adopt the following notational convention. Recall that, in Conductor, each validator invokes the ACS primitive to decide a vector of validator-slot pairs (line [line:acs-decide]) and then extracts the slot whose number is the median over all slot numbers in the vector (line [line:median-compute]). For brevity, we say that the ACS primitive decides slot \(s\) to refer to the outcome of this combined decision and extraction step, where \(s\) is the resulting slot. Crucially, the slot number of \(s\) lies between the minimum and maximum slot numbers proposed by correct validators (since the decided vector contains at least \(f + 1\) pairs contributed by correct validators). We next establish that the slot sets of distinct windows are pairwise disjoint. To this end, we first establish that the ACS primitives never decide overlapping slots.

We now precisely characterize, for each window, the exact set of slots that a correct validator opens upon entering it, and establish that consecutive windows cover non-overlapping ranges of \(W\) slots.

For each correct validator \(p_i\) and each slot \(s\), we define \(\mathsf{window}_i(s)\) to be the window \(\omega\) to which \(s\) belongs, that is, the window \(\omega\) with \[s \in \mathsf{slots}_i(\omega).\] If no such window exists, we set \(\mathsf{window}_i(s) = \bot\). By [prop:acs-fate-range], whenever such a window exists, it is unique; hence, \(\mathsf{window}_i(s)\) is well-defined. We now establish that no two correct validators disagree on the window to which a slot belongs.

13.2.0.2 Integrity.

We now prove the integrity property specified in [mod:orchestrator952], which ensures that each correct validator opens each slot at most once, and that no slot is opened before its starting time.

13.2.0.3 Monotonicity.

We now establish that each correct validator schedules the opening of slots in strictly increasing order of slot number, which we leverage to prove monotonicity.

We are now ready to prove that Conductor satisfies monotonicity (see [mod:orchestrator952]), which guarantees that correct validators open slots in strictly increasing order of slot number.

13.2.0.4 Boundedness.

We say that a correct validator \(p_i\) is in window \(\omega \in \mathbb{N}_{\geq 1}\) from the moment it enters window \(\omega\) until the moment it enters the next window (which is \(\omega + 1\), by [lemma:window-entry]). The following proposition relates the window in which a correct validator currently resides to the number of slots it has accumulated in its local variable \(\mathit{opened}_i\).

We are now ready to prove that Conductor satisfies \((2W - p)\)-boundedness (see [mod:orchestrator952]), which guarantees that at most \(2W - p\) slots are simultaneously open (that is, opened but not yet completed) at any point in time.

13.2.0.5 Totality.

The previous three properties were established for Conductor in isolation: each constrains only how Conductor schedules and opens slots, and therefore holds regardless of how — or even whether — slots are subsequently completed. The remaining two, totality and recovery, are of a different nature. Both hinge on slots actually completing, and on doing so in a timely, coordinated fashion — something Conductor only reacts to, but does not itself bring about. We therefore establish totality and recovery only for Conductor run within Cadence, alongside Chorus(14), whose finalization supplies precisely the completion guarantees that these two properties rely on.

We begin with totality. In fact, we establish a stronger, quantitative form of it — \(\Delta_{\mathsf{tot}}\)-totality: if a correct validator opens a slot \(s\) at some time \(t\), then every correct validator opens \(s\) by time \(\max(t, \mathrm{GST}) + \Delta_{\mathsf{tot}}\). Here, \(\Delta_{\mathsf{tot}}= 2\Delta\) is Chorus’s totality latency (by [prop:chorus-totality]), which enters the argument because completions within Cadence are Chorus finalizations. This is more than the orchestrator’s totality property demands — that property asks only that an opening eventually reach every correct validator — but we prove the sharper \(\Delta_{\mathsf{tot}}\) bound because the recovery proof later relies on it, not merely on eventual agreement about which slots are opened.

Before the formal argument, we sketch its shape, as the proof proceeds by an intricate recursion over the windows. The crux is a feedback loop between opening and completing: a correct validator opens the slots of window \(\omega\) only once enough of the earlier windows have completed, so the openings of window \(\omega\) are synchronized across correct validators — within \(\Delta_{\mathsf{tot}}\) of one another — only if the completions of the earlier windows are; and completions, in turn, are synchronized only for slots whose openings were already synchronized. We untangle this circularity by induction on the window number, through a single per-window guarantee — that the completions of a window’s slots reach all correct validators within \(\Delta_{\mathsf{tot}}\) — that ratchets forward: the first window satisfies it outright, and if every window before \(\omega\) satisfies it, then the openings of window \(\omega\) are \(\Delta_{\mathsf{tot}}\)-synchronized, which in turn makes window \(\omega\) satisfy the guarantee. Chaining this implication across all windows yields \(\Delta_{\mathsf{tot}}\)-totality for every slot.

Let \(\mathcal{W}\) denote the set of windows entered by at least one correct validator. By [prop:acs-fate-range] and the agreement property of the underlying ACS instances, any two correct validators that both enter a window \(\omega\) agree on its slot set, i.e., \(\mathsf{slots}_i(\omega) = \mathsf{slots}_j(\omega)\). We may therefore drop the subscript and write \(\mathsf{slots}(\omega)\) for this common set throughout the rest of the proof.

We name the aforementioned per-window guarantee — a window’s totality precondition — explicitly.

We first show that window \(1\) satisfies the totality precondition.

We now turn to the remaining windows. For a window \(\omega > 1\), we cannot guarantee \(\Delta_{\mathsf{tot}}\)-synchronized openings outright; instead, the following proposition establishes them conditionally, assuming that every earlier window already satisfies the totality precondition.

The previous proposition synchronizes the openings of a window’s slots; the next one closes the loop, showing that synchronized openings yield synchronized completions — precisely what a window needs to satisfy the totality precondition.

We are now ready to prove that Conductor satisfies \(\Delta_{\mathsf{tot}}\)-totality when run within Cadence.

Combining the two halves of the recursion — that openings are \(\Delta_{\mathsf{tot}}\)-total and that \(\Delta_{\mathsf{tot}}\)-total openings yield \(\Delta_{\mathsf{tot}}\)-total completions — we obtain that completions, too, propagate within \(\Delta_{\mathsf{tot}}\) for every slot.

13.2.0.6 Recovery.

Finally, we turn to Conductor’s recovery property, which we also show Conductor satisfies when run within Cadence. To this end, we first bound how long a correct validator takes to complete a slot it opens, in terms of Chorus’s termination latency \(\ell_{\mathrm{\small chorus}}\) — the parameter for which, if all correct validators start participating by some time \(t'\), then all finalize by time \(\max(t', \mathrm{GST}) + \ell_{\mathrm{\small chorus}}\).

Recall that \(\Phi_{oc} = \ell_{\mathrm{\small chorus}} + \Delta_{\mathsf{tot}}\), which is exactly the open-to-complete bound established just above ([prop:conductor-open-to-complete]). Throughout the remainder of this part of the proof, we focus exclusively on Conductor when run within Cadence. To avoid clutter, we leave this qualification implicit rather than restating it at every step. We now prove that every correct validator eventually enters every window.

Having established that every correct validator enters every window, we now turn to timing: we show that, once the network stabilizes, correct validators enter each window at a precise time. These timing guarantees rely on the protocol parameters being configured to satisfy the following constraints (lines [line:assumption-one]–[line:assumption-four]):

Recall that \(p \in \{0, \dots, W-1\}\) is the readiness threshold, \(W \in \mathbb{N}_{\geq 1}\) the window size, \(\ell\) the latency of the ACS primitive, \(\Phi_{oc} = \ell_{\mathrm{\small chorus}} + \Delta_{\mathsf{tot}}\) the open-to-complete delay, and \(\Delta\) the known upper bound on message delays after \(\mathrm{GST}\). Intuitively, these constraints ensure that all the work associated with a window, namely proposing to the next ACS instance, deciding, and completing its slots, fits within the window’s time span of \(W\tau\), so that one window follows the next without gaps once the network is synchronous.

Before proving the timing guarantee, we set up notation for the slots and starting times associated with each window. Note that, by [prop:enters-every-window], every correct validator enters every window \(\omega \in \mathbb{N}_{\geq 1}\), so \(\mathsf{slots}_i(\omega)\) is defined for every correct validator \(p_i\) and every window \(\omega\). By [prop:acs-fate-range], for every window \(\omega\), the common set \(\mathsf{slots}(\omega)\) consists of exactly \(W\) slots with consecutive slot numbers. For every window \(\omega\) and index \(x \in [1, W]\), we write \(\mathsf{slot}(\omega, x)\) for the \(x\)-th slot of \(\mathsf{slots}(\omega)\), ordered by slot number. Then, for every window \(\omega\) and index \(x \in [1, W]\), we denote by \(\mathcal{T}_x(\omega)\) the starting time of \(\mathsf{slot}(\omega, x)\), that is, \[\mathcal{T}_x(\omega) \;=\; s.\mathsf{deadline}- \Delta, \quad \text{where } s = \mathsf{slot}(\omega, x).\] Since consecutive slots are separated by exactly \(\tau\) time units, \(\mathcal{T}_x(\omega) = \mathcal{T}_1(\omega) + (x - 1)\tau\), for every \(x \in [1, W]\). Finally, we call a window \(\omega\) a post-\(\mathrm{GST}\) window if and only if \(\mathcal{T}_1(\omega) \geq \mathrm{GST}\), and a pre-\(\mathrm{GST}\) window otherwise.

We now show that every correct validator enters each window within \(\Delta_{\mathsf{tot}}+ \ell\) of its scheduled start (or of \(\mathrm{GST}\), if that is later).

We now establish the key timing invariant underlying recovery: if every correct validator enters a post-\(\mathrm{GST}\) window \(\omega\) by \(\mathcal{T}_p(\omega)\), then every correct validator opens window \(\omega + 1\) “on time” and there are no “gaps” between the two windows.

Next, we prove that from the second post-\(\mathrm{GST}\) window, the protocol “runs smoothly”.

[prop:smooth-windows] tells us that the protocol runs smoothly from the second post-\(\mathrm{GST}\) window onward: there are no gaps between consecutive windows, and every slot is opened exactly at its starting time. It remains to understand when this smooth regime begins, i.e., when the second post-\(\mathrm{GST}\) window can start. To this end, we bound when the first post-\(\mathrm{GST}\) window can arise.

We are finally ready to prove Conductor’s recovery.

References↩︎

---

1. Author order: alphabetical by last name.↩︎

2. Because existing blockchain protocols recognize this unique role of the leader, they typically rotate that role across blocks, thereby spreading power among validators over time; nonetheless, even short-lived control can enable rent extraction.↩︎

3. DAG-based consensus protocols also have multiple proposers, but these designs provide different properties since there can exist an advantage in conditioning one’s proposal on the others’.↩︎

4. We offer chain certificates as a practical add-on ([sec:chain-certification]), but they are not required for consensus.↩︎

5. If each proposal builds on an uncommitted parent, blocks that merge several proposals may build on different parents, so the merged block has no unique parent for the next block to chain to.↩︎

6. We occasionally refer to a slot’s starting time, which we define as its deadline minus \(\Delta\), where \(\Delta\) is the known bound on message delays after \(\mathrm{GST}\).↩︎

7. Henceforth, we write “censorship resistance” to mean this stronger notion when clear from the context.↩︎

8. This framework is not specific to the MCP problem: it supports “slot-based” consensus in general and may be of independent interest. We nevertheless present it through the lens of MCP, which is the focus of this work.↩︎

9. Validators also ignore chunks that arrive too long before \(D_s\), so a Byzantine proposer cannot flood them with proposals for far-future slots.↩︎

10. For this to pin the equivocation on proposer \(p_j\), each fallback-yes vote must carry the Merkle root as signed by \(p_j\); two such votes on different roots then amount to \(p_j\)’s own signatures on conflicting roots.↩︎

11. A ciphertext that does not decrypt to a well-formed proposal is discarded in the same way; this check, too, is deterministic, so all correct validators agree.↩︎

12. For safety, \(f+1\) signatures would suffice, since at least one is then from a correct validator; we use \(2f+1\) so that a supermajority signs, keeping the network in sync.↩︎

13. The fast path can also be derailed by equivocation, a proposer sending conflicting proposals to different validators; but two such signed proposals already form an equivocation certificate, so that case carries its own proof. We therefore set it aside and focus on partial dissemination, assuming below that no proposer equivocates.↩︎

14. In practice, this should be “good enough”: the actual number of faults is typically far below the worst-case bound \(f\) the protocol provisions for.↩︎

15. Since each positive vote carries the proposal’s Merkle root signed by the proposer, a single positive vote already proves that the proposer issued a proposal.↩︎

16. We assume that, in practice, chunk dissemination is decoupled from the more latency-critical vote dissemination: votes are sent first, before chunk re-dissemination begins.↩︎

17. In practice, the protocol instantiates this step using Deterministic RaptorCast [14].↩︎

18. Conductor does rely on Chorus for some of its own guarantees — namely its totality and recovery (see 14) — but the integrity property we invoke here holds unconditionally and depends on nothing about Chorus. Hence, there is no circularity.↩︎