All proofs
Project-declaredLean 4.32.0 · mathlib@81a5d257

Prob Event guarded Context Fork eq context Fork component

OracleComp.probEvent_guardedContextFork_eq_contextFork_component

Plain-language statement

A fixed guarded fork is the corresponding component of the dynamic semantic fork.

Exact Lean statement

theorem probEvent_guardedContextFork_eq_contextFork_component
    [IsProbabilitySpec spec]
    (main : OracleComp spec α) (qb : ι → ℕ) (i : ι)
    (cf : α → Option (Fin (qb i + 1))) (s : Fin (qb i + 1)) :
    Pr[fun result : Option (α × α) => result.isSome |
        guardedContextFork main qb i cf s] =
      Pr[fun result : Option (α × α) =>
          result.map (cf ∘ Prod.fst) = some (some s) |
        contextFork main qb i cf]

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem probEvent_guardedContextFork_eq_contextFork_component    [IsProbabilitySpec spec]    (main : OracleComp spec α) (qb : ι  ) (i : ι)    (cf : α  Option (Fin (qb i + 1))) (s : Fin (qb i + 1)) :    Pr[fun result : Option (α × α) => result.isSome |        guardedContextFork main qb i cf s] =      Pr[fun result : Option (α × α) =>          result.map (cf ∘ Prod.fst) = some (some s) |        contextFork main qb i cf] := by  letI : spec.toPFunctor.DecidableEq :=    (inferInstance : spec.DecidableEq).toDecidableEq  rw [contextFork_eq_contextForkByClassify]  unfold guardedContextFork contextForkByClassify  rw [PFunctor.FreeM.Cursor.filterMapLocateAndForkAt_eq_bind_complete,    PFunctor.FreeM.Cursor.filterMapLocateAndForkBy_eq_bind_complete,    probEvent_ofFreeM_bind_eq_tsum, probEvent_ofFreeM_bind_eq_tsum]  refine tsum_congr fun path => ?_  congr 1  rcases hcf : cf (PFunctor.FreeM.output main path) with _ | t  · rcases hloc : PFunctor.FreeM.Cursor.locateAt?        (P := spec.toPFunctor) i main path s with _ | located    · rw [probEvent_ofFreeM_pure, probEvent_ofFreeM_pure]      simp    · have hfirst :          cf (PFunctor.FreeM.output main located.completion.path) = none := by        simpa only [located.path_eq] using hcf      rw [probEvent_classifyForkView_isSome_eq_zero_of_first_ne          main qb i cf s located (by simp [hfirst]),        probEvent_ofFreeM_pure]      simp  · by_cases hts : t = s    · subst t      rcases hloc : PFunctor.FreeM.Cursor.locateAt?          (P := spec.toPFunctor) i main path s with _ | located      · simp only [hloc]        rw [probEvent_ofFreeM_pure, probEvent_ofFreeM_pure]        simp      · simp only [hloc]        rw [probEvent_ofFreeM_map, probEvent_ofFreeM_map]        congr 1        funext second        exact propext (classifyForkView_component_iff main qb i cf s {            occurrence := located.occurrence            first := located.completion            second := second }).symm    · trans (0 : 0∞)      · rcases hlocFixed : PFunctor.FreeM.Cursor.locateAt?            (P := spec.toPFunctor) i main path s with _ | locatedFixed        · rw [probEvent_ofFreeM_pure]          simp        · dsimp only          have hfirstNe :              cf (PFunctor.FreeM.output main locatedFixed.completion.path)  some s := by            simp only [locatedFixed.path_eq, hcf]            grind          rw [probEvent_classifyForkView_isSome_eq_zero_of_first_ne            main qb i cf s locatedFixed hfirstNe]      · dsimp only        rcases hlocDynamic : PFunctor.FreeM.Cursor.locateAt?            (P := spec.toPFunctor) i main path t with _ | locatedDynamic        · rw [probEvent_ofFreeM_pure]          simp        · rw [probEvent_classifyForkView_component_eq_zero_of_ne            main qb i cf t s locatedDynamic hts]
Project
VCVio
License
Apache-2.0
Commit
2ceb2d825ee3
Source
VCVio/CryptoFoundations/ReplayFork.lean:743-806

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.32.0

Expected Cost Nat eq sum tail probs of pathwise Cost At Most

AddWriterT.expectedCostNat_eq_sum_tail_probs_of_pathwiseCostAtMost

Plain-language statement

Finite tail-sum formula for natural-valued writer cost under a pathwise upper bound. If every execution path of oa incurs cost at most n, then the tail probabilities vanish above n, so the infinite tail sum truncates to Finset.range n.

program verificationseparation logiccryptography

Source project: VCVio

Person-level attribution pending.

View proof record
Project-declaredLean 4.32.0

IND CPA advantage to Real le sum step signed Advantage Real abs

AsymmEncAlg.IND_CPA_advantage_toReal_le_sum_step_signedAdvantageReal_abs

Plain-language statement

Planned generic one-time-to-many-time lift: bounded multi-query IND-CPA advantage is at most the sum of the extracted one-time signed advantages over the first q fresh LR queries.

program verificationseparation logiccryptography

Source project: VCVio

Person-level attribution pending.

View proof record