Vyper: `uint256` exponentiation can overflow without error as long as the result is greater than the base

[smarx]

@public
@constant
def test(x: uint256, y: uint256) -> uint256:
    return x**y # BUG: test(10, 78) returns 73663286101470436611432119930496737173840122674875487684339327936694962880512

This issue is due to the following code:

https://github.com/ethereum/vyper/blob/c296b2d7532d913103aad494b749f8179a3acddc/vyper/parser/expr.py#L646-L658

[fubuloubu]

Could maybe do something like:
assert a < a**(b/2) < a**b (iff b is even, else a**((b-1)/2) for the middle term)

Would make it more difficult to find a falsifying example, but probably very hard to do a full-on correctness proof without a more complicated and inefficient check/calculation

[charles-cooper]

I thought about this for awhile and one approach is x**y / x**(y - 1) == x. This works so long as there isn't a z between 1 and y where x**z == 1.

Probably a better approach is to calculate the largest power that any number can be raised to without overflowing. For powers of 2 this is quite obvious, e.g. for x=2, check that y<256. For others, the equation is

x**y < 2**256
# log both sides
log2 (x**y) < log2(2**256)
# simplify
y * log2(x) < 256

There is probably some way of interpreting x as a floating point number which makes this super easy, but it's unclear that is any more gas efficient than just calculating exp as a series of muls.

[fubuloubu]

Working on it a bit more, came to this: x < (MAX_UINT256+1)**(1/y), iff y > 1. I wonder if there is a special case for the latter

[charles-cooper]

Working on it a bit more, came to this: x < (MAX_UINT256+1)**(1/y), iff y > 1. I wonder if there is a special case for the latter

well for y <= 1 it can never overflow

[fubuloubu]

y < 1 because y=1 is the overflow case itself lol. But that just simplifies to x being a uint256

EDIT: I added y > 1 so that y != 0, which would short-circuit x**y to just 1

[fubuloubu]

There are algorithms for computing n-th root of a (in base B). Still reading about it, but was thinking there might be a special case when B is 2 that's a binary search or something

[iamdefinitelyahuman]

What about the following approach? Imagine we're handling c = a ** b:

1. When one of a or b is a literal, we can calculate the upper bound of the non-literal value during compilation. This is an efficient solution for most use cases - I believe the most common exponentiations are a**2 and 10**b.
2. When both a and b are variables, internally handle the calculation with:

c = a
for i in range(b-1):
   assert c*a > c
   c *= a

1. If a and b are variables but a user still wants to use the EXP opcode, add a new method exp_mod2_256(a, b) that does not include any checks on the output.

[fubuloubu]

In the case either a or b are known, it should be easy to solve the equation a ** b < 2**256 in Python, obtaining the limit value for a succinct runtime assertion

[fubuloubu]

Another resource: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

[iamdefinitelyahuman]

Related to this, the current bounds checks raise on 1**2 or 0**[>=2]

[fubuloubu]

I'd like to tackle this in 0.2.0

Suggested solution:

1. Change the current a ** b operation to be the pow_mod256(a, b) function (delegating to the opcode, which performs the calculation modulo 2**256 aka allowing overflows)
2. Allow the a ** b operation to be used where either a or b is known (introducing the "safe" version where we can check for the limits of the opposing side) link
3. Introduce an algorithm that performs a "safe" version of the full operation (where both a and b are unknowns) that coverges to the result the opcode would provide link

I'd like to move this over to a VIP to cover the changes. :+1: if you agree.

[iamdefinitelyahuman]

A more efficient approach when both values are not literal - thanks @michwill!

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

[michwill]

In particular, probably exp_by_squaring_iterative is what's needed

[michwill]

It's probably ok if exponentiation for nonconstant a and b will be not via a builtin. And really - is there anyone who calculates a ** b with variables?
So, probably if it's a bit more gas-hungry, but SAFU - should be good given that it is very rarely used

[fubuloubu]

Took a hand at (3) using the link @michwill sent: https://github.com/fubuloubu/integer-exponential. Looks like it takes 10994 gas in the uint256 case, and 9575 gas in the int128 case (one less round required). The calls normally take 558 gas and 752 gas respectively (no idea why uint256 is cheaper here), so about a 10x-20x markup for this most general case