Theorem 7.4 (corrected: proximity endpoints and range) — perfect zero-knowledge PCPP from a testable, extendable sheaf code
OpenZKSheafPCP.Supplement.theorem_7_4coding-theoryp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1pcppsheaf-codeszero-knowledge
Let be a finite field and let be a -testable sheaf code for the local code , with recursive test tree and top test cover . Suppose there is one and one simulation cover such that, for every honest input , that cover is -extendable for . The simulation cover need not equal the test tree's top cover.
For every such that or , and such that , there are actual bounds supplied by corrected Theorem 6.7 for which Construction 7.3 is a black-box -local perfect zero-knowledge PCPP for with
The prover is fixed to the uniform global-extension prover of Construction 7.3. The virtual word uses the implicit input on and the proof only off .
Differences from the source:
- correction: every → every with or ; reason: when , and , the printed proximity is zero, so every codeword is zero-far under Definition 3.25 and perfect completeness contradicts soundness error
- correction: proximity parameter for every → additionally ; reason: Definition 3.25 requires a proximity parameter in , while the printed hypotheses permit
- reading: “there exists such that has a -extendable cover,” with and the cover free → one and one simulation cover work for every , without identifying that cover with the test tree's top cover; reason: a single PCPP simulator is fixed before the honest input, while the page does not say the simulation and test covers coincide
- encoding: is “a function defined in Theorem 6.7” → existential actual query/clock bounds satisfying corrected Theorem 6.7, together with the resulting operational local simulator; reason: this makes the dependency on Theorem 6.7 explicit and excludes the vacuous zero bounds admitted by the printed quantifiers
- encoding: Construction 7.3 as prose → a
PCPPFamilywhose sole explicit instance encodes and its test tree, with the uniform-extension prover exposed byIsPZKPCPPWithProverand the same parameters also asserted throughIsPZKPCPP; reason: this fixes the constructed prover and gives the verifier and simulator meaningful clocks - encoding: →
TestTree.queries; reason: the published test-tree definition computes exactly the maximum size of a leaf reached by the recursive tester - encoding: uniform prover distribution on →
uniformOnwith the zero word as a default only if that set is empty; reason: the uniform extendability hypothesis makes the set nonempty for every honest input, so the default changes no theorem instance
Preamble
import Mathlib import Definitions.Def_ZKSheafPCP_Supplement_Construction73Data import Definitions.Def_ZKSheafPCP_Supplement_IsLocallySimulatable import Definitions.Def_ZKSheafPCP_simLaw import Definitions.Def_ZKSheafPCP_TestTree
Formal statement
namespace ZKSheafPCP.Supplement
open Classical
/-- Theorem 7.4, p.32 (Zeilberger, O'Connor, Gur, Spooner,
*Zero-Knowledge PCPs of Quasilinear Size via Locally Simulatable Sheaf Codes*,
STOC 2027 submission, manuscript sha256 ac5e528f…): Construction 7.3 for a
`(c,d)`-testable sheaf code, using one simulation cover that is `κ`-extendable
for every honest input word, is a black-box `lS(κ)`-local perfect zero-knowledge PCPP.
Its verifier makes `max_{α∈S₁}|α|` queries, represented by `test.queries`; its
zero-knowledge query bound is `κ`, soundness error is `1-ϵ`, and proximity is
`c^d·ϵ`.
The first conjunct fixes the prover to the uniform-extension prover printed in
Construction 7.3. The second exposes the same parameters through the published
`IsPZKPCPP` interface. In `construction73VirtualWord`, the implicit input supplies
all coordinates in `P_σ`, so a conflicting purported proof cannot overwrite it.
**Formalization Note** The page leaves the codeword `c` free in “`F_{σ=c}` has a
`κ`-extendable cover”; this is read uniformly, with one simulation cover and `κ`
before every `w ∈ F_σ`, as required for one PCPP. The simulation cover need not
be the test tree's top cover; the page does not identify them. The additional condition
`ϵ = 0 ∨ 0 < c^d` corrects the degenerate printed endpoint: if `c = 0`, `d > 0`
and `ϵ > 0`, the proximity parameter is zero, so under Definition 3.25 every
codeword is zero-far; perfect completeness then contradicts soundness error
`1-ϵ`. The bound `c^d·ϵ ≤ 1` keeps the proximity parameter in Definition 3.25's
declared interval. No endpoint is removed in the parameter regime used by the paper. -/
theorem theorem_7_4 {F D : Type} [Field F] [Fintype F] [Fintype D]
(I : Construction73Data F D) (h𝓕 : I.sheaf.IsSheaf I.PP)
(hσ : I.sigma ∈ I.PP.P) (c d κ : ℕ)
(htree : IsTree I.sheaf I.PP c I.test)
(hdepth : I.test.HasDepth d) (hroot : I.test.root = I.sigma)
(htop : ∃ μ child, I.test = .node I.sigma I.cover μ child)
(simCover : Finset (Finset D))
(hcover : ∀ w ∈ I.sheaf.code I.sigma,
I.sheaf.IsRelKExtendableCover I.PP κ (I.PP.geq I.sigma) w simCover)
(ϵ : ℝ) (hϵ0 : 0 ≤ ϵ) (hϵ1 : ϵ ≤ 1)
(hdeg : ϵ = 0 ∨ 0 < (c : ℝ) ^ d)
(hprox : (c : ℝ) ^ d * ϵ ≤ 1) :
∃ lS tS : ℕ → ℕ,
(∀ k, lS k ≤ (k + 1) * simCover.sup (fun τ => (τ ∩ I.sigma).card)) ∧
PolyBddIn tS (fun k => (k + 1) * simCover.sup Finset.card) ∧
IsLocallySimulatable (fun w : I.sheaf.code I.sigma => (w : D → F))
(extensionEncoding I.PP I.sheaf I.sigma) simCover tS lS κ ∧
IsPZKPCPPWithProver (D := D) (construction73Family I) (construction73Prover I)
(fun _ => I.test.queries) (fun _ => 1 - ϵ) (fun _ => (c : ℝ) ^ d * ϵ)
(fun _ => κ) (fun _ => lS κ) ∧
IsPZKPCPP (construction73Family I) (fun _ => Fintype.card D)
(fun _ => I.test.queries) (fun _ => 1 - ϵ) (fun _ => (c : ℝ) ^ d * ϵ)
(fun _ => κ) (fun _ => lS κ) := by sorry
end ZKSheafPCP.Supplement
Source
Zeilberger, O'Connor, Gur, Spooner, Zero-Knowledge PCPs of Quasilinear Size via Locally Simulatable Sheaf Codes, STOC 2027 submission (manuscript sha256 ac5e528f…), Theorem 7.4, p.32