When we discuss Reed-Solomon Codes or other codes in general in ZKPs, the main ingredient is really about proximity and their testing. For example, to test if $f_1, f_2, \cdots, f_m$ have correlated agreement to a codeword, how would you do it efficiently? In that sense, if I recall correctly, you need to dig a little deep to find relations between Reed-Solomon decoding and ZKPs. Of course, that doesn't mean there's no relation between the two. The most critical relationship between the two comes from, none other than, [BCIKS20]. The proof technique for correlated agreement starts with running an efficient Reed-Solomon decoding algorithm to a word over a formal variable. Also, the fact that there are polynomial number of codewords within the list decoding regime is an important part of some proofs, such as the soundness of STIR. Therefore, it seems like a good idea to study the relevant theory regarding Reed-Solomon Codes and their decoding possibilities. Also, it's just good coding theory study and it's fun. This note aims to study four things.

소개 이 글은 https://eprint.iacr.org/2024/390.pdf에 대해서 설명합니다. STIR의 목표는, Reed-Solomon Code와의 Proximity Testing을 최소한의 query로 하는 것입니다. 동일한 문제를 푸는 알고리즘 중 가장 잘 알려진 FRI는, degree $d$ 문제를 $\lambda$-bit security를 갖게 해결하기 위하여 query를 $\mathcal{O}(\lambda \log d)$개 사용합니다. STIR는, 그에 비해 $\mathcal{O}(\log d + \lambda \cdot \log \log d)$만큼의 query를 사용하여, 더 적은 query를 사용하게 됩니다. query의 개수는 STARK proof의 크기와 연결되어 있기 때문에, FRI를 STIR로 대체하여 STARK의 proof size 및 verifier time을 줄일 수 있습니다. STIR의 argument size는 FRI에 비해 (파라미터에 따라서) 대략 1.25x에서 2.46x 정도의 개선을 보인다고 합니다. STARK의 proof size를 줄일 수 있다는 점은, 다르게 말하면 Recursive STARKs의 overhead 역시 감소한다는 의미를 갖습니다. 이런 점에서 STIR는 FRI의 direct replacement로 작동할 수 있을 것으로 예상됩니다. 이 논문은 2024년 CRYPTO에서 Best Paper Award를 받기도 했으며, 현재 FRI를 사용하고 있는 ZKP 팀들은 대부분 STIR에 큰 관심을 보이고 있습니다. STIR 논문은 Polynomial IOP를 Reed-Solomon Proximity Test를 통해서 IOP로 compile 하는 새로운 방법에 대해서도 다루지만, 이에 대해서는 생략하도록 하겠습니다. 간단하게 소개하자면, round-by-round knowledge soundness를 높게 가져가는 새로운 compiler를 만들고, R1CS를 위한 IOP를 compile 하는 방법을 소개합니다. STIR 논문의 또다른 중요한 기여는 batch degree correction입니다. 이는, $f_1, f_2, \cdots, f_m: \mathcal{L} \rightarrow \mathbb{F}$와 $d_1, d_2, \cdots, d_m, d^\star$가 있어 $d^\star \ge d_i$이라 합시다.

 Audited by Allen Roh (rkm0959). Report Published by KALOS. ABOUT US Pioneering a safer Web3 space since 2018, KALOS proudly won 2nd place in the Paradigm CTF 2023 with external collaborators. As a leader in the global blockchain industry, we unite the finest in Web3 security expertise. Our team consists of top security researchers with expertise in blockchain/smart contracts and experience in bounty hunting. Specializing in the audit of mainnets, DeFi protocols, bridges, and the ZKP circuits, KALOS has successfully safeguarded billions in crypto assets. Supported by grants from the Ethereum Foundation and the Community Fund, we are dedicated to innovating and enhancing Web3 security, ensuring that our clients' digital assets are securely protected in the highly volatile and ever-evolving Web3 landscape. Inquiries: audit@kalos.xyz

chapter 23 of https://toc.cryptobook.us/book.pdf the book https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf thanks to cryptohack discord for sending me resources below https://nigelsmart.github.io/SCALE/ https://github.com/rdragos/awesome-mpc Key Definitions The intuitive setting - is that there are $n$ parties each with input $x_1, x_2, \cdots, x_n$ and a public function $f$. These $n$ parties want to work together to compute $y = f(x_1, \cdots, x_n)$, but they want to reveal nothing about their inputs $x_i$ except the information that is trivially revealed due to the output $y$. In this scenario, there's some desirable properties we can define.

Continued from https://hackmd.io/keVLzFSrQdmCcmUVh2l_BQ NOTE 1: There's an issue with a proof (and the proof in the paper as well) - to be fixed later. NOTE 2: https://hackmd.io/qb-NrfZ7SgWMvPGNF4xPxw NOTE 3: The proof is now fixed on eprint. Part 1: Extractor Definition The claim is that if $\mathcal{Q}$ is admissible, then our construction has extractability.

