An accountable subgroup multi-signature lets a selected subset S of registered nodes sign one message m. The resulting aggregate includes the subgroup’s signature sum, its public-key sum, and the list of participating node indices, allowing verification against that named subset. It extends BLS-style pairing signatures while avoiding a separate signature check for every signer. section 18.1 section 18.6.4
Figure 18.1 Subgroup signature basic schematic showing how only a few nodes sign the document
The schematic separates the full node population from the smaller set that actually signs a document. section 18.1
Setup binds every registered key into an ordered full-key aggregate A. Key order matters because public-key data is hashed, and each participant has a stable index. The subgroup-specific addition is a membership-key matrix μ: node j uses its private key ψj, public value aj, A, and each row index i to compute a column μi,j. It distributes that column to the other nodes; each node i then sums row i to obtain its membership key Mi. section 18.4 section 18.5
Signing and verification proceed as follows:
- Choose S as a subset of the registered public-key set, retaining the participating nodes’ indices. section 18.4
- Each selected node computes si = Mi + ψiH0(A,m), combining its membership key with a message hash bound to A. section 18.4 section 18.5
- A combiner sums the selected signatures into σS and their public keys into PS. The subgroup ordering need not matter, unlike the ordering of the complete key set. section 18.4 section 18.5
- Verify a three-pairing equality involving H0(A,m), PS, the indexed H2(A,j) terms for S, A, σS, and g2. section 18.4 section 18.8
The membership matrix is the accountability mechanism: signing is not merely a sum of ordinary signatures. Each membership key incorporates contributions derived from every registered participant’s key material, while verification also receives the claimed signer list. H0 and H2 map data to G1 points; H1 produces values modulo the torsion value r. H0 and H2 can share an implementation when separated by a domain-separation tag. section 18.4 section 18.8
Implementation has a substantial setup communication cost. With N nodes, distributing matrix columns directly requires (N−1)² data transfers. For more than 10 nodes, a central server can collect columns and redistribute rows in 2N transmissions; that server can also act as the signature combiner. This changes message flow, not the required membership-key computation. section 18.5
Simulated ten-node subgroup
A simulation selects nodes 5, 2, 17, 10, 16, 19, 7, 8, 14, and 4 from a larger registered set. Each selected node signs the same 200-byte message with its membership key. The combiner produces the aggregate signature and selected public-key sum, then verification receives those values together with the index list and reports success. section 18.6.4 section 18.6.4
Figure 18.10 Test program steps for simulating subgroup signature
The test-program flow shows the operational sequence from membership-key setup through subgroup signing, aggregation, and verification. section 18.6.4
