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
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₃ := 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
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...
Source project: ArkLib
Person-level attribution pending.
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.
Source project: ArkLib
Person-level attribution pending.
Gadget Decompose lawful
ArkLib.Lattices.Ajtai.gadgetDecompose_lawful
Plain-language statement
The base-b gadget decomposition is a lawful gadget decomposition.
Source project: ArkLib
Person-level attribution pending.