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.
`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 address0x05
, and performsb^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)
, withx1
,y1
,x2
, andy2
as 256 bit field elements, such that(x1, y1)
and(x2, y2)
are valid points on the curvebn256
, which has equationy^2 = x^3 + 3 mod fieldOrder
. The inputs here are simplyx1, y1, x2, y2
.bn256ScalarMul
lives at0x07
, and performsk * (x, y)
, fork
in a group with the order of the curve, and(x, y)
a valid curve point as above. The inputs here arex, y, k
.bn256Pairing
lives at0x08
. This takes as input arbitrarily many pairs of elliptic curve points, and performs the pairing checke(g1, g2) = e(-h1, h2)
, withg1
andh1
fromG1
, andg2
andh2
fromG2
.
- Points fromG1
have the form(x, y)
, as we have seen above;
- points fromG2
have the form(ai + b, ci + d)
, anda, b, c, d
(in that order — imaginary, real, imaginary, real) need to be supplied in the precompile call. Thebn256Pairing
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 tobn256ScalarMul
; - 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!