An exciting update from myself and @benediamond ( https://t.co/bKwowXYcMB). We show that the 𝘶𝘱-𝘵𝘰-𝘤𝘢𝘱𝘢𝘤𝘪𝘵𝘺 proximity gaps conjecture is 𝗳𝗮𝗹𝘀𝗲. More precisely, given any pair c, d we construct codes whose error grows faster than nᶜ / (q ⋅ (ρ η)ᵈ).

Amazing results by Rohan and Venkat! In a week of negative news about proximity gaps, they show that folded RS codes, univariate multiplicity codes, random linear codes and randomly punctured RS codes have mutual CA *up to capacity*!

If someone entirely or partially proves the updated conjecture in the future, we could always move back and reap the benefit.

The bigger question is to what extent do we trust an "updated conjecture" which adjusts the conjecture down to our upper bound or should ZK move away from the conjecture back to the proven lands and just eat the higher query cost.

What we have shown is that the conjecture is false. In particular we give an upper bound on what 𝘻/𝘕 can be which is a little (though not a lot) lower than 1/2 (and corresponds to ~103 queries).

When the code has rate 1/2 (whatever that means), it's been proven that 𝘻/𝘕 = 1/4 (corresponds to ~240 queries) is possible with very small ε and 𝘻/𝘕 = (2 - √2)/2 (~200 queries) with larger ε. The conjecture was that 𝘻/𝘕 = 1/2 (~100 queries) is possible with very small ε.

In general, when using a (𝘻/𝘕, ε)-proximity gap, then each 𝘲𝘶𝘦𝘳𝘺 has a 𝘻/𝘕 probability of catching a malicious prover. Hence the larger we can make 𝘻/𝘕 the better.

In the example here, they would win if we only ever chose 𝘪 = 0, 1. So, every 𝘲𝘶𝘦𝘳𝘺 here has a 2/4 probability of catching the prover. This means we would need ~100 queries to have a < 2⁻¹⁰⁰ probability of accepting this false claim.

Each 𝘲𝘶𝘦𝘳𝘺, we pick a random integer 𝘪 from 0 to 3 and the prover reveals the entry in location 𝘪. So if we pick 𝘪 = 0, 1 the prover reveals a 0. If we pick 𝘪 = 2, 3 the prover reveals a 6 or a 1. A malicious prover wins if we accept a word which is not a code word.

How does this relate to proofs? Essentially at some point in the proof, we want to check if some word is equal to a particular code word. But we are only able to randomly sample its entries. In the example above, maybe we receive 0061 and the prover claims it is equal to 0000.

A code has a (𝘻/𝘕, ε)-proximity gap if, given two words 𝘻-far from the code, the probability that a combination of those words is less than 𝘻-far from the code is < ε. For applications to ZK, we usually set ε≈2⁻¹⁰⁰ (or smaller) and then ask how large can we make 𝘻?

Additionally, we have some way, given a random letter from the alphabet to use it to linearly combine two words into one. It doesn't matter for us right now how this procedure works, just that it exists.

Given any word, the distance to the code is the minimum distance to any word in the code. E.g. 4444 has distance 0 to the code (it's already in the code), 0061 has distance 2 (it's close to 0000) and 0123 has distance 3.

A 𝘤𝘰𝘥𝘦 is a special subset of all words. For example, the set of words all of whose entries are equal. So 4444 is part of the code but 0061 and 0123 are not.

For example our alphabet might be the numbers 0 to 7 and 𝘕 might be equal to 4 in which case some example words would be 4444, 0061, 0123. The distance between two words is the number of unequal entries. So 0061 and 0123 would have distance 3 as only the first entries are equal.

Our result concerns proximity gaps over codes so let us start with defining these. Fix an 𝘢𝘭𝘱𝘩𝘢𝘣𝘦𝘵 and an integer 𝘕. Then a word will contain 𝘕 letters each from the alphabet.

It's basically impossible to give a meaningful rundown of our result avoiding all mathematics so we are going to have to define some things.

TLDR: (0 math version) zkSNARKs relying on the conjecture have to become a little slower/larger (~1-3%). They may however want to stop relying on the conjecture which would translate to a larger increase in proof time/size. zkSNARKs not relying on the conjecture are unaffected.

This post got a little more traction that I was expecting. Due to this, I thought it might be useful to jump back in try to give a sense of what our results entail skipping as much of the mathematics as possible. (Warning, long thread ahead)

What will we see in the production projects using Starks going forward? double proof size for starks under provable security? 2-3% increase in proof size under new conjecture, as suggested in table 1 of the paper? No changes for now as there is not a (aiui) constructive attack on

In light of these results, the ZK space should seriously consider operating only in proven regimes.