Threshold Multisignature

The threshold signature is a subset of Multisignature. A unique public key represents each participant. However, each participant's private key is kept secret. The full secret is never disclosed. Each participant signs using their part of the secret share. Therefore, the original secret can never be reconstructed by an external party.

FROST

A message or transaction will get through on condition that at least $t$ out of $n$ signers approve it. For example, if $n$ is ten signers and threshold $t$ is set to 0.7, at least seven participants must approve a transaction to go through, while three signers can stay inactive, down, or malicious.

An example of a Threshold Multisignature is FROST or Flexible Round-Optimized Schnorr Threshold Signature used since version 2.0 of the XP.NETWORK NFT Bridge.

FROST can be used in two forms:

1. A two-round Schnorr threshold signing protocol
2. A single-round protocol with preprocessing is an optimized version of the above, implemented by the XP.NETWORK NFT Bridge.

Signing operations can be done concurrently (in parallel) without impacting security. The FROST protocol is considered secure if an adversary controls up to $t-1$ signers.

Compared with other Schnorr based Threshold protocols, FROST looks fast (1 round of signing), is parallel secure, and requires at least $t$ signers. FROST is less finality robust than "Stinsol Strobl", should $n-t+1$ signers misbehave. It means that if malicious adversaries control enough signers that the benevolent ones can never reach the threshold, consensus will never be reached, and the transactions will not get through. For example, in a pool of ten signers with a threshold of 7 out of 10, if the adversaries control at least four signers, the threshold of 7 cannot be reached $10-4=6$.

	Rounds	Robust	Req.Signers	Parallel Secure
Stinsol Strobl	4	Yes	$t$	Yes
Gennaro et al.	1+preprocessing	No	$n$	No
FROST	1+preprocessing	No	$t$	Yes

Pic.1 Schnorr Comparative Table

Schnorr quick recap

Step	Signer	Exchange	Verifier	Explanation
1	$(x,Y)\leftarrow KeyGen()$			SK1 = Private ($x$) & PK = public ($Y$2) keys generation using a DKG Protocol3
2		$\xleftarrow[]{\text(m,~ Y)}$		The verifier wants a message $m$ to be signed
3	$k \leftarrow Z_q$			A secret unique nonce is generated
4	$\mathbb{R} = g^k \in \mathbb{G}$			A commitment to the nonce is generated
5	$c = H(\mathbb{R}, Y, m)$			A challenge is computed by hashing the commitment, PK, and the message
6	$z = k + c \times x$			Response is the nonce plus the product of the challenge and the SK
7		$\xrightarrow[]{\text(m,\sigma = (\mathbb{R}, z))}$		The signed message as the commitment & the response are returned to the Verifier
8			$c = H(\mathbb{R}, Y, m)$	The verifier calculates the challenge
9			$\mathbb{R}' = g^z \times Y^{-c}$	The verifier derives the expected commitment
10			$\mathbb{R}' \stackrel{?}{=} \mathbb{R}$	If the derived commitment matches the one from the signature, the signature is valid

Pic.2 Schnorr Multisignature

FROST Preprocessing

Step	Signer(i)	Exchange	Round Leader4	Explanation
1	$((d_{ij}, e_{ij}), ~ ...) \leftarrow \mathbb{Z}^*_q \times \mathbb{Z}^*_q$			Every signer generates a tuple of 2 nonces.
2	$(D_{ij}, E_{ij}) = (g^{d_{ij}}, g^{e_{ij}})$			Then they generate 2 commitments to the above nonces.
3	Store $((d_{ij}, D_{ij}),(e_{ij}, E_{ij})), ~ ...$			They store those values locally.
4		$\xrightarrow{\text((D_{ij}, E_{ij}), ~ ...)}$		If it is the 1st round, they publish the 1st commitments' round.
5			Store $((D_{ij}, E_{ij}), ~ ...)$	The round leader stores the commitments locally.

FROST signature built over Schnorr

Step	Signer(i)	Exchange	Round Leader	Explanation
1			$B = ((1,D_1,E_1),...,(t,D_t,E_t))$	The round leader has collected enough signer commitments.
2		$\xleftarrow{(m,B)}$		The leader requests a message signature from the signers.
3	$\rho_{\ell} = H_1(\ell,m,B), \\ \ell, \in S$5			The signers compute the challenge
4	$\mathbb{R} = \prod_{\ell \in S}D_{\ell} \times (E_{\ell})^{\rho_{\ell}}$			Signers generate the commitment as a product of the binding factors
5	$c = H_2(\mathbb{R},Y,m)$			Every signer generates a challenge
66	$z_i = d_i + (e_i \times \rho_i) + \lambda_i \times s_i \times c$			Then they generate the response as a combination of the 2 nonces & the binding factor, secret share & the challenge
7		$\xrightarrow{Z_i}$		Each signer sends the response to the round leader
8			$\sigma = (\mathbb{R},Z = \sum Z_i)$7	The round leader submits a signed transaction to the blockchain

---

1. The abbreviation $SK$ is often used to denote the private or Secret Key. While $PK$ is used to denote the Public Key.↩
2. $Y$ is a joint public key, while each signer holds a secret share $s_i$ and a public share $Y_i$. For example, private and public keys of the signers, generated with the elliptical curve cryptography, can be used as $s_i$ and $Y_i$.↩
3. A DGK Protocol is an $n-wise$ SSS (Shamir Secret Sharing) protocol, where each participant is a dealer.↩
4. Round Leaders are algorithmically elected in every round. It ensures leader rotations, eliminating a permanent signature aggregator in XP.NETWORK bridge by contrast with some other FROST implementations.↩
5. The signature format & verification is identical to a single party Schnorr↩
6. This step $d_i + (e_i \times \rho_i)$ cannot be inverted by an adversary who sees the response but does not know $(d_i, e_i)$↩
7. The binding factor $\rho$ binds the shares to index $\ell$, the message $m$ and the commitments tuples $B$. This is the reason why FROST is secure against attacks.↩