# Threshold ECDSA

## Prelimary
### Shamir Secret Sharing

A $(t,n)$-threshold scheme builds upon Shamir secret sharing.

In Shamir secret sharing, a trusted central dealer splits a secret $s$ to $n$ shares, any $t$ paticipants can reconstruct the secret, while individual shares do not reveal anything about the secret.

- To distrubute the secret, the dealer randomly selects $t-1$ coefficients $a_1,...a_{t-1}$ and defines a polynomial $f(x)=s+\sum_{i=1}^{t-1}a_{i}x^i$. The share for paticipant $P_i$ is $(i,f(i))$.

- To reconstruct the secret, $t$ shares are needed to perform Lagrange interpolation to reconstruct the polynomial $f(x)$ and thus compute the secret value $s=f(0)$.

### Verifiable Secret Sharing

Feldman’s Verifiable Secret Sharing builds upon Shamir secret sharing. It can be used to verify if a share is well formed using a dealer generated public commitment.

Following the notation above, the dealer also publishes the public commitments $v_i=g^{a_i}$ for $i\in\{1,...,t-1\}$ and $v_0=g^s$, so that each participant $P_i$ can check their share for consistency by verifying:

$$g^{f(i)}=\prod_{i=0}^{t-1}v_j^{i^j}$$

### Additive Secret Sharing

It allows $n$ party to jointly compute a secret $s=\sum_{i=1}^ns_i$, where each party $P_i$ contributing a value $s_i$. Here, $P_i$ acts as the dealer of their secret $s_i$, sending shares to other parties).

### Distributed Key Generation

Distributed Key Generation (DKG) ensures every participant contributes equally to the generation of the shared secret. At the end of running the protocol, all participants share a joint public key $X$.

## [(n,n)-Threshold ECDSA protocol Overview](https://eprint.iacr.org/2021/060) (the part without ZKP)

### Key Generation

Each $P_i$
- samples a local random key share $x_i$
- reveals $X_i=g^{x_i}$
- $x=\sum_{i=1}^nx_i$ is the signing key, $X=\prod_{i=1}^nX_i$ is the verifying key

### Key-Refresh
Each $P_i$
- chooses a random secret sharing of $0=\sum_{j=1}^nx_i^j$
- computes $X_i^j=g^{x_i^j}$ and $C_i^j=enc_j(x_i^j)$
- broadcases $(X_i^j, C_i^j)$
- updates its key shares by $x_i^*=x_i+\sum_{j=1}^ndec_i(C_j^i)$

### Presigning

Presigning provides significant efficiency and security benefits by generating partial signatures in advance, without requiring knowledge of the message to be signed.

An ECDSA signature has the form $(r=g^{k^{-1}}|_{x-axis},\sigma=k(m+rx))$.

**Main challenge**: $g^{k^{-1}}$ is computed from $(g^{\gamma})^{\delta^{-1}}$, where $\delta=k\gamma$. Here, $\gamma$ is used to mask $k$.

Each $P_i$
1. samples local shares $k_i$, $\gamma_i$
-- computes and broadcasts $K_i=enc_i(k_i)$ and $G_i=enc_i(\gamma_i)$
2. samples additive shares $\beta_{i,j},\hat{\beta}_{i,j}$ and computes $\alpha_{i,j},\hat{\alpha}_{i,j}$ (such that $\alpha_{i,j}+\beta_{j,i}=\gamma_jk_i$ and $\hat{\alpha}_{i,j}+\hat{\beta}_{j,i}=x_jk_i$). The interactive process is as follows by using an MtA (for Multiplicative to Additive) share conversion protocol:
-- computes $D_{j,i}=\gamma_iK_j+enc_j(-\beta_{i,j})=enc_j(\gamma_ik_j-\beta_{i,j})$ and $\hat{D}_{j,i}=x_iK_j+enc_j(-\hat{\beta}_{i,j})=enc_j(x_ik_j-\hat{\beta}_{i,j})$ using the homomorphic properties of Paillier
-- computes $\alpha_{i,j}=dec_i(D_{i,j})$ and $\hat{\alpha}_{i,j}=dec_i(\hat{D}_{i,j})$
3. computes shares of $\gamma k$ and $xk$
-- computes $\delta_i=\gamma_ik_i+\sum_{j\not=i}\alpha_{i,j}+\beta_{i,j}$, which is a share of $\gamma k$
-- computes $\chi_i=x_ik_i+\sum_{j\not=i}\hat{\alpha}_{i,j}+\hat{\beta}_{i,j}$, which is a share of $xk$
4. broadcasts $(g^{\gamma_i},\delta_i)$, and then computes $g^{k^{-1}}=(\prod_ig^{\gamma_i})^{(\sum_i\delta_i)^{-1}}$
5. stores $(g^{k^{-1}},k_i,\chi_i)$

