Repository navigation
Open
Labels
trackingRoadmap or tracking issue for a body of workRoadmap or tracking issue for a body of work
Description
cslib-frontier (formerly complexitylib) is the frontier library built on CSLib. It keeps each module at its future CSLib path, so a module moves upstream by an import change. PolyFunFrontier/ is PolyFun's side of the same square: a nested Lake package that requires PolyFun by path and cslib-frontier by commit, on cslib-frontier's toolchain. import PolyFun, VCVio, ArkLib and CatCrypt never resolve it, and scripts/check-modules.sh keeps it that way.
Conventions (see PolyFunFrontier/README.md):
- modules sit at the path and namespace they would have in PolyFun;
- each records the frontier modules it waits on (
-- frontier: …); - one moves into
PolyFun/once those reach CSLib; - anything that needs no frontier module goes straight into PolyFun.
Work, in dependency order:
- L0: skeleton and query lower bounds (feat(frontier): PolyFunFrontier, with query lower bounds from cslib-frontier #424). Decision trees are free programs over
monomial ι Bool. A program computing parity ofnbits has no total roll bound belown, and the sensitivity bounds transfer too. - L1: cost. Frontier's pathwise
IsCostBoundedagainst PolyFun's charge fold andIsRollBound(one lemma each way). Frontier's presampling theorem for PolyFun-bounded programs. This joins Interaction cost: discrete bounds on interface use, consolidated across PolyFun, VCVio, ArkLib and CatCrypt #387's consolidation. - L2: machine backend. Frontier's multi-tape polynomial time as a
StepClassandQuantitativeStepClass(WIP: feat(complexitylib): nested complexitylib bridge on Lean v4.36.0-rc1 (do not merge) #339'sBackend/StepClassandBackend/Quantitative, ported). That instantiates the closure theorem at a real machine class. With frontier's P/poly, this is whatComplexityBackends/CslibSingleTapewould need before it is retired. The Turing-machine cost laws from the closed Backend-relative resource bounds roadmap #279 belong here: polynomial envelopes, since machine composition is not additive. feat(frontier): realize handled free programs on polynomial-time machines #511 (open) adds theStepClasshalf:StepClass.multiTapePolyTime, Frontier's polynomial-time functions on injective binary encodings. - L3: adequacy. The closed case (WIP: feat(complexitylib): nested complexitylib bridge on Lean v4.36.0-rc1 (do not merge) #339's
Adequacy/Iterate), then the open case through typed lenses to word oracles (IsOraclePPTOn.iterateWith_spec). The whole-program linking theorem from Backend-relative resource bounds roadmap #279 belongs here too: one linked machine whose run length meetstotalTime. feat(frontier): realize handled free programs on polynomial-time machines #511 (open, on feat(realizability): prove admissibility of scoped term interpretations #510) realizes certified handled programs (PPTProgram) as one fair-coin machine with one polynomial clock whose output law is the program's (MachineRealization.ofPPTProgram); feat(frontier): sync PolyFun and realize one-time pad and ElGamal security VCVio#1206 instantiates it for the one-time pad and ElGamal. - L4: open systems. Frontier's
UC.Machine,Emulatesand dummy-adversary theorem againstInteraction/Open. - Tooling. A promotion-status script that reads frontier's
-- upstream:markers at the pinned commit. A collision test once all of PolyFun builds on frontier's pins.
VCVio tracks its nested frontier package and its cryptographic complexity definitions in Verified-zkEVM/VCVio#906.
Metadata
Metadata
Assignees
Labels
trackingRoadmap or tracking issue for a body of workRoadmap or tracking issue for a body of work
Activity
dtumad commentedon Nov 12, 2026
For L4: an inventory of cslib-frontier's UC layer at the pinned
f1b10c2(CslibFrontier/Crypto/Protocols/UC/, six files), from an audit of the UC definitions on both sides.What it has:
Machine(Machine.lean:73): a state, an initial sampler, and a handler per activation, withcomp.Protocol,IdealFunctionalityandAdversary(Execution.lean:109-137).Environment := ℕ → List Bool → ProbOracleComp _ Bool, with a Boolean verdict (:142), andadvantageas the game advantage of the verdicts (:205).EmulatesWithin(Emulation.lean:83): ∀A ∃S ∀C ∀Z, with the simulator chosen before the corruption set and the environment.Emulates(:142).emulates_iff_emulatesDummy(DummyAdversary.lean:431), from the program equationexec_eq_exec_dummy(:237).Emulates.compose(Composition.lean:765).Its scope. Budgets count calls, not running time (
Machine.lean:31-34), and the emulation docstring says polynomial-time security "would additionally restrict them by machine realizability" (Emulation.lean:41-44). No file in the directory usesIsPPTOnorIsOraclePPTOn.How it differs from
Interaction/Open:SecurelyEmulates(SecureEmulation.lean:65) andUCSecure(Emulates.lean:416) take the simulator asPlug Δ → Plug Δ, which can rewrite the whole closing context. The cslib-frontier simulator is a machine on the adversary interface.openTheory'splugdrops boundary traffic (BoundaryAction.closed,OpenProcess.lean:227-230; UC follow-ups from the PolyFun UC audit (HasPlugFactorization, quotient semantics, graded observations, non-vacuous OTP) VCVio#633 item 3), so an L4 bridge needs a delivering composition on the PolyFun side.OpenTheoryhas no environment/adversary split. That split exists today only in VCVio'sStandard.ProtocolBoundaryandReactiveWorld.For a polynomial-time instance later, the closure lemmas are already in cslib-frontier:
IsOraclePPTOn.bind;preprocess, by polynomial-time maps only;Computability/Probabilistic/Oracle/Substitution.lean:148).The VCVio side and a design note are tracked in Verified-zkEVM/VCVio#633.