0xPARC

In many SNARKs, we arrange our witness into columns. In code based SNARKs (informally STARKs), each of these columns is encoded using an error correcting code. The proof shows that each of these columns is sufficiently close to the code using a proximity test like FRI. Rather than showing this separately for each column, we would like to be able to batch the proximity tests. To do this, we would like to be able to argue something like: If a random linear combination of the columns is close to the code, then each column is itself close to the code with high probability. Then we could run the proximity test once on the linear combination. We say that a set 𝑆 S exhibits a proximity gap with respect to a property 𝜙 ϕ if either As an example, consider the set of all values of a degree 𝑘 k polynomial 𝑆 = { 𝑓 ( 𝑥 ) : 𝑥 ∈ 𝐹 } S={f(x):x∈F} and the property 𝜙 ( 𝑥 ) = ⊤ ϕ(x)=⊤ if 𝑓 ( 𝑥 ) = 0 f(x)=0. Either, 𝑓 ( 𝑋 ) = 0 f(X)=0 identically, in which case all 𝑓 ( 𝑥 ) = 0 f(x)

In many SNARKs, we arrange our witness into columns. In code based SNARKs (informally STARKs), each of these columns is encoded using an error correcting code. The proof shows that each of these columns is sufficiently close to the code using a proximity test like FRI. Rather than showing this separately for each column, we would like to be able to batch the proximity tests. To do this, we would like to be able to argue something like: If a random linear combination of the columns is close to the code, then each column is itself close to the code with high probability. Then we could run the pr