BLS digital signature

A gap group is a group in which the computational Diffie–Hellman problem is intractable but the decisional Diffie–Hellman problem can be efficiently solved. Non-degenerate, efficiently computable, bilinear pairings permit such groups.

Let ${\displaystyle e\colon G\times G\rightarrow G_{T}}$ be a non-degenerate, efficiently computable, bilinear pairing where ${\displaystyle G}$, ${\displaystyle G_{T}}$ are groups of prime order, ${\displaystyle r}$. Let ${\displaystyle g}$ be a generator of ${\displaystyle G}$. Consider an instance of the CDH problem, ${\displaystyle g}$,${\displaystyle g^{x}}$, ${\displaystyle g^{y}}$. Intuitively, the pairing function ${\displaystyle e}$ does not help us compute ${\displaystyle g^{xy}}$, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. Given ${\displaystyle g^{z}}$, we may check to see if ${\displaystyle g^{z}=g^{xy}}$ without knowledge of ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$, by testing whether ${\displaystyle e(g^{x},g^{y})=e(g,g^{z})}$ holds.

By using the bilinear property ${\displaystyle x+y+z}$ times, we see that if ${\displaystyle e(g^{x},g^{y})=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^{z})}$, then, since ${\displaystyle G_{T}}$ is a prime order group, ${\displaystyle xy=z}$.

A signature scheme consists of three functions: generate, sign, and verify.[1]

Key generation

The key generation algorithm selects a random integer ${\displaystyle x}$ such as ${\displaystyle 0<x<r}$. The private key is ${\displaystyle x}$. The holder of the private key publishes the public key, ${\displaystyle g^{x}}$.

Signing

Given the private key ${\displaystyle x}$, and some message ${\displaystyle m}$, we compute the signature by hashing the bitstring ${\displaystyle m}$, as ${\displaystyle h=H(m)}$. We output the signature ${\displaystyle \sigma =h^{x}}$.

Verification

Given a signature ${\displaystyle \sigma }$ and a public key ${\displaystyle g^{x}}$, we verify that ${\displaystyle e(\sigma ,g)=e(H(m),g^{x})}$.

• Simple Threshold Signatures[3]
• Signature Aggregation: Multiple signatures generated under multiple public keys for multiple messages can be aggregated into a single signature.[4]
• Unique and deterministic: for a given key and message, there is only one valid signature (like RSA PKCS1 v1.5, EdDSA and unlike RSA PSS, DSA, ECDSA and Schnorr).

• Chia network has used BLS signatures.[5][6]
• By 2020, BLS signatures were used extensively in version 2 (Eth2) of the Ethereum blockchain, as specified in the IETF draft BLS signature specification—for cryptographically assuring that a specific Eth2 validator has actually verified a particular transaction.[2] The use of BLS signatures in Ethereum is considered a solution to the verification bottleneck only for the medium term, as BLS signatures are not quantum secure. Over the longer term—say, 2025–2030—STARK aggregation is expected to be a drop-in replacement for BLS aggregation.[7]

• Pairing-based cryptography

• Summary description of the Algorand draft standard effort
• Ben Lynn's PBC Library
• Chia Network's BLS signatures implementation (C++)