(TODO for Tarak: update inaccuracies in this doc)

Where is the threshold signatures scheme used in Flow?

Threshold Signature is used by Flow to generate random values in a distributed manner, to form a native random beacon to the Flow protocol. The threshold signature is instantiated using the BLS signature. BLS signature generation is used as a Verifiable Random function (VRF - check definition here) to form a VRF-based random beacon. The threshold aspect makes the VRF construction distributed and decentralized, making the Flow random beacon a threshold-VRF instance.

What is a Threshold signature (TS)?

A threshold key generation (distributed or not) is a protocol that allows n participants to generate a key pair (SK, PK) and to divide it into n key shares, each share is a key pair (sk_i, pk_i) corresponding to the i-th participant. If the generation is distributed, SK is generated using entropy from the n participants (see next section for details on the keys)

The sk_i are the t-Shamir secret sharing of SK, i.e SK can be computed given any t+1 distinct key shares sk_i , and a set of up to t distinct key shares does not give any information about SK.

Threshold signatures allow the signature of a certain message m under the secret key SK without reconstructing SK first. The signature can be reconstructed using t+1 signatures of the same message m using distinct key shares sk_i. SK doesn't have to be recovered to sign a message. The process doesn't leak information about SK and therefore allows SK to be reused for signing different messages.

Overview of Threshold Signature methods:

Given n participants, indexed from 1 to n

1. a threshold-key generation protocol (distributed or not) generates a group key-pair (SK, PK) and n key-pair shares (sk_i, pk_i) , such that:
   • SK is not known by any of the n participants
   • PK and all pk_i are known by all n participants and all external parties
   • for all i , sk_i is known by participant of index i and not known to other participants of index j != i
   • sk_i s are the shamir sharing of secret SK
2. For any given message m, participants can sign m using their respective sk_i, and generate the signature share sig_i = sign(sk_i, m)
3. Each sig_i can be verified using m , pk_i and the simple signature verification algorithm Verify(sig_i, m, pk_i)
4. a signature of m under SK can be reconstructed using at least t+1valid  sig_i along with their corresponding indices i . The resulting signature is also called a threshold signature sig
5. The signature sig can be verified suing m and PK and the simple signature verification algorithm Verify(sig, m, PK)

Given n, how to pick the right t?

TODO: update below

A threshold signature scheme has to main security properties:

unforgeability: