Welcome to Part 2 of my total 19 summaries of the academic paper on zero-knowledge proofs written by Justin Thaler et al. called ‘’Proofs, Arguments, and Zero-Knowledge’’.

Each sub-chapter introduces us to key concepts central to our understanding of probabilistic proof systems and their applications in computer science and cryptography.

Reed-Solomon Fingerprinting is a method used for error detection and correction in data transmission. This technique is based on the mathematical concept of Reed-Solomon codes, which are a type of error-correcting code that can detect and correct multiple symbol errors. Understanding this concept is crucial for appreciating the role of error detection and correction in maintaining data integrity.

Freivalds’ Algorithm, on the other hand, is a probabilistic algorithm used to verify matrix multiplication. It uses randomness to achieve a high probability of correctness with a low computational cost. This algorithm exemplifies the power of randomness in creating efficient solutions in computer science.

The third sub-chapter presents an alternative view of fingerprinting and Freivalds’ Algorithm, discussing how these concepts can be understood in the context of polynomial identity testing. This perspective highlights the connections between these concepts and other areas of computer science and mathematics, broadening our understanding of the applications of probabilistic proofs.

Finally, we go into Univariate Lagrange Interpolation, a method used for constructing a polynomial that passes through a given set of points. This method is fundamental to understanding Reed-Solomon codes and their applications in fingerprinting.

By exploring these sub-chapters, we will gain a deeper understanding of the power of randomness in the context of fingerprinting and Freivalds’ Algorithm, and how these concepts contribute to the field of cryptography.

We understand that some of these terms might seem complex, especially if you're new to these concepts. But don't worry! Each of these topics will be explained in detail, with plenty of examples and background information to help you understand. We'll break down complex concepts like matrix multiplication and polynomials into understandable parts.

Before we dive into the specifics of the chapter, let's take a moment to understand the concepts of fingerprinting and Freivalds’ Algorithm.

Matrix multiplication is a fundamental operation in mathematics and computer science. It involves multiplying two matrices (which you can think of as tables of numbers) to produce a third matrix. However, matrix multiplication is computationally expensive, meaning it takes a lot of time and resources, especially for large matrices. Freivalds’ Algorithm offers a way to verify the result of a matrix multiplication operation without having to perform the multiplication itself, saving a lot of computational resources.

Polynomials are important mathematical expressions used in cryptography, which is all about securing information. They are like building blocks that help create secure systems and protect data. In simple terms, a polynomial is an equation that involves numbers and variables raised to different powers. For example, a simple polynomial could be:

y = 3x² + 2x + 1

In this polynomial, 'x' is the variable, and the coefficients (numbers multiplied by the variables) are 3, 2, and 1. The exponents on 'x' represent the powers to which 'x' is raised (in this case, 2, 1, and 0). Polynomials allow us to perform mathematical operations like addition, subtraction, multiplication, and even encryption, which help keep our information secure. They are an essential tool in cryptography, ensuring the confidentiality and integrity of our data in the digital world.

In the context of blockchains, matrix multiplication plays a significant role in improving scalability and efficiency. Here are some key aspects where matrix multiplication is utilized in blockchain technology:

In summary, matrix multiplication, despite being a mathematical operation, has practical applications in the world of blockchain technology. Understanding and utilizing these applications can lead to the development of more scalable and efficient blockchain systems, cough ZK-rollups cough.

As this summary will be quite heavy on mathematics, I will make the main points as brief as possible to explain why I explained all this and what you should remember from these concepts today.

The point of these concepts is that any data, whether it’s a message, proof, state transition or other information can be stored in matrices and polynomials. Hence the interest to make these calculations as efficient and secure as possible.

Reed-Solomon Fingerprinting is performed to see if encrypted data, which is in the form of a polynomial, has been correctly transferred with no errors.

Matrix Multiplication and its verification is needed in the context of zk-SNARKs (ZKPs). When building zk-SNARKs one of the steps involves a quadratic arithmetic program (QAP), which can be represented as a matrix equation. The prover needs to solve this matrix equation to generate the proof. Freivald’s algorithm can also be used in the QAP stage of building the zk-SNARK to increase efficiency.

