Question about soundness after Fiat--Shamir transformation

[mpzajac]

Hi Team! Great work!

Do you intend to use Fiat--Shamir transformation to get a non-interactive argument?

If you do, let me note the following result by Attema, Fehr and Kloss (https://eprint.iacr.org/2021/1377.pdf). They shown the following. Let Prot be a \kappa sound interactive \mu-round protocol. Let's amplify its soundness to \kappa^t by t-fold parallel repetition. Denote by Prot-t the "folded" protocol. Next, let Prot-t-FS be Prot-t after Fiat-Shamir transformation, then there is an adversarial prover P^* which produces acceptable proof for invalid statement with probability about 1/2 Q^\mu \kappa^t / \mu^{\mu + t} where Q is the upper bound for the random oracle queries P^* can make. (We can also interpret Q as the upper bound for the number of operations P^* makes, say 2^80). (NOTE: Some additional conditions for this attack apply though, but I think your protocol follow them.)

Hence, in practice, where the non-interactive protocol is used (assuming use of the FS transform) soundness requires greater number of rounds than 3 proposed in Sec 3.4.3.

Alternatively, one could do soundness amplification by running the protocol sequentially what would increase the number of rounds. In that case, security loss introduced by the Fiat--Shamir transformation is roughly of factor (Q + 1). Hence, give the example from 3.4.3 increasing the number of repetitions from 3 to 5, assuming n < 2^21 and adversary who makes up to 2^86 operations should give the required security of about 2^-128.

[dlubarov]

Hello! Thank you for reporting this, it seems like a very important issue. I haven't had a chance to look at the paper yet, but will do when I can.

[dlubarov]

I haven't had time yet to really digest the framework of that paper, but I thought for now I'd just give my informal reasoning for why I think our uses of r-fold parallel repetition give s^r soundness.

As the IOP paper states, the soundness of an IOP with Fiat-Shamir is the state-restoration soundness of the IOP.

Clearly r-fold parallel repetition doesn't always give s^r state-restoration soundness. I think FRI is a good example. If we repeated the commit phase r times in parallel and it involved at least r rounds, an attacker could attack the first instance in the first round, attack the second instance in the second round, etc., taking only O(r s) total computational power.

The IOP paper mentions an upper bound on r for sound parallel repetition, but mentions that some IOPs are robust to such attacks (I assume they mean they achieve s^r state-restoration soundness). For example, I think it's clear that single-round IOPs (i.e. PCPs) are robust to such attacks, as only the initial state can be restored. Restoring the initial state would mean restarting the protocol, so state-restoration soundness just equals standard soundness.

An example where we use parallel repetition is for permutation checks. The prover commits to f(x) and g(x), which should be permutations of one another. Then we repeat this PLONK-esque IOP r times in parallel:

• The verifier samples gamma.
• The prover commits to Z(x), the cumulative product of (f(g^i) + gamma) / (g(g^i) + gamma).

Later, it is shown that Z(g*x) g(x) = Z(x) f(x) for x in <g>. Crucially, this constraint is checked for each of the r Z(x) polynomials. So if f(x) is not a permutation of g(x), the attacker would need attack all r instances of the IOP above. And since it only involves one verifier message, I think the hardness of that attack would be s^r.

Do you see any issues with this line of reasoning? If not, we can try to write up a more complete and rigorous version. (Though analyzing the whole protocol seems like a big task, since AFAIK there's no such existing analysis for any of the PLONK/FRI protocols we build on.)

[mpzajac]

I think you are right in saying that a single round IOP is state-restoration sound by default. However, I am not sure that you can lift the security of the whole protocol by repeating only its part. As far as I understand, similarly to the original Plonk, Plonky2 combines constraints of the circuit with the permutation argument check (in Plonk it is done in polynomial t using randomly sampled alpha). Hence, one does not need to "attack" r repetitions of the permutation argument, but can attack the combination phase. More precisely, the attacker may try multiple f-s, g-s, hoping for getting alpha that fits the verification equation, even though some of the permutation checks don't hold.

[dlubarov]

For that step where alpha is used to combine constraints, I would argue state-restoration soundness as

• We generate r alphas in parallel, so the prover can restore a state before or after that step; there's no state where some but not all alphas have been generated
• If the prover rewinds to the step before alphas are generated, clearly there's a s^r chance that all r alphas result in a combination that vanishes
• If some but not all alphas result in a combination that vanishes, that's okay, because we later use a quotient argument on each combination to check that it vanishes

Does that make sense? I think the key point is that for each sub-protocol we repeat in parallel, the larger protocol is designed to handle the case where r - 1 instances of that sub-protocol fail.

[mpzajac]

That's a very interesting discussion and I am learning a lot from it. I agree that you can simply send r alphas. However, I think the final soundness error is still greater than s^r. Namely, we are not asking "what's the probability that r randomly sampled alpha-s fit the adversary" but we ask "what's the probability that in Q trials there is one such that randomly picks r alpha's that fit the adversary", no?

[Therecanbeonlyone1969]

@mpzajac @dlubarov ... awesome exchange. I must admit I am not a theoretical cryptographer by training, so please excuse any stupid questions. I find the plonky2 approach fascinating -- it is a bit of "have your cake and eat it too" ;-)

Two questions:

• I found this paper https://arxiv.org/abs/2105.00801 by Berman et al. and was wondering if their proof of "Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence" would improve the soundness property if applied to plonky2?
• More pedestrian, what if one sacrificed speed a bit and introduced fuzziness either by e.g. randomly placing some higher-degree gates further away from the root, but adding as an input a filer polynomial that values those to zero, or introducing some random advice wires even though not needed and again "negating" them (decoupling) through e.g. an input. This would require an attacker to go both wide and deep when trying to find the right sequence of random alphas, no?

Again, I might be totally off my rocker here.

BTW, we are building an NFT platform that uses recursive zk-snarks for proof of authenticity and genealogy using Aztec's Barretenberg library. Since we need recursive snarks at scale, we are looking for optimizations. We have made advances such that we can multi-thread the library but are schlepping, a lot of PCD with us -> e.g. for a 4 generation NFT tree of generative art with 10 derivative artworks per wrt work in each generation, we have over 11,000 proofs to generate ... for one NFT tree. We hope there will be hundreds of thousands.

So my question is, have you checked if plonky2 can be multi-threaded? @dlubarov

[4l0n50]

Why is this issue still considered open? Because known results bound soundness error of any IOP compiled into a NIROP by O(n_queries*e_rbr + n_queries^2/2^{hash_size}), where e_rbr is the round-by-round soundness of the IOP (I don’t know if it’s explicitly shown somewhere, but it follows from [BCS16] and [CCH+18]). Attema et al. attack takes a multi round protocol and execute in parallel t >=r independent executions of the same protocol, where r is the number of rounds. Therefore, a malicious prover can fake a proof for each independent execution at each round with not-so-small-enough probability by brute force finding the right hash. IOPs like Plonky2 instead usually use parallel repetition of independent polynomial checks ( ) in a round-by-round fashion. In order to cheat, the adversary needs that each challenge in (c_1,..,c_t) = H(statement, transcrip_so_far) lies in a small set of roots and the attack will not work anymore. The attack might work if for example we naively compute t > number_of_rounds different proofs for the same statement. —— () The polynomial checks are not really performed by the verifier, but more an artifact of the security proof called the State function. The State function can be computed for any (statement, partial_transcript) pair and is such that: (1) x \notin L ⇒ State(x, null) = 0, (2) State(x, full_transcript) = 0 ⇒ Ver(x, corresponding_proof) = 0; and (3) For all partial_trascript and any f s.t. State(x, partial_transcript) = 0, Pr_c[State(x, partial_transcript||f||c)=1]<= e_rbr