Published owned this noteowned this note Linked with GitHub
Any changes
Be notified of any changes
Mention me
Be notified of mention me
# 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.
Import from clipboard
Advanced permission required
Your current role can only read. Ask the system administrator to acquire write and comment permission.
This team is disabled
Sorry, this team is disabled. You can't edit this note.
This note is locked
Sorry, only owner can edit this note.
Reach the limit
Sorry, you've reached the max length this note can be.
Please reduce the content or divide it to more notes, thank you!