A (Relaxed) PCS by Merkle Trees and Low-Degree Tests
Chapter three dives into a first Succinct Argument of Circuit Satisfiability. It does so by introducing what it calls a Relaxed Polynomial Commitment Scheme that combines Merkle Trees and Low-Degree tests. Implementing a first Succinct Argument sounds like an interesting challenge, let's find out.
An Unnecessarily Generic Fiat-Shamir Transformation
The protocols we've taken a look so far are the Interactive Proofs. A Fiat-Shamir Transformation offers a way to turn any such protocol into a non-interactive one. That sounds extremely useful for almost all real-world scenarios and is worth looking into. But how far can the boundaries of the implementation generality be pushed? Let's find out.
The GKR Protocol
It has been a long time since the last post but it is finally time to play around with the last major protocol from Chapter 4 in The Book: the GKR protocol. It will involve running a protocol inside another protocol, let's go.
Efficient IP for MatMult
Hi how about some performance? In Chapter 4 the book first introduces a regular MatMult IP that has already been implemented in previous post and then discusses the performance improvements to it. Should be fun, let's dive right in.
Generalizing Sum Check protocol and counting the triangles
Welcome back. In the previous post we have
taken a first look at the Sum Check protocol from The Book and implemented
it for the case of multivariate::SparsePolynomial.
In this post I am going to attempt to generalize the protocol to
any polynomial and apply it to the Counting Triangles in Graphs problem.
Implementing Sum Check protocol in Rust
This post is going go into reading the Sum Check protocol from the book and discussing a naive implementation of the described protocol in Rust. Again as in previous post the main goal of the post is going to be so to speak "gluing" together the math text and the implementation in software.
Evaluating multilinear extensions with Rust
Hi there! This is a first post in a series where I am planning to take notes on Proofs, Arguments and Zero-Knowledge as I am reading it. I write code in Rust for a living so I am going to use this language to implement algorithms and protocols from the book.