### Signing
$P_i$ computes $\sigma_i=k_im+r\chi_i$, which is a share of $\sigma=\sum_{i}\sigma_i$.

## [(t,n)-Threshold ECDSA protocol Overview](https://eprint.iacr.org/2019/114.pdf) (the part without ZKP)

### Key Generation

Each $P_i$
- samples a local random key share $u_i$
- performs a (t,n) Feldman-VSS of the value $u_i$
- reveals $X_i=g^{u_i}$
- $x=\sum_{i=1}^nu_i$ is the signing key, $X=\prod_{i=1}^nX_i$ is the verifying key
- $x_i=\sum_{j}u_{i,j}$ is a (t,n)-share of $x$

### Signing
Let $S\subseteq[1,...,n]$ and $|S|=t$ be the set of players participating in the signature protocol. Similar to the (n,n)- protocol above. The key difference here is the secret reconstruction using shares indexed in $S$ instead of $[1,...,n]$:
- $k=\sum_{i\in S}k_i$, $\gamma=\sum_{i\in S}\gamma_i$, $x=\sum_{i\in S}(\lambda_{i,S} \cdot x_i)$
- $\delta_i=\gamma_ik_i+\sum_{i,j\in S, j\not=i}\alpha_{i,j}+\beta_{i,j}$ is an additive share of $\gamma k=\sum_{i\in S}\delta_i$
- $\chi_i=x_ik_i+\sum_{i,j\in S,j\not=i}\hat{\alpha}_{i,j}+\hat{\beta}_{i,j}$ is an additive share of $xk$
- $g^{k^{-1}}=(\prod_{i\in S}g^{\gamma_i})^{(\sum_{i\in S}\delta_i)^{-1}}$
- $\sigma = \sum_{i\in S}(k_im+r\chi_i)$

## Use ZKP to prevent Malicious Attacks

The main purpose of the ZK-proofs is to bypass the security vulnerabilities that arise from using Paillier encryption.

The GMW Compiler is a foundational technique used to transform a protocol that is secure against semi-honest adversaries into one that is secure against malicious adversaries. The core idea of the GMW compiler is to use ZK-proofs to "enforce" that every message, including those from malicious players, is the outcome of executing the protocol honestly.

Existing attaks:
- [GG18 and GG20 Paillier Key Vulnerability](https://www.fireblocks.com/blog/gg18-and-gg20-paillier-key-vulnerability-technical-report/)
- [A Note on the Security of GG18](https://info.fireblocks.com/hubfs/A_Note_on_the_Security_of_GG.pdf)
- [Alpha-Rays: Key Extraction Attacks on Threshold ECDSA Implementations](https://eprint.iacr.org/2021/1621)
- [BitGo Wallet Zero Proof Vulnerability](https://www.fireblocks.com/blog/bitgo-wallet-zero-proof-vulnerability/)
- [TSSHOCK: Breaking MPC Wallets and Digital Custodians for $BILLION$ Profit](https://verichains.io/tsshock/)

## References

1. [UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts](https://eprint.iacr.org/2021/060)
2. [Fast Multiparty Threshold ECDSA with Fast Trustless Setup](https://eprint.iacr.org/2019/114.pdf)