Bilinear Pairings on Bitcoin
Pairing-based cryptography is a variant of elliptic curve cryptography, which Bitcoin ECDSA signatures are based on. Thanks to the characteristics of pairing, new cryptographic algorithms and protocols can achieve functions or efficiency which cannot be realized otherwise, such as identity-based encryption (IBE), attribute-based encryption (ABE), authenticated key exchange (AKE), and short signatures.
Several applications of Pairing-based cryptography have been in practical use in many blockchains.
- Zcash implements a zero-knowledge proof algorithm named zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)
- Ethereum supports pairing check to perform zkSNARK verification
- DFINITY (now called The Internet Computer) constructed a BLS signature-based scheme, shorter than ECDSA signatures.
We demonstrate pairings can be implemented directly on Bitcoin and thus enable all kinds of pairing-based cryptography applications previously thought impossible on Bitcoin.
Bilinear pairings
A pairing e is simply a function that takes two inputs¹ and returns one output as below.
A bilinear pairing has the following property:
That is, it is linear in each of its inputs separately. It is easy to see the following holds.
Intuitively, one can swap the scalar n between its inputs and take it out as an exponent.
A Toy Example
Let us look at the following pairing function.
It is bilinear because it satisfies the two equations above. For instance,
Bilinear pairings on elliptic curves
In practice, the pairing above is not secure for cryptographic use. Instead, we use pairings over elliptic curves. The inputs are points on an elliptic curve and the output is a number². There are multiple ways to construct pairings over elliptic curves, such as Weil, Tate, and Ate pairings.
Miller’s Algorithm
Miller’s algorithm is used to efficiently compute pairings. It consists of two parts:
- main loop: Line 3 to 10. It is structurally akin to the double-and-add algorithm when calculating scalar point multiplication.
- final exponentiation at Line 11.
p, k, and r are parameters of the elliptic curve used³.
Implementation
We have implemented the Miller’s algorithm to compute Tate pairings below, based on our elliptic curve arithmetic library.
linefunc(P, Q, R) is a line function that passes through P and Q and is evaluated at R.
[1] Thus the name pairing.
[2] Strictly speaking, it is an element in a multiplicative group. Since this serves as an introduction on pairings, we choose readability over mathematical rigor throughout the article.
[3] Not all elliptic curves can be used for pairings. Only ones where pairings are efficiently computable are used in practice. They are called pairing-friendly curves, of which Barreto-Naehrig (BN) or Boneh–Lynn–Shacham (BLS) curves are notable examples.
