Grinding in the Fiat-Shamir heuristic

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.