Repository navigation
Description
This tracks one generic API for interaction cost: costs read structurally off a program's use of an interface, such as how many calls it makes, of which kinds, and at what price. Several projects built special cases of this independently, and the goal is one PolyFun API that they can all depend on. The core of the API (phase 1) merged on 7–8 November. This issue now tracks the roadmap for generalizing the rest, organized by what each reading of a program's calls keeps and forgets.
Scope
In scope. Discrete costs of interface use. A charge prices each call of an interface. Pure Lean code between calls is free, so a cost is a function of the program's interaction tree, which is ordinary data. Nothing here needs the cost of a Lean function, or any intensional distinction between extensionally equal functions. The notion applies to any program that interacts through an interface:
- oracle queries, group operations and ticks;
- handler reductions;
- protocol rounds.
Out of scope, tracked elsewhere:
- backend-relative bounds: composition laws for quantitative realizations, reactive conservation and a reference cost language (Composition laws for quantitative realizations #505, Reactive conservation under composition #506, A reference cost language in core PolyFun #507, from the closed Backend-relative resource bounds roadmap #279);
- polynomial time, PPT and adequacy (PolyFunFrontier: the cslib-frontier side of PolyFun #425, Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy) VCVio#906);
- the lens tensor and the multiset and graded exponentials, which the summaries below build on (merged in feat(pfunctor): monoidal closed structure of the tensor of lenses #429–feat(pfunctor): the weighted exponential on lenses #431, feat(pfunctor): the graded exponential and count matrices on lenses #448 and feat(pfunctor): Seely isomorphisms and the commutative comonoid for bangW #449);
- measure semantics, which the expected charge needs (Probability layer: measure interpretations in PolyFun, security in VCVio #400). feat(probability): expectations and expected charges of free programs through the fold #445, merged, adds the expected charge itself.
Expectations over randomness and security statements stay in VCVio.
The notion
A charge c : P.A → ω prices each call position of an interface P in an ordered additive monoid ω, and is paid when the call is made. ω ranges over ℕ, K → ℕ, ℕ∞, ℝ≥0∞, ℤ, ExecutionCost, and so on. As a polynomial map, a charge is the lens Lens.toConst c : P ⇒ C ω. Pulling it back along a lens is composition (Lens.toConst_comp), and the charge on a sum is the copairing (Lens.sumPair_toConst).
Every reading is a fold (wpFold) of a per-call rule over the program. Sequencing is therefore exact, and transfer through a handler is a pullback (wpFold_liftM).
| Reading | Per-call rule |
|---|---|
budget IsChargeBound x c B s |
allow the call if s + c a ≤ B, and continue from s + c a |
worst-case cost c x |
c a + ⨆ b, k b |
CallsIn x S |
the call lies in S |
IsRollBound |
canRoll a b, and continue from cost a b |
expected charge OpSpec.expectedCharge ν c (#445) |
c a + 𝔼[k] under the answer measure ν a |
Completed paths. Path.charge c x p bounds completed paths only. It is needed for signed weights, where a prefix can overspend while every completed run stays within budget.
Relation to IsRollBound. IsChargeBound is the additive special case of the general budget automaton IsRollBound (isChargeBound_iff_isRollBound). Roll bounds alone express non-additive protocols such as "never call b after a". What charges add are laws without side conditions: additive bind, transport along →+o, handler transfer with per-call certificates, a value form, automation and an exact Std.WP reading.
Other models. Resumption, DynComputation, ITree and IFreeM inherit the notion through truncation, unrolling and Σ-erasure. In an ITree, silent steps are charged tau.
Special cases this subsumes
| Where | Special case | Generic form |
|---|---|---|
| VCVio | IsTotalQueryBound, IsQueryBoundP, AllQueriesSatisfy, IsPerIndexQueryBound |
unit, indicator and Pi.single charges. Derived in Verified-zkEVM/VCVio#1060 (isQueryBoundP_iff_isChargeBound and siblings); the general IsQueryBound stays a roll bound |
| Verified-zkEVM/VCVio#942, Verified-zkEVM/VCVio#930 | weighted and per-kind budgets; CostCertificate.simulateQ_run; table growth |
IsChargeBound, .map, .run_liftM; resource growth le_of_canReturn_run_liftM |
| Verified-zkEVM/VCVio#1016 | mapLens, transport of query bounds |
IsChargeBound.mapLens, FreeM.liftM_mapLens, general IsRollBound.mapLens |
| Verified-zkEVM/VCVio#1013 | weighted-cost transfer through stateless handlers | Path.charge_liftM_le_of_forall. Derived in Verified-zkEVM/VCVio#1062 |
| Verified-zkEVM/VCVio#1018 | DeterminedCost; MeasuredProgram / BudgetedProgram |
run_liftM_withChargeW_id, derived in Verified-zkEVM/VCVio#1062; the same structures over PFunctor (Free/Cost/Measured.lean), not yet derived |
| VCVio | withAddCost, addCostOracle, enforceOracle; expectedSimulatedQueryCount |
Handler.withChargeW, withBudgetOr, derived in Verified-zkEVM/VCVio#1062; the expected charge OpSpec.expectedCharge (#445), not yet derived |
| ArkLib | arithmetic profiles, liftComp transport, ℝ≥0∞ keyError round costs, fresh-key charges, node-indexed stage budgets |
vector charges; mapLens; .map into ℝ≥0∞; TraceList.freshCharge; Path.chargeDec |
| CatCrypt | Container.cost, TickSig, query profiles, TimedM, useBound_liftM |
FreeM.cost; a tick as a call to linear ω; prod/pi budgets; a ≤-graded carrier; Certified.ofDemand |
| (new) | caching makes at most as many target calls as there are distinct keys | amortized transfer Path.exists_run_liftM_amortized |
Not covered, for reasons unrelated to cost:
- VCVio's quantum query mass, used in the √-hybrid bound. It is amplitude-weighted and state-dependent, so it is not a function of the tree. Quantum query counts are covered: VCVio's
QuantumComp.IsQueryBoundAt,IsQueryBound,IsTotalQueryBoundandIsCostBoundare instances ofIFreeM.IsChargeBound. CatCrypt's QROM adversaries (QAdv m n w q) fix the query count in their type; - direct-style
HasQueryprograms, which have no syntax to read.
Phase 1: merged
- feat(pfunctor): interface charges and structural charge bounds on free programs #388 Interface charges and charge bounds on free programs, with restricted answers (
IsChargeBoundUnder,PFunctor.restrict). - feat(pfunctor): worst-case cost, loops, support-restricted sequencing and
cost_bound#389 Worst-case cost, loops, support-restricted sequencing andcost_bound. - feat(pfunctor): charges of completed paths #390 Charges of completed paths and the exact substitution law
exists_path_liftM_iff. - feat(pfunctor): charge certificates, instrumented and gated handlers, handler transfer #391 Charge certificates, instrumented and gated handlers, stateful and amortized transfer, pausing runs (
FreeM.runUntil). - feat: charge bounds for resumptions, dynamical computations, interaction trees and indexed programs #392 Charge bounds for resumptions, dynamical computations, interaction trees and indexed programs.
- feat(pfunctor): measured and budgeted programs #393 Measured and budgeted programs.
- feat(free): core
vcgenfor charge bounds #394 Corevcgenfor charge bounds. - feat(pfunctor): certified handlers, costed reductions and stateful certificates #396 Certified handlers, costed reductions, stateful certificates along
link. - feat(pfunctor): vector charges, prices and demand maps over certified handlers #415 Vector charges, prices and demand maps, by Bas Spitters (recreated from feat(pfunctor): vector charges, prices and demand maps over certified handlers #410).
- docs(cost): why AddSupDistrib excludes the empty set; pin cost_bound on false budgets #416 Why
AddSupDistribexcludes the empty set; a goalcost_boundcannot close. - VCVio adoption: the pin is at the merged stack (chore(deps): bump PolyFun to the lens two-party API VCVio#1057), and refactor(query-bound): derive query-bound special cases from PolyFun charge bounds VCVio#1060 and Derive cost transfer, determined cost and enforcement from PolyFun charge handlers VCVio#1062 derive the rows marked above.
Roadmap
Every reading of a program's calls is a reading of its completed paths. The roadmap orders the work by what each reading keeps: the whole trace, a meter on it, a bound on the meter, or a summary that forgets order. Items name the existing API they build on and the consumers waiting for them.
1. Paths and traces
In place: Path, TraceList, splitBind/joinBind, Path.ofHandler_bind (#423), and the exact substitution law exists_path_liftM_iff: a completed path through x.liftM h is a path through x with a path through each call's implementation.
- Stateful threading.
Path.Threadswithexists_run_liftM_iff, the stateful counterpart of the substitution law (CatCrypt'smem_profile_simulate_iff).
2. Meters: every instrumentation reads the trace
A meter records something at each call. An additive meter is a monoid hom out of the free monoid of calls: withChargeW is withTraceBefore read through a hom (withChargeW_eq_withTraceBefore). Fresh charges (TraceList.freshCharge) and watermarks (#397) are functions of the trace that are not homs. The week's VCVio cost PRs re-prove the laws of this layer by hand, which is why it comes first.
- Instrumentation commutes with interpretation. For a monad morphism
F, interpreting awithChargeW- orwithTraceBefore-instrumented program and then applyingFequals instrumentingF ∘ h. For a monoid homφ, mapping the record byφequals charging byφ ∘ c. Both are instances ofliftM_naturalandliftM_comp, stated once. Consumers: the fusion lemmas of proof(rom): retain query charges during settled cache replay VCVio#1036 (simulateQ_withAddCost_runAdd_fusion), proof(merkle): account for settled sibling query charges VCVio#1038, proof(signature): realize counted experiments through query programs VCVio#1051 (mapCost_costed), proof(oraclecomp): relate writer costs to passive state VCVio#1067 and feat(cost): compose measured programs with declared budgets VCVio#1018 (simulateQ_withAddCost_comp), and the log transport of Resumed-run success bounds, logging after substitution, and a bind bound with an exceptional event VCVio#1064 (withQueryLog_simulateQ), feat(EvalDist): statistical distance and lemmas for oracle query navigation VCVio#1055 and proof(oraclecomp): retain coherent logged service histories VCVio#1041. A non-commutative monoid in the tests keeps the order of charges honest. Merged feat(pfunctor): move charges along monad morphisms and between meters #450 gives thewithChargeWand running-total forms:Handler.mapHom_liftM_withChargeW,Handler.run_liftM_mapTarget_withChargeandHandler.mapOutputHom_liftM_withChargeW. - One meter, several presentations.
withChargeW(a writer),withCharge(aStateTcounter), a counter component added to a stateful handler's own state, and the remaining-budget formB - spentunder ordered subtraction. Consumers: proof(oraclecomp): relate writer costs to passive state VCVio#1067 (run_withAddCost_eq_extendState), proof(signature): relate counted costs to passive query meters VCVio#1054, which re-proves an instance by induction, and Derive cost transfer, determined cost and enforcement from PolyFun charge handlers VCVio#1062'senforceOracle.run_simulateQ_sub_eq. Merged feat(pfunctor): move charges along monad morphisms and between meters #450 relates the first three (Handler.run_liftM_withCharge,Handler.Stateful.run_extend_eq_withChargeW); the remaining-budget form is still open. - Where the meter sits relative to a cache. A meter outside a caching handler charges every client call, so transfer is exact and cache hits pay. A meter inside it charges only the calls that reach the callee: for a memoizing cache, the client trace's
freshCharge. This is the exact amortized law for caching handlers, which Bas offered to state over the stateful handlers (CatCrypt'sOracleCache). The related settled-run result merged in feat(pfunctor): settled runs of partial handlers #451. A run returningsomeunder a partial deterministic handler keeps its result under extension and its selected path determines its charge. The remaining cache law must account for which calls actually reach the callee. Bas Spitters's feat(pfunctor): a caching handler and where the meter sits relative to it #499 (open) states both placements for a memoizing cache: forwarded calls are charged the client trace's fresh charge outside the initial cache (exists_path_run), their number is the growth of the cache (length_run_add_card), and a meter outside the cache charges the full path (exists_path_run_withCharge). Settled charge - Writer erasure for log-style writers (
[EmptyCollection ω] [Append ω]), so that VCVio'ssimulateQ_run_writerT_of_stepcan port.
3. Bounds and transfer
In place: upper-bound transfer for every reading, through free, stateful, amortized and certified handlers and costed reductions.
- Exact certificates. A per-call equation, where the target meter of
h arecords exactly the source charge ofa, gives exact transfer for any monoid with the meter laws above. This includes the expansion of one source call into several target calls. Consumer: the hypothesiscompatibleof proof(signature): realize counted experiments through query programs VCVio#1051'scosted_simulateQ. - Relational certificates. A refinement square at the
OpSpeclevel, under which one handler simulates another with a relation on costs. Relational and expected readings would then transfer through the same square. Consumer: proof(oracle): lift stateful support refinements through clients VCVio#1046 (simulateQ_run_support_refinement, with relations such ascheapCost ≤ fullCost). - Charges before an abort. With
ExceptorOptionoutside the meter, the charges of the prefix before an abort survive. Relate this torunUntilandIsChargeBound.runUntil_paused, besideFree/Except.lean. Consumer: feat(oraclecomp): reify exceptional replies as total programs VCVio#1025. -
runUntilandliftM. RelateFreeM.runUntiltoliftMthrough a handler intoStateT σ (OptionT (FreeM Q)). - A counting kernel (from Backend-relative resource bounds roadmap #279) beside
Path.ofHandler_eq_of_agree_positions: aq-call program run against oracles that differ on at mostksecrets per position changes its output on at mostq·ksecrets. This gives generic DLog, DDH and point-search witnesses (Tracking: generic and algebraic group models (GGM and AGM) VCVio#846).
4. Summaries: what an accounting forgets
A summary of a handler is the image of its trace under a quotient:
| Keeps | Forgets | Algebra | Composition through a handler |
|---|---|---|---|
| the trace | nothing | lists (the free monoid) | the substitution law |
| how often each resource is used | order, adaptivity, answers | multisets, count vectors (ι →₀ ℕ) |
multiset bind: the Diller–Nahm category (#460; #497 packages it) |
| which resources are used | also multiplicity | finite sets | union: the original Diller–Nahm variant |
| a price | also the kinds | ω |
the exchange →+o |
The finite-set row is the idempotent case, where using a resource twice costs once. A cache in front of the callee charges in this way. Historically, Gödel's Dialectica interpretation lets the opponent play one move, the Diller–Nahm variant a finite set, and modified realizability every move (Ferreira and Oliva, LMCS 7(1:9), 2011, §1). The multiset version in #430 is Moss and von Glehn's (LICS 2018, §8). #431's weighted exponential bangW S, over a commutative semiring S, would give these accountings uniformly: ℕ counts uses, ℕ∞ bounds them, and ℝ≥0 gives expected demand (with #400). Whether Bool gives the finite-set row, and a tropical semiring peak use, is to check.
Variance. PolyFun's handlers read a polynomial as requests and responses (the effects reading). Diller–Nahm reads it as outputs and inputs (the systems reading of DynSystem and Dialectica categories): data flows forward, and each demand at the output becomes a bag of demands at the input. So a handler implementing P by Q gives a demand morphism from Q's resources to P's. The summary map is contravariant: handler composition becomes Diller–Nahm composition in the opposite order.
- Category laws for
Certified.Certified.id,compandtransferexist;id_comp,comp_id,comp_assocand aCategoryinstance do not. They should follow fromHandler.id_comp,comp_idandcomp_assocand theOrderAddMonoidHomlaws, since the certificate is a proof. - The summary functor. Bas Spitters’s feat(pfunctor): certified handlers with natural demands as count-matrix lenses #460 proves that finite natural demand matrices compose by multiplication and that the associated certified exchanges agree under composition. This gives the composition calculation on one-shape objects. The remaining task is to package the certified-handler category and the contravariant functor at the resource types where the comparison applies; feat(pfunctor): summary functor of certified handlers into a Diller-Nahm category #497 (open) does this. General certified exchanges can have fractional or infinite entries. Demand matrices · Certified composition
- The accountings as instances of
bangW S. The weighted exponential and Seely comparisons merged in feat(pfunctor): the weighted exponential on lenses #431 and feat(pfunctor): Seely isomorphisms and the commutative comonoid for bangW #449.ℕ,ℕ∞andℝ≥0come first;Booland tropical are to check.
Limits. A summary keeps counts and forgets order, adaptivity and answers. A worst case taken per kind also loses correlations, such as a cap of q calls in total that a per-kind bound cannot express; completed-path charges keep those. Multisets do not share: each use re-runs its producer, so caching needs the finite-set row or the meter-placement law above.
5. Bridges
- Observers (feat(pfunctor): answer-dependent charges and watermarks #397, closed; branch
feat/cost-observerskept): answer-dependent charges and the watermark semigroup (signed prices, peak space). It waits for a consumer: answer sizes in VCVio'sOracleClosure, or peak space. - Machines and realizations (feat: bridges from interface charges to machines and backend cost #398, closed; branch
feat/cost-bridgeskept). Its realization layer comes back first, as a fresh PR in core PolyFun:ExecutionTrace.charge,RunsWithin.isChargeBoundand the bridgeRunsWithinUnder.executionCost_add_charge_le, with feat(pfunctor): a caching handler and where the meter sits relative to it #499 and FRI's extractor (Tracking: extractor resource accounting across ArkLib, VCVio, PolyFun and CompPoly ArkLib#1528) as consumers. Oracle realizers priced by their proved cost, with an overhead in path length and encoded sizes, go on top, then block simulation for hidden machine steps. It gives the concrete execution cost of a run from its charges, relative to a backend. feat(frontier): realize handled free programs on polynomial-time machines #511 (open) is the asymptotic counterpart on the frontier side: it realizes certified handled programs as one polynomially clocked machine, without going through charges. Machine classes and adequacy are PolyFunFrontier: the cslib-frontier side of PolyFun #425 (L2, L3), andRefinesViawaits for a machine-level user. The machine-level composition laws are in Composition laws for quantitative realizations #505. - The expected charge, Merged feat(probability): expectations and expected charges of free programs through the fold #445.
OpSpec.expectedCharge ν creads a call ataasc afollowed by the expected value of its continuation, and its fold is the expected charge. Under subprobability answers it is at most the worst-casecostWith(wpFold_expectedCharge_le_costWith). Under probability answers over discrete answer types it is the integral of the charge of the completed path (lintegral_measureFold_withPathCharge), and the expected query count is the unit charge (expectedQueryCount_eq_wpFold). Transfer through a free handler is an instance ofwpFold_liftM_le(wpFold_expectedCharge_liftM_le, exact formwpFold_expectedCharge_liftM). Consumers:countedandexpectedCallsin feat(Rewinding): frozen reruns with reset policies VCVio#934. - Expected-charge transfer through finite stateful handlers. Merged feat(pfunctor): transfer expected cost through stateful handlers #486 prices a request in its incoming private state. Its continuation sees the joint law of the answer and successor state.
FreeM.wpFold_expectedCharge_runtransfers exact per-call prices to any finite client.FreeM.wpFold_expectedCharge_run_leaccepts an upper bound for each request and incoming state. Transfer theorems - In review. feat(pfunctor): automate finite expected-cost calculations #498 automates finite expected-cost calculations and checks a core
vcgenbound. feat(pfunctor): extend expected charge to unbounded resumptions #487 extends the charge to unbounded resumptions by taking suprema over finite prefixes. Its dependent PR feat(pfunctor): bound the expected cost of stateful retries #500 bounds a stateful retrying client's expected cost byC / pwhen the per-attempt price is at mostCand the conditional success probability is at leastp > 0in every reachable state. Under lossless trials it also proves eventual success with probability one. - Adaptive collection. A fork prototype computes the expected number of draws for
nuniform coupon types asntimes thenth harmonic number. A separate theorem bounds the chance of still being unfinished at a global cutoff when each reached trial has a lower bound on conditional success. Coupon collector · Cutoff bound - Parallel composition: a cost law under
⊗(feat(pfunctor): monoidal closed structure of the tensor of lenses #429's monoidal closed structure), through a lax-interchange mixin. The first client is CatCrypt's costed two-hole UC law.
6. Contracts: what a cost claim states
From Alexander Hicks's review (comment of 2026-11-17) and Verified-zkEVM/ArkLib#1528. The generic predicates stay for the laws; these are the forms a contract states.
- A contract-grade cost predicate beside
CostAtMost: canonically ordered counts with the standard addition and order, finitely many kinds or→₀budgets, and finite total cost under natural-number counting, without requiring finite oracle domains.PolyFunTest/PFunctor/Charge/Basic.leanpins the failure modes it rules out. - One
MeasuredProgram. VCVio's becomes PolyFun's, landing together with ArkLib's repin. - Sized contracts (
CostWithin,PolyCostand the restricted forms), with cslib'sPolynomiallyBoundedas the growth predicate. They bound declared operations and are never namedPPT; strict PPT is Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy) VCVio#906.
Consumers waiting
- VCVio. Alexander Hicks's cost PRs map onto layers 2 and 3. Merged with hand proofs, to be derived from PolyFun's API, which VCVio's PolyFun pin now includes: proof(rom): retain query charges during settled cache replay VCVio#1036, proof(merkle): account for settled sibling query charges VCVio#1038 and proof(oraclecomp): relate writer costs to passive state VCVio#1067 (meters), proof(oracle): lift stateful support refinements through clients VCVio#1046 (exact transfer), proof(oraclecomp): retain coherent logged service histories VCVio#1041 (
Path.splitBind), and the GroupModel cost certificates of feat(GroupModel): count group operations and bound table growth VCVio#930 and feat(GroupModel): handle virtualization VCVio#938. Still drafts: proof(signature): realize counted experiments through query programs VCVio#1051 and proof(signature): relate counted costs to passive query meters VCVio#1054 (meters and relational transfer) and feat(oraclecomp): reify exceptional replies as total programs VCVio#1025 (aborts); open: feat(GroupModel): cost certificates for handler reductions VCVio#942 (GroupModel certificates). New drafts: proof(random-oracle): preserve adaptive replies across paired cache reads VCVio#1200 to proof(oracle): charge adaptive Bernoulli trials at their actual count VCVio#1203 and feat(oracle): account for cached searches and graph collisions VCVio#1205 (adaptive and cached random-oracle accounting for leanXMSS). Also, deriveMeasuredProgram/BudgetedProgramfrom PolyFun's (§6). These are suggestions for the PRs' authors. - CatCrypt. Its time bounds as
IsChargeBound(stage 2 of the division agreed above), the caching law, and the Diller–Nahm modules (feat(pfunctor): summary functor of certified handlers into a Diller-Nahm category #497). - ArkLib. Codec transport for fresh-key charges, and measured programs along protocol telescopes (feat(security): compose measured extraction along typed paths ArkLib#1448's
programAlongis tested). FRI's extractor is the first consumer of the realization bridge in §5 (Tracking: extractor resource accounting across ArkLib, VCVio, PolyFun and CompPoly ArkLib#1528).
Smaller follow-ups
- Generalize the answer universe of handler targets (
WithinCharge.comp,Path.exists_run_liftM_amortized). - A lawful graded-monad instance for
Budgeted(LawfulGradedMonadexists; onlyBudgeted.instGradedMonadis provided). - Module canaries for the
Underunfoldings; the event canaries come with feat(pfunctor): answer-dependent charges and watermarks #397. - A note in
docs/guides/cost.mdthat scored products (qubits × T-count, bytes × cycles) are monotone images of componentwise bounds. - Lemma-level instance arguments weakened;
Path.charge_const_zero; the universe note in the guide.
Upstream
- cslib:
no_indexonFreeM.liftM_lift_bindandliftM_lift, which do not fire on concreteabbrevinterfaces. PolyFun keeps the primed workaroundsliftM_lift'andliftM_lift_bind'. - cslib:
AddSupDistrib, staged inToCslib/Order/AddSupDistrib.leanwithℕ∞,ℝ≥0∞andPiinstances. Mathlib has onlyENat.add_iSupandENNReal.add_iSup. - The concrete tail-call regression from v4.35 and v4.36-rc1 is covered on stable v4.36 by chore(deps): port traces and program logic to Lean 4.36 #477. Both the scoped call rule and the budget reading solve a branch whose final request returns
Bool. Budget regression · Scoped rule
Open questions
IFreeM.IsChargeBoundis ℕ-valued and subtractive. Should it be generalized (a breaking change), or kept with the erasure bridgeisChargeBound_iff_toSigmaFreeM?- Bridges for
chargedFoldlMandReactiveNetwork.Charge(the potential method), and for stutter budgets in simulations. DynComputation.costis the supremum of the costs of its truncations. Does it satisfy a step equation, as a least fixed point of the per-step rule (costToGo, from Backend-relative resource bounds roadmap #279)?- Rewinding. An extractor over a prover interface costs
c₂ + c₁·n₂throughCostedReduction, and feat(pfunctor): the graded exponential and count matrices on lenses #448's count matrices give the same law. Which form should the forking lemmas state? For fixed answer tables, feat(Rewinding): charge reruns by their query cost VCVio#1166 already bounds the expected rerun charge by a per-rerun price times the expected count, including nonzero initial counters. A checked integration on VCViof1e63c780with PolyFun77731620derives the same statement by projecting both counters from one stateful simulation. Its final proof takes ten lines and needs nine preceding helper declarations and four local instances. The twelve-line induction remains the shorter implementation. The rewinding module, the alternative derivation, and the adaptive-world counterexample passed targeted builds and strict Lean checks. Maintained theorem · Reproduction - Codec transport for fresh-key charges (ArkLib).
cc @spitters @alexanderlhicks @quangvdao: this consolidates the cost work from your PRs; comments on the roadmap are welcome.
Activity
alexanderlhicks commentedon Nov 4, 2026
I think unifying as much as possible would be great. I think it's also important to think ahead about how to relate any resource modelling and bounds at different layers, from the high level protocol specifications to binaries and runtime.
edit: added a comment below based on my sessions with the agents in the last few days.
spitters commentedon Nov 4, 2026
CatCrypt-core already has most of this at ω = ℕ / ℕ∞, on top of
OpSpec.charge:cost, additive bind, lens pullback: CodeCostIsRollBound, sum charges,CallsIn(MayOnlyCall): OracleQueryVec, OracleSimulationprofile,charge_bind,Within): OracleProfileisQueryBoundBy_simulate,isQueryBoundBy_substquery_boundtactic: QueryFoldTimedM: XTimedMonadspTreeQueryCost=costfor query-bounded trees (queryCost_eq_cost, CodeCost)QAdv m n w q, SemiClassicalOracle), so the bounds there need no query-mass notion.We would move these onto the stack; #380 is the first part.
alexanderlhicks commentedon Nov 4, 2026
Some feedback from the ArkLib side, where we have just been through several rounds of adversarial review of extractor resource accounting (ArkLib #1359/#1364/#1370/#1397, now #1448 and #1453). The scope split looks right to me, and reading costs structurally off the interaction tree is the right base layer. Most of what follows is about how this layer connects to the layers above and below it. A bound is only useful if a reader can carry it from a protocol specification down to code and a machine.
1. Name what each certificate leaves uncharged, and where the next layer bounds it
"Pure Lean code between calls is free" is a sound definition of interaction cost. It is not a bound on work, and nothing in the types signals the difference. In #393's
MeasuredProgram, theview, theanswerfunction and all code between calls are uncharged. SoofFun fgivesRealizes f ∧ CostAtMost 0for everyf, and any statement of the form∃ M, M.Realizes f ∧ M.CostAtMost Bholds trivially. We hit exactly this in ArkLib: knowledge soundness with an existentially quantified extractor and no cost is equivalent to plain soundness. The fix there was to name the measured program in the statement, never to quantify over it. I'd suggest:Roughly, the layers I have in mind are:
Kind → ℕprofiles)QuantitativeRealization/RunsWithinUnder, #279, #3372. A stated bridge to
QuantitativeRealizationPolyFun already has the layer below:
QuantitativeRealization.executionCost,RunsWithinUnder,wrapStatewithWrapStateCostCertificate, and fixedBoundaryencodings. Right now the two layers are related only in prose. I think the most valuable addition, whether in this stack or as its first follow-up, is one theorem of roughly this shape:This is the standard shape in the literature. In EasyCrypt's cost judgements (Barbosa, Barthe, Grégoire, Koutsos, Strub, Mechanized Proofs of Adversarial Complexity and Application to Universal Composability, CCS 2021), an adversary's cost is its own cost plus the sum of its oracle-call counts times the oracles' costs. It is instantiated by substitution, and the adversary's intrinsic cost is a separate term. calf (Niu, Sterling, Grodin, Harper, POPL 2022) makes the same split a phase distinction: the extensional phase erases cost, which is what
Realizesis here. Without the bridge, a charge bound is a free-floating proxy. With it,→+otransport (IsChargeBound.map) becomes the pricing step from one layer to the next.A concrete gap at the layer interface: #391's amortized caching transfer (
Path.exists_run_liftM_amortized) has no quantitative counterpart. The realizability guide says a cache hit needs silent steps, whichwrapStatedoes not cover. The two layers should agree on which handler shapes they support.3. Separate generic laws from security-facing contracts
Generic
ω(signed,ℕ∞,ExecutionCost, …) is right for the laws. But some choices ofωmake "cost ≤ budget" meaningless as a resource bound, and the API should make the safe choice easy and the unsafe one visible:K → ℕandKinfinite, a pointwise budget does not bound total work: one call to each of unboundedly many kinds respects a budget of1per kind. ArkLib's public count contracts require[Finite Kind]for this reason (knowledgeSoundnessWithResources,MeasuredKnowledgeCertificate).K →₀ ℕbudgets avoid the problem because the budget's support is finite. It would help to document this and offer a finite-kind contract form.OrderDual) or max-plus addition makes≤ Bmean something else entirely. ArkLib pinsKind → ℕwith pointwise+and≤, and hasfail_if_successtests that a caller's local max-additive or reversed-order instance cannot instantiate the public certificate (ArkLibTest/OracleReduction/MeasuredExtraction.lean).CostAtMostadmits signed prices. With a negative-priced operation, padding a program with "refund" calls meets any budget. That is legitimate inside a potential argument, but it should not reach a contract. I'd suggest a canonically orderedω(CanonicallyOrderedAdd) for anything presented as a resource bound, keeping signed weights for the completed-path calculus.4. Budgets must not be free functions of the input
A budget allowed to depend freely on each input or view can be defined as the program's own worst-case cost there, which proves nothing. #393's price-per-operation, independent of the view, already avoids one form of this. For families, the next step is to make the size measure and the budget envelope parameters fixed independently of the program, and to prove growth separately. This is also where PolyFun's
PolynomialRunBoundandPolynomialProgramWitnesssplit already points.A related lesson from FMN24 (ePrint 2023/846, Lemma 2.31): the printed growth condition
(ℓ(k−1))^µ = poly(λ)holds trivially whenℓ(k−1) = 1, while the extractor runs the prover(ℓ(k−1)+1)^µ = 2^µtimes. Bounds should be stated about the actual calls of the actual algorithm, which is precisely what a structural fold provides. That is an argument for this design. It also argues for modelling the prover or adversary as an interface, so that rewinding extractors are charged per prover invocation and the prover's own cost enters by handler substitution.5. Expected cost and handler transfer
For the expected-charge reading on the VCVio side, transfer through a handler needs the per-call expected bound to hold for every call argument and handler state (or history), not on average. Otherwise substituting an expected-cost implementation into a program whose calls depend on earlier answers can break the bound. Katz and Lindell (Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs, J. Cryptology 2008) is the standard reference. Worth fixing in the statement of the expected-transfer theorem before VCVio derives
expectedSimulatedQueryCountfrom it.6. Open question: composition along protocol telescopes
ArkLib #1448 (open) has a working client:
MeasuredStages.programAlongcomposes per-stage measured programs along an execution path.programAlong_budget_legivespath.length • bound, and the state-restoration specialization (ProtocolBudgetAtMost) givesrounds.length • (messageBound + challengeBound), which is exactly2on the acceptance fixture. That matches #390'sPath.chargeDec_le_length_nsmulclosely, so it should port directly. It would make a good acceptance test for the PolyFun measured-program API. The same applies to ArkLib's negative tests (infinite kinds, reversed and max-plus orders) and its zero-stageofFunclient.Smaller points
MeasuredProgram. I'd plan the VCVio side as a derivation from PolyFun, landed with its downstream callers, rather than a long-lived parallel type. ArkLib does not keep compatibility aliases by default.implemented_by/ FFI realizers can only enter the machine layer as named, tracked assumptions. ArkLib's axiom sweep treats native-compiler trust as never allowlistable, and a cost certificate that depends on one should say so.AllQueriesSatisfy/CallsIn) as a separate conjunct. Keeping that separation explicit in the generic API would be good.Happy to help turn the ArkLib cases into PolyFun acceptance tests.
dtumad commentedon Nov 4, 2026
Thanks, both. This shaped a follow-up round. I surveyed the layers above and below (RISC-V/zkVM models, the Lean benchmark statements for EVM gas, cycles and T-counts, group models, UC, CatCrypt, ArkLib), plus the literature. Then I ran a spike on bridging cost layers. Below is how I think we generalize, and what is coming.
How the pieces generalize
The structural fold stays as the base. It matches what the literature converges on: effect observations in Dijkstra-monad terms, CryptHOL's
interaction_bound, EasyCrypt's instantiation rule, and calf's extensional phase. Two benchmark projects already rebuild it by hand: a RISC-V cycle writer overOracleComp, and a T-count that is exactlyFreeM.cost.The generalization sits one level up:
(P, c : P.A → ω).Pby the layer below;E : ω →+o ω'that converts prices;ExecutionCost.There is one notion of link per level PolyFun has:
Handler.Certified P Q c d(handler, exchange, certificate)transfer : x within B ⇒ x.liftM h within E B, plus a value formCertified.comp: Kleisli composition, with exchanges composedStateful.WithinCharge(from every state).run.link, alongStateful.linkRefinesVia L h x σ₀:Limplements the run ofxthrough packagehRefinesVia.isChargeBoundRefinesVia.linkExecutionTrace.charge, plus a bridgeRunsWithinUnder.executionCost_add_charge_le(below)A reduction is a certified simulation between setup and finish stages. Its bound is affine in the source budget,
setupCost + E B + finishCost. That is the cost transformer every group-model reduction carries, and the Diller–NahmClockedlaw in CatCrypt.Costs that are not additive sit beside this, as stateful observers on the call stream:
Parallel composition is the one gap at every layer. A lax-interchange mixin fits work and peak space, but qubit width interchanges the other way, so I'd add it only with a client such as budgeted UC emulation.
Spike result
Everything below compiles with no
sorryon a local branch above #394:The end-to-end test chains three layers:
qhash queries;2 •);The machine is then within
6 qsteps, by composing the certificates and never unfolding the program.Still open:
πare a bare function. Alex's full theorem needs realizers whose costs areπ, and a way to close a realization against them. That is a design decision in realizability, which I'd take on next.Alex's points
These go into the open PRs before they leave draft:
IsChargeBoundandMeasuredProgram. It lists what is free (views, answers, inter-call code, handler state, encodings) and where each is bounded one layer down∃ M, M.Realizes f ∧ M.CostAtMost Bis trivial0for everyfviaofFun; statements name the measured programωand finitely many kinds (K →₀ ℕor[Finite K]), signed prices stay inside potential and path arguments, availability (CallsIn) and termination are separate conjunctsImplementsWithinChargeuses a uniform budget, likeImplementsWithinofFun) can come now;programAlongonce #1448 lands, against #390'schargeDec_le_length_nsmulBas
Since CatCrypt's results mostly live on its own monads, the most valuable piece is a bridge.
OracleAdvis already equivalent toFreeM (AdvSig D R)viaequivFreeM. WithtoFreeM_bind,toFreeM_substandtoFreeM_simulate,OracleSimulation,OracleSubst,OracleQueryVecand most ofOracleProfilebecome corollaries of the stack.cost_eq_iSup_profileis being ported into feat(pfunctor): charges of completed paths #390 (underProgramProgress).ClockedisCostedReductionabove.DNLenscould move as is once a rewinding consumer appears.Thanks for the
QAdvandqueryCost_eq_costpointers; I'll correct the "not covered" list above.What's next on the stack
Hardening in #388–#394:
wpFold_liftM_le);Three more PRs above #394:
spitters commentedon Nov 4, 2026
Thanks. From the CatCrypt side:
toFreeM_bind,toFreeM_substandtoFreeM_simulateoverequivFreeM, so thatOracleSimulation,OracleSubst,OracleQueryVecandOracleProfilecan become corollaries of the stack once feat(pfunctor): interface charges and structural charge bounds on free programs #388–feat(pfunctor): charge certificates, instrumented and gated handlers, handler transfer #391 merge.DNLens. Our forking and tree extractors (TreeForkingLemma, GeneralForkingLemma) run the prover several times; Diller–Nahm use counts (c₂ + n₂c₁) charge exactly per prover invocation, as Alex suggests.timeBound_simulate), andlink_timedproves a derived cost bounds the cost of the reduction's term in a call-by-value language with the cost model of Forster–Kunze's L, for first-order reductions.dtumad commentedon Nov 4, 2026
Thanks, Bas. All five points fit the stack. Below I map each to it, then step back to what the generalization covers, read from the weakest-precondition side.
Your five points against the stack
Bridge. Once
toFreeM_bind,toFreeM_substandtoFreeM_simulateland,OracleSimulation,OracleSubst,OracleQueryVecand most ofOracleProfileshould become corollaries of feat(pfunctor): interface charges and structural charge bounds on free programs #388–feat(pfunctor): charge certificates, instrumented and gated handlers, handler transfer #391.cost_eq_iSup_profilealready has a generic counterpart,Path.cost_eq_iSup_chargein feat(pfunctor): charges of completed paths #390 (underProgramProgress). Happy to review the bridge when it's up.Rewinding. A forking or tree extractor is a program over a prover interface, run within a call budget
n₂(a unit charge). Substituting a prover implementation of costc₁is a certified handler with exchangen ↦ c₁ · n(feat(pfunctor): certified handlers, costed reductions and stateful certificates #396). With the extractor's own workc₂as the setup and finish stages of aCostedReduction,run_isChargeBoundgivesc₂ + c₁ · n₂. So each prover invocation is charged, as Alex asked, and the extractor is named rather than quantified.DNLenscould then come in as the non-adaptive (⊗) counterpart of these adaptive (◁) handlers.Machine layer. The EasyCrypt shape "own time + queries × oracle time" is a charge bound on
P + linear ω. The program's own time is a tick onlinear ω, charged byid; each query is priced by the oracle time through the exchange. A certified handler then transfers the bound, andlink_timedsits naturally as the bottom link. feat: bridges from interface charges to machines and backend cost #398 has the two PolyFun-side versions:RefinesViafor machines;RunsWithinUnder.executionCost_add_charge_lefor quantitative realizations.A Forster–Kunze L backend would be another instance of that bottom link.
Budgets. Your three fixed shapes all have a home:
e ⟨a, b⟩ = b · |answer|(feat(pfunctor): answer-dependent charges and watermarks #397).This matches the uniform-budget convention in feat: charge bounds for resumptions, dynamical computations, interaction trees and indexed programs #392's
ImplementsWithinChargeand the "Bounds as contracts" notes in feat(pfunctor): interface charges and structural charge bounds on free programs #388.Caching. An exact path law (inner calls = new keys ≤ distinct queries) is a sharper form of feat(pfunctor): charge certificates, instrumented and gated handlers, handler transfer #391's amortized transfer, which gives
target calls + |σ₀| ≤ |σ_final|on every completed path. An exact version (equality) would be a second potential lemma; we haven't stated it. The lazy random function as the cached run with fresh draws belongs on the probability side.What the generalization produced, from the WP side
Every reading is an effect observation. Each cost notion in the stack is the fold
wpFold Φof a per-call specificationΦ : OpSpec P Linto an ordered carrierL. This is the free-monad case of "Dijkstra monads for all".Φ a kIsChargeBoundfun s => s + c a ≤ B ∧ ∀ b, k b (s + c a)ω → Propcostc a + ⨆ b, k bωfun s => ∀ b, s + e ⟨a, b⟩ ≤ B ∧ k b (…)ω → Propfun σ => canRoll a σ ∧ ∀ b, k b (cost a σ)σ → PropCallsIn Sa ∈ S ∧ ∀ b, k bPropc a + 𝔼[k]over the handler's stepσ → ℝ≥0∞Two laws hold for every reading:
wpFold_bind).wpFold_liftM): folding overx.liftM his folding the pulled-back spec overx, and pullback is functorial (OpSpec.pullback_pullback).Certified implementations are spec refinement. For the upper-bound readings,
wpFold_liftM_leis the whole transfer theorem. If each implementation is observed below its call's spec (the per-call certificate, after the exchange), the simulated program is observed below the original. Composing certified handlers composes the refinements. The budget reading is the order dual, whose transfer is proved directly. The other cross-layer links have the same shape one level down:RefinesViasays the machine's behaviour is the handled run, so its observation is the run's (isChargeBound_init_iff_denote);Core
vcgen. A reading that is aWPMonadgets core triples andvcgen:isChargeBound_iff_triple);StateTreading, where under the demonic base a triple is a bound on every completed path;triple_liftM_of_isChargeBound).In these terms, EasyCrypt's cost judgement is roughly a budget-reading triple with oracle-indexed ranks, and CatCrypt's
XDijkstra/TimedMis the graded version of the same thing, which #393'sBudgetedmirrors as aGradedMonad.How much existing work it covers
IsRollBoundis the general automaton, and charge bounds are its additive case;OpSpec.chargefold andhandlerCostgeneralize to any cost type;isTotalRollBound_mapLensis now a corollary of a generalIsRollBound.mapLens;Resumption,DynComputation,ITree,IFreeM) inherit the readings by truncation or erasure.IsQueryBoundfamily and #942's weighted budgets are instances;DeterminedCostandMeasuredProgramhave PolyFun counterparts with the same API;expectedSimulatedQueryCountis the expectation fold above.Clockedis aCostedReduction;TimedMcorresponds toBudgeted;programAlongis the node-weighted path charge;FreeM.cost;ImplementsWithinChargewith the unit charge.Not covered yet
⊗. A lax-interchange mixin fits work and peak space, but qubit width interchanges the other way.From the WP side, the natural next step is to state the refinement law once at the
OpSpeclevel, as a square between a spec, its pullback and an exchange. Relational readings (comparing two layers' costs) and the expected reading, with a linear exchange, would then inherit transfer and composition without lemmas of their own.spitters commentedon Nov 4, 2026
On budgeted UC emulation as a client: CatCrypt-core has it in two forms.
RealizesTime X Y n o q tDquantifies over environments whose activations, per-activation costs, rounds and distinguisher are bounded (EnvTimeBound). Costed environment pullbacks carry these budgets through contexts:realizesTime_map(one hole),realizes_twoHole(two holes),realizes_seq_timed(cascade), with each reduced environment's budget growing by constants of the context; hybrids and adversary absorption in UCPullbackTimed; quantum versions in QPullbackCost.UCAdmClass_of_costModel), and time-bounded in a deep call-by-value language (ucCdistTime, with graded composition laws including the coproduct), plus the asymptotic form (UCTimeNegl).Parallel composition is non-expansive for the realization distance (UCCascadeEnrichedPar); a costed parallel instance of the two-hole law is the piece we have not stated, so a lax-interchange mixin in PolyFun would have a direct client here.
spitters commentedon Nov 4, 2026
The bridge is up: OracleAdversaryFreeBridge.
toFreeM_bind:toFreeM (A.bind f) = (toFreeM A).bind (toFreeM ∘ f).toFreeM_subst:toFreeM (subst impl A) = (toFreeM A).liftM (substHandler impl), wheresubstHandler implreissues sampling nodes and sends a querydtotoFreeM (impl d).toFreeM_simulate:toFreeM (simulate impl A s) = (simHandler impl).run (toFreeM A) s, withsimHandler impl : Handler.Stateful _ S _.isQueryBoundBy_iff_wpFold_charge,isQueryBound_iff_wpFold_charge: our per-query cost bounds are theOpSpec.chargefold oftoFreeM A. At the PolyFun revision VCV-io pins, the non-indexedFreeMhas noIsChargeBound, so these are stated throughwpFold; they becomeIsChargeBoundstatements once feat(pfunctor): interface charges and structural charge bounds on free programs #388 lands.dtumad commentedon Nov 4, 2026
I ran a dry run of VCVio adopting the stack, all local. VCVio
mainplus #1023 (reduciblesimulateQ) was built against the stack tip as a path dependency.Results
IsTotalQueryBound,IsQueryBoundP,IsPerIndexQueryBound, and the online and point bounds are each anIsChargeBound, with a unit, indicator,Pi.single, pair or point charge.WorstCaseCostBoundis a bound on the charge of every completed path.MeasuredProgramis PolyFun's (feat(pfunctor): measured and budgeted programs #393) up to renamingspectoAns. feat(pfunctor): measured and budgeted programs #393 now uses the same composite interface and the same argument order.wpFold_liftM_le, and the stateful case of the newwpFold_run_liftM_le.suffix_boundis plainrun_liftM.prefix_boundneeded a runner that can pause, with an amortized budget; that is the prefix-form item in the checklist.Fed back into the drafts
IsChargeBound.sumand.const;isChargeBound_natCast_iffover any ordered semiring of characteristic zero, soℝ≥0∞as well asℕ∞;isChargeBound_single_iff_isRollBound;IsChargeBound.liftM_nsmul;programProgress_of_nonempty;wpFold_run_liftM_le.Path.charge_finsetSumandPath.charge_apply;withPathCharge;Path.charge_bind_mapLens_le, of which feat(pfunctor): measured and budgeted programs #393'sCostAtMost.compis now an instance.Handler.withChargeW, which instruments in a writer (the shape of VCVio'sAddWriterT);FreeM.runUntilwithIsChargeBound.runUntil, which closes the prefix-form item.A second pass, pointing VCVio at the amended lemmas, removed another 68 lines net (+36 −104). It also re-proved one of the kept theorems,
IsTotalQueryBound.of_perIndex, in three lines. VCVio still builds against the new tip with no new warnings.Outside the stack
OracleCompgoals neededPFunctor.Obj.mkpassed tosimpby hand, sosimplemmas for the projections ofObj.mkwould help.Examplesmodule root collides with VCVio'sExampleslibrary. A git pin does not build a dependency's examples, so this is latent for now.The VCVio side is staged as three local branches:
WorstCaseCostBoundand measured programs;They can open once the stack merges and VCVio bumps its pin, which Quang coordinates.
spitters commentedon Nov 5, 2026
On
IsChargeBoundas the shared predicate: every costed tree kind in CatCrypt-core now has its time bound proved equivalent to a charge fold of its FreeM image, with the program's own step costs as tick calls.TimeBound↔IsRollBound↔ theOpSpec.chargefold of the tick tree (OracleAdversaryFree, OracleProgTimedFree). In oracle programs the continuation cost depends on the answer; it becomes a tick after the answer, so the charge stays per call.OpSpec.chargeUnder c allows, whose continuation is taken over the answersallowsadmits (chargeUnder_truerecoverscharge); seeSPTree.Timed.timeBound_iff_wpFold_chargeUnderin SPTreeTimedFree.On Alex's first point: in these tick trees the code between calls is charged. The costed form
R.timedof a reduction is derived from the reduction's term byderive_timed, each step carries the cost of the code it runs as a tick, and the erasure theoremR.erase_timedstates that removing the ticks givesRitself. The time bound is therefore a statement about the named reductionR.Once #388 lands we plan to define these time bounds as charge bounds of the tick trees. For the probabilistic case this needs a budget reading restricted by an answer relation,
s + c a ≤ B ∧ ∀ b, allows a b → k b (s + c a), the budget counterpart ofdemonicUnder. Would you consider anIsChargeBoundUnder(or anallowsargument onOpSpec.budget) in #388?dtumad commentedon Nov 5, 2026
The stack is ready for review. All ten PRs pass
./scripts/validate.sh --lint --test --axioms, and they are out of draft.Review order
Review bottom-up. Each PR is based on the previous one:
IsChargeBoundand its laws, the relation toIsRollBound, the transfer principleswpFold_liftM_leandwpFold_run_liftM_lecost_bound,CallsInandMayCallStateTand writer) and gated handlers, stateful and amortized transfer, pausing runsvcgenfor charge boundslinkRefinesVia) and to quantitative realizationsAdded since the last comment
cost_bound#389:MayCall x a, the calls occurring in a program. They form the least set it calls only in, as in CatCrypt'sMayAsk.joinBind, the inverse ofsplitBind;exists_path_liftM_iff(CatCrypt'smem_profile_subst_iff);charge_liftM_le_of_forall_output).runUntilrun stays within the interrupted program's budget (IsChargeBound.runUntil_paused, VCVio #945'sPrefixResult.Bounded).Open follow-ups, for anyone to pick up
Path.Threadspredicate withexists_run_liftM_iff, the stateful counterpart of the substitution law (CatCrypt'smem_profile_simulate_iff).joinBindis in place for it.OracleCache).[EmptyCollection ω] [Append ω]). The monoid writer case is in feat(pfunctor): charge certificates, instrumented and gated handlers, handler transfer #391; this would let VCVio'ssimulateQ_run_writerT_of_stepport.Overlap with the probability layer
PolyFun is adding an optional measure-theoretic library,
PolyFunProbability, outside thePolyFunumbrella (#400; #401, #402, #403, #404, #405). PolyFun's boundary with VCVio moves from probability to cryptographic security.expectedQueryCountfrom path length toPath.charge, with its bound fromIsChargeBound;wpFold_liftM_le/wpFold_run_liftM_le;AddSupDistrib ℝ≥0∞instance for worst-case costs inℝ≥0∞.Who might look at what
OracleProfile.VCVio's side stays local until the stack merges and VCVio bumps its PolyFun pin. It consists of bridges and re-proofs (21 theorems, 313 → 95 lines in the dry run),
WorstCaseCostBoundand measured programs, and expected cost.dtumad commentedon Nov 5, 2026
Thanks, Bas. Yes, both go into the stack, with
allowsat the automaton level rather than only on the budget.feat(pfunctor): interface charges and structural charge bounds on free programs #388. Restricted answers enter at the automaton level, so they cover roll bounds as well as charge bounds:
OpSpec.rollUnder canRoll cost allowsandIsRollBoundUnder;OpSpec.budgetUnder c B allows, which is yours + c a ≤ B ∧ ∀ b, allows a b → k b (s + c a), andIsChargeBoundUnder.With every answer allowed, these are
IsRollBoundandIsChargeBound(_truelemmas).isChargeBoundUnder_iff_isRollBoundUnderrelates them, asisChargeBound_iff_isRollBounddoes now. The laws are monotonicity inallows,bindandmap. A charge bound gives a bound under any restriction.feat(pfunctor): worst-case cost, loops, support-restricted sequencing and
cost_bound#389.OpSpec.chargeUnder c allowsandcostUnder, upstreamed from yourPFunctorChargeUnder, withchargeUnder_trueand the bridge fromIsChargeBoundUndertocostUnder ≤ B.On the accounting boundary:
derive_timedwitherase_timedis the cleanest version of what Alex asked for. The time bound becomes a statement about the named reductionR, with the code between calls charged as ticks.On #380: I'll comment there on how #389 builds on its
cost.spitters commentedon Nov 5, 2026
A proposal for dividing the work between the stack and CatCrypt's time certificates, in three stages.
derive_timedandderive_reductionturn a reduction written as ordinary Lean code into a costed form and prove an erasure theorem: removing the ticks gives the reduction back. The stack has no counterpart, since its programs carry their charges from the start.AllRet(SPTreeTimedFree, OracleAdversaryFree). For probabilistic trees the fold is taken over the program restricted to the supports of its sampling nodes:PFunctor.restrictkeeps the directions an answer relation admits, andwpFold_chargeUnder_eq_restrictmakes the restricted fold a plainOpSpec.chargefold. This answers our earlier request for an answer-restrictedIsChargeBound, so feat(pfunctor): interface charges and structural charge bounds on free programs #388 needs no change for it. Once feat(pfunctor): interface charges and structural charge bounds on free programs #388 lands we redefine these time bounds asIsChargeBound.cost_boundcloses concrete programs over finite answer types. Ourtime_boundandderive_time_boundclose bounds that stay symbolic in the adversary's time and query counts, over the same predicate. We are extending them to any goal of the formwpFold (charge c) x k ≤ B, including programs written directly inFreeM, and will pass concrete leaves tocost_bound.Two pieces are written so they could move into PolyFun:
PFunctor.restrictwithFreeM.wpFold_mapLens, and vector charges with handler composition (PFunctorChargeVec). The latter states the cost of a program run through a handler as composition with use counts, which is the Diller–Nahm composite (DNCert). We can open a PR for either if you want them in the stack.5 remaining items
feat(pfunctor): charges of completed paths (#390)
docs(cost): why AddSupDistrib excludes the empty set; pin cost_bound …
dtumad commentedon Nov 10, 2026
I rewrote the description for the state after phase 1.
useBound_liftMandisChargeBound_liftM_demandare instances of one composition theorem. The original Diller–Nahm variant, with finite sets, is the accounting a cache gives;bangW Sover different semirings may give each accounting uniformly, which is to check.costToGo, rewinding and parallel-composition questions. Backend-relative resource bounds roadmap #279 now tracks backend-relative bounds only.cc @alexanderlhicks @spitters @quangvdao
quangvdao commentedon Nov 10, 2026
A note on the quantum row of "Not covered".
Query counts of quantum programs are already covered. In VCVio,
QuantumComp.IsQueryBoundAt,IsQueryBound,IsTotalQueryBoundandIsCostBound(VCVio/Quantum/Comp/QueryBound.lean,TotalQueryBound.lean) are instances of the indexedIFreeM.IsChargeBound, with a unit charge on calls of the selected port and a costc oon local operations. Their bind and transfer lemmas come from the generic ones.What stays outside is query mass: an amplitude-weighted, state-dependent real quantity used in the square-root hybrid bound. It is not a function of the tree, so it is not a charge, and leaving it out is right.
CatCrypt's
QAdv m n w qfixes the count in the type, so it needs no bound. The proposal in lean-crypto-foundations/QuantumCrypto#2 takes general programs within a charge bound and maps them to a comb with exactlyqcalls. So the fixedqis the output of a normal-form theorem, andIsChargeBoundis its hypothesis. Could the row say this, so the quantum case is listed as covered for counts and out of scope for mass?dtumad commentedon Nov 10, 2026
Parked: #397 (answer-dependent charges and watermarks) and #398 (bridges from interface charges to machines and backend cost) are closed because neither has a consumer yet. Their branches
feat/cost-observersandfeat/cost-bridgesstay. Revive them when a proof needs prices that depend on answers, or cost at the machine level.alexanderlhicks commentedon Nov 17, 2026
An update from the ArkLib side, following the discussion above. Thanks for taking up most of the earlier points: the accounting-boundary section, the trivial-∃ test, the contract notes, the Katz–Lindell condition in the roadmap item on stateful expected-charge transfer, and the ArkLib-shaped tests. Since then we reviewed the resource work across PolyFun, VCVio, CompPoly, ArkLib and leanerVM, and prototyped the pieces that the review called for. The prototypes are local branches. Each passes its repository's validation on its own, and no combined downstream consumer has been validated yet. Claims marked "checked" are checked in Lean on these branches, and we will link them with the PRs. We will open the PRs once the owners here agree on the shapes.
What the review found
evalto Horner's method through@[csimp], while ArkLib charged the power-sum form (about n² multiplications) for FRI's extractor.IsFinder.costbounds expected reruns. Multiplying it by an expected per-challenge cost is unsound for theIsFindercontract, because the finder chooses challenges after it sees the world (checked counterexample at error 0). The expectation over worlds of the largest per-challenge cost is sound.MeasuredProgram.Prototypes (local branches; each passes its repository's validation)
MeasuredProgram.CostWithin size envelopebounds every completed path of the program, run on each input's own view, by the envelope at that input's size.PolyCostandFamilyPolyCostare the polynomial forms.PolynomiallyBounded, used only in a separateSized/Growthmodule. That module also refutes the polynomial forms from a super-polynomial lower bound on qualifying completed paths.CostWithinUnder,PolyCostUnder, …) bound only the paths whose answers anallowspredicate admits. Restricted toAnswered, they say exactly that the actual run meets the envelope (costWithinUnder_answered_iff). They compose alongCompAllows, given the intermediate output-size bound and monotone outer envelopes. Polynomial envelopes have the required monotonicity.∃ M, M.Realizes f ∧ M.PolyCost sizeholds for everyf, so the evidence is a named program, and even that is accounting, not adequacy. There is no consumer yet.Tthen has expected accumulated charge at mostTtimes the expected largest rerun cost over the frozen world (checked).@[csimp]targets ofevalandeval₂run one monadic definition, andevalHornerM_countinggives one read, one addition and one multiplication per coefficient. We raise it on tracking: formalize Reed–Solomon decoding and certified operation bounds in CompPoly CompPoly#377 first, where the primitive cost model is an open maintainer decision.Proposals for PolyFun
→₀budgets). GenericCostAtMoststays for laws. PolyFun already tests these failure modes (PolyFunTest/PFunctor/Charge/Basic.lean). A contract predicate would turn them into rejected instances, and ArkLib could then drop its local restrictions.executionCostbound.PFunctor.FreeM.expectedQueryCountof feat(probability): measure and kernel semantics of free programs, and the security boundary #441 has the same full name as a VCVio declaration. VCVio's next PolyFun bump past feat(probability): measure and kernel semantics of free programs, and the security boundary #441 therefore needs a rename on one side.MeasuredProgram. VCVio's has no non-test consumer inside VCVio. ArkLib uses it in 5 library files and 4 test files on main, so the unification lands together with an ArkLib repin.Open for discussion: multivariate size measures (security parameter, query count, field size) for
CostWithin, and the form of leanerVM's extractor contract (Verified-zkEVM/leanerVM#157).spitters commentedon Nov 17, 2026
Two points of the review concern constructions that CatCrypt already has; both are on CatCrypt-core main.
Counting what runs (point 3).
derive_csimp f via S₁, …, Sₙbuilds the runtime implementationf.csimpImplfrom source theorems, provesf.csimpImpl = fand installs it with@[csimp]. It then derives the cost off.csimpImpland registers it as the cost off, so a time certificate prices a call offby the code the compiler emits, and the@[csimp]theorem justifies that price. When the cost derivation is refused, no cost is registered forf.Rewinding (point 4).
forkExtractor_timedprices each retry of the fork atB, the certified time of one fork in the worst case over its runs, so the expected cost of the extractor is at mostB / forkBound A x. A constant worst-case price per attempt is an instance of the sound form in the review, the expectation over worlds of the largest per-challenge cost.On point 2: CatCrypt's extractors and reductions are named definitions, each with a time certificate (the costed program, its erasure theorem and a time bound), and its security statements bound the advantage of every adversary by the advantages of these reductions.
CatCrypt's cost and complexity work is summarized in
Crypto/Complexity.md, which indexes the other documents, among themContainer/README.md: costed programs as morphisms of the Diller–Nahm category, extractors as realizers of derivations, the expected cost of rewinding, and bound extraction from classical proofs.alexanderlhicks commentedon Nov 17, 2026
Thanks, these are useful references, and both agree with the review.
Point 3.
derive_csimpapplies the principle that the CompPoly prototype applies to one definition: price the replacement that the@[csimp]theorem installs. The prototype does this only forevalandeval₂. Both@[csimp]targets run one monadic Horner definition, and a counting instance of the same definition gives the count.derive_csimpis a general command. It proves that the replacement equalsf, and whenderive_costsucceeds on the replacement andfhas no registered cost, it registers the replacement's cost forf. The equality theorem justifies the replacement. How closely the registered cost tracks execution depends on the cost model. As its module docstring says, the price applies only to callers compiled after the@[csimp]theorem. The primitive cost model for CompPoly is still open on Verified-zkEVM/CompPoly#377, and the cost model ofderive_costis a reference point for that decision.Point 4. Yes. A constant worst-case price per attempt bounds the largest per-challenge cost for every world, so
forkExtractor_timedis an instance of the sound form. The VCVio form of this corollary is in Verified-zkEVM/VCVio#1166 (IsFinder.expectedCalls_bind_runCharged_le, andfinder_bounds_charged_of_worstCaseCostBoundat the attempt level). The two settings differ in one way that matters only for non-constant prices.forkExtractorretries a fixed fork at mostNtimes, each retry with fresh randomness, and the boundB / forkBound A xholds for everyN. VCVio'sIsFinderlets the finder choose the next challenge vector after it sees the world. Under that contract, our counterexample (VCVioTest/RewindingCost.leanin that PR) shows that the expected per-challenge cost does not suffice. With a flat priceB, both giveBtimes the expected number of attempts.Bcovers both runs of the fork, each with the adversary, the verifier and the oracle simulation, plus the extraction step (extractReduction.timeBound_timed). The relation checkcheckWis not charged:BboundsextractReduction.timed, andforkAttemptTimedapplies the check throughCostComp.pure. The VCVio PR also leaves work outside its accounting. It charges the queries of the computation that the caller supplies for each rerun, and it does not charge local computation.Point 2. Agreed. What matters is that the same extractor satisfies knowledge soundness and the stated cost bound. An existential theorem can express efficiency when its witness also has an adequate execution-cost certificate. CatCrypt's explicit programs, erasure theorems and cost bounds in a stated cost model are useful examples. The ArkLib prototype keeps the extractor named, but it counts declared operations only. It does not yet establish executable extraction within a runtime bound.
dtumad commentedon Nov 17, 2026
I'd also just flag that once v4.36 settles we can also hopefully get core's
vcgento prove most simple query count boundsalexanderlhicks commentedon Nov 17, 2026
that would be nice! Once things are stable we should also be able to add tactics as needed more generally.
spitters commentedon Nov 18, 2026
@dtumad, on
vcgenand query counts: CatCrypt-core's XDijkstra kernel relates the counter form to the graded form.costBoundedEquividentifies the programs into the graded monadCostM σ nwith the programs of the tick-counting state monadTickM σof cost at mostn, andxmvcgen!reduces a grade bound to arithmetic (example). After 4.36 we plan aWPMonadinstance forTickM, so thatvcgenproves the counter bound andcostBoundedEquivtransfers it to the graded one.spitters commentedon Nov 18, 2026
Thanks, Alex. The relation check is now charged: each attempt pays
tChkfor decidingP.rel x w, andforkExtractor_timedbounds the expected cost by(B + tChk) / forkBound A x.alexanderlhicks commentedon Nov 18, 2026
Two corrections to my update above, and a tracker.
PFunctor.FreeM.expectedQueryCountcollision needed no rename. refactor(EvalDist): import the generic measure semantics from PolyFun, with names unchanged VCVio#1085 made PolyFun the owner of these declarations and kept their names.CostWithinrelates to feat(pfunctor): relate deterministic query counts to path length #484's bridge to cslib'sQuery.UpperBound.The remaining work is tracked in Verified-zkEVM/ArkLib#1528. Two questions for the maintainers here:
MeasuredProgram(proposal 5) go ahead in PolyFun and VCVio? The predicate would require finite total cost under natural-number counting. It would not require finite oracle input domains.spitters commentedon Nov 19, 2026
Thanks, Alex. On your second question, from our side:
exists_path_runshows that the calls a cached run forwards are charged the fresh charge of the client trace outside the initial cache, andlength_run_add_cardshows that their number is the growth of the cache. A meter outside the cache charges the client's full path charge (exists_path_run_withCharge). Both statements relate a charge to the calls that actually reach the oracle, which is the handler-level case ofRunsWithinUnder.executionCost_add_charge_le.ExecutionTrace.charge,RunsWithinUnder) in PolyFun, since it needs no frontier module. L2 and L3 of PolyFunFrontier: the cslib-frontier side of PolyFun #425 would then instantiate it at frontier's machine classes. Machine refinement (RefinesVia) could wait for its first machine-level user, as Quang proposed.On the first question, a contract-grade predicate that requires finite total cost under natural-number counting fits our use: the summary functor of #497 and CatCrypt's tick-counting monad both count in ℕ.
dtumad commentedon Nov 21, 2026
Thanks, Alex and Bas. Answers to both questions:
1. Contracts and
MeasuredProgram. Yes to both, and to the sized contracts:CostAtMost, which stays for the laws: canonically ordered counts with the standard addition and order, finitely many kinds or→₀budgets, and finite total cost under natural-number counting, without requiring finite oracle domains;MeasuredProgram: VCVio's becomes PolyFun's, landing together with ArkLib's repin;CostWithin,PolyCostand the restricted forms) in PolyFun, with cslib'sPolynomiallyBoundedas the growth predicate. Their docstrings should say they bound declared operations, and no name should suggestPPT(Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy) VCVio#906). Strict PPT now has its own route: feat(realizability): prove admissibility of scoped term interpretations #510 and feat(frontier): realize handled free programs on polynomial-time machines #511 here, with feat(frontier): sync PolyFun and realize one-time pad and ElGamal security VCVio#1206, certify handled free programs (PPTProgram) and realize them as one fair-coin machine with one polynomial clock whose output law is the program's.Stateful expected-cost transfer (your proposal 4) merged as #486, and VCVio's PolyFun pin now includes it.
2. The bridge. We'll follow Bas's split. We'll revive the realization layer of #398 (
ExecutionTrace.charge,RunsWithin.isChargeBoundandRunsWithinUnder.executionCost_add_charge_le) as a fresh PR on currentmain, with #499 and FRI's extractor as its consumers. It gives the concrete execution cost of a run from its charges, relative to a backend; #511 is the asymptotic counterpart on the frontier side and does not go through charges. Oracle realizers priced by their proved cost, with an overhead in path length and encoded sizes, go on top. Machine classes and adequacy stay in #425, andRefinesViawaits for a machine-level user. Composition laws of quantitative realizations are #505.