Precompiles for bigint arithmetic

[vbuterin]

Parameters

• GADDSUBBASE: 15
• GMULDIVBASE: 30
• GMODEXPBASE: 45
• GARITHWORD: 6
• GQUADDIVISOR: 32
• METROPOLIS_FORK_BLKNUM: TBA

Specification

If block.number > METROPOLIS_FORK_BLKNUM, then:

At the address 0x0000....05, add a precompile that expects input in the following format:

<length of X, as a 32-byte-padded integer> <bytes of X> <bytes of Y>

This should then return the output:

<length of (X + Y), as a 32-byte-padded integer> <bytes of (X + Y)>

There are no leading zero bytes in the output; if X + Y = 0 it returns an empty array. An exception is thrown if the input data is shorter than the amount specified for X (eg. if the length of X is specified as 42 bytes but the total data size is 72 bytes so only 40 bytes for X are present). X and Y are interpreted as big endian integers; leading zero bytes in X or Y are allowed. Gas cost GADDSUBBASE + GARITHWORD * ceil(<total length of input data> / 32).

At the address 0x0000....06, add a precompile that works similarly, but returns X - Y in the same format. Throws if X < Y. Same gas cost as for addition above.

At the address 0x0000....07, add a precompile that works similarly, but returns X * Y in the same format. Gas cost GMULDIVBASE + GARITHWORD * ceil(<total length of input data> / 32) + <length of X> * <length of Y> / GQUADDIVISOR.

At the address 0x0000....08, add a precompile that works similarly, but returns floor(X / Y) in the same format. If Y = 0, returns zero (represented in the same format). Same gas cost as for multiplication above.

At the address 0x0000....09, add a precompile that expects input in the following format:

<length of B, as a 32-byte-padded integer> <bytes of B> <length of E, as a 32-byte-padded integer> <bytes of E> <bytes of M>

This should return B**E % M, and the data should be returned in the same format as above. If M = 0, it returns zero. Gas cost GMODEXPBASE + GARITHWORD * ceil(<total length of input data> / 32) + <length of M> * <length of M> * <length of E> / GQUADDIVISOR.

Examples

Call to 5:

0x 000000000000000000000000000000000000000000000000000000000000000d 0a5b3c4fe8aa7f5d68ec149e31 1791c60f6fed01

The first 32 bytes represent length 13, so the next 13 bytes are interpreted as X and the remaining 7 bytes are interpreted as Y. Returns 820517673944445067756173565489 + 6634204312890625 = 820517673944451701960486456114, ie. the bytes:

0x 000000000000000000000000000000000000000000000000000000000000000d 0a5b3c4fe8aa96ef2efb848b32

Call to 5:

0x 000000000000000000000000000000000000000000000000000000000000000d 65ad9912474aa649

Throws an exception, because it expects 13 bytes but only sees 8.

Call to 7:

0x 000000000000000000000000000000000000000000000000000000000000000 6fbc86c8fa94eaddc86e58a01bfccb1e339487614ce67d71a6cd

The first 32 bytes represent length 0, so the next zero bytes are interpreted as X (ie. X = 0), and te remaining bytes are interpreted as Y. Because anything times is zero is zero, this returns this:

0x 000000000000000000000000000000000000000000000000000000000000000

Call to 9:

0x 000000000000000000000000000000000000000000000000000000000000020 000000000000000000000000000000000000000000000000000000000000002 000000000000000000000000000000000000000000000000000000000000020 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff43 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff43

The first 32 bytes represent that the next 32 bytes represent B; these bytes specify B = 2 (note that there are leading zero bytes in this representation; this is ok). The 32 bytes after that represent that the next 32 bytes represent E; these bytes represent the prime number 2**256 - 189. Finally, the remaining bytes specify M, also equal to 2**256 - 189. By Fermat's little theorem, we know that 2**p % p = 2 if p is prime, so the result is 2. Hence, this returns thirty three bytes:

0x 000000000000000000000000000000000000000000000000000000000000001 02

Rationale

This allows for efficient bigint arithmetic, facilitating RSA verification as well as other forms of cryptography that require integers larger than 256 bytes. The gas costs are chosen to roughly maintain computational cost parity with other operations, and they also have the property that a single MODEXP where the base, modulus and exponent are 4096-bit values takes up slightly less than the maximum gas limit (it takes ~0.31s to compute in python); note that RSA can be designed in such a way that the exponent for signature verification is 3, and in this case, gas costs drop to ~10000.

[chriseth]

I think a justification why this problem should be solved using precompiles should be added here, including gas costs and runtime performance of the most efficient EVM assembly implementation.

One thing specifically to note about addition and subtraction: At least the Y value has to be copied around in memory at least once before the call to the precompile (probably both X, Y and the result will be copied around). If this is done using a loop, the loop itself should already take almost the same gas and runtime costs as an addition implemented in EVM assembly.

[gcolvin]

Why should these be precompiles and not instructions? Efficient bigint arithmetic generally requires coding fairly close to the metal - C and assembly tuned to the platform.

[axic]

Gas cost GMODEXPBASE + GARITHWORD * ceil(<total length of input data> / 32) + <length of M> * <length of M> * <length of E> / GQUADDIVISOR.

Should that read <length of B> * <length of M> * <length of E>?

Update: confirmed by @vbuterin that the original is correct.

[romanman]

@obscuren : I am curious to test bigint compatibility with go,
don't thinkn anybody ever tested 50bytes nums multiplication on
identity by all bits

[pirapira]

This is partially superseded by #198