Elliptic Curve Pairings: The Mathematics Behind zk-SNARKs

Elliptic Curve Pairings: The Mathematics Behind zk-SNARKs

Elliptic curve pairings, also known as bilinear maps, are mathematical functions that take two elliptic curve points as input and output an element in a third group. Pairings enable cryptographic operations that are impossible with standard elliptic curves alone, including short BLS signatures, identity-based encryption, and zero-knowledge proofs like zk-SNARKs. The bilinear property allows checking linear relationships between points without revealing the underlying secrets.

To understand elliptic curve pairings properly, it helps to be familiar with elliptic curve cryptography, finite fields, and zk-SNARKs.

┌─────────────────────────────────────────────────────────────────────────┐
│                      Elliptic Curve Pairings                              │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Bilinear Map: e: G1 × G2 → GT                                         │
│                                                                          │
│   Properties:                                                            │
│   • Bilinear: e(g^a, h^b) = e(g, h)^(ab)                               │
│   • Non-degenerate: e(g, h) ≠ 1                                         │
│   • Computable: Efficient algorithm exists                              │
│                                                                          │
│   ┌─────────────────────────────────────────────────────────────────┐   │
│   │                         BLS Signature                            │   │
│   │                                                                  │   │
│   │  Sign: σ = H(m)^sk               Verify: e(σ, g) ?= e(H(m), pk) │   │
│   │                                                                  │   │
│   │  1 signature = 1 group element (32-48 bytes)                     │   │
│   │  Batch verification: one pairing for many signatures            │   │
│   └─────────────────────────────────────────────────────────────────┘   │
│                                                                          │
│   ┌─────────────────────────────────────────────────────────────────┐   │
│   │                      zk-SNARKs (Groths16)                        │   │
│   │                                                                  │   │
│   │  Pairings check polynomial equality: e(A, B) ?= e(α, β)         │   │
│   │  Enables constant-size proofs (~200 bytes)                       │   │
│   └─────────────────────────────────────────────────────────────────┘   │
│                                                                          │
│   Popular Pairing-Friendly Curves: BLS12-381, BN254, BLS12-377          │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Are Elliptic Curve Pairings?

An elliptic curve pairing is a bilinear map e: G1 × G2 → GT, where G1, G2, and GT are cyclic groups of the same prime order r. The map satisfies bilinearity: for all a, b and for generators g in G1, h in G2, we have e(g^a, h^b) = e(g, h)^(ab). Pairings are also non-degenerate (e(g, h) ≠ 1) and efficiently computable. They provide a way to multiply encrypted values together in a way that reveals the product of the exponents.

