BLS Signature for Busy People

BLS_Signature.md

BLS Signature for Busy People

bls12-381 is pairing-friendly Barreto-Lynn-Scott elliptic curve construction allowing to:

• Construct zk-SNARKs at the ~120-bit security, as per Barbulescu-Duquesne 2017
• Efficiently verify N aggregate signatures with 1 pairing and N ec additions: the Boneh-Lynn-Shacham signature scheme is orders of magnitude more efficient than Schnorr

BLS can mean 2 different things:

• Barreto-Lynn-Scott: BLS12, a Pairing Friendly Elliptic Curve
• Boneh-Lynn-Shacham: A Signature Scheme.

Summary

1. BLS Relies on expensive bilinear pairing
2. Private Keys: 32 bytes
3. Public Keys: 48 OR 96 bytes - big-endian x coordinate of point on G1 OR G2 curve
4. Signatures: 96 OR 48 bytes - big-endian x coordinate of point on G2 OR G1 curve
5. The 12 stands for the Embedding degree.

Modes of operation:

• Long signatures: 48-byte keys + 96-byte sigs (G1 keys + G2 sigs).
• Short signatures: 96-byte keys + 48-byte sigs (G2 keys + G1 sigs).

Formulas

• P = pk x G - public keys
• S = pk x H(m) - signing, uses hash-to-curve on m
• e(P, H(m)) == e(G, S) - verification using pairings
• e(G, S) = e(G, SUM(n)(Si)) = MUL(n)(e(G, Si)) - signature aggregation

Curves

G1 is ordinary elliptic curve. G2 is extension field curve, think "over complex numbers".

• G1: y² = x³ + 4
• G2: y² = x³ + 4(u + 1) where u = √−1; r-order subgroup of E'(Fp²), M-type twist

Towers

Pairing G1 + G2 produces element in Fp₁₂, 12-degree polynomial. Fp₁₂ is usually implemented using tower of lower-degree polynomials for speed.

• Fp₁₂ = Fp₆² => Fp₂³
• Fp(u) / (u² - β) where β = -1
• Fp₂(v) / (v³ - ξ) where ξ = u + 1
• Fp₆(w) / (w² - γ) where γ = v
• Fp²[u] = Fp/u²+1
• Fp⁶[v] = Fp²/v³-1-u
• Fp¹²[w] = Fp⁶/w²-v

Further Reading

Standards / Specs

• BLS signatures draft
  • https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-04
• Pairing-friendly curves draft
  • https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-pairing-friendly-curves-11
• Ethereum 2.0 Spec for BLS signature verification
  • https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#bls-signatures
• Sean Bowe - New zk-SNARK curve (2017.03.11)
  • https://electriccoin.co/blog/new-snark-curve/

Papers

• Boneh, Lynn, Shacham - Short signatures from the Weil pairing
• Boneh, Drijvers, Neven - Compact Multi-Signatures for Smaller Blockchains
• Ben Lynn - On the Implementation of Pairing-Based Cryptosystems
• Boneh, Gentry, Lynn, Shacham - Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
• Craig Costello - Pairing for Beginners
• Victor S. Miller - Short Programs for functions on Curves
• Michael Naehrig - Constructive and Computational Aspects of Cryptographic Pairings
• Barreto, Naehrig - Pairing-Friendly Elliptic Curves of Prime Order

Articles / Posts

• Ben Edgington - BLS12-381 For The Rest Of Us
• Justin Drake - Proposal in Ethereum Research to use BLS Signature
• ORBS - Threshold Cryptography and Distributed Key Generation
• Yonezawa, Saito, Kobayashi - Pairing-Friendly Curves
• Vitalik Buterin - Exploring Elliptic Curve Pairings

Implementations

• Javascript - noble-curves: https://github.com/paulmillr/noble-curves
  • The summary gist was copied from the source code
• Java https://github.com/PegaSysEng/artemis/tree/master/util/src/main/java/tech/pegasys/artemis/util/bls
• Rust https://github.com/lovesh/signature-schemes
• Go https://github.com/kilic/bls12-381, https://github.com/phoreproject/bls
• C++ https://github.com/skalenetwork/libBLS
• NIM https://github.com/mratsim/constantine

Notes

Thanks to @benjaminion.

Thanks, updated.