This interactive paper companion includes a PDF viewer, a Q&A assistant, a tutorial, proof visualizations and a code browser, all of which need a larger screen.
This page is the entry point of the artifact. The PDF tab holds the submitted paper, the panel on the left answers questions about it, and the remaining tabs hold the interactive material. Everything on this page follows the paper as submitted; where a number comes from a specific testbed, the testbed is named.
Existing Byzantine atomic broadcast protocols either assume partial synchrony and a commonly recognized leader, or, under full asynchrony, run a step that makes proposals visible to a quorum before agreement begins. Validated Strong Consensus (VSC) is an asynchronous BFT abstraction that decides without that step: nodes holding different partial views of arbitrarily many candidates decide a common value. Realizing VSC through multi-valued validated Byzantine agreement reintroduces the step as a structural cost, which the paper states as an input-supply gap with an accompanying cost proposition.
VELA realizes VSC as an asynchronous Byzantine atomic broadcast protocol for asymmetric proposal visibility, tolerating f < N/3 Byzantine faults. A vote carries the references a receiver needs to reconstruct the evidence the voter used, so the receiver replays the voter's choice locally instead of relying on a globally aligned input set. Locally justified votes progressively eliminate incompatible candidates, and a threshold coin gives almost-sure convergence when the deterministic rules stall under adversarial scheduling.
A vote graph is reconstructed from a received vote by following the vote hashes it references. If the graph holds two votes from the same node at some height, that node's votes are discarded from the earliest such height upward within that graph. From the graph a node derives a direct-vote counter and a cumulative counter, the cumulative counter of a block summing the direct votes over its whole branch.
A compliant vote by node j at vote height k is a commit vote for the height-h block B'h on its chain when both clauses hold:
The margin g is the worst case by which enlarging a graph can erode a lead: at most 2f per vote height, since up to f Byzantine votes counted for the leader can vanish once equivocation is exposed and up to f missing honest votes can appear for a rival. Over heights h to k-1 that is 2(k-h)f. VELA commits at the adaptive gap, which is at most that bound and charges only the corrupted senders not yet exposed as equivocators in the committing node's own graph; it reaches 2(k-h)f at a full quorum with no exposed equivocation. Safety is unchanged, because the safety proofs use the gap only through the two-graph swing bound of the commit-exclusivity lemma.
Node i declares B'h final when it has already finalized the parent Bh-1 and B'h descends from it, and when it holds commit votes for B'h from a set of at least N-f nodes whose coin label excludes height h. That set is the witness set. A vote that applied the coin at some other unfinalized height still counts.
A commit vote binds only the next vote height. When one of the N-f parents of a vote, all of which sit at vote height k-1, is a commit vote for an alive block, the voter must select that block. Commit votes deeper in the graph carry no mandate, and a parent whose sender is pruned as an equivocator gives none and does not make its block alive. Commit exclusivity makes the bound block unique, since no two honest nodes hold commit votes for different blocks at one vote height. A block that has gathered its witness set stays selected afterwards anyway, because from the next vote height on no sibling receives a compliant vote and so no sibling is alive in any graph.
A node gives a received vote no verdict until it holds the block that vote refers to and the prior votes the vote references. Until then it buffers the vote and requests the missing objects. A block alive in an honest node's graph has an honest holder, so any honest node that needs it can obtain it; a block withheld from every honest node is alive in no honest graph, so no honest node selects it or waits on it. A negative verdict is therefore never final while a request is outstanding, which is why an implementation may cache a positive verdict but must not cache a negative one.
The paper numbers five algorithms: 1 Block Proposal, 2 Voting Process, 3 Vote Validation, 4 Finality Check, and 5 Leader-Collecting Broadcast.
Under Algorithm 5 a vote is retained by its caster and never pushed. The window leader sends a vote request, at most once per peer per window; a node answers each requester at most once per vote height; and a collector holding N-f votes for a height rebroadcasts one bundle for that height. One collection attempt costs N-1 requests, at most N-1 responses and N-1 bundle messages, so O(N). A height costs O(N) when the number of distinct requesters an honest node answers is O(1), and reaches the quadratic worst case the paper already reports under adversarial scheduling when a linear number of nodes request. Bounding that number by construction would need the receiver to judge which requester is the legitimate collector, which needs a timing assumption the asynchronous model does not grant.
Two measurement campaigns run in this artifact and they are not interchangeable.
The evaluation testbed carries every cross-protocol throughput and retention number: m6i.large instances in us-east-1, eu-west-1, ap-southeast-1 and ap-northeast-1, inter-region RTT about 200 ms, N in {16, 32, 64, 128}, up to 1,024 closed-loop clients submitting batches of 50 Ed25519-signed 256-byte transactions, knee-point throughput, medians over three seeds. At N = 16 the paper reports VELA at 1,486 tx/s with 1.4 s median commit latency, against 2,194 to 2,618 tx/s for Mysticeti, Bullshark and Dumbo-NG, which commit multiple values per epoch. Under S1 with S2 and S3 it reports VELA retaining 85%, 82%, 76% and 68% of benign throughput at N = 16, 32, 64 and 128, with no baseline reaching 10% at N = 128. Adding S4 costs VELA two to three points, 83% at N = 16 and 65% at N = 128, while HotStuff-1, HotStuff-2 and BFT-SMaRt retain at most 8% at N = 16 and at most 0.3% at N = 128.
The 16-region cluster is a separate deployment, one t3.micro per region across 16 regions, median RTT 134 ms, N = 16 only. The paper uses it in the appendix for per-incoming-message validation latency, coin invocation, the S5 results and the block-interval sweep, and it states there that its absolute rates are far below the evaluation testbed and that its purpose is to compare settings against each other. Per incoming message VELA spends 9.8 ms on compliance checking against 1.77 ms for HotStuff-1, the most expensive of the seven protocols and about five and a half times HotStuff's. The coin was invoked in no vote under benign WAN and in none under the delay-budget adversary at any budget from 0 to 2000 ms; under S5 it was invoked in 1.75% of votes, 16 of 914, converging in a mean of 2.63 vote heights and a maximum of 8. The paper reports no cross-protocol throughput or retention for this cluster, and neither does this artifact.
Two anonymous mirrors serve this artifact with scripts enabled: https://45-32-80-76.nip.io/ and, behind a CDN with identical content, https://c37a2b68.e0w0.de/. The Anonymous GitHub website preview has served these pages under a script-blocking sandbox since 2026-09-06, so the interactive tabs and the Q&A do not run there; use a mirror, or download the repository and serve the folder with a local static server.