Skip to content

Instantly share code, notes, and snippets.

@paulmillr

paulmillr/BLS_Signature.md

Last active August 5, 2024 09:00
Show Gist options
  • Save paulmillr/18b802ad219b1aee34d773d08ec26ca2 to your computer and use it in GitHub Desktop.
Save paulmillr/18b802ad219b1aee34d773d08ec26ca2 to your computer and use it in GitHub Desktop.
Download ZIP
BLS Signature for Busy People
Raw
BLS_Signature.md

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

  • 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

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/

Public Keys: 48 Bytes.

Signatures: 96 Bytes.

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

Further Reading

Standards / Specs

Papers

Articles / Posts

Implementations

Notes

  • Thanks a lot to @benjaminion !!!
@ArnaudBrousseau
Copy link

Awesome gist, thank you! Still relevant in 2023!

The ETH specs have moved around a bit so the links aren't valid anymore:

@paulmillr
Copy link
Author

Thanks, updated.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment