{"id":"0045284a-dc9d-4435-a25d-b132a80e4923","arxiv_id":"1908.01738","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"high","formal_verification":"none","parameter_count":7,"one_line_summary":"A new gossip-based protocol, Contagion, provides Byzantine reliable broadcast with O(log N) per-process communication and computation, at the cost of probabilistic rather than deterministic guarantees.","lead":"This paper presents Contagion, a Byzantine reliable broadcast protocol that replaces large quorum sets with small random samples, achieving logarithmic per-process communication. It is the first such protocol with O(log N) complexity, paired with a probabilistic analysis that lets each safety property fail with an arbitrarily small user-chosen probability.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 26's reduction to Threshold Contagion uses link probability l=0, which forbids any infection spread; the stated distribution cannot match Contagion, so the consistency bound of Theorem 13 is unsupported until corrected.","rationale":"The central claim, logarithmic-complexity Byzantine reliable broadcast, requires all three properties to hold with arbitrarily small ϵ. Consistency of Contagion is established by Theorem 13, whose proof depends on the distribution of the number of correct processes ready for a non-delivered message m, as characterized by Lemma 26. That lemma, as written, maps the protocol to a Threshold Contagion game with link probability l=0. With no edges, the game can never infect any healthy node, so the RHS assigns probability 1 to the event that no correct process becomes ready. This cannot be right: a correct process that sampled a Byzantine process receives Ready(m) from that Byzantine process and, for threshold ^R=1, becomes ready with positive probability. The disagreement is not a matter of loose bounds or conservative estimates; it is a concrete false statement for small parameters. Because Lemma 26 feeds directly into the consistency bound, the proof as currently written does not establish the central claim's consistency component. I do not treat this as a rejection of the whole approach: the parallel Lemma 25 suggests the intended link probability was l=1 (or an equivalent all-slots-occupied model), and the error may be a typo. But it must be corrected and the subsequent theorem re-verified. The reader's conditional verdict is therefore appropriate. I do not make the privacy assumption the primary attack: although the paper outsources private sampling to onion routing/private messaging and [10] without a formal proof, that is an explicit, standard modeling assumption and not an internal inconsistency. The Lemma 26 issue is more load-bearing because it is an internal mathematical flaw in the presented proof. Agreement is partial because the reader's weakest_assumption focused on sample privacy, while their rationale did separately flag Lemma 26; my stress-test elevates the lemma to the primary concern.","tokens_in":59037,"tokens_out":10013,"duration_ms":109192,"concrete_test":"Run the direct epidemic process of Lemma 24 on N=3, f=1/3, C=2, R=1, ^R=1, with one Byzantine node initially ready, no correct E-ready, and each correct node's single predecessor chosen uniformly among the 3 processes. By enumeration, correct nodes become ready in 5 of the 9 equally-likely sample assignments (a sample containing the Byzantine node). Compare with Lemma 26's RHS under l=0: the Threshold Contagion game has no edges, so γ(3,1,0,1,1,1)=1 deterministically, giving P[ρ=0]=1. The disagreement falsifies Lemma 26 as stated. Then recompute the consistency term µ in Theorem 13 under the corrected l=1 model (or the full protocol distribution) for the parameters used in Figure 2; if the failure probability rises above the claimed ~10^-16, the logarithmic-complexity claim requires revised security parameters.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 26 (Appendix C.7) is load-bearing for Contagion's consistency bound (Theorem 13) but its reduction to Threshold Contagion is internally inconsistent. The lemma considers an execution in which no correct process pcb.Delivers m and every Byzantine process sends Ready(m) to every correct process from which it received a ReadySubscribe. It claims P[ρ=r] = P[γ(N,R,0,1,N-C,^R)=r+(N-C)]. Under the paper's own definition (Appendix E.3), l is the probability that each of the R predecessor slots exists; l=0 gives an edge-free multigraph, so no healthy node ever reaches threshold ^R and γ is identically N-C. The RHS therefore assigns probability 1 to r=0. In the protocol, however, a correct process whose ready sample contains a Byzantine process receives Ready(m) from it (Algorithm 7, lines 20-23 and 37-45), and already for N=3, C=2, R=1, ^R=1 the protocol has P[ρ>0] = 1-(2/3)^2 > 0 while the RHS predicts P[ρ=0]=1. Lemma 25's analogous reduction correctly uses l=1-f for the correct-only graph; Lemma 26 needs l=1 (every slot is occupied, including Byzantine predecessors), not 0. Since Theorem 13 builds µ on this distribution, the stated consistency bound is unsupported until Lemma 26 is corrected and the subsequent bounds re-derived.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a probabilistic relaxation of Byzantine reliable broadcast in which each property (validity, consistency, totality) may fail with probability at most epsilon. It presents three protocols: Murmur, a gossip-based probabilistic broadcast; Sieve, an echo-based probabilistic consistent broadcast; and Contagion, a feedback-based probabilistic reliable broadcast that combines Sieve with a ready/delivery sample mechanism. Samples drawn from a uniform private sampling oracle replace quorums, giving O(log N) per-process communication and O(log N / log log N) latency for fixed epsilon. The main technical contributions are adversary decorators, used to reduce the Sieve adversary to a tractable two-phase form, and the Threshold Contagion game, used to analyze the Contagion feedback loop. The paper claims the first Byzantine reliable broadcast protocol with logarithmic per-process communication complexity in the asynchronous model with a static Byzantine adversary, with numerical failure probabilities around 10^-16.","tokens_in":59395,"tokens_out":8930,"duration_ms":88689,"significance":"If the analysis is correct, this is a substantial result: it replaces quorum intersection with representative random samples and provides an end-to-end probabilistic security argument for Byzantine reliable broadcast in a setting where previous protocols had linear per-process complexity. The manuscript is unusually detailed for an extended version: elementary properties (no duplication, integrity, Murmur totality via Erdos-Renyi connectivity) are proved cleanly, and the decorator framework is an original proof technique that may be reusable beyond this paper. The Threshold Contagion model is also a valuable abstraction for gossip-style feedback mechanisms. The paper does not provide machine-checked proofs or executable code, and the numerical section is not reproducible from the text; those are weaknesses in presentation rather than in the core analytic method. The central issue is a load-bearing inconsistency in the Contagion consistency proof, described below.","major_comments":[{"comment":"Lemma 26 is inconsistent with the Threshold Contagion model it invokes. The lemma claims P[rho] = P[gamma(N,R,0,1,N-C,hatR) = rho+(N-C)] for an execution in which no correct process pcb.Delivers m and every Byzantine process sends Ready(m) to every correct process that subscribed to it. Under the paper's own definition, l is the probability that each of the R predecessor slots exists; l=0 yields an edge-free multigraph, so no healthy node can ever reach threshold hatR and gamma is identically N-C. The right-hand side is therefore a point mass at rho=0. The protocol, however, has a positive probability of correct processes becoming ready: already with N=3, C=2, R=1, hatR=1, a correct process's single ready sample is Byzantine with probability f=1/3, and that Byzantine process sends Ready(m) to it, so P[rho>0] = 1-(2/3)^2 = 5/9. This contradicts the claimed distribution. Lemma 25's analogous reduction correctly uses l=1-f for the correct-only graph; Lemma 26 needs l=1, because every ready-sample slot is occupied and Byzantine predecessors act as initially infected nodes. Since Theorem 13 builds the consistency bound mu on gamma+, the stated bound is unsupported until Lemma 26 is corrected and the subsequent formulas in Theorem 13 are re-derived.","section":"Appendix C.7, Lemma 26; Appendix E.3; Theorem 13"},{"comment":"The privacy and uniformity of the sampling oracle are load-bearing assumptions that are not connected to a concrete implementation by any theorem. Section 2 assumes the adversary never learns which correct processes communicate with one another and cites onion routing, private messaging, and the BRAHMS sampling oracle [10], but no result states that those mechanisms provide exactly uniform, independent samples that remain hidden from a static Byzantine adversary. The decorator reductions in Appendix B and the sample-blind adversary argument in particular rely on the adversary seeing only the Byzantine membership of samples, not the samples themselves. If an implementation allows even one sample to be biased or observed, the Chernoff-based bounds in Theorems 9 and 14 no longer follow. Please either state formally that the ideal private uniform oracle is a modeling assumption and scope the practical claims accordingly, or supply a composition proof with [10] and the private-communication layer.","section":"Section 2; Appendices B and C"}],"minor_comments":[{"comment":"The numerical evaluation does not report the concrete parameter values used (G, E, R, D, the four thresholds, N, f) and does not provide code or data. A short table of the parameter settings and an artifact link would make the claimed 10^-16 failure probabilities checkable.","section":"Section 6 and Figure 2"},{"comment":"The definition of epsilon-totality contains the typo 'probabiity'; it should read 'probability'.","section":"Appendix C.1, totality definition"},{"comment":"The Byzantine oracle Psi is an artificial assumption used only for Simplified Sieve; the paper explicitly says no correct process invokes Psi during Sieve. This is acceptable, but the text should state once more, right before Theorem 9, that the final bound does not depend on Psi being implementable.","section":"Appendix B.6.2 and Algorithm 5"}],"recommendation":"major_revision","confidential_remarks":"The core contribution is significant and the proof framework is original. The Lemma 26 inconsistency is local and likely repairable, but until it is fixed, the Contagion consistency bound is not established. The numerical claims are also currently not reproducible. I would not reject the paper on these grounds, but the revision must address the threshold-contagion parameterization before the central claim can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, this is a real result: Contagion is the first Byzantine reliable broadcast protocol with logarithmic per-process communication, and the companion machinery (adversary decorators, Threshold Contagion) is worth stealing. Second, the proof as printed is not sound. Lemma 26, which Theorem 13 leans on, has a parameter error that makes the stated consistency bound unsupported. I do not think the protocol is broken, but the paper needs a fix before anyone should trust the headline.\n\nWhat is genuinely new: replacing quorum intersections with private random samples, and analyzing the resulting protocol with a full probabilistic model instead of a hand-wave. The structure—Murmur for gossip, Sieve for consistency, Contagion for totality—is clean, the pseudocode is complete, and the simpler properties (no duplication, integrity, validity) are proved cleanly. The literature review is fair, and the relationship to probabilistic quorum work is acknowledged.\n\nWhere it wobbles. The load-bearing problem is in Appendix C.7. Lemma 26 claims that an execution with no correct process having delivered m, and every Byzantine process sending Ready(m) to all subscribers, is modeled by Threshold Contagion with link probability l=0. Under the paper's own definitions, l is the probability a predecessor slot exists. Setting l=0 gives an edge-free multigraph, so infection never spreads and the lemma assigns probability 1 to rho=0. But in the protocol a correct process becomes ready when enough of its R-sample are Byzantine, because those Byzantine predecessors reply. With N=3, C=2, R=1, ^R=1, the lemma predicts no ready correct processes with certainty, while the actual probability that at least one correct process becomes ready is 5/9. Lemma 25 correctly uses l=1-f for the correct-only graph; Lemma 26 should use l=1 (all slots populated, including Byzantine picks), not 0. If that is the fix, the gamma-plus distribution changes and mu in Theorem 13 has to be recomputed. As it stands, the consistency bound does not follow.\n\nMinor but real: the numerical evaluation has no artifact, no parameter table, and no code pointers, so Figure 2 is not independently checkable. The privacy assumption (the adversary never learns which correct processes communicate with one another) is outsourced to onion routing or private messaging; that is a legitimate systems assumption, but the paper should state more sharply what exactly is needed and what can break it.\n\nWho it is for: researchers working on scalable BFT and permissionless consensus. The analysis framework alone justifies reading it. My own verdict would be conditional: fix Lemma 26, re-derive the bounds, and ship the numerical parameters. Then it is an accept.","headline":"A strong protocol with reusable analysis, but Lemma 26 has a load-bearing parameter error that must be fixed before the logarithmic-consistency claim is credible.","tokens_in":59873,"tokens_out":3454,"would_cite":true,"duration_ms":37750,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68W15","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims the first Byzantine reliable broadcast protocol with logarithmic per-process communication and computation, replacing quorums with private random samples and accepting small quantified failure probabilities.","keywords":["Byzantine reliable broadcast","probabilistic broadcast","stochastic samples","gossip protocols","adversary decorators","threshold contagion","logarithmic communication complexity","asynchronous distributed systems"],"falsifier":"Build the protocol on a network where the adversary can observe message metadata (no onion routing or private messaging) and run the numerical parameter regime claimed to give $10^{-16}$; if the adversary can then bias the ready or delivery sample of a single targeted correct process—for instance, by sending subscriptions that fill that process's sample with Byzantine identities—and the measured probability of a consistency or totality violation exceeds the claimed $\\epsilon$, the analysis's core privacy assumption is violated.","tokens_in":58855,"feed_emoji":"📡","tokens_out":4971,"duration_ms":51432,"temperature":0.7,"pith_summary":"The paper sets out to prove that Byzantine reliable broadcast—the primitive that lets a group of processes agree on a sender's message despite some members, possibly including the sender, being malicious—can be made scalable. Its protocol, Contagion, replaces the traditional quorum, whose size is linear in the number of processes $N$, with small random samples, and accepts that each broadcast property (validity, consistency, totality) fails with a fixed probability $\\epsilon$ that the analysis bounds. The central claim is that for any fixed $\\epsilon$ the per-process communication and computation stay $O(\\log N)$, with $O(\\log N / \\log\\log N)$ latency, and that for realistic parameters the failure probability is around $10^{-16}$ with thousands of processes. If correct, this is the first logarithmic-cost Byzantine reliable broadcast under an asynchronous model with a static Byzantine adversary.","feed_headline":"Byzantine reliable broadcast drops to logarithmic cost","feed_subtitle":"Random samples replace quorums, keeping failure odds near 10^-16 for networks of thousands of nodes.","key_machinery":"The load-bearing object is the private stochastic sample, replacing quorums: each process randomly selects $O(\\log N)$ peers for gossip, echo, ready, and delivery roles, relying on Chernoff-type concentration instead of intersection guarantees. Around this, two analysis tools carry the proof: adversary decorators, which transform any Byzantine adversary into a stronger one within a smaller class (ultimately two-phase adversaries) so that bounding failure under the restricted class bounds it for all adversaries; and Threshold Contagion, a game on a random multigraph that models how 'ready for message $m$' spreads through correct processes and shows the adversary's strategy cannot bias the final infection count. The ready threshold being lower than the delivery threshold is the mechanism that produces the all-or-none totality behavior.","core_discovery":"The paper's central discovery is a probabilistic generalization of Byzantine reliable broadcast plus an algorithm achieving it: each correct process uses private random samples instead of intersecting quorums, and the protocol is shown $\\epsilon$-secure with $\\epsilon$ arbitrarily small. Murmur provides probabilistic broadcast by gossip; Sieve provides consistency through echo samples and an adversarial analysis that reduces the set of strategies to 'two-phase adversaries' via adversary decorators; Contagion adds totality using a ready/delivery threshold feedback loop modeled as a Threshold Contagion game, in which the adversary's choices provably do not bias the infection process. The combined result: per-process communication and computation $O(\\log N)$, latency $O(\\log N / \\log\\log N)$, and numerical violation probabilities of order $10^{-16}$ for systems of thousands of processes. The analysis claims the first formal treatment of a probabilistic broadcast protocol under Byzantine faults, and the first logarithmic-complexity Byzantine reliable broadcast.","pith_inferences":["Editorial inference: if the private-sampling assumption can be enforced cheaply via anonymous communication, the logarithmic complexity should transfer to permissionless settings with churn, since the paper's sampling oracle is already designed for membership-free systems.","Editorial inference: the adversary-decorator method is a general recipe for bounding failure probabilities by shrinking the adversary's strategy space, and could be reused for other probabilistic consensus primitives.","Editorial inference: the threshold separation $\\hat{R}/R < \\hat{D}/D$ is a tunable knob the paper fixes; varying the gap should trade a larger critical infected fraction for a lower totality failure probability, which an implementation could exploit."],"forward_implications":["Byzantine reliable broadcast becomes practical at thousands of processes with per-node cost $O(\\log N)$ and near-negligible failure probability, if the sampling and privacy assumptions hold.","A Byzantine sender cannot make two correct processes deliver different messages except with probability $\\epsilon$, and cannot cause some-but-not-all correct delivery except with probability $\\epsilon$.","Failure probability decays exponentially in average sample size and grows at most quadratically in $N$, so keeping $\\epsilon$ fixed forces sample sizes to grow logarithmically.","Latency is $O(\\log N / \\log\\log N)$, comprising gossip dissemination plus two extra message delays for echo and ready rounds.","The same sample-based replacement for quorums can be applied to other quorum-based primitives, reducing their communication from linear to logarithmic at the price of probabilistic guarantees."],"supporting_citations":[{"why":"Defines Byzantine reliable broadcast, the primitive and the all-or-none delivery structure that Contagion mirrors in its final phase.","marker":"[12]"},{"why":"Supplies the Erdős–Rényi connectivity phase transition used to bound Murmur's totality and gossip diameter.","marker":"[21]"},{"why":"Provides the sparse random graph diameter result used for Murmur's $O(\\log N/\\log\\log N)$ latency.","marker":"[17]"},{"why":"Gives the near-uniform sampling mechanism the protocol relies on in membership-free and churning systems.","marker":"[10]"},{"why":"Introduces probabilistic quorums, the conceptual predecessor that justifies replacing deterministic intersections with random samples.","marker":"[44]"},{"why":"Underlies the echo-based consistent broadcast pattern that Sieve adapts from quorum to sample form.","marker":"[13]"},{"why":"Cited as the onion-routing mechanism implementing the private-communication assumption needed to hide samples from the adversary.","marker":"[18]"},{"why":"Cited as the private-messaging mechanism also available for hiding which correct processes talk to each other.","marker":"[52]"}],"fun_headline_variants":["Random samples replace quorums in Byzantine broadcast","Probabilistic Byzantine broadcast achieves log complexity","First logarithmic Byzantine reliable broadcast","Sampling beats quorums for Byzantine reliable broadcast"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole failure analysis assumes the Byzantine adversary never learns which correct processes communicate with one another—equivalently, that it cannot see or poison the private random samples of any targeted correct process—so the uniform sampling on which every bound rests stays hidden from it.","fun_headline_variants_meta":{"raw":{"variants":["Random samples replace quorums in Byzantine broadcast","Probabilistic Byzantine broadcast achieves log complexity","First logarithmic Byzantine reliable broadcast","Sampling beats quorums for Byzantine reliable broadcast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000534,"raw_usage":{"total_tokens":2585,"prompt_tokens":980,"completion_tokens":1605,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":596,"completion_tokens_details":{"reasoning_tokens":1550}},"tokens_in":596,"tokens_out":1605,"duration_ms":11481,"temperature":1.0,"reasoning_tokens":1550,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:06:03.563929+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the protocol on a network where the adversary can observe message metadata (no onion routing or private messaging) and run the numerical parameter regime claimed to give $10^{-16}$; if the adversary can then bias the ready or delivery sample of a single targeted correct process—for instance, by sending subscriptions that fill that process's sample with Byzantine identities—and the measured probability of a consistency or totality violation exceeds the claimed $\\epsilon$, the analysis's core privacy assumption is violated.","supporting_citations":[{"cited_title":"Asynchronous Byzantine agreement protocols","cited_arxiv_id":null,"evidence_quote":"Defines Byzantine reliable broadcast, the primitive and the all-or-none delivery structure that Contagion mirrors in its final phase."},{"cited_title":"On random graphs.Publicationes Math- ematicae, 6:290–297, 1959","cited_arxiv_id":null,"evidence_quote":"Supplies the Erdős–Rényi connectivity phase transition used to bound Murmur's totality and gossip diameter."},{"cited_title":"The diameter of sparse random graphs","cited_arxiv_id":null,"evidence_quote":"Provides the sparse random graph diameter result used for Murmur's $O(\\log N/\\log\\log N)$ latency."},{"cited_title":"Brahms: Byzantine resilient random membership sampling","cited_arxiv_id":null,"evidence_quote":"Gives the near-uniform sampling mechanism the protocol relies on in membership-free and churning systems."},{"cited_title":"Probabilistic quorum systems","cited_arxiv_id":null,"evidence_quote":"Introduces probabilistic quorums, the conceptual predecessor that justifies replacing deterministic intersections with random samples."},{"cited_title":"Asynchronous Consensus and Broad- cast Protocols","cited_arxiv_id":null,"evidence_quote":"Underlies the echo-based consistent broadcast pattern that Sieve adapts from quorum to sample form."},{"cited_title":"Tor: The second-generation onion router","cited_arxiv_id":null,"evidence_quote":"Cited as the onion-routing mechanism implementing the private-communication assumption needed to hide samples from the adversary."},{"cited_title":"Vuvuzela: Scalable private messaging resistant to traffic analy- sis","cited_arxiv_id":null,"evidence_quote":"Cited as the private-messaging mechanism also available for hiding which correct processes talk to each other."}],"review_version":1}