I’ve spent three years in Web3, watching the technology mature and the infrastructure for a billion users slowly take shape. But one problem still threatens everything — and it’s getting worse.

Most newcomers have no idea how this ecosystem works. They chase hype, follow influencers, and invest in projects they don’t understand. When they lose, they don’t know why. When they win, it’s luck — not strategy.

The market has become a circus of memecoins, pump-and-dumps, and manipulation. Scammers prey on the uninformed, and large players move prices at will. This isn’t a string of accidents — it’s a structural flaw.

I’ve seen millions wiped out — not from greed, but from ignorance. They were never given the tools to navigate this space. Web3 was meant to empower them, but instead, it’s failing them — driving people away and giving the entire ecosystem a bad reputation.

Why I Created EulerPhi ?

I started EulerPhi out of frustration — frustration at watching billions flow into hollow Web3 projects with no intrinsic value. Memecoins, hype-driven protocols, and fleeting trends were getting funded, while truly groundbreaking teams — the ones building technology that could reshape industries — were overlooked and underfunded.

The thought that kept echoing in my mind was: “If only I could redirect that capital toward the builders who actually deserve it.”

The problem is simple but profound: most people are not technical. They can’t easily distinguish between a protocol destined to change the world and one destined to disappear. And so, they follow the noise — not the value.

I wanted to change that. I wanted to create a place where investors, whether retail or institutional, could find the protocols that combine vision with execution, where true innovation is made visible and accessible. A place where capital flows toward value, not vanity.

History gives us powerful reminders. Take Nvidia: years ago, only a handful of technical minds in AI understood the magnitude of what they were building. For everyone else, it was just another chip company. But when the world finally realized Nvidia was powering the AI revolution, and so it became the largest company in the stock market.

It’s proof of a hard truth: most people don’t know how to allocate their funds toward high-performing, high-potential companies — until it’s too late.

As Warren Buffett once said, “Price is what you pay. Value is what you get.” EulerPhi is here to ensure capital flows toward innovation with true intrinsic value and to help educate investors, ultimately reshaping how society perceives and engages with our ecosystem.

Our Mission

Onboarding retail and institutional investors into crypto by redirecting capital toward protocols with the highest intrinsic value.

I - Barter System

The barter system is a system of trading goods and services directly for other goods and services. The barter system dominated during the prehistoric and early agrarian eras, before the advent of money and standardized commodities as mediums of exchange. This system was most prevalent in the Neolithic period (around 9000 BCE to 3000 BCE), when human societies transitioned from nomadic hunter-gatherer lifestyles to settled agricultural communities. This system was brought to life to fulfill a single goal, to meet everyone’s needs and demands. People would exchange goods and services for other goods and services, making life much easier. But this system had its potential flaws.

Unit of account

is a way to measure how valuable something is (used as a unit of account). Bitcoin is a poor unit of account since its price fluctuates and you cannot price items.

There wasn’t a proper form of measurement which made it hard for both parties to agree on the worth of the goods exchanged. One apple could be traded for 5 eggs between two people, while another person might exchange one apple for 8 eggs. Also another issue arises when someone attempts to trade 100 apples for half a livestock. Many goods cannot be easily divided to match the value of smaller items. Difficulty in storing goods for extended periods diminished their value, and transporting them over long distances made it highly impractical. To solve these issues, humanity was in need for a new system that could solve these problems and that’s where commodities came into place.

II - Commodity-based money

Gold aka God’s Money was first valued for its beauty and malleability, appearing in jewelry and ornamentation in ancient cultures such as those in Mesopotamia and Egypt (~4000 BCE). Its shine and resistance to tarnish made it a symbol of wealth and divinity. Gold's use as a medium of exchange began in ancient Egypt (~1500 BCE), where gold bars were used for trade. While not yet coined, gold's role in commerce marked a shift toward its recognition as money.

Medium of exchange

is an agreed upon method to transact with each other for example by buying groceries with gold or silver coins.

Gold became a standardized medium of exchange with the minting of the first gold coins by the Lydians in what is now Turkey, around 600 BCE. King Alyattes and his successors issued coins made of electrum (a naturally occurring alloy of gold and silver). These coins facilitated trade and were widely recognized for their intrinsic value. Over time, civilizations across the Mediterranean, Middle East, and Asia adopted gold and silver as primary forms of currency. Gold’s scarcity, durability, divisibility, and inherent value made it an ideal medium of exchange and storage of value. Long before the modern era, civilizations engaged in international trade across the Silk Road (connecting Asia, the Middle East, and Europe) and maritime routes, such as the Indian Ocean Trade. This facilitated the exchange of goods, ideas, and cultural practices, laying early foundations for globalization. Empires such as the Roman Empire, the Persian Empire, and the Mongol Empire expanded their territories and created extensive networks of trade, communication, and cultural exchange.

Storage of value

is a way for us to keep the value and wealth we’ve generated.

During the ancient Egyptian era, nobles instilled in society the belief that gold held immense value due to its scarcity, shining and anti-oxidant properties. This widespread belief persisted for centuries, shaping how people viewed wealth. For an asset to be seen as a reliable medium of exchange, it had to possess tangible value first. Just like gold and other commodities, goods were also deemed valuable because they provided nourishment and met people's real world needs. What reinforced this belief was the deep emotional connection between the holder and the asset. People worked tirelessly throughout their lives to earn money, so they needed it to have real-world value to believe that it really had value.

Since basic needs were seen as essential, they were highly valued, as they were considered luxuries in those times. In an era when life was much harder, basic needs were viewed as luxuries, and wants were simply never an option for normal people. At the beginning of the 20th century, owning a car was a luxury that only the wealthy could afford, while the everyday luxuries of the masses were the necessities required to survive. This is why one of the less obvious characteristics of money is that it must have tangible value or utility. Gold was best suited for them because they were able to establish an emotional connection with it which took thousands of years. So this solved the measurement and storing problem however Gold is heavy, costly to transport, and requires secure storage, making it impractical for large-scale or international trade. This was a critical issue as humanity was advancing at an increasingly faster rate. Humanity needed a new system—one that could fuel its expansion, ensure reliability and fairness for all, and gain universal adoption. A system capable of facilitating globalization on a far larger scale, while overcoming the limitations that metal money imposed on society.

III - Paper-based Currency

The first government-issued paper currency, known as "jiaozi," emerged in China during the Song Dynasty (960–1279 AD). In 1023, the Song government nationalized the issuance of these notes, establishing the world's earliest state-sponsored paper money system. Initially, merchants used privately issued promissory notes to avoid carrying heavy copper coins over long distances. Every system has its flaws, and the more complex it becomes, the more flaws it is likely to have. The overproduction of paper money and mismanagement of the monetary system led to hyperinflation. The government, in an effort to finance military campaigns, printed excessive amounts of paper currency, which devalued the money and contributed to widespread economic instability. This caused loss of confidence in the currency and further weakened the economy. While the fall of the Song Dynasty was caused by a combination of factors, the mismanagement of the monetary system and the resulting inflation played a crucial role in undermining the dynasty's financial foundation.

In 2024, several countries have made the same mistake with their economic systems:

• USA : The Great Depression (1929–1939)/1971/1987/2000/2008

• The 1997 Asian Financial Crisis

• The 2010 European Debt Crisis

• Venezuela’s Economic Collapse (2010s-present)

• The 1994 Mexican Peso Crisis

• The 2001 Argentine Financial Crisis

• Spain’s 2010-2012 Sovereign Debt Crisis

and the list goes on…

The overproduction of paper money has flooded the economy, causing inflation and reducing the currency's reliability. As a result, people often turn to gold as a hedge against inflation, valuing it for its scarcity and real-world value. History repeats itself, though with different shades. As I write this article, humanity finds itself in need of a new financial system—one capable of addressing the flaws of the previous system, such as inflation, counterfeiting, and durability issues.

Small Recap

Throughout centuries, money had 3 essential properties:

1. Storage of value

2. Unit of account

3. Medium of exchange

4. Tangible value (hidden property)

Digital-based System

Dogecoin

Now the part you’re been waiting for !!

It might sound confusing for the reader since it involves Game theory aka probability, psychology, strategy, discrete math and some insanity to understand it.

Comparing Dogecoin to a national currency is like comparing a red apple with a green apple. They both taste the same !! History has proven that even the strongest countries are prone to financial collapse and devaluation of their currency. The increase in trust and number of people holding the currency, the stronger it becomes. So if the number of holders holding Dogecoin keeps on increasing, it will have proven itself currently to be more reliable than most national currencies. The bigger the mass putting trust in a currency the safer it gets or I’d like to believe so, not accounting for black swans of course. It’s called a meme coin or shit coin since it has no tangible real world value and cannot be considered as shares of a stock since it doesn’t provide any useful services and doesn’t have a legal team backing it up, only rational/irrational people like Elon musk hyping it up only to use the so called victims/followers as exit liquidity. For some people acting rational is acting irrational. They put their faith in the hands of a billionaire who successfully built a couple of companies and did some good things for the community. It’s like he’s the lion and we’re the sheep, manipulation and persuasion at its finest. If you keep playing the game like a sheep you will remain a sheep, in the end its your decision.

Investing vs Gambling

Investing is investing, gambling is gambling, investing is gambling and gambling is investing. Take a moment to process this phrase, I mean really think about it. Everything you buy has a risk of it going bust.

Investing in something you know nothing about is called gambling.

Similarly gambling can also be explained as investing in something you know everything about. Hhmmm this sounds controversial.

Let just talk about it in a couple of phrases to broaden your perspective.

Consider Investing as a blue battery that has a positive and negative pole and gambling as a red battery with also a positive and negative pole.

Investing

Positive Pole:

1- Investing in something you know nothing about is called gambling.

2- Its inverse should be : Investing in something you know everything about is called gambling.

This deduces that Investing is Gambling even though you know nothing or everything about the purchase your making.

Negative Pole:

1- Gambling can be explained as investing in something you know everything about.

2- Its inverse should be : Gambling can be explained as investing in something you know nothing about.

This deduces that gambling is investing even though you know nothing about the purchase your making.

The positive and negative poles are like yin and yang, they are the same yet they are polar opposites.

Gambling

Positive Pole:

1- Gambling in something you know nothing about is called gambling.

2- Its inverse should be : Investing in something you know nothing about is called investing.

This deduces that investing is investing and gambling is gambling. They are not the same in anyway.

Negative Pole:

1- Gambling in something you know everything about is called gambling.

2- Its inverse should be : Investing in something you know everything about is called investing.

This deduces that gambling is investing even though you know everything about the purchase your making.

The positive and negative poles are like Tom and Jerry, completely different. Upps, I forgot that they both like food.

Anyway, I know it was well of confusing but we’re gonna stick to only 2 logical meanings since this article was intended for your average reader.

1- Investing in something you know nothing about is called gambling.

2- Gambling can be explained as investing in something you know everything about.

The Phoenicians, were the first people to establish a trading network across the Mediterranean in the first millennium BCE, from an original base in modern Lebanon.

Investing in something you know nothing about is called gambling.

In simple terms, if you invest in something you know nothing about, the odds are you’re better of buying shit (because its the worst investment you could possibly make) or buying gold(this is the best investment you could make) because there’s a slight chance that you could be right (if accounting for randomness which is impossible to do). So investing in something you know nothing about aka gambling is very risky yet very rewarding in some instances but the odds of it being very rewarding are very slim. It’s like walking in a fog wishing the next step isn’t your last because you don’t know the path you’re walking on. That’s why doing your fundamental analysis properly is crucial for a safer investment. Noobs aka retards proceed with technical analysis first without checking if the investment is shit or not. How do you know if someone’s a noob ?

They would say: “ You can do a proper fundamental analysis and buy something good but at the wrong time (technical analysis), you’ll lose money. And you only do technical analysis and buy shit at the right time and still turn on a profit.”

