All proofs
Project-declaredLean 4.31.0 · mathlib@fabf563a7c95

Append tree Special Sound

Verifier.append_treeSpecialSound

Plain-language statement

Generic preservation of tree-special soundness under binary verifier append.

Exact Lean statement

theorem append_treeSpecialSound
    (V₁ : Verifier oSpec Stmt₁ Stmt₂ pSpec₁)
    (V₂ : Verifier oSpec Stmt₂ Stmt₃ pSpec₂)
    (S₁ : ChallengeTreeShape pSpec₁) (S₂ : ChallengeTreeShape pSpec₂)
    (verify₁ : Stmt₁ → pSpec₁.FullTranscript → Stmt₂)
    (hV₁ : ∀ stmt tr, V₁.verify stmt tr = pure (verify₁ stmt tr))
    (h₁ : V₁.treeSpecialSound init impl S₁ rel₁ rel₂)
    (h₂ : V₂.treeSpecialSound init impl S₂ rel₂ rel₃) :
      (V₁.append V₂).treeSpecialSound init impl
        (S₁.append S₂) rel₁ rel₃

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem append_treeSpecialSound    (V₁ : Verifier oSpec StmtStmt₂ pSpec₁)    (V₂ : Verifier oSpec StmtStmt₃ pSpec₂)    (S₁ : ChallengeTreeShape pSpec₁) (S₂ : ChallengeTreeShape pSpec₂)    (verify₁ : Stmt pSpec₁.FullTranscript  Stmt₂)    (hV₁ :  stmt tr, V₁.verify stmt tr = pure (verify₁ stmt tr))    (h₁ : V₁.treeSpecialSound init impl S₁ rel₁ rel₂)    (h₂ : V₂.treeSpecialSound init impl S₂ rel₂ rel₃) :      (V₁.append V₂).treeSpecialSound init impl        (S₁.append S₂) rel₁ rel₃ := by  rcases h₁ with E₁, hE₁  rcases h₂ with E₂, hE₂  refine fun stmt tree => E₁ stmt tree.appendSplit.fst, ?_  intro stmt tree hStructured hAccept  apply hE₁ stmt tree.appendSplit.fst  · exact ChallengeTree.appendSplit_fst_isStructured tree hStructured  · intro tr₁ htr₁    obtain path, rfl :=      ChallengeTree.LeafPath.exists_of_mem_fullTranscripts (T := tree.appendSplit.fst) htr₁    have hSuffixStructured :        (tree.appendSplit.sndAt path).IsStructured S₂ :=      ChallengeTree.appendSplit_sndAt_isStructured tree hStructured path    have hSuffixAccept :        (tree.appendSplit.sndAt path).IsAccepting init impl V₂          (verify₁ stmt path.fullTranscript) rel₃.language := by      intro tr₂ htr₂      have hmem :          path.fullTranscript ++ₜ tr₂  tree.fullTranscripts :=        ChallengeTree.appendSplit_fullTranscripts_append_of_mem tree path htr₂      have hfull := hAccept (path.fullTranscript ++ₜ tr₂) hmem      simpa [append_run_pure_left V₁ V₂ verify₁ hV₁          stmt path.fullTranscript tr₂] using hfull    have hRel₂ :        (verify₁ stmt path.fullTranscript,          E₂ (verify₁ stmt path.fullTranscript) (tree.appendSplit.sndAt path))  rel₂ :=      hE₂ (verify₁ stmt path.fullTranscript) (tree.appendSplit.sndAt path)        hSuffixStructured hSuffixAccept    have hLang₂ : verify₁ stmt path.fullTranscript  rel₂.language :=      (Set.mem_language_iff rel₂ (verify₁ stmt path.fullTranscript)).2        E₂ (verify₁ stmt path.fullTranscript) (tree.appendSplit.sndAt path), hRel₂    exact pure_accepting_of_mem init impl V₁ stmt path.fullTranscript rel₂.language      (verify₁ stmt path.fullTranscript) (hV₁ stmt path.fullTranscript) hLang₂
Project
ArkLib
License
Apache-2.0
Commit
fad5cbf80877
Source
ArkLib/OracleReduction/Security/CoordinateWiseSpecialSoundness/Composition.lean:366-407

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.31.0

Affine gaps lifted to interleaved codes

affine_gaps_lifted_to_interleaved_codes

Project documentation

This lemma proves the final algebraic step in the DG25 Theorem 3.1 proof. It shows that if R > e + 1, then e * (R / (R - 1)) < e + 1. The intuition is that the fraction R / (R - 1) is always greater than 1, but as R gets larger, it gets closer to 1. The hypothesis R > e + 1 provides a strong enough bound to ensure the product e * (fraction) do...

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose coeff

ArkLib.Lattices.Ajtai.gadgetDecompose_coeff

Plain-language statement

The k-th coefficient (k < deg φ) of a gadget-decomposition block is exactly the corresponding digit of the corresponding input coefficient.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose lawful

ArkLib.Lattices.Ajtai.gadgetDecompose_lawful

Plain-language statement

The base-b gadget decomposition is a lawful gadget decomposition.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record