Sometimes also called bilinear mappings, bilinear parings allow us to take three numbers, a, b, and c, where ab = c, encrypt them to become E(a), E(b), E(c), where E is an encryption function, then send the two encrypted values to a verifier who can verify E(a)E(b) = E(c) but not know the original values. We can use bilinear pairings to prove that a 3rd number is the product of the first two without knowing the first two original numbers.
We will explain bilinear pairings at a high level and provide some examples in Python.
Prerequisites
The reader should know what point addition and scalar multiplication are in the context of elliptic curves.
The reader should also know the discrete logarithm problem in this context: a scalar multiplied by a point will result in another point, and it is infeasible in general to calculate the scalar given the elliptic curve point.
The reader should know what a finite field and cyclic group are, and what a generator is in the context of elliptic curves. We will refer to generators with the variable G.
The reader should know about Ethereum Precompiles.
We will use capital letters to denote EC (elliptic curve) points and lower case letters to denote elements of finite fields. When we say element, this could be an integer in a finite field or it could be a point on an elliptic curve. The context will make it clear.
It is possible to read this tutorial without fully understanding all of the above, but it will be harder to build a good intuition about this subject.
Authorship
RareSkills researcher Michael Amadi (LinkedIn, Twitter) coauthored this article and Jesse Raymond (LinkedIn, Twitter) contributed many helpful suggestions to make this article more understandable.
How the numbers are encrypted
When a scalar is multiplied by a point on an elliptic curve, another elliptic curve point is produced. That is P = pG where p is a scalar, and G is the generator. Given P and G we cannot determine p.
Assume pq = r. What we are trying to do is take P = pG, Q = qG, and R = rG and convince a verifier that the “preimages” of P and Q multiply to produce the preimage of R.
If p*q = r, and P = pG, Q = qG, and R = rG, then we want a function such that
f(P,Q)=Rand not equal to R when p*q ≠ r. This should be true of all possible combinations of p, q, and r in the group.
However, this is typically not how we express R when using bilinear pairings. For reasons we will discuss later, it’s usually computed as
f(P,Q) = f(R,G)G is the generator point, and can be thought of as “1.” In this context. For example, pG means we did (G + G + … + G) p times. G just means we took G and didn’t add anything. So in a sense, this is the same as saying P x Q = R x 1.
So our bilinear pairing is a special function that if you plug in elliptic curve points into the arguments in the manner above, you can easily determine if p * q = r without knowing p, q, or r (because they’ve been turned into elliptic curve points via G).
The feature of bilinear pairings that we care about is as follows:
f(aG,bG) = f(abG,G) = f(G,abG)The essential property of bilinear pairings is that if you plug in two points that are multiples of the generator point (aG and bG), the result is equal to plugging in the product of those two numbers times the generator point (abG) and the generator point itself (G).
In the literature, what we are calling f, is usually written as e in the following manner:
e: G × G → GᴛThe subscript T means it is the “target group.”
To respect the literature, we will write the above as
e(aG,bG) = e(abG, G) = e(G, abG)The distinction here is that a bilinear pairing is a “mapping” whereas we have been referring to it as a function. The distinction between a mapping and a function does not matter in our use-case as they both have the same behavior in the context we are using them.
Symmetric and Asymmetric Groups
The above notation implies that we are using the same generator and elliptic curve group everywhere when we say
e(aG, bG) = e(abG, G)In practice however, it turns out to be easier to create bilinear pairings when a different group is different for both of the arguments and the output result.
Specifically, we say
e(a, b) → c, a ∈ G, b ∈ G′, c ∈ G′′None of the groups used are the same.
However, the property we care about still holds.
e(aG, bG′) = e(abG, G′) = e(G, abG′)In the above equation, the group G’’ is not explicitly shown but that is the codomain (output space) of e(G, G’).
One could think of G, G’, and G’’ being different elliptic curve equations, possibly modulo different primes, and that would be valid because those are different groups.
In a symmetric pairing, the same group is used for both the arguments of the bilinear pairing function. This means that the generator and elliptic curve group used in both arguments is the same. In this case, the pairing function is often denoted as:
e(aG, bG) = e(abG, G) = e(G, abG)In an asymmetric pairing, the arguments use different groups. For example, the first argument can use a different generator and elliptic curve group than the second argument. The pairing function can still satisfy the desired properties
e(aG, bG′) = e(abG, G′) = e(G, abG′)In practice we use asymmetric groups, and the difference between the groups we use is explained in the next section.
Field Extensions
Bilinear pairings are rather agnostic to the kinds of groups you opt for, but Ethereum’s bilinear pairing of choice uses elliptic curves with field extensions. If you want to be able to read Solidity code that uses zk-snarks, you’ll at least need a rough idea of what these are.
We usually think of EC points as two points x and y. With field extensions, they consist of several (x, y) pairs. This is analogous to how complex numbers “extend” real numbers.
A field extension is a very abstract concept, and frankly, the relationship between a field and its extension doesn’t matter from a purely functional concept.
Just think of it this way:
Although these are higher dimensional, they still have the properties of of cyclic groups that you care about
closed under addition, which is associative
has an identity element
each element has an inverse
the group has a generator
You don’t have to worry about how these field extensions are constructed or how to do math in them, they are also cyclic groups that follow the same rules of the groups you are familiar with. We can add “higher dimensional elliptic curve points” associatively just like we would with regular elliptic curve points, and they do all the same other stuff.
What is the point of this?
The bilinearity property is hard to come by.
The chances that
e(aG, bG′) = e(abG, G′) = e(G,abG′)is true for three random groups is very slim.
Using groups of different “dimensions,” plus some other features which are far more complex than we want to get into here, make this property easier to construct.
Remember, this is a cyclic group. You don’t care what bizzare moon-math object you are “multiplying” by. You just care that it follows the properties of cyclic groups. Then you can leave the under-the-hood details to a library, which we will discuss next.
So don’t let the name “field extension” scare you. All that matters to us is that we will be dealing with elliptic curve points that have more dimensions than our typical (x, y) point on the curve.
Specifically, in the next section we will be dealing with three groups: G1, G2, and G12. These correspond to the dimensions of these groups.
Bilinear Pairings in python
Enough theory, let’s code this. Install the py_ecc library as follows.
python -m pip install py_eccNow let’s import the functions that we need from this
from py_ecc.bn128 import G1, G2, pairing, add, multiply, eq
print(G1)
# (1, 2)
print(G2)
# ((10857046999023057135944570762232829481370756359578518086990519993285655852781, 11559732032986387107991004021392285783925812861821192530917403151452391805634), (8495653923123431417604973247489272438418190587263600148770280649306958101930, 4082367875863433681332203403145435568316851327593401208105741076214120093531))G1 and G2 are the generator points for their respective groups. As you can see from the code above, G1 points have an (x, y), that is, they are the elliptic curve points we are used to. Members of G2 consist of a pair of points.
Even though G2 points might seem a little strange, their behavior is the same as other cyclic groups, especially the G1 group we are familiar with. This means we can construct other points with scalar multiplication (which is really repeated addition) as expected
print(eq(add(G1, G1), multiply(G1, 2)))
# True
print(eq(add(G2, G2), multiply(G2, 2)))
# TrueIt should be obvious that you can only add elements from the same group.
add(G1, G2) # TypeErrorBy the way, this library overrides some arithmetic operators (you can do that in python), meaning you can do the following:
print(G1 + G1 + G1 == G1*3)
# True
# The above is the same as this:
eq(add(add(G1, G1), G1), multiply(G1, 3))
Now let’s get to the good part, the pairing
A = multiply(G2, 5)
B = multiply(G1, 6)
print(pairing(A, B))
# (2737733771970589720147436295258995541017562764748775046990018238171083065584, 7355949162177082646197064865377481127039528955264110892670278171102027012957, 1389120597320745437757553030085914762401499323567753964656133081964131780715, 4070774491543958907062047566637569178763974576144707726129772744684275725184, 10823414137019623021013733227099721415368303324105358213304652659949682568395, 12697986880222911287030392175914090722292212037466224705879408804162602333706, 17697943997237703208660786428217562403504798830995307420075922564993565300645, 2702065915136914071855531840006964465333491722231468583849464437921405019853, 6762652910450025398171695126080749677225757293012137750262928324249233167133, 9495821522287762858490254871883860235240788822777455638443279749602676973720, 17813117134675140440034537765301248350834713246854720915775731738875700896539, 21027635025043266481235488683404016989778194881701554135606154029160033599034)That’s a very long and ugly output: it is a member of a group that has 12 dimensions, which we call G12. Thankfully, we never have to see it if we do the following:
A = multiply(G2, 5)
B = multiply(G1, 6)
C = multiply(G2, 5 * 6)
pairing(A, B) == pairing(C, G1)
# TrueWe’ve accomplished our verification of multiplication while hiding the inputs! (For technical reasons, this is not true zero knowledge, but that is outside the scope of this article).
Note that the pairing implementation requires you to use the G2 point as the first argument and the G1 point as the second argument. This is not a mathematical requirement, just an implementation detail in the library. The following would also be valid
A = multiply(G2, 5)
B = multiply(G1, 6)
C = multiply(G1, 5 * 6) # C is now a G1 point
pairing(A, B) == pairing(G2, C)
# TrueNote that the library has a strange glitch in it when using the shortcut arithmetic notation in combination with a pairing
pairing(G2 * 5, G1 * 6) == pairing(G2 * 30, G1)
# TypeError, seems to be a library bugSo if we want to be mathematical about this, our bn128 pairing does the following
e: G1 × G2 → G12Bilinear Pairings in Ethereum
EIP 197 Specification
The py_ecc library is actually maintained by the Ethereum Foundation, and as you can guess, it is what powers the precompile at address 0x8 in the PyEVM implementation.
The Ethereum Precompile defined in EIP 197 works on points in G1 and G2, and implicitly works on points in G12.
The specification of this precompile will seem a little weird at first. It takes in a list of G1 and G2 points laid out as follows:
A₁B₁A₂B₂...AₙBₙ : Aᵢ ∈ G1, Bᵢ ∈ G2These were originally created as
A₁ = a₁G1
B₁ = b₁G2
A₂ = a₂G1
B₂ = b₂G2
...
Aₙ = aₙG1
Bₙ = bₙG2The precompile returns 1 if the following is true
a₁b₁ + a₂b₂ + ... + aₙbₙ = 0and zero otherwise.
This might be a bit of a head-scratcher at first! This seems to imply that the precompile is taking the discrete log of each of the points, which is accepted to be infeasible in general. Furthermore, why doesn’t it behave like pairing from the earlier python examples?
Justification for EIP 197 design decision
The first problem with simply adding a wrapper around
e: G1 × G2 → G12is that G12 points are huge, and this will take up a lot of space in memory leading to larger gas costs. Also, because of how most zk verification algorithms work (this is outside the scope of this article), we generally don’t check the value of the output of a pairing, but only that it is equal to other pairings. Specifically, the final step in Groth16 (the zero knowledge algorithm used by tornado cash) looks like the following
e(A₁, B₂) = e(α₁, β₂) + e(L₁, γ₂) + e(C₁, δ₂)Where each variable is an elliptic curve point of either G1 or G2 based on it’s subscript notation (we would have used upper-case Greek letters to stay consistent with our notation, but those look too similar to the Latin alphabet).
The meanings of these variables is not important at this stage. The fact that it can be written as the sum of “products” (elliptic curve pairing) is what matters. Specifically, we can write it as
0 = e(−A₁, B₂) + e(α₁, β₂) + e(L₁, γ₂) + e(C₁, δ₂)And now it matches the precompile specification perfectly!
It’s not just groth16, most zk algorithm have verification formula that looks like that, which is why the precompile was designed to work with sums of pairings rather than return the value of a single pairing.
If we look at the verification code of tornado cash, we can see it is exactly implementing this (even the greek letters match, but don’t worry if you don’t understand it yet). The beta2 simply means it is a G2 point, alpha1 means G1 point, etc.
Inside the pairing function is where the call to address(8) is done to complete the pairing calculation and determine if the proof if valid or not.
Sum of preimages
The key insight here is that if
ab + cd = 0Then it must also be true that
A₁B₂ + C₁D₂ = 0₁₂ A₁,C₁ ∈ G1, B₂,D₂ ∈ G2in G12 space.
The precompile isn’t actually computing the discrete logarithm, it’s simply checking if the sum of pairings is zero.
The sum of pairings is zero if and only if the sum of the products of the discrete logarithms is zero.
End to End Solidity Example
Let us take these inputs of a, b, c and d.
a = 4
b = 3
c = 6
d = 2
-ab + cd = 0putting it into the formula we can get
A₁B₂ + C₁D₂ = e(−aG1, bG2) + e(cG1, dG2) = 0In python this will equate to
from py_ecc.bn128 import neg, multiply, G1, G2
a = 4
b = 3
c = 6
d = 2
# negate G1 * a to make the equation sum up to 0
print(neg(multiply(G1, a)))
#(3010198690406615200373504922352659861758983907867017329644089018310584441462, 17861058253836152797273815394432013122766662423622084931972383889279925210507)
print(multiply(G2, b))
# ((2725019753478801796453339367788033689375851816420509565303521482350756874229, 7273165102799931111715871471550377909735733521218303035754523677688038059653), (2512659008974376214222774206987427162027254181373325676825515531566330959255, 957874124722006818841961785324909313781880061366718538693995380805373202866))
print(multiply(G1, c))
# (4503322228978077916651710446042370109107355802721800704639343137502100212473, 6132642251294427119375180147349983541569387941788025780665104001559216576968)
print(multiply(G2, d))
# ((18029695676650738226693292988307914797657423701064905010927197838374790804409, 14583779054894525174450323658765874724019480979794335525732096752006891875705), (2140229616977736810657479771656733941598412651537078903776637920509952744750, 11474861747383700316476719153975578001603231366361248090558603872215261634898))Here’s the output in a strutured format
aG1_x = 3010198690406615200373504922352659861758983907867017329644089018310584441462,
aG1_y = 17861058253836152797273815394432013122766662423622084931972383889279925210507,
bG2_x1 = 2725019753478801796453339367788033689375851816420509565303521482350756874229,
bG2_x2 = 7273165102799931111715871471550377909735733521218303035754523677688038059653,
bG2_y1 = 2512659008974376214222774206987427162027254181373325676825515531566330959255,
bG2_y2 = 957874124722006818841961785324909313781880061366718538693995380805373202866,
cG1_x = 4503322228978077916651710446042370109107355802721800704639343137502100212473,
cG1_y = 6132642251294427119375180147349983541569387941788025780665104001559216576968,
dG2_x1 = 18029695676650738226693292988307914797657423701064905010927197838374790804409,
dG2_x2 = 14583779054894525174450323658765874724019480979794335525732096752006891875705,
dG2_y1 = 2140229616977736810657479771656733941598412651537078903776637920509952744750,
dG2_y2 = 11474861747383700316476719153975578001603231366361248090558603872215261634898Now we have the values encrypted into points on G1 and G2 groups, someone else or a program can confirm that we computed A1B2+C1D2=0 correctly without knowing the individual values of a, b, c, or d. Here’s a solidity contract that uses the ecPairing precompile to confirm that we computed the equations with valid values.
We create a file Pairings.sol to unit test in foundry (we will supply the test file next)
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.13;
contract Pairings {
/**
* returns true if == 0,
* returns false if != 0,
* reverts with "Wrong pairing" if invalid pairing
*/
function run(uint256[12] memory input) public view returns (bool) {
assembly {
let success := staticcall(gas(), 0x08, input, 0x0180, input, 0x20)
if success {
return(input, 0x20)
}
}
revert("Wrong pairing");
}
}
We use this foundry test file to deploy and call our Pairings contract to confirm our ecPairing calculation. The following file we call TestPairings.sol.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.13;
import "forge-std/Test.sol";
import "../src/Pairings.sol";
contract PairingsTest is Test {
Pairings public pairings;
function setUp() public {
pairings = new Pairings();
}
function testPairings() public view {
uint256 aG1_x = 3010198690406615200373504922352659861758983907867017329644089018310584441462;
uint256 aG1_y = 17861058253836152797273815394432013122766662423622084931972383889279925210507;
uint256 bG2_x1 = 2725019753478801796453339367788033689375851816420509565303521482350756874229;
uint256 bG2_x2 = 7273165102799931111715871471550377909735733521218303035754523677688038059653;
uint256 bG2_y1 = 2512659008974376214222774206987427162027254181373325676825515531566330959255;
uint256 bG2_y2 = 957874124722006818841961785324909313781880061366718538693995380805373202866;
uint256 cG1_x = 4503322228978077916651710446042370109107355802721800704639343137502100212473;
uint256 cG1_y = 6132642251294427119375180147349983541569387941788025780665104001559216576968;
uint256 dG2_x1 = 18029695676650738226693292988307914797657423701064905010927197838374790804409;
uint256 dG2_x2 = 14583779054894525174450323658765874724019480979794335525732096752006891875705;
uint256 dG2_y1 = 2140229616977736810657479771656733941598412651537078903776637920509952744750;
uint256 dG2_y2 = 11474861747383700316476719153975578001603231366361248090558603872215261634898;
uint256[12] memory points = [
aG1_x,
aG1_y,
bG2_x2,
bG2_x1,
bG2_y2,
bG2_y1,
cG1_x,
cG1_y,
dG2_x2,
dG2_x1,
dG2_y2,
dG2_y1
];
bool x = pairings.run(points);
console2.log("result:", x);
}
}
This passes and prints out true to the console. Notice that the points have been labeled by their variable name, which group they belong to, and if they represent an x or a y of the elliptic curve point.
Its important to note that the ecPairing precompile does not expect or require an array and that our choice of using one with inline-assembly is simply optional. One could do the same with solidity like so;
function run(bytes calldata input) public view returns (bool) {
// optional, the precompile checks this too and reverts (with no error) if false, this helps narrow down possible errors
if (input.length % 192 != 0) revert("Points must be a multiple of 6");
(bool success, bytes memory data) = address(0x08).staticcall(input);
if (success) return abi.decode(data, (bool));
revert("Wrong pairing");
}
And update the test file like so;
function testPairings() public view {
uint256 aG1_x = 3010198690406615200373504922352659861758983907867017329644089018310584441462;
uint256 aG1_y = 17861058253836152797273815394432013122766662423622084931972383889279925210507;
uint256 bG2_x1 = 2725019753478801796453339367788033689375851816420509565303521482350756874229;
uint256 bG2_x2 = 7273165102799931111715871471550377909735733521218303035754523677688038059653;
uint256 bG2_y1 = 2512659008974376214222774206987427162027254181373325676825515531566330959255;
uint256 bG2_y2 = 957874124722006818841961785324909313781880061366718538693995380805373202866;
uint256 cG1_x = 4503322228978077916651710446042370109107355802721800704639343137502100212473;
uint256 cG1_y = 6132642251294427119375180147349983541569387941788025780665104001559216576968;
uint256 dG2_x1 = 18029695676650738226693292988307914797657423701064905010927197838374790804409;
uint256 dG2_x2 = 14583779054894525174450323658765874724019480979794335525732096752006891875705;
uint256 dG2_y1 = 2140229616977736810657479771656733941598412651537078903776637920509952744750;
uint256 dG2_y2 = 11474861747383700316476719153975578001603231366361248090558603872215261634898;
bytes memory points = abi.encode(
aG1_x,
aG1_y,
bG2_x2,
bG2_x1,
bG2_y2,
bG2_y1,
cG1_x,
cG1_y,
dG2_x2,
dG2_x1,
dG2_y2,
dG2_y1
);
bool x = pairings.run(points);
console2.log("result:", x);
}
This will pass and return true just like the initial implementation because it sends the exact same calldata to the precompile.
The only difference is that in the first implementation, the test file sends an array of points to the pairing contract which uses inline-assembly to slice off the first 32 bytes (array length) and sends the rest to the precompile. And in the second implementation, the test file sends the abi encoded points to the pairing contract which forwards it as it is to the precompile.
Learn More from RareSkills
This material is taken from our Zero Knowledge Course. Please see the program to learn more.