BLS signatures on BitcoinPairing-based cryptography: Part 2 – CoinGeek

This post was first published onMedium.

Boneh-Lynn-Shacham(BLS) is a signature scheme based onbilinear pairings.

Compared toECDSAorSchnorrsignatures, it enjoys several salient advantages:

Due to its minimal storage and bandwidth requirements, it has been adopted by multiple blockchains such as Ethereum, Dfinity, Algorand, and Chia. We illustrate how to implement it on Bitcoin natively.

BLS Signatures: the Theory

Hash to Curve: H(m)

In ECDSA, a messagemis hashed into a number. In BLS, we hash it to a point on the elliptic curve.

One naive way is to hash the message and multiply the result with the generator pointGto get a curve point. However, it isinsecure.

To do this securely, we first hash the message using SHA-256 and treat the 256 bit result as the x-coordinate of a point. If no such point exists on the curve, we increment the x-coordinate and try again, till we find the first valid point.

Sign

Signing is trivial. We simply multiply:

pkis the private key andmis the message. Note no random number is needed.Sis just a curve point and can becompressedto 33 bytes, about half the size of an ECDSA signature.

Verify

To verify a signature, we simply compare two pairings:

To see why the verification works,

Bilinear pairingeallows us to move scalarpkfrom the first input to the second.

Implementation on Bitcoin

We have implemented BLS signature verification usingthe pairing library.

Note we let users passy-coordinate directly and verify it, to avoid computing modular square root.

Summary

We have only demonstrated how to verify a single BLS signature on Bitcoin. BLSs main power lies inaggregated signatures and keys. We leave their implementations on Bitcoin as exercises to readers.

***

NOTES:

[1] This approach is called Hash and Pray, which runs in non-constant time. Constant time approach exists, such asFouque and Tibouchi, but are harder to implement.

[2] We assume a curve point with the x-coordinate exists for ease of exposition here. A hash and pray approach can be easily added.

New to Bitcoin? Check out CoinGeeksBitcoin for Beginnerssection, the ultimate resource guide to learn more about Bitcoinas originally envisioned by Satoshi Nakamotoand blockchain.

Read more:
BLS signatures on BitcoinPairing-based cryptography: Part 2 - CoinGeek