Skip to content
Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
92 lines (62 sloc) 5.32 KB

Title

ECIP: 1026
Title: Modexp Precompiled Contract
Author: Wei Tang <hi@that.world>
Status: Draft
Type: Consensus (hard-fork)
Created: 2017/06/28

Rationale

This allows for efficient RSA verification inside of the EVM, as well as other forms of number theory-based cryptography. Note that adding precompiles for addition and subtraction is not required, as the in-EVM algorithm is efficient enough, and multiplication can be done through this precompile via a * b = ((a + b)**2 - (a - b)**2) / 4.

The bit-based exponent calculation is done specifically to fairly charge for the often-used exponents of 2 (for multiplication) and 3 and 65537 (for RSA verification).

Specification

Parameters

  • GQUADDIVISOR: 100

Algorithm

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

<length_of_BASE> <length_of_EXPONENT> <length_of_MODULUS> <BASE> <EXPONENT> <MODULUS>

Where every length is a 32-byte left-padded integer representing the number of bytes to be taken up by the next value. Call data is assumed to be infinitely right-padded with zero bytes, and excess data is ignored. Consumes floor(max(length_of_MODULUS, length_of_BASE) ** 2 * max(ADJUSTED_EXPONENT_LENGTH, 1) / GQUADDIVISOR) gas, and if there is enough gas, returns an output (BASE**EXPONENT) % MODULUS as a byte array with the same length as the modulus.

ADJUSTED_EXPONENT_LENGTH is defined as follows.

  • If length_of_EXPONENT <= 32, and all bits in EXPONENT are 0, return 0
  • If length_of_EXPONENT <= 32, then return the index of the highest bit in EXPONENT (eg. 1 -> 0, 2 -> 1, 3 -> 1, 255 -> 7, 256 -> 8).
  • If length_of_EXPONENT > 32, then return 8 * (length_of_EXPONENT - 32) plus the index of the highest bit in the first 32 bytes of EXPONENT (eg. if EXPONENT = \x00\x00\x01\x00.....\x00, with one hundred bytes, then the result is 8 * (100 - 32) + 253 = 797). If all of the first 32 bytes of EXPONENT are zero, return exactly 8 * (length_of_EXPONENT - 32).

For example, the input data:

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000020
0000000000000000000000000000000000000000000000000000000000000020
03
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

Represents the exponent 3**(2**256 - 2**32 - 978) % (2**256 - 2**32 - 977). By Fermat's little theorem, this equals 1, so the result is:

0000000000000000000000000000000000000000000000000000000000000001

Returned as 32 bytes because the modulus length was 32 bytes. The ADJUSTED_EXPONENT_LENGTH would be 255, and the gas cost would be 32**2 * 255 / 100 = 2611 gas (note that this is ~five thirds of the cost of using the EXP opcode to compute a 32-byte exponent). A 4096-bit RSA exponentiation would cost 512**2 * 4095 / 100 = 10734796 gas in the worst case, though RSA verification in practice usually uses an exponent of 3 or 65537, which would reduce the gas consumption to 2621 or 41943, respectively.

This input data:

0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000020
0000000000000000000000000000000000000000000000000000000000000020
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

Would be parsed as a base of 0, exponent of 2**256 - 2**32 - 978 and modulus of 2**256 - 2**32 - 978, and so would return 0. Notice how if the length_of_BASE is 0, then it does not interpret any data as the base, instead immediately interpreting the next 32 bytes as length_of_EXPONENT.

This input data:

0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000020
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd

Would parse a base length of 0, a modulus length of 32, and an exponent length of 2**256 - 1, where the base is empty, the modulus is 2**256 - 2 and the exponent is (2**256 - 3) * 256**(2**256 - 33) (yes, that's a really big number). It would then immediately fail, as it's not possible to provide enough gas to make that computation.

This input data:

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000002
0000000000000000000000000000000000000000000000000000000000000020
03
ffff
8000000000000000000000000000000000000000000000000000000000000000
07

Would parse as a base of 3, an exponent of 65535, and a modulus of 2**255, and it would ignore the remaining 0x07 byte.

This input data:

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000002
0000000000000000000000000000000000000000000000000000000000000020
03
ffff
80

Would also parse as a base of 3, an exponent of 65535 and a modulus of 2**255, as it attempts to grab 32 bytes for the modulus starting from 0x80, but then there is no further data so it right pads it with 31 zeroes.

You can’t perform that action at this time.