Threshold Cryptography II: Unidentifiability in Decentralized FROST Implementation

The second post in our Threshold Cryptography series explores the FROST threshold signing protocol, as proposed in FROST: Flexible Round-Optimized Schnorr Threshold Signatures [1], and highlights a potential issue that arises when implementing the protocol in a decentralized setting. This issue allows a malicious participant to send inconsistent nonce commitments, leading to honest participants to be falsely accused of misbehavior.

FROST is a novel threshold signature scheme based on the Schnorr signature, so we will begin by reviewing the fundamentals of Schnorr signature.

Schnorr Signature

A Schnorr signature over a message $m$ using a secret key $s$ and its corresponding public key $Y = s \bullet g \in G$ involves the following steps, where the group $G$ consists of elliptic curve points generated by the generator $g$ of a large prime order $q$ and $\bullet$ denotes the scalar multiplication on curve points.

Signature Generation

Sample a random unused nonce $r$ from $\mathbb{Z}_q^*$ (i.e., nonzero elements in the prime field $\mathbb{Z}_q$), and compute the nonce commitment $R = r \bullet g \in G$ .
Calculate the challenge scalar $c = H(R, Y, m)$ , where $H$ is a cryptographic hash function.
Compute the response $z = r + c \cdot s$ mod $q$ .
The signature is $\sigma = (R, z)$ where $R$ is a curve point $G$ and $z$ is a scalar $\mathbb{Z}_{q}$ .

The signature generation process is incorporated in the formula modified from the one in Notes on Threshold EdDSA/Schnorr Signatures [3], Page 9.

1 Graph

Signature Verification

Given signature $\sigma = (R, z)$ :

Compute the challenge scalar $c = H(R, Y, m)$ .
Then compute commitment $R' = z \bullet g - c \bullet Y$ , where $\bullet$ denotes scalar multiplication and $-$ denotes the curve point subtraction.
The signature is valid if $R' = R$ .

FROST Threshold Signature Scheme

The FROST protocol specifies a threshold Schnorr signature scheme executed in three phrases over two communication rounds. It assumes a secret key $s$ is shared among $n$ participants via key distribution with a trusted dealer or distributed key generation (as described in Threshold Cryptography I: Distributed Key Generation [4]) such that any subset of $t+1$ or more participants are able to reconstruct the secret key.

In both FROST [1] and RFC 9591 [2], the protocol incorporates a semi-trusted signature aggregator (SA) to enhance efficiency. The SA is a participant or an external entity, depending on implementation.

2 Graph

The protocol is instantiated with a generator $g$ on an elliptic curve $G$ of large prime order $q$ , and operates over the finite field $\mathbb{Z}_q$ and its multiplicative subgroup $\mathbb{Z}_q^*$ (i.e., nonzero elements in $\mathbb{Z}_q$). Two hash functions, $H_1$ and $H_2$ , map arbitrary strings to $\mathbb{Z}_q^*$ .

1. Nonce Pair Generation

Each participant $P_i$ generates an unused nonce pair $(d_i, e_i)$ with each in $\mathbb{Z}_q^*$ along with its commitments $(D_i , E_i)$ such that $D_i = d_i \bullet g$ and $E_i = e_i \bullet g$ .

2. Signing

SA selects a subset $S$ of $t+1$ distinct participants to join the signing process, then computes the public key $Y = \sum_{i \in S} Y_i$ of the group of these participants, where $Y_i$ is the public key share of $P_i$ that is publicly known.
SA creates an ordered list $B = <(i, D_i , E_i)>$ of the participant index and nonce commitments where $i \in S$ .
SA broadcasts $(m, B)$ to all the participants, where $m$ is the message.
Upon receiving $(m, B)$ , each participant $P_i$ validates message $m$ and checks that all nonce commitments are in $G$ but are not the identity.
Then $P_i$ calculates the binding values $\rho_i = H_1(i, m, B)$ , $i \in S$ , group commitment $R = \sum_{i \in S} (D_i + \rho_i \bullet E_i)$ and challenge $c = H_2(R, Y, m)$ .
$P_i$ then computes its signature share $z_i = d_i + \rho_i \cdot e_i + c \cdot \lambda_i \cdot s_i$ with its Shamir secret share $s_i$ and multiplied by the Lagrange coefficient $\lambda_i = \prod_{j=1, j \neq i}^{t+1} \frac{p_j}{p_j - p_i}$ to convert the Shamir secret share into additive secret share, and nonce pair $(d_i, e_i)$ .
Finally, $P_i$ sends $z_i$ to the SA and deletes the used nonce pair and commitments.

