A survey of vulnerabilites and attacks related to the Fiat-Shamir transformation in modern zero-knowledge proof systems, including:
- Implementation flaws.
- Applying the Fiat-Shamir transformation is itself a flaw.

## 0. Fiat-Shamir transformation

### Introduction

Fiat-Shamir transformation is a technique for removing interactivity from interactive, public-coin proof systems.

In these systems, the verifier generates and sends to the prover some random values acting as challenges which can only be solved if the statement being proved is correct (the soundness property). Usually, if these random values are known in advance, the prover will be able to forge proofs for incorrect statements.

The way the Fiat-Shamir transformation works is that it replaces random values with outputs from a cryptographic hash function, hashing the verifier context whenever randomness is needed. Public parameters, the statement being proved, previously exchanged messages, ... all contribute to this context. Since randomness is removed, the verifier becomes deterministic and simulatable, thus making the proof system non-interactive.

### Security concerns

The convenience brought by the Fiat-Shamir transformation does not come without a price. It is fair to say that some security has been sacrified due to a larger attacking surface when applying the Fiat-Shamir transformation. Not only the hash function in use must be collision-resisant, what will be fed into that hash function is also a big concern.

Recall that in probabilistic proof systems, knowing the verifier challenges in advance help the prover to forge proofs. As a result, vulnerabilities in Fiat-Shamir implementation usually make the security of these systems completely broken.

Another important thing to notice is that the Fiat-Shamir transformation allows brute-forcing attack. This means, a malicious prover does not pay for a failed attempt to forge proof. She/he can simply make another attempt until the attack is succeed. What follows is that if an implementation flaw increases the proof system's soundness error from a negligible value to, say, $\frac{1}{2^{32}}$, forging proof will become very practical.

---

For each of the remaining sections, we will describe in detail one type of practical Fiat-Shamir implementation flaw. More precisely, we will identify the root cause, provide methods to forge proof under a vulnerable cryptographic scheme, and give suggestions on remediation. Additionally, in the final section, we will also mention other non-implementation vulnerabilities, which means, applying Fiat-Shamir is itself a flaw and may lead to proof forgery attacks.

## 1. Missing public statement

This type of vulnerability, also known as Frozen Heart, was first published by Jim Miller in April 2022.

### 1.1 Root cause
Fiat-Shamir hashing context always includes the public statement to be proved. If this is not the case, a malicious prover will be able to change the statement without changing the future challenges. This may lead to severe consequences if the prover can make profit from proving any false statement in a large set.

### 1.2 Case study: PLONK

#### The scheme
PLONK [1] (Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge) is a SNARK released in 2019 by Ariel Gabizon, Zachary J. Williamson and Oana Ciobotaru. Since then, PLONK has been widely adopted due to its extensibility nature to support beyond-arithmetic polynomial constraints such as permutation (polynomials' evaluations over a domain is the same as others' under an optionally predefined permutation) or lookup (each evaluation of a polynomial over a domain is contained in a table possibly made up from the evaluations of another polynomial).

This section gives only some of the main points on the technical side of PLONK that are required for understanding the attacks. Additional details will be provided on the fly when needed. For the full specification, please refer to [1].

First of all, PLONK makes use of a polynomial commitment scheme that allows a prover to commit to a polynomial and later on, prove to a verifier the correctness of the committed polynomial's evaluations at certain points chosen by the verifier.

Originally designed to prove the correctness of computation over arithmetic circuits that support only addition and multiplication gates, the (simplified) PLONK prover algorithm is as follows:

- Round 1: Compute 3 wire polynomials $a(X), b(X), c(X)$ and output their commitments.
- Round 2: Derive permutation challenges $\beta, \gamma$ from $H(transcript)$, compute permutation polynomial $z(X)$ and output its commitment.
- Round 3: Derive quotient challenge $\alpha$ from $H(transcript)$, compute quotient polynomial $t(X)$ and output its commitment.
- Round 4 & Round 5: Derive evaluation challenge $\xi$ from $H(transcript)$, evaluate the committed polynomials at desired points ($\xi$ and others) and output the evaluations together with their proofs of correctness.

