# FROST notes
###### Links:
[FROST](https://eprint.iacr.org/2020/852.pdf)
[How to prove Schnorr assuming Schnorr](https://eprint.iacr.org/2021/1375.pdf)
[Concurrent signing forgery attack](https://eprint.iacr.org/2018/417.pdf)
[Craige's forgery attack against Feldman's VSS](https://www.jcraige.com/vss-forgery)
[ROAST](https://eprint.iacr.org/2022/550.pdf) robust signing, running concurrent sessions for failover
[ICE FROST](https://eprint.iacr.org/2021/1658) robust keygen
[IETF FROST](https://datatracker.ietf.org/doc/draft-irtf-cfrg-frost/)
[NIDKG](https://eprint.iacr.org/2021/339.pdf)
[Fifty shades of FROST](https://eprint.iacr.org/2022/833.pdf)
###### Questions
### KeyGen:
#### Round 1: _prove knowledge of your secret commitment_
##### Sample a secret
Participant $P_i$ samples $t$ random scalars $a_{i,0}, a_{i, 1}, ... a_{i, t-1}$ and constructs a polynomial $f_i(x) = a_{i,0} + a_{i,1}x + a_{i,2}x^2... + a_{i,(t-1)}x^{t-1}$.
##### Create a proof of knowledge of the constant-term
Participant $P_i$ samples a random nonce $k \leftarrow \mathbb{F}_q$, computes a commitment to that nonce $R_i := [k]G$, and a challenge $c_i := H(i, \Phi, [a_{i,0}]G, R_i)$ where $\Phi$ is a [_context string_]() (TODO: is this more than a domain separator?).
They create $\mu_i = k + a_{i,0}\cdot c_i$, and $\sigma_i = (R_i, \mu_i)$.
##### Public commitment
Participant $P_i$ computes a public commitment to the coefficient of its polynomial: $\vec{C_i} = \langle\phi_{i,0}, \phi_{i,1}, .., \phi_{i, (t-1)}\rangle$.
Remark: note that this enables another participant to homomorphically evaluate $f_i$ at an arbitrary point $w$ by computing: $\sum_{k=0}^{t-1} \phi^{w^k}_{i,k}$, this will prove useful in the key generation step.
##### Broadcast to your peers
Participant $P_i$ broadcasts $(\sigma_i, \vec{C_i})$ to the rest of the cohorts, and expects its peers to reciprocate.
##### Verify your peers
Participant $P_i$ receives $(\sigma_l, \vec{C_l})$ from $P_l$, reconstructs the challenge $c_l = H(l, \Phi, \phi_{l,0}, R_l)$ verifies that:
$\sigma_l = (R_l, \mu_l)$ by checking that $[\mu_l]G+[c_l]\phi_{l,0} \stackrel{?}{=} R_l$.
#### Round 2: _generate the cohort's signing key_
##### Constructing their secret-share
Participant $P_i$ computes $(i, f_i(i))$
##### Broadcasting peers' secret-share
For each peer $P_l$, participant $P_i$ sends $(l, f_i(l))$
##### Verifiy their own peer generated secret share
For each peer $P_l$, participant $P_i$ _receives_ a tuple $(i, f_l(i))$, the participant needs to verify that untrusted share by homomorphically evaluating $f_l(i)$ using $\vec{C_l}$:
$f_l(i) \stackrel{?}{=} \sum_{j=0}^{t-1} \phi_{l,j}^{i^j}$
##### Compute the local signing key
Participant $P_i$ computes their local private key from the shares it receives from its peers:
$s_i = \sum_{j=1}^{n} f_j(i)$
##### Compute the public verification share
Participant $P_i$ can compute their public verification share:
$Y_i = [s_i]G$
##### Cache peers' verification share
Participant $P_i$ can compute the public verification share of another participant $P_l$:
$Y_l := \sum_{a=1}^n \sum_{j=0}^{t-1} \phi_{a,j}^{l^j} (= [\sum_{a=1}^n f_a(l)]G)$
##### Compute the group public key
$Y = \sum^{n}_{j=1} \phi_{j,0} (= [\sum_{j=1}^n f_j(0)]G)$
## API shape
```rust
struct ThresholdSigner {
public_key: Element,
}
enum State {
Init,
KeyGenRoundOne,
KeyGenRoundTwo,
Ready,
}
struct Participant<State> {
identifier: usize,
nonce: Fr,
secrets: Vec<Fr>,
signing_key: SigningKey,
verification_key: VerificationKey,
peer_cache: Vec<VerificationKey>,
}
```
```go
│
│
▼
┌─────┐
┌──────┤Init │
│ └─────┘
│
│
└────► ┌───────────────┐ each participant has:
│KeyGenRoundOne │ a local polynomial of degree t-1
┌───── └───────────────┘ a local random nonce
│
│
│
│
│
└────► ┌───────────────┐ every participant has generated
│KeyGenRoundTwo │ a public commitment vector
┌───── └───────────────┘ a valid PoK
│
│
│
│
│
│ ┌──────┐ each participant has:
└────► │Ready │ a local signing share
└──────┘ a local verification share
a cohort verification key
```
## Threshold signing
### Preprocessing
The preprocessing step consist of having every participant, precompute and commit to $\pi$ tuples of single-use nonces, where $\pi \geq 1$ is a protocol parameter.
##### Sampling single-use nonces:
Participant $P_i$ samples $1 \leq j \leq \pi$ single use nonces: $n_{i,j} := (d_{i,j}, e_{i,j})$ and caches them in a secure location.
##### Commitments
Participant $P_i$ prepares public commitments of every tuple, for $1 \leq j \leq \pi$:
$N_{i,j} := (D_{i,j}, E_{i,j}) = ([d_{i,j}]G, [e_{i,j}]G)$
##### Broadcast
Participant $P_i$ publishes $\langle N_{i,0}, N_{i,1}, ..., N_{i, \pi}\rangle$
```rust
struct Nonce {
// idea: embed an internal unique identifier
// so that nonces from a previous aggregation round
// cannot be used accidentally
inner: Fr,
}
impl Nonce {
pub fn sample(rng: OsRng) -> Self;
pub fn commit(basepoint: Element) -> Commitment;
pub fn use(self) -> Fr;
}
```
### Signing
We denote $P_{leader}$ the leader for the current round $k$ of signing message $m$.
Remark: as far as I can tell every participant can assume the position of leader, and an implementation could leverage that fact to avoid round-trips between leader/participants when building the nonce-list.
##### Round leader fetch nonces
For round $k$, $P_{leader}$ fetches every participant's committed nonce and constructs and ordered list $B := \langle (i, N_{i,k})\rangle_{0\leq i \leq n}$
##### Round leader broadcasts the nonce-list
$P_{leader}$ sends $(m, B)$ to every participant.
##### Participants validates input
Participant $P_i$ receives $(m, B)$ from $P_{leader}$ and:
- validates the message $m$ (TODO: what if you dont?)
- checks that $N_{i,k} \in \mathbb{G^*} \times \mathbb{G^*}$
##### Participants prepare signing
1. $P_i$ computes the _set_ of binding values $\langle \rho_l = H_1(l, m, B) \rangle_{P_l \in S}$
2. $P_i$ derives the group commitment $R = \sum_{P_l \in S} D_l + [\rho_l]E_l$
3. $P_i$ computes the challenge $c = H_2(R, Y, m)$
Now, $P_i$ is ready to compute its signature share.
##### Computing the signature share
$z_i = d_i + (e_i \cdot \rho_i) + \lambda_i \cdot s_i \cdot c$
where $\lambda_i$ is the lagrange coefficient. AFAICT, it's probably optional
```
nonce-commitment list
┌─────┬─────┬─────┐
│ D_1 │ │D_pi │ message
│ │ ... │ │ ┌───┐
│ E_1 │ │E_pi │ │ m │
└─────┴───┬─┴─────┘ └─┬─┘
│ │
│ │
│ │
│ │
│ │
participant index └────┐ ┌──────┤
─────────────────┐ │ │ │
│ │ │ │
│ │ │ │
│ │ │ │
▼ ▼ ▼ │
│
───────────┬─────────── │
│ │
│ │
▼ │
┌──────────────────┐ │
│ │ │
│r_l = H_1(l, m, B)│ │
│ │ │
└──────────────────┘ │
binding value for P_l │
│
│ │
│ │
┌─────────────────┘ └──────────────────────┐
│ │
│ │
│ │
│ │
│ ┌───────────────────────────────┐ │
│ │ Y = \sum_{j=1}^{n} \phi_{j,0} │ │
│ └─────────────────────┬─────────┘ │
│ Cohort public key │ │
│ │ │
▼ └─────┐ │
│ │
group commitment │ │
┌────────────────────────────────────────────────────────┐ │ │
│ R = D_1 + [r_1]E_1 + ... + D_alpha + [r_alpha]E_alpha │ │ │
└────────────────────────────────────────────────────────┘ │ │
│ │
│ │ │
└───────────┐ ┌────────────────────┘ │
│ │ │
│ │ ┌──────────────────────┘
│ │ │
│ │ │
▼ ▼ ▼
─────────────┬───────────────
│
│
│
▼
┌───────────────────────┐
│ c = H_2(R, Y, m) │
└───────────────────────┘
challenge
```
##### Group signing
Participant $P_i$
## Roast extension
Sign in with Wallet
Connect another wallet