Skip to Content
Scalus Club is now open! Join us to get an early access to new features 🎉

Tuning Your Proof

Not every statement is decided at once. A check can come back inconclusive, or run until its time limit. Four things can be tuned: the budget of steps Lean’s machine runs each program, the data the statement ranges over, the form in which a script context reaches Lean, and the time a check may take.

The Budget

Lean runs each program of a statement for at most a budget of steps of its CEK machine, and Blaster reasons about that bounded run.

  • A proof at any budget holds without the budget. A run that needs more steps counts against the proof: a claim must return true within the budget, and a premise that has not finished counts as true. So too small a budget cannot prove a false statement.
  • Too small a budget gives a spurious counterexample. Scalus replays it on its own CEK machine, sees that the statement holds there, and reports Inconclusive. The reason says how many steps would do.

Let Scalus Find It

check(statement), without a budget, searches for one (Budget.Auto). It starts at 100 steps. Where Lean’s counterexample is spurious, Lean’s machine counts what each program does on it, and the search goes on at the least budget at which the statement holds there. For a statement that the vesting validator rejects an early withdrawal, the search went 100, 262, 649, 694, 1315, 1573, 1584, 1608, and proved it there: eight checks in 45 seconds.

The budget found is kept with the result, in <Suite>.proofs.json. A statement that has not changed is taken as it was kept. When the code changes, the next search starts at the kept budget, so a statement still decided there takes one check.

Give It Yourself

check(statement, budget = 4000) checks at a fixed budget (Budget.LeanSteps(4000)). Use it when you know the cost of the statement, or to save the search on a run without kept results.

  • Stay close above the worst path. Proof cost grows faster than the budget. For a gcd property whose worst sample needs 203 steps, budget 250 proved in 2 seconds, 350 took 52 seconds, and 500 did not finish.
  • The path that counts is that of the runs the statement is about. A statement that a validator rejects a transaction needs the budget of the rejection, not that of a whole accepted spend. The vesting validator rejects an early withdrawal after about 1600 steps: the statement is proved in 12 seconds at budget 1700, and not at all at 12000.

Do not derive budgets from ExUnits. Plutus charges for each Eval transition, while Lean’s machine counts Eval and Return: a Lean budget is about 1.85 times Scalus’s step count.

Within a Bound

Budget.Within(n) proves a statement of the inputs whose runs end within n steps. A run that the budget cuts is read in the statement’s favour, so it is no counterexample. The result is ProvenWithin, with the bound: a weaker statement, not a theorem. Use it for a statement that no budget proves, to learn that it holds as far as the runs go.

Limit the Data

A validator that walks a collection of the script context, such as the signatories, the inputs or the outputs, walks it to its end. For a statement over every context, the solver can always propose a longer collection than the budget’s runs walk. Its counterexample is then spurious at every budget, and the check runs until its time limit.

forAllDataLimited bounds the length of the collections of a variable:

forAllDataLimited[ScriptContext](ctx => ctx.txInfo.signatories.length <= 2)(ctx => (isRefund(ctx) && !signedByTheCommitter(ctx)) ==>: fails(validator, ctx.toData) )
  • The limit is of the shape of the values: maxCollectionLength(x) <= n, the length of a collection of x compared with a number (x.txInfo.inputs.length <= 3), isEmpty, nonEmpty, and forall over a list, or over a map’s keys or values, of the limits of each element, joined with &&. Any other condition belongs in the statement’s premise; the compiler says so.
  • Each test checks the limits first, with a walk that ends, so a walk over a limited list runs to its end. The statement is proved as a theorem of the values within the limits. With Budget.Auto, the search starts at the steps the programs take on the largest values the limits allow.
  • It says nothing of larger values. Name the statement so, and keep the statement of every context beside it.

The HTLC suite does all three for the rules that depend on the signatories. It states each rule of every context, and tags that test Unfinished. It states the rule again of the contexts of at most two signatures, under the same name with _limited, where Lean proves it:

inline def forAllContextsMax2Signatures(inline body: ScriptContext => Prop | Boolean): Prop = forAllDataLimited[ScriptContext](ctx => ctx.txInfo.signatories.length <= 2)(body) private val refundRejectedUnlessTheCommitterSignsLimited = verifier.statement( "htlc.refund.rejected_unless_the_committer_signs_limited", forAllContextsMax2Signatures(ctx => (isRefund(ctx) && !signedByTheCommitter(ctx)) ==>: fails(validator, ctx.toData) ) )

The rules that the validator decides by the time, before it reads the signatories, need no limit: see Your First Proof.

How a Script Context Reaches Lean

