Cadence: Extreme Pipelining with Multiple Concurrent Proposers Kushal Babel, Fatima Elsheimy, Lioba Heimbach, Mohammad Mussadiq Jalalzai, Tobias Klenze, Jovan Komatovic, Jason Milionis, Mike Setrin, and Victor Shoup ⋆
arXiv:2607.02275v1 [cs.DC] 2 Jul 2026
Category Labs
Abstract. We present Cadence, a Byzantine fault-tolerant multi-proposer consensus protocol with arbitrarily low block intervals, optimal resilience, and optimal fast-path latency. Cadence divides time into equally spaced slots, one block per slot, each finalized in its own consensus instance. Blocks do not build directly on their predecessor, which lets these instances run independently, so none waits for an earlier block to finish or even to propagate over the network; we call this extreme pipelining, and it decouples the block interval from network latency. Cadence also removes the single-leader monopoly over transaction inclusion and ordering: under multiple concurrent proposers (MCP), several validators propose for each block, and it guarantees that, under synchrony, a transaction a correct proposer includes cannot be censored or deferred to a later block (shortterm censorship resistance), and that no proposer can craft its proposal in reaction to the others’ (hiding). To realize extreme pipelining, we introduce a framework that turns any one-shot consensus meeting our slot-consensus specification into a multi-shot protocol with arbitrarily low block intervals. It is general and of independent interest. We instantiate it for the MCP setting with two protocols of our own: Chorus, an MCP slot consensus whose fast path finalizes a block in an optimal three communication rounds, with speculative finality one round earlier, and Conductor, an orchestrator that opens slots at an even cadence in normal operation, and more slowly under asynchrony to keep the number of open slots bounded. To our knowledge, Cadence is the first MCP protocol to provide short-term censorship resistance and hiding at the fast-path latency of single-leader consensus. We prove safety, liveness, short-term censorship resistance, and hiding under partial synchrony with optimal resilience (n = 3f + 1). Beyond the theory, we address the practical considerations of deploying Cadence and evaluate its latency in simulation: over Monad mainnet’s 200 globally distributed validators with five concurrent proposers per slot, the finalization latency averages 219 ms (167 ms to speculative finality), and at a 100 ms block interval, a transaction waits on average only 50 ms to enter a proposal.
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.1 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: Shortterm 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 ⋆ 1
Author order: alphabetical by last name. 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.
1
way, a proposer cannot condition their proposal’s contents on the other ones, and proposals are truly simultaneous.2 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. 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 Figure 1: Chorus, a single-shot MCP consensus run for each slot, and Conductor, which schedules the slots, normally at a regular interval τ (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 (Section 6.3). Those same low block intervals keep economic ticks short, since transactions enter proposals frequently (Requirement 3). 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 chain3 : 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 ∆. Removing this dependency on the previous block lets the block interval drop below ∆, 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.4 Extreme pipelining, however, makes the per-slot consensus 2
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’. 3 We offer chain certificates as a practical add-on (Section 6.3), but they are not required for consensus. 4 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.
2
Conductor deadlines every τ
τ s
Bs
s+1
Bs+1
s+2
Bs+2
s+3 concurrent proposals
independent Chorus instances
Bs+3
deadline Ds
fast finalize
fallback finalize
B
block
Fig. 1: Cadence architecture. In normal operation, Conductor schedules consecutive slot deadlines τ apart. Each deadline belongs to an independent single-shot Chorus instance. Here every slot has three concurrent proposers; on finalizing, the slot emits one slot-numbered block that merges the proposals it includes. In slot s+1 the last proposer disseminates only partially (dotted), forcing the slower fallback path, so a later fast slot produces its block first; the ledger order is still determined by slot number. 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 τ , 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 τ apart and known at least ∆ in advance (recovery). 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 τ adaptively does not affect the slot consensus. Conversely, instantiating the slot consensus with a 5f +1 3
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 (Section B). 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 (Section 6) and work through several further practical considerations (Section 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 (Section 8). 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. Paper organization. The rest of this paper is organized as follows. We present the problem and our design informally: the MCP problem (Section 2), our extreme-pipelining framework (Section 3) and its components in Cadence: Chorus (Section 4) and Conductor (Section 5). We then discuss deploying Cadence as part of a blockchain (Section 6) and further practical considerations (Section 7), evaluate its latency (Section 8), and review related work (Section 9). The appendix gives the formal treatment: the formal problem definition (Section A), the Cadence framework and its correctness (Section B), Chorus (Section C), and Conductor (Section D).
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 (GST), after which it stabilizes and delivers messages within a known bound ∆. Throughout, δ ≤ ∆ denotes the actual network delay after 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: – a fixed set of k proposers, the validators entitled to propose that slot’s contents; – a deadline (a point in global time), the cut-off by which proposers must ensure that validators have received sufficient information about their proposals for casting votes; the deadline is not hardcoded, but set by the protocol itself.5 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. 5
We occasionally refer to a slot’s starting time, which we define as its deadline minus ∆, where ∆ is the known bound on message delays after GST.
4
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 G such that both hold from time GST + 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 GST + 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.6 – 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 GST+G onwards, the slots come “without gaps”: successive slots follow one another promptly, with no undue gaps between their deadlines. Figure 2 illustrates the problem together with these five guarantees.
slot s
one block per slot
proposer p1 block Bs proposal of p1
proposer p2
proposal of p2
proposer p3 (Byzantine)
τ
grace period G
B4
···
B3
B3
B2
B2
B1
B1
ledger of validator 1
ledger of validator 2
common prefix
τ time
GST
Ds−1
Ds
Ds+1
Guarantees Safety: the ledgers never fork — at any time, one is a prefix of the other (dashed box). Liveness: every slot eventually adds its block to every honest ledger (upward arrows). Censorship resistance: for slots past the grace period G, an honest proposal always enters the block (see Bs ). Hiding: proposals stay concealed until it is too late to react to them (locks). Eventual stability: after the grace period G, deadlines come “without gaps” (in Cadence: consecutive deadlines spaced by exactly τ ).
Fig. 2: The MCP problem and its 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 GST, but only after a grace period G following it. In other words, slots whose starting time is within the grace period need not enjoy censorship resistance. 6
Henceforth, we write “censorship resistance” to mean this stronger notion when clear from the context.
5
This grace period is not incidental : our formal definitions (Section A) parametrize the guarantees by its length, and the shorter the 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 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 τ -spaced, for a fixed duration τ : from some point on, the deadlines of consecutive slots are separated by exactly τ .
3
Our Extreme-Pipelining Framework
We now describe our extreme-pipelining framework,7 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. Interface & Guarantees. The interface of slot consensus is simple: the slot’s proposers propose their proposals as input, and each validator may eventually finalize a block for the slot as output. Roughly speaking, slot consensus is required to satisfy the following four guarantees: – Agreement. Honest validators never finalize conflicting blocks for the slot. – Termination. Every honest validator eventually finalizes a block for the slot. – Proposal inclusion. If the slot’s starting time (the slot’s deadline minus ∆) is past GST, the finalized block contains the proposals of all honest proposers that proposed by the slot’s starting time. – Hiding. The proposals stay concealed until it is too late for a faulty proposer to react to them: it is impossible for a faulty proposer to first learn the honest proposals and then, equipped with that knowledge, craft a new proposal of its own that still gets included in the finalized block. 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. Figure 3 collects the interface and the guarantees of slot consensus in one place. 7
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.
6
proposer p1
proposer p2
input: proposals
output: finalized block
propose(prop 1 )
finalize(Bs )
propose(prop 2 )
finalize(Bs )
validator v2
Slot Consensus for slot s
. . . proposer pk
validator v1
propose(prop k )
. . . finalize(Bs )
validator vn
Guarantees Agreement: honest validators never finalize conflicting blocks — all finalize the same Bs . Termination: every honest validator eventually finalizes a block for the slot. Proposal inclusion: after GST, an honest proposal submitted by the slot’s starting time enters Bs . Hiding: proposals stay concealed until it is too late for a faulty proposer to react to them.
Fig. 3: The slot consensus primitive for a slot s: its interface and its guarantees. The slot’s proposers submit their proposals as input (violet arrows), and every validator eventually finalizes a block for the slot as output (green arrows). 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. Interface & Guarantees. Like slot consensus before it, the orchestrator exposes a simple interface. As input, a validator notifies the orchestrator that a slot is complete, meaning that the validator’s work within that slot is done; in our framework, as we show in Section 3.3, this happens once the slot’s block is finalized. As output, the orchestrator 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: – Boundedness. The orchestrator should keep validators from running arbitrarily far ahead: it imposes a fixed limit on how many slots a correct validator may have underway at any one time — slots whose deadlines it has already received but has not yet completed. It enforces this limit through its output, withholding the deadlines of new slots and throttling the pace until the validator reports that enough earlier slots are complete. Crucially, this limit need not be finite: taking it to be infinite imposes no constraint at all, recovering the most general orchestrator, which may let validators run arbitrarily far ahead. A finite limit is the stronger guarantee, and is what keeps each validator’s resource footprint in check. – Recovery. Once the network stabilizes (some grace period after GST), the orchestrator must schedule the slots “properly”, and this requirement is twofold. First, the schedule must be steady: the deadlines of consecutive slots are spaced by exactly the fixed amount τ (the same τ with which we capture eventual stability in Section 2). Second, the schedule must be known in advance: every correct validator learns each deadline (i.e., receives it as the orchestrator’s output) at least ∆ time before the deadline itself. The first half is what keeps the slots coming without gaps; the second is what gives proposers room to act: in our framework, as we show in Section 3.3, it ensures that every honest proposer issues its proposal on time, i.e., by the slot’s starting time. Figure 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 net7
input: complete notifications
output: deadlines of new slots
complete(s)
schedule(D ′ ) s
validator v1
schedule(D ′ ) s
complete(s)
validator v2
Orchestrator
. . .
validator v2 . . .
schedule(D ′ ) s
complete(s)
validator vn
validator v1
validator vn
Guarantees Boundedness: at any moment, each honest validator has only a bounded number of slots underway — scheduled, but not yet complete. Recovery: after the network stabilizes (some “short” grace period after GST), consecutive deadlines are spaced by exactly τ , and every honest validator learns each deadline at least ∆ time before the deadline itself.
Fig. 4: The orchestrator primitive: its interface and its guarantees. Validators notify the orchestrator that slots are complete as input (violet arrows), and the orchestrator schedules new slots by announcing their deadlines as output (green arrows). work 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 Section B.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 τ -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 τ , 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 ∆ 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; Figure 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 (∆ 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. 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 τ , 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. 8
Extreme-Pipelining Framework deadline D1 complete slot 1
deadline D2 complete slot 2
deadline D3
Slot Consensus for slot 1
finalize B1
Slot Consensus for slot 2
finalize B2
B1
B2
Slot Consensus for slot 3
Orchestrator deadline D4
Slot Consensus for slot 4
complete slot 4
deadline D5
finalize B4
B4
Slot Consensus for slot 5 . . .
Fig. 5: Our framework as the composition of its two building blocks: a single orchestrator, and one slot consensus instance per slot. The orchestrator schedules slots by setting their deadlines: it announces the deadline Ds of each slot s (teal arrows), thereby spawning a slot consensus for it. Each slot consensus independently finalizes a block (green arrows). The instances run concurrently and may finalize out of order: here, slot 4 has already finalized its block B4 , even though the earlier slot 3 (and the later slot 5) is still in progress (dashed borders). Upon a finalization, the validator notifies the orchestrator that the slot is complete (orange arrows), which may let the orchestrator schedule further slots; the finalized blocks are then appended to the ledger in slot-number order. 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 τ 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. Proof Sketch. Let us now explain why our framework solves the MCP problem as defined in Section 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 G following GST, the recovery property of the orchestrator guarantees that every honest validator learns each upcoming deadline at least ∆ 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. 9
Eventual stability is exactly the first half of the recovery property: once the network stabilizes (from time GST + G onward), the orchestrator spaces consecutive deadlines by exactly τ , 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 singleleader 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). Cryptography. Chorus relies on a handful of standard cryptographic primitives, which we use as follows. – Collision-resistant hashing, used to build Merkle commitments: a short root that binds a whole sequence of values, while any single value can later be proven to be among them with a logarithmicsize proof. – Digital signatures that can moreover be aggregated, so that many signatures on the same message collapse into a single short multi-signature. – Erasure coding, which encodes a piece of data into n chunks such that any f + 1 of them suffice to reconstruct the original data. – A per-slot threshold encryption scheme, which encrypts a message so that it can be decrypted only once f + 1 validators release their decryption shares for that slot. The shares are bound to the slot itself, not to any individual ciphertext, so a single set of f + 1 shares opens every message encrypted for that slot. 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 (Figure 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 Section 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 Section C. With several proposers in a slot, this object of agreement grows into a vector of such roots: 10
Merkle root
r (3) build Merkle tree over the chunks h12
plaintext proposal M
(1) encrypt
h34
(2) encode
encrypted proposal C
c1
c2
c3
c4
n chunks, one per validator (any f + 1 recover C)
Fig. 6: From a plaintext proposal to its Merkle root, step by step. 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. – For a positive entry (one carrying a Merkle root), the certificate is a proof of availability, attesting that the data behind the root is available: every honest validator can retrieve it and arrive at the same outcome, either reconstructing the committed proposal in full, or deterministically concluding that its encoding is broken (the chunks are inconsistent); crucially, whichever of the two it is, all honest validators conclude the same. – For a negative entry, the certificate is instead a proof that the proposer’s proposal is correctly excluded, for instance because the proposer failed to disseminate it on time. We call this vector of certified entries a meta-block (Figure 7): one entry per proposer, each a Merkle root or the empty value ⊥. 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 ⊥ 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 Section 4.4. meta-block proposer 1
proposer 2
proposer 3
proposer 4
r1
r2
⊥
r4
π1 : data available
π2 : data available
π3 : correctly excluded
π4 : data available
deterministic
block B
Fig. 7: A meta-block, the object Chorus agrees on. Once it is agreed upon, the slot’s block follows with no further agreement: each validator independently recovers the proposal behind every positive entry (discarding any invalidly encoded one) and assembles them into the same well-defined block (see Section 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. 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 11
of Figure 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 Ds − ∆, 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 pj : if it has received a valid chunk from pj , carrying pj ’s Merkle root rj , it broadcasts a positive vote ⟨yes, s, pj , rj , σ⟩, where σ is its signature on ⟨yes, s, pj , rj ⟩, so that 2f + 1 such votes can later be combined into a single certificate on rj . 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 Section 4.3. If, instead, no valid chunk from pj arrived by the deadline,8 the validator broadcasts a signed negative vote ⟨no, s, pj , σ⟩, where σ is now its signature on ⟨no, s, pj ⟩. Crucially, as already noted in Section 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 rj 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 Section 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 rj and, as discussed above, to either reconstruct the proposal in full or unanimously deem it invalid (see Section 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. Figure 8 traces this communication pattern for a slot with two proposers. How Fast is the Fast Path? As we emphasized in Section 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 GST, the fast path finalizes in just two voting rounds, by time D + 2δ, where D is the slot’s deadline and δ ≤ ∆ 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. 8
Validators also ignore chunks that arrive too long before Ds , so a Byzantine proposer cannot flood them with proposals for far-future slots.
12
fast meta-block proposer 1
proposer 2
r1
⊥
π1 = 2f +1 signatures on r1
2f +1 no certificate
Validator 1 proposer p1
Legend chunk dissemination (encrypted proposal) silent proposer: no chunk received
Validator 2 proposer p2 (silent)
round-1 vote (per proposer) chunk attached to the round-1 vote decryption share attached to the vote
Validator 3
fast vote (round 2) build fast meta-block, speculatively finalize finalize on 2f +1 fast votes
Validator 4
encrypt, then disseminate (before deadline D)
deadline D: round-1 vote (per proposer)
build metablock; spec. finalize; fast vote
collect 2f +1 fast votes, then finalize
Fig. 8: The Chorus fast path for a slot with two proposers p1 and p2 (n = 4, f = 1). Proposer p1 disseminates its (encrypted) proposal as one chunk per validator (orange), while p2 stays silent (gray, dashed). At deadline D, each validator broadcasts one vote per proposer (blue, dashed), ⟨yes, r1 ⟩ for p1 and ⟨no⟩ for p2 , carrying along the chunk it received (small squares) and its decryption share (diamonds). On 2f + 1 matching votes per proposer, it builds the fast meta-block (r1 with its 2f + 1-yes certificate for p1 , ⊥ with its 2f + 1-no certificate for p2 ), casts a fast vote (green), and, as we explain later in this subsection, can already speculatively finalize the block (violet nodes). A second round of 2f + 1 fast votes then finalizes the meta-block’s entries (green nodes). 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 Section 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. 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. Second, it votes on each proposer separately. For a proposer pj , it checks whether it has collected at least f + 1 yes votes on the same Merkle root: – If it has, it can recover pj ’s proposal on its own: recall that each yes vote carries its sender’s chunk, and any f +1 chunks suffice to reconstruct the proposal. (This is exactly why, in the first round, every positive vote carried its chunk.) To be sure the recovered data is genuine, the validator re-encodes it and checks that this reproduces the same Merkle root. If it does, it broadcasts a fallback-yes vote signing that root. – Otherwise (there are no f + 1 yes votes on a common root, or the re-encoding yields a different root), it broadcasts a fallback-no vote for pj . 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 13
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 Figure 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: – At least one fast vote is received in the second voting round. In this case, the validator adopts the fast meta-block that vote carries and proposes it to the fallback agreement. (Note that any validator that built a fast meta-block at the end of the first voting round holds its own fast vote, so it always falls into this case and proposes that fast meta-block.) – All 2f + 1 messages are fallback votes. The validator instead assembles a fallback meta-block, a second kind of meta-block alongside the fast one, and proposes it to the fallback agreement. We now describe how a fallback meta-block is built. The validator first aggregates the 2f + 1 received no-fast-votes into a single certificate; by quorum intersection, the mere existence of this certificate proves that no one could have finalized on the fast path. It then fills in one entry per proposer pj : (i) if it holds f + 1 fallback-yes votes on the same root r, then pj ’s entry is that root r, certified by those f + 1 fallback-yes votes; (ii) if it sees two fallback-yes votes on different roots, then pj ’s entry is ⊥, certified by those two conflicting votes as an equivocation proof;9 (iii) otherwise, pj ’s entry is ⊥, certified by f + 1 fallback-no votes. In short, the fallback meta-block bundles a single 2f + 1 no-fast-vote certificate with, for each proposer, one of three entries: an f + 1 fallback-yes certificate on a root, an equivocation proof, or an f + 1 fallback-no certificate. 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. Figure 9 traces the whole fallback path end to end.
Validator 1
Legend
Validator 2 Black-box fallback agreement
no fast meta-block built
FINALIZE
Validator 3
no-fast-vote + fallback votes propose to fallback agreement fallback agreement finalizes
Validator 4
end of the first voting round
collect 2f +1 second-round votes; obtain a fast or a fallback meta-block
propose to fallback agreement
Fig. 9: The Chorus fallback path (n = 4, f = 1). Each validator broadcasts either a fast vote (see Section 4.2) or, failing that, a no-fast-vote together with a per-proposer fallback-yes/fallbackno vote (violet, dashed). It then proposes a meta-block (fast or fallback; orange) to the slot’s single black-box fallback agreement, which finalizes one (green) as the slot’s.
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 9
For this to pin the equivocation on proposer pj , each fallback-yes vote must carry the Merkle root as signed by pj ; two such votes on different roots then amount to pj ’s own signatures on conflicting roots.
14
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 ⊥ (Figure 10), subject to the following two guarantees: (i ) all correct validators recover the same proposal vector, each entry being either the same recovered proposal at every validator or discarded at every validator (the consistency of Section 4.1); (ii ) an honest proposer’s proposal is never lost: if B certifies the proposal Pi of a correct proposer pi (i.e., B contains the root committing to the encryption of Pi ), then every correct validator recovers exactly Pi in its proposal vector. Both follow from how a single positive entry of B, committing to a root r, is recovered. Recovery Procedure. If B is a fast meta-block, then such an entry carries a 2f + 1 yes certificate (see Section 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 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 D and checks that this reproduces exactly r. If it does, the encoding is valid and the validator decrypts D with the slot’s f + 1 decryption shares (released at the slot’s deadline) to obtain the plaintext proposal.10 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 Section 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 (Section 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 D behind r. Recovery then proceeds exactly as in the fast case: re-encode 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 Section 4.1, achieved through Chorus’s certificate over the disseminated root. Whether B is fast or fallback, recovery provides both guarantees: (i ) holds because whether a proposal is discarded depends only on r: it is discarded if and only if the chunks committed under r do not form a valid erasure encoding, regardless of which chunks a validator happens to collect. When they do form one, every correct validator decodes the same ciphertext and, decryption being deterministic, recovers the same plaintext. When they do not, every correct validator discards the proposal: even one whose own chunks were individually valid finds, on re-encoding, that they fail to reproduce r, since validity is a property of the whole committed set, not of the chunks one happened to receive. (ii ) holds because a correct proposer encrypts a valid proposal and encodes the ciphertext into a valid erasure encoding; the chunks committed under r therefore re-encode to r at every correct validator, so the proposal is always recovered and never discarded. Proposal Recovery Adds No Latency. Proposal recovery runs in parallel with voting, so it adds no latency. The latency claims of Section 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 10
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.
15
recovered proposals
meta-block B r1
decodes correctly
P1
2f +1 signatures on r1 , or f +1 fallback-yes on r1
r2
decodes correctly
P2
2f +1 signatures on r2 , or f +1 fallback-yes on r2
⊥
excluded
2f +1 no, or f +1 fallback-no
r4
⊥
decodes incorrectly
⊥
2f +1 signatures on r4 , or f +1 fallback-yes on r4
recovering a positive entry with root rj : collect f +1 chunks
decode to ciphertext D
re-encode D to root r ′
yes
Pj = dec(D)
no
⊥
r ′ = rj ?
Fig. 10: Recovering the proposals from a (fast or fallback) meta-block. (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 (Section 4.3), so every correct validator holds its chunk for r; once the fallback meta-block forms, each broadcasts that chunk, and one ∆ 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 Figure 3). 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. 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. Proposal Inclusion. Consider an honest proposer that submits its proposal on time (∆ 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 16
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. 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. Safety of speculative finalization. We claimed in Section 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 pj a different proposal in the slot’s block. Since B is a fast meta-block, it backs pj ’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: – Conflicting roots. Say B records a Merkle root r for pj while B ′ records a different root r′ . A positive entry always rests on first-round yes votes for its root — 2f + 1 of them in a fast meta-block, and the f +1 that every fallback-yes requires its caster to have collected. Since (2f +1)+(f +1) > n = 3f +1, the yes-voters for r and those for r′ must overlap; as a correct validator yes-votes a single root, the validator in the overlap signed both — an equivocation. – Inclusion vs. exclusion. Say instead that B includes pj under a root r while B ′ leaves pj out. Including pj rests on 2f + 1 first-round yes votes on r, since B is a fast meta-block. Excluding pj requires a negative entry carrying f + 1 fallback-no votes, at least one of them from an honest validator — and an honest fallback-no is cast after its sender has collected f + 1 first-round no votes. Since (2f + 1) + (f + 1) > n = 3f + 1, the two sets overlap, and the validator in the overlap cast both a yes on r and a no for pj in the first round — contradictory votes for the same proposer, once again an equivocation. (There are two further ways an honest validator casts a fallback-no for pj : it gathers f + 1 yes votes for a root r whose chunks fail to re-encode to r, or it receives conflicting yes votes and never gathers f + 1 on any single root. Either way the proposer is the culprit — committing to an invalidly encoded root or disseminating several distinct proposals — misbehavior all the same.)
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 τ apart, where τ 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, . . . , W , window 2 is slots W + 1, . . . , 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 ω + 1 is scheduled only once correct validators report that every slot of windows 1, . . . , ω − 1 and the first p slots of window ω are complete. This is what keeps the number of open slots bounded as window ω + 1 is withheld until the first p slots of window ω are complete. Recall the two parameters of Conductor: the window size W and the threshold p ∈ {0, . . . , W − 1}. We now describe the protocol from the perspective of a single correct validator pi ; recall that the validators’ clocks are synchronized, so they all share a single global timeline. At genesis, pi schedules window 1 by issuing its slots’ τ -spaced deadlines: slot 1 at ∆ (so its starting time is ∆ − ∆ = 0), slot 2 at ∆ + τ , and so on up to slot W at ∆ + (W − 1)τ . From then on, the only input that drives Conductor is the completion of slots. (In Cadence, as discussed in Section 3.3, pi marks a slot complete once it has finalized that slot’s block.) 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 ω to ω + 1, works the same way (up to one minor change that we flag below). 17
As soon as pi has completed all of the first p slots, it reads the current time T and computes a proposed deadline for the first slot of window 2; the remaining slots of window 2 are then simply τ -spaced after it, so this single deadline fixes the whole window. This is only pi ’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 pi forms its proposal. Validator pi forms its proposed deadline as follows (see Figure 11): – If T is earlier than the deadline of window 1’s last slot (slot W ) — i.e., pi completed the first p slots before slot W ’s deadline had even arrived — then the system is keeping up, and pi proposes the deadline of slot W + 1 to be exactly τ after the deadline of slot W . In other words, pi proposes that the global cadence runs on unbroken, with no gap between the two windows. – Otherwise, the first p slots completed only after slot W ’s deadline had already passed; pi reads this as the system falling behind, and its proposed deadline for slot W + 1 is the current time T — a proposal that, being later than the cadence point, leaves a gap for the lagging slots to catch up. These two cases capture exactly what Conductor wants to achieve: it preserves the steady τ -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).
window 1 T
healthy
window 2
s1
s2
s3
∆
∆+τ
∆+2τ
s4
s5
s6
∆+3τ
∆+4τ
∆+5τ
time
τ : no gap window 1
lagging
window 2
s1
s2
s3
s4
s5
s6
∆
∆+τ
∆+2τ
T
T +τ
T +2τ
time
gap
Fig. 11: How a single validator pi computes its proposed deadline for window 2’s first slot (W = 3, p = 2). Healthy (top): no gap; lagging (bottom): gap exists. 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 (Figure 12).
proposed deadlines
common vector
p1 : e 1 e1 p2 : e 2 e2
ACS
median
e2
p3 : e 3 e4 agreed deadline of slot W +1
p4 : e 4
Fig. 12: How validators agree on the deadline (n = 4, f = 1; p4 Byzantine). An ACS instance delivers all correct validators the same vector of 2f +1 proposed deadlines, of which each correct validator takes the median as the agreed deadline e2 . Since at most f entries are Byzantine, the median always lies between the smallest and largest honest proposed deadline in the common vector. 18
Every later window is handled the same way, with the one change flagged above: pi 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 ω’s prerequisites are met — the slots of all earlier windows and the first p slots of window ω are complete — validator pi runs the same two-case computation (now against window ω’s last deadline) and agrees on it through ACS and the median. This finally yields the bound promised above: when window ω + 1 opens, only the unfinished part of window ω and the fresh window ω + 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 Section 3.2. Boundedness. We already did the counting at the end of the previous subsection: a correct validator opens window ω + 1 only once every slot of windows 1, . . . , ω − 1 and the first p slots of window ω are complete, so at most 2W − p slots are ever underway at once. Recovery. Recovery asks that, within a bounded grace period after the network stabilizes, the schedule “heals”: deadlines become τ -spaced again, with no gaps, and every correct validator learns each deadline at least ∆ in advance. We sketch why this happens within bounded time after GST. Everything hinges on one question: once the network is running smoothly (after GST), does such a “good” window leave enough time to schedule its successor before its own cadence ends? A window lasts W τ , and within it two things must happen (Figure 13). To begin, the first p slots must complete. Chorus finalizes a slot within some latency ℓChorus after GST, so every correct validator finalizes all of the first p slots by time Tp + ℓChorus — the p-th slot’s deadline Tp 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 ℓacs time, fixing the next window’s first deadline. We pick the parameters so that this whole pipeline fits inside the window, i.e., Tp + ℓChorus + ℓacs ≤ W τ . Thus, in a good window, every correct validator opens the first p slots (outputs their deadlines) by Tp and they all settle the next window’s deadline by Tp + ℓChorus + ℓacs ≤ W τ — 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.
window ω+1
window ω first p slots
gapless: τ -cadence continues time
ℓChorus Tp
ℓacs
all complete the first p slots ⇒ all propose to ACS
next deadline decided
Fig. 13: Scheduling the next window inside a “good” (post-GST) window. By time Tp + ℓChorus — the p-th slot’s deadline Tp plus Chorus’s latency (orange) — every correct validator has completed the first p slots and proposed to the window’s ACS, which then decides within a further ℓacs (blue), fixing the next window’s first deadline. Whenever Tp + ℓChorus + ℓacs ≤ W τ (shown here at the tight extreme), that deadline is fixed before the cadence ends, so window ω+1 continues the τ -cadence with no gap.
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: Section 6.1 builds valid proposals under this uncertainty, Section 6.2 turns the 19
committed entries into an execution block, and Section 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 Section 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 ξ 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 − ξ, 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 (Section 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 (Section 6.2), these are revealed, and translation re-applies the same check. Since the state reference is stale by ξ 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 − ξ to its proposal, its ticket. This certificate pins the executed state it validated against (Section 6.3). A proposer can form it only once 2f + 1 validators certify that they have executed slot s − ξ, so it cannot make a valid proposal while execution lags more than ξ slots behind: there is then no ticket to attach. This keeps proposals within ξ 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 (Section 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 − ξ, it merges the slot’s proposals into 20
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 signatures11 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, . . . , s are all committed; an execution certificate attests that slots 1, . . . , s − ξ have all been committed and executed, with its 2f + 1 signers agreeing on the resulting state root at slot s − ξ. 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 − ξ) execution certificate to its proposal as its ticket (Section 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 11
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.
21
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).12 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.13 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. 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. 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.14 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
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 ∆ is a conservative bound; a well-connected proposer reaches all validators within a smaller delay δ < ∆ of its own, so it can disseminate as late as δ 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 12
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. 13 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. 14 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.
22
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. 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. Cycles. Some blockchains decouple the on-chain economic tick from the consensus tick with cycles: onchain 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,21,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 shortterm 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 τ = 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 (Section 7.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. 23
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 (Section 6.1), and the bandwidth-induced queueing delay, which is at most a few milliseconds.15
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 [24,9,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∆. 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 ∆ itself, though not below it. We go below this bound with extreme pipelining, which achieves sub-∆ block intervals by running independent, non-chained single-shot consensus instances rather than chaining proposals at all. A similar line of work reaches sub-∆ 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 Section 7.2. 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. 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 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 GST, but may be placed at any point. In Chorus, by contrast, censorship resistance holds for all slots beyond a bounded interval following 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. 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. 15
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.
24
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. DAG-based protocols. DAG-based protocols [35,36,37,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.
References 1. Pranav Garimidi, Joachim Neu, and Max Resnick. Multiple Concurrent Proposers: Why and How. CoRR, abs/2509.23984, 2025. 2. Jason Milionis, Ciamac C Moallemi, and Tim Roughgarden. Automated market making and arbitrage profits in the presence of fees. In International Conference on Financial Cryptography and Data Security, pages 159–171. Springer, 2024. 3. Anza. Constellation. White Paper v0.9, https://anza.xyz/constellationwhitepaper, March 2026. Accessed: June 2026. 4. Jian Yin, Jean-Philippe Martin, Arun Venkataramani, Lorenzo Alvisi, and Mike Dahlin. Separating agreement from execution for byzantine fault tolerant services. In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, SOSP ’03, page 253–267, New York, NY, USA, 2003. Association for Computing Machinery. 5. Victor Shoup. Sing a song of simplex. In 38th International Symposium on Distributed Computing (DISC 2024), volume 319 of LIPIcs, pages 37:1–37:22, 2024. 6. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM (JACM), 32(2):374–382, 1985. 7. Manu Drijvers, Tim Gretler, Yotam Harchol, Tobias Klenze, Ognjen Maric, Stefan Neamtu, Yvonne-Anne Pignolet, Rostislav Rumenov, Daniel Sharifi, and Victor Shoup. A New Broadcast Primitive for BFT Protocols. CoRR, abs/2410.22080, 2024. 8. Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI ’99, pages 173–186, Berkeley, CA, USA, 1999. USENIX Association. 9. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM PODC, PODC ’19, page 347–356, New York, NY, USA, 2019. Association for Computing Machinery. 10. Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, DragosAdrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: a scalable decentralized trust infrastructure for blockchains. CoRR, abs/1804.01626, 2018. 11. Mohammad M. Jalalzai, Jianyu Niu, Chen Feng, and Fangyu Gai. Fast-hotstuff: A fast and robust bft protocol for blockchains. IEEE Trans. Dependable Secur. Comput., 21(4):2478–2493, July 2024. 12. Mohammad Mussadiq Jalalzai, Kushal Babel, Jovan Komatovic, Tobias Klenze, Sourav Das, Fatima Elsheimy, Mike Setrin, John Bergschneider, and Babak Gilkalaye. Monadbft: Fast, responsive, fork-resistant streamlined consensus, 2026. 13. Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. In Proceedings of the 19th International Conference on Distributed Computing, DISC’05, page 503–504, Berlin, Heidelberg, 2005. Springer-Verlag. 14. Category Labs. MIP-10: Deterministic RaptorCast. Monad Improvement Proposals, no. 10, April 2026. Online serial.
25
15. Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Good-case latency of byzantine broadcast: a complete categorization. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 331–341. ACM, 2021. 16. Monad Foundation. Asynchronous execution. https://docs.monad.xyz/monad-arch/consensus/ asynchronous-execution. Online; accessed 2026-04-30. 17. Category Labs. Monad initial specification proposal. https://category-labs.github.io/ category-research/monad-initial-spec-proposal.pdf. Online; accessed 2026-06-07. 18. Caspar Schwarz-Schilling, Fahad Saleh, Thomas Thiery, Jennifer Pan, Nihar Shah, and Barnabé Monnot. Time is money: Strategic timing games in proof-of-stake protocols. In 5th Conference on Advances in Financial Technologies (AFT 2023), volume 282 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. 19. Kaya Alpturer, Kushal Babel, and Aditya Saraf. Timing games in responsive consensus protocols. arXiv:2510.25144, https://arxiv.org/abs/2510.25144, 2025. 20. Amit Agarwal, Kushal Babel, Sourav Das, Babak Poorebrahim Gilkalaye, Arup Mondal, Benny Pinkas, Peter Rindal, and Aayush Yadav. Weighted batched threshold encryption with applications to mempool privacy. IEEE SP, 2026. 21. Amit Agarwal, Sourav Das, Babak Poorebrahim Gilkalaye, Peter Rindal, and Victor Shoup. Btx: Simple and efficient batch threshold encryption. Cryptology ePrint Archive, 2026. 22. Jan Bormet, Arka Rai Choudhuri, Sebastian Faust, Sanjam Garg, Hussien Othman, Guru-Vamsi Policharla, Ziyan Qu, and Mingyuan Wang. Beast-mev: Batched threshold encryption with silent setup for mev prevention. Cryptology ePrint Archive, 2025. 23. Pranav Garimidi, Joseph Bonneau, and Lioba Heimbach. On the limits of encrypted mempools. a16z Crypto Research, July 2025. 24. Dakai Kang, Suyash Gupta, Dahlia Malkhi, and Mohammad Sadoghi. Hotstuff-1: Linear consensus with one-phase speculation, 2024. 25. Dahlia Malkhi and Kartik Nayak. Extended abstract: Hotstuff-2: Optimal two-phase responsive bft. Cryptology ePrint Archive, Paper 2023/397, 2023. https://eprint.iacr.org/2023/397. 26. Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback, 2021. 27. Isaac Doidge, Raghavendra Ramesh, Nibesh Shrestha, and Joshua Tobkin. Moonshot: Optimizing chain-based rotating leader bft via optimistic proposals, 2024. 28. Nibesh Shrestha and Aniket Kate. Hydrangea++: Enhancing hydrangea with optimistic proposals. https: //supra.com/documents/hydrangea-plus-plus.pdf, 2025. 29. Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman. Shoal++: High throughput DAG BFT can be fast and robust! In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 813–826. USENIX Association, 2025. 30. Andrei Tonkikh, Balaji Arun, Zhuolun Xiang, Zekun Li, and Alexander Spiegelman. Raptr: Prefix consensus for robust high-performance bft, 2025. 31. Giulia Scaffino, Max Resnick, and Joachim Neu. Gatling: Rapid-fire consensus from parallel composition, 2026. 32. Zhuolun Xiang, Andrei Tonkikh, and Alexander Spiegelman. Prefix consensus for censorship resistant BFT, 2026. 33. Daniel Cason, Gordon Liao, Sergio Mena, Nenad Milošević, Adi Seredinschi, Alessandro Sforzin, João Sousa, and Preston Vander Vos. AMP: Arc multi-proposer protocol with bounded inclusion guarantees, 2026. 34. Quentin Kniep, Kobi Sliwinski, and Roger Wattenhofer. Solana alpenglow consensus, increased bandwidth, reduced latency. 2025. 35. George Danezis, Eleftherios Kokoris Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and tusk: A dag-based mempool and efficient bft consensus, 2022. 36. Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: Dag bft protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS ’22, page 2705–2718, New York, NY, USA, 2022. Association for Computing Machinery. 37. Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All you need is dag. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, page 165–175, New York, NY, USA, 2021. Association for Computing Machinery. 38. Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. Mysticeti: Reaching the limits of latency with uncertified dags, 2024. 39. Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, October 14-17, 2001, pages 136–145. IEEE Computer Society, 2001.
26
Organization of the Appendix This appendix gives the formal treatment underlying the body. It restates the MCP problem precisely (Section A), defines our extreme-pipelining framework and proves that it solves MCP given conforming building blocks (Section B), and then instantiates the two building blocks: Chorus (Section C) and Conductor, together with its boundedness and recovery guarantees (Section D).
A
Multiple Concurrent Proposers (MCP): Formal Problem Definition
This section gives a precise, formal statement of the MCP problem that Section 2 introduced informally.
A.1
Preliminaries
The MCP problem involves several abstract entities; we begin by introducing each of them precisely.
Slots. Each slot s carries three fields: – a number s.number, which is a positive integer; – a deadline s.deadline, which is a point in global time; and – a set of proposers s.proposers, which is a subset of the entire set of validators. 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 Section 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 ∈ N≥1 , there exists exactly one slot s with s.number = i. Moreover, deadlines respect the slot order: for any two slots s1 , s2 with s1 .number < s2 .number, we have s1 .deadline ≤ s2 .deadline. (For our extreme-pipelining framework, we additionally assume that consecutive deadlines are a fixed, known interval τ apart, with τ > 0: that is, s.deadline = s′ .deadline + τ for every slot s with s.number > 1, where s′ is the slot with s′ .number = s.number − 1.) We sometimes refer to the starting time of a slot s, by which we mean s.deadline − ∆. Moreover, we require the first slot (the slot s with s.number = 1) to have a deadline of at least ∆, 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.)
Proposals & Proposal Vectors. A proposal P carries three fields: – a slot P.slot; – a proposer P.proposer, which must be a proposer of the proposal’s slot (P.proposer ∈ P.slot.proposers); and – a payload P.payload, an arbitrary string carrying the proposal’s content (e.g., its transactions). We also introduce proposal vectors, which bundle one proposal per proposer of a slot. Concretely, a proposal vector V carries: – a slot V.slot; and – a mapping that assigns to each proposer p ∈ V.slot.proposers either a proposal or the special value ⊥ (meaning “no proposal”); we write V [p] for the proposal (or ⊥) assigned to p. We impose one constraint on the aforementioned mapping: whenever V [p] ̸= ⊥, the proposal V [p] must be p’s own proposal for that slot, i.e., V [p].slot = V.slot and V [p].proposer = p. Two proposal vectors are identical if and only if their slots are identical and their mappings are identical: V1 = V2 exactly when V1 .slot = V2 .slot and V1 [p] = V2 [p] for every proposer p ∈ V1 .slot.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. 27
Logs. A log is a (possibly empty) ordered list of proposal vectors with strictly increasing slot numbers: if V1 precedes V2 in the log, then V1 .slot.number < V2 .slot.number. For a log L, we write L.length to denote its number of proposal vectors, and L[i] for its i-th proposal vector, where i ∈ [1, L.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, L.length may be strictly less than L[L.length].slot.number. (Permitting such skips is the formal counterpart of the informal view in Section 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 Section B.1.) For a proposal vector V and a log L, we write “V ∈ L” to denote that V appears in L. Furthermore, we say that two logs L1 and L2 are consistent if and only if L1 [i] = L2 [i], for every i ∈ [1, min(L1 .length, L2 .length)]; otherwise, they are inconsistent. (Any log is consistent with the empty log.) A.2
Interface
The interface of the MCP problem is simple: – Input. For each slot s, every proposer p ∈ s.proposers holds a single proposal P for that slot (with P.slot = s and P.proposer = p). – Output. Each validator pi maintains an append-only local log, denoted log(pi ). Every correct validator initializes its local log to the empty log [] at time 0, and we write log(pi , t) for the local log of pi at time t. A.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. Safety. As in any consensus protocol, the foundational property is safety: the logs of all correct validators must be mutually consistent at all times. Definition 1 (Safety). A protocol satisfies safety if and only if, for any two correct validators pi , pj and any two times t1 , t2 , logs log(pi , t1 ) and log(pj , t2 ) are consistent. Liveness. As noted in Section A.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 GST: there exists a post-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 Section 2. Definition 2 (ℓ-Liveness). A protocol satisfies ℓ-liveness, for some time duration ℓ, if and only if, for every slot s with s.deadline − ∆ ≥ GST + ℓ and every correct validator pi , there exist a proposal vector V and a time t such that (1) V.slot = s, and (2) V ∈ log(pi , t). We underline that the parameter ℓ 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 GST, and we naturally prefer protocols that achieve a smaller ℓ. Accordingly, ℓ need not be a constant and may depend on the parameters of the model and the execution, such as n, f , ∆, and 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 ℓ that increases with GST. Short-Term Censorship Resistance. Liveness ensures that slots are not skipped indefinitely after GST, but says nothing about the content of the finalized proposal vectors: a protocol that always finalizes empty proposal vectors (assigning ⊥ 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 GST, the proposal vector finalized for s includes the proposals of all correct proposers of s. 28
Definition 3 (c-Censorship Resistance). A protocol satisfies c-censorship resistance, for some time duration c, if and only if, for every slot s with s.deadline − ∆ ≥ GST + c, every correct validator pi , and every correct proposer pj ∈ s.proposers, there exist a proposal vector V and a time t such that (1) V.slot = s, (2) V [pj ] = P , where P is the proposal of proposer pj for slot s, and (3) V ∈ log(pi , t). As with the parameter ℓ of ℓ-liveness, the parameter c measures the quality of a protocol: it bounds how quickly the proposals of correct proposers are included after 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. 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: – At the very least, such a property should imply “semantic security”, which would just say that the adversary does not learn the contents of the honest proposals before the deadline for submitting proposals passes. – Ideally, we want a stronger notion of security that captures “non-malleability”, which would say that the adversary cannot submit a proposal whose contents depend in some non-trivial way on an honest proposal. For example, suppose an honest proposal x is encrypted as y. If the encryption scheme is malleable, an adversary may be able to compute an encryption y ′ of x + 1 without ever learning what x is. Our definition of security will capture this guarantee. – The most ambitious definition of security would say that each faulty proposer gets to submit (at most) one proposal (which does not depend on the honest proposals), and does not learn the contents of the honest proposals until the set of included proposals is fully decided. While such a definition could be realized, it would add significant latency to the protocol. For that reason, we propose a somewhat weaker definition that gives the adversary the ability to (1) have faulty proposers effectively submit multiple proposals (which do not depend on honest proposals), and (2) use the contents of the honest proposals to influence the decided set of included proposals. 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 F and a simulator (a.k.a. ideal-world adversary) S. Both worlds are driven by an environment 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 S, with which 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 Z and F , while inputs from and outputs to faulty validators pass between S and F. Critically, the interface seen by the environment is the same in both worlds. It thus suffices to define the ideal functionality F corresponding to our hiding property, which we do next. We describe F for a single slot; the full functionality applies it to every slot. – Proposers, both honest and faulty, can input proposals to F, but only before the slot’s deadline. – Unlike an honest proposer, a faulty proposer may input several proposals (and not all at the same time). – When an honest proposer pi inputs a proposal to F , F informs S that pi has submitted a proposal, but divulges no information about the proposal to S beyond the identity of pi and the length of its proposal. – When the deadline passes, F gives to S the contents of all of the honest proposals. – Later, S chooses the actual set S of proposals to be included in the proposal vector, and sends this to F. The set S must be a subset of the proposals that were input to the ideal functionality, and can include at most one proposal per proposer. 29
– After sending S to F, S may then instruct F to output the proposal vector determined by S to individual validators (one at a time, in the order of its choosing). Having specified 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. Definition 4 (Hiding). A protocol satisfies hiding if and only if there exists a simulator S such that no efficient environment can distinguish the real world from the ideal world, where the ideal world is defined by the ideal functionality F described above, applied to every slot.
B
Our Extreme-Pipelining Framework: Formal Exposition
We now give the formal account of the extreme-pipelining framework, the framework we introduced informally in Section 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. B.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 Section 3.1 and Section 3.2, respectively. Slot Consensus. The slot consensus primitive is specified formally in Module 1; 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 Section 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 (Definition 4), specialized to the instance’s slot s. Orchestrator. Module 2 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 (Section 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 (Section A.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 τ -spaced deadline structure foreshadowed in Section A.1: consecutive slots’ deadlines are a fixed, known interval τ 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 30
Module 1 Slot Consensus Parameters: - s ∈ Slot Interface: - input participate(): a validator starts participating. - input abandon(): a validator stops participating. - input propose(P ∈ Proposal): a proposer submits its proposal P . - output finalize(V ∈ PVector): a validator finalizes proposal vector V . Properties: - Agreement: If a correct validator pi finalizes a proposal vector Vi and a correct validator pj finalizes a proposal vector Vj , then Vi = Vj . - Termination: If every correct validator starts participating, then every correct validator eventually finalizes a proposal vector. - Slot safety: If a correct validator finalizes a proposal vector V , then V.slot = s. - Proposal inclusion: If s.deadline − ∆ ≥ GST, a correct proposer pj ∈ s.proposers proposes its proposal P at time s.deadline − ∆, and a correct validator finalizes a proposal vector V , then V [pj ] = P . - Hiding: Hiding as in Definition 4, specialized to this instance’s single slot s.
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 pi opens a slot s, every correct validator opens exactly the same set of slots with number at most s.number. To see this, consider any slot s′ with s′ .number ≤ s.number. First, note that s′ can be opened at most once (due to the integrity property). If pi opens s′ , then by totality every correct validator opens s′ as well. Otherwise, pi skips s′ ; that is, it opens s without ever opening s′ (here, s′ .number < s.number). We argue that then no correct validator opens s′ either: suppose some correct validator pj did: by totality, pi would open s′ too, and by monotonicity — as s′ .number < s.number — it would have to do so before opening s, which is impossible, since pi opened s without ever opening s′ . In both cases, pi 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, B-boundedness, bounds how many slots may be simultaneously open but not yet completed at any given time; the second, R-recovery, bounds how long after network stabilization it takes before the orchestrator opens all upcoming slots on time. We motivate B-boundedness before stating it, since the reason to bound the open slots is memory. Memory consumption in our framework. In our extreme-pipelining framework (as we detail in Section B.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 B-boundedness property we define next — and with the very same bound B. 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 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 31
extreme-pipelining framework, since completing a slot means its proposal vector has been finalized, Bboundedness implies that every correct validator has already finalized all but the last B opened slots, yielding a complete log prefix that trails the frontier by at most B slots. Here, B ∈ N≥0 ∪ {∞}: a finite B bounds the number of simultaneously open slots, whereas B = ∞ imposes no such bound and thus captures orchestrators that open slots arbitrarily far ahead without completing earlier ones. We underline once more that 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 , ∆, and GST. 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 R-recovery if both conditions hold for every slot whose starting time is at least R after GST. Unlike B, R must be finite; but, like B, it captures protocol quality (smaller is preferable) and may be any function of the model and execution parameters.
Module 2 Orchestrator Interface: - input complete(s ∈ Slot): a validator completes slot s. - output open(s ∈ Slot): a validator opens slot s. Properties: - Totality: If some correct validator opens any slot s, then every correct validator eventually opens s. - Integrity: No correct validator opens the same slot s more than once. Moreover, no correct validator opens slot s before time s.deadline − ∆. - Monotonicity: If a correct validator opens any two slots s and s′ with s.number < s′ .number, then it opens s before opening s′ . - B-Boundedness: Let B ∈ N≥0 ∪ {∞}. For every correct validator pi and every time t, if pi has opened k slots by time t (ordered by slot number as s1 , . . . , sk ), then every sj with j ≤ k − B has already been completed by pi . - R-Recovery: Let R be a time duration. For every slot s with s.deadline − ∆ ≥ GST + R, every correct validator opens slot s and it does so at time s.deadline − ∆.
B.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 O and one slot consensus instance S[s] per slot s, and the framework is simply the glue that wires these components together. Throughout, O is assumed to achieve B-boundedness and R-recovery for some B ∈ N≥0 ∪ {∞} and some time duration R. The pseudocode is given in Algorithm 1, traced from the perspective of a correct validator pi , with a complementary visual overview in Figure 14. Protocol description. Upon starting, pi begins executing O (line 13), 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 O opens slot s (line 14), pi records s as opened and starts participating in S[s] (lines 15–17); if pi is a designated proposer (i.e., pi ∈ s.proposers), it additionally submits its proposal Ps for slot s to S[s] (lines 18–19). Whereas opening is signaled explicitly by O, 32
skipping is not: when pi opens s, it records every smaller-numbered slot it has not opened as skipped (line 16). 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 S[s] finalizing a proposal vector V , for some slot s (line 20), pi places V in a pending set (line 21), notifies O that slot s has been completed (line 22), and stops participating in S[s] (line 23). Pending proposal vectors are then appended to pi ’s local log in slot-number order: a pending proposal vector V ′ is appended (line 25) as soon as every slot with a strictly smaller number than V ′ .slot.number has already been resolved, that is, either recorded as skipped or finalized and appended to log i (line 11). This ordering condition ensures that log i is indeed a log in the sense of Section A.1: proposal vectors appear in strictly increasing order of slot number. Algorithm 1 Extreme-Pipelining Framework: Pseudocode (for validator pi ) 1: Uses: 2: Slot consensus, instances S[s], for every s ∈ Slot, parameterized by slot s 3: Orchestrator (B-boundedness, R-recovery), instance O 4: Local variables: 5: Log log i ← [] 6: Set(Slot) opened i ← ∅ 7: Set(Slot) skipped i ← ∅ 8: Set(PVector) pending i ← ∅
▷ append-only local log of pi ▷ slots opened by the orchestrator ▷ slots skipped by the orchestrator ▷ finalized proposal vectors not yet appended to log i
9: Local functions: 10: function ready to append(V ∈ PVector) → Bool: 11: return true if and only if every slot s′ with s′ .number < V.slot.number satisfies one of: (1) s′ ∈ skipped i , or (2) some proposal vector V ′ ∈ log i has V ′ .slot = s′ 12: upon starting the protocol: 13: start executing O 14: upon O.open(s ∈ Slot): 15: opened i ← opened i ∪ {s} 16: skipped i ← skipped i ∪ {s′ ∈ Slot : s′ .number < s.number and s′ ∈ / opened i } 17: invoke S[s].participate() 18: if pi ∈ s.proposers: 19: invoke S[s].propose(Ps ), where Ps is pi ’s proposal for slot s
▷ implicitly skipped slots
20: upon S[s].finalize(V ∈ PVector), for some s ∈ opened i : ▷ fires once s is opened; “early” finalizations buffered 21: pending i ← pending i ∪ {V } 22: invoke O.complete(V.slot) 23: invoke S[s].abandon() 24: upon ready to append(V ′ ∈ PVector), for some proposal vector V ′ ∈ pending i : 25: append V ′ to log i 26: pending i ← pending i \ {V ′ }
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 Modules 1 and 2. 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-concurrentproposers setting entirely: instantiating the slot consensus with a single designated proposer per slot 33
Extreme pipelining open(s1 )
S[s1 ]: Slot Consensus
finalize(V1 )
V1
complete(s1 )
open(s2 )
S[s2 ]: Slot Consensus
finalize(V2 )
V2
complete(s2 )
Orchestrator O
s3 skipped: no open(s3 ) issued
∅
open(s4 )
S[s4 ]: Slot Consensus
finalize(V4 )
V4
complete(s4 )
open(s5 )
S[s5 ]: Slot Consensus . . .
Fig. 14: Interaction between the orchestrator O and slot consensus instances S[·] in the extreme-pipelining framework (Algorithm 1). Teal solid arrows: O outputs open(s), upon which the framework invokes participate() on S[s] (and propose(·) if pi ∈ s.proposers). Implicit skip (slot s3 ): the orchestrator has no “skip” output, so a slot is skipped simply by never being opened — no open(s3 ) is issued, no slot consensus instance is spawned, and no proposal vector is produced (∅). Orange arrows: upon finalize(V ), the framework invokes complete(s) on O and abandon() on S[s]. Green arrows: S[s] outputs finalize(V ); the proposal vector is eventually appended to the local log. Slot s5 (dashed border) is still in progress. 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. B.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. Safety. We first establish that the safety property is satisfied. Lemma 1 (Safety). Algorithm 1 satisfies safety. Proof. Suppose, for contradiction, that two correct validators pi , pj and two times t1 , t2 exist such that log(pi , t1 ) and log(pj , t2 ) are inconsistent. Let k ∈ N≥1 be the smallest index at which the two logs differ, i.e., log(pi , t1 )[k] ̸= log(pj , t2 )[k]; such an index exists by the definition of inconsistency. Let V1 = log(pi , t1 )[k] and V2 = log(pj , t2 )[k]. We distinguish two possible cases: – Let V1 .slot ̸= V2 .slot. The ready to append condition (line 10) ensures that a validator appends a proposal vector for a slot only after every smaller-numbered slot is either skipped or already covered by a proposal vector in its log; hence the slot at position k is determined by how each validator resolved all preceding slots. Since both logs agree at positions 1, . . . , k − 1, the two validators resolved all those slots identically. Assume, without loss of generality, that V1 .slot.number < V2 .slot.number. Then, pi appended a proposal vector for slot V1 .slot, and so opened that slot. Validator pj , in contrast, appended a proposal vector for the higher-numbered slot V2 .slot at position k without ever appending one for V1 .slot, and so did not open V1 .slot. By the monotonicity property, having already opened the higher-numbered slot V2 .slot, pj never opens V1 .slot. This contradicts the totality property of the orchestrator O: since the correct validator pi opened V1 .slot, every correct validator — including pj — must eventually open it. 34
– Let V1 .slot = V2 .slot. Since V1 ̸= V2 while V1 .slot = V2 .slot, the two proposal vectors must differ in their mappings. Note that a validator appends a proposal vector only upon finalizing it (line 20), and by the slot safety property of slot consensus a proposal vector finalized for slot V1 .slot comes from the instance S[V1 .slot]. Thus pi and pj finalized V1 and V2 , respectively, from the same instance S[V1 .slot], contradicting its agreement property, which forbids two correct validators from finalizing different proposal vectors. ⊔ ⊓ Liveness. Next, we prove that the extreme-pipelining framework satisfies liveness. Lemma 2 (Liveness). Algorithm 1 satisfies R-liveness. Proof. Fix any slot s with s.deadline − ∆ ≥ GST + R. By the R-recovery property of the orchestrator O, every correct validator eventually opens s (line 14). By the monotonicity property of O, before opening s, every correct validator has already resolved — opened or (implicitly) skipped — every slot s′ with s′ .number < s.number. Moreover, by the totality property of O, for every slot s⋆ with s⋆ .number ∈ [1, s.number], either (1) every correct validator opens s⋆ and begins participating in the slot consensus S[s⋆ ] (line 17), or (2) no correct validator opens s⋆ , i.e., every correct validator skips it (line 16). In case (1), since every correct validator starts participating in S[s⋆ ], the termination property of S[s⋆ ] guarantees that every correct validator eventually finalizes a proposal vector for s⋆ (line 20). Inductively, starting from slot number 1, each correct validator resolves slot s⋆ (by either skipping it or finalizing and appending a proposal vector for it) before proceeding to slot s⋆ + 1: once slot s⋆ is resolved, the ready to append condition (line 11) for a proposal vector associated with slot s⋆ +1 is satisfied, and the next proposal vector can be appended (line 25). Applying this argument inductively up to slot number s.number − 1, every correct validator eventually resolves all preceding slots, at which point the ready to append condition for a proposal vector associated with slot s is satisfied. Therefore, every correct validator eventually appends a proposal vector V with V.slot = s (line 25), establishing R-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. Censorship resistance. We next prove the censorship resistance property. Lemma 3 (Censorship resistance). Algorithm 1 satisfies R-censorship resistance. Proof. Fix any slot s with s.deadline − ∆ ≥ GST + R, any correct validator pi , and any correct proposer pj ∈ s.proposers; let Ps denote pj ’s proposal for slot s. To prove the lemma, we must exhibit a proposal vector V and a time t such that V.slot = s, V [pj ] = Ps , and V ∈ log(pi , t). By the R-liveness of the extreme-pipelining framework (Lemma 2), pi eventually finalizes (line 20) and appends (line 25) a proposal vector V with V.slot = s to its local log, at some time t. By the R-recovery property of the orchestrator O, pj opens slot s at time s.deadline − ∆ (line 14) and, being a correct proposer, submits its proposal Ps to S[s] at that same time (line 19). Since s.deadline − ∆ ≥ GST and pj proposes by the slot’s starting time, the proposal-inclusion property of S[s] ensures that the proposal vector V finalized by pi satisfies V [pj ] = Ps , which concludes the proof. ⊓ ⊔ Hiding. Next, we prove hiding, which reduces to the hiding of each slot consensus instance. Lemma 4 (Hiding). Algorithm 1 satisfies hiding. Proof. A correct proposer submits its proposal for slot s solely to S[s] (line 19), and a correct validator appends a proposal vector for slot s only upon S[s] finalizing it (lines 20 and 25). Proposal contents are thus observable only through the per-slot instances, so hiding follows by composing the hiding of each. ⊔ ⊓ Bounded concurrency. Recall from Section B.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: Lemma 5 (Bounded concurrency). Algorithm 1 satisfies B-bounded concurrency. That is, for every correct validator pi and every time t, at most B slot consensus instances S[s] exist such that pi has started participating in S[s] by time t but has not yet abandoned S[s] by time t. Proof. For any slot s, validator pi starts participating in S[s] upon opening s (line 14–17), and abandons S[s] immediately after completing s (line 23). Hence, S[s] is active for pi at time t if and only if pi has opened s but not yet completed it by time t. The bound of B therefore follows directly from the B-boundedness property of the orchestrator O. □ 35
C
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 Section 4; here we give its full specification. C.1
Cryptographic Primitives
Chorus builds on several standard cryptographic primitives, whose notation we fix here. Hash function. We assume a collision-resistant cryptographic hash function H : {0, 1}∗ → {0, 1}λ . Digital signatures. Each validator pi holds a signing keypair (ski , pki ). We use the following operations: – Signi (m): On input message m, outputs a digital signature σ computed using ski . – Verifypki (m, σ): Outputs ⊤ if σ is a valid signature on m under public key pki , and outputs ⊥ otherwise. A set of signatures {σi }i∈I on a common message m can be aggregated into a short multi-signature Σ verifiable against {pki }i∈I . Erasure coding. The encrypted proposal is erasure-coded to enable distributed availability. Throughout the section, we rely on the following operations: – Encode(c): On input ciphertext c, outputs n fragments (d1 , . . . , dn ) such that any subset of at least f + 1 fragments is sufficient to reconstruct c. – Decode({di }): On input a set of fragments {di } with |{di }| ≥ f + 1, outputs the reconstructed ciphertext c, or ⊥ if decoding fails. Merkle trees. Merkle trees are used to commit to encoded payload chunks. We assume the following interface: – MerkleRoot(c1 , . . . , cn ): Outputs the root merkle root of the Merkle tree over leaves c1 , . . . , cn . – MerkleProof(i): Outputs a Merkle authentication path πi for chunk ci . – VerifyMerkle(merkle root, ci , πi ): Outputs ⊤ if πi is a valid proof that ci is a leaf in the Merkle tree with root merkle root, and outputs ⊥ otherwise. Random-oracle convention. For the simulation argument in §C.2, we model several hash functions as distinct random oracles, including the identity hash Hid , the pad-derivation hash Hpad , and the Merkle hash HMerkle . The simulator programs Hpad ; it does not program HMerkle , 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. C.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. 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 (mpk , msk ) ← Setup(1λ ),
sk id ← Extract(msk , id ),
(Z, Ckem ) ← Encap(mpk , id ),
Z ← Decap(sk id , id , Ckem ). 36
Here, Z is the KEM’s raw key and Ckem 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 Extract. A (t, n)-distributed extraction mechanism consists of algorithms (mpk , vk , st 1 , . . . , st n ) ← DSetup(1λ , n, t), σi ← ShareExtract(st i , id ),
b ← VerifyShare(mpk , vk , id , i, σi ),
sk id ← CombineExtract(mpk , vk , id , {(i, σi )}i∈I ),
|I| ≥ t.
After combining extraction shares to obtain sk id , decapsulation is the ordinary non-threshold operation. Thus extraction shares depend only on the identity id , not on any particular proposal ciphertext. Correctness requires that honestly generated and verified shares combine to the same sk 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 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 id , except with negligible probability. Equivalently, if a later layer derives a pad as a random-oracle value H(Z, . . .), 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 id , let Qid = Hid (id ) and sk id = aQid . A distributed private-key generator can Shamir-share a: server i returns the verified extraction share σi = ai Qid , and interpolation reconstructs aQid . Encapsulation chooses r at random, publishes Ckem = U = rG, and computes Z = e(Qid , aG)r . Decapsulation with the reconstructed identity secret key computes Z = e(sk id , U ) = e(aQid , 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. Encrypting proposals. For a slot s, let id s be the canonical encoding of s as an IB-KEM identity. A proposer P encapsulates to this identity, obtaining (Z, Ckem ) ← Encap(mpk , 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 = Hpad (Z, s, P, ctx). The inputs Z, s, and P are essential. The value ctx denotes any remaining public context for this encryption, and may include Ckem , protocol-version information, and deployment or chain identifiers. If the proposal payload is M , the encrypted payload is the xor mask Cpay = K ⊕ M, where Hpad 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 Hpad at the appropriate point. The object encoded for data availability contains at least (Ckem , Cpay ) 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.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. 37
Releasing the slot key. At the slot’s deadline, validators publish extraction shares σi ← ShareExtract(st i , id s ) for the slot identity. Once enough verified shares have been collected, anyone computes sk id s ← CombineExtract(mpk , vk , id s , {(i, σi )}i∈I ). The same reconstructed slot key opens all well-formed proposal encapsulations for slot s: for each decoded proposal ciphertext, parties compute Z ← Decap(sk id s , id s , Ckem ),
M = Cpay ⊕ Hpad (Z, s, P, ctx).
The released values are therefore extraction shares for the slot identity, not decryption shares tied to individual proposals. Simulation argument. We sketch why this realizes the hiding property (Definition 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 Cpay 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.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 HMerkle . 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 Hpad , it is not programmed. For each well-formed corrupt ciphertext submitted by a corrupt proposer P ′ , the simulator obtains the released slot key sk id s , decapsulates Ckem , and obtains the raw key Z. It then considers the pad-oracle point q = (Z, s, P ′ , ctx). If Hpad (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 ′ = Cpay ⊕ Hpad (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 Cpay and the desired plaintext M . It programs the corresponding pad-oracle point by setting Hpad (Z, s, P, ctx) := Cpay ⊕ 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 38
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. C.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 metablock’s entries are committed either via the fast path or via the fallback path (Phase III). Algorithm 2 implements Phase I and runs at proposers only. Algorithm 3 implements Phase II at every validator. Phase III is implemented by two modules running in parallel: Algorithm 4 aggregates proposal votes into FastQCs and runs the two-round fast commit on a fast meta-block, while Algorithm 5 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, Module 3) — 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 (Algorithm 6) provides chunk validation, ciphertext reconstruction, decryption, and proposal recovery. Modules communicate through the shared local state declared in their “Local variables” blocks (e.g., Ev (j) and pathVote are shared between the fast-path and fallback-path modules). Throughout the pseudocode, we say that pi is actively participating in s if it has invoked the slot-consensus input participate() but has not yet invoked abandon(). Dissemination & Voting Each slot s is bounded by a deadline s.deadline. Each honest proposer in s.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.deadline − ∆ (in the style of AVID [13] and DispersedSimplex [5])16 . 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. Proposal. A proposal by proposer pj in slot s is P = ⟨s, j, Payload , σ⟩, where s is the slot, j is the proposer index, Payload is the proposal’s transaction payload, and σ is pj ’s signature over ⟨s, j, H(Payload )⟩. The triple ⟨s, j, Payload ⟩ is exactly a proposal in the sense of the problem definition (Section A.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 . Chunks. To distribute the dissemination load, the proposer erasure-codes the encrypted proposal EP into n fragments d1 , . . . , dn (one per validator) and builds a Merkle tree over the leaves H(1, d1 ), . . . , H(n, dn ), yielding a root ρ. 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, ChunkHeader = ⟨s, j, ρ, σ⟩, where σ is pj ’s signature over (s, j, ρ), and sends a chunk ⟨Chunk, ChunkHeader , r, dr , πr ⟩ 16
In practice, the protocol instantiates this step using Deterministic RaptorCast [14].
39
Algorithm 2 Proposer Dissemination for Slot s (for validator pi ) 1: upon propose(proposal ∈ Proposal): 2: parse proposal = ⟨s, i, Payload ⟩ ▷ s = proposal .slot, i = proposal .proposer, Payload = proposal .payload 3: if local time = s.deadline − ∆: 4: Let P ← ⟨s, i, Payload , Signi (⟨s, i, H(Payload )⟩)⟩ 5: Let EP ← TIBE.Enc(MPK , s, P ) ▷ hide proposal contents 6: Let (d1 , . . . , dn ) ← Encode(EP ) ▷ erasure-code into n chunks; any f + 1 suffice to decode 7: Let ρ ← MerkleRoot(H(1, d1 ), . . . , H(n, dn )) ▷ bind each chunk to its position 8: Let ChunkHeader ← ⟨s, i, ρ, Signi (⟨s, i, ρ⟩)⟩ 9: for each validator pr : 10: send ⟨Chunk, ChunkHeader , r, dr , πr ⟩ to pr
Algorithm 3 Voting for Slot s (for validator pi ) 1: Local variables: Map(Proposer → Entry) Entry(j) for each proposer pj ∈ s.proposers, initially ⊥; the entry pi will sign for pj (positive iff ρ⊥ ̸= ⊥). 2: function onChunkValidated(j, ρ): ▷ invoked by Alg 6 when a valid chunk has been received from pj 3: if local time < s.deadline and Entry(j) = ⊥: 4: Entry(j) ← ⟨s, j, ρ⟩ ▷ positive entry; chunk received before the deadline 5: upon local time ≥ s.deadline for the first time and pi is actively participating: 6: for each proposer pj ∈ s.proposers with Entry(j) = ⊥: 7: Entry(j) ← ⟨s, j, ⊥⟩ ▷ negative entry: no valid chunk by the deadline 8: Let SignedEntries ← {⟨Entry(j), σj ⟩}pj ∈s.proposers where σj = Signi (⟨vote, Entry(j)⟩) 9: Let Chunks ← ∅ 10: for each pj ∈ s.proposers with Entry(j) positive: 11: add to Chunks the chunk assigned to pi that it received and validated from pj 12: Let DecryptShare ← TIBE.KeyShare(s, MSK i ) 13: broadcast ⟨Vote, s, SignedEntries, Chunks, DecryptShare⟩
to each validator pr , where πr is a Merkle proof for H(r, dr ) under root ρ. We refer to this message as the chunk assigned to pr . Entries. Each validator pi collects incoming chunks until the slot’s deadline s.deadline. For each proposer pj , pi records an entry E = ⟨s, j, ρ⊥ ⟩, where ρ⊥ ∈ MerkleRoot ∪ {⊥} is the Merkle root of the chunk assigned to pi that it received from pj (a positive entry), or ⊥ if no valid chunk arrived by the deadline (a negative entry). Validators vote on entries by signing them. Proposal vote. At the deadline s.deadline (or when pi enters the slot, if later), each validator pi reports what it received for the slot by broadcasting a single proposal vote. This message does three things at once: it carries pi ’s signed positive/negative entry for each proposer, supplies the chunks backing the positive entries, and releases pi ’s decryption share for the slot. Concretely: ⟨Vote, s, SignedEntries, Chunks, DecryptShare⟩, where SignedEntries contains a signed entry ⟨E, σ⟩ per proposer in s.proposers (with pi ’s signature σ on ⟨vote, E⟩), Chunks contains the chunk messages pi received and validated for each positive entry, and DecryptShare is pi ’s share toward decrypting slot-s proposals. FastQC. A fast-path quorum certificate (FastQC) for an entry E aggregates 2f + 1 signatures over ⟨vote, E⟩: FastQC = ⟨vote, E, Σ⟩. A FastQC for a positive entry E = ⟨s, j, ρ⟩ certifies that 2f + 1 validators received and validated a chunk from pj under root ρ, so at least f + 1 honest validators hold chunks; this is what guarantees data availability for pj ’s proposal. 40
Fast Path. The fast path commits the slot in two voting rounds after the deadline, without needing a leader to drive progress, provided a FastQC can be formed for every proposer (a fast meta-block ). Recall that a 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 FastQC forms. In that case, validators take the fallback path. Fast meta-block. A fast meta-block for slot s is B = ⟨CEj1 , . . . , CEjk ⟩, where each CEj is a FastQC for proposer pj ∈ s.proposers. We write entries(B) for the sequence of entries E embedded in the FastQCs. Fast commit vote and certificate. Once a validator pi has a fast meta-block B, it broadcasts a fast commit vote ⟨CommitVote, s, entries(B), σi ⟩, where σi signs ⟨Commit, s, entries(B)⟩. A (2f +1)-aggregate of such votes forms a fast commit certificate CommitQC = ⟨Commit, s, entries(B), Σ⟩, which finalizes the entries entries(B): any validator that holds the CommitQC recovers the underlying proposals via Alg 6.recoverProposals(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. Speculative commit. Once a validator has FastQCs for every proposer, it can speculatively commit the proposal vector before waiting for the CommitQC. Fallback Path. If a FastQC fails to form for some proposer, validators cannot assemble a fast meta-block and the fast path stalls. A 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 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.deadline + ∆ 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 FastQC when one exists, otherwise a FallbackQC (a weaker certificate that the validators help assemble in this phase), or, in adversarial cases, an 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. Fallback signed entries & FallbackQC. A fallback signed entry from validator pr for proposer pj is ⟨E, σv ⟩ (negative, E.ρ⊥ = ⊥)
or
⟨E, σv , σp ⟩ (positive, E.ρ⊥ = ρ),
where σv is pr ’s signature over ⟨fb, E⟩ and, for the positive case, σp is the proposer’s signature on ⟨s, j, ρ⟩ 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 ρ⊥ ← ρ if it has accumulated f + 1 valid fast-path positive votes for the same root ρ and the data is locally available (Alg 6.isDecoded(ρ) returns true), and ρ⊥ ← ⊥ otherwise. A fallback-path quorum certificate (FallbackQC) for entry E aggregates f + 1 signatures over ⟨fb, E⟩: FallbackQC = ⟨fb, E, Σ⟩. The vote/fb tags domain-separate the universal proposal-vote signatures from the fallback-only signatures. 41
Algorithm 4 Fast-Path for Slot s (for validator pi ) 1: Local variables: Map(Proposer × (MerkleRoot ∪ {⊥}) → Set(SignedEntry)) Votes(j, ρ⊥ ) for each pj ∈ s.proposers and ρ⊥ ∈ MerkleRoot ∪ {⊥}, initially ∅; collects the fast-path signed entries received for (pj , ρ⊥ ). Map(Proposer → Evidence) Ev (j) for each proposer pj ∈ s.proposers, initially ⊥; the strongest evidence about pj , shared with Alg 5. Evolves monotonically along ⊥ → fallback signed entry → FallbackQC → EquivCert → FastQC. Enum pathVote ∈ {none, fast, fallback}, initially none; pi ’s second-phase vote (fast-commit or fallback) for slot s, shared with Alg 5. 2: upon receiving ⟨Vote, s, SignedEntries, Chunks, DecryptShare⟩ from validator pr and pi is actively participating: 3: for each proposer pj ∈ s.proposers: 4: if SignedEntries has no entry for pj , or its signature fails verification under pr : 5: return 6: Let ⟨⟨s, j, ρ⊥ ⟩, σ⟩ be the signed entry for pj 7: if ρ⊥ ̸= ⊥, and either no m ∈ Chunks has matching ρ⊥ or Alg 6.tryIngestChunk(m) = false: 8: return 9: if Alg 6.tryIngestShare(r, DecryptShare) = false: 10: return 11: for each signed entry pv = ⟨E, σ⟩ ∈ SignedEntries with E = ⟨s, j, ρ⊥ ⟩: 12: Votes(j, ρ⊥ ) ← Votes(j, ρ⊥ ) ∪ {pv } 13: upon |Votes(j, ρ⊥ )| ≥ 2f + 1 for some pj and ρ⊥ , and pi is actively participating: 14: Let Σ be the aggregate of the signatures 15: Ev (j) ← ⟨vote, ⟨s, j, ρ⊥ ⟩, Σ⟩
▷ FastQC
16: upon first time Ev (j) is a FastQC for every proposer pj ∈ s.proposers, and pi is actively participating: 17: Let B ← {Ev (j)}pj ∈s.proposers ▷ fast meta-block 18: broadcast ⟨FastBlock, s, B⟩ ▷ disseminate so peers can adopt; broadcast unconditionally 19: if pathVote = none: 20: Let σi ← Signi (⟨Commit, s, entries(B)⟩) 21: broadcast commit vote ⟨CommitVote, s, entries(B), σi ⟩ 22: pathVote ← fast ▷ commit vote and fallback vote are mutually exclusive 23: Let V ← Alg 6.recoverProposals(entries(B)) 24: speculatively commit V 25: upon receiving ⟨FastBlock, s, B⟩ where B is a valid fast meta-block, and pi is actively participating: 26: for each proposer pj ∈ s.proposers: 27: Ev (j) ← B(j) 28: upon pi has collected 2f + 1 fast commit votes carrying the same entries entries(B), and pi is actively participating: 29: Let Σ be the aggregate of the 2f + 1 signatures, and let CommitQC ← ⟨Commit, s, entries(B), Σ⟩ 30: broadcast CommitQC 31: upon receiving a valid fast CommitQC = ⟨Commit, s, entries(B), Σ⟩: ▷ no active-participation precondition 32: broadcast CommitQC 33: trigger finalize(Alg 6.recoverProposals(entries(B)))
42
EquivCert. An equivocation certificate for proposer pj is EquivCert = ⟨equiv, s, j, ρ1 , σp,1 , ρ2 , σp,2 ⟩, where ρ1 ̸= ρ2 and each σp,k is pj ’s signature over ⟨s, j, ρk ⟩. The 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 FallbackQC unformable; pinning the proposer to two contradictory signed roots still certifies its exclusion. Fallback vote message. Once time has reached s.deadline + ∆ and pr 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, pr broadcasts a fallback vote: ⟨FallbackVote, s, σr , Ev j1 , . . . , Ev jk ⟩, where σr = Signr (⟨fallback, s⟩) is pr ’s commitment to entering the fallback path, and each Ev j is the strongest evidence pr holds for pj , by precedence FastQC ≻ EquivCert ≻ FallbackQC ≻ fallback signed entry (the last being pr ’s own signed entry when no higher-tier evidence is available). Fallback certificate. Once 2f + 1 fallback votes are collected, their σr fields aggregate into a fallback certificate FBCerts = ⟨fallback, s, Σ⟩, certifying that the fast path can no longer commit slot s. Fallback meta-block. From 2f + 1 fallback votes, each validator builds a fallback meta-block B = ⟨CEj1 , . . . , CEjk , FBCerts ⟩, where each CEj is a certified entry for pj : a FastQC, FallbackQC, or EquivCert (the latter two assembled from the signed entries collected in fallback votes, when no FastQC is available). Extending the convention from Section C.3, entries(B) contributes the embedded E for a FastQC or FallbackQC, and the negative entry ⟨s, j, ⊥⟩ for an EquivCert for pj (equivocation excludes the proposer); FBCerts is not part of entries(B). We call a meta-block valid if it is either a fast meta-block or a fallback meta-block in this sense. Invocation to the MVBA primitive. The validator then proposes its meta-block B to MVBA[s], the slot’s multi-valued Byzantine agreement instance, invoking it at most once; B is valid by construction. The MVBA we use (Module 3) 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 Certifies, that attests to a meta-block. Module 3 Multi-Valued Byzantine Agreement (MVBA) Associated functions: - Certifies(cert, B): a publicly computable function returning true if the certificate cert certifies the metablock B, and false otherwise. Each certificate certifies at most one meta-block, i.e., Certifies(cert, B) = Certifies(cert, B ′ ) = true implies B = B ′ . Interface: - input propose(B): a validator proposes a valid meta-block B. - output decide(B, cert): a validator decides a valid meta-block B together with a certificate cert for it. Properties: - Agreement: No two distinct meta-blocks are both certified: if certificates cert and cert ′ — obtained by any (possibly faulty) validators — satisfy Certifies(cert, B) = Certifies(cert ′ , B ′ ) = true, then B = B ′ . - ℓMVBA -Termination: If all correct validators propose by time t, then every correct validator decides by time max(t, GST) + ℓMVBA , where ℓMVBA ≥ 2∆.17 - Validity: If a correct validator decides (B, cert), then Certifies(cert, B) = true.
When the MVBA outputs a meta-block B ′ , the validator recovers the underlying proposals by calling recoverProposals(entries(B ′ )) on the DA module and commits them. Even after invoking the MVBA, a validator still finalizes on the fast path if a CommitQC arrives; whenever it finalizes, by either path, it broadcasts the commitment proof and concludes all activity for the slot, including its MVBA invocation. 17
We rely on the bound ℓMVBA ≥ 2∆ in the proofs.
43
Algorithm 5 Transition to Fallback Path for Slot s (for validator pi ) 1: Local variables: Map(Proposer → Evidence) Ev (j) for each pj ∈ s.proposers, shared with Alg 4. Set(FallbackVote) Mi , initially ∅; the FallbackVote messages received for slot s. Enum pathVote, shared with Alg 4. Map(Proposer × (MerkleRoot ∪ {⊥}) → Set(SignedEntry)) Votes(j, ρ⊥ ), shared with Alg 4. Bool mvbaInvoked , initially false. ▷ If no fast meta-block can be formed one timeout after the deadline, we enter the fallback path. 2: upon local time reaches s.deadline + ∆, at least 2f + 1 valid Vote messages have been received, pathVote = none, and pi is actively participating: 3: for each proposer pj ∈ s.proposers with Ev (j) = ⊥: 4: if collected f + 1 valid positive votes for (pj , ρ) for some ρ and Alg 6.isDecoded(ρ): 5: Let E ← ⟨s, j, ρ⟩ ▷ cast a positive fallback vote for pj 6: Let σp be the proposer’s signature on ⟨s, j, ρ⟩ from any chunk pi validated under ρ 7: Ev (j) ← ⟨E, Signi (⟨fb, E⟩), σp ⟩ ▷ positive fallback signed entry 8: re-encode proposal; send each validator its assigned chunk for ρ 9: else: 10: Let E ← ⟨s, j, ⊥⟩ ▷ cast a negative fallback vote 11: Ev (j) ← ⟨E, Signi (⟨fb, E⟩)⟩ ▷ negative fallback signed entry 12: Let σi ← Signi (⟨fallback, s⟩) ▷ pi ’s fallback vote for slot s 13: broadcast ⟨FallbackVote, s, σi , {Ev (j)}pj ∈s.proposers ⟩ 14: pathVote ← fallback 15: upon receiving m = ⟨FallbackVote, s, σ, {Rj }pj ∈s.proposers ⟩ from a validator pr where σ verifies as pr ’s signature over ⟨fallback, s⟩, and pi is actively participating: 16: for each proposer pj ∈ s.proposers: 17: if Rj is not valid evidence for (s, j): 18: return 19: Mi ← Mi ∪ {m} 20: for each proposer pj where Rj is a FastQC: 21: Ev (j) ← Rj ▷ harvest FastQCs 22: for each proposer pj where Rj is a FallbackQC and Ev (j) is neither a FastQC nor an EquivCert: 23: Ev (j) ← Rj ▷ harvest FallbackQCs 24: upon first time there exist f + 1 messages in Mi containing fallback signed entries ⟨E, ·⟩ for the same entry E, Ev (E.j) is neither a FastQC nor an EquivCert, and pi is actively participating: 25: Let Σj be the aggregate of the f + 1 signatures 26: Ev (E.j) ← ⟨fb, E, Σj ⟩ ▷ FallbackQC 27: upon first time two messages in Mi contain positive fallback signed entries for some proposer pj ∈ s.proposers with different roots ρ1 ̸= ρ2 and valid proposer signatures σp,1 , σp,2 , Ev (j) is not a FastQC, and pi is actively participating: 28: Ev (j) ← ⟨equiv, s, j, ρ1 , σp,1 , ρ2 , σp,2 ⟩ ▷ EquivCert; never overwrites a FastQC 29: upon first time Ev (j) is a FastQC for every proposer pj ∈ s.proposers and local time reaches s.deadline + 2∆, mvbaInvoked = false, and pi is actively participating: 30: mvbaInvoked ← true 31: Let B ← {Ev (j)}pj ∈s.proposers ▷ fast meta-block 32: Let (B ′ , cert ′ ) ← MVBA[s](B) ▷ decided meta-block and its certificate 33: broadcast ⟨Commit, s, B ′ , cert ′ ⟩ ▷ transferable commitment proof 34: trigger finalize(Alg 6.recoverProposals(entries(B ′ ))) 35: upon first time |Mi | ≥ 2f + 1, mvbaInvoked = false, and pi is actively participating: 36: mvbaInvoked ← true 37: Let B ← {Ev (j)}pj ∈s.proposers ▷ by the rules above, every Ev (j) is a FastQC, FallbackQC, or EquivCert 38: if some Ev (j) is not a FastQC: 39: Let Σfb be the aggregate of 2f + 1 fallback votes (the σ fields of messages in Mi ) 40: Let FBCerts ← ⟨fallback, s, Σfb ⟩ 41: append FBCerts to B ▷ fallback meta-block 42: Let (B ′ , cert ′ ) ← MVBA[s](B) ▷ decided meta-block and its certificate 43: broadcast ⟨Commit, s, B ′ , cert ′ ⟩ ▷ transferable commitment proof 44: trigger finalize(Alg 6.recoverProposals(entries(B ′ ))) 45: upon receiving a valid ⟨Commit, s, B ′ , cert ′ ⟩ with Certifies(cert ′ , B ′ ): ▷ no active-participation precondition 46: broadcast ⟨Commit, s, B ′ , cert ′ ⟩ 47: trigger finalize(Alg 6.recoverProposals(entries(B ′ )))
44
Data Availability. The data-availability (DA) module is responsible for recovering the proposals originally embedded by each proposer in chunks. Chunk reception. On receiving a chunk, the DA module verifies the proposer’s signature and the chunk’s Merkle proof against its root ρ. 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 ρ before the deadline. Second, once f +1 valid chunks for the same root ρ accumulate, the module decodes them into a candidate encrypted proposal c and re-encodes c, comparing the resulting root against ρ: if they match, c is confirmed; otherwise ρ is marked invalid, catching a proposer that disseminated inconsistent chunks under one root. 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 ρ invalid if decryption fails. Proposal recovery. At commit time (speculative or formal), a validator calls recoverProposals(entries(B)) on the DA module. The call blocks until every positive entry ⟨s, j, ρ⟩ ∈ 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 FastQC for a positive entry implies that f + 1 honest validators contributed chunks (enough to decode by erasure coding); a FallbackQC for a positive entry implies that at least one honest validator has already decoded the proposal locally and re-disseminates the chunks (Alg 5). These two facts are the formal counterpart of the availability of §4.1. Its companion consistency corresponds to the determinism of the re-encode-and-compare check in tryIngestChunk (Alg 6, line 18), 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. C.4
Proof
This subsection proves that, when run within Cadence, Chorus realizes the slot-consensus primitive (see Module 1). We do so by establishing each of its properties — agreement, termination, slot safety, proposal inclusion, and hiding — in turn. Hiding. We begin with the hiding property. Lemma 6 (Hiding). Chorus (Algorithms 2 to 6) satisfies hiding. Proof. This is established by the simulation argument of §C.2. Slot safety. Next, we prove the slot safety property. Lemma 7 (Slot safety). Chorus (Algorithms 2 to 6) satisfies slot safety. Proof. Follows directly from line 7 of Algorithm 6: a validator finalizes only the proposal vector returned by recoverProposals, which is a proposal vector for slot s. 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 CommitQC or the certificate the MVBA decides (Module 3) — whereupon it triggers finalize: in the fast path on a valid CommitQC (Algorithm 4, line 33), and in the fallback path on the MVBA’s decision (Algorithm 5, lines 34 and 44) or on a received commit message (Algorithm 5, line 47). 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. Proposition 1. Consider any two (potentially faulty) validators pi and pj such that pi obtains (i.e., stores in its local memory) a commitment proof for a meta-block Bi and pj obtains a commitment proof for a meta-block Bj . Then, entries(Bi ) = entries(Bj ). Proof. A commitment proof is either a fast commit certificate CommitQC (Algorithm 4) or an MVBAdecided certificate (Algorithm 5), so we distinguish three cases. 45
Algorithm 6 Data Availability for Slot s 1: Local variables: Map(MerkleRoot → Status) status(ρ) for each ρ ∈ MerkleRoot, initially ⊥, with possible values: ⊥: pending; insufficient chunks received for decoding. ⟨cipher, c⟩ for c ∈ Ciphertext: ciphertext reconstructed and Merkle-verified, awaiting decryption key. ⟨plain, P ⟩ for a decrypted proposal P = ⟨s, j, Payload , σ⟩: the recovered proposal, retaining its embedded proposer identity j and signature σ. invalid: settled as not recoverable. Map(MerkleRoot → Set(Symbol)) data(ρ) for each ρ ∈ MerkleRoot, initially maps to ∅; a set of validated erasure-code symbols dr . Set shares initially ∅; a set of (validator-index, decryption-share) pairs. 2: function isDecoded(ρ): 3: return (status(ρ) ∈ {⟨cipher, ·⟩, ⟨plain, ·⟩}) 4: function recoverProposals(entries): 5: wait until, for every positive entry ⟨s, j, ρ⊥ ⟩ ∈ entries, status(ρ⊥ ) ∈ {⟨plain, ·⟩, invalid} 6: the entry is invalid unless status(ρ⊥ ) = ⟨plain, P ⟩ with P ’s proposer equal to j 7: return the proposal vector V for slot s assigning each proposer its recovered proposal (or ⊥) 8: function tryIngestChunk(chunkMsg): 9: parse chunkMsg = ⟨Chunk, ChunkHeader , r, dr , πr ⟩ with ChunkHeader = ⟨s, j, ρ, σ⟩ 10: if j ∈ / s.proposers, σ does not verify, or VerifyMerkle(ρ, dr , πr ) ̸= ⊤: 11: return false 12: if r = i: 13: broadcast chunkMsg 14: call Alg 3.onChunkValidated(j, ρ) ▷ records a positive entry if received before the deadline 15: data(ρ) ← data(ρ) ∪ {dr } 16: if status(ρ) = ⊥ and |data(ρ)| ≥ f + 1: 17: Let c ← Decode(data(ρ)) 18: if c = ⊥ or MerkleRoot(Encode(c)) ̸= ρ: 19: status(ρ) ← invalid 20: else: 21: status(ρ) ← ⟨cipher, c⟩ 22: return true 23: function tryIngestShare(r, DecryptShare r ): 24: if TIBE.VerifyShare(MPK , s, r, DecryptShare r ) ̸= ⊤: 25: return false 26: shares ← shares ∪ {(r, DecryptShare r )} 27: return true 28: upon receiving chunkMsg = ⟨Chunk, . . .⟩: 29: tryIngestChunk(chunkMsg) 30: upon ∃ ρ such that status(ρ) = ⟨cipher, c⟩ for some c, and |shares| ≥ f + 1: 31: Let m ← TIBE.Dec(MPK , c, s, shares) 32: if m = ⊥, or m does not parse as a proposal P = ⟨s, j, Payload , σ⟩ whose signature σ verifies under pj : 33: status(ρ) ← invalid 34: else: 35: status(ρ) ← ⟨plain, P ⟩
46
– Both pi and pj hold a CommitQC. Then Bi and Bj are fast meta-blocks (Algorithm 4, line 17), each of whose entries is a FastQC (line 15) — an aggregate of 2f + 1 matching signed entries. Fix a proposer; the two supporting sets of 2f + 1 signed entries (one from Bi , one from Bj ) intersect, among the n = 3f + 1 validators, in at least f + 1, hence in a correct validator. Since a correct validator signs a single entry per proposer (Algorithm 3, line 13), the two entries for that proposer coincide. As this holds for every proposer, entries(Bi ) = entries(Bj ). – Both hold an MVBA-decided certificate. This holds due to the agreement property of the MVBA (Module 3). – One holds a CommitQC and the other an MVBA certificate. Without loss of generality, pi holds a CommitQC for Bi and pj an MVBA certificate for Bj . A CommitQC aggregates 2f + 1 commit votes (Algorithm 4, line 28), so at least f + 1 correct validators broadcast a commit vote and thereby set pathVote = fast (line 22). A correct validator issues a fallback vote only while pathVote = none (Algorithm 5, line 2), so these f + 1 correct validators never do; fewer than 2f + 1 fallback votes can form, and hence no fallback meta-block — which requires a 2f + 1-fallback-vote certificate — is valid. The MVBA decides a valid meta-block, which here must be a fast meta-block, so Bj is a fast meta-block. As Bi is a fast meta-block as well, entries(Bi ) = entries(Bj ) due to the quorum intersection. ⊔ ⊓ Proposition 2. For any set of entries E, any two correct validators that recover proposal vectors V and V ′ from recoverProposals(E) satisfy V = V ′ . Proof. We show that whenever two correct validators both return from recoverProposals(E), they return the same vector. Negative entries recover to ⊥ at every validator, so fix a positive entry ⟨s, j, ρ⟩ ∈ E; we show that any two correct validators that resolve it recover the same value for pj . A correct validator returns a value for ⟨s, j, ρ⟩ only once status(ρ) ∈ {⟨plain, ·⟩, invalid} (Algorithm 6, line 5). The verdict on ρ — accept and decode, or mark invalid — is fixed by the re-encode-and-compare check of tryIngestChunk (Algorithm 6, line 18): a validator decodes its f + 1 chunks to a candidate c and accepts ρ only if MerkleRoot(Encode(c)) = ρ. The chunks admissible under ρ are pinned down by the root itself (collision resistance of the Merkle hash), and Decode and Encode are deterministic; hence the verdict depends only on ρ and not on which f + 1 chunks a validator happens to collect. Every correct validator that resolves ρ thus reaches the same verdict and, on acceptance, the same ciphertext c. Decryption is likewise deterministic once the slot key is reconstructed, so all such validators recover the same proposal P for pj , or all mark ρ invalid (recovering ⊥). As this holds for every proposer, the two validators recover the same proposal vector. ⊔ ⊓ We are ready to prove the agreement property of Chorus. Lemma 8 (Agreement). Chorus (Algorithms 2 to 6) satisfies agreement. Proof. A correct validator finalizes only the proposal vector recoverProposals(entries(B)) (Algorithm 6, line 7) for a meta-block B for which it holds a commitment proof. Let Vi and Vj be proposal vectors finalized by correct validators, backed by commitment proofs for meta-blocks Bi and Bj ; thus Vi = recoverProposals(entries(Bi )) and Vj = recoverProposals(entries(Bj )). By Proposition 1, entries(Bi ) = entries(Bj ), and by Proposition 2, applying recoverProposals to these equal entries yields the same proposal vector at both validators. Hence Vi = Vj . ⊔ ⊓ 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. Proposition 3. Suppose s.deadline − ∆ ≥ GST and a correct proposer pj ∈ s.proposers disseminates its proposal P , with Merkle root ρP , at time s.deadline − ∆. Then in every certified meta-block, pj ’s entry is the positive entry ⟨s, j, ρP ⟩. Proof. Since s.deadline − ∆ ≥ GST and pj disseminates by the slot’s starting time, every correct validator receives and validates a chunk under ρP by the deadline, setting its entry for pj to the positive entry ⟨s, j, ρP ⟩ (Algorithm 3, line 4). Hence no correct validator ever signs a negative entry ⟨s, j, ⊥⟩, nor an entry on a root ̸= ρP , for pj . A FastQC for pj is an aggregate of 2f + 1 matching signed entries (Algorithm 4, line 15); as at most f validators are Byzantine, no 2f + 1 matching signed entries can carry ⊥ or a root ̸= ρP , so any FastQC for pj is the positive entry ⟨s, j, ρP ⟩. 47
The fallback path yields the same conclusion. A correct validator casts a fallback signed entry for pj only after collecting 2f + 1 first-round votes (Algorithm 5, line 2); at least f + 1 of these come from correct validators, each carrying the positive entry ⟨s, j, ρP ⟩ for pj together with its chunk. The validator therefore holds f + 1 positive entries on ρP and can decode ρP , so it casts a positive fallback signed entry on ρP — never a negative one, nor one on another root (Algorithm 5, line 7). Since a FallbackQC aggregates f + 1 matching fallback signed entries and at most f validators are Byzantine, any FallbackQC for pj is likewise positive on ρP , and no negative FallbackQC can form; an EquivCert would require pj to sign two different roots, impossible for a correct proposer. Thus every piece of evidence ever formed for pj — a FastQC or a FallbackQC — is the positive entry ⟨s, j, ρP ⟩, which is therefore its entry in every certified meta-block. ⊔ ⊓ With the proposer’s entry pinned down by Proposition 3, we can now establish proposal inclusion. Lemma 9 (Proposal inclusion). Chorus (Algorithms 2 to 6) satisfies proposal inclusion. Proof. Let ρP be the Merkle root of pj ’s encrypted proposal, and let B be the certified meta-block the validator finalizes, so that V = recoverProposals(entries(B)). By Proposition 3, pj ’s entry in B is the positive entry ⟨s, j, ρP ⟩ — a FastQC or a FallbackQC on ρP . Either way, the chunks under ρP are re-disseminated by honest validators: a FastQC carries ≥ f + 1 honest signers, each re-broadcasting its own chunk (Algorithm 6, line 13); a FallbackQC has an honest caster that sends each validator its assigned chunk (Algorithm 5, line 8), which each then re-broadcasts (Algorithm 6, line 13). So every correct validator collects f + 1 valid chunks under ρP , and recoverProposals does not block on this entry (Algorithm 6, line 5). Because pj is correct, its proposal is well-formed: the recovered chunks reconstruct the ciphertext committed by ρP , which re-encodes to ρP and, once the slot key is released, decrypts to P (Algorithm 6, line 18; §C.2); moreover P ’s proposer is pj , so the entry is not marked invalid. Hence recoverProposals recovers P for pj , i.e., V [pj ] = P . ⊓ ⊔ Termination. We first establish totality: once one correct validator finalizes, every correct validator finalizes within 2∆ (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 (Lemma 14) — so we record it as a standalone property. Proposition 4 (Totality). If a correct validator finalizes a proposal vector for slot s at some time t, then every correct validator does so by time max(t, GST) + 2∆. Proof. On finalizing a meta-block B, a correct validator broadcasts a transferable commitment proof for B — a fast commit certificate CommitQC (Algorithm 4, line 32) or the certificate the MVBA decides (Algorithm 5, lines 33, 43, and 46; Module 3). A correct validator finalizes upon receiving any valid commitment proof (Algorithm 4, line 31; Algorithm 5, line 45), by recovering and committing recoverProposals(entries(B)) (Algorithm 6, line 7). Suppose a correct validator finalizes at time t with such a proof for B. After GST its broadcast reaches every correct validator within ∆, so every correct validator holds a valid commitment proof for B by max(t, GST) + ∆. It remains to bound when recovery succeeds at every correct validator. Each positive entry of B is certified by a FastQC or a FallbackQC, and the certificate is formed no later than t (it is part of B). For a FastQC, its 2f + 1 positive signed entries include at least f + 1 from honest validators, each of which has broadcast the chunk assigned to it (Algorithm 6, line 13); these single-hop broadcasts reach every correct validator within ∆, hence by max(t, GST) + ∆. For a FallbackQC, at least one honest validator reconstructed the proposal and sent every validator its assigned chunk (Algorithm 5, line 8) at some time r ≤ t; each correct validator then rebroadcasts the chunk it receives (Algorithm 6, line 13), so after this two-hop dissemination every correct validator holds f + 1 valid chunks by max(r, GST) + 2∆ ≤ max(t, GST) + 2∆. The decryption shares, broadcast with the proposal votes, likewise reach everyone within ∆. Hence by max(t, GST) + 2∆ every correct validator holds a commitment proof for B together with all the chunks and shares that recoverProposals(entries(B)) needs, so it recovers the proposal vector (Algorithm 6, line 7) and finalizes it. ⊔ ⊓ With totality in hand, we bound when every correct validator finalizes assuming no correct validator stops participating. Proposition 5. Suppose all correct validators start participating in slot s by some time t, and no correct validator stops participating before time T = max(t, GST) + 3∆ + ℓMVBA . Then every correct validator finalizes a proposal vector by time T . 48
Proof. We trace the protocol round by round; all bounds are relative to max(t, GST), after which every message between correct validators is delivered within ∆. First-round votes, by max(t, GST) + ∆. Within Cadence a correct validator starts participating in s no earlier than s.deadline − ∆ (by the integrity of Conductor).18 While actively participating, each correct validator issues its first-round vote on reaching the deadline — or as soon as it is past, if the validator entered the slot late (Algorithm 3, line 13). As established above, no correct validator starts before s’s starting time, which lies exactly ∆ before the deadline; hence every correct validator issues its first-round vote by time max(t, GST) + ∆. Second-round votes, by max(t, GST) + 2∆. The first-round votes reach every correct validator within a further ∆, so each either forms a FastQC and broadcasts a commit vote (Algorithm 4, line 21) or else enters the fallback path and broadcasts a fallback vote (Algorithm 5, line 2) — in either case by max(t, GST) + 2∆. Moreover, since each correct validator releases its decryption share together with its first-round vote, every correct validator holds at least f + 1 valid decryption shares — enough to reconstruct the slot key — by time max(t, GST) + 2∆. MVBA proposals, by max(t, GST) + 3∆. On the fallback path the second-round votes again propagate within ∆, so by max(t, GST) + 3∆ every correct validator has either already finalized on the fast path (on obtaining a CommitQC; Algorithm 4) or assembled a valid meta-block and proposed it to MVBA[s] (Algorithm 5). Deciding, by T . If some correct validator finalizes by time max(t, GST) + 3∆, totality (Proposition 4) carries every correct validator to finalization within a further 2∆, hence by T (as ℓMVBA ≥ 2∆). Otherwise every correct validator proposed to MVBA[s] by max(t, GST) + 3∆; the ℓMVBA -termination of the MVBA (Module 3) then guarantees that every correct validator decides (B ′ , cert ′ ) by max(t, GST)+3∆+ℓMVBA = T. Reconstruction does not add delay. To finalize, a validator recovers the proposal vector from the decided meta-block (Algorithm 6, line 7), which needs f +1 chunks under each positive entry’s root to reconstruct the ciphertext and f + 1 decryption shares to open it. For a FastQC entry, at least f + 1 honest validators validated and broadcast their chunk by the deadline (or as soon as it is past, if the validator entered the slot late) (Algorithm 6, line 13); these single-hop broadcasts reach every correct validator by max(t, GST)+2∆. For a FallbackQC entry, the chunks instead spread by a two-hop dissemination — the honest fallback caster sends each validator its chunk (Algorithm 5, line 8), which each then rebroadcasts (Algorithm 6, line 13) — completing by max(t, GST) + 4∆. So the chunks are in place by max(t, GST) + 4∆, and the f + 1 decryption shares needed to open each ciphertext arrived even earlier, by max(t, GST) + 2∆ (as argued above). Both ingredients that recoverProposals needs are therefore present by max(t, GST) + 4∆, and since ℓMVBA ≥ 2∆ gives 3∆ + ℓMVBA ≥ 4∆, they are in place no later than the MVBA decision; hence recovery never blocks (Algorithm 6, line 5). Therefore every correct validator finalizes a proposal vector for s by time T .
⊓ ⊔
We are finally ready to establish Chorus’s termination. Lemma 10 (Termination). When run within Cadence, Chorus (Algorithms 2 to 6) satisfies ℓtermination with ℓ = 5∆ + ℓMVBA : if all correct validators start participating by some time t, then every correct validator finalizes a proposal vector by time max(t, GST) + 5∆ + ℓMVBA . Proof. Within Cadence a correct validator invokes abandon() only after it has finalized (Algorithm 1, line 23); equivalently, once a correct validator starts participating it keeps participating until it finalizes. Let T0 = max(t, GST) + 3∆ + ℓMVBA and distinguish two cases. – Some correct validator finalizes by T0 . By totality (Proposition 4), every correct validator then finalizes within a further 2∆, hence by T0 + 2∆ = max(t, GST) + 5∆ + ℓMVBA . – No correct validator finalizes by T0 . Then no correct validator has abandoned its instance by T0 , so all correct validators remain participating throughout [t, T0 ]; by Proposition 5, every correct validator finalizes by T0 ≤ max(t, GST) + 5∆ + ℓMVBA . In either case, every correct validator finalizes by max(t, GST) + 5∆ + ℓMVBA . ⊔ ⊓ 18
Conductor does rely on Chorus for some of its own guarantees — namely its totality and recovery (see Lemma 14) — but the integrity property we invoke here holds unconditionally and depends on nothing about Chorus. Hence, there is no circularity.
49
D
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 Section 5. D.1
Protocol
Here, we introduce Conductor (Algorithm 7). Before presenting it, we describe the building block it relies on, agreement on a core set (ACS). Agreement on a Core Set (ACS). The full specification of ACS is given in Module 4. 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.
Module 4 Agreement on a Core Set (ACS) Parameters: - id ∈ N≥1 : a unique identifier. Interface: - input propose(s ∈ Slot): a validator proposes slot s. - output decide(set ∈ Set(Validator × Slot)): a validator decides a set set of validator-slot pairs. Properties: - Agreement: No two correct validators decide different sets. - ℓ-Termination: If all correct validators propose by time t, then every correct validator decides by time max(t, GST) + ℓ. - Validity: If a correct validator decides a set set, then |set| ≥ 2f + 1, and for every validator-slot pair (pi , si ) ∈ set such that pi is a correct validator, pi proposed slot si . - Integrity: If a correct validator decides, then some correct validator has previously proposed. - ∆-Totality: If a correct validator decides at some time t, then all correct validators decide by time max(t, GST) + ∆.
Protocol Description. Algorithm 7 gives Conductor’s pseudocode, written from the perspective of a single correct validator pi ; recall that validators’ clocks are synchronized, so they share one global timeline. As described informally in Section 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, . . . , 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, pi tracks the window it is currently scheduling in current window i (initially 1, line 14), the slots it has opened in opened i , the slots reported complete in completed i , the last (highest-numbered) slot of each window in last i , and the windows for which it has already submitted an ACS proposal in proposed i . Parameters & constants. Conductor takes two tunable parameters: the window size W ∈ N≥1 and the readiness threshold p ∈ {0, . . . , W − 1}, which controls how much of a window must complete before the next one is opened. Its timing further involves several constants: ℓ, the termination latency of the underlying ACS primitive (line 12); ℓchorus , the termination latency of Chorus, the slot-consensus protocol whose finalizations complete Conductor’s slots within Cadence; ∆tot = 2∆ (Proposition 4), the totality latency of Chorus— the time within which one correct validator’s completion of a slot propagates to all correct validators; ∆, the post-GST bound on message delays; and τ , the spacing between consecutive slot deadlines. From these we derive the open-to-complete delay Φoc = ℓchorus + ∆tot , which bounds the time between a correct validator opening a slot and completing it (Proposition 15). For Conductor to achieve its recovery property, W and p must be chosen so that the following four assumptions hold (lines 7–10): 50
– (p − 1)τ + Φoc + ℓ ≤ W τ ; – (p − 1)τ + Φoc ≤ (W − 1)τ ; – ∆ < ℓ; and – ∆tot + ℓ ≤ (p − 1)τ . 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 τ , 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 Section D.2. Startup. Upon starting (line 29), pi enters window 1 (line 30) and schedules the opening of its W slots in increasing order (lines 31–33), recording slot W as that window’s last slot (line 34). Opening is asynchronous: schedule opening(s) waits until the slot’s starting time s.deadline − ∆ — or fires at once if it has already passed — and then outputs open(s) (lines 27–28). Since deadlines are τ -spaced, window 1’s slots thus open at times 0, τ, . . . , (W − 1)τ . Completions. After startup, the only input to Conductor is the completion of slots: upon completed(s) (line 35), pi adds s to completed i (line 36). Within Cadence, pi completes a slot precisely when it finalizes that slot’s proposal vector. Estimating the next window’s deadline. Conductor opens window current window i +1 only once enough of the current schedule has completed, as captured by ready for next window() (line 23): writing s1 < · · · < sk for the opened slots, it returns 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 37), pi estimates that window’s first slot: it reads the current time tcur (line 38) and lets s⋆ be the earliest slot whose starting time has not yet passed (line 39); if that slot still falls within the current window, it advances s⋆ to the first slot beyond it (lines 40–41). These two cases are exactly the estimate of Figure 11: when the system is keeping up, s⋆ is the slot immediately after the current window, so the cadence continues with no gap; when it is lagging, s⋆ is pushed to tcur , leaving a gap for the backlog to drain. Validator pi then proposes s⋆ to the next window’s agreement instance ACS[current window i + 1] (line 42) and records that it has done so (line 43), 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 ACS[current window i + 1] decides and pi is ready (line 44), pi advances to the next window (lines 45–46) and takes its first slot s⋆ to be the median of the decided estimates (line 47); 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⋆ , . . . , s⋆ + W − 1 in increasing order (lines 48–50) and records s⋆ + W − 1 as the window’s last slot (line 51). Because pi opens a fresh window only when at most the last W − p slots of the current one remain incomplete (line 23), at most (W − p) + W = 2W − p slots are ever in flight — precisely Conductor’s boundedness. D.2
Proof
This section proves that, when run within Cadence, Conductor satisfies the orchestrator specification of Module 2. 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. Structural facts about windows. We first establish that windows are entered at most once and in strictly increasing order. Proposition 6. For every correct validator pi and every window ω ∈ N≥1 , pi enters window ω at most once. Moreover, if ω ≥ 2, then pi enters window ω only after having previously entered window ω − 1. Proof. Let us first prove that pi enters window ω at most once. First, note that the variable current window i of a correct validator never decreases: it is modified only at line 45, where it is incremented by one. Moreover, any two successive enterings are separated by such an increment. Indeed, only the first entering occurs at startup (line 30), and this happens exactly once since the startup handler fires only once; every later entering occurs at line 46, immediately after current window i is incremented at line 45. Hence each entering corresponds to a distinct, strictly increasing value of current window i , so no window is entered more than once. 51
Algorithm 7 Conductor: Pseudocode (for validator pi ) 1: Parameters: 2: Integer W ∈ N≥1 3: Integer p ∈ {0, . . . , W − 1} 4: Time Φoc = ℓchorus + ∆tot 5: Time ℓ
▷ window size ▷ readiness threshold ▷ open-to-complete delay ▷ latency of the utilized ACS
6: Assumptions on the parameters: 7: (1) (p − 1)τ + Φoc + ℓ ≤ W τ 8: (2) (p − 1)τ + Φoc ≤ (W − 1)τ 9: (3) ∆ < ℓ 10: (4) ∆tot + ℓ ≤ (p − 1)τ 11: Uses: 12: ACS (ℓ-termination), instances ACS[i], for every i ∈ N≥2 , parameterized by i 13: Local variables: 14: Integer current window i ← 1 15: Set(Slot) opened i ← ∅ 16: Set(Slot) completed i ← ∅ 17: Map(Integer → Slot) last i , with last i [j] ← ⊥ for all j ∈ N≥1 18: Set(Integer) proposed i ← ∅ ▷ windows for which an ACS proposal has been submitted 19: Local functions: 20: function ready for next window() → Bool: 21: Let s1 < s2 < · · · < sk be the slots in opened i 22: Let j be the largest index such that s1 , . . . , sj ∈ completed i 23: return k − j ≤ W − p 24: 25: 26: 27: 28:
(j = 0 if none)
▷ asynchronous: returns immediately; opening is triggered in the background at the appropriate time function schedule opening(s ∈ Slot) → Void: ▷ open at s.deadline − ∆, or immediately if that time has already passed wait until the first time ≥ max(current local time, s.deadline − ∆) trigger open(s) ▷ output of Conductor
29: upon starting the protocol: 30: enter window 1 31: for each s ∈ Slot such that s.number ∈ [1, W ]: 32: invoke schedule opening(s) 33: opened i ← opened i ∪ {s} 34: last i [1] ← the slot whose number is W
▷ marked for the analysis ▷ process slots in increasing order
35: upon completed(s ∈ Slot): 36: completed i ← completed i ∪ {s} / proposed i : 37: upon ready for next window() = true and (current window i + 1) ∈ 38: Let tcur be the current local time 39: Let s⋆ be the slot with the smallest number whose starting time (i.e., s⋆ .deadline − ∆) is ≥ tcur 40: if s⋆ .number ≤ last i [current window i ].number: 41: s⋆ ← the slot whose number is last i [current window i ].number + 1 42: invoke ACS[current window i + 1].propose(s⋆ ) 43: proposed i ← proposed i ∪ {current window i + 1} 44: upon ACS[current window i + 1].decide(set ∈ Set(Validator × Slot)) and ready for next window() = true: 45: current window i ← current window i + 1 46: enter window current window i ▷ marked for the analysis 47: Let s⋆ be the slot with s⋆ .number = median({s.number : (·, s) ∈ set}) 48: for each s ∈ Slot with s.number ∈ [s⋆ .number, s⋆ .number + W ): ▷ process slots in increasing order 49: invoke schedule opening(s) 50: opened i ← opened i ∪ {s} 51: last i [current window i ] ← the slot whose number is s⋆ .number + W − 1
52
We now turn to the second claim. The handler that enters window ω ≥ 2 (line 44) fires only when current window i equals ω − 1; it then increments current window i to ω (line 45) and enters window ω (line 46). If ω − 1 = 1, then current window i = 1 was set at initialization (line 14), which coincides with pi entering window 1 at startup (line 30). If ω − 1 ≥ 2, then current window i reached ω − 1 exclusively by being incremented at line 45; this increment executes in the same handler that enters window ω − 1 (line 46). In both cases, pi must have previously entered window ω − 1. ⊓ ⊔ For every correct validator pi and every window ω ∈ N≥1 that pi enters, we define the following set of slots: slotsi (ω) := {s ∈ Slot : pi schedules the opening of s upon entering window ω}. Concretely, slotsi (1) consists of the W slots scheduled to be opened at startup (lines 31–33). For ω ≥ 2, slotsi (ω) consists of the W slots scheduled to be opened in the loop at lines 48–50. 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 44) and then extracts the slot whose number is the median over all slot numbers in the vector (line 47). 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. Proposition 7. For every correct validator pi and every window ω ∈ N≥2 , the following holds: – If ω = 2 and pi decides slot s from ACS[2], then s.number > W . – If ω > 2 and pi decides slot s from ACS[ω] and slot s′ from ACS[ω − 1], then s.number ≥ s′ .number + W. Proof. We first address the case ω = 2. No correct validator proposes to ACS[2] a slot with number ≤ W . To see this, observe that a correct validator pk proposes to ACS[2] only via the rule at line 37, which fires when ready for next window() returns true. At that point, s⋆ is computed as the first slot whose starting time is at least the current local time (line 39). If s⋆ .number ≤ last k [1].number (line 40), the guard at line 41 reassigns s⋆ to the slot with number last k [1].number + 1. Crucially, last k [1].number = W always holds, since last k [1] is set exactly once (upon entering window 1), at line 34, to the slot with number W . Hence, every correct proposal to ACS[2] carries a slot number of at least W + 1. Since the decided slot number is at least the minimum slot number among all correct proposals, we obtain s.number ≥ W + 1, establishing the first point. We now address the case ω > 2. First, we establish that no correct validator proposes to ACS[ω] a slot with number < s′ .number + W . A correct validator pk proposes to ACS[ω] only via the rule at line 37, which fires when ready for next window() returns true. At this point, current window k + 1 = ω (line 42), so current window k = ω − 1 ≥ 2. Since current window k is incremented only at line 45, pk must have previously decided from ACS[ω − 1] (line 44). By the agreement property of ACS[ω − 1], every correct validator that decides from ACS[ω − 1] does so with slot s′ ; hence, line 51 sets last k [ω − 1] to the slot with number s′ .number + W − 1. Thus, when pk computes s⋆ at line 39, if s⋆ .number ≤ last k [ω − 1].number = s′ .number + W − 1 (line 40), line 41 reassigns s⋆ to the slot with number s′ .number + W . Hence, every correct proposal to ACS[ω] carries a slot number of at least s′ .number + W . Since the decided slot number is at least the minimum slot number among all correct proposals, we obtain s.number ≥ s′ .number + W , establishing the second point. ⊔ ⊓ 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. Proposition 8. For every correct validator pi and every window ω ∈ N≥1 that pi enters, the following holds: – If ω = 1, then slotsi (1) = {s ∈ Slot : s.number ≤ W }. – If ω ≥ 2, let sω denote the slot decided by pi from ACS[ω], and let sω−1 denote the slot with the largest number in slotsi (ω − 1). Then, sω .number > sω−1 .number, and moreover: slotsi (ω) = {s ∈ Slot : s.number ∈ [sω .number, sω .number + W − 1]}. Proof. The first point follows directly from the startup handler (lines 31–32), which schedules the opening of exactly the slots with number in [1, W ]. 53
We now prove the second point. Fix any window ω ≥ 2 that pi enters. We first observe that last i [ω −1] equals sω−1 , the largest slot in slotsi (ω − 1). Indeed, if ω − 1 = 1, then line 34 sets last i [1] to the slot with number W , which is exactly the largest slot in slotsi (1) = {s : s.number ≤ W }. If ω − 1 ≥ 2, then line 51 sets last i [ω − 1] to the largest of the W slots opened upon entering window ω − 1 (lines 48–50), which is exactly the largest slot in slotsi (ω − 1). Upon activating line 44 for ACS[ω], pi opens every slot with number in [sω .number, sω .number + W − 1] (line 48). By Proposition 7, sω .number > sω−1 .number, establishing the ordering claim. Let s′ be the slot decided from ACS[ω], so sω = s′ ; the largest slot of slots(ω − 1) has number ′ sω−1 .number + W − 1, where s′ω−1 is the slot decided from ACS[ω − 1]. By Proposition 7, s′ .number ≥ ⊔ ⊓ s′ω−1 .number + W > s′ω−1 .number + W − 1 = sω−1 .number, establishing the ordering claim. For each correct validator pi and each slot s, we define windowi (s) to be the window ω to which s belongs, that is, the window ω with s ∈ slotsi (ω). If no such window exists, we set windowi (s) = ⊥. By Proposition 8, whenever such a window exists, it is unique; hence, windowi (s) is well-defined. We now establish that no two correct validators disagree on the window to which a slot belongs. Proposition 9. For every two correct validators pi and pj and every slot s, if windowi (s) ̸= ⊥ and windowj (s) ̸= ⊥, then windowi (s) = windowj (s). Proof. If s.number ≤ W , both windows equal 1, so the claim holds trivially. Thus, assume s.number > W . By Proposition 6, correct validators enter windows in increasing order. Therefore, validator pi (resp., pj ) activates the rule at line 44 for ACS[2], . . . , ACS[windowi (s)] (resp., ACS[2], . . . , ACS[windowj (s)]) in increasing order. The agreement property of each ACS primitive together with Proposition 8 then gives windowi (s) = windowj (s). ⊔ ⊓ Integrity. We now prove the integrity property specified in Module 2, which ensures that each correct validator opens each slot at most once, and that no slot is opened before its starting time. Lemma 11 (Integrity). Conductor (Algorithm 7) satisfies integrity. Proof. Fix a correct validator pi and a slot s. By construction of the schedule opening function (line 27), pi does not open s before time s.deadline − ∆. It remains to show that pi opens s at most once. We distinguish two cases: – If windowi (s) = ⊥, then pi never opens s, and the claim holds trivially. – Otherwise, let ω = windowi (s), so that s ∈ slotsi (ω). By Proposition 6, pi enters window ω at most once. Hence, pi opens s exactly once in this case. In either case, pi opens s at most once, establishing the lemma. ⊔ ⊓ 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. Proposition 10. For every correct validator pi and every two slots s, s′ with s.number < s′ .number, if pi schedules the opening of both s and s′ , then it schedules the opening of s′ only after having previously scheduled the opening of s. Proof. Since pi schedules the opening of both s and s′ , we have windowi (s) ̸= ⊥ and windowi (s′ ) ̸= ⊥. Moreover, since s.number < s′ .number, Proposition 8 gives windowi (s) ≤ windowi (s′ ). We distinguish two cases: – windowi (s) = windowi (s′ ). Both slots are scheduled to be opened upon entering this common window, within the loop that processes slots in strictly increasing order of slot number (line 31 for window 1, line 48 otherwise); since s.number < s′ .number, pi schedules the opening of s before that of s′ . – windowi (s) < windowi (s′ ). By Proposition 6, pi enters window windowi (s) before window windowi (s′ ); as s is scheduled upon entering the former and s′ upon entering the latter, pi schedules the opening of s before that of s′ . ⊔ ⊓ We are now ready to prove that Conductor satisfies monotonicity (see Module 2), which guarantees that correct validators open slots in strictly increasing order of slot number. Lemma 12 (Monotonicity). Conductor (Algorithm 7) satisfies monotonicity. 54
Proof. Fix any correct validator pi and any two slots s and s′ that pi opens. Without loss of generality, let s′ .number > s.number. Since s′ .number > s.number, the definition of slots implies s′ .deadline > s.deadline (see Section A). By Proposition 10, pi schedules the opening of s prior to scheduling the opening of s′ . We distinguish two cases. – Suppose pi opens s at the moment of scheduling its opening (i.e., it does not wait for s’s starting time). In this case, when opening s′ (which cannot occur before the scheduling of its own opening), pi has already opened s. – Suppose pi opens s after scheduling its opening. Hence, pi opens s at time s.deadline − ∆ (line 27). In this case, when opening s′ , which cannot occur before time s′ .deadline − ∆ > s.deadline − ∆ (line 27), pi has already opened s. ⊔ ⊓ Boundedness. We say that a correct validator pi is in window ω ∈ N≥1 from the moment it enters window ω until the moment it enters the next window (which is ω+1, by Proposition 6). 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 opened i . Proposition 11. For every correct validator pi and every window ω ∈ N≥1 , while pi is in window ω, the local variable opened i contains exactly ω · W slots. Proof. We proceed by induction on ω. Base case (ω = 1). Validator pi enters window 1 at startup, upon which the startup handler adds exactly the slots with number in [1, W ] to opened i (lines 31–33). As opened i is modified only upon entering a new window, the count remains 1 · W throughout the time pi is in window 1. Inductive step (ω ≥ 2). By the inductive hypothesis, |opened i | = (ω − 1) · W while pi is in window ω − 1. Validator pi enters window ω upon activating the rule at line 44, where the loop at lines 48–50 adds exactly W fresh slots (by Proposition 8) to opened i , yielding |opened i | = (ω − 1) · W + W = ω · W . Since opened i is modified only upon entering a new window, the count remains ω · W throughout the time pi is in window ω. ⊔ ⊓ We are now ready to prove that Conductor satisfies (2W − p)-boundedness (see Module 2), which guarantees that at most 2W − p slots are simultaneously open (that is, opened but not yet completed) at any point in time. Lemma 13 (Boundedness). Conductor (Algorithm 7) satisfies (2W − p)-boundedness. Proof. Fix a correct validator pi and a time t. Let s1 < s2 < · · · < sk be the slots in opened i at time t, ordered by slot number, and let j ⋆ be the largest index such that pi has completed each of s1 , . . . , sj ⋆ by time t (with j ⋆ = 0 if no such index exists). It suffices to show that k − j ⋆ ≤ 2W − p, i.e., that at most 2W − p of the slots s1 , . . . , sk remain uncompleted by pi at time t (since every slot pi has opened has been previously recorded in opened i ). Let ω = windowi (sk ) be the window of slot sk . We know that pi is in window ω at time t. Let us now distinguish two cases: – Suppose ω = 1. Then, sk .number ≤ W , so k ≤ W , and the bound k − j ⋆ ≤ k ≤ W ≤ 2W − p holds immediately. – Suppose ω ≥ 2. Validator pi enters window ω upon activating the rule at line 44 for ACS[ω], which fires only when ready for next window() returns true. By the readiness condition (line 23), at the moment pi enters window ω, at most the last W − p slots in opened i (by slot number) remain uncompleted. Just before entering window ω, validator pi was in window ω − 1, so |opened i | = (ω − 1)W by Proposition 11. Upon entering window ω, validator pi adds the W slots of window ω to opened i (lines 48–50). Hence, while pi is in window ω, at most (W − p) + W = 2W − p of the slots in opened i remain uncompleted, and therefore k − j ⋆ ≤ 2W − p, establishing the lemma in this case. ⊔ ⊓ 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 (Algorithm 1), whose finalization supplies precisely the completion guarantees that these two properties rely on. 55
We begin with totality. In fact, we establish a stronger, quantitative form of it — ∆tot -totality: if a correct validator opens a slot s at some time t, then every correct validator opens s by time max(t, GST)+ ∆tot . Here, ∆tot = 2∆ is Chorus’s totality latency (by Proposition 4), 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 ∆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 ω only once enough of the earlier windows have completed, so the openings of window ω are synchronized across correct validators — within ∆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 ∆tot — that ratchets forward: the first window satisfies it outright, and if every window before ω satisfies it, then the openings of window ω are ∆tot -synchronized, which in turn makes window ω satisfy the guarantee. Chaining this implication across all windows yields ∆tot -totality for every slot. Let W denote the set of windows entered by at least one correct validator. By Proposition 8 and the agreement property of the underlying ACS instances, any two correct validators that both enter a window ω agree on its slot set, i.e., slotsi (ω) = slotsj (ω). We may therefore drop the subscript and write slots(ω) for this common set throughout the rest of the proof. We name the aforementioned per-window guarantee — a window’s totality precondition — explicitly. Definition 5 (Totality precondition). A window ω ∈ W satisfies the totality precondition if and only if, for every slot s ∈ slots(ω), if a correct validator completes s at time t, then every correct validator completes s by time max(t, GST) + ∆tot . We first show that window 1 satisfies the totality precondition. Proposition 12. When Conductor is run within Cadence, window 1 satisfies the totality precondition. Proof. Consider any slot s ∈ slots(1), that is, any slot with s.number ≤ W , and suppose some correct validator pi completes s at a time t. Within Cadence, a validator records a completion only upon finalizing the corresponding slot consensus instance, and the handler that does so fires only for slots it has already opened (line 20 of Algorithm 1); hence pi finalizes S[s] at time t, having already opened s. At startup, every correct validator schedules the opening of s (lines 31–32) and thus opens it precisely at its starting time s.deadline − ∆ ≤ t (line 27). By the totality of Chorus (Proposition 4), every correct validator finalizes S[s] by time max(t, GST) + ∆tot ; since each has by then already opened s, the guard on Cadence’s finalization handler (line 20 of Algorithm 1) is satisfied, so each completes s by time max(t, GST) + ∆tot . ⊔ ⊓ We now turn to the remaining windows. For a window ω > 1, we cannot guarantee ∆tot -synchronized openings outright; instead, the following proposition establishes them conditionally, assuming that every earlier window already satisfies the totality precondition. Proposition 13. Suppose Conductor is run within Cadence, and let ω > 1 be a window in W. If every window ω ′ < ω satisfies the totality precondition, then the following holds for every slot s ∈ slots(ω): if a correct validator opens s at some time t, then every correct validator opens s by time max(t, GST) + ∆tot . Proof. By hypothesis, every window ω ′ < ω satisfies the totality precondition (Definition 5). Let pi be a correct validator that opens slot s ∈ slots(ω) at time t. By line 27, t ≥ s.deadline − ∆. Validator pi schedules the opening of s upon entering window ω, at some time t′ ≤ t. By Proposition 6, pi has previously entered all windows smaller than ω, which implies that pi has activated the rule at line 44 for ACS[ω ′ ], for all ω ′ ∈ [2, ω], by time t′ . We now prove by induction on ω ′ that, for each window ω ′ ∈ [2, ω], every correct validator enters window ω ′ by time max(t′ , GST) + ∆tot . Base case (ω ′ = 2). Since pi has entered window 2 by time t′ , the following two facts hold: (1) pi decides from ACS[2] by time t′ ; and (2) pi has completed every slot of window 1 except possibly the last W − p (by slot number) by time t′ . Consider any correct validator pj . By the ∆-totality property 56
of ACS[2], pj decides from ACS[2] by time max(t′ , GST) + ∆. Moreover, since window 1 satisfies the totality precondition (Definition 5), every slot of window 1 that pi completes by t′ is completed by pj by time max(t′ , GST) + ∆tot ; hence, pj likewise has all but the last W − p slots of window 1 completed by that time. Therefore, both conditions for activating the rule at line 44 for ACS[2] hold at pj by time max(t′ , GST) + ∆tot (as ∆tot = 2∆, the later of the two bounds is max(t′ , GST) + ∆tot ), which implies that pj enters window 2 by this time. Inductive step (ω ′ − 1 → ω ′ ). Since pi has entered window ω ′ by time t′ , the following two facts hold: (1) pi decides from ACS[ω ′ ] by time t′ ; and (2) pi has completed every slot in windows 1, . . . , ω ′ − 1 except possibly the last W − p by time t′ . Consider any correct validator pj . First, by the inductive hypothesis, pj enters window ω ′ − 1 by time max(t′ , GST) + ∆tot , so that current window j = ω ′ − 1 at that point (which is required for pj to subsequently activate the rule at line 44 for ACS[ω ′ ]). By the ∆-totality property of ACS[ω ′ ], pj decides from ACS[ω ′ ] by time max(t′ , GST) + ∆. Finally, since windows 1, . . . , ω ′ − 1 all satisfy the totality precondition, every slot that pi completes by t′ is completed by pj by time max(t′ , GST) + ∆tot ; hence, pj likewise has all but the last W − p slots completed by that time. Therefore, both conditions for activating the rule at line 44 for ACS[ω ′ ] hold at pj by time max(t′ , GST) + ∆tot (again using ∆tot = 2∆), completing the induction. Applying the claim with ω ′ = ω, every correct validator pj enters window ω at some time t⋆ ≤ max(t′ , GST) + ∆tot ≤ max(t, GST) + ∆tot , and thereby schedules the opening of s (since s ∈ slots(ω)). We distinguish two cases. – If t⋆ ≥ s.deadline − ∆, then pj opens s at time t⋆ ≤ max(t, GST) + ∆tot , as required. – If t⋆ < s.deadline − ∆, then pj opens s at time s.deadline − ∆. Since t ≥ s.deadline − ∆, the claim holds in this case as well. ⊔ ⊓ 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. Proposition 14. When Conductor is run within Cadence, the following holds for every slot s. Suppose the opening of s is ∆tot -total: if a correct validator opens s at some time t, then every correct validator opens s by time max(t, GST) + ∆tot . Then the completion of s is ∆tot -total as well: if a correct validator completes s at some time t′ , then every correct validator completes s by time max(t′ , GST) + ∆tot . Proof. Let pi be a correct validator that completes s at time t′ . Within Cadence, a validator records a completion only upon finalizing the corresponding slot consensus instance, and the handler that does so fires only for slots it has already opened (line 20 of Algorithm 1); hence pi finalizes S[s] at time t′ , having opened s at some time t ≤ t′ . Applying the assumption to pi ’s opening of s at time t, all correct validators open s by time max(t, GST) + ∆tot ≤ max(t′ , GST) + ∆tot . By the totality of Chorus (Proposition 4), every correct validator finalizes S[s] by time max(t′ , GST) + ∆tot ; since each has by then already opened s, the guard on Cadence’s finalization handler (line 20 of Algorithm 1) is satisfied, so each completes s by time max(t′ , GST) + ∆tot . ⊓ ⊔ We are now ready to prove that Conductor satisfies ∆tot -totality when run within Cadence. Lemma 14 (Totality). When run within Cadence (Algorithm 1), Conductor (Algorithm 7) satisfies totality. More specifically, for every slot s, if a correct validator opens s at some time t, then every correct validator opens s by time max(t, GST) + ∆tot . Proof. Consider any slot s that a correct validator pi opens, and let ω = windowi (s). We first show, by strong induction on ω ′ , that every window ω ′ < ω satisfies the totality precondition (Definition 5). For ω ′ = 1, this is ensured by Proposition 12. For ω ′ ≥ 2, the induction hypothesis gives that every window smaller than ω ′ satisfies the totality precondition; hence Proposition 13 applies and makes the opening of every slot in slots(ω ′ ) ∆tot -total, whereupon Proposition 14 shows that ω ′ itself satisfies the totality precondition. It remains to establish that the opening of s is ∆tot -total. If ω = 1, then s.number ≤ W , and every correct validator schedules the opening of s at startup, opening it exactly at its starting time s.deadline−∆ (lines 31–32, via line 27); since all do so at the same time, the opening of s is ∆tot -total. Otherwise ω > 1, and since every window ω ′ < ω satisfies the totality precondition, Proposition 13 applied to ω shows that the opening of s ∈ slots(ω) is ∆tot -total. ⊔ ⊓ Combining the two halves of the recursion — that openings are ∆tot -total and that ∆tot -total openings yield ∆tot -total completions — we obtain that completions, too, propagate within ∆tot for every slot. 57
Corollary 1. When run within Cadence (Algorithm 1), Conductor satisfies ∆tot -totality of completions: for every slot s, if a correct validator completes s at some time t, then every correct validator completes s by time max(t, GST) + ∆tot . Proof. By Lemma 14, the opening of every slot s is ∆tot -total. Proposition 14 then yields that the completion of s is ∆tot -total as well. ⊔ ⊓ 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 ℓchorus — the parameter for which, if all correct validators start participating by some time t′ , then all finalize by time max(t′ , GST) + ℓchorus . Proposition 15. When run within Cadence, the following holds for every slot s: if a correct validator opens s at some time t, then it completes s by time max(t, GST) + ∆tot + ℓchorus . Proof. Let pi be a correct validator that opens slot s at time t; upon doing so, it starts participating in S[s] (line 17 of Algorithm 1). By the ∆tot -totality of Conductor (Lemma 14), every correct validator opens s — and hence starts participating in S[s] — by time max(t, GST) + ∆tot . The ℓchorus -termination of Chorus (Lemma 10) therefore guarantees that every correct validator finalizes S[s] — and thus completes s (line 22 of Algorithm 1) — by time max(t, GST) + ∆tot + ℓchorus . ⊓ ⊔ Recall that Φoc = ℓchorus + ∆tot , which is exactly the open-to-complete bound established just above (Proposition 15). 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. Proposition 16. Every correct validator eventually enters every window ω ∈ N≥1 . Proof. We prove the proposition by induction on the window number ω. Base case (ω = 1). This holds trivially: every correct validator enters window 1 upon starting the protocol (line 30). Inductive step (ω − 1 → ω). By the inductive hypothesis, every correct validator eventually enters window ω −1. We first show that every correct validator eventually decides from ACS[ω], distinguishing two cases: – Some correct validator decides from ACS[ω]. By the totality property of ACS[ω] (Module 4), every correct validator then decides from ACS[ω]. – No correct validator decides from ACS[ω]. Then no correct validator ever enters a window greater than ω − 1: entering window ω requires activating the rule at line 44 for ACS[ω], which cannot fire if no correct validator decides from ACS[ω]; and, by Proposition 6, entering any larger window requires first entering ω. Fix any correct validator pj . By the inductive hypothesis it enters window ω − 1, and as it never advances beyond it, current window j = ω − 1 from then on; by Proposition 11, opened j then contains exactly (ω − 1)W slots. Each such slot was opened by pj (line 32 or line 49), so by Proposition 15, pj eventually completes it. In particular, pj eventually completes the first (ω − 2)W + p slots of opened j (ordered by slot number), at which point ready for next window() returns true (line 23). Once it does, pj proposes to ACS[ω] (lines 37–42), if it has not already. Hence every correct validator proposes to ACS[ω], so by the termination property of ACS[ω] (Module 4) every correct validator decides from it. In either case, every correct validator eventually decides from ACS[ω]. It remains to show that every correct validator pi eventually enters window ω. While pi is in window ω − 1 (i.e., current window i = ω − 1), it enters window ω upon activating the rule at line 44 for ACS[ω] (line 46), which fires once its two conditions hold simultaneously: (1) pi decides from ACS[ω], which it eventually does, as just shown; and (2) ready for next window() returns true (line 23), which holds eventually — by the argument of the second case above, via Proposition 15 — and remains so, since opened i does not change while pi is in window ω − 1 and completed slots only accumulate. Therefore, both conditions eventually hold at pi , so pi activates the rule at line 44 for ACS[ω] and enters window ω (line 46). ⊔ ⊓ 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 7–10): 58
– (p − 1)τ + Φoc + ℓ ≤ W τ (line 7); – (p − 1)τ + Φoc ≤ (W − 1)τ (line 8); – ∆ < ℓ (line 9); and – ∆tot + ℓ ≤ (p − 1)τ (line 10). Recall that p ∈ {0, . . . , W − 1} is the readiness threshold, W ∈ N≥1 the window size, ℓ the latency of the ACS primitive, Φoc = ℓchorus + ∆tot the open-to-complete delay, and ∆ the known upper bound on message delays after 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 τ , 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 Proposition 16, every correct validator enters every window ω ∈ N≥1 , so slotsi (ω) is defined for every correct validator pi and every window ω. By Proposition 8, for every window ω, the common set slots(ω) consists of exactly W slots with consecutive slot numbers. For every window ω and index x ∈ [1, W ], we write slot(ω, x) for the x-th slot of slots(ω), ordered by slot number. Then, for every window ω and index x ∈ [1, W ], we denote by Tx (ω) the starting time of slot(ω, x), that is, Tx (ω) = s.deadline − ∆,
where s = slot(ω, x).
Since consecutive slots are separated by exactly τ time units, Tx (ω) = T1 (ω)+(x−1)τ , for every x ∈ [1, W ]. Finally, we call a window ω a post-GST window if and only if T1 (ω) ≥ GST, and a pre-GST window otherwise. We now show that every correct validator enters each window within ∆tot + ℓ of its scheduled start (or of GST, if that is later). Proposition 17. Let ω be any window. Then, every correct validator enters window ω by time max(T1 (ω), GST) + ∆tot + ℓ. Proof. If ω = 1, every correct validator enters window 1 at time 0 = T1 (1), so the proposition holds trivially. Assume henceforth that ω > 1. Suppose first that some correct validator enters window ω by time max(T1 (ω), GST) + ∆. The proof of Proposition 13 shows that the entry of one correct validator into window ω propagates to every correct validator within ∆tot time. Hence, every correct validator enters window ω by time max(T1 (ω), GST) + ∆ + ∆tot , which is earlier than max(T1 (ω), GST) + ∆tot + ℓ (as ∆ < ℓ, line 9); the claim follows. We may therefore assume that no correct validator enters window ω by time max(T1 (ω), GST) + ∆; by Proposition 6, no correct validator enters any window ≥ ω by that time. Due to Proposition 16, every correct validator enters window ω, and hence decides from ACS[ω] (line 44); by Proposition 8, the decided slot is slot(ω, 1), whose starting time is T1 (ω). By the validity property of ACS[ω], at least f + 1 correct validators proposed to ACS[ω], with median proposal slot(ω, 1); in particular, some correct validator pk proposed a slot s′ with s′ .number ≤ slot(ω, 1).number by time T1 (ω) (line 42). A correct validator proposes to ACS[ω] only when ready for next window() returns true (line 37). Since current window k = ω − 1 when pk proposes, opened k contains exactly (ω − 1)W slots (Proposition 11), so pk has completed the first (ω − 2)W + p of them by time T1 (ω). Due to Corollary 1, every correct validator completes each of these (ω − 2)W + p slots by time max(T1 (ω), GST) + ∆tot . Moreover, every correct validator has entered window ω − 1 by that time (follows from the proof of Proposition 13). Therefore, ready for next window() returns true at every correct validator, and each proposes to ACS[ω] by time max(T1 (ω), GST) + ∆tot . By the termination property of ACS[ω], every correct validator then decides from ACS[ω] by time max(T1 (ω), GST) + ∆tot + ℓ, which proves the proposition. ⊓ ⊔ We now establish the key timing invariant underlying recovery: if every correct validator enters a post-GST window ω by Tp (ω), then every correct validator opens window ω + 1 “on time” and there are no “gaps” between the two windows. Proposition 18. Fix any post-GST window ω. If every correct validator enters window ω by time Tp (ω), then: – slot(ω + 1, 1).number = slot(ω, W ).number + 1; and – every correct validator enters window ω + 1 by time T1 (ω + 1). 59
Proof. We prove each point in turn. Point 1. We establish the first point by showing that every correct validator that proposes to ACS[ω + 1] does so with a slot s⋆ with s⋆ .number = slot(ω, W ).number + 1. Suppose, for contradiction, that some correct validator pi proposes a slot s ̸= s⋆ . Note that validator pi opens each of the first p slots of window ω by time Tp (ω) (at line 28, as each slot is opened either when scheduled or at the slot’s starting time). For pi to propose to ACS[ω + 1] at line 42, ready for next window() must return true (line 37). By Proposition 15, pi completes the first (ω − 1)W + p open slots by time Tp (ω) + Φoc , at which point ready for next window() returns true (line 23), triggering the rule at line 37. We now verify that the trigger fires before slot(ω, W ).deadline − ∆. By definition, Tp (ω) = T1 (ω) + (p − 1)τ and slot(ω, W ).deadline − ∆ = T1 (ω) + (W − 1)τ . Hence, Tp (ω) + Φoc = T1 (ω) + (p − 1)τ + Φoc . By assumption at line 8, (p − 1)τ + Φoc ≤ (W − 1)τ , so: Tp (ω) + Φoc = T1 (ω) + (p − 1)τ + Φoc ≤ T1 (ω) + (W − 1)τ = TW (ω) = slot(ω, W ).deadline − ∆. Consequently, pi selects s⋆ with s⋆ .number = slot(ω, W ).number + 1 (lines 39–41) and invokes ACS[ω + 1].propose(s⋆ ) (line 42), contradicting our assumption. To conclude the first point, by the validity property of ACS[ω + 1], at least f + 1 correct proposals appear in the decided set. Hence, the median slot number (line 47) equals slot(ω, W ).number + 1, establishing slot(ω + 1, 1).number = slot(ω, W ).number + 1. Point 2. We first show that every correct validator decides from ACS[ω + 1] by time Tp (ω) + Φoc + ℓ. Since Tp (ω) = T1 (ω) + (p − 1)τ and (p − 1)τ + Φoc + ℓ ≤ W τ (line 7), we have Tp (ω) + Φoc + ℓ ≤ T1 (ω) + W τ = T1 (ω + 1), so this suffices to establish the claim. (Recall that every correct validator completes the first (ω − 1)W + p open slots by time Tp (ω) + Φoc ; hence ready for next window() returns true strictly before time Tp (ω) + Φoc + ℓ.) We distinguish two cases. – Suppose some correct validator decides from ACS[ω +1] by time Tp (ω)+Φoc . By the totality property of ACS[ω + 1], every correct validator then decides by time Tp (ω) + Φoc + ∆ < Tp (ω) + Φoc + ℓ, and the claim holds. – Otherwise, no correct validator decides from ACS[ω + 1] by time Tp (ω) + Φoc . In particular, no correct validator has activated line 44 for ACS[ω + 1] by that time, so no correct validator has entered any window larger than ω (line 46). By Proposition 15, every correct validator completes all (ω − 1)W + p open slots by time Tp (ω)+Φoc , at which point ready for next window() returns true (line 23), triggering each correct validator to propose to ACS[ω + 1] (lines 37–42). Since ACS[ω + 1] has latency ℓ, every correct validator decides by time Tp (ω) + Φoc + ℓ, and the claim holds. ⊔ ⊓ Next, we prove that from the second post-GST window, the protocol “runs smoothly”. Proposition 19. Let ω ⋆ denote the smallest post-GST window. Then, for every window ω > ω ⋆ , the following holds: – slot(ω, 1).number = slot(ω − 1, W ).number + 1; and – every correct validator opens every slot s ∈ slots(ω) at time s.deadline − ∆. Proof. We proceed by induction on ω, with base case ω = ω ⋆ + 1. By Proposition 17, every correct validator enters window ω ⋆ by time T1 (ω ⋆ ) + ∆tot + ℓ. Since ∆tot + ℓ ≤ (p − 1)τ , every correct validator enters window ω ⋆ by time Tp (ω ⋆ ). Therefore, Proposition 18 gives us the following for window ω = ω ⋆ + 1: (1) slot(ω ⋆ + 1, 1).number = slot(ω ⋆ , W ).number + 1, and (2) every correct validator enters window ω ⋆ + 1 by time T1 (ω ⋆ + 1), which indeed implies that every correct validator opens every slot s ∈ slots(ω ⋆ + 1) at its starting time s.deadline − ∆ (line 27). The inductive step is identical: applying Proposition 18 at each subsequent window yields the claim for all ω > ω ⋆ + 1. ⊔ ⊓ Proposition 19 tells us that the protocol runs smoothly from the second post-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-GST window can start. To this end, we bound when the first post-GST window can arise. Proposition 20. Let ω denote the smallest post-GST window. Then: T1 (ω) − GST ≤ W τ. Proof. If ω = 1, then T1 (ω) = 0 = GST, so the proposition holds trivially. Hence, assume that ω > 1. Since ω is the first (i.e., the smallest) post-GST window and ω > 1 and correct validators enter window 1 at time 0, we have that there exists a pre-GST window. Let ω ⋆ denote 60
the greatest pre-GST window. Since ω ⋆ is the greatest pre-GST window and ω is the first post-GST window, we have ω = ω ⋆ + 1. We show that every correct validator pi that proposes to ACS[ω] (line 42) does so with a slot whose starting time is at most GST + W τ . To propose to ACS[ω], pi must have previously entered window ω − 1 = ω ⋆ (line 37). By Proposition 17, pi enters window ω ⋆ by time GST + ∆tot + ℓ. Since ω ⋆ is a pre-GST window, its first slot starts before GST, and since consecutive slots are τ apart, pi opens the first p slots of window ω ⋆ by time GST + (p − 1)τ (line 28). By Proposition 15, pi completes the first (ω ⋆ − 1)W + p slots by time GST + (p − 1)τ + Φoc , which implies that pi proposes to ACS[ω] by time GST + (p − 1)τ + Φoc . The proposed slot s⋆ is determined at lines 39–41; we show its starting time is strictly less than GST + W τ . We distinguish two cases based on whether the guard at line 40 holds. If it does not hold, pi keeps s⋆ as the first slot whose starting time meets or exceeds the current local time (line 39); since pi proposes by time GST + (p − 1)τ + Φoc , the starting time of s⋆ is strictly less than GST + (p − 1)τ + Φoc + τ = GST + pτ + Φoc , which is at most GST + W τ by assumption (2) (line 8), since (p − 1)τ + Φoc ≤ (W − 1)τ implies pτ + Φoc ≤ W τ . If the guard holds, pi reassigns s⋆ to the slot immediately after the last slot of window ω ⋆ (line 41); since ω ⋆ is a pre-GST window, its last slot has starting time strictly less than GST + (W − 1)τ , and hence s⋆ has starting time strictly less than GST + W τ . Hence, by the median rule at line 47, T1 (ω) ≤ GST + W τ , which proves the proposition. ⊓ ⊔ We are finally ready to prove Conductor’s recovery. Lemma 15 (Recovery). When run within Cadence (Algorithm 1), Conductor (Algorithm 7) satisfies (2W τ )-recovery. Proof. Fix a correct validator pi . Let ω denote the first post-GST window. Consider any slot s opened via ACS[ω ′ ], for some ω ′ ≥ ω +1. By Proposition 19, pi opens s and it does so precisely at time s.deadline−∆. Notably, every slot with starting time ≥ T1 (ω + 1) is resolved by ACS[ω ′ ], for some ω ′ ≥ ω + 1 (by Proposition 8). By Proposition 19, there are no gaps between windows after ω, and by Proposition 20, T1 (ω) − GST ≤ W τ ; since each window spans W τ time, we have that T1 (ω + 1) − GST ≤ 2W τ , which concludes the lemma. ⊔ ⊓
61