# Grinding in the Fiat-Shamir heuristic

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?

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.