I would totally agree with them, but why risk it ?! You can have the best of both worlds by buying something good and the right time. If it goes down, who the hell cares ? You can go to bed and sleep like a baby knowing that your investment will very likely turn a profit in the long run because you’re an investor not a day trader. You did your due diligence, you worked smart and hard for it and you’re gonna earn your rewards eventually.

Warren buffet said : “The longer you hold your asset, the less risky it becomes.“

Gambling can be explained as investing in something you know everything about.

Imagine doing all your research for the past 100 years on a specific investment. You’ve done your fundamental and technical analysis. You’re 100% sure that this is a very secure and very rewarding investment but a black swan happened and the company/coin went bankrupt and so as you. I won’t talk much about it except that this is very unlikely to happen like the 2008 mortgage crisis in the USA or the Terra Luna incident. No one was expecting it, maybe only a handful of people like Michael Burry who is exceptionally gifted in his field. I won’t talk much about it, because it’s unpredictable. Just take that L and move on. Professional investors use asset allocation and risk management to lower the risk of them losing all their money.

Philip Coggan, author of More (The 10,000-Year Rise of the world Economy) famously said : “Send your grains across the seas, and in time, profit will flow back to you. But divide your investments among many places for you do not know what risks might lie ahead.“

Conclusion

Dogecoin is an amazing and shitty asset at the same time. To see if it’s a good investment for you, you should go back to your values/morals and investment strategy. If it doesn’t fit your trading strategy or it doesn’t fit your beliefs then it isn’t the best investment for you.

Also consider the fact that since human beings are animals. For some probably most, acting rational is acting irrational. You can’t anticipate their next move since they are crazy psychopaths. So beware of these people because as you can see they are flooding the crypto market. $$\text{FUNDAMENTAL ANALYSIS}$$ protects you from them !!

Personal Opinion

As a blockchain developer, security researcher and cryptography enthusiast with a background ranging from finance, economics, psychology and data analytics, I follow the teachings of other well known economists such as Friedrich Hayek, Benjamin graham, Adam Smith, Nicholas Nassim Taleb. So from my personal research dogecoin isn’t an investments that fit my values and beliefs.

Hope you enjoyed this article as much as I did writing it and I hope you learned a thing or two about yourself. You are the only person who can give yourself what you want, you reap what you sow so put the work in and enjoy your success !!

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.

Pairings are used in commitment schemes, where the Prover commits to certain values (e.g., polynomials) without revealing them.

• The Verifier uses pairings to ensure the commitments are consistent with the proof and the public inputs.

• For example, pairings verify that a committed polynomial satisfies certain algebraic constraints.

• Bilinear pairings enable Verifiers to detect forgery or invalid proofs by enforcing algebraic consistency.

Homomorphism

Let’s take an example,

$$200 \space G+275 \space G = 475 \space G$$

$$\begin{align*} & A = 200 \space G \ & B = 275 \space G \ & C = 475 \space G \end{align*}$$

If I want to calculate what C is, there are two possible ways to do so.

Method 1 :

First calculate $$ 200 \times G = A$$ then $$275 \times G = B$$ and finally do $$A+B = 475 \space G = C$$.

Method 2 :

First calculate $$200 + 275 = 475$$ then do $$475 \times G = C$$

If you perform scalar multiplication first and then addition (Method 1), or addition first and then scalar multiplication (Method 2), both methods produce the same result. This property is why elliptic curve groups are said to be homomorphic under addition.

Example 1

The Prover calculates A and B, then sends A, B, and G to the Verifier. The Verifier computes A + B and returns C to the Prover. The advantage here is that the Verifier can do proper computation without knowing the underlying secret values.

Example 2

The Prover calculates A and B, then adds them together to obtain a new value C. The Prover then asks the Verifier to confirm whether A + B indeed equals C.

Both Example 1 and 2 are homomorphic under addition but are they homomorphic under multiplication ?

Calculating $$D$$ such that $$D = (200 \times 275) G$$ by multiplying $$A \times B$$ won’t work because we cannot multiply two elliptic curve points. We say this is not homomorphic under multiplication.

The only way we can calculate D is if we first multiply $$200 \times 275$$ then multiply the result with G.

Fully Homomorphic = homomorphic under addition and homomorphic under multiplication

Providing the Verifier with A and B alone does not allow them to compute D under multiplication. Therefore, similarly to example 2, where 200 and 275 remain secret, the Prover computes A, B, and D and sends them to the Verifier. Using elliptic curve pairings, the Verifier can then verify that $$A \times B = D$$.

Definition

Cryptographic pairings are special mathematical functions that map two group elements into a target group. Formally, a pairing $$e$$ is a function:

$$e : G_1 \times G_2 \rightarrow G_T$$

where $$G_1$$, $$G_2$$, and $$G_T$$ are groups, and the function 𝑒 satisfies the following properties:

• Bilinearity:

  For all $$a,b \in \mathbb{Z}$$, $$P \in G_1, Q \in G_2$$ :

  $$e(aP,bQ)=e(P,Q)^{ab} $$$

• Non-degeneracy:

  If $$𝑃 ≠ 0$$ and $$𝑄 ≠ 0$$, then $$𝑒 ( 𝑃 , 𝑄 ) ≠ 1$$ . This ensures the pairing provides useful information.

• Computability/Efficiency:

  There exists an efficient algorithm to compute $$e(P,Q)$$ for all $$P \in G_1, Q \in G_2$$.

Note that $$G_1$$ and $$G_2$$ are elliptic curve groups and $$G_T$$ isn’t.

Elliptic Curve Pairings

A pairing on $$(G_1,G_2,G_T)$$ defines the function $$e : G_1 \times G_2 \rightarrow G_T$$, and where $$g_1$$ is a generator for $$G_1$$ and $$g_2$$ is a generator for $$G_2$$. If we have the points of $$\color{lightblue}U_1$$ and $$\color{lightblue}U_2$$ on $$\color{lightblue}G_1$$ and $$\color{pink}V_1$$ and $$\color{pink}V_2$$ on $$\color{pink}G_2$$, we get the bilinear mapping of:$$ \begin{align*} & e(U_1+U_2,V_1)=e(U_1,V_1) \times e(U_2,V_1) \ & e(U_1,V_1+V_2)=e(U_1,V_1) \times e(U_1,V_2) \end{align*} $$If $$\color{lightblue}U$$ is a point on $$\color{lightblue}G_1$$, $$\color{pink}V$$ is a point on $$\color{pink}G_2$$ and $$\color{orange}a,b$$ are scalars, we get:$$ e(\textcolor{orange}{a}U,\textcolor{orange}{b}V)=e(U,V)^{\textcolor{orange}{ab}} = e(\textcolor{orange}{ab}U,V) = e(U,\textcolor{orange}{ab}V) $$If $$G_1$$ and $$G_2$$ are the same group, we get a symmetric grouping $$(G_1=G_2=G)$$, and the following commutative property will apply:$$ e(U^{\textcolor{orange}{a}},V^{\textcolor{orange}{b}})=e(U^{\textcolor{orange}{b}},V^{\textcolor{orange}{a}})=e(U,V)^{\textcolor{orange}{ab}} = e(V,U)^{\textcolor{orange}{ab}} $$$

As mentioned by Vitalik, “zk-SNARKs cannot be applied to any computational problem directly; rather, you have to convert the problem into the right “form” for the problem to operate on. The form is called a “quadratic arithmetic program” (QAP)”

Along with the process for converting the code of a function into a QAP is another process that can be run alongside so that if you have an input to the code you can create a corresponding solution (sometimes called “witness” to the QAP).

After this, there is another fairly intricate process for creating the actual “zero knowledge proof” for this witness, and a separate process for verifying a proof that someone else passes along to you, but these are details that are out of scope for this post.

Introduction

We will use the same example as Vitalik because it is simple enough that the resulting QAP will not be so large as to be intimidating, but nontrivial enough that you can see all of the machinery come into play. Our goal is to prove that we know the solution to a cubic equation :

$$x^3 + x + 5 = 35$$

As you can see, the solution for this is $$x=3$$. The Prover must thus show to Verifier that he knows the solution, without giving away the value 3.

To keep things simple, we will use a Galois Field (or finite field) of GF(641) which is a prime number.

If you’re not familiar with Modular Arithmetic, I recommend reading the Finite Fields and Modular Arithmetic for ZK Proofs chapter from Rareskills Zero Knowledge book before proceeding an further.

Problem Statement to R1CS

Definition of R1CS

Rank-1 Constraint System (R1CS) is a way to represent complex mathematical statements as a series of equations that a computer can verify efficiently. In essence, R1CS allows us to break down a problem into simple constraints that verify if a solution is valid. This let’s us easily prove to the Verifier that the Prover does really know a proper witness $$w$$ (solution) for a specific problem or in this case a cubic equation.

Step 1: Flattening

We have a function $$x^3 + x +5 = 35$$, we want to simplify it into multiple small functions called constraints which take the form of $$x = y \space (op) \space z$$ where $$(op)$$ can be any arithmetic operation $$(+, -, \times, /)$$.

$$\begin{align*} a &= x \times x \quad & x^2 \ b &= a \times x \quad & x^3 \ c &= b + x \quad & x^3 + x \ d &= c + 5 \quad & x^3 + x + 5 \end{align*}$$

We have 4 gates because in every line $$a, b, c$$ and $$d$$ we have one arithmetic operations. Since $$a$$ and $$b$$ both have multiplication, we’ll need two multiplication gates:Gate#1 and Gate#2. Similarly, since $$c$$ and $$d$$ both have addition, we’ll also need two addition gates: Gate#3 and Gate#4.

Step 2: Gates to R1CS

Next, we will need to convert the previous statements into the R1CS (Rank-1 Constrain System) format, and which defines three vectors: A, B and C. The solution to this is a vector $$(S)$$ that must satisfy the equation below.

$$(A.S) \times (B.S) - (C.S) = 0$$

. represents the dot product which is a mathematical operation that takes two vectors and returns a single number (a scalar) so it’s not multiplication.

The length of each vector is equal to the total number of variables in the system, including a dummy variable one at the first index representing the number 1 which allows all constraints to be written in a constant form, the input variable x, a dummy variable d representing the output, and then all of the intermediate variablesa, b and c. So we will use this layout to display the variables:

$$S=[1,x,a,b,c,d]$$

Other articles might use a different layout like the one below. They are all the same, they all serve the same purpose. You can structure your layout depending on your own needs.

$$S=[1,d,x,a,b,c,d,1]$$

In this case, the Prover proves that he knows a solution that satisfies the equation$$(x^3 + x +5 = 35)$$ by producing a vector S which is the witness $$w$$ for $$x = 3$$ :

$$\begin{align*} S = \text{witness} = [1, x, (x \times x), (x^2 \times x), (x^3 + x), (x^3 + x + 5)] \ S = \text{witness} = [1, 3, (3 \times 3), (9 \times 3), (27 + 3), (27 + 3 + 5)] \ S = \text{witness} = [1, 3, 9, 27, 30, 35] \end{align*}$$

For the First Constraint:

By applying $$x= 3$$ on our first constraint $$a =x \times x$$, we will get:

$$\begin{align*} A = [0,1,0,0,0,0] \ B = [0,1,0,0,0,0] \ C = [0,0,1,0,0,0] \end{align*}$$

So for $$x = 3$$, $$a= x \times x$$ will be represented as $$ 9 =3 \times 3$$ or $$3 \times 3 -9 = 0$$ . The first $$x$$ which is 3 will be in the second index of the vector A because the second index in $$S = [1,3,9,27,30,35]$$ is 3. The second $$x$$ which is also 3 will also be in the second index of vector B. This leaves us with 9 which will be in the third index of vectorC.

So the function $$(A.S) \times (B.S) - (C.S) = 0$$ for $$x = 3$$ will look like this in vector form :

