{"id":"ceaf8893-33c9-490a-94b1-84784e500149","arxiv_id":"2501.01062","paper_version":4,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Fides proposes a TEE-assisted asynchronous DAG BFT consensus with n=2f+1 and low commit latency, but its liveness proof relies on an unsupported set-intersection claim.","lead":"Fides is a new consensus protocol that uses trusted hardware enclaves to make DAG-based Byzantine fault tolerance faster and more scalable, claiming support for more faulty nodes with fewer messages. The authors report high throughput on cloud testbeds, but the theoretical liveness proof has serious gaps that undermine the central guarantee.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6 is false as stated: for n=5, f=2, a valid Fides wave can have only 2 first-round vertices reachable from at least 3 third-round vertices, so the claimed six-round expected commit bound rests on an invalid liveness proof.","rationale":"The reader's weakest assumption correctly identified Lemma 6 as the foundation of the liveness lower bound. I agree with that diagnosis, and the explicit counterexample above shows the lemma is not just missing a proof step but is actually false in the protocol's own model: all strong-edge quotas are satisfied, yet fewer than f+1 first-round vertices are committable. The reader attributed the flaw to the 'same set' assertion in Case 1; the falsifying configuration actually invalidates Case 2's set-theoretic inequality, so my concern is slightly more specific but points to the same load-bearing step. Since Lemma 7, Lemma 9, and Theorem 2 all depend on Lemma 6, the central liveness claim of the paper is unsupported as written. This does not change the reader's REJECT verdict; the engineering evaluation may be salvageable, but the theoretical core needs a repaired liveness argument before the main claims can be accepted.","tokens_in":27093,"tokens_out":8264,"duration_ms":76825,"concrete_test":"Enumerate all valid 3-round waves for n=5, f=2 under the paper's construction rule: each vertex has at least f+1 strong edges to the previous round, and a replica may advance once it has seen f+1 vertices. For every assignment of 3-element strong-edge sets for round 2 and round 3, count first-round vertices strongly reachable from at least 3 third-round vertices, then take the minimum over all valid waves. The configuration T1={A,B,D}, T2={A,C,E}, T3={B,C,D} with A={1,2,3}, B={1,2,4}, C={1,2,5}, D={3,4,5}, E={1,3,5} is a certificate giving minimum 2; verifying that this assignment is accepted by the protocol's own validation (each referenced vertex reliably delivered, f+1 distinct sources) settles that Lemma 6's universal claim is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The liveness argument collapses at Lemma 6, which asserts every wave has at least f+1 first-round vertices that satisfy the commit rule (strongly reachable from at least f+1 third-round vertices). The proof's Case 2 uses an incorrect set-theoretic identity, and the conclusion that |I(V)| > f does not follow. The lemma is not merely unproven; it is false. With n=5, f=2, construct a valid wave: round 1 = {1,2,3,4,5}; round 2 vertices A,B,C,D,E have strong edges A={1,2,3}, B={1,2,4}, C={1,2,5}, D={3,4,5}, E={1,3,5}; round 3 vertices T1={A,B,D}, T2={A,C,E}, T3={B,C,D}. Every vertex respects the required f+1 strong edges and the rule that a replica may advance after seeing f+1 prior vertices. The first-round reachability sets from T1, T2, T3 are {1,2,3,4}, {1,2,3,5}, and {1,2,4,5}; only vertices 1 and 2 are reachable from all three third-round vertices, while vertices 3,4,5 are reachable from exactly two. Thus fewer than f+1=3 first-round vertices satisfy the commit rule. Lemma 7's expected-six-round bound, Lemma 9's constant-round commitment, and Theorem 2's liveness proof all invoke Lemma 6. Because the central liveness guarantee depends on this step, the main correctness claim is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"Fides is an asynchronous DAG-based BFT consensus protocol that uses four TEE-assisted components (MIC-based reliable broadcast, RAC-based vertex validation, RANG-based common coin, and TRAD-based transaction disclosure) to tolerate f Byzantine faults among n=2f+1 replicas while using only f+1 strong references per vertex. The paper proposes three-round waves with a commit rule and claims that a vertex leader is committed every three rounds under random delays and every six rounds under an asynchronous adversary, with O(κn²+n³) metadata communication. The manuscript contains a formal correctness appendix (Appendix A) and an experimental evaluation on LAN, WAN, and delay-injected networks comparing Fides with Tusk, RCC, HotStuff, and PBFT.","tokens_in":27470,"tokens_out":11824,"duration_ms":110008,"significance":"If the claims held, Fides would be a substantial contribution: it would improve the quorum size and reference degree for asynchronous DAG consensus, replace threshold-signature common coins with a lightweight TEE primitive, and demonstrate large throughput gains on a real implementation. The authors deserve credit for specifying four trusted components, for attempting a complete correctness appendix, and for a broad evaluation. However, the central formal claims are not established. In particular, the key liveness lemma is false, the one-echo reliable broadcast does not satisfy its stated Agreement property as written, and the common-coin unpredictability guarantee is not delivered by the deterministic shared-seed RANG described in the paper. These are not presentation issues; they undermine the safety and liveness theorems as stated.","major_comments":[{"comment":"The proof of Lemma 6 is invalid and the lemma is false. In Case 2 the identity |U(V)| = |I(V)| + Σ_k (R(v_k)-|I(V)|) is not a set-theoretic identity, because the sets R(v_k)\\I(V) need not be pairwise disjoint. More decisively, for n=5, f=2 consider first-round vertices {1,2,3,4,5}, second-round vertices A={1,2,3}, B={1,2,4}, C={1,2,5}, D={3,4,5}, E={1,3,5}, and third-round vertices T1={A,B,D}, T2={A,C,E}, T3={B,C,D}. Every vertex has exactly f+1=3 strong edges to the previous round, so this is a valid wave under the rules of §6.1. The first-round sets strongly reachable from T1, T2, and T3 are {1,2,3,4}, {1,2,3,5}, and {1,2,4,5}; their intersection contains only {1,2}. Hence only two, not f+1=3, first-round vertices are reachable from at least f+1 third-round vertices. The commit rule would elect a leader among the other three with positive probability. Lemma 7, Lemma 9, and Theorem 2 all invoke Lemma 6, so the claimed six-round expected commit and the liveness theorem are not established.","section":"Appendix A.4.2 (Lemma 6)"},{"comment":"The one-echo reliable broadcast does not satisfy the Agreement property as written. The pseudocode in Fig. 3 delivers upon receiving at least 1 ⟨echo,v⟩ (line 10). A Byzantine replica can send an echo of a valid vertex to a single correct replica and to no one else; similarly, a Byzantine source can create a valid MIC-certified vertex and send the proposal only to that Byzantine echoer. The correct replica then delivers v while no other correct replica does. The proof of Theorem A.3 states that a correct replica 'must have received at least one valid ⟨echo,v⟩ from a correct replica', but the protocol does not require or verify that the echo is from a correct replica, and the validity check concerns v's certificate, not the echoer's provenance. Requiring f+1 matching echoes from distinct replicas would repair this specific step (giving at least one correct echoer that broadcasts to all), but that is not the protocol presented. Because Lemma 1 (identical DAGs) is derived from T-RBC Agreement, this flaw affects safety as well as liveness.","section":"§5.1 and Theorem A.3"},{"comment":"The RANG common coin does not provide Unpredictability as defined in §3.3. RANG is initialized with a shared seed from DKG and runs a deterministic PRNG; the interface Rand(round-cert) returns the leader as soon as a single valid round-certificate for the wave's final round is supplied. Any replica (honest or Byzantine) that has obtained such a round-cert can call Rand and learn the wave's leader before f+1 replicas have invoked ChooseLeader. Thus the outcome is not computationally indistinguishable from random while fewer than f+1 replicas have invoked the coin, contrary to the Unpredictability requirement. Lemma 7's probabilistic liveness argument assumes the adversary cannot predict the coin before the leader is revealed; with early prediction, the adversary can arrange the DAG so that the elected leader is among the vertices that do not satisfy the commit rule (as in the Lemma 6 counterexample).","section":"§5.3 and Theorem A.6"},{"comment":"Lemma 8's stochastic model is not derived from the protocol. The proof assumes each second-round vertex independently points to the leader with probability p=(f+1)/(2f+1) and that third-round vertices independently sample f+1 second-round vertices; but in §6.1 a replica's strong edges are determined by the f+1 vertices currently in its local DAG at the moment it advances, with an adversarial (or arbitrary) delivery order. The protocol does not select references uniformly at random. Therefore the binomial computation and the lower bound 0.965 are properties of an assumed random-reference model, not of Fides. If the authors intend Lemma 8 as a performance statement under a specific stochastic network model, that model must be defined precisely and connected to the protocol; as written, the lemma does not support the claimed three-round expected commit latency.","section":"Appendix A.4.2 (Lemma 8)"}],"minor_comments":[{"comment":"The phrase 'in cenributed networks' should read 'in distributed networks'.","section":"Conclusion"},{"comment":"The comment for weak edges says they 'represent strong edges'; it should say they represent weak edges.","section":"Fig. 4"},{"comment":"Line 25 contains the typo 'Deqeue' instead of 'Dequeue', and lines 65 and 70 use the symbol 'Ð' where set union/cup is intended.","section":"Fig. 5"},{"comment":"Reference [51] contains a corrupted author name ('Michał undefinedwiundefinedtek'); please restore the correct Aleph author list.","section":"References"},{"comment":"The measured value of 3.54 rounds to commit per vertex for Fides should be reconciled with the theoretical claims of 3 rounds (Lemma 8) and 6 rounds (Lemma 7), since the discrepancy is not explained.","section":"§7.4"},{"comment":"The claimed complexity O(κn²+n³) is not defined in the body; please provide the definitions of κ and the message-accounting that yields this expression.","section":"Abstract"}],"recommendation":"reject","confidential_remarks":"The stress-test counterexample to Lemma 6 is correct and directly invalidates the main liveness claim. My additional concerns about the one-echo reliable broadcast and the deterministic RANG coin are independent of the Lemma 6 issue and are also load-bearing. Although the protocol is interesting and the evaluation is extensive, the current manuscript is not close to a publishable correctness argument; the fixes require protocol redesign (e.g., echo thresholds and a genuinely unpredictable coin) and a complete re-proof of the main theorems, so I would recommend rejection rather than a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know the main thing before reading: the liveness argument does not hold. Lemma 6 claims that every wave has at least f+1 first-round vertices satisfying the commit rule, but the proof is not just incomplete, it is wrong. With n=5, f=2 you can build a valid wave where only 2 first-round vertices are reachable from all three third-round vertices. Take second-round vertices A={1,2,3}, B={1,2,4}, C={1,2,5}, D={3,4,5}, E={1,3,5} and third-round vertices T1={A,B,D}, T2={A,C,E}, T3={B,C,D}. Every vertex respects the f+1 reference rule, yet the intersection of reachable first-round sets is {1,2}. So Lemma 6's conclusion fails, and with it Lemma 7's six-round expected commit bound, Lemma 9's constant-round commit, and Theorem 2's liveness. This is load-bearing, not a cosmetic gap.\n\nThat said, the paper is not a throwaway. The combination of TEE-based reliable broadcast with a DAG and reducing the reference degree to f+1 is genuinely new relative to the cited work—Hybster, DAMYSUS, and TBFT are not DAG-based, and Tusk/Bullshark/Mysticeti are not at 2f+1. The safety argument is plausible, the communication complexity claims are reasonable, and the implementation on ResilientDB/Open Enclave is real engineering. The evaluation numbers are impressive, though they lack error bars and the WAN results use simulated SGX, which should be labeled more prominently.\n\nTwo smaller issues: the full-text abstract says '2x larger quorum size,' which contradicts the actual n=2f+1 claim, and Lemma 8's random-delay model is not a substitute for an asynchronous-adversary liveness proof. The paper itself draws that line, but then Theorem 2 relies on Lemma 9, which leans on the broken Lemma 7.\n\nWho is this for? Anyone working on TEE-assisted BFT or DAG consensus. The idea is worth engaging with even if this version is not correct. I would give it a serious referee—the flaw is specific and might be fixable, and the system design deserves scrutiny. But as a preprint, I cannot rely on its liveness guarantee.","headline":"The liveness proof collapses at Lemma 6—the counterexample is real—but the TEE-plus-DAG combination is new enough to warrant a careful look and a chance to fix.","tokens_in":28041,"tokens_out":3025,"would_cite":false,"duration_ms":26469,"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":"Fides claims asynchronous DAG-based BFT can run with n=2f+1 replicas and only f+1 references per vertex, using TEE-based broadcast, validation, coin, and transaction disclosure.","keywords":["asynchronous BFT consensus","DAG-based consensus","trusted execution environment","reliable broadcast","common coin","quorum size","censorship resistance","liveness"],"falsifier":"Construct a concrete $n=5$, $f=2$ DAG in which two second-round vertices reference disjoint pairs of first-round vertices and a third-round vertex references both second-round vertices, making its reachable first-round set larger than $f+1$; check whether every such third-round vertex still shares at least $f+1$ first-round ancestors. If a completed wave can have no first-round vertex with $f+1$ strong-path supporters, the expected commit-rate analysis fails.","tokens_in":26863,"feed_emoji":"🔐","tokens_out":8046,"duration_ms":65817,"temperature":0.7,"pith_summary":"Fides proposes a way to make asynchronous DAG-based Byzantine fault tolerant consensus cheaper and faster by moving four critical operations into trusted execution environments. The paper's central claim is that with a TEE-assisted reliable broadcast and a TEE-assisted common coin, replicas can build a DAG in which each vertex references only $f+1$ vertices from the previous round, while still tolerating $f$ Byzantine replicas out of $n = 2f+1$. On that structure Fides defines a three-round wave and a commit rule that, the paper argues, commits a wave leader every three rounds in expectation under random delays and every six rounds under an asynchronous adversary. If correct, this would reduce quorum size, communication complexity, and commit latency relative to DAG protocols that require $n = 3f+1$ or threshold-signature coins, and the encrypted-transaction mechanism would resist front-running. The price is a threat model that trusts the enclave itself.","feed_headline":"TEE-assisted DAG consensus cuts quorum to 2f+1","feed_subtitle":"Fides claims f+1 references per vertex and a leader commit every three rounds, at n=2f+1.","key_machinery":"The load-bearing object is the three-round wave with strong edges cut down to $f+1$ references. A strong edge from a round-$r$ vertex to a round-$(r-1)$ vertex counts toward the quorum that lets a replica advance; weak edges only help ensure every vertex is eventually included in some causal history. The commit rule uses the TEE-assisted common coin on the third round to elect a first-round leader, then checks whether at least $f+1$ third-round vertices reach that leader via strong paths; if not, the leader is skipped and a later committed leader recursively pulls in earlier waves. The monotonic counter inside the TEE is what makes each replica's per-round vertex unique, which is what lets a single echo phase replace the multiple all-to-all phases of classic reliable broadcast and what allows the system to run at $n = 2f+1$.","core_discovery":"On the paper's own terms, the discovery is that the reference requirement in asynchronous DAG consensus can be weakened from $2f+1$ to $f+1$ per vertex without losing safety or liveness, if trusted components supply three things: a monotonic counter that makes each replica's per-round proposal unique, a validator that certifies quorum references before a replica advances rounds, and a shared unpredictable random source for leader election. Fides packages these as four TEE components and arranges the DAG in waves of three rounds: first-round vertices are proposals, second- and third-round vertices vote by strong references, and the third round uses the common coin to elect a first-round leader. A leader commits directly when at least $f+1$ third-round vertices have a strong path to it, and indirectly through later committed leaders otherwise; the causal history of committed leaders is then ordered deterministically. The paper argues this yields $n = 2f+1$ Byzantine fault tolerance, $O(\\kappa n^2 + n^3)$ metadata communication complexity, and expected leader commitment every three rounds under random delays.","pith_inferences":["If the liveness proof gap in Lemma 6 can be closed, the same three-round wave and $f+1$ reference rule might be portable to non-TEE settings, replacing the trusted counter with digital signatures or erasure-coded broadcast at the cost of extra communication.","The three-round expected commit bound is derived under random message delays; an adversarial scheduler is credited with only a six-round bound, so a worst-case simulation could reveal whether the recursive commit rule ever stalls beyond that.","A small-$n$ configuration with $n=5, f=2$ shows that the 'same set' step inside Lemma 6 does not follow from quorum intersection alone; if that step fails, the liveness bound may need revision for small systems or the commit rule may need an extra condition.","The censorship-resistance guarantee depends on decryption happening strictly after ordering inside the TEE; an empirical test would be to submit timed transactions and check whether any replica can learn a payload before its vertex is committed."],"forward_implications":["If the central claim holds, Fides would combine $2f+1$ resilience with $f+1$ references per vertex, roughly halving the per-vertex metadata and the quorum size of the DAG protocols this work builds on.","The four-round commit rule would give the theoretically minimal commit latency for this DAG structure, with a leader committed every three rounds in expectation under random delays.","The TEE-assisted common coin removes threshold signatures from the critical path, so leader election adds no extra communication rounds beyond the DAG itself.","Transaction encryption until the commitment point would make front-running impossible for replicas, since they cannot read payloads before ordering is fixed.","The reported throughput figures (up to 400k tx/s geo-distributed and 810k tx/s local) would make the protocol practical for permissioned high-throughput deployments."],"supporting_citations":[{"why":"Supplies the asynchronous DAG consensus structure and the round/wave framework that Fides modifies.","marker":"[19]"},{"why":"Provides the wave-based commit rule and ordering baseline; Fides changes the wave length to three rounds and the reference threshold to f+1.","marker":"[20]"},{"why":"Baseline DAG mempool and consensus protocol used for performance comparison and for the garbage-collection mechanism.","marker":"[26]"},{"why":"Classic reliable broadcast protocol whose three all-to-all phases the TEE-assisted reliable broadcast compresses into one.","marker":"[48]"},{"why":"Introduces the trusted monotonic counter for equivocation prevention, the basis of the MIC component.","marker":"[57]"},{"why":"Supplies the trusted execution environment platform assumed for the four trusted components.","marker":"[25]"},{"why":"Prior TEE-assisted BFT protocol whose threat model and performance results Fides follows and compares against.","marker":"[33]"},{"why":"Shows the latency cost of threshold-signature common coins, motivating the lightweight RANG-based coin.","marker":"[23]"}],"fun_headline_variants":["TEE cuts DAG quorum from 2f+1 to f+1 per vertex","Four-round commit in DAG consensus via TEEs","Fides: TEE-assisted DAG consensus with f+1 references","Asynchronous DAG consensus slashes reference quorum","TEEs shrink DAG commit latency to three rounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The liveness proof assumes that quorum intersection alone forces all second-round vertices of a wave to reference the same set of $f+1$ first-round vertices, so that every third-round vertex reaches that same set; this 'same set' consequence does not follow from intersection, and the six-round commit bound depends on it.","fun_headline_variants_meta":{"raw":{"variants":["TEE cuts DAG quorum from 2f+1 to f+1 per vertex","Four-round commit in DAG consensus via TEEs","Fides: TEE-assisted DAG consensus with f+1 references","Asynchronous DAG consensus slashes reference quorum","TEEs shrink DAG commit latency to three rounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000138,"raw_usage":{"total_tokens":1229,"prompt_tokens":1093,"completion_tokens":136,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":709,"completion_tokens_details":{"reasoning_tokens":45}},"tokens_in":709,"tokens_out":136,"duration_ms":1950,"temperature":1.0,"reasoning_tokens":45,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:36:25.673058+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a concrete $n=5$, $f=2$ DAG in which two second-round vertices reference disjoint pairs of first-round vertices and a third-round vertex references both second-round vertices, making its reachable first-round set larger than $f+1$; check whether every such third-round vertex still shares at least $f+1$ first-round ancestors. If a completed wave can have no first-round vertex with $f+1$ strong-path supporters, the expected commit-rate analysis fails.","supporting_citations":[{"cited_title":"All You Need is DAG","cited_arxiv_id":null,"evidence_quote":"Supplies the asynchronous DAG consensus structure and the round/wave framework that Fides modifies."},{"cited_title":"Bullshark: DAG BFT Protocols Made Practical","cited_arxiv_id":null,"evidence_quote":"Provides the wave-based commit rule and ordering baseline; Fides changes the wave length to three rounds and the reference threshold to f+1."},{"cited_title":"Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus","cited_arxiv_id":null,"evidence_quote":"Baseline DAG mempool and consensus protocol used for performance comparison and for the garbage-collection mechanism."},{"cited_title":"Asynchronous Byzantine Agreement Protocols","cited_arxiv_id":null,"evidence_quote":"Classic reliable broadcast protocol whose three all-to-all phases the TEE-assisted reliable broadcast compresses into one."},{"cited_title":"Douceur, Jacob R","cited_arxiv_id":null,"evidence_quote":"Introduces the trusted monotonic counter for equivocation prevention, the basis of the MIC component."},{"cited_title":"Intel SGX Explained","cited_arxiv_id":null,"evidence_quote":"Supplies the trusted execution environment platform assumed for the four trusted components."},{"cited_title":"Hybrids on Steroids: SGX- Based High Performance BFT","cited_arxiv_id":null,"evidence_quote":"Prior TEE-assisted BFT protocol whose threat model and performance results Fides follows and compares against."}],"review_version":1}