Question
Reach while-loop invariant rejected when referencing interact-supplied value
Ira Indigo
0 reputation · 23 Nov 2021, 15:15 UTC
25.2K views
Loading…
0 reputation · 23 Nov 2021, 15:15 UTC
Reach supports while loops in local steps, but each loop must carry an invariant and a decrease measure so the built-in verifier can discharge termination and safety obligations at compile time. The goal is to write a loop whose invariant references a value obtained from the frontend through interact. The uncertainty is whether the verifier treats that value as opaque, making the invariant unprovable even when the frontend guarantees the property.
Because interact crosses the consensus boundary, the verifier may model the result as unknown. This raises an unresolved semantic question: should an invariant justified only by a frontend promise be accepted locally, or must the loop body re-establish the fact from consensus-known state? The distinction between assume and checked assertions is central, and misclassifying a frontend guarantee as a consensus fact is the likely source of the impasse.
This behavior is version-sensitive; simplification rules and accepted proof obligations have changed across Reach releases, so a program that verifies on one toolchain may fail on another without code changes.
Should the verifier accept an invariant that quantifies over an interact-provided value when the frontend guarantees it, or is an explicit assume required to bridge the boundary? If the latter, must the loop re-derive the property from consensus state, or is there a supported way to document the frontend contract for the prover?
34775 reputation · 24 Nov 2021, 02:35 UTC
Yes, the verifier treats an interact-supplied value as opaque for proof purposes, so an invariant that depends on a property of that value will be rejected unless you either insert an explicit assume after the call or re-derive the property from consensus-known state. A frontend guarantee is not automatically available to the prover.
The confirmed symptom is that the invariant is rejected when it references the interact result. The likely explanation is that the verifier models values crossing the consensus boundary as non-deterministic, and loop invariants must be provable from local state and constraints already in scope. Because the verifier has no formal model of the frontend's contract, it cannot discharge an obligation that relies on an unconstrained external value.
Using assume tells the prover to treat the property as given. That is the supported way to document a frontend contract locally, but it shifts the safety burden to the frontend: if the frontend violates the assumption, the consensus step may still accept the result.
reachinteract value in the invariant with a constant. If the loop verifies, the origin of the value is the cause.assume immediately after the interact call, asserting the property the frontend promises. If the invariant is then accepted, the boundary is confirmed as the issue.Use assume only when the frontend genuinely enforces the property and you accept the soundness trade-off. If the invariant protects a consensus invariant that must hold regardless of frontend behavior, re-establish the fact from consensus state.
One diagnostic detail would change the recommendation: the exact Reach compiler version. Because verifier behavior is version-sensitive, a pattern that works on one stable release may fail on another. Sharing the version would let me narrow the advice to that release's specific proof obligations.
Use comments to ask for clarification. Post a solution as an answer.
No question comments on this page.