Succinct Verification Through Reed-Solomon and Folded Reed-Solomon Codes

Abstract

The overarching problem for our thesis talks is succinct verification: how can one check that a computation (e.g. $2^{10} = 1024$) has been performed correctly? A natural way to verify is to repeat the claimed computation from scratch and check that the results agree. However, repeating computations from scratch can be very expensive, especially when the computation is not as simple as the given example. Given a computation that takes time $T$ naively, can we instead produce a proof that can be checked reasonably accurately in time sublinear in $T$, such as $O(\log T)$? In the 1990s, researchers studied probabilistically checkable proofs (PCPs) that solved the above problem. Informally, the PCP theorem (ALMSS, 1992) stated that there exists a proof format that allows a grader to read 3 words in a proof and still successfully grade the proof as correct or incorrect with high probability. The tradeoff in accuracy in exchange for succinct verifiability is called soundness. Such initial proof formats produced implausibly long proofs (despite being quick to verify), so some recent research has focused on making proof systems that are not only succinctly verifiable but also concretely efficient. Their primary real-world application today is making cryptocurrencies more scalable – networks like Ethereum are currently limited in their throughput due to it being time and energy intensive to verify transactions. However, such proof systems involve many beautiful mathematical tools as well. They reduce the verification step to a math problem called Reed-Solomon proximity testing (RPT): discerning whether a polynomial is low degree or far from a low-degree polynomial for some notion of ``farness". One algorithm used to solve RPT in succinct verification systems is the Fast Reed-Solomon IOPP (FRI). The first few chapters of this thesis are expository sections introducing succinct verification and how succinct verification is connected to mathematical objects called error-correcting codes (ECCs). These sections build up to an explanation of FRI and its soundness. We then explain a related ECC called Folded Reed-Solomon codes have a property called list decodable up to capacity. Informally, this means that such codes can tolerate a large number of errors while still being able to output a small list of candidate code words. FRI can solve RPT, but its soundness depends on the list-decoding size of Reed-Solomon codes, which is not known to achieve list-decoding capacity. Folded Reed-Solomon codes do achieve capacity when instantiated with the right parameters. In the final part of this thesis, we propose modifications to FRI that can solve proximity testing for Folded Reed-Solomon codes.