{"id":"10835169-9753-4c08-b1b1-16ded50395b5","arxiv_id":"2501.14732","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Orthrus accelerates BFT consensus by confirming conflict-free payment transactions through per-instance partial ordering, reserving global ordering for contract transactions, cutting WAN latency by up to 87%.","lead":"Orthrus is a new multi-leader Byzantine fault tolerant consensus protocol that lets simple payment transactions confirm without waiting for a global transaction order, while still ordering smart-contract transactions globally. Tests on 128 replicas across WAN regions show latency reductions of up to 87% compared with existing multi-BFT protocols when a slow straggler instance is present.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Multi-payer escrow lacks a cross-instance commit protocol: Algorithm 1 lines 20-30 can re-process, double-charge, or both commit and abort the same transaction, so Lemma 5's atomicity claim is unsupported.","rationale":"The reader's weakest assumption focuses on the block-state tuple S and how leaders establish cross-instance dependencies. That is a real gap, but in my reading it primarily threatens liveness or clean executions: a stale or Byzantine-chosen S can cause spurious aborts, yet if all replicas process the same block under the same actual state, consistency can still hold. The more direct threat to the paper's safety and atomicity claim lives in the escrow execution path: Algorithm 1 processes the same multi-payer transaction independently in each instance's plog with no synchronization or commit protocol. This can produce double decrements, premature confirmation, or a transaction being both committed and aborted at one replica, and it makes Lemma 5's proof a restatement of the desired property rather than an argument. I therefore partially agree with the reader: both concerns are about underspecified cross-instance coordination, but the escrow race is the one most likely to invalidate Theorem 1 for the paper's headline payment workload. I keep the reader's CONDITIONAL verdict: the system is promising and the evaluation is detailed, but the current write-up does not establish the central safety/atomicity guarantee. If the proposed interleaving check reveals a counterexample, the verdict should move to REJECT for this version; if the check passes under a stated synchronization assumption, that assumption must be added to the algorithm and proof before acceptance.","tokens_in":22077,"tokens_out":12950,"duration_ms":131780,"concrete_test":"Model-check Algorithm 1 under its natural concurrency semantics (in TLA+ or a small Promela/Go harness): one two-payer transaction T with A pays 1, B pays 1, C receives 2, initial balances (1,1,0), both subtransactions delivered in instances 0 and 1, with plog execution threads running concurrently. Enumerate all interleavings of the two escrow/commit/abort paths under both plausible removal policies: keep the partially escrowed transaction pending, or mark it confirmed after partial escrow. The concern lands if any reachable interleaving yields final balances other than (0,0,2), or yields one thread confirming T while the other thread aborts T. If no such interleaving exists, the paper must still state the implicit synchronization assumption that rules it out; without that statement, the proof of Lemma 5 is incomplete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that Orthrus preserve safety and atomicity for multi-payer payment transactions via the escrow mechanism (Challenge-I, Solution-I, Lemma 5). The load-bearing condition is that when two payers of one transaction are assigned to two different instances, the two independent plog execution threads must jointly commit or jointly abort exactly once. Algorithm 1 (lines 20-30) does not implement this condition. For a transaction present in both plog[0] and plog[1], each occurrence independently executes the loop: it escrows its own decremental objects, then checks allEscrowed(tx). If the other instance's escrow has not arrived, the code neither commits nor aborts nor marks the transaction; the paper gives no rule for whether the occurrence is removed from the plog. If it remains pending, the same object is re-escrowed when firstPending fires again, decrementing the payer twice or spuriously aborting the transaction when funds are now insufficient. If it is removed as confirmed, the occurrence in the other instance can later commit while this instance has already reported success, or can observe its escrow entry removed by the commit and abort a transaction just committed. There is no lock, no two-phase protocol, and no per-transaction state machine that would make Lemma 5's 'if any sub-transaction fails, all associated escrow requests are aborted' mechanically true. Thus the stated safety/atomicity guarantee does not follow from the pseudocode, and multi-payer transactions--roughly the payment workload the paper targets--are exactly the regime where the central claim depends on this mechanism.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Orthrus, a Multi-BFT consensus protocol that combines partial ordering for payment transactions with global ordering for contract transactions. Transactions are partitioned into per-instance buckets by payer; each instance runs a sequenced-broadcast consensus, payment transactions are executed from partial logs as soon as they are delivered, and contract transactions are ordered globally using the Ladon dynamic global ordering algorithm. A distributed escrow mechanism is proposed to preserve atomicity for multi-payer transactions and to prevent pending contract transactions from blocking payments. The authors implement Orthrus on the ISS platform and evaluate it on AWS with up to 128 replicas in WAN and LAN settings, reporting latency reductions of up to 87% compared with existing Multi-BFT protocols when a straggler is present.","tokens_in":22371,"tokens_out":4624,"duration_ms":49537,"significance":"If the protocol is correct, Orthrus addresses a real performance problem in Multi-BFT systems: global ordering imposes latency even for conflict-free transactions and is severely amplified by straggler instances. The evaluation is credible and follows standard methodology, includes a real Ethereum-derived workload, compares against several relevant baselines, and makes the source code available. The paper's main conceptual contribution, using partial ordering for commutative payments while retaining global ordering for non-commutative contracts, is potentially valuable. However, the correctness argument is not yet at the level required for a systems venue: the escrow-based atomicity mechanism is under-specified in the pseudocode, and the state-snapshot mechanism that underpins the partial order is not defined precisely enough to support the safety lemmas.","major_comments":[{"comment":"The atomicity argument for multi-payer payment transactions is not supported by the pseudocode. Each occurrence of a transaction in a different plog is processed independently: the replica escrows the local payer's decremental object, checks allEscrowed(tx) against its local elog, and then either commits, aborts, or does nothing. There is no per-transaction state machine, no cross-instance commit protocol, and no rule stating whether an occurrence that is not yet all-escrowed is removed from the plog or re-examined later. As written, the same object can be re-escrowed on a later firstPending trigger, causing a double decrement or a spurious abort when funds are insufficient; alternatively, if the occurrence is removed as confirmed, the other instance may later abort a transaction that was already reported as committed. Lemma 5's proof restates the intended escrow semantics but does not establish exactly-once joint commit/abort across instances, so the atomicity guarantee does not follow from the algorithm.","section":"Section V-C, Algorithm 1 lines 20-30; Lemma 5"},{"comment":"The block state tuple S is load-bearing for the correctness of partial ordering, but the paper does not specify how a leader computes S, how pullValidTx validates transactions against S, or how cross-instance dependencies are discovered and encoded in block references. The running example in Appendix B illustrates one intended scenario, but it is not a protocol definition. Lemma 1 asserts that replicas in the same state execute the same set of transactions because each block refers to an agreed state b.S; however, a Byzantine leader can propose a stale or inconsistent S, and the failure-detector discussion only treats invalid transactions as post-hoc evidence of misbehavior. Without a precise definition of valid state references and a proof that honest replicas derive the same validation outcomes from them, Lemma 1 does not follow from the SB agreement property alone.","section":"Section V-B, Algorithm 1 lines 4-6; Lemma 1"},{"comment":"The global-log execution path has the same cross-instance coordination gap for contract transactions. When the last occurrence of a contract transaction is executed against the glog, the replica checks allEscrowed(tx) against its local elog. If the escrow from another instance has not yet been processed locally, the transaction can be aborted even though all payers would eventually escrow; if the other instance has already committed and removed its escrow entries, allEscrowed(tx) can become false and cause an abort after a commit has been reported. The pseudocode gives no synchronization or ordering between per-instance escrow processing and the global-log execution, so the atomicity and consistency guarantees claimed in Lemma 5 and Theorem 1 are not established for contract transactions either.","section":"Section V-C, Algorithm 1 lines 32-41; Lemma 5"},{"comment":"The correctness proof assumes that a payment transaction valid under block state b.S will succeed under b.S or any subsequent state derived from it, but the paper's own examples in Section II-A show that success can depend on the order in which decrements are applied when balances are limited. Since Orthrus executes payment transactions concurrently and asynchronously across instances, two honest replicas can reach the same state S with different intermediate escrow histories; the paper does not provide an invariant that would make validity outcomes identical across replicas. Lemma 2's summation formula also only applies after a fixed set T is known to succeed, so it does not address the required agreement on which transactions succeed and which fail. The safety argument therefore needs an additional invariant connecting per-instance escrow state to the block-state tuple S.","section":"Section VI, Lemma 1 and Lemma 2 proofs"}],"minor_comments":[{"comment":"There are formatting typos: 'W AN' appears with a space in the abstract and in several places in Section VII, and 'V AN' appears in the abstract.","section":"Abstract and Section VII"},{"comment":"The caption refers to the 'executions module' while the text and architecture consistently name it the 'execution module'; please make the terminology uniform.","section":"Figure 2 caption"},{"comment":"The line 'allEscrowed(tx) ← true' uses the function name as if it were a local variable; please rename the local boolean (e.g., 'ok') to avoid confusion.","section":"Algorithm 2, line 8"},{"comment":"The execution trigger 'firstPending(plog[i])' does not specify how the index i is chosen in the concurrent execution module, nor how multiple per-instance execution threads interact when they touch the same transaction; please clarify the execution thread model.","section":"Section V-C, Algorithm 1 line 20"},{"comment":"The paper imports the dynamic global ordering algorithm from Ladon [19] without stating the precise theorem it relies on; please add an explicit statement of the agreement and monotonicity properties being assumed, even if the proof is delegated to the earlier paper.","section":"Appendix A"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's central performance claim is plausible and the evaluation is solid, but the correctness section is not yet convincing: the escrow mechanism's cross-instance behavior is under-specified in exactly the places where safety and atomicity are claimed. Because the global ordering component is imported from Ladon, which shares four authors with this paper, an independent or at least fully stated proof of the imported properties would substantially strengthen the submission. I would ask the authors to either provide a formal transaction lifecycle with per-transaction states and cross-instance commit/abort rules, or weaken the safety/atomicity claims to what the pseudocode actually guarantees."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: Orthrus is a sensible hybrid—partial ordering for payments, global ordering for contracts, and an escrow mechanism to connect the two—and the evaluation is the most believable part of the paper. The correctness story is not.\n\nWhat's actually new: the components are known (payer-based partitioning, O'Neil's escrow, Ladon's dynamic global ordering), but the combination is new. The paper's real contribution is showing that you can let payment transactions confirm without waiting for global order while still keeping contract transactions safe, and that this pays off in WAN settings with stragglers. That is worth having.\n\nCredit where due: the experimental work is solid. The authors deploy on 128 replicas across four AWS regions, use a real Ethereum workload with 200k transactions, and compare against five state-of-the-art Multi-BFT protocols. The 87% latency reduction under a straggler is plausible, and the latency breakdown in Fig. 6 makes the mechanism clear. Source code is linked. This is reproducible, evaluative work.\n\nThe soft spots are in the correctness argument. Algorithm 1's execution loop has no cross-instance state machine for multi-payer payments. If two payers land in different instances, each instance can escrow its own payer's funds, but nothing prevents the same occurrence from being re-processed before the other instance's escrow arrives—leading to double-decrement or a spurious abort when the other instance commits and removes its escrow entries. Lemma 5's atomicity claim does not follow from the pseudocode. The block state S has the same problem: leaders are told to reference the current state and pull valid transactions, but the paper never specifies how leaders discover cross-instance dependencies, so Lemma 1's \"same state implies same transaction set\" is asserted rather than shown. The global ordering algorithm is imported from Ladon; that is acceptable if you trust the sibling paper, but the proof here is just a pointer.\n\nThese issues are fixable. The evaluation stands, and the design is reasonable. But as written, the safety and atomicity claims outrun the protocol description.\n\nWho this is for: researchers working on BFT consensus scalability, especially in payment-heavy workloads. It deserves a serious referee, not a desk reject. I would send it to peer review with a clear expectation of major revision: specify the multi-payer commit protocol (or fix the pseudocode), give a real proof of Lemma 5, and explain how block state S is computed and agreed upon.","headline":"Promising hybrid BFT design with a credible evaluation, but the multi-payer escrow atomicity is under-specified and the correctness proof does not close the gap.","tokens_in":22914,"tokens_out":3513,"would_cite":true,"duration_ms":36204,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Orthrus claims per-instance partial ordering of payments can keep BFT safety while cutting WAN latency by up to 87%.","keywords":["Byzantine fault tolerance","Multi-BFT consensus","partial ordering","global ordering","escrow mechanism","transaction atomicity","latency optimization","blockchain consensus"],"falsifier":"Run a two-instance experiment where a leader proposes a block whose state S omits a recently delivered block from the other instance that funds the payer's balance. If honest replicas accept and execute the payment under that stale S while another replica with the current state executes a conflicting spending transaction, the two replicas will reach different object values, directly contradicting Theorem 1. The Appendix B running example can be modified to force this by delivering tx0 on Instance 1 before Instance 0's block referencing S = {0,⊥} is proposed.","tokens_in":21883,"feed_emoji":"⚡","tokens_out":6027,"duration_ms":53945,"temperature":0.7,"pith_summary":"Orthrus is a Multi-BFT consensus protocol that tries to show that most blockchain transactions, the conflict-free payments, can be confirmed under a per-instance partial order instead of waiting for a global total order. The paper argues that by assigning transactions to instances based on the payer, only decremental operations on shared accounts need ordering, while incremental operations and payments between different accounts commute. A carefully designed escrow mechanism keeps multi-payer and contract-plus-payment transactions atomic, so the relaxed ordering does not sacrifice safety or liveness. If the protocol is right, payment-heavy workloads in partially synchronous Byzantine networks can cut confirmation latency dramatically, up to 87% in the paper's WAN experiments at 128 replicas with a straggler, without weakening the system's Byzantine guarantees.","feed_headline":"Partial ordering cuts Multi-BFT latency by up to 87 percent","feed_subtitle":"Orthrus confirms payments in parallel while globally ordering contracts, preserving safety via escrow.","key_machinery":"The load-bearing mechanism is the combination of per-instance partial logs (plog) with a single global log (glog), coordinated by an escrow log (elog). Payment transactions that pass the escrow check are committed straight from the partial log, while contract transactions continue through the global-ordering algorithm, adopted from Ladon, so that non-commutative operations execute in a common sequence. The escrow operation temporarily applies a decrement to an owned object, records the request in elog, and either commits all requests of a transaction or undoes them, which is what lets the protocol claim atomicity across instances and claim that a payment can proceed without waiting for a related contract transaction to be globally ordered.","core_discovery":"On its own terms, the paper's central claim is that a hybrid ordering discipline suffices for Byzantine fault-tolerant state-machine replication: payment transactions can be partially ordered within each consensus instance and executed concurrently across instances, while only non-commutative contract transactions need to be merged into a global log. Orthrus partitions transactions by payer into buckets, lets each instance leader propose blocks that reference a system-state tuple S, and uses an escrow mechanism to temporarily reserve funds so that multi-payer transactions either all commit or all abort. The paper proves safety, replicas in the same state see identical object values, and liveness, every correct client transaction is eventually confirmed, and reports experiments on 8 to 128 replicas in WAN and LAN where Orthrus lowers latency by up to 87% compared with existing Multi-BFT protocols such as ISS, Mir-BFT, RCC, DQBFT, and Ladon.","pith_inferences":["If the payer-based partition is sound, the same hybrid partial/global-ordering pattern could be applied to sharded blockchains, where cross-shard transactions are the minority, to reduce cross-shard confirmation latency.","The escrow primitive could be reused as a general concurrency-control mechanism for any replicated state machine with commutative and non-commutative operation classes, decoupling fast-path confirmation from total order.","The reported 87% gain is tied to the workload mix, 46% payment transactions in the Ethereum-derived dataset; workloads with a higher payment share should see larger relative gains, and purely contract workloads should see the advantage shrink toward zero.","A direct testable prediction is that Orthrus's latency advantage over global-ordering Multi-BFT protocols should grow roughly with the payment-transaction fraction and with the straggler slowdown factor, since both increase the time that would otherwise be spent waiting for the global log."],"forward_implications":["Payment transactions from different payers can be confirmed as soon as their own instance delivers them, without waiting for the slowest instance in the system.","A straggler instance no longer stalls the confirmation of unrelated payments, which is the main source of the reported latency reduction.","Multi-payer payment transactions remain atomic: all escrow requests succeed or all are undone, so no payer can lose funds while another payer's transfer aborts.","Contract transactions keep global ordering, so non-commutative operations such as assignments to shared state still produce identical outcomes on all honest replicas.","Throughput stays comparable to top Multi-BFT protocols in the no-straggler case, while latency improves, meaning the concurrency gain does not require sacrificing raw throughput."],"supporting_citations":[{"why":"This is the Multi-BFT baseline protocol and the platform on which Orthrus is implemented.","marker":"[16]"},{"why":"This is the source of the bucket partition mechanism that Orthrus adopts for assigning transactions to instances.","marker":"[18]"},{"why":"This is the dynamic global-ordering algorithm that Orthrus uses to merge partial logs into a global log.","marker":"[19]"},{"why":"This is the original escrow transactional method that inspires Orthrus's atomicity mechanism.","marker":"[22]"},{"why":"This is the PBFT protocol used to implement the sequenced-broadcast instances in Orthrus.","marker":"[13]"},{"why":"This defines the partial-synchrony network model that the safety and liveness proofs assume.","marker":"[25]"},{"why":"This is the double-spending attack that payer-based partitioning is designed to prevent.","marker":"[12]"}],"fun_headline_variants":["Orthrus cuts Multi-BFT latency 87% via partial ordering","Hybrid BFT ordering: payments parallel, contracts global","Orthrus escrow enables 87% WAN latency reduction","Partial ordering for Multi-BFT: up to 87% less latency"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The protocol assumes that the state tuple S that each leader writes into a block is an accurate, consistent snapshot of all instances, so that every transaction pulled into that block is valid under that state; the paper does not specify how leaders discover and reference cross-instance dependencies, and if S can be stale or mutually inconsistent, the claim that replicas in the same state execute the same transactions does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Orthrus cuts Multi-BFT latency 87% via partial ordering","Hybrid BFT ordering: payments parallel, contracts global","Orthrus escrow enables 87% WAN latency reduction","Partial ordering for Multi-BFT: up to 87% less latency"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00023,"raw_usage":{"total_tokens":1447,"prompt_tokens":877,"completion_tokens":570,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":497}},"tokens_in":493,"tokens_out":570,"duration_ms":5815,"temperature":1.0,"reasoning_tokens":497,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:58:10.624288+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a two-instance experiment where a leader proposes a block whose state S omits a recently delivered block from the other instance that funds the payer's balance. If honest replicas accept and execute the payment under that stale S while another replica with the current state executes a conflicting spending transaction, the two replicas will reach different object values, directly contradicting Theorem 1. The Appendix B running example can be modified to force this by delivering tx0 on Instance 1 before Instance 0's block referencing S = {0,⊥} is proposed.","supporting_citations":[{"cited_title":"State Machine Replication Scalability Made Simple","cited_arxiv_id":null,"evidence_quote":"This is the Multi-BFT baseline protocol and the platform on which Orthrus is implemented."},{"cited_title":"Mir-BFT: Scalable and Robust BFT for Decentralized Networks","cited_arxiv_id":null,"evidence_quote":"This is the source of the bucket partition mechanism that Orthrus adopts for assigning transactions to instances."},{"cited_title":"Ladon: High-Performance Multi-BFT Consensus via Dynamic Global Ordering","cited_arxiv_id":null,"evidence_quote":"This is the dynamic global-ordering algorithm that Orthrus uses to merge partial logs into a global log."},{"cited_title":"The Escrow Transactional Method","cited_arxiv_id":null,"evidence_quote":"This is the original escrow transactional method that inspires Orthrus's atomicity mechanism."},{"cited_title":"Consensus in the Presence of Partial Synchrony","cited_arxiv_id":null,"evidence_quote":"This defines the partial-synchrony network model that the safety and liveness proofs assume."},{"cited_title":"Double- spending Fast Payments in Bitcoin","cited_arxiv_id":null,"evidence_quote":"This is the double-spending attack that payer-based partitioning is designed to prevent."}],"review_version":1}