$${ \small \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} \times \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} - \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} = \begin{pmatrix} 0 \end{pmatrix} }$$

For the Second Constraint:

Similarly to the first constraint, by applying $$x=3$$ on our second constraint $$b = a \times x$$, we will get:

$$\begin{align*} A = [0,0,1,0,0,0] \ B = [0,1,0,0,0,0] \ C = [0,0,0,1,0,0] \end{align*}$$

In simple terms, for $$x =3$$, the second constraint will become $$27 = 9 \times 3$$ or $$9 \times 3 -27 = 0$$. 9 is the third index in vector $$A$$, 3 is the second index in vector $$B$$ and 27 is the fourth index in vector $$c$$. Remember these vectors are made this way because of the structure of our layout for vector S :

$$S = [1, 3, 9, 27, 30, 35]$$

So the function $$(A.S) \times (B.S) - (C.S) = 0$$ for $$x = 3$$ will look like this in vector form :

$${ \small \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} \times \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} - \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} = \begin{pmatrix} 0 \end{pmatrix} }$$

For the Third Constraint:

By applying $$x = 3$$ on our third constraint $$c = b + x$$ or $$c = (b + x) \times 1$$, we will get:

$$\begin{align*} A = [0,1,0,1,0,0] \ B = [1,0,0,0,0,0] \ C = [0,0,0,0,1,0] \end{align*}$$

The third constraint will become $$30 = (27 + 3) \times 1$$ or $$(27 + 3) \times 1 - 30 =0$$.

27 is the fourth index in vector A and 3 is the second index in vector A. 1 is the first index in vector B and 30 is the fifth index in vector C.

$${ \small \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} \times \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} - \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} = \begin{pmatrix} 0 \end{pmatrix} }$$

So vector $$A$$ is $$3 + 27$$, vector $$b$$ is $$1$$ and vector $$C$$ is $$30$$. Thus, $$27 +3 - 30 = 0$$.

For the Fourth Constraint:

By applying $$x = 3$$ on our third constraint $$d = c + 5$$ or $$d = (c+5) \times 1$$, we will get:

$$\begin{align*} A = [5,0,0,0,1,0] \ B = [1,0,0,0,0,0] \ C = [0,0,0,0,0,1] \end{align*}$$

$${ \small \begin{pmatrix} 5 & 0 & 0 & 0 & 1 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} \times \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} - \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 \ \end{pmatrix} \begin{pmatrix} S \ \end{pmatrix} = \begin{pmatrix} 0 \end{pmatrix} }$$

We have 5 as the first index in vector A and $$c=30$$ as the fifth index in vector A. 1 is the first index in vector B and d = 35 is the last index in vector C.

After adding the vector A of all the constraints from 1 to 4 into a single vector A and doing the same thing for vector B and C, we will get the complete R1CS or final vector form of $$(A.S) \times (B.S) - (C.S) = 0$$ for $$x =3$$ :

$${\small {\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 1 & 0 & 0 \ 5 & 0 & 0 & 0 & 1 & 0 \ \end{pmatrix}} \begin{pmatrix} S

\end{pmatrix} \times {\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \ \end{pmatrix}} \begin{pmatrix} S

\end{pmatrix}

{\begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 \ \end{pmatrix}} \begin{pmatrix} S \end{pmatrix}

\begin{pmatrix} 0 \ 0 \ 0 \ 0 \end{pmatrix} }$$

Now let’s do the dot product of vector A,B and C with vector S but only for the first row of each vector to check if our calculations are correct.

For Vector A :

$${\begin{pmatrix} \textcolor{lightblue}{0} & \textcolor{lightblue}{1} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} \ 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 1 & 0 & 0 \ 5 & 0 & 0 & 0 & 1 & 0 \ \end{pmatrix}} \begin{pmatrix} \textcolor{lightblue}{1} \ \textcolor{lightblue}{3} \ \textcolor{lightblue}{9} \ \textcolor{lightblue}{27} \ \textcolor{lightblue}{30} \ \textcolor{lightblue}{35} \end{pmatrix} = 3$$

$$(0 \times 1) + (1 \times 3) + (0 \times 9) + (0 \times 27) + (0 \times 30) + (0 \times 35) = 3$$

For Vector B :

$${\begin{pmatrix} \textcolor{lightblue}{0} & \textcolor{lightblue}{1} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} \ 0 & 1 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \ \end{pmatrix}} \begin{pmatrix} \textcolor{lightblue}{1} \ \textcolor{lightblue}{3} \ \textcolor{lightblue}{9} \ \textcolor{lightblue}{27} \ \textcolor{lightblue}{30} \ \textcolor{lightblue}{35} \end{pmatrix} = 3$$

$$(0 \times 1) + (1 \times 3) + (0 \times 9) + (0 \times 27) + (0 \times 30) + (0 \times 35) = 3$$

For Vector C :

$${\begin{pmatrix} \textcolor{lightblue}{0} & \textcolor{lightblue}{0} & \textcolor{lightblue}{1} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} & \textcolor{lightblue}{0} \ 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 \ \end{pmatrix}} \begin{pmatrix} \textcolor{lightblue}{1} \ \textcolor{lightblue}{3} \ \textcolor{lightblue}{9} \ \textcolor{lightblue}{27} \ \textcolor{lightblue}{30} \ \textcolor{lightblue}{35} \end{pmatrix} = 9$$

$$(0 \times 1) + (0 \times 3) + (1 \times 9) + (0 \times 27) + (0 \times 30) + (0 \times 35) = 9$$

Final Equation :

$$(A.S) \times (B.S) - (C.S) = 3 \times 3 - 9 = 0$$

The Prover has provided the correct first part of the proof. We can then got through the other 3 rows for each vector A, B and C to find that the results will be zero but we won’t do it because you got the point. You can try it yourself and see that for every line $$A \times B - C$$ will always be zero. The Prover has thus proven that he knows the solution of the cubic equation. If you’re too lazy here’s the answers :

$$\begin{align*} 3 \times 3 - 9 = 0 \ 9 \times 3 - 27 = 0 \ (3+27) \times 1 - 30 = 0\ (5+30) \times 1 - 35 = 0 \ \end{align*}$$

To not create any confusion later we will refer to $$(A.S) \times (B.S) - (C.S) = 0$$ as

$$(A’.S) \times (B’.S) - (C’.S) = 0$$. A will be called A’, B’ for B and C’ for C.

R1CS to QAP

The next step is taking this R1CS and converting it into QAP form, which implements the exact same logic except using polynomials instead of dot products. We go from four groups of three vectors of length six to six groups of three degree-3 polynomials, where evaluating the polynomials at each x coordinate represents one of the constraints. That is, if we evaluate the polynomials at $$x=1$$, then we get our first set of vectors, if we evaluate the polynomials at $$x=2$$, then we get our second set of vectors, and so on.

We can make this transformation using something called a Lagrange interpolation. The problem that a Lagrange interpolation solves is this: if you have a set of points (i.e. (x, y) coordinate pairs), then doing a Lagrange interpolation on those points gives you a polynomial that passes through all of those points.

What we are going to do is take the first value out of every A’ vector, use Lagrange interpolation to make a polynomial out of that (where evaluating the polynomial at i gets you the first value of the ith A’ vector), repeat the process for the first value of every B’ and C’ vector, and then repeat that process for the second values, the third values, and so on.

Step 1

Since we have 4 constraints, we will choose values for $$x$$ such that $$x \in [ 1,2,3,4 ]$$.

We’re gonna have 6 polynomials against 6 variables and A’,B’,C’ are going to be these polynomials. Don’t worry if you didn’t understand this, we’ll explain everything.

We’re gonna evaluate each vector A,B and C for every value of $$x \in [ 1,2,3,4 ]$$ at every constraint.

First constraint

Remember vector A, B and C for the first constraint :

$$\begin{align*} A = [0,\textcolor{lightblue}{1},0,0,0,0] \ B = [0,\textcolor{lightblue}{1},0,0,0,0] \ C = [0,0,\textcolor{lightblue}{1},0,0,0] \end{align*}$$

We evaluate A, B and C for $$x = 1$$ :

$$\begin{align*} A_1(1) = 0 \hspace{1 cm} B_1(1) = 0 \hspace{1 cm} C_1(1) = 0 \ A_2(1) = \textcolor{lightblue}{1} \hspace{1 cm} B_2(1) = \textcolor{lightblue}{1} \hspace{1 cm} C_2(1) = 0 \ A_3(1) = 0 \hspace{1 cm} B_3(1) = 0 \hspace{1 cm} C_3(1) = \textcolor{lightblue}{1} \ A_4(1) = 0 \hspace{1 cm} B_4(1) = 0 \hspace{1 cm} C_4(1) = 0 \ A_5(1) = 0 \hspace{1 cm} B_5(1) = 0 \hspace{1 cm} C_5(1) = 0 \ A_6(1) = 0 \hspace{1 cm} B_6(1) = 0 \hspace{1 cm} C_6(1) = 0 \end{align*}$$

Second Constraint

$$\begin{align*} A = [0,0,\textcolor{lightblue}{1},0,0,0] \ B = [0,\textcolor{lightblue}{1},0,0,0,0] \ C = [0,0,0,\textcolor{lightblue}{1},0,0] \end{align*}$$

We evaluate A, B and C for $$x = 2$$ :

$$\begin{align*} A_1(2) = 0 \hspace{1 cm} B_1(2) = 0 \hspace{1 cm} C_1(2) = 0 \ A_2(2) = 0 \hspace{1 cm} B_2(2) = \textcolor{lightblue}{1} \hspace{1 cm} C_2(2) = 0 \ A_3(2) = \textcolor{lightblue}{1} \hspace{1 cm} B_3(2) = 0 \hspace{1 cm} C_3(2) = 0 \ A_4(2) = 0 \hspace{1 cm} B_4(2) = 0 \hspace{1 cm} C_4(2) = \textcolor{lightblue}{1} \ A_5(2) = 0 \hspace{1 cm} B_5(2) = 0 \hspace{1 cm} C_5(2) = 0 \ A_6(2) = 0 \hspace{1 cm} B_6(2) = 0 \hspace{1 cm} C_6(2) = 0 \end{align*}$$

Third Constraint

$$\begin{align*} A = [0,\textcolor{lightblue}{1},0,\textcolor{lightblue}{1},0,0] \ B = [\textcolor{lightblue}{1},0,0,0,0,0] \ C = [0,0,0,0,\textcolor{lightblue}{1},0] \end{align*}$$

We evaluate A, B and C for $$x = 3$$ :

$$\begin{align*} A_1(3) = 0 \hspace{1 cm} B_1(3) = \textcolor{lightblue}{1} \hspace{1 cm} C_1(3) = 0 \ A_2(3) = \textcolor{lightblue}{1} \hspace{1 cm} B_2(3) = 0 \hspace{1 cm} C_2(3) = 0 \ A_3(3) = 0 \hspace{1 cm} B_3(3) = 0 \hspace{1 cm} C_3(3) = 0 \ A_4(3) = \textcolor{lightblue}{1} \hspace{1 cm} B_4(3) = 0 \hspace{1 cm} C_4(3) = 0 \ A_5(3) = 0 \hspace{1 cm} B_5(3) = 0 \hspace{1 cm} C_5(3) = \textcolor{lightblue}{1} \ A_6(3) = 0 \hspace{1 cm} B_6(3) = 0 \hspace{1 cm} C_6(3) = 0 \end{align*}$$

Fourth Constraint

$$\begin{align*} A = [\textcolor{lightblue}{5},0,0,0,\textcolor{lightblue}{1},0] \ B = [\textcolor{lightblue}{1},0,0,0,0,0] \ C = [0,0,0,0,0,\textcolor{lightblue}{1}] \end{align*}$$

We evaluate A, B and C for $$x = 4$$ :

