In new work with @AngusGruen, we show that the 𝘶𝘱-𝘵𝘰-𝘤𝘢𝘱𝘢𝘤𝘪𝘵𝘺 proximity gaps conjecture (Ben-Sasson–Carmon–Ishai–Kopparty–Saraf) is not true. This affects the security analysis of most zkVMs deployed today.

proximity gap result: the distance between my understanding and the latest findings is increasing exponentially

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

Amazing work by my brilliant coworker @AngusGruen and the equally formidable @benediamond ! Tldr: they disproved a security conjecture that many teams using FRI rely on. Might be time to opt for proven soundness!

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 ⋅ (ρ η)ᵈ).

In Subsection 1.5 of the paper, we 𝘴𝘶𝘨𝘨𝘦𝘴𝘵 new parameters for practical use in SNARKs. we don't mean to say that these 𝘢𝘳𝘦 secure, but rather that at least we don't know that they 𝘢𝘳𝘦𝘯'𝘵. We recommend working in proven regimes.

Our work shows that for proximity parameters η too close to 1 − ρ (covering radius / "capacity"), proximity gaps must fail. In fact, the operative η, at least heuristically grows like O(1 / log n). this carves away a chunk of the parameter space previously thought workable.

Our techniques are mainly combinatorial—we introduce new sharp estimates for the volumes of Hamming balls and their intersections. We relate the 𝘱𝘳𝘰𝘹𝘪𝘮𝘪𝘵𝘺 𝘦𝘳𝘳𝘰𝘳 of a code to the proportion of its words covered by the union of all Hamming balls centered at codewords.

What this announcement fails to convey is how easy it is to write circuits. Binius64 feels more like writing digital logic circuits writing than ZK arithmetic circuits.

Very cool to see confidential tokens on Solana! Couple of remarks: 1. The system offers confidentiality but not anonymity. The transferred amounts are hidden but the transaction graph is fully traceable. While this is not the best privacy guarantees, it does mean hackers are

thrilled to announce that 𝘚𝘶𝘤𝘤𝘪𝘯𝘤𝘵 𝘈𝘳𝘨𝘶𝘮𝘦𝘯𝘵𝘴 𝘰𝘷𝘦𝘳 𝘛𝘰𝘸𝘦𝘳𝘴 𝘰𝘧 𝘉𝘪𝘯𝘢𝘳𝘺 𝘍𝘪𝘦𝘭𝘥𝘴, joint with @jimpo_potamus, has been accepted to EUROCRYPT. pleasure to do this great work w/ @IrreducibleHW—we are just getting started. https://t.co/WAXmsIUzjy

alongside the big announcement at @IrreducibleHW, we are simultaneously releasing exhaustive documentation of Binius:

Today we are open-sourcing more Binius code! The binius-models repo is a package with Python prototype (model) code for Binius algorithms. This learning resource that has been invaluable for us, and hopefully it will be for you too! https://t.co/XyWaNJ9KPr

We made FRI-Binius proofs smaller and faster, again! Last week we published an update to the FRI-Binius paper that improves our ring-switching technique for small-field polynomial commitments. https://t.co/aHZl8wmsys 👇

@IrreducibleHW consistently pushing the frontier on STARKs, in IMO exactly the most important spots for long term performance e.g. Binary fields, gracefully handling multiple different 'bit lengths', linear codes, and now interleaved codes. (Same area of work as IOP recursion)

@EliBenSasson the amended version of the conjecture, which appears as Conjecture 4.3 of the new paper 2024/1351, remains wide-open, as far as we are aware.

this counterexample also shows that the theorem [Ben+23, Thm. 4.1] https://t.co/cvQWpw7Q6R of @EliBenSasson et al. for Reed–Solomon codes in the UDR is sharp: its false witness probability n / q is the best possible!

we also show that the conjecture for general codes [DP23, Conj. 2.4] needs to be amended—i.e., its false witness bound needs to be increased from e + 1 to n. we prove this by exhibiting a counterexample; i.e., a line which is not interleaved-e-close, but which has n close points.

the main result of our new paper supersedes and replaces the proof of Theorem 2.3 of https://t.co/mCf9xVrzTQ, whose currently-written proof is unfortunately flawed (this is my mistake!). we will shortly update that latter paper by replacing Thm. 2.3 with a reference to 2024/1351.

our proof of this result goes through for any proximity parameter up to the unique decoding radius, in contrast with the technique @GuilleAngeris, @alexhevans, and @rkm0959 used, which only works for proximity parameters less than a third of the code's distance.