I am using a simplified circuit for case demonstration purpose:
The bus statement to be proved is:
\([x_0,x_1]\) in [0] with \(bus_{id}\)=a,
this case has only one valid witness [0,0], with multiplicity to be 2
Original protocol:
The above statement essentially proves:
\(\frac{1}{\alpha -x_0}+\frac{1}{\alpha -x_1}=\frac{2}{\alpha}\)
where \(\alpha\) is a random value, obtained by the hash result of the witness \((x_0,x_1)\), this is the application of Fiat-Shamir transform.
Modified protocol
The above statement essentially proves:
\(\frac{1}{\alpha +a -\beta x_0}+\frac{1}{\alpha +a-\beta x_1}=\frac{2}{\alpha+a}\)
where \(\alpha, \beta\) are random values, obtained by the hash result of the witness \((x_1,y_1)\), \(bus_{id}=a\) is a hash of some circuit information, which can be consider as part of a statement to be proved.
attack of the modified protocol:
Since the \(bus_{id}=a\) is independent of the witness, it can be crafted in a way that let the verifier accepts a proof from an invalid witness, as shown below:
attacker wants to let verifier accepts \([x_0,x_1]=[2,3]\), attacker computes the hash result of the witness \([2,3]\) honestly and gets the result \(\alpha’, \beta’\)
attacker creates bus id \(a\) such that \(a = \frac{12\beta’}{5} – \alpha’\), assume attacker is able to find the pre-image of \(a\).
one can check the following equation can hold, verifer in this case accepts \([x_0,x_1]=[2,3]\).
\(\frac{1}{\alpha’ +a -\beta’ x_0}+\frac{1}{\alpha’ +a-\beta’ x_1}=\frac{2}{\alpha’+a}\)
The difference of the original and modified protocols.
in the original protocol, attacker can only convinced the verifier to accepts a wrong witness with probability \(\frac{1}{|\mathbb{F}|}\), while in the modified version, an attacker can convinces the verifier to accepts a wrong witness with probability 1, with the assumption that attacker can find the pre-image of the hash function.
At this point, one may already conclude the second protocol is not as secure as the first one, this is generally true especially when the added assumptions are easier to be broken than the assumption that the original protocol has.
To compare the two protocols more rigorously, let’s make their underlying assumptions more clear:
original protocol:
Assumption 1: the challenge is a random challenge, which means the hash function is complex enough to be almost equivalent to a random function. namely, the attack cannot predict the randomness before it choose any witness.
Modified protocol:
assumption 1: the above assumption
assumption 2: the attacker cannot find a pre-image of the function.
if assumption 1 and assumption 2 are equivalent, or assumption 2 is even harder to break than assumption 1, one can still conclude the two protocol may be at least equally secure, but the following reduction proves an attacker can break assumption 2 but couldn't break assumption 1, which means the modified protocol is easier to break than the original protocol.
reduction 1: attacker with ability to break assumption 1 can always break assumption 2
assumption 1 requires the attacker to find the struct of the hash function, turning a hash function to normal function, without the random property anymore, that means, give a witness \(x\), its hash result can be computed by a function directly: \(\alpha=f(x)\) (think it like f can be a high degree polynomial or something), if an attacker manages to do this, compute the pre-image of hash function is just compute the inverse of the function \(f\), thus assumption 2 break.
reduction 2: attacker with ability to break assumption 2, is not always able to break assumption 1.
if an attacker finds the pre-image of a certain value by doing brute force attack, it doesn’t mean it can find the structure of the hash function. so in this case, assumption 2 broken, but assumption 1 still holds.
Mitigation and More confusing points
The modified protocol is more like a weak Fiat-Shamir transform: the challenge is not generated by all the values that a prover can control, namely, the transcript doesn’t include all the values that can vary in a statement. There are many cases in the literature and practice that go wrong because of weak Fiat-Shamir problem, in zk field as well, see these papers 1,2,3.
The security analysis of protocols using weaker Fiat-Shamir is more complex than checking the security of the added assumption. The security definition can change to adaptive security, the security model can change, I would’t be able to give a security proof detailed to the security bits level in this case. so the best practice would be following the common practice and avoid this rabbit hole.
mitigation:
- using random linear combination to batch accumulators, the extra challenge is generated base on witnesses.
- or let the bus_id generated based on the witness as well
One can add a restriction that the bus_id is basically fixed value, it then restricts the freedom of the attacker crafting bus_id, but this mitigation is to "reduce the attack surface on implementation level", while the underlying cryptography is not secure in theoretical level, it is not recommended, but if you insist...
My wrong thought before: The modified protocol adds one more assumption, this assumption requires that break the protocol is equivalent to break the security property of the hash function, so the security level should go to the security level given by the hash function (this is where I was wrong), which means, if using SHA256 for generate a field element of length 124 bits, it should still give 124 bits security for the pre-image attack (this is about the security of the hash function), but this thought is wrong. The wrong part is I cannot just assume when one more assumption added in the system, the security just follows to the new assumption.