$$\begin{align*} A_1(4) = \textcolor{lightblue}{5} \hspace{1 cm} B_1(4) = \textcolor{lightblue}{1} \hspace{1 cm} C_1(4) = 0 \ A_2(4) = 0 \hspace{1 cm} B_2(4) = 0 \hspace{1 cm} C_2(4) = 0 \ A_3(4) = 0 \hspace{1 cm} B_3(4) = 0 \hspace{1 cm} C_3(4) = 0 \ A_4(4) = 0 \hspace{1 cm} B_4(4) = 0 \hspace{1 cm} C_4(4) = 0 \ A_5(4) = \textcolor{lightblue}{1} \hspace{1 cm} B_5(4) = 0 \hspace{1 cm} C_5(4) = 0 \ A_6(4) = 0 \hspace{1 cm} B_6(4) = 0 \hspace{1 cm} C_6(4) = \textcolor{lightblue}{1} \end{align*}$$

Step 2

We can see $$A_1(x), …, A_6(x)$$, $$B_1(x), …, B_6(x)$$ and $$C_1(x), …, C_6(x)$$ at every point $$x$$ from 1 to 4. We will display them in the format below :

$$\begin{align*} A_1(1) = 0 \hspace{1 cm} B_1(1) = 0 \hspace{1 cm} C_1(1) = 0 \ A_1(2) = 0 \hspace{1 cm} B_1(2) = 0 \hspace{1 cm} C_1(2) = 0 \ A_1(3) = 0 \hspace{1 cm} B_1(3) = 1 \hspace{1 cm} C_1(3) = 0 \ A_1(4) = 5 \hspace{1 cm} B_1(4) = 1 \hspace{1 cm} C_1(4) = 0 \ \hspace{0.5 cm}... \hspace{2.5 cm} ... \hspace{2.5 cm} ...\ A_6(1) = 0 \hspace{1 cm} B_6(1) = 0 \hspace{1 cm} C_6(1) = 0 \ A_6(2) = 0 \hspace{1 cm} B_6(2) = 0 \hspace{1 cm} C_6(2) = 0 \end{align*}$$

We have only a single polynomial of degree 3 that passes through $$A_1(1)$$ to $$A_1(4)$$. The polynomial will intersect the $$x-axis$$ at $$x = 1, 2 \space \text{and} \space 3$$ since the result for each one of them is 0 $$(A_1(1) = 0, A_1(2) = 0, A_1(3) = 0)$$ and will hit the line $$y = 5$$ for $$x = 4$$.

Or we can also take the $$ y-coordinates$$ in the first column in $$(A’.S) \times (B’.S) - (C’.S) = 0$$ for $$x \in [1,2,3,4]$$ resulting to 4 points $$(1,0), (2,0), (3,0), (4,5)$$ :

$${\small {\begin{pmatrix} \textcolor{orange}{0} & 1 & 0 & 0 & 0 & 0 \ \textcolor{orange}{0} & 0 & 1 & 0 & 0 & 0 \ \textcolor{orange}{0} & 1 & 0 & 1 & 0 & 0 \ \textcolor{orange}{5} & 0 & 0 & 0 & 1 & 0 \ \end{pmatrix}} \begin{pmatrix} S

\end{pmatrix} \times {\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \ \end{pmatrix}} \begin{pmatrix} S

\end{pmatrix}

{\begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 \ \end{pmatrix}} \begin{pmatrix} S \end{pmatrix}

\begin{pmatrix} 0 \ 0 \ 0 \ 0 \end{pmatrix} }$$

This is an arbitrary interpretation which we use to convert the R1CS into the QAP form. We could have as well used $$[5,7,9,11]$$ instead of $$[1,2,3,4]$$ as long as we are consistent across all equations.

The number of polynomials & their degree would depend on the length of the solution vector & the number of gates.

The solution vector S contains 6 elements $$[1, 3, 9, 27, 30, 35]$$, so we can construct 6 polynomials per vector. Each gate contributes 1 point to each polynomial. We have 4 gates here meaning we get 4 points per polynomial. 4 points allows us to define a polynomial of maximum degree 3. So we can construct 6 polynomials each with a maximum degree of 3.

A visual representation of the points for each polynomial of vector A’ will look like :

$$\begin{align*} \textcolor{orange}{(}A_1(1),..., A_1(4)\textcolor{orange}{)}, \textcolor{orange}{(}A_2(1),..., A_2(4)\textcolor{orange}{)}, \textcolor{orange}{(}A_3(1),..., A_3(4)\textcolor{orange}{)}, \ \textcolor{orange}{(}A_4(1),..., A_4(4)\textcolor{orange}{)}, \textcolor{orange}{(}A_5(1),..., A_5(4)\textcolor{orange}{)}, \textcolor{orange}{(}A_6(1),..., A_6(4)\textcolor{orange}{)} \end{align*}$$

So in total we have 3 vectors A’, B’ and C’ with 6 polynomials each, resulting in 18 polynomials.

We can find the polynomial passing through these 4 points using Lagrange Interpolation. We will only demonstrate for only the first polynomial and give you the result for all 18 polynomials. You can do the other ones by yourselves and compare your answers.

Lagrange Interpolation

To construct the Lagrange interpolation polynomial for the points $$(1,0),(2,0),(3,0),(4,5)$$ over a finite field with $$GF(641)$$, we’ll use the following approach.

Given points $$(x_1 ​ ,y_1 ​ ),(x_2 ​ ,y_2 ​ ), …, (x_n ​ ,y_n ​)$$, the Lagrange polynomial $$L(x)$$ is constructed as:

$$L(x) = \sum^n_{i=1} y_i ⋅ l_i(x)$$

where each $$l_i(x)$$ is the Lagrange basis polynomial for point $$(x_i, y_i)$$, defined by:

$$l_i(x) = \Pi_{j \neq i} \frac{x-x_j}{x_i - x_j} \space (mod \space 641)$$

In this case :

• The points are :

  • $$( 𝑥_1 , 𝑦_1 ) = ( 1 , 0 )$$

  • $$( 𝑥_2 , 𝑦_2 ) = ( 2 , 0 )$$

  • $$( 𝑥_3 , 𝑦_3 ) = ( 3 , 0 )$$

  • $$( 𝑥_4 , 𝑦_4 ) = ( 4 , 5 )$$

• Field $$GF(641)$$

Since $$𝑦_1 ​ =y_2 ​ =y_3 ​ =0$$, only $$𝑦_4 = 5$$ contributes to the polynomial, so we need only compute $$l_4 ( 𝑥 )$$.

Step-by-Step Calculation of $$l_4 ( 𝑥 )$$ :

$$l_4(x)= \frac{(x-x_1)(x-x_2)(x-x_3)}{(x_4-x_1)(x_4-x_2)(x_4-x_3)} \space (mod \space 641)$$

Substitute $$𝑥_1=1, 𝑥_2​ =2, 𝑥_3=3$$, and $$𝑥_4=4$$ :

1. Calculate the denominator :

   $$(4−1)(4−2)(4−3)=3⋅2⋅1=6 $$$

   Inverse of $$6 \space mod \space 641$$ is $$107$$, since $$6 \times 107 \equiv 1 \space (mod \space 641)$$.

2. Compute $$l_4 ( 𝑥 )$$ :

   $$$ l_4(x) = 107 ⋅(x−1)(x−2)(x−3) \space (mod \space 641) $$$

3. Expand $$(x-1)(x-2)(x-3)$$ :

   Expanding this product :

   $$$ (x−1)(x−2)=x^2−3x+2 $$$$$

(x^2−3x+2)(x−3) = x^3−3x^2 −3x^2+9x+2x−6 = x^3 −6x^2+11x−6 $$Substitute into $$l_4(x)$$ :$$ l_4(x)= 107(x^3−6x^2+11x−6)=107x^3 - 642x^2 + 1177x - 642 \space (mod \space 10) $$Final Polynomial $$L(x)$$ :$$ \begin{align*} L(x) &= y_4 \times l_4(x)=5 \times(107x^3 - 642x^2 + 1177x - 642 ) \space (mod \space 641) \ L(x) &= (535x^3 - 3210x^2 + 5885x - 3210) \space (mod \space 641) \end{align*} $$So the polynomial corresponding to the first Column of vector A’ is :$$ L(x)=535x^3+ 636x^2+ 116x+ 636 $$Since we didn’t calculated $$𝑦_1, y_2, y_3$$, you can ask chatgpt to calculate $$y_1, y_2, y_3, y_4$$ and generate the final polynomial if you have more than one point with coordinates other than 0.

Below are all coefficients of all 18 polynomials that we applied a finite field 641 to :

Polynomials of vector A’ : We’ll call the new vector, vector A’’.$$ {\begin{pmatrix} 636 & 116 & 636 & 535 \ 213 & 5 & 416 & 8 \ 635 & 330 & 637 & 321 \ 4 & 634 & 324 & 320 \ 640 & 536 & 640 & 107 \ 0 & 0 & 0 & 0 \ \end{pmatrix}} $$You can see the polynomial we got from the first column i.e. $$(535x^3+ 636x^2+ 116x+ 636$$) appear in first row of vector A’’. The Row is to be interpreted in reverse order - i.e. $$[4, 2, 3, 7]$$.

I’m going to re-explain what happened so we won’t get confused later. We applied Lagrange interpolation to the first column of vector A’ and we got the first row of vector A’’ but in reverse.$$ { \small {\begin{pmatrix} \textcolor{orange}{0} & 1 & 0 & 0 & 0 & 0 \ \textcolor{orange}{0} & 0 & 1 & 0 & 0 & 0 \ \textcolor{orange}{0} & 1 & 0 & 1 & 0 & 0 \ \textcolor{orange}{5} & 0 & 0 & 0 & 1 & 0 \ \end{pmatrix}} \longrightarrow {\begin{pmatrix} \textcolor{orange}{636} & \textcolor{orange}{116} & \textcolor{orange}{636} & \textcolor{orange}{535} \ 8 & 416 & 5 & 213 \ 635 & 330 & 637 & 321 \ 4 & 634 & 324 & 320 \ 640 & 536 & 640 & 107 \ 0 & 0 & 0 & 0 \ \end{pmatrix}} } $$Polynomials of vector B’ : We’ll call the new vector, vector B’’.$$ {\begin{pmatrix} 3 & 529 & 323 & 427 \ 639 & 112 & 318 & 214 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ \end{pmatrix}} $$Polynomials of vector C’ : We’ll call the new vector, vector C’’.$$ {\begin{pmatrix} 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 4 & 423 & 322 & 534 \ 635 & 330 & 637 & 321 \ 4 & 634 & 324 & 320 \ 640 & 536 & 640 & 107 \ \end{pmatrix}} $$This finishes the transformation of the problem to the QAP Form.

What do we achieve by converting it into the QAP form? Instead of checking the constraints in the R1CS individually, we can now check all of the constraints at the same time by doing the dot product check on the polynomials.

Our solution S has 6 elements $$[1, 3, 9, 27, 30, 35]$$. we can do a dot product of $$(S.A'')$$ whose output again will be a polynomial. Likewise for the other 2 polynomial matrices.

