This article first appeared on Medium.
Pairing-based cryptography is a variant of elliptic curve cryptography, on which Bitcoin ECDSA signatures are based. Thanks to the characteristics of pairing, new cryptographic algorithms and protocols can achieve functions or efficiency that cannot be achieved 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 used in practice in many blockchains.
- Zcash implements a zero-knowledge proof algorithm named zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)
- Ethereum supports pairing verification to perform zkSNARK verification
- DFINITY (now called The Internet Computer) built a scheme based on the BLS signature, which is shorter than ECDSA signatures.
We demonstrate that pairings can be implemented directly on Bitcoin and thus enable all sorts of pairing-based cryptography applications previously considered impossible on Bitcoin.
Bilinear pairings
A pairing e is simply a function that takes two inputs¹ and returns an output like below.
Twinning
A bilinear matching has the following property:
That is, it is linear in each of its inputs separately. It is easy to see the following takes.
Intuitively, we can permute the scalar not between its inputs and output it as an exponent.
An example of a toy
Consider the following matching 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 on elliptical curves. The inputs are points on an elliptic curve and the output is a number². There are several ways to construct pairings on elliptic curves, such as Weil, Tate, and Ate pairings.
Miller’s algorithm
Miller’s algorithm is used to efficiently calculate pairings. It consists of two parts:
- main loop: Lines 3 to 10. It is structurally similar to the double-addition algorithm when calculating the multiplication of scalar points.
- final exponentiation at line 11.
pack, and r are parameters of the elliptic curve used³.
Miller’s algorithm to compute the Tate matching e(P, Q)
Implementation
We have implemented Miller’s algorithm to compute Tate pairings below, based on our elliptic curve arithmetic library.
Implementing Tate e(P, Q) pairing
rowfunction(P, Q, R) is a linear function that passes through P and Q and is evaluated in R.
***
REMARKS:
[1] So the name twinning.
[2] In the strict sense, it is an element of a multiplicative group. Since this serves as an introduction to pairings, we favor readability over mathematical rigor throughout the article.
[3] Not all elliptical curves can be used for pairings. Only those where the pairings are efficiently computable are used in practice. These are called favorable matching curves, of which the Barreto-Naehrig (BN) or Boneh–Lynn–Shacham (BLS) curves are notable examples.
Watch: Keynote speech by Dr. Craig Wright: Cloud Security, Overlays & Blockchain at the BSV Global Blockchain Convention
New to Bitcoin? Discover CoinGeek bitcoin for beginners section, the ultimate resource guide to learn more about Bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.