In the context of zk-SNARKs and zk-STARKs, univariate Lagrange interpolation is used in the process of constructing a polynomial commitment scheme, which is a way of committing to a polynomial in such a way that you can later reveal evaluations of the polynomial in a verifiable manner. This is needed since the verifier is not sharing the original polynomial, hence the prover needs to use Univariate Lagrange interpolation to create a polynomial which goes over the same points.

So how does matrix multiplication work? To start, I will make an example of how we need to multiply the different slots within two matrices to get their product properly. Unfortunately, matrices cannot be notated within Beehiiv, hence I will use pictures to explain this.

The product of two matrices is bound in size to how many rows Matrix A has and how many columns Matrix B has, see next photo:

Below we have two simple matrices that we would like to multiply with each other.

We already know that the matrix product will have a 2×2 size, as both Matrix A and B have a size of 2×2. To get this product we have to multiply and add some elements of these matrices. To get the final product these are the required steps:

Step 1: a∗e+b∗g = Left-top

Step 2: a∗f+b∗h = Right-top

Step 3: c∗e+d∗g = Left-bottom

Step 4: c∗f+d∗h = Right-Bottom

If you look closely you will see that there is a pattern for multiplying matrices. Step 1 and 2 both start their first multiplication with a, whereas the first multiplication in steps 3 and 4 starts with c. In addition, the same happens in the second part of the multiplication in each step with b and d. Matrix B with e, f, g and h are also showing a pattern where they rotate between each step. This can also be given in a scheme for when matrices get larger.

Now let adds some numbers so we can get a grip on what is happening:

Step 1: (1×5) + (2×7) = 19

Step 2: (1×6) + (2×8) = 22

Step 3: (3×5) + (4×7) = 43

Step 4: (3×6) + (4×8) = 50

Then the final product of Matrix A and B is Matrix C with values:

If you still can’t wrap your head around how the logic of multiplying matrices works, then I highly suggest you watch this video which takes 5 minutes and makes use of a scheme to not lose track when matrices get larger. Note: This is very important to understand as multiplying matrices is a deep fundamental method which is used in many mathematics.

Freivald’s Algorithm

Freivald's algorithm is a randomized algorithm used to efficiently verify matrix multiplication. It can determine if the product of two matrices is correct or if an error occurred during the multiplication process. This means the algorithm is used when a product of two matrices is already given and we just want to verify if the person has done a good job at multiplying them.

Given the same matrices as before:

The product of these matrices (A*B) is also given by the prover and is defined as matrix “C”:

To check for the validity of the matrix multiplication a randomized vector of values of 5 and 1 is introduced:

Step 1: Calculate: Matrix B * Vector R = Br

Step 2: Calculate: Matrix A * Br = A * Br

Step 3: Calculate Matrix “C” * Vector “R” = Cr

Step 4: Calculate the difference between steps 2 and 3: A*Br - C*r

The idea is based on the fact that if C is a product, then the value of A × (Br) – Cr will always be 0. If the value is non-zero, then C can not be a product.

Let’s perform these steps with the actual values present in the matrices and vectors.

A polynomial is a mathematical expression involving a sum of powers in one or more variables multiplied by coefficients. It is a fundamental concept in mathematics and has wide-ranging applications in various fields, including computer science and cryptography.

A simple example of a polynomial is a quadratic equation, which is a polynomial of degree 2. The general form of a quadratic equation is y=ax²+bx+c, where a, b, and c are constants, and x is the variable.

In the context of this subject, polynomials play a crucial role in Reed-Solomon fingerprinting, which is a method used for error detection and correction in data transmission. Reed-Solomon codes, which are a type of error-correcting code, are based on the mathematical concept of polynomials.

Let's take a look at a simple polynomial: y=x². This is a quadratic polynomial, and its graph is a parabola. Here's what it looks like:

In this graph, the x-axis represents the variable x, and the y-axis represents the value of the polynomial y=x² for each value of x. As x varies, y changes according to the rule y=x². This means that for any point on the graph, its x-coordinate and y-coordinate satisfy the equation y=x².

For example, when x=2, y=2²=4. So points (2, 4) lie on the graph. Similarly, when x=−3, y=(−3)²=9, so the point (-3, 9) is also on the graph.

Polynomials can be made very complex, look at this next example:

