Repository navigation
Description
Xreal: hint simplify of_realI makes delta-reduction of Rp.inv / (inv x)%rp loop (hangs call /(fun v => inv c ** v) in ehoare)
Claude found this bug as it was testing ehoare to then write some documentation on it for me. It generated this bug report.
Version: EasyCrypt r2026.10 (OCaml 4.14.2)
Summary
In theories/datatypes/Xreal.ec, three things together form a rewrite cycle:
op inv (x : realp) = (inv x%r)%rp(inRp): delta-unfoldingRp.inv cgives(inv c%r)%rp;hint simplify of_realI, withof_realI : (inv x)%rp = inv x%rp: this turns that back intoRp.inv (c%r%rp);hint simplify to_realK_simpl(x%r%rp = x): this gives backRp.inv c.
Plain simplify never unfolds Rp.inv, so nothing goes wrong there.
Every reduction that does delta-unfold it loops: simplify delta and trivial hit a stack overflow, and the conversion done by apply and hint-based solve seems to run until memory is exhausted.
This shows up in practice in ehoare.
call /(fun v => (1%r / 2%r) ** v) H never returns.
Its concave_incr side condition is discharged by t_solve over the concave_incr hints (t_concave_incr, src/phl/ecPhlConseq.ml).
** unfolds to if c%rp = 0%rp then ..., which with c = inv 2%r contains (inv 2%r)%rp.
Every hint application then tries to unify up to conversion, enters the cycle, and the process is eventually killed for lack of memory (here after about 6 minutes).
The t_try around the search never gets control back.
Reproduction
Smallest form, with stack overflow in about 2 s:
require import AllCore Xreal.
lemma x (c : realp) : Rp.inv c = 0%rp.
proof. simplify delta. admit. qed. (* anomaly: Stack overflow *)The same happens with (inv c)%rp = 0%rp for c : real, with (inv 2%r)%rp = 0%rp, and with trivial instead of simplify delta (there it hangs rather than overflowing).
Without Xreal, simplify delta on 0%r <= inv 2%r or inv 2%r = 0%r returns at once.
How it shows up in an ehoare proof (never returns):
require import AllCore Distr DBool Xreal.
module M = { proc coin() : bool = { var b; b <$ {0,1}; return b; } }.
lemma coin_e : ehoare [M.coin : (1%r / 2%r)%xr ==> res%xr].
proof. by proc; rnd; skip => &hr /=; rewrite Ep_dbool. qed.
module N = { proc f() : bool = { var b; b <@ M.coin(); return b; } }.
lemma t : ehoare [N.f : (1%r / 4%r)%xr ==> (1%r / 2%r) ** res%xr].
proof.
proc; call /(fun v => (1%r / 2%r) ** v) coin_e. (* never returns *)
admit.
qed.The general mechanism, without Xreal: a hint simplify rule that folds a term back into a definition makes delta-reduction loop, with no cycle detection:
require import AllCore.
op f : int -> int.
op g (x : int) = f x.
lemma fg x : f x = g x by [].
hint simplify fg.
lemma t : g 0 = 0.
proof. simplify delta. admit. qed. (* anomaly: Stack overflow; same with trivial *)How I narrowed it down
goal / tactic (with Xreal loaded) |
result |
|---|---|
call /(fun v => (inv 2%r)%xr * v) H |
fine, ~1.3 s |
call /(fun v => 2%r ** v) H, c ** v, xinv v |
search fails fast, side goal left open |
call /(fun v => (1%r/2%r) ** v) H, (inv 2%r) ** v, 0.5 ** v, (inv c) ** v |
never returns |
solve 1 (concave_incr) on concave_incr (fun v => (inv 2%r) ** v) |
hangs already at depth 1 (solve 2 succeeds at once for 2%r ** v) |
apply concave_incr_X for each of the 7 hints, and trivial, on that goal |
each one hangs |
trivial on (inv 2%r) ** v = v |
hangs |
simplify delta on (inv 2%r)%rp = 0%rp, Rp.inv c = 0%rp |
anomaly: Stack overflow |
simplify / cbv / rewrite /Rp.inv on the same goals |
fine |
So the search depth is not the issue: a single conversion step does not terminate.
Suggested fixes
- In
Xreal.ec, don't useof_realIas a simplification hint, or orient it so it doesn't undo the definition ofRp.inv. The same check may be worth doing for otherhint simplifylemmas there that restate operator definitions (to_realD,to_realM,to_realI,smulrp, ...). - Add a
concave_incrhint for**, e.g.
lemma concave_incr_smul c f : concave_incr f => concave_incr (fun x => c ** f x).
so thatcall /(fun v => c ** v)works directly. - More generally: detect, or bound, cycles between
hint simplifyrules and delta-unfolding. That would turn an "anomaly: Stack overflow", or an unbounded allocation insidet_try, into an ordinary failure.
Workaround
Write the scaling as an xreal product: call /(fun v => c%xr * v) H.
Activity
[-]`call /(fun v => inv c ** v) H` in ehoare never returns (memory bug)[/-][+]Xreal: `hint simplify of_realI` makes delta-reduction of `Rp.inv` / `(inv x)%rp` loop (stack overflow)[/+]oskgo commentedon Nov 9, 2026
Can this be fixed by making
invopaque? It seems to me like the issue here is that the definition is being unfolded.fdupress commentedon Nov 9, 2026
There is a simplification rule for addition that simplifies
1+1into2. Say you further prove a lemmafoo: 2 = 1 + 1(perhaps byrefl).If you then add
hint simplify foo, you should expect looping. And we should not try to detect whether adding a particular rule to user-defined reduction will cause a loop. (We are trying to decide enough undecidable problems as it is.) If this is an instance of that, then this is not an EasyCrypt bug.One thing we could do: when extending the
simplifydatabase, print out a reminder that this could lead to looping, and perhaps add a list of all lemmas already in the DB (perhaps filtered by symbols that appear in the new rule) and definitions for the symbols that appear in the rule?JoaoDiogoDuarte commentedon Nov 9, 2026
I think that be nice, especially because in:
there is no user facing
delta, which makes this confusing.fdupress commentedon Nov 9, 2026
Wait wait. Ok. The issue is that
Xrealadds the loopy hint, not you. This indeed seems ill-advised. (I had missed that because I only read about 1/10 of that long report. Would be helpful to put more work into extracting the marrow from your bones of contention for us :))@bgregoire any thoughts about what the right fix here should/could be?
JoaoDiogoDuarte commentedon Nov 9, 2026
Next time I'll be more concise ;)
oskgo commentedon Nov 10, 2026
Making
invopaque indeed fixes it.Removing
[opaque]in the following example makes it break.I think that's likely the right fix here. It allows us to keep both simplification hints, which are not loopy by themselves.