This post was first published on Medium.
Implement Groth16 in sCrypt
Recently, we have implemented zk-SNARKs in sCrypt and run it on Bitcoin. More specifically, we have implemented the verifier of the Groth16 algorithm, which allows a zero-knowledge proof to be verified directly on chain. This article dives into some of the details, shedding light on how to efficiently implement other advanced cryptographic techniques on Bitcoin.
Bilinear pairings on elliptic curves
Groth16 enjoys extremely small proof size and fast verification. Pairing is the most expensive part of the Groth16 verifier algorithm. We have chosen the optimal Ate pairing, since its efficiency has been demonstrated in practice.
We implement it over the pairing-friendly elliptic curve BN256 (also known as ALT_BN128 and BN254). We use BN256 since it is 1) supported by popular ZKP tools like ZoKrates and Circom; 2) compatible with other blockchains such as Ethereum.
Miller’s algorithm is used to efficiently compute the optimal Ate pairing. At a high level, it consists of two parts:
- Miller loop: compute an intermediate function of the two input points f(P, Q) recursively
- Final exponentiation: raise f to a large power c
Reduce to 3 pairings
The verifier needs to check if the following equation holds.
We have 4 pairings in total. We notice that α and β are known at setup, so we precompute the second pairing and add it as part of the verification key, saving one pairing.
One single final exponentiation
Eq. 1 can be rewritten as:
It in turn can be written as the following, since e is bilinear and we can move the exponent (-1) into the bracket.
Plugging in Eq. 2, we get:
Instead of calculating final exponentiation 4 times, which are computationally intensive, we only have to do it once in the end.
Loop unrolling
In sCrypt/Script, all if branches are included in a transaction and incur transaction fees, regardless of whether they are executed later or not. In the miller loop, sᵢ is known at compile time. We unroll the loop and avoid branching at Line 5 and 7.
Extension field twist
Computing pairing of two points directly requires elliptic curve arithmetic over extension field Fq¹², which is immensely complicated and inefficient. We use a twist to map it to Fq², drastically improving the efficiency. Please refer to this article for more detailed explanation.
Summary
After all these optimizations, we are able to cut the Script size of pairing by 100X to 5MB. We are exploring more optimizations to reduce it further. The full version of the code can be found on GitHub.
Traditionally, the objective of optimizing a program is to minimize its CPU and/or memory usage. In Bitcoin where transaction fee is proportional to the size of a transaction containing the Script, the objective is minimize script size. How to optimize against this objective is an interesting open topic worthy of novel research.
Watch: The BSV Global Blockchain Convention presentation, Smart Contracts and Computation on BSV
width=”560″ height=”315″ frameborder=”0″ allowfullscreen=”allowfullscreen”>
New to Bitcoin? Check out CoinGeek’s Bitcoin for Beginners section, the ultimate resource guide to learn more about Bitcoin—as originally envisioned by Satoshi Nakamoto—and blockchain.