For vector A’’ :$$ {\begin{pmatrix} \textcolor{orange}{636} & \textcolor{orange}{116} & \textcolor{orange}{636} & \textcolor{orange}{535} \ 8 & 416 & 5 & & 213 \ 635 & 330 & 637 & 321 \ 4 & 634 & 324 & 320 \ 640 & 536 & 640 & 107 \ 0 & 0 & 0 & 0 \ \end{pmatrix}} \begin{pmatrix} \textcolor{orange}{1} \ \textcolor{orange}{3} \ \textcolor{orange}{9} \ \textcolor{orange}{27} \ \textcolor{orange}{30} \ \textcolor{orange}{35} \end{pmatrix} = ... $$We know the dot product is done by multiplying all the values of each row at a time in A’’ with vector S. Like this for the first row:$$ (636 \times 1) + (116 \times 3) + (636 \times 9) + (535 \times 27) + (0 \times 30) + (0 \times 35) = ... $$This approach is not correct!! Since we have rotated A’ going to A’’, we will need to calculate the dot product vertically like this for the first column :$$ {\begin{pmatrix} {636} & {116} & 636 & \textcolor{orange}{535} \ 8 & 416 & 5 & \textcolor{orange}{213} \ 635 & 330 & 637 & \textcolor{orange}{321} \ 4 & 634 & 324 & \textcolor{orange}{320} \ 640 & 536 & 640 & \textcolor{orange}{107} \ 0 & 0 & 0 & \textcolor{orange}{0} \ \end{pmatrix}} \begin{pmatrix} \textcolor{orange}{1} \ \textcolor{orange}{3} \ \textcolor{orange}{9} \ \textcolor{orange}{27} \ \textcolor{orange}{30} \ \textcolor{orange}{35} \end{pmatrix} = 529\textcolor{orange}{x^3} + 359\textcolor{orange}{x^2} + 354\textcolor{orange}{x} + 43 $$$$ \begin{align*} &(535 \times 1) + (213 \times 3) + (321 \times 9) + (320 \times 27) + (107 \times 30) + (0 \times 35) \ & 535 + 639 + 2889 + 8640 + 3210 + 0 = 15913\ \end{align*}
$$We do the same thing for all 4 columns while applying $$GF(641)$$ :$$ \begin{align*} & \text{1st column : } 15913 \textcolor{orange}{x^3} \ & 15913 \textcolor{orange}{x^3} \mod 641 = 529\textcolor{orange}{x^3} \ & \text{2nd column : } 34332 \textcolor{orange}{x^2} \ & 34332 \textcolor{orange}{x^2} \mod 641 = 359\textcolor{orange}{x^2} \ & \text{3rd column : } 37532\textcolor{orange}{x} \ & 37532\textcolor{orange}{x} \mod 641 = 354\textcolor{orange}{x} \ & \text{4th column : } 25683 \ & 25683 \mod 641 = 43 \end{align*} $$or we can rotate the vector A’’ to get 4 rows and 6 columns instead of 6 rows and 4 columns and do the dot product as we usually do it, horizontally.

For vector B’’ :$$ {\begin{pmatrix} 3 & 529 & 323 & 427 \ 639 & 112 & 318 & 214 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ \end{pmatrix}} \begin{pmatrix} 1 \ 3 \ 9 \ 27 \ 30 \ 35 \end{pmatrix} = 428\textcolor{orange}{x^3} + 636\textcolor{orange}{x^2} + 224\textcolor{orange}{x} + 638 $$$$ \begin{align*} & \text{1st column : } 1069\textcolor{orange}{x^3} \ & 1069\textcolor{orange}{x^3} \mod 641 = 428\textcolor{orange}{x^3} \ & \text{2nd column : } 1277\textcolor{orange}{x^2}\ & 1277\textcolor{orange}{x^2} \mod 641 = 636\textcolor{orange}{x^2} \ & \text{3rd column : } 865\textcolor{orange}{x} \ & 865\textcolor{orange}{x} \mod 641 = 224\textcolor{orange}{x} \ & \text{4th column : } 1920 \ & 1920 \mod 641 = 638 \end{align*} $$For vector C’’ :$$ {\begin{pmatrix} 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 4 & 423 & 322 & 534 \ 635 & 330 & 637 & 321 \ 4 & 634 & 324 & 320 \ 640 & 536 & 640 & 107 \ \end{pmatrix} } \begin{pmatrix} 1 \ 3 \ 9 \ 27 \ 30 \ 35 \end{pmatrix} = 537\textcolor{orange}{x^3} + 296\textcolor{orange}{x^2} + 499\textcolor{orange}{x} + 600 $$$$ \begin{align*} & \text{1st column : } 26818\textcolor{orange}{x^3} \ & 26818\textcolor{orange}{x^3} \mod 641 = 537\textcolor{orange}{x^3} \ & \text{2nd column : } 52217\textcolor{orange}{x^2} \ & 52217\textcolor{orange}{x^2} \mod 641 = 296\textcolor{orange}{x^2} \ & \text{3rd column : } 50497\textcolor{orange}{x} \ & 50497\textcolor{orange}{x} \mod 641 = 499\textcolor{orange}{x} \ & \text{4th column : } 39701 \ & 39701 \mod 641 = 600 \end{align*} $$So by taking the dot product of S with each of matrix A’’, B’’, C’’, we created 3 polynomials.$$ \begin{align*} & (A''.S) = 529\textcolor{orange}{x^3} + 359\textcolor{orange}{x^2} + 354\textcolor{orange}{x} + 43 \ & (B''.S) = 428\textcolor{orange}{x^3} + 636\textcolor{orange}{x^2} + 224\textcolor{orange}{x} + 638 \ & (C''.S) = 537\textcolor{orange}{x^3} + 296\textcolor{orange}{x^2} + 499\textcolor{orange}{x} + 600 \end{align*} $$We can define a new polynomial :$$ T = (A''.S) \times (B''.S) - (C''.S) $$$$ {\small T =
{\begin{pmatrix} 636 & 116 & 636 & 535 \ 213 & 5 & 416 & 8 \ 635 & 330 & 637 & 321 \ 4 & 634 & 324 & 320 \ 640 & 536 & 640 & 107 \ 0 & 0 & 0 & 0 \ \end{pmatrix}} \begin{pmatrix} 1 \ 3 \ 9 \ 27 \ 30 \ 35 \end{pmatrix} \times {\begin{pmatrix} 3 & 529 & 323 & 427 \ 639 & 112 & 318 & 214 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ \end{pmatrix}} \begin{pmatrix} 1 \ 3 \ 9 \ 27 \ 30 \ 35 \end{pmatrix} - {\begin{pmatrix} 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 4 & 423 & 322 & 534 \ 635 & 330 & 637 & 321 \ 4 & 634 & 324 & 320 \ 640 & 536 & 640 & 107 \ \end{pmatrix}} \begin{pmatrix} 1 \ 3 \ 9 \ 27 \ 30 \ 35 \end{pmatrix} } $$$$ \begin{align*} & {\small T(x) =(529\textcolor{orange}{x^3} + 359\textcolor{orange}{x^2} + 354\textcolor{orange}{x} + 43) \times (428\textcolor{orange}{x^3} + 636\textcolor{orange}{x^2} + 224\textcolor{orange}{x} + 638 ) - (537\textcolor{orange}{x^3} + 296\textcolor{orange}{x^2} + 499\textcolor{orange}{x} + 600) } \ & T(x) = 139\textcolor{orange}{x^6} + 372\textcolor{orange}{x^5} + 275\textcolor{orange}{x^4} + 58\textcolor{orange}{x^3} + 147\textcolor{orange}{x^2} + 379\textcolor{orange}{x} + 553
\end{align*}
$$In the R1S, we had checked if $$(A.S)∗(B.S)-(C.S) = 0$$ for each of the Gates. After conversion to QAP, we can do the same by checking the value of $$T$$ at $$x$$  at $$1,2,3,4$$- if all 4 are zero, then we have checked all the constraints together - thereby proving that the solution vector known to the Provers satisfies the equation.$$ T(1) = T(2) = T(3) = T(4) = 0 $$Let take a value, for example $$3$$ at lets check if its $$0$$ for $$T(3)$$ :$$ \begin{align*} & T(3) = 139 \times \textcolor{orange} {3^6} + 372 \times \textcolor{orange} {3^5} + 275 \times \textcolor{orange} {3^4} + 58 \times \textcolor{orange}{3^3} + 147\times \textcolor{orange}{3^2} + 379 \times \textcolor{orange}{3} + 553 \ & T(3) = 218581 \mod 641 = 0 \end{align*}
$$However, the Verifier doesn’t know the polynomial $$T$$, nor can he compute it since he doesn’t know the solution vector S. So the Prover has to prove it to the Verifier that $$T$$ is zero at $$x \in [1,2,3,4]$$. If T is really zero at $$x \in [1,2,3,4]$$, then we say that these are all roots of $$T$$. So we create a new polynomial $$Z$$ known by both the Prover & the Verifier. If $$T$$ is perfectly divisible by $$Z$$, then it will leave no remainder.

Let $$Z$$ be :$$ Z = (x-1) \times (x-2) \times (x-3) \times (x-4) $$So there must exist a Polynomial $$H$$ such that :$$ T(x)=H(x) \times Z(x) $$$$ H(x) = \frac {T(x)} {Z(x)} = \frac{ 139\textcolor{orange}{x^6} + 372\textcolor{orange}{x^5} + 275\textcolor{orange}{x^4} + 58\textcolor{orange}{x^3} + 147\textcolor{orange}{x^2} + 379\textcolor{orange}{x} + 553 } {((x-1) \times (x-2) \times (x-3) \times (x-4))} = 0 $$$

In real life $$T$$ won’t be equal to 0. If it was 0, the Prover can act maliciously and prove that $$H(x) = 0$$ for any kind of polynomial $$Z(x)$$. This was just an example. If you structure vector $$S$$ like this $$[\textcolor{orange}{1},\textcolor{orange}{35},3,9,27,30]$$, $$T(x)$$ will equal to :

Usually they put the dummy variables like 1 or the output $$d = 35$$ at the start or/and in the end of the vector so this structure is also true : $$[\textcolor{orange}{1},\textcolor{orange}{35},3,9,27,30,\textcolor{orange}{35},\textcolor{orange}{1}]$$ or $$[\textcolor{orange}{1},\textcolor{orange}{35},3,9,27,30]$$.

In a typical zk-SNARK, the Prover proves that $$Z$$ exactly divides $$T$$ using Polynomial Commitments & Elliptic Curve Bilinear Pairings.

This is the end of our article. Hope it wasn’t hard to understand. To make sure you fully understood, you can try different structures of vector S then check that $$T(x) = 0$$ for $$x \in [1,2,3,4]$$ and $$H(x) = \frac {T(x)} {Z(x)}$$ has no a remainder of 0.

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 }$$ ?

Let's say the Prover has a function $$g$$ that takes several binary variables, $$b_1,b_2,…,b_l$$, where each variable can only be either $$0$$ or $$1$$. The goal is for the Prover to convince the Verifier that he can compute the sum of the function $$g$$ evaluated on all possible combinations of these binary inputs correctly without any malicious intent.

This sum would be:

$$C = \sum_{b_1,b_2,…,b_l \in { 0,1 }} g(b_1,b_2,…,b_l)$$

simplified to :

$$\sum_{b_1 \in { 0,1 }} \sum_{b_2 \in { 0,1 }} ... \sum_{b_l \in { 0,1 }} g(b_1,...,b_l)$$

However, instead of the Verifier recomputing everything to check if the Prover’s claim is correct (which could take too long if there are many variables), they use the sumcheck protocol.

For instance suppose we define the function $$g$$ :

$$g(b_1,b_2,b_3,b_4,b_5)= 2b^2_1+b_2+b_1b_2b_3-b_4+b_2b^3_5$$

As you can see below, this function has a different evaluation for all possible combination of 0 and 1 for the variables of $$b_1$$ to $$b_5$$.

If the Prover has calculated the sum of all evaluations and combined them together by taking the result of $$g(b_1,b_2,b_3,b_4,b_5)$$ at every possible combination (32 combinations because $$2^5=32$$) and adding them up, it will amount to 44.

Quick demonstration:

If we replace $$g(b_1,b_2,b_3,b_4,b_5)$$ with $${ 0,0,0,0,0 }$$, we will get 0.

$$g(b_1,b_2,b_3,b_4,b_5)= 2b^2_1+b_2+b_1b_2b_3-b_4+b_2b^3_5$$

