owned this note
owned this note
Published
Linked with GitHub
# BLS Cheatsheet
[TOC]
## The Curve
[bls12_381]
BLS12-381: [Barreto-Lynn-Scott(2002)] curves with embedding degree of *12* with base field modulus $q \approx 2^{381}$ [^1]
```
k = 12
q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
E(Fq) := y^2 = x^3 + 4
E'(Fq2) := y^2 = x^3 + 4(i + 1)
```
The group $\Bbb G_1$ is a $r$ order subgroup of $E$. The group $\Bbb G_2$ is a $r$ order subgroup of $E'$. $r$ is a prime smaller than $2^{255}$ so it can fit into 32 bytes.
Generator $g_1$ of $\Bbb G_1$ (The small and fast) Fq
```
x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569
```
Generator $g_2$ of $\Bbb G_2$ (The big and slow) Fq2
```
x = 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758*i + 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
y = 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582*i + 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905
```
## The Signature Scheme
### Math
[Boneh-Lynn-Shacham (2003)] (Note that the authers are different from that of the curve)
#### Bilinear pairing
$$
e:\Bbb G_2 \times \Bbb G_1 \to \Bbb G_T
$$
$g_1$, $g_2$ are the generators of $\Bbb G_1$ and $\Bbb G_2$ respectively. $G_T$ is Fq12
bilinearity: $e(P^a, Q^b) = e(P, Q)^{ab}$
> Explain a, b. Curve Add Operation.
#### Hash function
$$
H_0: \mathcal{M} \to \Bbb G_2
$$
#### Key Generation
secret key:
$$
\alpha \gets \Bbb Z_r
$$
publick key:
$$
h \gets g_1^\alpha \in \Bbb G_1
$$
#### Sign
$$
\sigma \gets H_0(m)^\alpha \in \Bbb G_2
$$
#### Verify
$$
e(\sigma, g_1)\stackrel{?}{=} e(H_0(m), h)
$$
Proof:
$$
e(\sigma, g_1) = e(H_0(m)^\alpha, g_1) = e(H_0(m), g_1)^\alpha = e(H_0(m), g_1^\alpha) = e(H_0(m), h)
$$
### Code
[BLS codebase]
```python
Hash32 = NewType('Hash32', bytes) # 32 bytes, 256 bits
BLSPubkey = NewType('BLSPubkey', bytes) # 48 bytes, 384 bits
BLSSignature = NewType('BLSSignature', bytes) # 96 bytes
G1Uncompressed = Optimized_Point3D[optimized_bls12_381_FQ]
G1Compressed = NewType('G1Compressed', int)
G2Uncompressed = Optimized_Point3D[optimized_bls12_381_FQ2]
G2Compressed = NewType('G2Compressed', Tuple[int, int])
def hash_to_G2(message_hash: Hash32, domain: int) -> G2Uncompressed:
def privtopub(k: int) -> BLSPubkey:
def sign(message_hash: Hash32,
privkey: int,
domain: int) -> BLSSignature:
def verify(message_hash: Hash32, pubkey: BLSPubkey, signature: BLSSignature, domain: int) -> bool:
def pairing(Q: Optimized_Point3D[FQ2],
P: Optimized_Point3D[FQ],
final_exponentiate: bool=True) -> FQ12:
```
## Aggregation
### Math
Alice, Bob, and Carlos signing a message $m$.
Verifying:
$$
\sigma = \sigma_A \sigma_B \sigma_C
$$
$$
h = h_A h_B h_C
$$
$$
e(\sigma, g_1)\stackrel{?}{=} e(H_0(m), h)
$$
### Code
```python
domain = 5566
# Hash your message to 32 bytes
message_hash = b'\xab' * 32
private_keys = [3, 14, 159]
public_keys = [bls.privtopub(key) for key in private_keys]
signatures = [bls.sign(message_hash, key, domain) for key in private_keys]
# Aggregating
agg_sig = bls.aggregate_signatures(signatures)
agg_pub = bls.aggregate_pubkeys(public_keys)
# Verifying
assert bls.verify(message_hash, agg_pub, agg_sig, domain)
```
## What Could Possibly Go Wrong?
### Rogue Key Attack
Alice signed message $m$, $(\sigma_A, h_A)$
Rogue Bob generate rogue key $h_B = g_1^\beta h_A^{-1}$ and publish the aggregated signature $\sigma = H_0(m)^\beta$ and the aggregated public key $h = h_B h_A$
$$
e(\sigma, g_1)\\
= e(H_0(m)^\beta, g_1) = e(H_0(m), g_1^\beta)\\
= e(H_0(m), g_1^\beta h_A^{-1} h_A)= e(H_0(m), h_B h_A)\\
= e(H_0(m), h)
$$
> No worries, a validator is required to register the public key before being activated (proof of possession)
### Gotcha of the Hash to G2 function
#### Discrete log is compromised
The scheme would be highly insecure if the discrete log of the hash point can be calculated.
Say, one can compute the $k$ of
$$
H_0(m) = g_2^k
$$
Attacker Bob can sign a message $m'$ for Alice without knowing her private key, once Alice has already signed a message $m$ with signature $\sigma_{mA}=H_0(m)^\alpha$.
let the $m = g_2^k$ and $m' = g_2^{k'}$, Bob compute $(\sigma_{mA} )^{k'/k} = g_2^{k\alpha k'/k} = g_2^{k'\alpha} = \sigma_{m'A}$
#### Constant time hash function
The hash-and-check function is insecure since it is easy to waste verifiers' or signers' time by accidentally or adversarially choosing a difficult to hash message. Related [ethereum/eth2.0-specs#898], ia.cr/2019/403 .
## Why is BLS Signature Scheme so nice?
- Simple
- Deterministic(no random number like ECDSA)
- Threshold sigs and aggregations sigs friendly
- Same public key or signature size
## Tricks To Save More Pairings
- [Fast verification of multiple BLS signatures] and [ethereum/py_ecc#66]
- ia.cr/2019/1177
## Standardization
- github.com/cfrg/draft-irtf-cfrg-bls-signature
- github.com/cfrg/draft-irtf-cfrg-hash-to-curve
- github.com/CarlBeek/bls_key_standards
- [IETF draft] from Dan Boneh et al.
### Outdated
- [Announcement Medium]
- [ethereum/eth2.0-specs#605]
- https://github.com/pairingwg/bls_standard [inactive]
## What to Expect Next?
- Mass adoption from the blockchain ecosystem
## More References
- This short note by Dan Boneh et al. is easier to understand the construction https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html
- Read this Vitalik's post to learn more about the hairy arithmetic details https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
- This research post by Justin gives good background on using BLS in Casper and Sharding https://ethresear.ch/t/pragmatic-signature-aggregation-with-bls/2105
- BLS Berlin introduction by Vitalik and Justin. Many details and insights https://www.youtube.com/watch?v=DpV0Hh9YajU
[Announcement Medium]:https://medium.com/algorand/posting-bls-standard-draft-30a89723f386
[ethereum/eth2.0-specs#605]:https://github.com/ethereum/eth2.0-specs/issues/605
[IETF draft]:https://tools.ietf.org/id/draft-boneh-bls-signature-00.txt
[ethereum/py_ecc#66]:https://github.com/ethereum/py_ecc/issues/66
[BLS codebase]:https://github.com/ethereum/py_ecc/blob/master/py_ecc/bls/api.py
[bls12_381]:https://github.com/zkcrypto/pairing/tree/master/src/bls12_381
[Boneh-Lynn-Shacham (2003)]:https://crypto.stanford.edu/~dabo/papers/aggreg.pdf
[Barreto-Lynn-Scott(2002)]:https://eprint.iacr.org/2002/088.pdf
[ethereum/eth2.0-specs#898]:https://github.com/ethereum/eth2.0-specs/issues/898
[Fast verification of multiple BLS signatures]:https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407
[^1]:$q \approx 2^{384}$ targets the 128-bit security level.