Grinding in the Fiat-Shamir heuristic

Question

The Fiat-Shamir heuristic is assumed to substitute public-coin messages from the verifier by hashes of the prover's messages until this point, i.e.: $$H(\alpha_1) = \beta_1, \\ H(\alpha_1, \alpha_2) = \beta_2,\\H(\alpha_1, \alpha_2, \alpha_3) = \beta_3,\\\vdots$$ where the $\alpha_i$'s are the prover's messages.

I understand why the Fiat-Shamir heuristic is proven to be secure in the ROM, however, in practise, the hash function $H$ is NOT an oracle, so what avoids the prover to grind over his messages to be able to forge a fake proof?

For instance, in a $\Sigma$-protocol there is only one message from the verifier $\beta_1 = H(\alpha_1)$. What if the prover grinds over some $\alpha_1'$ until he finds some input to the hash function such that $\beta_1$ lets him to obtain some advantage?

Why do we hash ALL the previous prover's messages to obtain the next non-interactive verifier message? Which is the problem of performing, for instance, $H(\alpha_i) = \beta_i$? Even worse, what if the prover can hash anything that he wants?

Answer 1

What avoids the prover to grind over his messages to be able to forge a fake proof?

We could ask exactly the same question with respect to a random oracle as well! What prevents the prover to grind over his messages until he can forge a fake proof? What you suggest can totally be done with a RO.

And the answer is: there should be a very small number of messages $\alpha_1$ such that $\beta_1 = H(\alpha_1)$ lets the prover have an advantage. In a typical $\Sigma$-protocol, for example, when the statement is not in the language (hence the prover is cheating), there is on average one $\alpha_1$ that allows the prover to cheat. (Exercise: show that this is the case for the $\Sigma$-protocol for DDH tuples, where the word is $(X,Y)$ and the witness is $x\in\mathbb{Z}_p$ such that $X = g^x$ and $Y = h^x$). Hence, if there are $2^c$ possible values $\beta_1$ (that's the challenge space), the malicious prover will have to compute $O(2^c)$ hashes to forge a fake proof. Now make $c$ big enough, and you get computational security.

Note that the grinding attack is still an important consideration: $\Sigma$-protocols have unconditional security, but at soon as you compile them in the ROM with Fiat-Shamir, they only have computational soundness. This means that the security parameter for soundness (the challenge space) must be adjusted accordingly: a 40-bit challenge space is fine for a $\Sigma$-protocol (since it gives a malicious prover a $2^{-40}$ statistical probability of successfully breaking soundness, which can be acceptable in practice), but broken for Fiat-Shamir (since breaking the compiled protocol requires $2^{40}$ operations, which is trivial to perform). Typically, we will use a challenge space about $2^{128}$ when using Fiat-Shamir.