Finally, the PLONK verifier verifies that:

- All polynomial evaluation proofs are correct.
- All polynomial constraints are satisfied at $\xi$. In other words, the following aggregated constraint must hold at $\xi$:

$$
\begin{align*}{\tag{1}}
t(X) &= \frac{1}{Z_{H}(X)}(a(X)b(X)q_{M}(X) + a(X)q_{L}(X) + b(X)q_{R}(X) + c(X)q_{O}(X) + P(X) + q_{C}(X)) \newline
&+ \frac{\alpha}{Z_{H}(X)}((a(X) + \beta X + \gamma)(b(X)+\beta k_{1}X + \gamma)(c(X)+\beta k_{2}X +\gamma)z(X)) \newline
&+ \frac{-\alpha}{Z_{H}(X)}((a(X) + \beta S_{\sigma 1}(X) + \gamma)(b(X)+\beta S_{\sigma 2}(X) + \gamma)(c(X)+\beta S_{\sigma 3}(X) +\gamma)z(X\omega))\newline
&+ \frac{\alpha^2}{Z_{H}(X)}((z(X) - 1)L_{1}(X))
\end{align*}
$$

Note that in the equation above, $a(X), b(X), c(X), z(X), t(X)$ are known only to the prover. Other terms are public parameters and $P(X)$ is the polynomial constructed from public input/output signals of the circuit.

#### The flaw

The vulnerability is fairly simple: $P(X)$ is not included in the Fiat-Shamir hashing context. This means, changing $P(X)$ will not result in re-randomization of the challenges ($\beta,\gamma,\alpha,\xi$).

#### The attack

The attack strategy is as follows.
1. Pick arbitrary $a(X), b(X), c(X), z(X), t(X)$. All challenges are now determined.
2. Deduce from (1) a value $p_\xi$ such that the constraint will hold at $\xi$ if $P(\xi)=p_\xi$.
3. Choose suitable $P(X)$ such that $P(\xi)=p_\xi$.
4. Follow the rest of the prover algorithm (Round 4 & 5) as usual.

Note that, Step 3 is only accomplishable if there is at least one public signal, say $P(1)$, allowed to be randomized so that $P(\xi)$ and other public signals can be fixed to desired values. Whether or not this condition can be satisfied is application-specific. In practice, it is actually very likely to hold. For example, when withdrawing money from Tornado Cash, a popular privacy-preserving ZK application, there is a randomizable public signal called nullifier that acts as a nonce to prevent double-spending. Another example is that in every scalability ZK application, there is always a public signal representing the next system state hash after processing a block of transactions. This signal is randomizable, and if it gets a random value, the layer-2 system will be frozen (falling into an unknown state).

### 1.3 Vulnerable libraries
Not only PLONK, a lot of proof systems and their implementations are vulnerable to this flaw. For more details, please refer to [2].

### 1.4 Remediation
Always include the public statement being proved in the Fiat-Shamir hashing context.

## 2. Ambiguous encoding
The first attack to the Ambiguous Encoding flaw was discovered by Nguyen Duy Hieu et al. It was published at Blackhat USA 2023 as part of TSSHOCK.

### 2.1. Root cause
Deriving a random challenge with Fiat-Shamir transformation always involves some encoding scheme applied to an `object`, usually a list of integers. The encoding result `E(object)` is then fed to a cryptographic hash function `H` (see Figure 2.1).

_Figure 2.1: Applying the Fiat-Shamir transformation always involves an encoding scheme._

In case the encoding is ambiguous, i.e., different objects may have the same `E(object)`, the whole transformation process will never be collision-resistant: one can choose `object1` and `object2` such that `H(E(object1)) == H(E(object2))` regardless of `H`.

### 2.2 Case study: `dlnproof`
#### The scheme

