runtimeverification / runtimeverification/haskell-backend

Lemma with an `ensures` clause is not being applied

Open
#3,669 8 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Haskell
Stars
224
Forks
43
PR merge metrics
No merged PRs in 30d

Description

We are using the following lemma:

rule [keccak-eq-conc-false]: keccak(A)  ==Int B => false
    ensures #notEq(keccak(A), B, "keccak-eq-conc-false") [symbolic(A), concrete(B), simplification, comm]

The idea is that sometimes we want to assume that the keccak of a symbolic expression will not collide with a pre-existing concrete value, but we are using the ensures clause to record this assumption in the configuration (with a new #notEq symbol) so we can check afterwards that the cases where this lemma is applied are sound.

However, we have the following claim:

claim [lookup-keccak]:
    <k> runLemma ( #lookup ( STORAGE:Map [ 1 <- 2 ] , keccak ( X ) ) )
    => doneLemma ( #lookup ( STORAGE:Map , keccak ( X ) ) ) ... </k>

It should be passing by the lemma above and this lemma about #lookup, but it fails with the lemma as it is. However, if we remove the ensures clause, it passes.

I'm attaching a keccak-lemmas.k file with the lemma and claim above. The behavior should be reproducible using kprove. It's worth noting that this claim is based on a proof that we were running with the booster, where this subexpression was also not being simplified.

keccak-lemmas.k.txt

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the attached keccak-lemmas.k.txt and reproduce the lookup-keccak claim using kprove. Compare the behavior with and without the ensures clause, then inspect the referenced #lookup lemma in kevm-pyk/kproj/evm-semantics/lemmas/lemmas.k. Done means the claim passes while the ensures clause records the #notEq assumption.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.