The CoSi Multi-Signature Scheme
CoSi is a multi-signature scheme introduced by Syta et al. [STV+16] that follows a long line of work on Schnorr-based multi-signatures. By organizing signers in a tree structure, thousands of signers can create a multi-signature in seconds, as demonstrated by the open source implementation.
github.com/dedis/cothority
Parameters generation.
The algorithm sets up a group of order where is a -bit prime. It also chooses two hash functions Output . Key generation.
The key generation algorithm samples and computes . It then generates a proof of possession by choosing and computing Output and .
Signing. Signing is a four-step protocol. A signer on input behaves as follows.
If is the leader (i.e., the root of tree ), it initiates the protocol by sending an announcement to its children, which consists of a unique identifier for this signing session . If is not the leader, it waits to receive an announcement message and forwards it to its children in . After doing so, proceeds with the commitment phase. Let denote the set of children of in tree waits to receive all values for Note that if has no children (i.e., it is a leaf in tree it will proceed immediately. chooses and computes and for If is not the leader, it sends to its parent. If is the leader, proceeds with the challenge phase. waits to receive all values for (note that if is a leaf it will proceed immediately), and then computes It sends to its parent, unless is the root, then sets and outputs Key Aggregation. On input a set of public keys checks for all that If so, it outputs aggregate public key . Verification. on input an aggregate public key , a signature and a message checks that