`dlnproof` is an argument system used for proving knowledge of a discrete log modulo a composite number $N$. The protocol is very similar to Schnorr's and is given in Figure 2.2. There are 2 main differences:
- The group order $\phi(N)$ is unknown to the verifier.
- The challenge space is only $\{0, 1\}$. As a result, proof repetition is required to achieve negligible soundness error. This is done in parallel: the prover sends $\alpha_0, \alpha_1,...$, the verifier replies with $c_0, c_1, …$, and the prover sends $\tau_0, \tau_1, …$. The verifier only accepts if all triples $(\alpha_i, c_i, \tau_i)$ are valid. Note that the Fiat-Shamir hashing context consists of $N, g, h, \alpha_0, \alpha_1, …$.

_Figure 2.2: Schnorr-similar protocol for proving knowledge of $\log_g h$ modulo $N$_.

The interesting thing about `dlnproof` is that it is a building block of many threshold ECDSA libraries, and the Ambiguous Encoding flaw eventually makes the security of the vulnerable libraries completely broken: a malicious party can recover the TSS group private key using only a single signature. For more details, please refer to [3].

#### The flaw

The following Golang code snippet is taken from a vulnerable library:

for i := range in {
    data = append(data, ptrs[i]...)
    data = append(data, hashInputDelimiter) // safety delimiter
}

Here, `data` holds the result of encoding a list containing $N, g, h, \alpha_0, \alpha_1,...$. It is constructed by joining `ptrs[i]` with a constant delimiter. In fact, each `ptrs[i]` is the byte representation corresponding to one of the integers. Clearly, this encoding scheme is ambiguous. For example, let the delimiter be `"(DELIM)"`, then `["a(DELIM)a", "a"]` and `["a", "a(DELIM)a"]` are both encoded to `"a(DELIM)a(DELIM)a"`.

#### The attack
The idea to forge proof is as follows:
1. Prepare the payloads $\stackrel{0}{\alpha}, \stackrel{1}{\alpha}$ to bypass the cases $c=0$ and $c=1$, respectively. Note that knowing $c$ in advance allows `dlnproof` to be forged.
2. The byte representation of $\stackrel{0}{\alpha}, \stackrel{1}{\alpha}$ satisfy Figure 2.3.
3. Shuffle $\alpha_i$ (see Figure 2.4).

_Figure 2.3: Byte representations of $\stackrel{0}{\alpha}, \stackrel{1}{\alpha}$_.

_Figure 2.4: An example of alpha-shuffling in the case #repetitions = 4_.

Note that shuffling the list of $\alpha_i$ does not change its byte representation because of the vulnerability. Consequently, the challenges $c_i$ are also not changed.

### 2.3 Vulnerable libraries

As of mid 2023, all the following projects were vulnerable (we had working PoC exploit for each project, either on its main branch or latest release):
- `tofn` (Axelar)
- `tss-lib` (Binance)
- `FastMulThreshold-DSA` (Multichain)
- `tss-lib` (Swingby)
- `multi-party-sig` (Taurus)
- `tss-lib` (Thorchain)
- `multi-party-ecdsa` (Zengo)

For more details, please refer to [3].

### 2.4 Remediation
Always use a proper encoding scheme (unambiguous) combined with a collision-resistant hash function when carrying out the Fiat-Shamir transformation.

## 3. Missing prover messages
### 3.1 Root cause

In a multi-round protocol, it is important that all messages output by the prover in previous rounds are included in the hashing context. Missing any of them may lead to proof forging, as a malicious prover can rewind and change that message without affecting the currently generated challenge.

### 3.2 Case study: PLONK
#### The scheme

The basics of PLONK are already described in Section 1.2.

#### The flaw

The following Javascript code snippet is taken from a vulnerable library:

const transcript1 = new Uint8Array(zkey.nPublic*n8r + G1.F.n8*2*3);
for (let i=0; i<zkey.nPublic; i++) {
    Fr.toRprBE(transcript1, i*n8r, A.slice((i)*n8r, (i+1)*n8r));
}
G1.toRprUncompressed(transcript1, zkey.nPublic*n8r + 0, proof.A);
G1.toRprUncompressed(transcript1, zkey.nPublic*n8r + G1.F.n8*2, proof.B);
G1.toRprUncompressed(transcript1, zkey.nPublic*n8r + G1.F.n8*4, proof.C);

