{"id":"46c9febb-f2c8-4097-9ff0-17b64769364c","arxiv_id":"2501.11051","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"NxBFT is a TEE-based, asynchronous, leaderless DAG consensus protocol that achieves the highest throughput in the authors' comparison against MinBFT and Chained-Damysus for up to 40 replicas, at the cost of higher latency and a trust model where operators do not attack their own TEEs.","lead":"The paper introduces NxBFT, a state-machine replication protocol that uses trusted execution environments (TEEs) to make replicas unable to equivocate, allowing a middle-ground 'Not eXactly Byzantine' operating model between crash and Byzantine faults. Its authors measure NxBFT against two TEE-based baselines and report the highest throughput in all tested settings, with crash faults affecting latency only temporarily.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Recovery impossibility is not established: quorum-certificate broadcast layers could permit quorum-based TEE recovery in asynchrony, contradicting the paper's fundamental claim.","rationale":"The reader's conditional verdict identified the N XB trust model as the weakest assumption and noted that correctness arguments rely on cited lemmas and informal impossibility reasoning. The stress-test pass agrees that the protocol's empirical claims are plausible and the trust model is clearly stated, so no objection is raised there. The most load-bearing concern is the recovery impossibility itself: it is a headline contribution ('We identify fundamental issues with crash recovery'), and the paper's informal argument depends on the broadcast layer delivering messages immediately. Because the paper explicitly compares against Narwhal and discusses quorum certificates, a careful reader can ask whether a quorum-certificate broadcast layer would invalidate the impossibility. If the proposed concrete test succeeds, the impossibility claim collapses to a design trade-off rather than a fundamental result, weakening the paper's theoretical novelty and its justification for requiring synchrony for recovery liveness. The test is concrete and small-scale: it requires only a modest modification of the existing protocol and a bounded model check. Until such a test is run, the central theoretical claim should be treated as unverified, which supports the reader's conditional verdict rather than a full accept or reject. The evaluation methodology and the protocol description are otherwise internally consistent, and the performance measurements are extensive enough to support the throughput claims under the stated assumptions.","tokens_in":22236,"tokens_out":32366,"duration_ms":365790,"concrete_test":"Construct a quorum-certificate version of NxBFT's broadcast layer (add one ack round, as in Fig. 2(b), before a vertex is considered delivered) and a recovery procedure in which a crashed replica's history is reconstructed from any 2f+1 replicas' checkpoints, each checkpoint containing the certificates (or DAG vertices) that replica has accepted. Use a model checker for n=3, f=1 and n=5, f=2 over asynchronous schedules with delayed and reordered messages, and verify: (1) no correct replica is ever forced to remove a delivered vertex, and (2) every vertex that any correct replica delivered is present in the union of any 2f+1 checkpoints. If both properties hold, the paper's impossibility claim is falsified, and the all-n recovery requirement is not fundamental.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central theoretical claim (Sec. IV-C1) is that quorum-based checkpoint agreement for TEE recovery is impossible in asynchrony, forcing recovery to rely on synchrony for liveness. The argument assumes a broadcast layer that delivers vertices immediately on receipt (non-uniform reliable broadcast), so a correct replica Alice may be the only one to have delivered a value from the crashed replica, and a quorum smaller than n could omit it, forcing Alice to undeliver. This is an artifact of NxBFT's specific broadcast design, not a fundamental TEE-plus-asynchrony limitation. NxBFT itself discusses Narwhal (Sec. IV-A3), whose broadcast layer uses quorum certificates: a vertex is only delivered after f+1 acks. With such a layer, any vertex delivered by a correct replica is known to at least f+1 replicas; for n=2f+1, any quorum of 2f+1 checkpoints contains all f+1 ackers, so the vertex is recoverable without all n. For larger n, the certificates are propagated through the DAG itself, so a quorum that has the relevant DAG vertices can supply them. The paper gives no proof that such a quorum-certificate scheme cannot satisfy the 'no rollback' condition. Thus the claimed impossibility is not established; it may be a consequence of the immediate-delivery choice. If the impossibility is false, the paper's stated contribution is overstated, and the all-n recovery liveness requirement (which Byzantine replicas can block, as admitted in App. A.3) is a design limitation rather than a fundamental necessity.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes NxBFT, an asynchronous, DAG-based, leaderless State Machine Replication protocol designed for a 'Not eXactly Byzantine' (NXB) operating model in which replicas are equipped with a small TEE that provides non-equivocation via a counter-based signature service and a PRNG-based common coin. Normal-case operation builds one vertex per replica per round, uses backfilling in place of echo-based reliable broadcast, and derives total order from waves of four rounds using a common-coin-selected root; the NXB client model lets each client unicast to a single replica and accept a single response. The paper also claims a fundamental impossibility: quorum-based TEE crash recovery cannot be safe under asynchrony without rollbacks, so recovery must rely on synchrony for liveness and on the participation of all replicas. It evaluates NxBFT against MinBFT and Chained-Damysus under the ABCperf framework for up to 40 replicas and network round-trip latencies up to 150 ms, reporting that NxBFT achieves the highest throughput in all tested configurations, with a latency penalty relative to leader-based protocols and with latency that is only mildly affected by actual crash faults.","tokens_in":22535,"tokens_out":15968,"duration_ms":186313,"significance":"If the correctness and recovery claims hold, NxBFT is a valuable datapoint for TEE-based asynchronous consensus: it demonstrates a practical n>2f design that combines DAG-based ordering with a small enclave, and it provides a systematic throughput-latency comparison against two established TEE-based SMR protocols. The paper ships an implementation and a substantial experimental study with multiple repetitions and a stated sensitivity analysis, and it is explicit about the recovery protocol's liveness dependence on all replicas in App. A.3. The main theoretical contribution, however, is the recovery impossibility; as written, that claim is not established with a formal proof and is tied to the specific immediate-delivery broadcast used by NxBFT. The empirical headline is extensive, but the throughput tables lack variance information, so the significance of the closest performance margins cannot be assessed from the paper alone.","major_comments":[{"comment":"The claimed fundamental impossibility of quorum-based TEE recovery in asynchrony is not established. The argument depends on the specific broadcast design: 'In a TEE-based reliable broadcast with a fault tolerance of n > f, a receiving replica can, on successful signature verification, deliver immediately.' That is the property of NxBFT's backfilling-only broadcast, not of all possible asynchronous TEE-based reliable broadcasts. The paper itself discusses Narwhal in Sec. IV-A3, where delivery is mediated by a quorum certificate of f+1 acknowledgements; with such a layer, a value delivered by a correct replica is witnessed by f+1 replicas and can be supplied as a certificate during recovery. The paper gives no proof that quorum-certificate layers cannot satisfy the no-rollback condition. Therefore the abstract's and Sec. IV-C1's 'fundamental' claim is too strong as stated: at minimum, the argument must be restricted to the chosen broadcast layer, or a formal proof must be given for the general setting.","section":"Sec. IV-C1"},{"comment":"The recovery protocol is not live under the paper's own Byzantine fault model. The protocol requires n RecoveryProposals before a RecoveryCommit can be issued, and App. A.3 states, 'Obviously, the proposed recovery protocol is only live if all replicas are eventually reactive: Byzantine faulty replicas can stop the recovery procedure by not sending a RecoveryProposal at any time.' Since the consensus layer tolerates up to f < n/2 Byzantine replicas, recovery liveness in NxBFT is guaranteed only when the recovering replica's peers are correct, which is a substantially stronger assumption than the one used for normal-case operation. The paper should either explicitly restrict the recovery guarantee to the NxB operating model and state this restriction in the contributions, or provide a recovery protocol whose liveness does not require all n replicas to cooperate.","section":"Sec. IV-C2 / App. A.3"},{"comment":"The correctness of the consensus layer is delegated to cited results rather than proved for the modified protocol: Sec. III-B(c) refers to [11, Lemma 3] and [12, Proposition 2], while Sec. IV-A3 replaces TEE-Rider's echo broadcast with backfilling-only reliable broadcast and Sec. IV-B3 replaces a threshold-signature common coin with a TEE PRNG coin. Appendix A gives informal arguments, but no formal proof that the modified broadcast and coin satisfy the hypotheses of the cited lemmas, nor that the wave/commit construction remains correct under the NXB client model. Because the central claim is a correct and resilient SMR protocol, the paper should either supply a precise transfer argument showing which properties are inherited unchanged, or give direct proofs for the modified protocol.","section":"Sec. III-B(c), Sec. IV-A3, Sec. IV-B3"},{"comment":"The maximum sustained throughput values that support the headline claim 'NxBFT achieves the highest throughput in all scenarios' are reported as single point estimates without confidence intervals or per-run variance. Figure 4 and Table III provide error bars or confidence intervals for latency and recovery time, but Tables I and II do not report variance for throughput. Some margins are not large enough to be obviously stable under measurement noise (for example, 45 vs 33 kOp/s for n=3 at 150 ms network latency in Table II). Please report run-level throughput distributions, confidence intervals, or a statistical test, or explicitly state which differences are significant under the described measurement methodology.","section":"Sec. V-B, Sec. V-C, Tables I and II"}],"minor_comments":[{"comment":"The legend appears to contain stray axis-label text ('0 500000'), and the small window on the right is referenced but not explained in the caption; please clean up the figure.","section":"Fig. 3"},{"comment":"The code availability link is a placeholder ('https://blinded.for/review'); the final version should provide the actual repository identifier or DOI.","section":"Footnote 1"},{"comment":"The name 'Yanadmuri et al.' in the text should be 'Yandamuri et al.' to match reference [32].","section":"Sec. II-B"},{"comment":"The phrase 'n synchronous authenticated reliable broadcast instances with a fault tolerance of n > f' is ambiguous; please state precisely what fault-tolerance property is guaranteed during setup when f replicas are faulty.","section":"Sec. IV-B1"},{"comment":"The text says 'both Chained-Damysus and NxBFT loose this ability'; 'loose' should be 'lose'.","section":"Sec. V-C"}],"recommendation":"major_revision","confidential_remarks":"The work is within scope for a distributed-systems or security venue, and the experimental study is substantial. The main risk is the framing of the recovery impossibility as fundamental: as written, the argument is specific to NxBFT's broadcast layer and is not a formal proof, and the recovery protocol's liveness requires all replicas to be reactive, which is explicitly acknowledged in App. A.3. The consensus correctness also rests on unmodified citations to TEE-Rider and DAG-Rider without a precise transfer argument. These issues are fixable within the paper's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has a good protocol and a strong evaluation, but the headline theoretical result is not proven. NxBFT is a sensible engineering combination: a TEE signature service for non-equivocation, a Narwhal-inspired backfilling broadcast, a PRNG common coin, and a client model that spreads requests across replicas. The evaluation is the best part. It covers 3 to 40 replicas, latencies up to 150 ms, compares against MinBFT and Chained-Damysus under both client models, injects real faults, and measures recovery times. The reported numbers, 584 kOp/s at 10 replicas in a datacenter and 20 kOp/s at 40 replicas with 150 ms latency, are plausible even though the summary tables lack error bars.\n\nThe soft spot is the recovery impossibility in Sec. IV-C1. The argument depends on a broadcast layer that delivers immediately on valid signature, letting a correct replica be the only one holding a value from a crashed replica. That describes NxBFT's chosen backfilling design, but it is not a property of all TEE-based reliable broadcasts. A Narwhal-style quorum-certificate layer would deliver only after f+1 acks; with n = 2f+1, any f+1 quorum shares a correct replica with the certificate holders, so a quorum-based checkpoint can include every value any correct replica delivered. The stress-test concern lands. The all-n recovery protocol may be sound for NxBFT, but the paper does not establish that synchrony is fundamentally required. The authors should either prove the impossibility for a broader class of broadcast layers or soften the claim.\n\nMinor issues: the artifact URL is a placeholder, correctness relies on cited lemmas from TEE-Rider and DAG-Rider rather than full proofs, and throughput tables would benefit from confidence intervals. None of this undercuts the engineering.\n\nWho should read this: systems people working on TEE-assisted BFT or DAG-based consensus. The evaluation methodology and the NXB client model are genuinely useful. The paper deserves a serious referee. I would send it out, with reviewers asked to push for a more careful treatment of the recovery claim and for actual artifact release.","headline":"A solid TEE-based SMR systems paper whose evaluation is worth engaging, but the claimed recovery impossibility only holds for the authors' specific broadcast design, not as a fundamental result.","tokens_in":23122,"tokens_out":9483,"would_cite":true,"duration_ms":112922,"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":"TEE-based async consensus beats leader-based BFT throughput in every test","keywords":["state machine replication","Byzantine fault tolerance","trusted execution environment","asynchronous consensus","DAG-based consensus","crash recovery","non-equivocation","common coin"],"falsifier":"Run the recovery protocol with $n=3$ and one deliberately Byzantine replica that never sends a RecoveryProposal; if recovery still completes, the paper's liveness claim is wrong, and if it never completes, the claim that recovery depends on all replicas being reactive is confirmed.","tokens_in":22003,"feed_emoji":"⚡","tokens_out":7674,"duration_ms":75262,"temperature":0.7,"pith_summary":"NxBFT claims that a federation of operators can get Byzantine-grade resilience at crash-fault cost by adopting a \"Not eXactly Byzantine\" (NxB) operating model: operators do not attack their own TEE, do not tamper with application logic, and allow scheduled synchronous maintenance windows. On top of that model, the paper builds an asynchronous, leaderless, DAG-based state machine replication protocol whose small TEE provides non-equivocation and a private common coin, so every exchanged message can carry new client requests and no leader bottleneck exists. The paper's experiments, across 3 to 40 replicas and network round-trip latencies up to 150 ms, show NxBFT with the highest throughput in every configuration tested, with fault-free decisions in about two network round trips and with throughput degrading at most by $c/n$ when $c$ replicas crash. The paper also establishes an impossibility: in asynchrony, recovering a crashed TEE-based replica cannot be done by quorum-based checkpoint agreement, and liveness of recovery requires synchrony and the participation of all replicas.","feed_headline":"TEE-based async consensus beats leader-based BFT throughput in every test","feed_subtitle":"NxBFT orders requests with two network round trips, survives crashes without latency spikes, and needs synchrony only for recovery.","key_machinery":"The machinery is NxBFT's layered protocol: a broadcast layer in which each replica proposes one vertex per round referencing $\\lfloor n/2\\rfloor+1$ vertices of the previous round, a small TEE providing a signature service with an increment-only counter (so each counter value can be used once, eliminating equivocation) and a common coin implemented as a PRNG seeded by XORed setup shares (so wave-root selection is fair, unpredictable, and cheap), and a consensus layer that groups four broadcast rounds into a wave, selects a wave root by the coin, and orders all earlier waves by a deterministic DAG traversal without extra communication. The load-bearing mechanism is that every message performs double duty as both a new client request and a consensus step, and the one-step backfilling-based reliable broadcast replaces echo-based or certificate-based schemes, reducing common-case communication to one $n^2$ all-to-all step per broadcast round. The four-round wave length is essential: the paper proves (and gives a counterexample) that reducing it to three rounds breaks the get-core property needed for liveness at $n>2f$.","core_discovery":"The central claim is that the NxB operating model unlocks an asynchronous, graph-based, leaderless SMR protocol, NxBFT, that is both efficient and crash-resilient: correct replicas build a DAG one vertex per round, a TEE-enforced counter-signature prevents equivocation, and a TEE-seeded PRNG serves as a common coin that selects the wave root for deterministic ordering. Because clients unicast to one randomly chosen replica and a single correct response suffices, the load is balanced across all replicas and each broadcast message simultaneously carries client requests, yielding two network round trips between decisions in the fault-free case and one $n^2$ communication step per broadcast round. In direct measurement against MinBFT (static leader) and Chained-Damysus (rotating leader), NxBFT achieves the highest sustained throughput in every tested scenario—up to 178 kOp/s at 40 replicas in a datacenter and 20 kOp/s at 40 replicas with 150 ms round-trip latency—and, unlike the leader-based protocols, its end-to-end latency recovers after actual crash faults. The paper further claims a fundamental boundary: TEE-based crash recovery in asynchrony cannot use quorum-based checkpoint agreement without violating reliable-broadcast totality, so recovery must require all replicas' input and synchrony for liveness.","pith_inferences":["If the NxB operating model is accepted, the protocol's real scalability ceiling shifts to payload-dependent cryptographic work and to the memory needed to store the unbounded DAG; the paper's observation that one replica CPU core is saturated at about 25% total server CPU suggests that parallelizing vertex validation at each replica is a direct, testable next step.","The impossibility argument points to a general design rule beyond this paper: TEE-based SMR with asynchronous reliable broadcast and $n>f$ cannot recover a replica through quorums, so any system that offers online recovery must either abandon asynchrony for recovery or require all replicas' participation; this explains why leader-based, partially synchronous TEE systems provide recovery while asyn","The NXB client model delegates censorship-resistance to random replica choice plus a fallback timer; an extension worth testing is whether application-signed responses and client-side proof of correct behavior are enough to keep liveness under a client that deliberately selects a corrupt replica or under colluding replicas that selectively drop requests.","The recovery protocol's all-replica input requirement means one Byzantine replica can block recovery forever; a practical mitigation, not explored in the paper, would be to combine the maintenance-window assumption with a synchrony-bounded timeout after which the recovering replica is expelled and reconfigured out."],"forward_implications":["Adopting the NxB operating model lets an asynchronous DAG-based SMR reach 178 kOp/s at 40 replicas in a datacenter and 20 kOp/s across a 150 ms wide-area network, the best throughput among the three protocols in every configuration tested.","Fault-free operation needs only two network round trips per decision, and each broadcast round costs one $n^2$ communication step in the common case, improving on TEE-Rider's $n^2+n^3$ and Narwhal's $3n^2$ patterns.","Crash faults are cheap for NxBFT: throughput degrades by at most $c/n$ for c crashed replicas and latency recovers once clients reroute, whereas MinBFT stalls on leader failure and Chained-Damysus's timeouts inflate cumulatively.","Recovery of a crashed TEE replica is Byzantine-safe only with all-replica participation, and quorum-based checkpoint agreement is impossible in asynchrony without rollbacks; consequently recovery liveness requires synchrony, which the NxB model provides via scheduled maintenance windows.","Liveness with the reduced resilience threshold $n>2f$ requires a wave length of four rounds; shortening to three breaks the get-core property, with a concrete counterexample for $n=5$."],"supporting_citations":[{"why":"supplies the base TEE-Rider protocol, the DAG construction, and the $n>2f$ proof that NxBFT compiles and optimizes.","marker":"[11]"},{"why":"provides the DAG-Rider wave construction, ordering rules, and the liveness lemmas NxBFT's consensus layer reuses.","marker":"[12]"},{"why":"supplies the Narwhal backfilling and DAG communication ideas that NxBFT adapts into its one-step reliable broadcast.","marker":"[10]"},{"why":"defines Chained-Damysus, the rotating-leader baseline with trusted components that NxBFT is compared against.","marker":"[13]"},{"why":"defines MinBFT, the static-leader TEE-based baseline and the source of the counter-based non-equivocation idea.","marker":"[14]"},{"why":"establishes the increment-only counter signature service (TrInc) that the NxBFT enclave's non-equivocation mechanism relies on.","marker":"[22]"},{"why":"supplies the reliable broadcast specifications and totality property that the correctness and impossibility arguments use.","marker":"[36]"},{"why":"furnishes the interactive-consistency basis for the recovery protocol's all-replica agreement.","marker":"[37]"},{"why":"provides the evaluation harness and client emulation used for the throughput-latency and fault experiments.","marker":"[42]"}],"fun_headline_variants":["TEE-based leaderless consensus hits 2 round trips, tops BFT throughput","NxBFT: async TEE consensus beats leader BFT in crashes and speed","Leaderless TEE consensus: two hops, highest throughput, crash-proof","NxBFT: TEE-powered async consensus outruns leader-based BFT","TEE async consensus: 2 round trips, top throughput, crash-surviving"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that operators never attack their own TEE, never tamper with the application logic, and provide sufficiently long synchronous windows for maintenance; if an operator compromises its TEE, the guarantees that each message is unique and that coin values stay secret disappear, and with them the $n>2f$ asynchronous resilience argument.","fun_headline_variants_meta":{"raw":{"variants":["TEE-based leaderless consensus hits 2 round trips, tops BFT throughput","NxBFT: async TEE consensus beats leader BFT in crashes and speed","Leaderless TEE consensus: two hops, highest throughput, crash-proof","NxBFT: TEE-powered async consensus outruns leader-based BFT","TEE async consensus: 2 round trips, top throughput, crash-surviving"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000781,"raw_usage":{"total_tokens":3510,"prompt_tokens":1065,"completion_tokens":2445,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":2340}},"tokens_in":681,"tokens_out":2445,"duration_ms":16355,"temperature":1.0,"reasoning_tokens":2340,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:41:03.253567+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the recovery protocol with $n=3$ and one deliberately Byzantine replica that never sends a RecoveryProposal; if recovery still completes, the paper's liveness claim is wrong, and if it never completes, the claim that recovery depends on all replicas being reactive is confirmed.","supporting_citations":[{"cited_title":"Brief announcement: Let it TEE: asynchronous Byzantine atomic broadcast with n ≥ 2f+1,","cited_arxiv_id":null,"evidence_quote":"supplies the base TEE-Rider protocol, the DAG construction, and the $n>2f$ proof that NxBFT compiles and optimizes."},{"cited_title":"TrInc: Small trusted hardware for large distributed systems,","cited_arxiv_id":null,"evidence_quote":"establishes the increment-only counter signature service (TrInc) that the NxBFT enclave's non-equivocation mechanism relies on."},{"cited_title":"Cachin, R","cited_arxiv_id":null,"evidence_quote":"supplies the reliable broadcast specifications and totality property that the correctness and impossibility arguments use."},{"cited_title":"ABCperf: Performance evaluation of fault tolerant state machine replication made simple: Demo abstract,","cited_arxiv_id":null,"evidence_quote":"provides the evaluation harness and client emulation used for the throughput-latency and fault experiments."}],"review_version":1}