$$g(0,0,0,0,0) = 2 \times 0 + 0 + 0 \times 0 \times 0 - 0 + 0 \times 0 = 0$$

$$g(0,0,0,0,0) + g(0,0,0,0,1)+ ... + g(1,1,1,1,1) = 44$$

How can the Prover convince the verifier that the calculated value 44 is correct and has not been tampered with?

The naive solution is that the verifier could calculate the sum himself but this is time consuming, so we need a more efficient algorithm. The sum-check protocol provides a solution for this problem.

General Overview of Sumcheck Protocol

This is just a general overview, don’t worry if you don’t understand it. We’ll explain everything later so you skip it if you want.

• Start : Prover sends claimed answer $$C_1$$ which in our previous example was 44. The protocol must check that :

$$C_1 = \sum_{b_1 \in {0,1 }} \sum_{b_2 \in{0,1}} ... \sum_{b_l \in {0,1 }} g(b_1,...,b_l)$$

• Round 1 : Prover sends univariate polynomial $$S_1(X_1)$$ claimed to equal :

$$H_1(X_1) = \sum_{b_2 \in{0,1}} ... \sum_{b_l \in {0,1 }} g(X_1,...,b_l)$$

$$s_1$$ what the prover actually sends and $$H_1$$ is what the prover would send if the prover is honest. Note that the degree of $$H_1$$ and $$X_1$$ is at most the degree of the multivariate $$g$$ in its first variable meaning that if $$g$$ has a low degree in each variable (for example : 2 or 3) then even though there are $$2^{l -1}$$ terms in this sum, $$H_1$$ will simply be a degree 2 or 3 univariate polynomial. Hence, specifying $$H_1$$ can be done by just sending three or 4 coefficients.

Verifier checks that $$C_1 = s_1(0) + s_1(1)$$. If this check passes, it is safe for the Verifier to assume that $$C_1$$ is the correct answer, so long as the Verifier believes that $$s_1 = H_1$$. How do we check that ? We just check that $$s_1$$ and $$H_1$$ agree at a random point $$r_1$$.

• Round $$l$$ (Final Round): The Prover sends univariate polynomials $$s_l(X_l)$$ claimed to be equal :

  $$H_l := g(r_1,...,r_{l-1},X_l) $$$

Verifier checks that $$s_{l-1}(r_{l-1}) ] = s_l(0) + s_l(1)$$.

Verifier picks $$r_l$$ at random, and needs to check that $$s_l(r_l) = g(r_l,…,r_l)$$.

No need for more rounds, the verifier can perform this check with one oracle query. So after $$ l$$ rounds of interaction, the prover can convince the verifier.

Round One

In this example we will be sticking to our original function $$g$$:$$ \boxed {g(b_1,b_2,b_3,b_4,b_5)= 2b^2_1+b_2+b_1b_2b_3-b_4+b_2b^3_5} $$Prover knows the function $$g(b_1,b_2,b_3,b_4,b_5)$$ and he wants to compute :$$ C_1 = \sum_{b_1 \in {0,1 }} \sum_{b_2 \in{0,1}} \sum_{b_3 \in {0,1 }}\sum_{b_4 \in {0,1 }}\sum_{b_5 \in {0,1 }} g(b_1,b_2,b_3,b_4,b_5) $$

In the first step, the Verifier shares the function with the Prover and ask him what the summation of all evaluations which is $$C_1$$.

In the first round, the Prover calculates the required summation which is $$C_1$$. This means that the Prover needs to open the summation over all the variables of $$b_1$$ to $$b_5$$ for the values $$0$$ and $$1$$. For better comprehension, we can write the above image/function like this :$$ g(0,0,0,0,0) + g(0,0,0,0,1)+ ... + g(1,1,1,1,1) = 44 $$After the Prover has calculated the sum of all evaluations and combined them together, he will get the value 44 which is the required summation $$C_1$$.

Then the prover will have to share this value with the verifier. However only providing the value isn’t enough to satisfy the Verifier because she doesn’t know if the Prover has really done the work, has really calculated this summation properly. Thus some extra calculations need to be done and shared to satisfy the Verifier. We can’t upset the Verifier. The Prover might also need to buy her some flowers while he’s at it.

For the extra calculations, the Prover needs to define $$H_1X_1$$. This step is repetitive in different in every single interaction. So in each round the Prover has to form a function $$H_iX_i$$. In the first round, the Prover forms the function $$H_1X_1$$ by only swapping the first variable $$b_1$$ of function $$g$$, by $$X_1$$. This means that the Prover needs to hold this fixed variable and then calculate the summation based on the remaining variables $$b_2$$ to $$b_5$$. So each variable in the function g except $$X_1$$ can be either $$0$$ or $$1$$.

This computation leads a polynomial :$$ H_1(X_1) = 32X^2_1 + 4X_1 + 4 $$

By assuming that the Prover is malicious and might not have shared the accurate function $$H_1(X_1)$$, we will need to use a different notation as $$s_1(X_1)$$.

$$s_1$$ what the prover actually sends and $$H_1$$ is what the prover would send if the prover is honest.

We expect that $$s_1$$ should be equal to $$H_1$$. The Prover later sends $$C_1$$ as the summation of the evaluation, the polynomial $$s_1(X_1)$$ and the coefficient of the polynomial $$32X^2_1+4X_1+4$$ which are $${32,4,4 }$$.

On the verification side, the Verifier forms $$s_1(X_1)$$ using the received coefficients and then calculates $$s_1(0)$$ which is 4.

So the Verifier replaces $$X_1$$ with 0 in the polynomial $$32X^2_1+4X1+4$$ which results to $$32×0+4×0+4=4$$ and she did the same thing with $$s_1(1)$$ = $$32 \times 1 + 4 \times 1 + 4 = 40$$

We can see the equation is correct because $$s_1(0)+s_1(1)= C_1 =44$$ meaning the first check is approved.

This is not enough to satisfy the Verifier so we need to perform a second round. I guess the Prover should have also bought her some chocolate. Let’s keep going and see what’s his second move.

Round Two

The prover takes the previous function and changes $$b_1$$ to $$r_1$$ and $$b_2$$ to $$X_2$$$$ \boxed {g(r_1,X_2,b_3,b_4,b_5)= 2r^2_1+X_2+r_1X_2b_3-b_4+X_2b^3_5} $$

Then he proceeds to calculate the sum of all evaluations of function $$g(r_1,X_2,b_3,b_4,b_5)$$ over all possible values that consists of $$0$$ and $$1$$ for only $$b_3,b_4,b_5$$ and add them up to form a polynomial. This means that the Prover should not change $$r_1$$ and $$X_2$$ which are the first two variables to $$0$$ or $$1$$.

In the end, we will have a the equation :$$ (4r_1+12)X_2+16r^2_1-4 $$My guy has no rizz so she decided to give him a hint by sending him a random value $$r_1$$ equal to 93. He takes the random value $$r_1$$ and puts it in the equation above.$$ s_2(X_2) = (4 \times 93 +12)X_2+16 \times 93^2-4 = 352X_2+ 115596 $$The Prover was able to calculate $$s_2(X_2)$$ which is $$352X_2+ 115596$$ and similarly to the previous round the Prover should send the coefficient of the polynomial which is $${ 352,115596 }$$ to the Verifier (Bold move by the Prover).

On the verification side, the Verifier will calculate $$s_2(0) + s_2(1)$$ by changing $$X_2$$ to $$0$$ which gives us $$352 \times 0 + 115596 = 115596 = s_2(0)$$ and changing $$X_2$$ to $$1$$ which gives us $$352 \times 1 + 115596 = 115948 = s_2(1)$$.$$ s_2(0)+s_2(1) = 115596 + 115948 = 277144 $$In addition from the previous rounds, the Verifier knows the function $$s_1(X_1)$$so then the verifier could calculate the value of $$s_1(r_1)$$ by changing $$X_1$$ with $$r_1$$.$$ 32X^2_1+4X_1+4 = 32 \times 93^2 + 4 \times 93 + 4 = 277144 $$So the sum of $$s_2(0)+s_2(1)$$ should be equal to $$s_1(r_1)$$. The second test passed.

The verifier is convinced that the Prover did everything right till now.

Bro is winning but she’s playing hard to get.

Bro needs to be persistent and patient.

Let’s see his next move!!

Round Three

Like last time, the Verifier chooses another random value $$r_2 = 35$$ and sends it to the Prover (What a lucky guy). The Prover generates an updated version of our original function by replacing $$b_1, b_2$$ and $$b_3$$ with $$r_1,r_2$$ and $$X_3$$.$$ \boxed {g(r_1,r_2,X_3,b_4,b_5) = 2r^2_1 + r_2 + r_1r_2X_3 - b_4 + r_2b^3_5} $$He then proceeds to compute the function $$H_3(X_3)$$ by calculating the summation for the variables $$b_4$$ and $$b_5$$ which are the only two remaining values that should be replaced by $$0$$ and $$1$$.

$$ H_3(X_3) = s_3(X_3,r_2) = 4r_1r_2X_3 + 8r^2_1 + 6r_2 - 2 $$By replacing the values $$r_1​ = 93$$ and $$r_2​ = 35$$, the Prover will get :$$ s_3(X_3) = 13020X_3 + 69400 $$

Then the Prover will share the coefficients $${ 13020,69400 }$$ of the polynomial $$s_3(X_3)$$ with the Verifier so she can calculate $$s_2(r_2)$$.

Since she knows the coefficients of $$s_2(X_2)$$, she can calculate $$s_2(r_2)$$ and get the same value as $$s_3(0)+s_3(1) = 151820$$.

You may be asking how can she calculate $$s_2(r_2)$$ with only the coefficients ?

The Verifier receives the coefficients in this format :$$ [0, 0, 0, 0, 384, 138380] $$For more clarity, you can imagine the function $$s_2(r_2)$$ like this$$ [0(x^5), 0(x^4), 0(x^3), 0(x^2), 384(x), 138380] $$So from the coefficients, the Verifier can construct $$s_2(r_2)$$:$$ s_2(r_2) = 384x^2 + 138380 $$and then replace $$r_2$$ with 35 :$$ s_2(35) = 384 \times 35^2 + 138380 = 151820 $$This can be done by replacing $$X_2$$ with $$r_2$$. So we just replace $$r_1$$ with 93 and $$r_2$$ with 35 :$$ (4r_1+12)X_2+16r^2_1-4 = (4 \times 93 + 12) \times 35 + 16 \times 93^2 - 4 = 151820 $$$$ s_2(r_2) = s_3(0)+s_3(1) = 151820 $$If the two sides of the equation is correct then the next round passes.

Round Four

Round 4 is similar to round 2 and 3.

Round Five (Final Round)

I’d like to mention that we have 5 rounds of interaction between Prover and Verifier because we have 5 variables in the function $$g$$ → $$(b_1,b_2,b_3,b_4,b_5)$$.

5 Rounds of Interactions: (1,2), (3,4), (5,6), (7,8), (9,10).

So for the final round, the Verifier chooses a random value $$r_4$$. On the other side the Prover calculates the function g by replacing $$b_1$$ to $$b_5$$ by $$r_1,r_2,r_3,r_4,X_5$$$$ \boxed {g(r_1,r_2,r_3,r_4,X_5) = 2r^2_1 + r_2 + r_1r_2r_3 - r_4 + r_2X^3_5} $$$$H_5(X_5)$$ is similar to $$g(r_1,r_2,r_3,r_4,X_5)$$ because there’s no remaining variables to be replaced by $$0$$ and $$1$$ to calculate any summation.

The Prover will replace the variables $$r_1$$ to $$r_4$$ in $$s_5(X_5,r_4)$$ to get :$$ 35X^3_5 + 82407 $$and share the coefficients of the polynomial to the Verifier one last time .

The Verifier will calculate $$s_5(0) + s_5(1)$$ and check if its equal to $$s_4(r_4)$$ based on the coefficient received $$s_4$$ from the previous round and then the verifier.

This can be done by replacing $$X_4$$ with $$r_4$$.$$ s_4(r_4) = -2r_4 + 164901 = -2 \times 26 + 164901 = 164849 $$So $$s_5(0) + s_5(1)$$ is equal to $$s_4(r_4)$$. The test passes!!

Last Check

The only thing left is to check if the final round passes. The verifier picks a random value $$r_5 = 14$$ and then she will need to calculate $$ g(r_1,r_2,r_3,r_4,r_5)$$.

Since the verifier knows the function $$g$$, she can replace the variables $$b_1$$ to $$b_5$$ by $$r_1$$ to $$r_5$$ and calculate $$s_5(r_5)$$ :$$ g(r_1,r_2,r_3,r_4,r_5) = s_5(r_5) = 2r^2_1 + r_2 + r_1r_2r_3 - r_4 + r_2r^3_5 $$$$ g(93,35,20,26,14) = 2 \times 93^2 + 35 + 93 \times 55 \times 20 - 26 + 35 \times 14^3 = 178447 $$We then check $$s_5(r_5)$$ :$$ s_5(r_5) = 35r^3_5 + 82407 = 35 \times 14^3 + 81407 = 178447 $$Thus :$$ g(r_1,r_2,r_3,r_4,r_5) = s_5(r_5) = 178447 $$$

This means that the verifier is convinced that the first received value of $$C_1$$ which is 44 is the correct summation. Finally the Prover and Verifier are dating!!!!!

Conclusion

We can conclude that SumCheck Protocol needs $$l$$-rounds of interactions between Prover and Verifier to convince the Verifier that the summation was correctly computed. We can use Fiat-Shamir to make the SumCheck protocol non interactive.

Hope this was helpful and you finally understood the SumCheck Protocol. If you’re wondering there isn’t a season 2 for it so at least it was a happy ending.

Stay tuned for more !!

References

Ehsan Meamari

The Sum-Check Protocol

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.

Formulation :

The formulation of the multilinear extension can be thought of as a multi-dimensional extension of the Lagrange interpolation formula. The idea is to maintain the properties of the function at the vertices while allowing for interpolation within the entire hypercube.

Given as input all $$2^l$$ evaluations of a function $$f: { 0,1 }^l → \mathbb{F}$$, for any point $$r \in \mathbb{F}^l$$ there is an $$O(2^l)$$-time algorithm for evaluating $$\tilde{f}(r)$$.

Multilinear Extension Formula:

$$\tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$$

where $$\tilde{\delta}_w(r)$$ is the Multilinear Lagrange basis Polynomial corresponding to $$w$$ :

$$\tilde{\delta}w(r) = \Pi{i=1}^l(r_iw_i + (1-r_i)(1-w_i))$$

The formula $$\tilde{\delta}_w(r)$$ is part of a multilinear extension (MLE), which allows us to extend a function defined on binary inputs to work with real inputs between 0 and 1.

It works by multiplying together simple terms that either "pick" $$r_i​ $$or $$1− r_i​,$$ depending on whether the binary value $$w_i$$ is 1 or 0. This product ensures a smooth transition between the values at each binary point. Essentially, it blends between these binary points based on the real values of $$r$$, allowing us to interpolate the function over continuous inputs.

If you still don’t understand how it works, no worries you don’t need to. Just keep going and you’ll get a much simpler formula that you can use easily at the end.

How It Uses Lagrange Concepts

• Basis Structure: $$\tilde{\delta}_w(r)$$​, can be seen as a generalization of Lagrange basis polynomials. They ensure that at each vertex $$r​$$, the extension matches the value of $$f(r_i)$$, similar to how Lagrange interpolation ensures the polynomial passes through each point.

• Generalization: The multilinear extension extends the concept of interpolation from one dimension to multiple dimensions. The basis polynomials in both cases are structured to ensure that the extended function preserves the behavior of the original function at specified points (the vertices).

What is the Boolean Hypercube ?

A Boolean hypercube is a geometric representation of all possible binary values $${0, 1}$$ in n-dimensional space. Each vertex of the hypercube corresponds to an n-length binary string, and there are $$2^𝑛$$ n vertices in total, representing all possible combinations of 0 and 1.

For example:

• In a 1-dimensional Boolean hypercube, you have 2 vertices: $$0$$ and $$1$$, which is just a line.

• In a 2-dimensional Boolean hypercube, you have 4 vertices: $$(0,0),(0,1),(1,0),(1,1)$$, forming a square.

• In a 3-dimensional Boolean hypercube, you have 8 vertices:$$(000),(001),(010),(011),(100),(101),(110),(111),$$ forming a cube.

               000---------001
              / |          / |
             /  |         /  |    3-Dimensional Boolean Hypercube:
            010--------011   |    {000,001,010,011,100,101,110,111}
            |   |        |   |
            |   100------|-101
            |  /         |  /
            | /          | /
            110--------111
  

In ZKPs, you often need to work with functions that are defined over binary inputs. For instance, a function $$f$$ might be defined on inputs of length $$n$$ that are either 0 or 1, meaning $$f$$ is naturally defined on the vertices of a Boolean hypercube of dimension $$n$$. So a Boolean Hypercube is another way of describing our multivariate function.

Derivation of Multilinear Extension

• Building the Formula

  • Choose the points for interpolation: For bilinear interpolation in two dimensions, you generally have four points:

    • $$v_0 = (x_{v_0},y_{v0})$$

    • $$v_1 = ( 𝑥_{𝑣 1} , 𝑦{𝑣 _1})$$

    • $$v_2 = ( 𝑥_{𝑣 2} , 𝑦{𝑣 _2})$$

    • $$v_3 = ( 𝑥_{𝑣3} , 𝑦{𝑣 _3})$$

  • Lagrange Basis Functions:

    • To construct the MLE, we first need to define the Lagrange basis functions. These functions will ensure that the MLE passes through the vertex values of $$f$$.

    • The Lagrange basis functions for the vertices $$𝑣_0, 𝑣_1,$$, $$v_2$$ and $$v_3$$ ​ are:

$$L_0(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_1})((\textcolor{skyblue}{x_1}-x_{v_2})}{(x_{v_0}-x_{v_1})(x_{v_0}-x_{v_2})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_1})(\textcolor{skyblue}{x_2} -y_{v_2})}{(y_{v_0} -y_{v_1})((y_{v_0}-y_{v_2})}$$

$$L_1(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_2})}{(x_{v_1}-x_{v_0})(x_{v_1}-x_{v_2})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_2})}{(y_{v_1} -y_{v_0})((y_{v_1}-y_{v_2})}$$

$$L_2(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_1})}{(x_{v_2}-x_{v_0})(x_{v_2}-x_{v_1})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_1})}{(y_{v_2} -y_{v_0})((y_{v_2}-y_{v_1})}$$

$$L_3(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_1})}{(x_{v_3}-x_{v_0})(x_{v_3}-x_{v_1})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_1})}{(y_{v_3} -y_{v_0})((y_{v_3}-y_{v_1})}$$

Each $$L_i(x,y)$$ equals 1 at vertex $$v_i$$ and 0 at the other vertices meaning:

• $$L_0(x_1,x_2)$$ is 1 when $$𝑥1 ​ = x{v_0}$$ ​and $$𝑥2 ​ = y{v_0}$$, and 0 when either $$𝑥1 ​ = x{v_1}$$ or $$𝑥2 ​ = y{v_1}$$

• $$L_1(x_1,x_2)$$ is 1 when $$𝑥1 ​ = x{v_1}$$ ​and $$𝑥2 ​ = y{v_0}$$, and 0 when either $$𝑥1 ​ = x{v_0}$$ or $$𝑥2 ​ = y{v_1}$$

• $$L_2(x_1,x_2)$$ is 1 when $$𝑥1 ​ = x{v_0}$$ ​and $$𝑥2 ​ = y{v_1}$$, and 0 when either $$𝑥1 ​ = x{v_1}$$ or $$𝑥2 ​ = y{v_0}$$

• $$L_3(x_1,x_2)$$ is 1 when $$𝑥1 ​ = x{v_1}$$ ​and $$𝑥2 ​ = y{v_1}$$, and 0 when either $$𝑥1 ​ = x{v_0}$$ or $$𝑥2 ​ = y{v_0}$$

• Formulating the Multilinear Extension:

  • Now, we can express the multilinear extension $$\tilde{f}(x,y)$$ using the function values at the vertices and the Lagrange basis functions:

$$\tilde{f}(x_1,x_2) = \textcolor{skyblue}{f(v_0)}L_0(x_1,x_2) + \textcolor{skyblue}{f(v_1)}L_1(x_1,x_2) + \textcolor{skyblue}{f(v_2)}L_2(x_1,x_2) + \textcolor{skyblue}{f(v_3)}L_3(x_1,x_2)$$

• Final Formula (Simplified):

$$\tilde{f}(x_1,x_2) = \textcolor{skyblue}{f(v_0)}(1-x_1)(1-x_2) + \textcolor{skyblue}{f(v_1)}(1-x_1)x_2 + \textcolor{skyblue}{f(v_2)}x_1 (1-x_2) + \textcolor{skyblue}{f(v_3)}x_1x_2$$

You only need to understand this formula when dealing with MLEs without going through all of the math behind it.

$$\tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$$

So the Final Formula is basically this formula but written in a more elegant way.

Example

We define a bivariate function over the domain $${ 0,1 }^l$$ :

$$f(0,0)= 1 \space \space \space \space f(0,1) = 2 \space \space \space \space f(1,0) = 8 \space \space \space \space f(1,1) = 10$$

The MLE of the bivariate function will look like this:

$$\tilde{f}(x_1,x_2) =\textcolor{skyblue}{1}(1-x_1)(1-x_2) + \textcolor{skyblue}{2}(1-x_1)x_2 + \textcolor{skyblue}{8}x_1 (1-x_2) + \textcolor{skyblue}{10}x_1x_2$$

which we can simplify it to:

$$\tilde{f}(x_1,x_2) = 1+ 7x_1 + x_2 + x_1x_2$$

Notice that each of the four terms on the right hand side of the equation ensures that the MLE evaluates equally to our predefined values for the bivariate function:

$$f(0,0) = \tilde{f}(0,0) = \textcolor{skyblue}{1}⋅1 + 2⋅0 + 8⋅0 + 10⋅0 = \textcolor{skyblue}{1}$$

$$f(0,1) = \tilde{f}(0,1) = 1⋅0 + \textcolor{skyblue}{2}⋅1 + 8⋅0 + 10⋅0 = \textcolor{skyblue}{2}$$

$$f(1,0) = \tilde{f}(1,0) = 1⋅0 + 2⋅0 + \textcolor{skyblue}{8}⋅1 + 10⋅0 = \textcolor{skyblue}{8}$$

$$f(1,1) = \tilde{f}(1,1) = 1⋅0 + 2⋅0 + 8⋅0 + \textcolor{skyblue}{10}⋅1 = \textcolor{skyblue}{10}$$

So our MLE looks like this:

By replacing $$x_1$$ and $$x_2$$ in $$\tilde{f}(x_1,x_2)$$ by the indexes (4,5) we will get 54 which is the most bottom right cell.

$$\tilde{f}(x_1,x_2) = 1+ 7x_1 + x_2 + x_1x_2$$

$$\tilde{f}(5,5) = 1 + 7⋅4 + 5 + 4⋅5 = 1 + 28 + 5 + 20 = 54$$

Conclusion

$$Formula \space 1: \space \space \space \space \tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$$

$$Formula \space 2: \space \space \space \space \tilde{f}(x_1,x_2) = {f(v_0)}(1-x_1)(1-x_2) + {f(v_1)}(1-x_1)x_2 + {f(v_2)}x_1 (1-x_2) + {f(v_3)}x_1x_2$$

Both of these formulas represent multilinear extensions (MLE) of a Boolean function defined on binary points like $${0,1}$$ to a continuous domain.

The first formula is the general case for an $$l$$-dimensional Boolean function, where you're summing over all possible binary vectors $$𝑤 ∈ {0 , 1}^l$$ .

The second formula is the specific bivariate (2-dimensional) case, where $$l=2$$, and you're interpolating between the four possible binary inputs $$(0,0),(0,1),(1,0),(1,1)$$ as we saw in the previous example.

This is all you need to know about Multi-dimensional Lagrange Interpolation for Multilinear extensions. Hope this article was helpful. The next article will be a full guide on the sumcheck protocol. We’ll be applying everything we’ve learned so far.

This article cuts through the noise and gives you everything you need to understand them—without endlessly searching the internet or looping through videos (like I did).

I’ve got you covered. Ready? Let’s jump right in!

Overview

First of all, don’t be worried if you’re not familiar with Sumcheck Protocol and GKR Protocol, we’ll cover them in other article. You only need to understand that we have a Prover and a Verifier. The Prover generates a proof $$\pi$$ using public and private inputs and sends it to the verifier that will later accept or reject.

1. Multilinear Extensions (MLEs):

   A function $$f$$ (with multiple inputs) can be transformed into a multilinear polynomial. This allows us to represent the function in a more "manageable" form for certain cryptographic protocols. In ZKP systems, this is essential because polynomials have nice properties (like interpolation), which help in proving things efficiently. By turning a function into a polynomial, the prover can later prove things about it (like evaluations) without revealing the whole function.

2. Sumcheck Protocol:

   This is a way to prove that a sum over a large number of values (typically from a multilinear polynomial) is correct. Imagine you want to prove that the sum of evaluations of your multilinear polynomial at many points equals some value. Instead of having the verifier check every single evaluation (which is costly), the prover can use the sumcheck protocol to prove it with only a few rounds of interaction.

3. GKR Protocol (Goldwasser-Kalai-Rothblum):

   The GKR protocol is designed to verify computations over layered arithmetic circuits. These circuits consist of multiple layers of gates, each computing simple arithmetic functions like addition or multiplication. The protocol is structured to efficiently verify computations on these circuits. It allows a verifier to check the correctness of a computation (like a circuit or a function evaluation) by checking only a few random positions in the multilinear extension of the function.

   In your case, after the prover creates the multilinear extension and runs the sumcheck protocol, the GKR protocol can be used to verify that the entire computation (represented by the circuit) was done correctly using MLEs and sumcheck. The GKR protocol verifies whether the result of the computation is correct without requiring the verifier to redo the entire computation.

How They Work Together

• The prover takes a function (or computation) and transforms it into a multilinear extension (using MLE).

• The sumcheck protocol helps prove that the sum of evaluations of this multilinear polynomial is correct.

• The GKR protocol adds an extra layer by allowing the verifier to check that this computation was done correctly with minimal effort.

The process becomes non-interactive by applying Fiat-Shamir, allowing the prover to send the proof directly to the verifier, who can then easily check the proof without additional communication rounds.

What is an Extension ?

Imagine you have a function that works only on a specific set of values. For example, let's say you have a simple function that works on integers:

• For $$x=1$$, it gives 5

• For $$x=2$$, it gives 8

• For $$x=3$$, it gives 10

This function is only defined for $$x=1,2,3$$, but you might want to “extend” it so it works on other numbers like $$x=1.5, \space x=2.7$$, etc. That's called an extension—taking a function that works on a small set and extending it to work on more values.

Multilinear Extensions

Now, instead of just having one variable (like $$x$$), imagine you have multiple variables (like $$x$$ and $$y$$). A multilinear extension is when you take a function that only gives you results at specific combinations of values (like a list or table of results) and extend it to fill in all the gaps between those values. This means the function will work not just at those specific points but smoothly across all values in between.

Original Function (Specific Points Only)

Let's say we have a function that gives values only at specific points for $$x$$ and $$y$$. For example:

In this table, the function is only defined for $$x=0$$ or $$1$$, and $$y=0$$ or $$1$$.

But this function does not tell us what happens when $$x = 0.5$$ or $$y = 0.5$$, or other values in between.

Multilinear Extension (Filling in the Gaps)

Now, the multilinear extension smoothly fills in the gaps between the known points. It creates new values for points like $$x=0.5, \space y=0.5$$, etc. The table might look something like this:

Now, the function provides values not just for $$x=0$$ and 1, but also for points in between, like $$x=0.5$$, $$y=0.5$$. The values are calculated in a way that ensures smooth changes between the known points.

So, the multilinear extension allows the function to work not just at the original grid points (like $$x=0$$, $$y=0$$) but also at every point in between, like $$x=0.5$$, $$y=0.5$$, while ensuring the transitions are smooth and linear.

Why use it in ZKPs ?

In protocols like GKR, you're often working with huge amounts of data, but you want to prove things efficiently. Instead of dealing with all the data points individually, you can summarize the behavior of a function over a small set of values and then extend it to cover the whole space. This makes the computation easier and faster while preserving the structure of the data.

The Core Idea

The key idea is that multilinear extensions allow you to deal with complex, multi-variable functions in a more efficient way, by extending them from a small number of points to a larger range, while still keeping the math manageable.

Visualization

Imagine you're looking at a huge high-resolution picture (like 4K). Instead of sending or analyzing every single pixel, you take a few key points that define the overall image (like the corners and a few central spots). Then, you use these points to reconstruct the image at a lower resolution. It saves time, but you still get a good idea of what the whole picture looks like.

This is similar to how multilinear extensions work in ZKPs: you only work with a few key data points, extend the function over the rest of the space, and still have enough information to prove things about the whole dataset.

Example

If you have a dataset of 10 elements, you can pick 2 or 3 key elements, use those to create a multilinear extension of the function, and then evaluate that function on 4 or 5 elements to get a good representation of how the function behaves across the entire set. This way, you avoid the need to process all 10 elements directly.

Small Exercise

Let's do a simple exercise for a multilinear extension using two variables $$x$$ and $$y$$. I’ll explain the step-by-step process and then walk you through the solution.

Given the following values for a function $$f(x,y)$$ at four points:

$$f(0,0)=1, \space \space \space f(0,1)=3,\space \space \space f(1,0)=5,\space \space \space f(1,1)=7$$

Goal : Construct the multilinear extension of $$f(x,y)$$, and find the value of the function at $$(0.5,0.5)$$.

Steps

1. Start with the four known Key Points. We know the values of the function at $$(0,0), (0,1), (1,0)$$ and $$(1,1)$$.

2. Define the multilinear extension formula. For two variables, the multilinear extension is a bilinear interpolation between the known points.

   Bilinear Interpolation: is a fixed formula that applies universally when you have values at the four corners of a grid (in two dimensions) and by four corners I mean the four Key points $$(0,0), (0,1), (1,0) (1,1)$$. It always follows the same structure because it's derived from linear interpolation along two axes. (You can watch a video on Youtube that explains this formula in depth if want to know how its built).

   The general formula is :

   $$f(x,y)= \textcolor{skyblue}{f(0,0)}⋅(1−x)(1−y)+\textcolor{skyblue}{f(1,0)}⋅x(1−y)+\textcolor{skyblue}{f(0,1)}⋅(1−x)y+\textcolor{skyblue}{f(1,1)}⋅xy $$$

3. Substitute the known values of the function into the formula :

   $$$ f(x,y)=\textcolor{skyblue}{1}⋅(1−x)(1−y)+\textcolor{skyblue}5⋅x(1−y)+\textcolor{skyblue}3⋅(1−x)y+\textcolor{skyblue}7⋅xy $$$

4. Find the value at $$(0.5,0.5)$$ by plugging $$x=0.5$$ and $$y=0.5$$ into the formula:

   $$$ f(0.5,0.5)=\textcolor{skyblue}1⋅(1−0.5)(1−0.5)+\textcolor{skyblue}5⋅0.5(1−0.5)+\textcolor{skyblue}3⋅(1−0.5)⋅0.5+\textcolor{skyblue}7⋅(0.50⋅0.5) $$$

5. Now let’s calculate that step by step:

   $$$ f(0.5,0.5)=\textcolor{skyblue}1⋅(0.5)(0.5)+\textcolor{skyblue}5⋅0.5(0.5)+\textcolor{skyblue}3⋅(0.5)(0.5)+\textcolor{skyblue}7⋅(0.5)(0.5) $$$

   $$$ f(0.5,0.5)=\textcolor{skyblue}1⋅0.25+\textcolor{skyblue}5⋅0.25+\textcolor{skyblue}3⋅0.25+7⋅0.25 $$$

   $$$ f(0.5,0.5)=0.25+1.25+0.75+1.75=4 $$$

   Answer : The value of the multilinear extension of the function at $$(0.5,0.5)$$ is 4.

   This process shows how you can extend a function defined at a few specific points (in this case, 4 points) to other values (like $$x=0.5, y=0.5$$) using multilinear interpolation.

Notes

• A polynomial is considered multilinear if he has degree at most 1 in each variable for example: $$(1-x_1)(1-x_2)$$.

• $$x^2_1x_2$$ is not a multilinear polynomial because it has a variable with degree 2.

• Any function $$f$$ who’s domain is $${ 0,1 }^l$$ has many extension polynomials but only one of them will be exactly multilinear of degree at most 1 in each variable.

Recap with some visualize

Here we have a function $$f$$ defined on two bit inputs $${ 0,1 }^2$$.

$$f$$ has four inputs $$(0,0), (0,1), (1,0)$$ and $$(1,1)$$.

So for each of these four inputs, it spits out some field element:$$ f(0,0)=1, \space \space \space f(0,1)=2,\space \space \space f(1,0)=8,\space \space \space f(1,1)=10 $$and here is its multilinear extension:

The multilinear extension polynomial is defined over all pairs of field elements. Often when we run these interactive proofs the field size is say $$2^{64}$$ or $$2^{128}$$.

If $$f$$ has these four inputs $$(0,0), (0,1), (1,0), (1,1)$$, we can express $$\tilde{f}$$ via Lagrange interpolation where sum each of the four inputs to $$f$$ and ensure that the polynomial your defining $$\tilde{f}$$ has exactly the current behavior on that input.

Lagrange interpolation and bilinear interpolation are both methods used for estimating unknown values, but they serve different purposes and are applied in distinct contexts. So this function is the same as the previous one we saw in the small exercise.

So for example if $$f(0,0) = 1$$, this function is the Lagrange basis polynomial that captures that.$$ \tilde{f}(x_1,x_2) = \textcolor{skyblue}1(1-x_1)(1-x_2) + \textcolor{skyblue}2(1-x_1)x_2 + \textcolor{skyblue}8x_1(1-x_2) +\textcolor{skyblue}{10}x_1x_2 $$$$ \tilde{f}(0,0) = \textcolor{skyblue}1(1-0)(1-0)+\textcolor{skyblue}2(1-0)⋅0+\textcolor{skyblue}8⋅0(1-0)+\textcolor{skyblue}{10}⋅0⋅0 $$$$ \tilde{f}(0,0) = 1 + 0 + 0 + 0 = 1. $$$

So a function $$f$$ that has $${ 0,1 }^l$$ or $$2^l$$ inputs will take $$O(2^l)$$-time (linear time) algorithm for evaluating $$\tilde{f}(r)$$, $$r$$ being random points $$(x_i,x_j)$$ in the finite field $$F^l$$.

That concludes everything you need to know about Multilinear Extensions. It wasn't so hard, was it ? In the next article we’ll be covering a full guide on the sumcheck Protocol. If you think this article was helpful feel free to subscribe and share it, byby.