ch.beta = hashToFr(transcript1);

const transcript2 = new Uint8Array(n8r);
Fr.toRprBE(transcript2, 0, ch.beta);
ch.gamma = hashToFr(transcript2);

...

const transcript3 = new Uint8Array(G1.F.n8*2);
G1.toRprUncompressed(transcript3, 0, proof.Z);
ch.alpha = hashToFr(transcript3);

...

const transcript4 = new Uint8Array(G1.F.n8*2*3);
G1.toRprUncompressed(transcript4, 0, proof.T1);
G1.toRprUncompressed(transcript4, G1.F.n8*2, proof.T2);
G1.toRprUncompressed(transcript4, G1.F.n8*4, proof.T3);
ch.xi = hashToFr(transcript4);

...

const transcript5 = new Uint8Array(n8r*7);
Fr.toRprBE(transcript5, 0, proof.eval_a);
Fr.toRprBE(transcript5, n8r, proof.eval_b);
Fr.toRprBE(transcript5, n8r*2, proof.eval_c);
Fr.toRprBE(transcript5, n8r*3, proof.eval_s1);
Fr.toRprBE(transcript5, n8r*4, proof.eval_s2);
Fr.toRprBE(transcript5, n8r*5, proof.eval_zw);
Fr.toRprBE(transcript5, n8r*6, proof.eval_r);
ch.v = [];
ch.v[1] = hashToFr(transcript5);

...

const transcript6 = new Uint8Array(G1.F.n8*2*2);
G1.toRprUncompressed(transcript6, 0, proof.Wxi);
G1.toRprUncompressed(transcript6, G1.F.n8*2, proof.Wxiw);
res.u = hashToFr(curve, transcript6);

Here we have:

- $\beta$ = $H(\text{public inputs, commitments of } a(X), b(X), c(X))$
- $\gamma$ = $H(\beta)$
- $\alpha$ = $H(\text{commitment of } z(X))$
- $\xi$ = $H(\text{commitment of } t(X))$
- $v$ = $H(\text{polynomial evaluations})$
- $u$ = $H(\text{polynomial evaluation proofs})$

Certainly, this Fiat-Shamir transformation is insecure.

#### The attack

The goal is to make (1) satisfied when $X = \xi$ for arbitrary $P(X)$. Because of the flawed Fiat-Shamir transformation, it is possible to do so:

1. Pick arbitrary $t(X)$ and compute the evaluation challenge $\xi$ which only depends on $t(X)$.
2. Choose $z(X)$ such that it is evaluated to $0$ at $\xi$ and $\xi\omega$ . This will eliminate $\beta, \gamma$ from (1). Now $\alpha$, which only depends on $z(X)$, is also determined.
3. Finally, pick suitable $a(X), b(X), c(X)$ such that $a(\xi), b(\xi), c(\xi)$ satisfy (1). The rest of the prover algorithm (round 4 & 5) can then be processed normally.

### 3.3 Vulnerable libraries
- SnarkJS (0.4.0 - 0.6.11)

### 3.4 Remediation
Always make sure that all prover messages in previous rounds contribute to the Fiat-Shamir transformation process. One possible approach is to feed the last generated challenge into the hash function. This makes the outputs from all previous rounds recursively involved in the computation of the current challenge, thus eliminating the vulnerability.

## 4. Non-implementation vulnerabilities

### 4.1 Grinding attack

#### 4.1.1 Root cause

The soundness property of an interactive proof system means that a dishonest prover cannot convince the verifier if the statement being proved is false except with some small probability. It is always possible to amplify soundness until the soundness error becomes negligible. This can be achieved by repeating the proof and accepting only if all proofs are valid.

When apply Fiat-Shamir transformation to an interactive proof, the non-interactive version also inherits the soundness error. However, non-interactive proof allows the prover to generate the challenge deterministically by applying hash function to a context. In this case, the malicious actor can just try different contexts until they find a challenge that suits the false statement without being detected by the verifier.

