precompiles & solidity

Edit: updated for 2019!

Ethereum’s October 15th 2017 hardfork introduced some cryptography precompiles, so now you can do more fancy privacy friendly things. However, it’s a bit tricky using precompiles if you don’t know how to call them, and get all of that low-gas-consuming goodness for yourself. So I’ll explain.

Fancy vim solidity syntax highlighting courtesy of https://github.com/tomlion/vim-solidity. Also note the ability to do `if` in inline assembly!

inline assembly? The evm? Precompiles? Solidity???

I’m going to assume you know what solidity looks like, and the general idea of ethereum. What we care about here is that ethereum has a distributed (replicated on every computer running a full node) virtual machine (the EVM), with an instruction set that anyone can choose to have executed and recorded on the blockchain, with state updated accordingly. A quick update on the things that are important here, if you’re a little rusty: storage means information is permanently stored in the blockchain state. memory is simply evm working memory, where variables are stored during computation. uint is an alias for uint256, which holds up to 256 bits, perfect for elliptic curve coordinates. public means that the function is publicly callable. view used to be constant , and tells the compiler that the code doesn’t change anything in storage. There’s also a keyword pure, that means the code doesn’t even view anything in storage.

precompiles

The precompile directory in ethereum’s Go client currently looks like this:

var PrecompiledContractsByzantium = map[common.Address]PrecompiledContract{     common.BytesToAddress([]byte{1}): &ecrecover{}, common.BytesToAddress([]byte{2}): &sha256hash{}, common.BytesToAddress([]byte{3}): &ripemd160hash{}, common.BytesToAddress([]byte{4}): &dataCopy{}, common.BytesToAddress([]byte{5}): &bigModExp{}, common.BytesToAddress([]byte{6}): &bn256Add{}, common.BytesToAddress([]byte{7}): &bn256ScalarMul{}, common.BytesToAddress([]byte{8}): &bn256Pairing{},
}

This is mapping precompiles (listed on the right) to the addresses at which the precompile resides. The new precompiles are the last four:

• bigModExp now resides at address 0x05, and performs b^e mod m, taking as input, in order:
  - length of the base;
  - length of the exponent;
  - length of the modulus;
  - the base itself (b above);
  - the exponent itself (e);
  - the modulus (m).
• bn256Add lives at0x06, and performs (x1, y1) + (x2, y2), with x1, y1, x2, and y2 as 256 bit field elements, such that (x1, y1) and (x2, y2) are valid points on the curve bn256, which has equation y^2 = x^3 + 3 mod fieldOrder. The inputs here are simply x1, y1, x2, y2.
• bn256ScalarMul lives at 0x07, and performs k * (x, y), for k in a group with the order of the curve, and (x, y) a valid curve point as above. The inputs here are x, y, k.
• bn256Pairing lives at 0x08. This takes as input arbitrarily many pairs of elliptic curve points, and performs the pairing check e(g1, g2) = e(-h1, h2), with g1 and h1 from G1, and g2 and h2 from G2.
  - Points from G1 have the form (x, y), as we have seen above;
  - points from G2 have the form (ai + b, ci + d), and a, b, c, d (in that order — imaginary, real, imaginary, real) need to be supplied in the precompile call. The bn256Pairing code first checks that a multiple of 6 elements have been sent, and then performs the pairings check(s).

The values x, y, a, b, c, d are all field elements, and so they are taken modulo the field size. The value k, as used in bn256ScalarMul, is modulo the elliptic curve group order.

We’re going to explore through two main examples, bn256ScalarMul and bigModExp. bn256ScalarMul operates very similarly to bn256Add, and bn256Pairing operates a little more like bigModExp, as they both take variable length inputs. This means the input size needs to be given to the function as a parameter alongside the actual function inputs you'd expect to be present. If you’re brave (or already understand solidity and are just looking for copy-pastey code), here is what the function for calling bn256ScalarMul looks like:

function ecmul(uint ax, uint ay, uint k) public view returns(uint[2] memory p) {
 uint[3] memory input;
 input[0] = ax;
 input[1] = ay;
 input[2] = k;

 assembly {
   if iszero(staticcall(gas, 0x07, input, 0x60, p, 0x40)) {
       revert(0,0)
   }
 }
 return p;
}

