CS Paper Radar

Soundness of the GKR Protocol for Sparse-Merkle Updates, with a Machine-Checked Core

Jinwook Kim

cs.CR cs.LO ·submitted 2026-10-04 15:56 UTC · v3
theorycode/data

Abstract

The GKR soundness theorem bounds the acceptance of a false output claim for a fixed circuit and input. It does not say what the outputs of a compiled circuit mean for that input, and that has to be proved for each family of circuits. For a sparse Merkle tree over a compressing hash, heuristically almost every root admits a valid path for almost any leaf, so the needed statement concerns the witness as well as the claim. We prove per-input soundness for membership, non-membership and update claims, for trees of every depth, in the delegation setting of GKR: the verifier reads the circuit input in the clear and leaves the node hashes to the circuit. Assuming correct hash sub-circuits, every accepted input, honestly encoded or not, determines a valid witness, and the chain constraint cannot be dropped. If the witness read from an input fixed before the challenges is not valid, this verifier accepts with probability at most $\bigl(s_{\mathrm{out}}+\sum_i(8s_i+1)\bigr)/|\mathbb{F}|$ for a circuit with $2^{s_{\mathrm{out}}}$ outputs and $2^{s_i}$ wires read at layer $i$. This covers cube gates for the Poseidon2 S-box and, with $|\mathbb{F}| = p^4$, circuits over the 31-bit KoalaBear field with challenges from its quartic extension. The implemented node hash, a truncated permutation, is not collision resistant, so the statement that accepted runs for one key and root assert the same leaf assumes position binding of the tree. All our results are proved in the paper. Isabelle/HOL also checks a layer-chain bound, the exactness of the verifier's checks on encoded witnesses in a constraint-level model with abstract hash sub-circuits and, over one field, their composition for claims with no valid witness. All bounds concern the interactive public-coin protocol.

Comment
36 pages, 4 figures, 3 tables. v3: new title; the collision-resistance assumption on the node hash is replaced by a position-binding assumption; all results are proved in the paper. Companion paper: arXiv:2610.14849. Software: https://github.com/Oraclizer/statesync-gkr (doi:10.5281/zenodo.23280552)

Closest papers

Nearest neighbours by meaning across the whole index.

Constant-Coin Complete-Information Debates for $\mathsf{P}$ with Arbitrarily Small Strong Error

cs.CC cs.FL ·2026-09-21 ·M. Utkan Gezer
similarity 0.61
Abstract · 11 pages

We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and Yakaryılmaz showed that every language in $\mathsf{P}$ has such debates checkable with a constant number of random bits and arbitrarily small weak error. Their strong-error construction, which also counts nontermination as failure, did not permit arbitrary error reduction. We close this gap: for every $L\in\mathsf{P}$ and every $\varepsilon>0$, there is a constant-space verifier using a constant number of private coin tosses that has perfect completeness and strong error at most $\varepsilon$. The verifier simulates a polynomial-time alternating multihead finite automaton, privately spot-checking one of its input heads. The key observation is that, on a nonmember, the refuter may concede any round in which the prover first misreports a head reading. This ensures termination against every prover when the refuter follows the specified strategy, and permits strong-error reduction by repetition.

0.34

StateSync-GKR: Design and Evaluation of a Reusable Sparse GKR Engine

