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.