This post looks at Plonky3 and combining Mixed Matrix Commitment Schemes with STIR 🥣 and WHIR 🌪️ as the low-degree test. As far as I understand, the problem that we are aiming to solve is the following: The prover has committed to a matrix of functions (note the possibly different number of columns in each row) $$ \begin{bmatrix} f_{1, 1}, \dots, f_{1, n_1} \\ \vdots \\ f_{m, 1}, \dots, f_{m, n_m} \end{bmatrix} $$...
Just some spare thoughts on LDPC codes and RS codes (for IOPP based SNARKs), as an answer to Dev’s questions . TLDR; LDPC are an amazing avenue of research, that I hope to explore more, but I am bit skeptical on the current maturity of prover and verifier performance that they bring to the table. I think it makes sense to consider the question on two parts: prover time and verifier complexity....
Our recent work, WHIR 🌪️ (See 2024/1586 and blog-post. ) is an IOPP for constrained RS codes with exceptionally fast verification. In this blog we explain in detail one of the optimization that we used to achieve a faster verifier, with applications to schemes such as FRI and STIR as well. Verifier complexity usually consists of two components: (i) an algebraic component and; (ii) computing hashes. Reducing the second load (ii) usually involves reducing the IOPP query complexity, which is the main objective of STIR and WHIR....
This blog-post is a short introduction to our new work: “WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification”. This is joint work with Gal Arnon, Alessandro Chiesa, and Eylon Yogev, and the full version is available on ePrint . Code is also available at WizardOfMenlo/whir. WHIR 🌪️ We present WHIR (Weights Help Improving Rate), a concretely efficient IOPP for constrained Reed–Solomon codes1. WHIR is both an IOPP for Reed–Solomon codes and a multilinear polynomial commitment scheme (PCS), and achieves the fastest verification speed of any such scheme, even including univariate PCS with trusted setup....
This blog-post is a short introduction to our new work: “zkSNARKs in the ROM with Unconditional UC-Security”. This is joint work with Alessandro Chiesa, and the full version is available on ePrint. The Universal Composability (UC) [Can01]1 framework is a “gold-standard” for security in cryptography. UC-secure protocols achieve strong security guarantees against powerful adaptive adversaries, and retain these guarantees when used as part of larger protocols. Zero knowledge succinct non-interactive arguments of knowledge are often used within larger protocols deployed in dynamic environments, and so UC-security is a highly desirable, if not necessary, goal....
This blog-post is a short introduction to our new work: “STIR: Reed-Solomon Proximity Testing with Fewer Queries”. This is joint work with Gal Arnon , Alessandro Chiesa , and Eylon Yogev , and the full version is available on ePrint . Code is also available at WizardOfMenlo/stir . Here are also some slides that might be helpful, the recording of the talk at zkSummit11 , and our episode on zkPodcast ....
Our recent work, STIR 🥣 (See 2024/390 and blog-post. ) is an IOPP for RS codes with improved query complexity compared to the state-of-the art, FRI. Compared to FRI, STIR has a few more parameters that one can tweak, which can have a rather large impact on prover time, verifier time and argument size. This short blurb details what these parameters are, and how they translate, concretely, in the resulting argument....
This blog-post is a short introduction to our new work: “A Time-Space Tradeoff for the Sumcheck Prover”. This is joint work with Alessandro Chiesa, Elisabetta Fedele, Andrew Zitek-Estrada, and the full version is available on ePrint. Code accompanying this work can be found at space-efficient-sumcheck. The sumcheck protocol [LFKN92]1 is an interactive protocol between a prover and a verifier that allows a verifier to succinctly check claims of the form $$ \sum_{\mathbf{b} \in \{0, 1\}^n} p(\mathbf{b}) = \gamma \enspace....