Research proof index

Predicate-targeted query bounds are preserved by lifting along a SubSpec when the target predicate agrees with the source predicate on lifted queries. No LawfulSubSpec assumption is needed: query bounds only inspect query indices, not the distribution of responses.

Every counting-oracle support point of the body oa lifts to a counting-oracle support point of replicate n oa whose query count is n times the body's. -/ private lemma countingOracle.support_simulate_replicate_const [DecidableEq ι] {oa : OracleComp spec α} {z : α × QueryCount ι} (hz : z ∈ support (countingOracle.simulate oa 0)) : ∀ n, ∃ ys, (ys, fun...

Key bound of the forking lemma: the probability that both runs succeed with fork point s is at least Pr[cf(main) = s]² - Pr[cf(main) = s] / |Range i|.

Trace noninterference is preserved by sequential composition (bind). The continuations may depend on both the result and the trace, but whenever the traces match, the continuations must themselves be trace noninterfering.

When running loggingOracle inside cachingOracle, every log entry ends up in the cache. We prove two properties simultaneously by induction: 1. Every log entry is in the final cache. 2. The initial cache is a subset of the final cache (monotonicity). The proof works by induction on oa. The pure case is trivial (empty log). For query t >>= mx: the...

Invariant-gated state-projection theorem for a simulated prefix followed by a stateful continuation.