Skip to content

Xreal: hint simplify of_realI makes delta-reduction of Rp.inv / (inv x)%rp loop (stack overflow) #1230

Open

Description

@JoaoDiogoDuarte

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 (in Rp): delta-unfolding Rp.inv c gives (inv c%r)%rp;
  • hint simplify of_realI, with of_realI : (inv x)%rp = inv x%rp: this turns that back into Rp.inv (c%r%rp);
  • hint simplify to_realK_simpl (x%r%rp = x): this gives back Rp.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 use of_realI as a simplification hint, or orient it so it doesn't undo the definition of Rp.inv. The same check may be worth doing for other hint simplify lemmas there that restate operator definitions (to_realD, to_realM, to_realI, smulrp, ...).
  • Add a concave_incr hint for **, e.g.
    lemma concave_incr_smul c f : concave_incr f => concave_incr (fun x => c ** f x).
    so that call /(fun v => c ** v) works directly.
  • More generally: detect, or bound, cycles between hint simplify rules and delta-unfolding. That would turn an "anomaly: Stack overflow", or an unbounded allocation inside t_try, into an ordinary failure.

Workaround

Write the scaling as an xreal product: call /(fun v => c%xr * v) H.

Activity

  1. changed the title [-]`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)[/+] on Nov 9, 2026
  2. oskgo commented on Nov 9, 2026

    @oskgo
    Contributor

    Can this be fixed by making inv opaque? It seems to me like the issue here is that the definition is being unfolded.

  3. fdupress commented on Nov 9, 2026

    @fdupress
    Member

    There is a simplification rule for addition that simplifies 1+1 into 2. Say you further prove a lemma foo: 2 = 1 + 1 (perhaps by refl).

    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 simplify database, 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?

  4. JoaoDiogoDuarte commented on Nov 9, 2026

    @JoaoDiogoDuarte
    Author

    One thing we could do: when extending the simplify database, 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?

    I think that be nice, especially because in:

    require import AllCore Xreal.
    
    lemma x (c : realp) : Rp.inv c = 0%rp.
    proof. simplify delta. admit. qed.     (* anomaly: Stack overflow *)

    there is no user facing delta, which makes this confusing.

  5. fdupress commented on Nov 9, 2026

    @fdupress
    Member

    Wait wait. Ok. The issue is that Xreal adds 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?

  6. JoaoDiogoDuarte commented on Nov 9, 2026

    @JoaoDiogoDuarte
    Author

    Next time I'll be more concise ;)

  7. oskgo commented on Nov 10, 2026

    @oskgo
    Contributor

    Making inv opaque indeed fixes it.

    Removing [opaque] in the following example makes it break.

    type t.
    type u.
    
    op inv: u -> u.
    op f: t -> u.
    op g: u -> t.
    
    op [opaque] inv' (x: t): t = g (inv (f x)).
    
    axiom a1 x: g (inv x) = inv' (g x).
    axiom a2 x: g (f x) = x.
    
    hint simplify a1, a2.
    
    lemma L x : inv' x = g witness.
    proof. simplify delta. abort.
    

    I think that's likely the right fix here. It allows us to keep both simplification hints, which are not loopy by themselves.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions