{{ message }}

Instantly share code, notes, and snippets.

# hermanjunge/BLS_Signature.md

Last active Sep 6, 2020
BLS Signature for Busy People

# BLS Signature for Busy People

## Summary

• BLS stands for

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

• It is possible to verify `n` aggregate signatures on the same message with just `2` pairings instead of `n+1`.
• Secure enclaves to provide the following APIs

• Private Key generation
• Public Key computation (`pk X G`)
• Where `pk` is the private key, `X` is the group multiplication, and `G` is the generator.
• `Sign(pk, message)`
• BLS Relies on Bilinear Pairing

• Expensive. Now, given that we are signing the same message, this scheme requires only 2 pairings per validation.
• Sizes

• Private Keys: 32 Bytes.
• Public Keys: 48 Bytes.
• Signatures: 96 Bytes.

## Discussion

### BLS12-381 facts

• BLS12-381 is not a single curve, but a family of curves instantiated over different field extensions.
• The 12 stands for the Embedding degree.
• The 381 means that the prime in the finite field `F_p` is of 381 bits, i.e. 2^381 points.

### Sizes

#### Private Keys: 32 Bytes.

• The private key is just a scalar that your raise curve points to the power of. The subgroup order for G1 and G2 is `r~2^255`, so for private keys higher than this the point just wraps around. Therefore, useful private keys are `<2^255` and fit into 32 bytes.
• Recall that `r` is defined here: https://electriccoin.co/blog/new-snark-curve/

### Bilinear pairings

A relative expensive calculation that satisfies the following properties.

``````e(P, Q + R) = e(P,Q) x e(P,R)
e(P + S, Q) = e(P,Q) x e(S,Q)
``````

`P`, `Q` and `R` to be points within the elliptic curve. Operations `+` and `x` can be arbitrary operators.

It follows that we can say from these properties that

``````e(aP, Q) =

e(P + P + ... + P, Q) = e(P,Q) x ... x e(P,Q)

e(aP,Q) = e(P,Q) ^ a = e(P, aQ)

or

e(SUM(n)(Pi), Q) = MUL(n)(e(Pi, Q))
``````

### Signature and Verification

• Signature
``````S = pk x H(m)
``````

That's all. One group multiplication.

• Verification

People will have `P = pk x G`, they can verify the signature by comparing the following pairings:

``````e(P, H(m)) = e(G,S)
``````

This works, due to the fact that

``````e(P, H(m)) = e(pk x G, H(m))
= e(G, pk x H(m))
= e(G, S)
``````

### Signature Aggregation

If we have `S = SUM(n)(Si)`, then

``````e(G, S) = e(G, SUM(n)(Si)) = MUL(n)(e(G, Si))
``````

Now, remember that `e(G, S) = e(P, H(m))`, so

``````MUL(n)(e(G, Si)) = MUL(n)(e(Pi, H(mi)))
``````

### Standards / Specs

• BLS Standard Draft
• Ethereum 2.0 Spec for BLS signature verification
• Sean Bowe - New zk-SNARK curve (2017.03.11)

### 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

• BLS, Java Implementation
• BLS, Rust Implementation
• BLS, Go language Implementations
• BLS, Javascript Implementation
• BLS, C++ Implementation

## Notes

• Thanks a lot to @benjaminion !!!

### gakonst commented Dec 2, 2019

 May want to add: Short description on rogue key attacks Fast constant time hash to curve https://eprint.iacr.org/2019/403 `6 pairings + (n+logn)` exponentiations vs `n+1` pairings for `n` distinct messages, https://eprint.iacr.org/2019/1177.pdf

### 0xAshish commented Dec 17, 2019 • edited

 Few more resources to add For rouge key attacks: https://eprint.iacr.org/2007/264.pdf

### ace0 commented Apr 27, 2020

 Excellent, compact write-up. Using `pk` as designator for secret key is confusing because it looks like shorthand for public key. Recommend changing `pk` to `sk` or `k`.

### turon commented Jul 11, 2020

 You may want to include the configuration option optimized for signature size: Public Keys: 96 Bytes. Signatures: 48 Bytes.

### alex-miller-0 commented Jul 19, 2020

 Is anyone aware of a C implementation (or plans of anyone to write one)?

### goldenMetteyya commented Aug 4, 2020

 Is anyone aware of a C implementation (or plans of anyone to write one)? https://github.com/supranational/blst