argotorg / argotorg/act

Integers & Bitvectors in Act and bytecode verifying backends

Open
#53 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Haskell
Stars
279
Forks
51
Avg merge
17h 42m
Merged PRs (30d)
1

Description

Every arithmetic expression in an act `Behaviour` is a true integer expression, and can therefore never overflow or underflow.
This makes it easier to express and prove interesting, higher level properties and in mosts cases for developers to accurately capture intended meaning of smart contracts.

However, since the EVM is always dealing with words instead of integers, there are currently two problems arising from this discrepancy:

1. There are things expressible in act that cannot be implemented in the EVM. If we specify that a storage location changes:
```
x => x + a
```
the RHS of the rewrite can be larger than 2^256 and for it to be at all possible for a contract to realize this spec we must further assume `x + a`. It would be reasonable to add a stage to the act compiler which checks if an overflow is possible for every subexpression in a behaviour, and warn the user if that is the case. Expressions that are topmost terms on the left hand side of a `mod` should be exempt from this check.

2. Since the current hevm symbolic implementation deals with bitvectors instead of integers, all act claims have to be translated into bitvectors, which turns out to be quite detrimental for proving any [spec containing safemath](https://github.com/ethereum/act/blob/master/Makefile#L32).

The bottleneck here is in the integer - bitvector conversion in the smt solver. A fairly trivial looking claim like this:
```
(declare-fun a () (_ BitVec 256))
(declare-fun b () (_ BitVec 256))
(define-fun max () Int 115792089237316195423570985008687907853269984665640564039457584007913129639935)
(define-fun aNat () Int (bv2nat a))
(define-fun bNat () Int (bv2nat b))

(assert (< (+ aNat bNat) max))

(assert (not (= (bvadd a b) ((_ int2bv 256) (+ aNat bNat)))))

(check-sat)
```
is too difficult for z3 and cvc4 to resolve in a reasonable timeframe.

It appears that the only solution right now to make the hevm backend act compatible is to implement to follow KEVM's suit and implement the EVM logic in terms of integers modulo 2^256 instead of bitvectors of size 256.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the safemath claim referenced in Makefile#L32 and trace how the hevm symbolic backend translates integer expressions into bitvectors. Compare the proposed modulo-2^256 integer semantics with KEVM's approach, then define the overflow-checking boundary and backend behavior; done means the specified cases are representable and the safemath claim proves in reasonable time.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.