A script context that a statement quantifies over reaches Lean in one of two forms:

  • As Data: one Lean Data, restricted by a premise to the encodings of Scalus’s ScriptContext. This form assumes nothing, but Lean decodes the context for every rule that reads it.
  • As a typed value: a value of the ScriptContext type of IOG’s CardanoLedgerApi , a Lean structure of the Plutus V3 context, with its transaction, redeemer and script purpose. The programs get its Data, which the library encodes as Plutus does. The solver then searches structured contexts instead of arbitrary Data.

The programs are the same in both forms. What differs is what the statement ranges over, and how fast Lean decides it.

Auto: The Default

By default (VariableMapping.auto) the statement’s form chooses, so that the choice assumes nothing:

The statementThe context isWhy
has isValid(ctx) as a premisetypedisValid holds only of the Data of a valid value of the library’s type, so the statement over typed values says exactly what the one over Data does
is a negative control (refute)typedthe replay checks the counterexample on Scalus’s own value, so the mapping cannot make a refutation wrong
anything elseDataa typed value would assume that the library’s type has a counterpart of every Scalus context, which is checked of samples, not proved
asks for a witness (exists)by fieldsthe solver builds the witness, and neither form above can stand for one

Only the variable itself is typed, not a part of another variable. A context is typed with limits too (Limit the Data): the guard reads its Data.

Auto was chosen by measuring the example suites with every context as Data, and with every context typed:

  • With isValid, typed is faster. Over Data, Lean evaluates the ledger’s rules on a decoded Data, which cost 5 to 11 seconds a check on the HTLC validator; typed, the rules read the value. Several statements with limits got two to three times faster, the HTLC suite’s statements as a whole about a quarter faster, and a few small ones a second or two slower.
  • Negative controls typed: those with limits three to four times faster, the others about the same.
  • Without isValid, typed is not reliably faster. It was faster for 7 of 10 statements, but the largest statement of the payment splitter took twice as long (170 s, then 341 s), and the statement would rest on an assumption.

Writing Statements for It

  • Put isValid(ctx) in a premise: isValid(ctx) ==>: premise ==>: claim. Auto finds it in any premise of the chain, inside && too, and under further forAlls, but not under an exists. isValid in a claim is no premise, and leaves the context as Data.
  • Leave isValid out of a negative control. Its refutation would need a balanced transaction the validator accepts, and the solver does not find one in time. State it of every context, valid or not.
  • State a sample as valid too: isValid(sample) && succeeds(validator, sample.toData) shows that the ledger accepts the transaction, and Lean evaluates both.

Choosing Otherwise

A suite overrides variableMapping; a tactic takes withMapping:

class SomeVerificationTest extends AnyFunSuite with LeanProofsSuite { // Every context typed, with or without isValid. override protected def variableMapping = VariableMapping.rules.preferLeanTypes
MappingWhat it does
VariableMapping.autothe default, as above
VariableMapping.rulesData for every context, by fields for small case classes
VariableMapping.rules.preferLeanTypesa typed value wherever the library has a type, also without isValid
VariableMapping.rules.forType[A](choice)choice for the type A only, one of VariableMapping.Choice: Auto, Rules, ByFields, AsData or LeanType

A mapping is part of what a kept result rests on: a result kept under one mapping is checked again under another.

A typed counterexample is repaired. The library’s type keeps some parts of a context as any Data, so it has values that no Scalus context has. Where Lean’s counterexample is one of them, the replay repairs those parts, says so, and decides on the repaired value.

The Time Limit

A check has a time limit by the clock: ten minutes (UplcBlaster.defaultTimeout). A check that reaches it is given up, and is Inconclusive. The reason says where the check was:

  • still running a program symbolically: the budget lets a program run through a long walk. A smaller budget, or limited data, may cure it;
  • with the solver: the statement is hard for the solver as it is stated.

To give a check another limit, pass the tactic yourself:

check(VerificationRequest(statement, UplcBlaster(Budget.Auto, lean, 20.minutes)))
  • With Budget.Auto, the limit is that of the whole search. withAttemptTimeout(t) adds one for each check of the search.
  • withoutTimeout lifts the limit.
  • withMaxHeartbeats(n) sets Lean’s own limit of work for one command, twice Lean’s default unless you say otherwise; 0 means none. It ends a check the same way on every machine, but the solver’s time does not count towards it.

Mark What Does Not Finish

Tag a test of a statement that Lean does not finish with Unfinished. Such a test waits for its time limit, and the solver can take gigabytes meanwhile. verify leaves these tests out, and so should test (see sbt Commands). They stay in the suite as the record of what is not proved yet, and testOnly runs them on purpose.

To see what Lean is given for a check that does not finish, keep the checks (SCALUS_LEAN_KEEP_CHECKS) and run one by hand: see Looking at a Check.

Last updated on