Implementation of distributed TSS for Schnorr signatures

[msgmaxim]

DKG (Distributed Key Generation)

The protocol is based on Pedersen's distributed key generation scheme (Pedersen, 1991). We acknowledge a potential weakness of the scheme (which allows a malicious party to hand craft u_i after having seen the commitments from other players and thus influence the aggregate public key y to some degree), however we rely on the result in Gennaro, 2003 proving the scheme nonetheless secure. The alternative would be to introduce an additional round, where parties first commit to u_i before revealing it.

Reliable Broadcast Channel

The original scheme assumed a reliable broadcast channel. We can't make this assumption, so we simulate broadcasting with p2p connections as follows.

1. Party P_i wants to "broadcast" data D_i. They distribute D_ij (presumably D_i = D_ij) to all other parties P_j (j != i).
2. Each party P_j and distributes (i, D_ij) to all other parties P_k (k != j)
3. Each party P_k now holds N "votes" for what the value of D_i was. If there is a majority agreement, P_k sets D_i to that value, other wise the protocol is aborted in P_i is blamed.

Ceremony

Consider a ceremony where N parties (P_1, ... P_N) want to generate a shared secret key that could be reconstructed by any t members of the original set.

Phase 1: Broadcast commitments and distribute secret shares.

1. Each party P_i samples a random secret u_i and sets y_i = G * u_i.

let u_i: FE = ECScalar::new_random();
let y_i = &ECPoint::generator() * &u;

2. Each party P_i generates a sharing polynomial f_i(u) of degree t-1 such that f_i(0) = u_i and splits the private secret u_i into t shares by evaluating f_i(u) at different non-zero indexes index_vec = [1..=N] (according to the Shamir Secret Sharing Scheme).

let poly = VerifiableSS::<P>::sample_polynomial(t, u_i);
let secret_shares = VerifiableSS::<P>::evaluate_polynomial(&poly, index_vec);

2. Each party P_i commits to the coefficients of f_i(u) by multiplying each by the group's generator G to obtain C_i. Note that y_i = G * f_i(0).

let G: P = ECPoint::generator();
let commitments = (0..poly.len())
    .map(|i| G.clone() * poly[i].clone())
    .collect::<Vec<P>>();

---

Communication round: "broadcast" C_i = commitments; privately send SS_ij = secret_shares[j] to each party j

---

Phase 2: Verify broadcast values

1. The broadcasting of values C_i is verified accoring to the "Reliable Broadcast Channel" protocol above.

---

Communication round: send (i, H_ij) for each i to all parties

---

Phase 3: Verify secret shares, broadcast results

1. Each party P_i verifies the shares sent to them in secret from party P_j:

G * secret_share[j] == C[0] + C[1] * i + C[2] * i^2 ... C[t-1] * j ^ (t-1)

2. If all secret shares received by P_i are valid, P_i broadcasts OK message to other parites. Otherwise, P_i broadcasts a complaint against all misbehaving parties.

   Note: We want a *reliable* broadcast here, so there is no confusion between nodes as to whether a ceremony was successful, and which nodes are misbehaving when it wasn't. Also, we would like to avoid the scenario where an honest party is not told that it is being blamed and doesn't know to respond as a result.

---

Phase 4: Verify the broadcasting of results

1. Follow the "Reliable Broadcast Channel" protocol above.

---

Communication round: send (i, H_ij) for each i to all parties

---

Phase 5: Check for complaints

1. Each party P_i checks for complaints from other parites. If all messages are OK, the ceremony is considered to have been performed correctly. If not, we enter the blaming phase.

---

Most of the time we won't need to go beyond this point

---

P_i receiving a complaint from P_j about P_k means that either P_j or P_k are misbehaving. There is no way to find out which party is wrong, but there is a way to recover which is outlined below.

Phase 6: Response of blamed parties

1. When P_k is blamed by P_j, it reveals SS_kj to all other parties to avoid being reported to SC.

---

Communication round: blamed parties P_k "broadcast" SS_kj for every challenger P_j.

---

Note: We want a *reliable* broadcast here, so the blamed parties could not avoid getting slashed and still disrupt the protocol (e.g. by only responding to one half of all parties).

---

2. Each party P_i receives a response, it verifies the secret share SS_kj (the same way as in Phase 3). If the response is invalid (or the response times out), the party is reported to SC. Otherwise, P_i sends SS_kj to the blaming party P_j.

---

Communication round: Each node sends secret share response SS_kj to the blaming party P_j (for every pair blamer/blamee P_j/P_k).

---

3. We can now assume that P_j hold the valid share and is able to sign. (Just one correct response is enough, no need for a majority).

Random implementation remarks

• Each time we set a timeout, we should add the time remaining from the previous round. This is done to enusre that the node's "performance" in the previous round does not impact it "performance" in the next round. Importantly, this prevents a malicious node from getting some honest node reported by communicating with them at the last moment.

[morelazers]

@msgmaxim do we want to PR this into the design-documentation repo and close out this issue?

[msgmaxim]

Yeah, I will do that

[msgmaxim]

This is now included in https://github.com/chainflip-io/design-documentation/pull/90, so closing it here.