TIP-905 Add modular exponentiation opcode

[jaybutera]

TIP	905
Category	Consensus-breaking (9xx)
Author	Jay Butera jay@themelio.org

Summary

Adds an arithmetic modular exponentiation, modulo 2^256 opcode to melVM as bytecode 0x15.

Motivation

Currently there is not such an opcode. However it is very useful for cryptography applications, i.e. elliptic curves.

The computational complexity of modular exponentiation for our purposes can be expressed as O(k) where k is the bit-length of the exponent (see exponentiation by squaring).

To allow exponents to be determined algorithmically, the number shouldn't be part of the byte code itself. However because weights are statically computed there needs to be a way to price gas by the number of bits in an exponent.

Therefore, like with the loop opcode, the exp opcode will have a bound on the number of bits in the exponent without actually hardcoding the number itself in the bytecode.

Because integers are 256-bit in melvm, we use an 8-bit unsigned integer to represent k in bytecode. Because u8 values range from 0-255 we need a way to represent 256 bits. Since we don't need a lower-bound of 0, the actual bound will be k+1.

For instance, the opcodes for 2^3 is

[PushIM(3), PushIM(2), Exp(1)]

k=1 so the number of bits in the exponent 3, is 1+1=2.

In practice type systems of languages should help to infer the bit-bound on an exponent. For example in melodeon the following should be able to infer from the type e: {10} that the bit value for the exponent opcode is 4.

let e = 10 in
3 ** e

Proposed Changes

Introduce an opcode exp pops off the stack a base b and exponent e and takes as a bytecode parameter the number of bits in e - 1.

exp(k) = u256::pow(pop(), pop())

[jaybutera]

Code has been implemented here https://github.com/themeliolabs/themelio-stf/blob/0275c7745d9f155ad7ce938d6408797079456a32/src/melvm/executor.rs#L209

[nullchinchilla]

Nice, this seems really useful.

One question: does the covenant fail when the exponent has more than the given number of bits, or does it truncate it to that number of bits? Second one seems more "reasonable", but in any case it should be documented.

[jaybutera]

I have it failing if the exponent has more bits than specified. I can't really think of a use case for truncating since it would produce a completely different result than what would be expected from the code which is probably not good.

[nullchinchilla]

This has been merged.