3. Signature Share Aggregation

For each $i \in S$ , SA computes $\rho_i = H_1(i, m, B)$ , $R_i = D_i + \rho_i \bullet E_i$ , then aggregates the group commitment $R = \sum_{i \in S} R_i = \sum_{i \in S} (D_i + \rho_i \bullet E_i)$ . The challenge is computed via $c = H_2(R, Y, m)$ .
Each signature share $z_i$ is verified through $R_i = z_i \bullet g - (c \cdot \lambda_i) \bullet Y_i$ , where $Y_i$ is the $P_i$’s public key share $Y_i = s_i \bullet g$ and $\lambda_i = \prod_{j=1, j \neq i}^{t+1} \frac{p_j}{p_j - p_i}$ is the Lagrange coefficient. This corresponds to individual Schnorr signature share verification. If any check fails, the corresponding $P_i$ is identified as misbehavior and the process is aborted.
Upon successful verification, the final signature is aggregated as $(R, z)$ where $z = \sum_{i \in S} z_i$ .

Unidentifiability Issue

In some implementations, the protocol is executed in a decentralized manner by eliminating the signature aggregator for ease of implementation. Each participant independently broadcasts their nonce commitments and signature shares to all other participants.

The Issue

Without a signature aggregator, participants may receive inconsistent nonce commitments from a malicious participant. As in Section 7.5 of RFC 9591 [2], this could possibly lead to an invalid signature:

“The requirements for the underlying network channel remain the same in the setting where all participants play the role of the Coordinator, in that all exchanged messages are public and the channel must be reliable. However, in the setting where a player attempts to split the view of all other players by sending disjoint values to a subset of players, the signing operation will output an invalid signature. To avoid this DoS, implementations may wish to define a mechanism where messages are authenticated so that cheating players can be identified and excluded.”

In addition to the DoS attack, this version of FROST implementation loses its identifiability feature. Even worse, it also enables a malicious participant to falsely implicate honest participants as misbehaving.

By sending the different commitments to subsets of the group, the malicious participant is able to partition the participants into divergent views of the set of nonce commitments $B = <(i, D_i , E_i)>$ , $i \in S$ .
Each participant generates its signature share based on its local view of $B = <(i, D_i , E_i)>$ , including the nonce commitment received from the malicious participant.
Consequently, signature shares from participants with differing views become invalid during verification, causing honest participants to be incorrectly flagged as misbehavior.
Depending on the specific operations later, the worst scenario would allow malicious actors to kick out honest participants.

An Example

Let’s consider a case with 4 participants, where Participant 1 is malicious and the others are honest.

Participant 1 sends inconsistent nonce commitments: $(D_1, E_1)$ to Participants 2 and 3, and $(D'_1, E'_1)$ to Participant 4.
Each participant then computes its signature share based on its local view of the nonce commitments.
During the signature verification,
- Verification of the signature share of participant 4 fails in participants 2 and 3, and it could also fail in participant 1 as it’s malicious.
- Verification of the signature share of participant 2 or 3 fails in participant 4 depending on the order of arrival of the message.
- Verification of the signature share of participant 1 is successful in all participants as it could send different signature shares based on the receiver’s local view of the nonce commitment.
As a result, the honest Participant 4 will be falsely accused of misbehavior.

3 Graph

This enables the malicious participant to remain undetected while falsely implicating an honest participant as misbehavior.

To mitigate this issue, the protocol may incorporate an additional round in which each participant verifies that all received nonce commitments are consistent across the network. If any inconsistency is detected, the protocol aborts immediately.

This mitigation relies on the assumption that at least two participants are honest, ensuring that any deviation from consistency will be detected. While it may be possible to isolate the group of honest participants, it is not feasible to isolate a single honest party without the others noticing the discrepancy.

Conclusion

This post reviewed the Schnorr signature and its threshold signature scheme, FROST protocol with signature aggregator role, highlighting challenges in decentralized implementations without an aggregator. The next three posts will cover the ECDSA threshold signature scheme in GG18 [5] and its implementation in Binance's Go-based library, tss-lib [6].