Frost

Komlo, C. (n.d.). FROST: Flexible Round-Optimized Schnorr Threshold Signatures. 35. https://eprint.iacr.org/2021/1375.pdf

https://www.youtube.com/watch?v=4DFfZovCBB0

Thresh-hold Schemes

(t-n) schemes require any subset t of n to be able to recover a shared secret s. Subsets smaller than are unable to recover the secret.

Shamir Secret Sharing

  • For a (t, n) scheme a dealer creates t-1 co-efficients a_1, .., a_t-1 randomly for a polynomial f(x)
  • For every participant P_i, the dealer calculates f(i) and sends the point to them (i, f(i))
  • The secret s is the y-intercept, so when s = f(0)

  • When any t participants collaborate, there will be t points available, and with these points using lagrange interpolation the polynomial can be retrieved again. With this the secret s can be found.

  • For a n-th degree polynomial, having n+1 points is sufficient to re-construct the polynomial.

  • If you thus want 10 people to be required to re-construct a polynomial, you need a 10-1 = 9th degree polymomial.

  • If you thus want 3 people to be required to re-construct a polynomial, you need a 3-1 = 2th degree polynomial i.e.

    • f(x) = 5 + 2x + 4x^2
    • 3 points needed to re-construct the above

  • Distribution round of s:

    • 1 round: dealer sends messages to all participants
  • Reconstruction:
    • 1 round: t participants collect secret shares and re-construct secret
  • (-) There is a centralized dealer needed who at some point knows s.

Feldman Verifiable Secret Sharing (VSS)

https://medium.com/asecuritysite-when-bob-met-alice/making-the-card-game-honest-for-the-players-and-the-dealer-meet-feldman-verifiable-secret-shares-7f8436956bfe

https://en.wikipedia.org/wiki/Verifiable_secret_sharing

Problem: how can a participant trust that the dealer actually gave them a a valid point from the polynomial and that all other participants also got a valid point from the SAME polynomial?

Solution: commitments, this is Feldman's contribution

The dealer creates commitments for s and all co-efficients using mod p.

c_s = .. c_1 = .. c_2 = ..

The dealer also creates a main commitment.

g^v = .. v = f(i) mod p

Remember f(i) is secret, cannot share this to the participants.

The dealers sends 2 lists: - all commitments c_s... c_n and - g^v to the participants.

At no point are f(i) or secret co-efficients revealed.

The participants i.e. participants i can now verify using: - v = f(i) mod p

(...)

====

TL;DR:

  • (+) VSS used to verify if the dealer actually send all participants points from the same polynomial function f(i).
  • (-) Still centralization problem of a participant at some point knowing the key.

Thresh-hold signature schemes for Schnorr Signatures

  • Requires no participant to ever know the secret s (representing private key) or the random nonce k that is used for the Schnorr signature
  • Of the n participants, t participants are needed to sign a valid thresh-hold signature. A single public key Y is used to represent the group.
  • Distributed Key Generation (DKG) protocol is required for this to work (no central dealer). Generation of the shares s_1, ..., s_n and the secret s.
  • A Schnorr signature requires a random nonce k. In thresh-hold signature schemes no participant must know k. Additive secret sharing is used for participants to contribute to k, but no participants will know k.

BIP 340 Compatibility

BIP 340 is the Bitcoin Improvement Specification for the usage of Schnorr signatures in the Bitcoin protocol. This specification is done over the secp256k1 curve.

In addition to Schnorr signatures, a number of non-schnorr signature specific improvements are made. This is important, because not every implementation that uses Schnorr signatures will be compatible.

  • Schnorr signatures
  • secp256k1 curve
    • re-uses same curve used in bitcoin already
  • fixed 64 byte encoding for signatures (vs variable)
  • public keys are 32 bytes (vs 33 bytes)