{"id":"fa73b59e-9ce0-40cf-ac30-abf7a8c0fb7c","arxiv_id":"2504.18649","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Raptr is a BFT consensus protocol whose prefix-voting mechanism commits nested prefixes of proposed blocks, delivering high throughput, near-optimal latency, and robustness to message loss in a 100-replica deployment.","lead":"This paper presents Raptr, a Byzantine fault-tolerant consensus protocol that lets replicas vote on partial blocks, not just whole blocks, so missing data no longer stalls agreement. It reports a 100-replica geo-distributed deployment sustaining 250,000 transactions per second at 755ms latency while staying stable during network glitches.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Safety proof assumes one QC-vote per honest replica per round, but Raptr explicitly allows two QC-votes (timer-based partial, then full-prefix); without a distinct-voter check in VerifyQC, Byzantine aggregators can form quorums below 2f+1 distinct replicas, invalidating Lemma C.1.","rationale":"The reader's weakest assumption pointed at the aggregate signature scheme and the possibility of conflicting votes, which is the right area, but the specific load-bearing gap is more precise: the protocol explicitly allows two QC-votes per replica per round, and the formal proof's quorum intersection treats a QC as containing one vote per distinct replica. If the aggregation scheme accepts two signatures from the same replica on the same block hash with different prefixes, a quorum certificate can be formed with fewer than 2f+1 distinct replicas. Lemma C.1 then no longer guarantees an honest intersection between two quorums, and the entire safety induction in Lemmas C.3-C.5 collapses. This is not a disagreement with the BFT consensus literature; it is an internal inconsistency in the paper's own protocol description and proof. The issue is concrete and testable: either the implementation or the formal VerifyQC must reject duplicate replica IDs, or the protocol should be changed to allow only one QC-vote per round (for example, voting at the maximum prefix available at vote time and not updating). The proposed fix is small, and the protocol's high-level prefix-containment idea may still be salvageable. However, as written, the central safety claim is unsupported. I agree with the conditional verdict but would add this specific correctness condition to the acceptance requirements, alongside the reproducibility and baseline-comparison concerns already raised by the reader.","tokens_in":27753,"tokens_out":10157,"duration_ms":105950,"concrete_test":"Check the public Raptr implementation (github.com/aptos-labs/aptos-core, raptr-public branch) for a distinct-replica check when constructing or verifying a QC's votePrefixes. If no such check exists, run a 7-replica (n=7, f=2) simulation with a Byzantine leader proposing two different blocks to two disjoint honest groups, collecting each honest replica's timer-based partial vote and later full-prefix vote, and attempt to form two valid QCs for different block hashes in the same round using the double-counted votes. If both QCs verify, Lemma C.1 is violated and the prefix-containment safety argument fails. If the code rejects duplicate voters, the paper must still add this assumption to VerifyQC and Lemma C.2 for the proof to be complete.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The weakest point is the interaction between the two-votes-per-round QC rule and the quorum-intersection argument. Algorithm 5 lets a replica QC-vote twice for the same block: once when the QC-Vote timer expires (lines 131-132) with some prefix p < K, and again when all batches are available (lines 133-134) with prefix K. Both votes are multicast. A Byzantine aggregator can retain both signatures. VerifyQC (Algorithm 2, lines 46-47) checks only the aggregate signature over the (replicaId, prefix) tuples and the tuple count (>= ceil((n+f+1)/2)); it does not require replicaIds to be distinct. With a tag-based aggregate scheme such as the simplified no-commit proofs in Section 6.2, the two votes use different key shares and aggregate as if they came from two different virtual signers. Thus a quorum can be built from f Byzantine votes plus as few as ceil((f+1)/2) honest replicas each contributing two votes, i.e., fewer than 2f+1 distinct replicas. Lemma C.1 then does not apply: two such quorums can intersect only in Byzantine replicas. The induction in Lemmas C.3-C.5 and Theorem C.7 relies on an honest overlap to force prefix containment; without it, a Byzantine leader can equivocate and cause conflicting prefixes to be committed. The proof's statement in Lemma C.2 that an honest replica will never sign two QC-votes with different block hashes does not address the two same-hash votes with different prefixes, so the gap is real even if each honest replica votes only for the first block it sees. This is an internal inconsistency between the protocol design (two votes allowed, Section 5.2) and the proof's implicit one-vote-per-replica model.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Raptr, a leader-based BFT state machine replication protocol that augments the Jolteon*/Quorum Store baseline with prefix consensus. Instead of voting only on complete blocks, replicas vote on the longest available prefix of a proposed block; quorum certificates certify the S-th largest prefix among votes, commit certificates commit the minimum certified prefix in a quorum, and the next leader extends the maximum certified prefix. The paper claims a common-case ordering latency of five message delays, high throughput under favorable conditions, and graceful degradation under message loss. It provides full pseudocode, formal safety and liveness proofs in Appendices B and C, and an implementation evaluated on a 100-replica geo-distributed testbed against Shoal++, Mysticeti, Aptos+, and Baby Raptr.","tokens_in":28156,"tokens_out":11952,"duration_ms":125861,"significance":"If the protocol is correct, Raptr would be a significant practical contribution: it aims to eliminate the latency-versus-robustness tradeoff between pessimistic and optimistic data dissemination in BFT SMR while keeping throughput comparable to certified DAG protocols. The paper is commendably concrete: it ships detailed pseudocode, self-contained formal proofs, an open-source implementation, and a large-scale evaluation against externally developed baselines (Mysticeti, Shoal++). The latency breakdown and fault-injection experiments are informative. However, I find a load-bearing gap in the safety argument: the QC verification does not enforce that the votes in a quorum come from distinct replicas, while the protocol explicitly permits two QC-votes per replica per round. A Byzantine aggregator can exploit this to build quorums whose honest intersection is empty, invalidating the formal safety proof. The central idea is likely repairable with a distinct-voter check, but the manuscript as submitted does not establish the claimed Byzantine safety guarantee.","major_comments":[{"comment":"VerifyQC (Algorithm 2, lines 46-47) checks only that |qc.votePrefixes| >= ceil((n+f+1)/2) and that the aggregate signature verifies over the listed (replicaId, prefix) tuples; it does not require the replica identifiers to be distinct. Meanwhile, Algorithm 5 (lines 131-143) explicitly lets an honest replica issue two QC-votes for the same block: one on timer expiry with some prefix p < K and another when the full block is available with prefix K, and both votes are multicast. With the no-commit-proof instantiation of Section 6.2, these two votes are signed with different key shares corresponding to different prefix tags, so an aggregate signature over both tuples (q, p) and (q, K) verifies. A Byzantine aggregator can therefore include two votes from the same honest replica q in one QC, and the quorum-size check counts one physical replica twice. Formally, with n = 3f+1, a QC needs 2f+1 tuples; a Byzantine aggregator can assemble this from f Byzantine votes plus as few as ceil((f+1)/2) honest replicas each contributing two votes, i.e., from fewer than 2f+1 distinct replicas. Lemma C.1's supermajority quorum intersection applies to sets of replicas, not to multisets of votes, so two such QCs can intersect only in Byzantine replicas. This invalidates Lemma C.2 (no two different-block QCs in the same round), and with it the prefix-containment induction in Lemmas C.3-C.5 and Theorem C.7. It also breaks the assumption in Algorithm 6, line 158, that all same-round QCs have the same block hash. The statement in Section 5.2 that issuing more than two QC-votes would not violate safety is therefore not supported by the proof as written. The fix is to require qc.votePrefixes to contain distinct replica identifiers in VerifyQC, to aggregate at most one vote per replica when forming a QC, and to re-verify all quorum-intersection arguments under that requirement.","section":"Appendix C, Lemmas C.1-C.5; Algorithms 2 and 5"}],"minor_comments":[{"comment":"The sentence 'the ⪯ relation is commutative' is mathematically imprecise for a binary relation; the intended statement is presumably that the relation is transitive and that qc1 ⪯ qc2 implies messages(chain(qc1)) is a prefix of messages(chain(qc2)).","section":"Appendix A"},{"comment":"The QCVote function updates lastQCVote to the newly issued (round, prefix), so a timer-based vote followed by a full-prefix vote is intentionally allowed; this design choice should be revisited explicitly after enforcing distinct-voter checks, since it is the source of the duplicate-counting ambiguity in QC formation.","section":"Section 5.2, Algorithm 5"},{"comment":"The description of the simplified no-commit-proofs scheme should state whether the same replica identity may appear with multiple prefix tags in one aggregate, and how verification enforces the intended quorum semantics; the current prose says only that 'signature verification will be evaluated based on the claimed prefix numbers and corresponding public key shares.'","section":"Section 6.2"},{"comment":"The phrase 'after correcting for any possible clock speed differences' is vague; the proof should state the clock-drift assumption explicitly or cite a standard bounded-drift model, since the liveness argument depends on timer lower bounds.","section":"Appendix C, Lemma C.8"}],"recommendation":"major_revision","confidential_remarks":"The paper is from an industrial lab and compares against open-source implementations of Mysticeti and Shoal++; this is a strength, though the reader should confirm that the referenced code versions correspond to the published protocol descriptions. The duplicate-vote flaw is a genuine safety gap in the submitted pseudocode and proof, but it appears fixable within the paper's scope by a distinct-voter check in VerifyQC and consistent aggregation rules. If the authors cannot repair and re-prove that point, the central safety claim fails and the paper should not be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRaptr is a genuinely interesting BFT SMR design, and the prefix-voting idea is the real contribution: letting replicas vote on the longest available prefix, committing nested partial blocks, and decoupling the availability quorum from the safety quorum. The write-up is clear, the evaluation is serious (100 geo-distributed replicas, public code), and the latency analysis is sound. If the correctness gap I'm about to describe is fixed, this could be a strong systems paper.\n\nThe gap is real. Section 5.2 explicitly allows a replica to QC-vote twice in a round: once on the timer (partial prefix) and once when all batches have arrived (full prefix). VerifyQC (Algorithm 2) checks the number of vote tuples and verifies the aggregate signature, but it does not require the replica IDs in votePrefixes to be distinct. With the no-commit-proofs aggregate signature scheme (Section 6.2), each replica has a different key per prefix, so two votes from the same honest replica look like two different virtual signers. A Byzantine aggregator can therefore build a valid-looking QC from f Byzantine votes plus about (f+1)/2 honest replicas each contributing two votes — fewer than 2f+1 distinct replicas. Two such QCs can intersect only in Byzantine replicas. Lemma C.1 no longer applies, and with it the prefix-containment induction in Lemmas C.3–C.5 and Theorem C.7 collapses. This is not a cosmetic proof issue; the protocol as written can commit conflicting prefixes.\n\nThe fix is straightforward: VerifyQC should reject any QC containing the same replica ID more than once (and the correctness argument should be explicit that a QC contains at most one vote per replica). The two-vote rule can stay; the local data structure already keeps only the highest prefix per replica, so the fix is consistent with the intended design. The rest of the proof structure should survive once the distinct-voter invariant is in place.\n\nMinor points: the Autobahn comparison is indirect — they substitute Aptos+ without a head-to-head run; and the artifact would benefit from a pinned commit hash and raw configs. Neither is load-bearing.\n\nBottom line: this paper deserves peer review, and a serious referee should catch the QC distinctness issue. With that fixed, it's likely to be a significant contribution.","headline":"Raptr's prefix-consensus mechanism is a genuine advance, but the safety proof has a load-bearing gap: the protocol allows two QC-votes per replica per round while certificate verification does not enforce distinct voters, so a Byzantine aggregator can form a QC with fewer than 2f+1 distinct replicas and break quorum intersection.","tokens_in":28694,"tokens_out":4560,"would_cite":true,"duration_ms":46519,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68M15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Raptr claims that voting on block prefixes lets Byzantine-tolerant replication hit optimal latency and high throughput at the same time.","keywords":["Byzantine fault tolerance","state machine replication","prefix consensus","block prefix voting","data dissemination","partial synchrony","quorum certificates","atomic broadcast"],"falsifier":"Instrument a Raptr deployment, inject network partitions or Byzantine leaders that send different blocks in the same round, and search the logs for two valid quorum certificates with the same round number but different block hashes; Lemma C.2 proves such a pair cannot exist, so finding one would settle that the safety argument is wrong.","tokens_in":27577,"feed_emoji":"⚡","tokens_out":8176,"duration_ms":75340,"temperature":0.7,"pith_summary":"Raptr is a protocol for Byzantine fault-tolerant state machine replication, letting a group of replicas maintain one ordered transaction log even when some are malicious or the network misbehaves, and it aims to show that the usual trade-off between speed and resilience is not necessary. The key idea is prefix consensus: rather than voting for or against a whole proposed block, each replica votes for the longest prefix of that block whose data it already has locally. Because a quorum of such votes certifies only a prefix, and later proposals are required to extend already-committed prefixes, different replicas can commit different prefixes of the same block without ever ordering them differently. If the proof is right, a leader-based BFT system can have the optimal 3-message-delay consensus latency, 5-message-delay ordering latency, and throughput comparable to DAG-based systems. The paper's experiments with 100 geo-distributed replicas report 260,000 transactions per second at sub-second latency, and only mild degradation when 1% of messages are dropped.","feed_headline":"Raptr hits 260k TPS at sub-second latency, 5 message-delay ordering","feed_subtitle":"By voting on available block prefixes, Raptr keeps throughput and low latency even when 1% of messages are dropped","key_machinery":"The load-bearing mechanism is the pair (block hash, prefix) as the unit of voting, together with the rule 'certify the $S$-th largest prefix, commit the minimum prefix, extend the maximum prefix.' A quorum certificate certifies a prefix only when at least $S \\ge f+1$ replicas voted for that prefix or larger, guaranteeing that a committed prefix's data is retrievable from at least one honest replica. A commit certificate commits the minimum prefix among a quorum of CC-votes, and the next round's entry rule forces the leader to extend the maximum certified prefix from a full-prefix QC, a CC, or a TC. This mechanism makes the availability quorum ($S$) independent of the safety quorum ($\\lceil(n+f+1)/2\\rceil$ votes), which is why full blocks can commit while only a minority of replicas have all the data. The implementation uses a no-commit-proof aggregate signature scheme and groups batch digests into $K$ sub-blocks so that verifying heterogeneous prefix votes costs constant-size pairing work.","core_discovery":"The central claim is that non-binary voting on block prefixes preserves atomic broadcast safety while removing the latency cost of certifying data before consensus. Replicas sign votes of the form (block hash, prefix), and a quorum certificate is valid if it contains a quorum of votes for the same block; it certifies the prefix that is the $S$-th largest among the votes, with $S \\ge f+1$, so at least one honest replica holds all batches in that prefix. A commit certificate is built from a quorum of votes on a QC and commits the minimum certified prefix among them. Quorum intersection then forces every later proposal to extend the maximum certified prefix, yielding the prefix-containment property that underlies safety. Raptr therefore commits full blocks in the common case, degrades to partial-prefix commits when batches are slow, and reaches the optimal 3-message-delay consensus latency with a 5-message-delay ordering latency.","pith_inferences":["Because prefix votes are agnostic to whether the underlying proposal is a leader's block or a DAG anchor, a similar partial-vote rule could be layered onto uncertified DAG protocols, targeting exactly the missing-node stall the paper identifies as their weakness.","The decoupling of the availability quorum from the safety quorum is a general resource: any BFT protocol that separates data availability from ordering might use a smaller availability threshold without weakening safety, as long as committed prefixes remain nested.","Optimistic proposal techniques or K parallel instances of Raptr, which the paper notes are orthogonal, should cut the one-message-delay block-inclusion time further; a direct test would be rerunning the 100-replica evaluation with eight parallel instances and comparing the reported 610 ms latency.","A testable tuning question the paper leaves open is the QC-vote timer: too long makes replicas wait unnecessarily, too short makes them vote on low prefixes that the next leader must extend, so the optimal setting likely depends on network jitter and batch size distribution."],"forward_implications":["The optimal-latency bound need not be purchased with fragile optimistic data dissemination: Raptr shows a leader-based BFT protocol can commit in 3 message delays and order in 5 while sustaining 260k TPS at sub-second latency in a 100-replica deployment.","Data certification can run in the background rather than on the critical path: the paper reports that Raptr eliminates the two message delays of quorum store proof creation, giving up to 25% lower end-to-end latency than the baseline at low to moderate load.","Full blocks can be committed even when only $f+1$ replicas have all the data, because the remaining votes in the safety quorum may be partial; this is what keeps throughput high under load and steady under 1% message loss.","In the full network glitch experiment, Raptr keeps a flat transaction rate with no failed rounds and roughly 15% higher latency, while the compared certified DAG protocol loses its smooth block rate and the uncertified DAG protocol spikes sharply."],"supporting_citations":[{"why":"The Jolteon leader-based consensus protocol whose block-ordering logic Raptr builds on.","marker":"[18]"},{"why":"The latency-reduced Jolteon* voting variant that supplies Raptr's 3-message-delay all-to-all voting baseline.","marker":"[41]"},{"why":"Quorum Store parallel data dissemination, whose proof-of-availability overhead Raptr removes from the critical path.","marker":"[35]"},{"why":"Narwhal/Tusk DAG-based mempool work showing parallel dissemination gains and motivating the data/consensus decoupling.","marker":"[15]"},{"why":"Mysticeti, the uncertified DAG protocol compared against on fragility under message loss.","marker":"[7]"},{"why":"Shoal++, the certified DAG baseline used in the evaluation for throughput and latency comparison.","marker":"[4]"},{"why":"The no-commit-proof aggregate signature scheme used to sign heterogeneous (block hash, prefix) votes efficiently.","marker":"[19]"},{"why":"The good-case latency lower bound establishing that Raptr's 3-message-delay consensus latency is optimal.","marker":"[1]"},{"why":"The fast Byzantine consensus analysis supporting the optimal-latency claim.","marker":"[25]"}],"fun_headline_variants":["Prefix votes: 260k TPS, sub-second latency, robust to 1% drops","Raptr: 3-message consensus, 5-message ordering, 260k TPS","Non-binary prefix votes: safety without certifying data first","Raptr: near-optimal latency at 260k TPS, survives network glitches","Raptr: 260k TPS, sub-second, even with 1% message loss"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The design assumes that a malicious party cannot forge the aggregated digital signatures behind any certificate, and that an honest participant never signs two different statements in the same round; if either fails, the ordering guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["Prefix votes: 260k TPS, sub-second latency, robust to 1% drops","Raptr: 3-message consensus, 5-message ordering, 260k TPS","Non-binary prefix votes: safety without certifying data first","Raptr: near-optimal latency at 260k TPS, survives network glitches","Raptr: 260k TPS, sub-second, even with 1% message loss"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001621,"raw_usage":{"total_tokens":6453,"prompt_tokens":948,"completion_tokens":5505,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":564,"completion_tokens_details":{"reasoning_tokens":5388}},"tokens_in":564,"tokens_out":5505,"duration_ms":34357,"temperature":1.0,"reasoning_tokens":5388,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:13:58.889084+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument a Raptr deployment, inject network partitions or Byzantine leaders that send different blocks in the same round, and search the logs for two valid quorum certificates with the same round number but different block hashes; Lemma C.2 proves such a pair cannot exist, so finding one would settle that the safety argument is wrong.","supporting_citations":[{"cited_title":"Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback","cited_arxiv_id":null,"evidence_quote":"The Jolteon leader-based consensus protocol whose block-ordering logic Raptr builds on."},{"cited_title":"AIP-89 Consensus Latency Reduction using Order Votes","cited_arxiv_id":null,"evidence_quote":"The latency-reduced Jolteon* voting variant that supplies Raptr's 3-message-delay all-to-all voting baseline."},{"cited_title":"Quorum store: How consensus horizontally scales on the aptos blockchain","cited_arxiv_id":null,"evidence_quote":"Quorum Store parallel data dissemination, whose proof-of-availability overhead Raptr removes from the critical path."},{"cited_title":"Narwhal and tusk: a dag-based mempool and efficient bft consensus","cited_arxiv_id":null,"evidence_quote":"Narwhal/Tusk DAG-based mempool work showing parallel dissemination gains and motivating the data/consensus decoupling."},{"cited_title":"No-commit proofs: Defeating livelock in bft.Cryptology ePrint Archive, 2021","cited_arxiv_id":null,"evidence_quote":"The no-commit-proof aggregate signature scheme used to sign heterogeneous (block hash, prefix) votes efficiently."},{"cited_title":"Good- case latency of byzantine broadcast: A complete categorization","cited_arxiv_id":null,"evidence_quote":"The good-case latency lower bound establishing that Raptr's 3-message-delay consensus latency is optimal."},{"cited_title":"Revisiting optimal resilience of fast byzantine consensus","cited_arxiv_id":null,"evidence_quote":"The fast Byzantine consensus analysis supporting the optimal-latency claim."}],"review_version":1}