This snippet introduces precompile handling that wasn’t possible before the various hardforks of 2017. In particular, inline assembly now has support for if statements, and defining the amount of gas to be sent along with a call has been made simpler — calling with gas equal to gas, as we have here, will send all available gas to the function being called. This removes the need to guess or upper-bound the amount of gas being sent yourself.

The revert opcode reverts all state changes. It’s slotted in after calls to ensure that if we’ve run out of gas or experienced some other disaster while calling the precompile in question, all potentially partially complete state changes will be reverted.

the evm

persistent storage

The persistent memory associated with each address is called storage. This is a key-value store, mapping 256-bit words to 256-bit words. It cannot be enumerated from inside a contract, and contracts have no access or view of the storage associated with other addresses.

If you initialise variables as in uint256 blah;, this will save blah to storage. uint is an alias of uint256, and bytes can also be assigned on a more fine-grained level, using uint8, uint16, etc.

volatile memory

The EVM has a virtual stack with which to store 256 bit values. 256-bit words were chosen for compatibility with cryptographic operations. All EVM operations are performed using this virtual stack. The maximum number of elements the stack can contain is 1024. You can copy one of the top 16 elements, or swap the top element with one of the 16 below (meaning you can here access the 17th highest value on the stack). All other opcodes take the pre-determined number of elements from the top of the stack and then push the return value onto the stack.

Volatile memory is received as a freshly cleared instance for each message call. Memory is allocated in words, and gas is used to pay for the expansion of memory to hold the amount of words you’re storing. We need the values with which we want to call a precompile to be sat at the top of this memory.

We can assign variables previously stored in storage to memory in the following way:

uint256[2] memory inputToPrecompile;
input[0] = somePreviouslyStoredValue;
input[1] = someOtherPreviouslyStoredValue;

This is, in fact, exactly what we’re doing with the first four lines in ecmul. We are pushing the values ax, ay, and k to the top of the virtual stack. The precompile is then immediately called, by invoking the address where the code necessary to perform a bn256ScalarMul operation is sat. Looking at the next section of code, we see:

assembly {
   if iszero(staticcall(gas, 0x07, input, 0x60, p, 0x40)) {
       revert(0,0)
   }
 }

The staticcall opcode is called with the following:

staticcall(gasLimit, to, inputOffset, inputSize, outputOffset, outputSize)

We see then that, in the case of the bn256ScalarMul-calling code above, we are:

• Sending the amount of gas currently available to us, after subtracting 2000;
• Calling the contract at address 0x07, which the mapping at the top tells us corresponds to bn256ScalarMul;
• Defining the input offset as input, as we have just declared in memory;
• Declaring the input size as 0x60, corresponding to a value of three 256 bit words, exactly the size of an elliptic curve point and one 256 bit scalar;
• the output will be stored at value p; and
• the output size is 0x40, corresponding to the elliptic curve point that will be returned to us.

And that’s it! the return value of the function ecmul will now be the return value of the bn256ScalarMul precompile!

modexp

The code needed to call the bigModExp precompile is as follows:

function expmod(uint base, uint e, uint m) public view returns (uint o) {
  
  assembly {
   // define pointer
   let p := mload(0x40)
   // store data assembly-favouring ways
   mstore(p, 0x20)             // Length of Base
   mstore(add(p, 0x20), 0x20)  // Length of Exponent
   mstore(add(p, 0x40), 0x20)  // Length of Modulus
   mstore(add(p, 0x60), base)  // Base
   mstore(add(p, 0x80), e)     // Exponent
   mstore(add(p, 0xa0), m)     // Modulus
   if iszero(staticcall(sub(gas, 2000), 0x05, p, 0xc0, p, 0x20)) {
     revert(0, 0)
   }
   // data
   o := mload(p)
  }
}

The important thing to know here is that 0x40 is always free memory, and so pointers to memory can be initialised as let p := mload(0x40).

And that’s it! Now we can all check pairings and do giant exponentiations until our hearts are content!

Thanks to @chriseth for introducing me to new inline assembly abilities!