• Bilinearity: e(g^a, h^b) = e(g, h)^(ab). This is the fundamental property that enables advanced cryptography.
• Non-degeneracy: e(g, h) ≠ 1, meaning the map is not trivial.
• Computability: There exists an efficient algorithm (Miller's algorithm) to compute pairings.
• Symmetry: Some curves have G1 = G2 (symmetric pairings), others have distinct groups (asymmetric pairings).
• Examples: BLS12-381 (used in Ethereum 2.0, Zcash), BN254 (used in early zk-SNARKs), BLS12-377.

Why Elliptic Curve Pairings Matter

Pairings enable cryptographic primitives that are impossible with standard elliptic curve groups alone. They are the foundation of modern advanced cryptography.

• BLS Signatures (Short Signatures): Single group element signature (32-48 bytes). Batch verification: verify many signatures with one pairing operation. Public key aggregation: combine multiple signatures into one. Used in Ethereum 2.0 for consensus.
• zk-SNARKs (Groth16, PLONK): Pairings check polynomial equality: e(A, B) = e(α, β). Enable constant-size proofs (~200 bytes). Efficient verification (milliseconds). Foundation of privacy (Zcash) and scaling (zk-rollups).
• Identity-Based Encryption (IBE): Encrypt using recipient's identity (email address) as public key. No certificate authority needed. Private key generated by trusted key server.
• Short (BLS) Aggregate Signatures: Combine many signatures into one (constant size). Useful for blockchains (vote aggregation, consensus). Reduces storage and verification cost.
• Pairing-Based Cryptography: Tripartite Diffie-Hellman (three parties can agree on shared key). Attribute-based encryption (fine-grained access control). Searchable encryption.

Application                 Key Property                     Use Case
─────────────────────────────────────────────────────────────────────────────
BLS Signatures              e(σ, g) ?= e(H(m), pk)           Ethereum 2.0
zk-SNARKs (Groth16)         e(A, B) ?= e(α, β)               Zcash, zkSync
BLS Aggregate               One signature = many signatures  Blockchain consensus
Identity-Based Encryption   Encrypt to email address         Secure email
Tripartite DH               Three-party key agreement        Group messaging

The Bilinear Pairing Property

Basic property:
e(g^a, g^b) = e(g, g)^(ab)

This enables checking equality of exponents without revealing them:

Given g^a, g^b, g^c, can verify a × b = c:
  e(g^a, g^b) ?= e(g, g^c)

Because:
  Left:   e(g^a, g^b) = e(g, g)^(ab)
  Right:  e(g, g^c)   = e(g, g)^c

Requires ab = c for equality

Example: Proving you know x such that g^x = h (without revealing x)
  e(g^x, g) ?= e(h, g)  // Always true, leaks nothing

Pairing-Friendly Elliptic Curves

Curve       G1 size   G2 size   Pairing Cost   Use Case
─────────────────────────────────────────────────────────────────────────────
BN254       32 bytes  64 bytes  Moderate       Legacy zk-SNARKs
BLS12-381   48 bytes  96 bytes  Fast           Current standard
BLS12-377   48 bytes  96 bytes  Fast           Recursion
BW6-761     96 bytes  192 bytes Slow           Nested proofs

BLS12-381 is the current industry standard (Ethereum, Zcash, Filecoin)
Security: BLS12-381 ≈ AES-128 (128-bit security)

BLS Signatures

BLS (Boneh-Lynn-Shacham) signatures are a pairing-based signature scheme with unique properties. The signature is a single elliptic curve point (32-48 bytes). Batch verification allows verifying many signatures with one pairing operation. Signatures can be aggregated into a single signature. Used extensively in Ethereum 2.0 for consensus and for BFT protocols.

• Key Generation: sk ∈ Fr (random), pk = g^sk ∈ G2 (or G1).
• Sign: σ = H(m)^sk ∈ G1 (or G2).
• Verify: e(σ, g) ?= e(H(m), pk).
• Aggregation: σ_agg = ∏ σ_i, pk_agg = ∏ pk_i.
• Batch Verification: e(∏ σ_i, g) ?= ∏ e(H(m_i), pk_i).

Property                    BLS                         ECDSA
─────────────────────────────────────────────────────────────────────────────
Signature Size              48 bytes                    64 bytes (DER)
Batch Verification          O(1) pairings for N sigs    O(N) operations
Signature Aggregation       Yes (N into 1)              No
Deterministic?              Deterministic (hash-to-curve) Randomized (k)
Threshold signatures        Native (via aggregation)    Complex (Feldman)
Key generation              Fast                        Fast

Ethereum 2.0 uses BLS12-381 signatures for consensus
- 16384 validators aggregate into 1 signature per epoch

Pairings in zk-SNARKs (Groth16)

zk-SNARKs use pairings to verify polynomial equality in constant time. The prover constructs group elements A, B, C from the witness and circuit. The verification equation uses pairings to check correctness.

Given:   Prover sends A, B, C ∈ G1
         Verification key has α, β, γ, δ, etc.

Check:   e(A, B) = e(α, β) + e(x, γ) + e(C, δ)

Where x depends on public inputs and verification key

Intuition:
  Pairings allow checking linear relationships between group elements
  Without pairings, verifier would need to recompute the whole computation
  Pairings reduce verification to constant time (milliseconds)

Reference: Groth16 is proof system used in Zcash and early rollups

Pairings Anti-Patterns

• Using Deprecated Curves (BN254): BN254 provides only ~100-bit security (too low). Use BLS12-381 for current security standards. BN254 still used in legacy systems but not recommended for new protocols.
• Implementing Pairings from Scratch: Extremely complex (Miller's algorithm, final exponentiation). Tiny implementation errors cause security vulnerabilities. Use audited libraries (libff, arkworks, MCL, relic).
• Ignoring Subgroup Attacks: Small subgroup attacks can break pairing security. Validate that points are in correct subgroup. Use cofactor multiplication or subgroup checks.
• Misusing Pairings for Key Agreement: Not all curve pairings are designed for Diffie-Hellman. Use standard protocols (BLS, Boneh-Franklin IBE). Consult cryptographic literature for correct usage.
• Assuming All Pairings Are Symmetric: G1 and G2 have different element sizes. Cannot swap G1 and G2 in verification equations. Know which group is which for your protocol.

✓ Use BLS12-381 (not BN254) for new projects
✓ Use audited pairing libraries (arkworks, libff, MCL)
✓ Validate subgroup membership (points in correct group)
✓ Distinguish G1 and G2 (different element sizes)
✓ Use hash-to-curve for BLS signatures (not simple map)
✓ Test edge cases (point at infinity, zero exponents)

Pairing Best Practices

• Use BLS12-381 for New Projects: Industry standard with 128-bit security. Supported in nearly all pairing libraries. Used in Ethereum 2.0, Zcash Sapling, Filecoin, and many zk-rollups.
• Use Well-Audited Libraries: arkworks (Rust), libff (C++), relic (C), MCL (C++), noble (JavaScript) for pairing operations. Avoid custom implementation of Miller's algorithm.
• Validate Subgroup Membership: Always check points are in correct subgroup (use library validation). Multiply by cofactor for subgroup checks. Prevent small subgroup attacks.
• Use Appropriate Hash-to-Curve Method: BLS signatures require deterministic hash to curve (not simple map). Use suite from IETF RFC 9380. Avoid using map-to-group without domain separation.
• Optimize Batch Verification: Use random exponentiations to combine pairings (small random weights w_i). Reduces verification cost from O(N) pairings to O(1) pairings (2 pairings per batch). Use multi-exponentiation for summations.

Standard verification (N signatures):
  For each signature i:
    e(σ_i, g) = e(H(m_i), pk_i)   // O(N) pairings

Batch verification:
  1. Choose random weights r_i ∈ [1, 2^64]
  2. Compute σ_agg = ∏ σ_i^{r_i}
  3. Compute product over i: ∏ e(H(m_i), pk_i)^{r_i}
  4. Check e(σ_agg, g) = product         // O(1) pairings

Cost reduction: 2 pairings vs N pairings
Security: batch verifies all signatures (probability of false positive negligible)

Popular Pairing Libraries

Frequently Asked Questions

1. What is the difference between symmetric and asymmetric pairings?
   Symmetric pairings have G1 = G2 (same group). Asymmetric have G1 ≠ G2. Most modern curves (BLS12 family) are asymmetric. Asymmetric pairings offer better security and performance for most applications.
2. Are pairings quantum-safe?
   No. Elliptic curve pairings rely on discrete log hardness, which is broken by Shor's algorithm on sufficiently large quantum computers. Pairings are not quantum-resistant. Post-quantum zero-knowledge proofs (zk-STARKs) do not use pairings.
3. Why are BLS12-381 pairings preferred over BN254?
   BN254 provides only ~100-bit security (too low for modern standards). BLS12-381 provides ~128-bit security (same as AES-128). BLS12-381 also has faster pairing computation. BN254 still used in legacy applications, but BLS12-381 is standard for new ones.
4. What is hash-to-curve and why is it important?
   BLS signatures need to hash messages to elliptic curve points (not just numbers). Simple map to point can be insecure. IETF RFC 9380 defines secure hash-to-curve using random oracle. Uses SHA-256 or SHA-384, deterministic, constant-time.
5. Can pairings be used for encryption?
   Yes. Identity-Based Encryption (Boneh-Franklin) uses pairings. Public key can be arbitrary string (email address). Trusted key server generates private key. Not widely deployed due to key escrow requirement.
6. What should I learn next after elliptic curve pairings?
   After mastering elliptic curve pairings, explore zk-SNARKs (Groth16, PLONK), BLS signatures for Ethereum 2.0, aggregate and threshold signatures, identity-based encryption (IBE), and pairing-friendly curve design.