I have the rare privilege of being able to do research at work. Since my working life was half industry and half academy, I relish the opportunity to join both in the same day job. There is the drive and urgency of writing production code, but also the excitement and uncertainty of not knowing if something will work.
In many ways, research is like an adventure: you have a more or less defined goal, and possibly several ways to reach it. You go down one path, battle your obstacles or find clever ways to avoid them, until you reach an insurmountable wall. You go back, repeat and repeat again, until you quit or achieve your Grail.
For the last couple of months or so, my adventure has been ZK-SNARKs. It started as testing a technology to see if it was viable, and morphed to building an actual product with it. It has led me down many interesting paths, that in themselves would probably merit a post. Occasionally, I would find a little gem of knowledge under a rock. Other times, a bend in the road would plunge me unavoidably in the middle of a topic that I had skirted around for a long time and now had to look seriously in the face or explore into some depth.
This post is about one example of the first case. For the second case, I expect to write something about Elliptic Curve Pairings sometime in the future.
As I have recounted in a previous post, I’ve used ZoKrates to produce ZK-SNARKs. The end-to-end experience with ZoKrates goes from specifying a statement that we want to prove to someone else, to generating a verifier in Solidity for that statement. The magic underlying ZK-SNARKs is some heavy cryptography based on Elliptic Curve pairings. When you look at it carefully, it is pretty impressive that a smart contract can execute the necessary maths within the gas cost limits of an Ethereum transaction. So, what is the secret?
Ethereum pre-compiled contracts
The answer is in the contract verifier.sol that you get from ZoKrates. You can find the template here. I will not go into the details of these in this post, but basically they provide the ability to execute a bilinear pairing on an elliptic-curve. I know, that is a mouthful: it’s pretty hard-core cryptography, and as you’d expect it’s computationally heavy. Let’s look at the relevant method under the lens:
/// @return the result of computing the pairing check
/// e(p1[0], p2[0]) * .... * e(p1[n], p2[n]) == 1
/// For example pairing([P1(), P1().negate()], [P2(), P2()]) should
/// return true.
function pairing(G1Point[] p1, G2Point[] p2) internal returns (bool) {
require(p1.length == p2.length);
uint elements = p1.length;
uint inputSize = elements * 6;
uint[] memory input = new uint[](inputSize);
for (uint i = 0; i < elements; i++)
{
input[i * 6 + 0] = p1[i].X;
input[i * 6 + 1] = p1[i].Y;
input[i * 6 + 2] = p2[i].X[0];
input[i * 6 + 3] = p2[i].X[1];
input[i * 6 + 4] = p2[i].Y[0];
input[i * 6 + 5] = p2[i].Y[1];
}
uint[1] memory out;
emit LogDebug("P1.X", p1[0].X);
emit LogDebug("P1.Y", p1[0].Y);
emit LogDebug("P2.X0", p2[0].X[0]);
emit LogDebug("P2.X1", p2[0].X[1]);
emit LogDebug("P2.Y0", p2[0].Y[0]);
emit LogDebug("P2.Y1", p2[0].Y[1]);
bool success;
assembly {
success := call(sub(gas, 2000), 8, 0, add(input, 0x20), mul(inputSize, 0x20), out, 0x20)
// Use invalid to make gas estimation work
switch success case 0 { invalid() }
}
require(success);
return out[0] != 0;
}
Once you look at this carefully, this method is not doing anything really special. It receives two arrays of the same length, representing points in two elliptic curves. Each pair of points can be represented in the space of 6 256-bit words and so the function stores them in an array of the required size. It also allocates an array for the return of the method, which is a single word. And then we reach the highlighted part, a bit of assembly code that makes a function call. Can you see what it does?
This is what the documentation says about this function:
call(g, a, v, in, insize, out, outsize)
call contract at address a with input mem[in..(in+insize)) providing g gas and v wei and output area mem[out..(out+outsize)) returning 0 on error (eg. out of gas) and 1 on success
This makes a call to the address 8, without sending any Ether. The gas limit is reduced to account for the expenditure of the call itself and some other work, and the two arrays are passed in as input data and output buffer.
If you are familiar with Ethereum addresses, you’ll know these are normally random-looking 160-bit strings, so 8 is definitely not a normal address. What is more, this pattern is repeated twice more, with addresses 6 and 7.
Addresses 1 to 8 are indeed reserved, and correspond to the notion of a precompiled contract, as specified in the Ethereum yellow paper. Initially only 4, their number has been increased by Ethereum Improvement Proposals 198, 196 and 197 specifically to support some cryptographic operations.
What are precompiled contracts?
Let’s take a look at the Yellow Paper to learn a bit more about these contracts. I hesitate a little in recommending this, because the Yellow Paper seems to be, at many points, an exercise in obfuscation, clouding the concepts in heavy mathematical notation that distracts the reader and renders the concepts hard to keep in your mind. I can’t commend enough the Beige paper for the truly valuable work that it does. But nevertheless, this is where they’re first defined, so let’s take a look:
these are eight so-called ‘precompiled’ contracts, meant as a preliminary piece of architecture that may later become native extensions. The eight contracts in addresses 1 to 8 execute the elliptic curve public key recovery function, the SHA2 256-bit hash scheme, the RIPEMD 160-bit hash scheme, the identity function, arbitrary precision modular exponentiation, elliptic curve addition, elliptic curve scalar multiplication and an elliptic curve pairing check respectively.
Then there is a formal specifcation in Appendix E that does not add much more to their comprehension, and which I’ll ignore.
Aside from the identity function, all the other contracts perform cryptographic operations, which by their nature would be hard to implement using EVM bytecode. Remember that the EVM is the environment where ultimately every contract runs: the contract’s code is reduced to assembly-like opcodes, which are very basic minute operations, like moving data from stack to memory, or doing some arithmetic computation on a 256-bit word. Each opcode in a computation increases the gas cost, and so hard computations like these can become prohibitively expensive. For that reason, precompiled contracts are not executed inside the EVM.
Instead, they are executed by the Ethereum client and therefore implemented in a higher level language, like Rust or Javascript, in which the client has been written. These may even call low level optimized libraries. The advantage is that the execution is faster and the gas cost lower than running the same algorithm in the EVM.
The first four contracts above have been part of Ethereum, as far as I can tell, from the start. They enable the basic functions necessary for the construction of the blockchain itself: hashing and signature verification.
The other 4 contracts were released as part of the Byzantium fork in October 16th 2017. Contract EXPMOD, at address 5, was created to enable efficient RSA verification inside of the EVM, but that particular operation is widely prevalent in cryptography. The other 3 contracts were deliberately included to support SNARKs. These are:
BN_ADD: Adds two points on the elliptic curve ALT_BN_128BN_MUL: Multiplies a point on the same elliptic curve by a scalarSNARKV: Used to verify a Snark. This multiplies a series of pairings and checks that the result is 1, that is, that they cancel out.
As an example, currently, the Geth implementation looks like this. The dispatcher:
// PrecompiledContractsByzantium contains the default set of pre-compiled Ethereum
// contracts used in the Byzantium release.
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{},
}
And the pairing check (here and here):
// RequiredGas returns the gas required to execute the pre-compiled contract.
func (c *bn256Pairing) RequiredGas(input []byte) uint64 {
return params.Bn256PairingBaseGas + uint64(len(input)/192)*params.Bn256PairingPerPointGas
}
func (c *bn256Pairing) Run(input []byte) ([]byte, error) {
// Handle some corner cases cheaply
if len(input)%192 > 0 {
return nil, errBadPairingInput
}
// Convert the input into a set of coordinates
var (
cs []*bn256.G1
ts []*bn256.G2
)
for i := 0; i < len(input); i += 192 {
c, err := newCurvePoint(input[i : i+64])
if err != nil {
return nil, err
}
t, err := newTwistPoint(input[i+64 : i+192])
if err != nil {
return nil, err
}
cs = append(cs, c)
ts = append(ts, t)
}
// Execute the pairing checks and return the results
if bn256.PairingCheck(cs, ts) {
return true32Byte, nil
}
return false32Byte, nil
}
// PairingCheck calculates the Optimal Ate pairing for a set of points.
func PairingCheck(a []*G1, b []*G2) bool {
pool := new(bnPool)
acc := newGFp12(pool)
acc.SetOne()
for i := 0; i < len(a); i++ {
if a[i].p.IsInfinity() || b[i].p.IsInfinity() {
continue
}
acc.Mul(acc, miller(b[i].p, a[i].p, pool), pool)
}
ret := finalExponentiation(acc, pool)
acc.Put(pool)
return ret.IsOne()
}
When I look at the above, it feels like looking at a landscape hidden in fog. I can perceive what it does but I have to take it on faith. Even as a cryptographer, I approached elliptic curves as black boxes that give me some functionality, but I never had to dig into the details of how to compute operations on them (especially pairings). The majority of users will not need to understand this code in deep detail, but in the off case that you do, at least now you know where to search for it.
At any rate, this is the executive summary: the outer function merely packs the inputs in two lists, representing the points on the two source groups of the pairing. The inner function efficiently computes the product of all the pairings in a batch.
Conclusion
The aim of this post was to explain what precompiled contracts are, where they are implemented and how they are used to support SNARKs in Ethereum. I didn't cover any of the mathematics in this post, as that is subject enough for one or maybe more posts in the future. I hope the above has helped you in understanding the idea of precompiled contracts, and how you can make use of these capabilities if you need to use cryptography in your smart contracts.
Let me know what you think, if this kind of post is helpful to you, if you need more details or would prefer a lighter approach. You can write in the comments below, or drop me an email, and if you like this post, please hit the like button below and share it.
Thank you for reading, and see you in a future post.