bipschnorr-Threshold.md

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 a_i0...a_i(t-1) and a'_i0...a'_i(t-1) in the range 1...n-1 , 2t integers.
• Let the sharing polynomials be f_i(x) and f'_i(x)
  • f_i(x) = a_i0 + a_i1x¹ + ... + a_i(t-1)x^t-1
  • f'_i(x) = a'_i0 + a'_i1x¹ + ... + a'_i(t-1)x^t-1
• Let the commitments be C_i0...C_i(t-1) : C_ih = a_ihG + a'_ihH (h = 0...t-1).
• The user(i) sends commitments(C_i0...C_i(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 s_ij = f_i(j) mod n , s'_ij = f'_i(j) mod n
  • The user(i) sends (s_ij , s'_ij) to the user(j).
  • The user(i) sends other user's commitments(C_h0...C_h(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 s_jiG + s'_jiH ≠ i⁰C_j0 + ... + i^t-1C_j(t-1)
• Fail if commitments(C_h0...C_h(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 A_i0...A_i(t-1) : A_ih = a_ihG (h = 0...t-1).
• The user(i) sends A_i0...A_i(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 s_jiG ≠ i⁰A_j0 + ... + i^t-1A_j(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 = A₁₀ + ... + A_k0

Signing

• The t users participating in the signing process(u_i , i = 1...t) .
• 1 ≤ u_i ≤ k , i = 1...t ; u_i1 ≠ u_i2 , i1 ≠ i2 , 1 ≤ i1 ≤ t , 1 ≤ i2 ≤ t .

Step 1

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

• Let there be random numbers b_ui0...b_ui(t-1) and b'_ui0...b'_ui(t-1) in the range 1...n-1 , 2t integers.
• Let the sharing polynomials be g_ui(x) and g'_ui(x)
  • g_ui(x) = b_ui0 + b_ui1x¹ + ... + b_ui(t-1)x^t-1
  • g'_ui(x) = b'_ui0 + b'_ui1x¹ + ... + b'_ui(t-1)x^t-1
• Let the commitments be C'_ui0...C'_ui(t-1) : C'_uih = b_uihG + b'_uihH (h = 0...t-1).
• The user(u_i) sends commitments(C'_ui0...C'_ui(t-1)) to the other users(u_j , j = 1...t , j ≠ i).

Step 2

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

• For j = 1...t , j ≠ i :
  • Let r_uiuj = g_ui(u_j) mod n , r'_uiuj = g'_ui(u_j) mod n
  • The user(u_i) sends (r_uiuj , r'_uiuj) to the user(u_j).
  • The user(u_i) sends commitments(C'_uh0...C'_uh(t-1) , h = 1...t , h ≠ i , h ≠ j) of other users to the user(u_j).

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

• Fail if r_ujuiG + r'_ujuiH ≠ u_i⁰C_uj0 + ... + u_i^t-1C_uj(t-1)
• Fail if commitments(C'_uh0...C'_uh(t-1) , h = 1...t , h ≠ i , h ≠ j) sent from user(i_j) does not match commitments received at Step 1.
• If fail , sends result to other user(u_h , h = 1...t , h ≠ i).

Step 3

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

• Let the B_ui0...B_ui(t-1) : B_uih = b_uihG (h = 0...t-1).
• The user(u_i) sends B_ui0...B_ui(t-1) to other users(u_j , j = 1...t , j ≠ i).

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

• Fail if r_ujuiG ≠ u_i⁰B_uj0 + ... + u_i^t-1B_uj(t-1)
• If fail , sends result to other user(u_h , h = 1...t , h ≠ i).

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

Step 4

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

• Let r = r_u1ui + ... + r_utui
• Let R = B_u10 + ... + B_ut0
• If jacobi(y(R)) ≠ 1 , let r = n - r
• Let P = A₁₀ + ... + A_k0
• Let e = int(hash(bytes(x(R)) || bytes(P) || m)) mod n
• Let s = s_u1ui + ... + s_ukui
• Let sig_ui = r + es mod n
• The user(u_i) sends sig_ui to other users(u_j , j = 1...t , j ≠ i).

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

• Let B be the point at infinity
• For h = 1...t :
  • B = B + j⁰B_uh0 + ... + j^t-1B_uh(t-1)
• Let R = B_u10 + ... + B_ut0
• If jacobi(y(R)) ≠ 1 , let B = -B
• Let P = A₁₀ + ... + A_k0
• 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 + j⁰A_uh0 + ... + j^t-1A_uh(t-1)
• Fail if sig_ujG ≠ B + eA
• If fail , sends result to other user(u_h , 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 , u_h ≠ u_j :
      • o = o × u_h ÷ (u_h - u_j) mod n
    • s = s + o × sig_uj mod n
• Let R = B_u10 + ... + B_ut0
• 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.

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-August/016292.html

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-August/016329.html

@tnakagawa: Thanks for sharing. I have a few questions:

1. How to determine a good value for x in order to produce the secondary generator H?
2. What are the criteria for x & H?
3. Can x & H be reused for other rounds?
4. Can you give example for x & H for the Bitcoin curve?

Thanks.

Sorry for my late response.

I do not have a good idea.