f(x)=5x²⁰−3x¹⁹+7x¹⁸−2x¹⁷+4x¹⁶−6x¹⁵+8x¹⁴−9x¹³+10x¹²−11x¹¹+12x¹⁰−13x⁹+14x⁸−15x⁷+16x⁶−17x⁵+18x⁴−19x³+20x²−21x+22

Which looks like this between X=-1 and X=1:

As you can see, the polynomial is quite complex due to its high degree (20). These coefficients determine the shape of the polynomial. The higher the degree of the polynomial (the highest power of x), the more complex the shape of the graph.

Here's a simplified example of how Reed-Solomon fingerprinting might work:

Let’s say that our message of “HELLO” is corrupted. The person that receives the message receives “HELPP”. This changes the polynomial of the message from 72x⁴+69x³+76x²+76x+79 into 72x⁴+69x³+76x²+80x+80.

Let’s see how much these two messages differ mathematically when using the reed-solomon X, and Y pairs:

For the “HELLO” polynomial (72x⁴ +69׳+76x²+76x+79):

For the received “HELPP” polynomial (72x⁴+69x³+76x²+80x+80):

As you can see, having the prior Reed-Solomon Fingerprint (the X and Y-values for “HELLO”) we can verify If the message got corrupted. The y-values of the two polynomials differ at the x-value of -4 (and other values), indicating that the message has been corrupted.

This is a simplified example. However, the basic idea is to use the properties of polynomials and the concept of error-correcting codes to ensure data integrity during transmission.

Here's a simplified example of how Univariate Lagrange Interpolation might work:

Suppose we have the following set of X, Y points: (1,2), (2,3), and (3,5). The goal of univariate Lagrange interpolation is to find a polynomial that passes through these points. The general formula for a Lagrange polynomial is:

where yi​ are the y-values of the given points, and li​(x) are the Lagrange basis polynomials, defined as:

Do not worry if you do not know the formulas by heart. The most important thing is that you know what we can do with Univariate Lagrange Interpolation.

This polynomial passes through the given points, as you can see in the plot below:

The red dots represent the given points (1,2), (2,3), and (3,5). The blue curve is the Lagrange polynomial that we calculated, which passes through all the given points. We have constructed a polynomial of degrees N-1, where N = amount of X,Y pairs.

The chapter highlights the power of randomness in creating efficient solutions in computer science and cryptography. It shows how randomness can be used to reduce the computational cost of operations like matrix multiplication, and how it can be used to create unique fingerprints for data. But how much quicker is Freivald’s algorithm in relation to other algorithms? The efficiency of Freivald's algorithm comes from its time complexity, which is O(n^2), where n is the dimension of the input matrices. This is significantly more efficient than the time complexity of matrix multiplication itself, which is O(n^3) for the naive algorithm and can be reduced to approximately O(n^2.376) with the best-known algorithm.

Randomness isn't directly incorporated into the process of Univariate Lagrange interpolation itself. The method of Lagrange interpolation is deterministic, given a set of points, it will always produce the same interpolating polynomial.

However, randomness can play a crucial role in the broader systems or protocols where Lagrange interpolation is used. For example, in cryptographic protocols like zk-SNARKs and zk-STARKs, randomness is often used in the selection of evaluation points or in the generation of secret keys.

In the context of polynomial commitment schemes, which are used in zk-SNARKs and zk-STARKs, the prover might choose a secret random point at which to evaluate the polynomial when creating the commitment. This secret point is then used in the Lagrange interpolation process during the verification phase. The randomness here is crucial for the security of the protocol, as it prevents an adversary from being able to predict or manipulate the commitment or the verification process.

So, while randomness isn't a part of the Lagrange interpolation process itself, it is often a crucial component of the cryptographic protocols where Lagrange interpolation is used.

This opens up a discussion about the role of randomness in other areas of computer science and cryptography and the potential impact of further advancements in these fields.

Here is a summary of this week’s chapter!

Next week I will go into detail about the definitions and technical preliminaries of:

This will explain the different types that are used in constructing proofs and/or argument systems. Which will give us some background in understanding Chapter 4.

For those interested in learning more about the concepts introduced in this chapter, here are a few additional resources:

If you enjoyed it, make sure to subscribe. Thanks for reading and see you next time!