#### 4.1.2 Details


_Figure 4.1: 3-message proof protocol._

To illustrate this concept, let's examine the 3-message non-interactive protocol (Figure 4.1). Given a false claim $x$, note that the first message $\alpha$ is controlled by the prover, when applying Fiat-Shamir transformation, the challenge $\beta$ can be brute-forced to fit the prover message $\gamma$.

<!-- Applying Fiat-Shamir to an interactive protocol with a soundness error of $2^{-λ}$, and computing $2^{b}$ hash evaluations, grinding attack will succeed with a probability of $2^{-λ+b}$. -->

#### Example

Consider this non-interactive Schnorr's protocol (Figure 4.2) where q is a 64 bits prime number.


_Figure 4.2: Non-interactive Schnorr's protocol_ [4].

*Completeness*: if $z = r + cx$ then $g^z = g^{r+cx} = g^r \cdot (g^x)^c = u \cdot h^c$.

For the malicious provers, who do not know the real value x, they can use the grinding attack to find a bad challenge c, and in this context, they would want c to be equal 0.

Grinding out a value of $c = H(g,h,u) = 0$ in a 64-bit space $(\phi(q))$ is trivial in today's world. After that, the cheating prover can simply set $z = r$ without knowing $x$. Hence, this allows the cheating prover to pass the verifier's check.

However, in the same bit setting for interactive Schnorr's protocol, the chance of the prover receiving a bad challenge (c = 0) from a verifier is technically impossible $({1 \over 2^{64}})$.

#### 4.1.3 Remediation

For an interactive protocol with proven knowledge soundness in a bit setting security context, when applying the Fiat-Shamir transformation, the corresponding protocol security needs to be reconsidered.

### 4.2 Multi-round security loss

#### 4.2.1 Root cause

As mention above, the soundness error of a proof system can become negligible if the proof is repeated for a multiple of times/rounds, regardless of how non-negligible the soundness error in each round is.

However, when applying Fiat-Shamir transformation to a proof system whose security is depends on repeating rounds, the security loss can be immense if the soundness error is not carefully proved.

#### 4.2.2 Details

A multi-round interactive protocol is the protocol with soundness error of ${1 \over n^λ}$ where ${1 \over n}$ is soundness error for each round and λ is the number of rounds.

#### Example

Take the multi-round interactive proof protocol described in Case study 2.2 and render it non-interactive by applying Fiat-Shamir transformation (Figure 4.2).


_Figure 4.2: Non-interactive Schnorr-similar protocol for proving knowledge of $\log_g h$ modulo $N$_.

Since the scheme only have soundness error $1 \over 2$ for each round, the cheating prover on expectation will have to use the grind attack only 2 times each round until he found the bad challenge c, allowing him to pass all verifer rounds without knowing the witness.

The risk of applying Fiat-Shamir transformation to said protocol is extremely catastrophic since the protocol security is reduce to $\lambda 2^n$ from $2^{\lambda n}$ where n is the security bits and λ is the number of rounds.

#### 4.2.3 Remediation

Its useful and sometimes crucial to turn an interactive argument into non-interactive one using Fiat-Shamir transformation, however when designing protocols, and choosing which protocol to uses, round-by-round soundness [5] of the protocol should be proven before applying Fiat-Shamir transform.

## References

[1] Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru. _PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge_.

[2] Quang Dao, Jim Miller, Opal Wright, Paul Grubbs. _Weak Fiat-Shamir Attacks on Modern Proof Systems_.

[3] Duy Hieu Nguyen, Anh Khoa Nguyen, Huu Giap Nguyen, Thanh Nguyen, Anh Quynh Nguyen. _TSSHOCK: Breaking MPC Wallets and Digital Custodians for \$BILLION\$ Profit_.

[4] Dima Kogan. _CS 355: Topics in Cryptography, Proofs of Knowledge, Schnorr’s protocol, NIZK_.

[5] Justin Holmgren. _On Round-By-Round Soundness and State Restoration Attacks_.