Summary Recall the statement from 1/3: Ligero's Proof for $q < d'/3$ - The main statement is that $$\left\lVert \sum_{i=1}^n r_i x_i - V \right\rVert_0 \le q \implies X \text{ is } q\text{-close to } V$$ where $r_i$ are random, with failure probability $q/\lvert \mathbb{F} \rvert$. To test $n$ vectors, we needed $n$ random elements. However, this isn't all that great - for example, in the ultimate batched FRI soundness proof in [BCI+23], it deals with correlated agreement over a parameterized curve, so that one samples $r \in \mathbb{F}$ and uses the coefficients $1, r, r^2, \cdots , r^{n-1}$ instead of sample $n$ random values like we did in Ligero.

Chapter 3 of https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf GMW Protocol Consider a $n$-party boolean arithmetic circuit. For each input bit, secret sharing is done $$b = s_1 \oplus s_2 \cdots \oplus s_n$$ We assume we have AND, NOT, XOR gates. NOT: The first party just flips the corresponding share

Continued from https://hackmd.io/c2eTRG3PSLeverwHTMkNDQ A similar approach is now integrated into the eprint manuscript. The Issue The issue with the original paper was that it runs a straight-line extractor of BSCS16, and explains it as if a single execution of $\mathcal{A}$ is sufficient to extract all $(u_i)$ via BSCS16. However, this is actually not true - a single execution of $\mathcal{A}$ only gives $\kappa$ column openings, and this is definitely not sufficient. The extractor of BSCS16 allows one to query arbitrary many times, and only guarantees the extraction of merkle trees "up to the queried leaves". So for example, consider the following scenario.

Chapter 23.3 of https://toc.cryptobook.us/book.pdf Chapter 3.1 of https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf https://infossm.github.io/blog/2021/02/20/Multi-Party-Computation-1/ First Idea - Lookup Table + Oblivious Transfer If one wants to compute $f(x, y)$ where $x$ is supplied by $P_1$ and $y$ is supplied by $P_2$, we can do this as follows. For each possible input $x$, $P_1$ selects a key $k_x$. This is done similarly for $y$. Then, $P_1$ computes, for all $\lvert X \rvert \cdot \lvert Y \rvert$ possible combinations, the value $\text{Enc}_{k_x, k_y}(f(x, y))$. $P_1$ then sends this encryption table to $P_2$. Also, $P_1$ sends the $k_x$ corresponding to its input $x$. The hard part arises from $P_1$ having to send $k_y$ corresponding to the $P_2$'s input $y$, without knowing $y$ itself. This can be done via 1-out-of-$\lvert Y \rvert$ Oblivious Transfer. Once $P_2$ receives $k_y$, they can try to decrypt all encryptions, with only success being $f(x, y)$ if the encryption is authenticated. This is a quite unoptimized protocol, but one that provides MPC. To allow this lookup table idea to work, we only work with 2-party boolean circuits.

Chapter 23.2 of https://toc.cryptobook.us/book.pdf The Big Idea Consider that we want to deal with $$(y_1, \cdots, y_m) = f(x_1, \cdots, x_n)$$ Similar to ideas in ZKP, we first write $f$ as an arithmetic circuit, composed of addition, multiplication, constant addition, scalar multiplication. Here, we work over $\mathbb{F}_q$. So we wish to deal with the four operations, but in an MPC setting.

I actually skipped over a lot of parts on this, mostly intuitive understanding only. The reason for this was that the proof techniques were way too mathematically advanced and the techniques are really specialized towards Reed-Solomon codes only. It seems that the really hard part only comes from the list decoding part for the correlated agreement, and the other parts aren't that bad. I am also feeling a need to understand FRI much much better, so... IMO the most painful part is that [BBHR18b] is the most accessible proof for FRI soundness yet it writes everything in additive form so it's hard to read for my not-abstract-enough brain. Anyways this is more of a proof writing session than a short summary. Denote $\text{RS}[\mathbb{F}, D, k]$ as the Reed-Solomon code over domain $D$ with degree $\le k$ polynomials. Let $\rho = (k + 1) / n$ where $n = \lvert D \rvert$. $n$ is assumed to be a power of $2$.

preparation for studying Binius / more code-related PCS stuff fundamentally note: this write-up is really for my understanding so something that might be well-known for the readers might not be for me and something that might be well-known for me might not be for the readers paper link: https://eprint.iacr.org/2023/1478.pdf additional material

This is also used in Brakedown for its soundness proof. It's for general codes, so... The main statement is that $$\left\lVert \sum_{i=1}^n r_i x_i - V \right\rVert_0 \le q \implies X \text{ is } q\text{-close to } V$$ where $r_i$ are random, with failure probability $q/\lvert \mathbb{F} \rvert$. To be more precise, we will assume that the distance from $X$ to $V$ is $>q$ and show that