I know you're eager to jump right in, but before we rush ahead, let's hit pause and travel back in time—back to an era when civilization was on the verge of making its next great leap, a breakthrough almost as monumental as the discovery of fire itself. Please note that this is a brief article written for curious readers looking to understand how money and investments work.

Pairings are mathematical tools that allow efficient verification of certain cryptographic properties without revealing any additional information to the other party. Verifiers rely on cryptographic pairings because pairings enable efficient and secure verification of complex algebraic relationships, particularly those arising from polynomial commitments without knowing the underlying polynomial's coefficients thus satisfying the zero knowledge property.

This beginner friendly article is an extended version of Vitalik’s article on Quadratic Arithmetic Programs. We will provide a deeper technical dive on how to transition from a Problem to R1CS and from R1CS to QAP.

How can a Prover convince a Verifier that he can accurately compute the sum of the evaluation of a function $$g$$ over all possible inputs $${ 0,1 }$$ ?

If you’re familiar with the Lagrange interpolation, you may know that it is used to construct the interpolation polynomial for a set of points in one dimension and if you’re not, no worries you can just watch these two videos (Video 1, Video 2) before proceeding. Our main focus today is using Lagrange interpolation in multilinear extensions. Don’t be overwhelmed by the upcoming formulas, you only need to understand what they do. We will provide you with a much simpler formula to use when dealing with MLEs at the end of the article, after understanding everything.

Let’s be real—there’s nothing worse than gridding through a long-ass article only to realize you’ve spent 20 minutes getting to the good part. So, here’s the deal: before we dive in, we’re giving you the why. Why are multilinear extensions a big deal in the world of ZKPs? Because trust me, they are.