Overview

18 Exploring BLS multi-signatures

Multi-signatures based on BLS pairings extend ordinary short signatures so that many signers can authenticate the same message while reducing verification work. The chapter frames this around elliptic-curve pairing groups, where messages are hashed to a curve point and public keys are hashed into a scalar that binds the entire key set together. The result is a scheme that can collapse many individual signatures into a single aggregate object, making verification far cheaper than checking each signer separately.

The first construction, key aggregation, hashes the ordered list of public keys so each signer gets a unique coefficient, then uses those coefficients to form a combined public key. Each participant signs the same message with a value derived from their private key and the shared message hash, and a combiner sums the signatures into one group element. Verification succeeds when a pairing identity shows the aggregate signature matches the aggregate public key against the message hash, with the ordering of keys being essential for security and correctness.

The second construction, accountable subgroup multi-signatures, adds a membership matrix so only a chosen subset of nodes can sign while still proving who participated. Each node computes membership keys from the aggregate public-key structure, exchanges matrix data, and signs with both its private key and membership key; the combiner then sums the subgroup’s signatures and public keys. Verification uses three pairings to confirm consistency between the subgroup message hash, the subgroup public key sum, and the aggregate signature, and the chapter closes by showing simulation code and test data that demonstrate the mathematics working in practice.

Subgroup signature basic schematic showing how only a few nodes sign the document
figure
Aggregated digital signature signing detailed schematic
figure
Hash functions used with aggregation
figure
Hash \(H_0(M)\) to base curve: converts a text message into a point on the curve using a hash function.
figure
Hash \(H_1(Q)\) to large prime factor in base curve: hashes the concatenation of public keys to a single value.
figure
Schematic of key aggregation method
figure
Polynomial keys in memory as a list of coefficients, converted to a byte array for hashing.
figure
Individual nodes create a signature of the document, and then a single node sums all signatures into composite point.
figure
Equations creating value \(A\)
figure
Test program steps for simulating subgroup signature
figure

Summary

  • \(H_0\) and \(H_2\) convert input data to a \(G_1\) point.
  • \(H_1\) converts input data to a value modulo the torsion value \(r\).
  • \(a_j\) is a hash of all public keys in order with key \(j\) placed before the other keys \[a_j=H_1(P_j, P_1, P_2,\cdots P_n)\]which means key \(P_j\) is used twice.
  • The sum of all keys is \[A=\sum_{j=1}^{n}a_j P_j\]
  • A single node’s signature combines a node’s private key, \(a_j\) value, and a hash of the message \[s_j=\psi_j a_j H_0(m)\]
  • A multi-group signature is the sum of individual node’s signatures \[\sigma=\sum_{j=1}^{n}s_j\]
  • Verification of a multi-group signature uses two pairings by checking\[e(\sigma, g_2) \stackrel{?}{=} e(H_0(m), A)\]
  • A subgroup multi-signature uses a membership key derived from a matrix \[\mu_{i, j}=a_j \psi_j H_2(A, i)\]
  • Each node computes one column of the \(\mu_{i, j}\) matrix and sends its value to all other nodes.
  • When the matrix is fully distributed, every node computes its membership key as the sum of its row of the matrix \[M_i=\sum_{j=1}^{n} \mu_{i, j}\]
  • Nodes signing a message use their membership key and private key to compute \[s_i = M_i + \psi_i H_0(A, m)\]
  • A subgroup \(S\) of nodes creates an aggregate signature with a sum of individual signatures and sum of participating public keys: \[P_S=\sum_{j\in S}P_j \qquad \sigma_S=\sum_{j\in S}s_j\]
  • A subgroup signature is verified using three pairing calculations and checking \[e(H_0(A, m), P_S) \cdot e \left(\sum_{j\in S} H_2(A, j),A \right) \stackrel{?}{=} e(\sigma_S, g_2)\]

FAQ

What is the main goal of BLS multi-signatures in this chapter?The goal is to combine multiple individual signatures into one aggregate signature so verification can be done with far fewer pairing calculations than checking each signer separately.
How do multi-signatures with key aggregation improve verification speed?They combine all public keys into one aggregated public key value, so the verifier only needs to perform a small number of pairing computations instead of verifying each signature on its own.
Why does the order of public keys matter in key aggregation?The order matters because the hash used to compute each key coefficient depends on the full ordered list of public keys. If the order changes, the resulting coefficients and aggregated key will change too.
What are the two hash functions used in the key aggregation scheme?H0 hashes the message into a point on G1, and H1 hashes the public-key list into a value modulo r.
How is an individual multi-signature computed?Each signer computes s_i = a_i ψ_i H0(m), where ψ_i is the private key, a_i is the key-aggregation hash value, and H0(m) is the hashed message point.
What is the verification equation for an aggregate BLS multi-signature?The signature verifies if e(σ, g2) = e(H0(m), A), where σ is the summed signature and A is the aggregated public key.
What extra idea does accountable subgroup multi-signatures add?It adds a membership-key matrix so only a chosen subgroup of signers can produce a valid aggregate signature, while still allowing the signature to be verified publicly.
Why does the subgroup scheme use three hash functions instead of two?It uses H0 for hashing the message, H1 for aggregating public keys, and H2 to derive membership-related values from the aggregated key and signer index.
What is the purpose of the membership key in the subgroup scheme?The membership key M_i is a row sum of the membership matrix for node i. It ties the signer to the subgroup setup and is included in that signer’s signature.
How is a subgroup signature verified?Verification checks whether e(H0(A, m), P_S) · e(Σ H2(A, j), A) = e(σ_S, g2), using the subgroup’s public-key sum, signer list, and aggregate signature.

pro $24.99 per month

  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose one free eBook per month to keep
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime

lite $19.99 per month

  • access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more


Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free