cs.CR cs.PF ·2026-10-10 ·Jinwook Kim
code/data similarity 0.60
Abstract · 167 pages; 12 main figures and a detailed experimental atlas appendix. v2 evaluates release 1.2.0 (new serving path; reorganized prover arit…

Authenticated state transitions need proof engines that conserve memory, avoid repeated setup, keep every result bound to its request under parallel execution and return complete proofs at service rates. We present StateSync-GKR, a reusable Rust sumcheck/GKR core with a sparse-Merkle frontend, and evaluate release 1.2.0 against release 1.1 measured on the same day on the same instance types, request corpus and latency budgets. Sparse layer reduction keeps additional requested allocation 3,242-fold and peak process memory about 89-fold below the engine's dense reference at width 4,096. Release 1.2 changes two parts of the software while proof bytes and verifier acceptance stay fixed: reorganized round arithmetic raises prepared proving throughput 2.4 to 2.7-fold on a 192-core bare-metal host, and a new serving path starts each job as soon as a worker is free, bounds queued work and buffered replies, and returns proofs in completion order bound to request identifiers. On a 192-core VM at 1,000 requests/s, 99th-percentile latency to verified acceptance falls from 440 to 34 ms. One connection carries 3,300 requests/s with every request inside one second, confirmed in three 60-second runs and a 30-minute run of 5.94 million requests without a latency or queue trend; at 3,400 requests/s reply traffic reaches the provider's documented 5-Gbit/s single-flow limit, and two connections passed 5,000 requests/s in 15-second screens. In single 15-second screens on 48 cores, the highest passing rate rose from 500 to 2,000/s. Offered 1.5 times its highest screened one-connection rate under a memory limit, with excess offers held back by the client, the worker held its resident memory near a fifth of that limit and left no submitted request unresolved. For an integrating service, fewer servers deliver the same proof rate with bounded tail latency, and existing verifiers accept the GKR proofs unchanged.

0.57

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

cs.CC ·2026-09-25 ·Sebastian Ben Daniel
similarity 0.59
Abstract

Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership comparator merely excludes one of the four membership vectors of a pair. We ask how much nonuniform advice turns such information into exact recognition. Our main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language: $2-mc \subseteq NP /(3n+5)\cap\mathrm{coNP}/(3n+5)$, with common fixed advice and certificates of at most $5n+12$ bits. The class is strictly larger; some 2-mc sets are not truth-table reducible to any P-selective set. The proof replaces the tournament king by an independent two-step cover of true signed literals, together with a short-forcing-or-exact-majority dichotomy, and it relativizes. Via an advice-preserving isolation transfer, a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives $2-mc \subseteq P/O(n)$. For selectors we determine tight orders of ordinary advice: $Θ(n)$ for errorless average-case computation and $Θ(n^2)$ for worst-case bounded-error computation, the latter independent of the interpreter's coin bound. One oracle realizes both orders on a single language and separates ordinary from coin-dependent advice. The quadratic and linear lower bounds hold for tournament-query procedures and relativized languages, not unconditionally for unrelativized P-selective sets.

0.38

Vigil: Accountable Liveness against Selective Silence

cs.DC cs.CR ·2026-09-16 ·Jiawei Cheng, Huiping Sun, Rui Zhou, Jinjue Zhou, Zhong Chen
theory similarity 0.59
Abstract · 20 pages, 8 figures

BFT accountability is well understood for safety violations, and recent work attributes global liveness violations; \emph{recipient-selective} silence remains unresolved. A selectively silent adversary withholds messages from some honest nodes while behaving correctly toward others. It can stall consensus yet evade every existing mechanism. We initiate a systematic study of accountability against selective silence. Negatively, a lone attacker silent toward at most $f$ honest nodes is indistinguishable from an honest node, yielding a universal lower bound $K_{\mathrm{SI}} \ge f{+}1$ on the \emph{silence identification threshold}; moreover, any feedback-free repair after a silence-induced violation costs $Θ(n^3)$. Positively, \textsc{Vigil}, a Tendermint variant, matches these bounds with attack-adaptive forwarding, via bitmap cross-attestation, core-based membership, and challenge--response auditing. It pays $O(n)$ authenticators per node when no selective silence occurs (plus $Θ(n^2)$ bitmap metadata bits per node), relays in proportion to the attack's width (sub-threshold silence can force up to $n^3/27$ relays per view, a cost we price exactly), and majority-accuses any node silent toward more than a tunable resilience $τ_A$ of honest peers ($K_{\mathrm{SI}} = τ_A{+}1$, optimal at $τ_A = f$). We also price the residual sub-threshold griefing surface exactly and extend identification to $x$-partial synchrony. Real-network experiments on a three-region WAN, together with a simulator held to exact equality with every closed form, confirm each threshold and cost: at $2\%$ loss, an $f{+}1$ accusation bar falsely accuses $91.2\%$ of honest nodes, while our majority bar accuses $0.002\%$.

0.19

Seal, Then Sample: Sampled Layerwise Proofs for Verifiable LLM Inference from GPT-2 to 70B

cs.CR cs.IR ·2026-09-23 ·Youki Lim, Sam Yong
code/data similarity 0.59
Abstract · 15 pages, 4 figures, 8 tables. Raw experiment logs and data tables: https://github.com/TrueOpen/slp-experiments

Verifying outsourced language-model inference requires a precisely identified computation and an audit whose cost a service can afford. We present Sampled Layerwise Proofs (SLP), a protocol and prototype that commits the boundary activations of every chunk of an inference trace, absorbs all commitments before any challenge is drawn, and then proves a verifier-selected subset of chunks together with the chunks that bind the prompt and the answer. Audit coverage becomes a runtime parameter over one set of commitments: on a TinyLlama-1.1B trace, proving seven of 47 chunks takes 22.0% of the time and 6.8% of the proof size of proving all 47. Because proof cost is dominated by weights rather than tokens, SLP packs concurrent requests into one trace under a block-diagonal causal mask and binds the prompt and answer of each request to its slot. Twelve packed requests are proved in 181.9 s, 6.5 times less than twelve separate proofs at the measured single-proof cost, and a simulated service proves twelve requests at 30.6 s per request with 0.6 s of verification each, rejecting a tampered answer. Disk-backed integer weights and streamed polynomial commitments let a single Llama-2-70B run complete on a 2 TB CPU host: 163 chunks sealed, five proved, a 4.34 MiB proof in 1,259 s, verified in 46.3 s without the weights. The proven object is a fixed-point canonical model; we trace a severe fidelity loss to the residual-stream bit width, repair it with an LLM-aware observer, and measure 84.8-84.9% argmax agreement with the floating-point reference over 334,705 WikiText-2 test positions. The limits are stated as precisely: guarantees cover proven chunks only, a fixed invalid chunk in the 70B setting is covered with probability 3/161, a manifest-only Fiat-Shamir schedule can be ground at 12.5 ms per attempt and needs an externally ordered challenge, and all measurements use a test reference string.

0.60

A BUD You Can Count On: Efficient, Verifiable Membership Proofs

cs.CR cs.DBcs.DC ·2026-09-10 ·Alejandro Ranchal-Pedrosa, Cody Littley, Ben Marsh
theorycode/data similarity 0.59
Abstract

A block typically changes only a small fraction of blockchain state, yet producing a state root makes validators update an authenticated tree spanning it all. We show how to support verifiable reads from the writes alone. We introduce Block Update Digests (BUDs), that commit to a block's writes and link each key touched in that block to its previous modification. An optional prior-value record lets one successor BUD authenticate the value between modifications, replacing the baseline's two BUD openings. SuperBUDs summarize those writes over longer intervals, letting a reader verify that a value remained unchanged without checking every intervening block. Thanks to BUDs and SuperBUDs, validators can just keep ordinary flat state while still serving proofs of current and historical values, including deletion. We prove soundness and completeness for reads at or after a key's first logged modification when the required proof data is available. In experiments with the baseline format, a 50x increase in state size raises the measured base-BUD cost by just 1.24x. In paired QMDB experiments, lowering its garbage-collection activation threshold raises process CPU time by 1.3-2.7x and device bytes written by 1.6-2.4x relative to its dormant configuration. BUD authentication requires no corresponding relocation of live entries. In the evaluated baseline, two-digest read-layer payloads stay below 800 bytes, and warm hash-path verification takes at most 146 μs at p99. Authenticated reads need not make validators maintain an authenticated tree over the entire state.

0.20

Generator-Independent Runtime Assurance under Partial Observation

cs.AI ·2026-09-05 ·Guangxi Wan, Yongbo Xie, Yuqi Liu, Qingwei Dong, Qingxin Li +2 more
theory similarity 0.59
Abstract

Proposal-based controllers---learned policies, language-model planners, and other black-box \emph{generators}---are increasingly deployed behind runtime verification gates. We ask when the closed-loop safety guarantee decouples from the generator. The prevailing per-candidate certification pattern does not compose: under retry or best-of-$k$ selection a per-candidate false-admission level $α$ can inflate to $1-(1-α)^{k}$. Our main theorem shows that \emph{simultaneous setwise soundness}---certifying a set of admissible proposals containing no nonviable action---is necessary and sufficient for generator-independent \emph{admission soundness}, the worst case over all generators of executing a nonviable proposal equalling the probability of setwise failure; together with a design-time certificate and a no-bypass rule it is sufficient for \emph{contract safety}, with violation bound $Γ+\sum_t\varepsilon_t+η$ invariant under arbitrary, even adversarial, replacement of the generator. A second theorem bounds every admission mechanism under partial observation: for a fixed probing and admission policy, if two state hypotheses whose information laws lie within total-variation distance $δ$ require different safe decisions, then $\abar+β+δ\ge1$. A sequential risk ledger makes the guarantee implementable with time-uniform confidence tubes, and shows that deterministic admission computations concentrate all statistical risk in state estimation. Simplex-style runtime assurance and control-barrier-function filtering are recovered as degenerate cases.

0.32

Verification with Transfer: Exact Information Frontiers and Their Price in Calls

cs.LG cs.CRcs.ITstat.ML ·2026-10-08 ·Hazar Yueksel
similarity 0.58
Abstract · 46 pages, of which 8 pages main text. The Lean 4 formalization is in the ancillary files

A verifier that accepts or rejects whole answers reveals little: under a flat prior over $k$-bit answers, zero error needs $2^k-1$ verifications. The usual remedy is to solve related source tasks, either all first, as a curriculum does, or interleaved with verification. We price this remedy in information and in calls. With an exact verifier, the least causal information that any interleaving of source calls and $n$ verifications needs to succeed with probability $s$ is a list rate-distortion function, attained by one observation before any verification. It lower-bounds the expected number of binary source calls, which designed sources meet within $1+\log_25$ calls for unique answers and within a logarithmic term in general, where no additive constant suffices. With an exact verifier and fixed sources, moving every call before the first verification preserves all hard caps on calls, although interleaving can save unboundedly many expected calls; under a noisy verifier, source-first protocols can lose unbounded factors in information and in error. For linear banks over $\mathbb{F}_2$, optimal accuracy has a closed form, and after a polynomial-time reduction the budget profile is computable in time $2^{O(h^2)}\operatorname{poly}(J,k+h)$ for $J$ sources and nuisance dimension $h$. In these banks, for zero error under a hard cap, the calls beyond the rounded-up information price are exactly those spent on nuisance. Every numbered result apart from two clauses about the planner is machine-checked in Lean 4, assuming two published results. Used as a ruler, the frontier shows a small transformer using all delivered bits at latent dimension $5$ and none at $11$ within fixed training budgets; in a test with predictions recorded before training, low XOR degree of the target bits did not suffice for their use.

0.22