Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

  • 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 !!!
@gakonst

This comment has been minimized.

Copy link

gakonst commented Dec 2, 2019

May want to add:

@0xAshish

This comment has been minimized.

Copy link

0xAshish commented Dec 17, 2019

@ace0

This comment has been minimized.

Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.