{"id":"23439b4f-7909-4d4a-96a5-77440bcfc64a","arxiv_id":"2501.15904","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Snowman⋄ is a lock-based variant of the Snowman consensus protocol proved to achieve probabilistic consistency under partial synchrony without lockstep sampling rounds.","lead":"Snowman⋄ modifies the Avalanche blockchain's Snowman protocol to keep blocks consistent when message delays are unbounded and computers sample at their own speed. The change adds a locking step and a probabilistic proof that two honest computers cannot finalize different chains.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised 2e-5 error bound rests on an unenforced 5-rounds/sec cap; Algorithms 2/3 let correct processes initiate rounds faster when message delays are small, so the abstract overstates what the proof gives.","rationale":"The reader's weakest-assumption pinpoints the same load-bearing gap. I re-read the Snowflake⋄ and Snowman⋄ proofs with this in mind. The per-round probabilistic arguments (binomial bounds, the lock/unlock contradiction for (†⋄1), and the decomposition in §8 Part 2) are internally plausible, and the consistency conclusion does follow if one accepts the 'at most 5 rounds per second' accounting. The trouble is that the protocol text contains no rate limiter or minimum round spacing: Algorithm 2 lines 36-47 and Algorithm 3 lines 44-45 allow early progression on sufficient responses or after 2Δ, and partial synchrony permits arbitrarily small message delays after GST, so a correct process can legitimately initiate rounds faster than 5/s. Because the proof's union bounds are linear in the number of round initiations, the advertised 2e-5 is not a property of the protocol alone. This does not falsify the conditional theorem, and it is not an internal inconsistency; it is a gap between the abstract's unconditional wording and the proven conditional statement. No additional concern supersedes this one; the honest fix is either to enforce a minimum spacing (e.g., a 200ms/round timer) or to state all error bounds as functions of the actual round rate and total execution length. I therefore keep the reader's CONDITIONAL verdict rather than moving it.","tokens_in":31559,"tokens_out":14665,"duration_ms":140999,"concrete_test":"Run a discrete-event simulation of Algorithm 3 with n=250 correct processes, Δ=1s, and one-way message delay ε=0.01s after GST, measuring each process's round-initiation rate over a 100s interval (count increments of s at line 45). If the observed rate exceeds 5/s, recompute the Section 8 union bound with the observed rate r: the leading error term becomes 1e4 × (r × 3.1536e10) × 1.18e-20 = (3.72e-6)·r, which already exceeds 2e-5 for r>5.4/s. This directly settles whether the protocol, without modification, can produce executions in which the advertised 2e-5 bound does not follow from the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Sections 6 and 8 every union bound is computed under the Section 2 assumption that each process initiates at most 5 rounds per second (e.g., §6 Part 1 counts fewer than 1.6e11 rounds per process; §8 Part 1 and Part 2 use the same count). The protocol itself imposes no such cap. Algorithm 2 (lines 36-47) and Algorithm 3 (lines 44-45) permit a new round as soon as either enough responses have arrived to determine the round value or 2Δ has elapsed since start; in partial synchrony, once past GST the adversary may schedule message delays much smaller than Δ and correct processes may answer promptly, so a correct process can initiate rounds at rates far above 5/sec. The per-round failure probabilities (1.18e-20 for (†⋄0), 0.0131^12 for (†⋄2)) are per round initiation, so the cumulative error is R × 1e4 × 1.18e-20 + ...; at even 100 rounds/sec over 1000 years the leading term is about 3.7e-4, already 20x the advertised 2e-5, and at higher rates the bound degrades further. The theorem is therefore conditional on an execution cap that the protocol does not enforce; the abstract's unconditional 'ensures consistency ... at their own speed' is stronger than the proof supports. The proof itself appears coherent if one accepts the cap as an external bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper presents Snowflake⋄ and Snowman⋄, modifications of the Snowflake+ and Snowman protocols introduced in [9], and analyzes them in the partially synchronous setting without the lockstep assumption. Snowflake⋄ is a binary Byzantine agreement protocol in which processes sample k peers and update their value upon seeing α1 samples of the opposite color, and lock on a value upon seeing α2 samples of their present value; a lock can be broken only by α2 samples reporting the opposite color with a sufficiently long lock time. Snowman⋄ builds a state-machine-replication protocol from multiple Snowflake⋄ instances over the bits of block hashes. The main results are probabilistic agreement for Snowflake⋄ (Section 6) and probabilistic consistency for Snowman⋄ (Section 8): for t < n/5, n ≥ 250, k = 80, α1 = 41, α2 = 72, β = 12, the cumulative probability of inconsistency is bounded by approximately 2e-5, under the accounting assumption that at most 10,000 processes run for at most 1,000 years with each process initiating at most 5 rounds per second. The proofs proceed by establishing three invariants, namely (†⋄0), (†⋄1), and (†⋄2), via binomial tail bounds and union bounds over processes and rounds. Section 9 discusses optional mechanisms for quicker finality.","tokens_in":31886,"tokens_out":10688,"duration_ms":96293,"significance":"If the stated bounds hold, the paper is a meaningful step: it removes the synchronous lockstep restriction from the prior analysis of Snowman and provides explicit parameter values and concrete error probabilities for a partially synchronous setting. The proof technique is transparent: the key probabilistic facts are simple binomial calculations, and the protocol pseudocode is precise enough to check the round and response accounting. The paper also honestly identifies t < n/5 as a convenience assumption and refers to the Frosty module for liveness, so the contribution is sharply scoped to consistency. The main qualification is that the advertised 2e-5 error bound is conditional on a per-process round-rate cap that the protocol does not enforce; as written, the central theorem overstates what the proof establishes. With that gap repaired, either by enforcing the cap in the protocol or by stating the theorem conditionally, the paper would make a solid contribution to the rigorous analysis of the Snow family.","major_comments":[{"comment":"The advertised consistency error bound, under 2e-5 in Sections 6 and 8, is computed under the assumption that each process initiates at most 5 rounds per second, but the protocol does not enforce any such rate limit. Algorithm 2 (lines 36-48) and Algorithm 3 (lines 44-45) allow a correct process to start a new round as soon as the responses received so far suffice to determine the round value, or after a 2Δ timeout; in partial synchrony, once past GST the adversary can schedule message delays much smaller than Δ and correct processes can respond promptly, so a correct process can initiate rounds at rates arbitrarily higher than 5 per second. The per-round failure probabilities, such as 1.18e-20 for (†⋄0) and 0.0131^12 for (†⋄2), are per round initiation, so the cumulative error grows linearly with the number of initiations. At 100 rounds per second per process over 1000 years, the (†⋄0) contribution alone is about 3.7e-4, already exceeding the advertised 2e-5. The theorem statements at the starts of Sections 6 and 8 do not list a round-rate bound among their hypotheses. I recommend either adding a minimum spacing between round initiations to Algorithms 2 and 3 and proving the bound for that modified protocol, or explicitly stating the theorem as conditional on an environment-imposed execution bound and revising the abstract's claim that processes proceed 'at their own speed'.","section":"Sections 3.1, 6, 8; Algorithms 2 and 3"},{"comment":"The proof of consistency for Snowman⋄ is presented as a compressed analogue of the Snowflake⋄ argument, but it is the central theorem of the paper and needs to be spelled out at the same level of detail as Section 6. In particular, Part 3 states that consistency 'follows directly from (†⋄1) and (†⋄2)' after defining the strings Ξ_t and Ξ*_t, but it does not fully justify why the 'longest string' thresholds remain well-defined as the preferred prefix pref grows, how the lock and unlock conditions in Algorithm 3 (lines 15-19 and 35-41) preserve the invariants across the multiple Snowflake⋄ instances, or why the union bound in Part 2 remains valid when a process may initiate rounds at different rates for different parts of the hash chain. These steps are plausible and analogous to Section 6, but they are load-bearing for the paper's central claim and should be expanded so that a reader can verify the induction without reconstructing it.","section":"Section 8"}],"minor_comments":[{"comment":"The '5 rounds per second' bound is introduced as an accounting assumption in the prose but is not named as a formal parameter. I recommend defining R_max explicitly and stating the final theorem as, for example, 'for any execution with at most R_max round initiations per process, the error probability is at most ...'.","section":"Sections 3.1 and 6"},{"comment":"The proof uses the symbols Ξ_t and Ξ*_t, whose subscript and superscript placement is easy to confuse in the typeset text; using distinct symbols such as A_t and B_t would improve readability.","section":"Section 8"},{"comment":"The temporary-finality analysis assumes clocks synchronized to within Δ* but does not state whether Δ* is known to the processes or only to the analyst; this should be clarified.","section":"Section 9"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The manuscript is a serious theoretical contribution, and the main proof strategy is sound under the stated execution accounting. The unenforced 5-rounds-per-second cap is the key obstacle: it is not a minor typo, because the advertised error probability depends linearly on the number of round initiations, and the protocol as written permits unbounded initiation rates. I believe this is repairable with an explicit rate-limiting mechanism or an honest conditional theorem, so I recommend major revision rather than rejection. The current Section 8 also needs expansion, but that is less concerning than the rate cap. The paper's use of [9] is appropriate and not circular."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main contribution is real: a Snowman variant with an explicit lock/locktime mechanism, and a probabilistic consistency proof that works in partial synchrony without the lockstep assumption. The proof is the paper. The three-part structure around (†⋄0), (†⋄1), and (†⋄2) is clear, and the binomial accounting is consistent. The paper also does the right thing by focusing on consistency and leaving liveness to the Frosty module from the earlier paper. The citation pattern is fine; the self-citation to [9] is appropriate since this is explicitly an extension of that analysis.\n\nThe soft spot is the round-rate cap. Every union bound in Sections 6 and 8 assumes each process initiates at most 5 rounds per second. The protocol imposes no such limit. Algorithm 2's lines 36–47 and Algorithm 3's lines 44–45 start a new round as soon as the responses for the current round suffice, or after 2Δ. Once past GST, the adversary can arrange message delays well below Δ, so a correct process can initiate rounds far faster than 5/sec. The per-round failure probabilities are per round initiation, so the cumulative error scales with the actual rate. At 100 rounds/sec, the leading term alone is about 3.7e-4, twenty times the advertised 2e-5. The theorem, as stated, is conditional on an external bound the protocol does not enforce, and the abstract overstates what the proof gives.\n\nThis is fixable. Enforce a minimum spacing between rounds, or state the error bound as a function of the actual round rate. The rest of the proof is plausible and deserves a careful read. The Snowman⋄ section is compressed — it is an analogue of Section 6 rather than a fully expanded argument — but the mapping is reasonable, and Section 9's temporary-finality discussion is honest about its extra assumptions.\n\nWho this is for: people working on leaderless BFT and Avalanche-style protocols. It is a serious paper with a genuine new result, and it should go to peer review. The round-rate gap needs to be addressed before publication, but it is not a reason to desk-reject.","headline":"Real new result — a non-lockstep partial-synchrony consistency proof for Snowman — but the advertised 2e-5 error bound rests on a 5-rounds-per-second cap the protocol never enforces.","tokens_in":32427,"tokens_out":3049,"would_cite":true,"duration_ms":28255,"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":"Snowman consensus stays safe under partial synchrony","keywords":["Snowman protocol","Avalanche","partial synchrony","probabilistic consensus","Byzantine fault tolerance","state machine replication","metastability"],"falsifier":"Run Snowman⋄ with 250 processes and 49 Byzantine processes under partial synchrony, with adversarial message-delivery schedules that concentrate multiple sampling rounds within a small window while 75% of correct processes are locked on red. The paper's claim is that a locked process switches to blue with probability below $1.9\\times 10^{-5}$ per such opportunity; a simulation that, across many independent opportunities, finds a higher frequency of unlocks and incompatible finalizations would refute the bound.","tokens_in":31314,"feed_emoji":"☃️","tokens_out":6876,"duration_ms":68299,"temperature":0.7,"pith_summary":"The paper claims that a modified version of Avalanche's Snowman protocol, called Snowman⋄, guarantees probabilistic consistency even when message delays are unbounded before an unknown global stabilization time and when correct processes run sampling rounds as fast as their local message delays allow. This removes two restrictions of the prior proof: synchrony and lockstep execution. The key change is a lock rule that makes a sufficiently strong sampled majority sticky, so the earlier 75%-threshold argument can be rebuilt without synchronized clocks. For at least 250 processes, fewer than one fifth of them Byzantine, and parameters $k=80$, $\\alpha_1=41$, $\\alpha_2=72$, $\\beta=12$, the paper bounds the probability that any two correct processes finalize incompatible chains by about $2\\times 10^{-5}$ under stated bounds on execution length and round rate. If correct, Snowman⋄ gives Avalanche-style low communication cost with a safety guarantee that holds through periods of asynchrony.","feed_headline":"Snowman consensus stays safe under partial synchrony","feed_subtitle":"A lock-on-sampling modification removes the lockstep assumption and bounds inconsistency below 2e-5.","key_machinery":"The machinery is the lock/locktime state attached to each sampled value. In Snowflake⋄, the local variable $val$ is the current bit, $lock$ says whether the process has recently seen a strong sample ($\\alpha_2$ out of $k$) of that bit, and $locktime$ records when it locked; responses report the value together with the duration for which it has been locked. A locked process can only switch color after sampling $\\alpha_2$ responses reporting the opposite value locked for at least $2\\Delta$. This replaces the lockstep assumption with an interval-based threshold: the protocol's statements $(\\dagger^\\diamond_0)$, $(\\dagger^\\diamond_1)$, and $(\\dagger^\\diamond_2)$ show that a 75% locked-on-red interval is absorbing and that any output implies such an interval existed. Snowman⋄ runs one Snowflake⋄ instance per bit of the hash chain, using the first disagreeing bit to choose between competing blocks, so the same lock machinery lifts to state machine replication.","core_discovery":"The central discovery is that consistency for Snowman does not require synchrony or lockstep if the protocol makes its decision threshold sticky. In Snowflake⋄, the binary agreement layer underlying Snowman⋄, a process that samples at least $\\alpha_2$ copies of its current color in a round locks onto that color; once locked, it only flips after a later sample reports at least $\\alpha_2$ processes locked on the opposite color for at least $2\\Delta$. Because sampled processes report how long they have been locked, a process can tell whether a response supports the claim that a large locked majority existed throughout a recent interval, even though clocks are not synchronized. The proof then mirrors the synchronous argument: if 75% of correct processes are locked on a value for an interval of length $2\\Delta$, the locked set is stable forever (except with small probability), and no one can finalize the opposite value. Section 8 converts this into a probabilistic consistency guarantee for Snowman⋄: with $k=80$, $\\alpha_1=41$, $\\alpha_2=72$, $\\beta=12$, at least 250 processes, and fewer than one fifth Byzantine, cumulative error below $2\\times 10^{-5}$.","pith_inferences":["The stated $2\\times 10^{-5}$ bound is an accounting bound, not a protocol-invariant one: nothing in Snowman⋄ prevents a process from starting more than five rounds per second when delays are small, so a deployment that wants the bound should enforce a round pace or re-derive the union bound for faster rounds.","The lock-and-report-locktime mechanism is a general recipe for adding partial-synchrony safety to other metastable sampling protocols; one could try attaching the same $2\\Delta$-lock semantics to DAG-based Avalanche or to FPC-BI-style voting.","A natural empirical check is to simulate Snowman⋄ around the global stabilization time with adversarial message schedules and measure how often the 75%-locked interval property fails; the paper predicts a rate below $1.9\\times 10^{-5}$ for the stated parameters, which is testable even though the full 1000-year bound is not."],"forward_implications":["If the proof is correct, Snowman⋄ remains safe during arbitrarily long periods of asynchrony before the global stabilization time, rather than only under reliable communication.","A correct process's finalized chain only grows over time, and no two correct processes can finalize chains that diverge, except with probability below $2\\times 10^{-5}$ under the stated bounds.","The result tolerates any number of crash or omission failures alongside fewer than one fifth Byzantine processes, because the consistency argument does not rely on liveness of crashed processes.","With a known bound $\\Delta^*$ on clock skew, the protocol can cut finalization latency by up to $2\\Delta$; with an additional assumption that at most 10% of processes are Byzantine over a one-hour window, temporary finalization has reversion probability below $10^{-6}$.","Communication remains sampling based, so the expected per-participant cost stays constant in the common case, preserving the scalability property that motivated Snowman."],"supporting_citations":[{"why":"Gives the prior Snowman/Snowflake+ analysis in synchronous lockstep, whose three-part threshold argument this paper adapts to partial synchrony.","marker":"[9]"},{"why":"Introduces the Snow family and the original Snowman protocol that Snowman⋄ modifies.","marker":"[26]"},{"why":"Supplies the O(log n)-round stabilization analysis used to justify the paper's decision not to prove termination.","marker":"[1]"},{"why":"Provides the earlier formal security treatment of Avalanche consensus and its liveness attack, which motivates the partial-synchrony setting.","marker":"[2]"}],"fun_headline_variants":["Snowman's lock-on-sampling fixes partial synchrony","Snowman consensus without lockstep: partial sync safe","Partial synchrony? Snowman now provably safe","Snowman's sticky threshold ensures safety in partial sync","Lock-on-sampling keeps Snowman consistent partially async"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is the accounting bound under which the error probabilities are union-bounded: at most 10,000 processes running for at most 1,000 years at at most five sampling rounds per second, a cap the protocol itself does not enforce.","fun_headline_variants_meta":{"raw":{"variants":["Snowman's lock-on-sampling fixes partial synchrony","Snowman consensus without lockstep: partial sync safe","Partial synchrony? Snowman now provably safe","Snowman's sticky threshold ensures safety in partial sync","Lock-on-sampling keeps Snowman consistent partially async"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000161,"raw_usage":{"total_tokens":1193,"prompt_tokens":857,"completion_tokens":336,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":259}},"tokens_in":473,"tokens_out":336,"duration_ms":3482,"temperature":1.0,"reasoning_tokens":259,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T13:51:22.864086+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Snowman⋄ with 250 processes and 49 Byzantine processes under partial synchrony, with adversarial message-delivery schedules that concentrate multiple sampling rounds within a small window while 75% of correct processes are locked on red. The paper's claim is that a locked process switches to blue with probability below $1.9\\times 10^{-5}$ per such opportunity; a simulation that, across many independent opportunities, finds a higher frequency of unlocks and incompatible finalizations would refute the bound.","supporting_citations":[{"cited_title":"An Analysis of Avalanche Consensus","cited_arxiv_id":"2401.02811","evidence_quote":"Supplies the O(log n)-round stabilization analysis used to justify the paper's decision not to prove termination."},{"cited_title":"When is Spring coming? A Security Analysis of Avalanche Consensus","cited_arxiv_id":"2210.03423","evidence_quote":"Provides the earlier formal security treatment of Avalanche consensus and its liveness attack, which motivates the partial-synchrony setting."}],"review_version":1}