Instantly share code, notes, and snippets.

# Threshold Signatures

This text is a procedure for t-of-k threshold signatures.

The symbols and functions used are defined in the following URL.

https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

## Introduction

• The number of users k.
• The number of required signers t. ( 0 < t ≤ k )
• The constant H refers to the generator. ( G ≠ H )
• Let H = xG , x mod n , x is random.
• The message m : an array of 32 bytes

The n , G and functions are cited from the original text.

Each user i(i = 1...k) is in an agreed ordered set so that user i is always the same for every user.

## Shared Secret

### Step 1

Each user i(i = 1...k) sends t commitments to a set of random numbers:

• Let there be random numbers ai0...ai(t-1) and a'i0...a'i(t-1) in the range 1...n-1 , 2t integers.
• Let the sharing polynomials be fi(x) and f'i(x)
• fi(x) = ai0 + ai1x1 + ... + ai(t-1)xt-1
• f'i(x) = a'i0 + a'i1x1 + ... + a'i(t-1)xt-1
• Let the commitments be Ci0...Ci(t-1) : Cih = aihG + a'ihH (h = 0...t-1).
• The user(i) sends commitments(Ci0...Ci(t-1)) to the other users(j = 1...k , j ≠ i).

### Step 2

Each user(i = 1...k) sends shared secrets and the other users' commitments to each other user:

• For j = 1...k , j ≠ i :
• Let sij = fi(j) mod n , s'ij = f'i(j) mod n
• The user(i) sends (sij , s'ij) to the user(j).
• The user(i) sends other user's commitments(Ch0...Ch(t-1) , h = 1...k , h ≠ i , h ≠ j) to the user(j).

Each user(i = 1...k) verifies secret and commitments received from user(j = 1...k , j ≠ i) :

• Fail if sjiG + s'jiH ≠ i0Cj0 + ... + it-1Cj(t-1)
• Fail if commitments(Ch0...Ch(t-1), h = 1...k , h ≠ i , h ≠ j) does not match commitments received at Step 1.
• If fail , sends result to other user(h = 1...k , h ≠ i).

### Step 3

Each user(i = 1...k) sends shared points :

• Let the Ai0...Ai(t-1) : Aih = aihG (h = 0...t-1).
• The user(i) sends Ai0...Ai(t-1) to other users(j = 1...k , j ≠ i).

Each user(i = 1...k) verifies shared points received from user(j = 1...k , j ≠ i) :

• Fail if sjiG ≠ i0Aj0 + ... + it-1Aj(t-1)
• If fail , sends result to other user(h = 1...k , h ≠ i).

The publickey of shared secret is sum of each 0-th points. : P = A10 + ... + Ak0

## Signing

• The t users participating in the signing process(ui , i = 1...t) .
• 1 ≤ ui ≤ k , i = 1...t ; ui1 ≠ ui2 , i1 ≠ i2 , 1 ≤ i1 ≤ t , 1 ≤ i2 ≤ t .

### Step 1

Each user ui(ui , i = 1...t) sends t commitments to a set of random numbers :

• Let there be random numbers bui0...bui(t-1) and b'ui0...b'ui(t-1) in the range 1...n-1 , 2t integers.
• Let the sharing polynomials be gui(x) and g'ui(x)
• gui(x) = bui0 + bui1x1 + ... + bui(t-1)xt-1
• g'ui(x) = b'ui0 + b'ui1x1 + ... + b'ui(t-1)xt-1
• Let the commitments be C'ui0...C'ui(t-1) : C'uih = buihG + b'uihH (h = 0...t-1).
• The user(ui) sends commitments(C'ui0...C'ui(t-1)) to the other users(uj , j = 1...t , j ≠ i).

### Step 2

Each user(ui , i = 1...t) sends random numbers and the other user's commitments to each other user :

• For j = 1...t , j ≠ i :
• Let ruiuj = gui(uj) mod n , r'uiuj = g'ui(uj) mod n
• The user(ui) sends (ruiuj , r'uiuj) to the user(uj).
• The user(ui) sends commitments(C'uh0...C'uh(t-1) , h = 1...t , h ≠ i , h ≠ j) of other users to the user(uj).

Each user(ui , i = 1...t) verifies random number and commitments received from user(uj , j = 1...t , j ≠ i) :

• Fail if rujuiG + r'ujuiH ≠ ui0Cuj0 + ... + uit-1Cuj(t-1)
• Fail if commitments(C'uh0...C'uh(t-1) , h = 1...t , h ≠ i , h ≠ j) sent from user(ij) does not match commitments received at Step 1.
• If fail , sends result to other user(uh , h = 1...t , h ≠ i).

### Step 3

Each user(ui , i = 1...t) sends random points :

• Let the Bui0...Bui(t-1) : Buih = buihG (h = 0...t-1).
• The user(ui) sends Bui0...Bui(t-1) to other users(uj , j = 1...t , j ≠ i).

Each user(ui , i = 1...t) verifies random points received from user(uj , j = 1...t , j ≠ i) :

• Fail if rujuiG ≠ ui0Buj0 + ... + uit-1Buj(t-1)
• If fail , sends result to other user(uh , h = 1...t , h ≠ i).

The Point of random number is sum of each 0-th points. : R = Bu10 + ... + But0

### Step 4

Each user(ui , i = 1...t) sends signature :

• Let r = ru1ui + ... + rutui
• Let R = Bu10 + ... + But0
• If jacobi(y(R)) ≠ 1 , let r = n - r
• Let P = A10 + ... + Ak0
• Let e = int(hash(bytes(x(R)) || bytes(P) || m)) mod n
• Let s = su1ui + ... + sukui
• Let sigui = r + es mod n
• The user(ui) sends sigui to other users(uj , j = 1...t , j ≠ i).

Each user(ui , i = 1...t) verifies signature received from user(uj , j = 1...t , j ≠ i) :

• Let B be the point at infinity
• For h = 1...t :
• B = B + j0Buh0 + ... + jt-1Buh(t-1)
• Let R = Bu10 + ... + But0
• If jacobi(y(R)) ≠ 1 , let B = -B
• Let P = A10 + ... + Ak0
• Let e = int(hash(bytes(x(R)) || bytes(P) || m)) mod n
• Let A be the point at infinity
• For h = 1...k :
• A = A + j0Auh0 + ... + jt-1Auh(t-1)
• Fail if sigujG ≠ B + eA
• If fail , sends result to other user(uh , h = 1...t , h ≠ i).

### Step 5

Anyone holding sig and who knows the predefined user order can produce a valid signature:

• Let s = 0
• For j = 1...t :
• Let o = 1
• For h = 1...t , uh ≠ uj :
• o = o × uh ÷ (uh - uj) mod n
• s = s + o × siguj mod n
• Let R = Bu10 + ... + But0
• The signature is bytes(x(R)) || bytes(s).

## References

Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates
http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps

## Acknowledgements

I would like to thank everyone who advised.

Owner Author

### vietlq commented Sep 5, 2018

 @tnakagawa: Thanks for sharing. I have a few questions: How to determine a good value for `x` in order to produce the secondary generator `H`? What are the criteria for `x` & `H`? Can `x` & `H` be reused for other rounds? Can you give example for `x` & `H` for the Bitcoin curve? Thanks.
Owner Author

### tnakagawa commented Sep 14, 2018

 Sorry for my late response. I do not have a good idea.