This has been copied from a hackmd post I made before this site was active.

Document structure

This document is split into five sections:

Preliminaries: This is background knowledge that will be helpful in understanding the rangeproof protocol.

PLONK Programs: This is the abstraction over PLONK that allows us to think of PLONK circuits as Programs where each row is a gate, and the row that the program is currently at is the state.

Rangeproof protocol: This section describes the rangeproof protocol by Aztec in isolation.

Rangeproof in PLONK: This section describes how the rangeproof protocol integrates into PLONK using the PLONK programs abstraction

Extras: Includes questions, details ommitted and further questions.

Notation

We use $11_2$ to denote a binary number. $11_2$ is therefore 3 in decimal. In general we use $abcd_b$ to denote the digits $a$, $b$, $c$, $d$ are in base $b$. If the base is omitted, then it means base-10 ie $3$ is the same as writing $3_{10}$

Preliminaries

This section will briefly note how rangeproofs work in essence using base-2. We then show how to convert a number represented in base-2 to a number represented in base-4, as this is the base that is used in the protocol by Aztec that is introduced.

Rangeproofs In Essence

The rough idea behind rangeproofs is the following:

• Given a number x, if for example, we can show that x can be represented using 4 bits.
• Then x must be between $0000_2$ and $1111_2$.
• In decimal x is within the range 0 and 15. $x \in [0, 2^4 -1]$

Generalisation

We can generalise the above argument.

• Given a number x, if we can show that x can be represented using n base-k digits.
• Then x must be between $\underbrace{00..0_k}_n$ and $\underbrace{(k-1)(k-1)..(k-1)_k}_n$
• In decimal $x \in [0,k^n -1]$

How do we show that x has n base-k digits?

This is protocol specific, this document will only discuss the method by Aztec. In their protocol, base-4(quaternary) is used. We therefore briefly recap, how to convert base-2 to base-4, as the number is initially given in base-2.

Base-2 to Base-4

Because $2^2 = 4$ converting between binary and quaternary is fairly trivial.

1. Given a number in binary form
2. Starting from the right, group each digit into pairs
3. Use Table1 to convert the numbers to base-4

We will elaborate with an example.

Table1 : Showing how to convert two binary digits to quaternary

Example

• Given x is $10011010_2$ .
• Lets split x into pairs $10; 01; 10; 10;$
• Using Table1, x in base-4 is $2 1 2 2_4$

What if we do not have an even number of binary digits?

Pad the left with an extra zero. Howver, in the protocol we will require an even number of digits.

Note

Note that if $x$ can be represented as 10 binary digits, then it can be represented as 5 quaternary digits. If $y$ can be represented as 11 binary digits, we must append a zero to make it even, so in quaternary $y$ can be represented as 6 digits.

PLONK Programs

This section will explain the abstraction from PLONK circuits to PLONK programs.

Brief overview of PLONK

In [2] Page 28, the quotient polynomial t(x) is defined.

We can split up the quotient polynomial into two parts:

• Part a asserts that the circuit must be satisfied (Circuit satisfiability)
• Part b asserts that the conditions for the Permutation argument must be satisfied. (Copy satisfiability)

We will focus on Part a, the circuit satisfiability equation.

$q_{M_i} a_i b_i + q_{L_i} a_i + q_{R_i} b_i + q_{O_i} c_i + q_{C_i} = 0$

The following equation asserts that the i’th gate must satisfy the following equation, where $a_i$ is the i’th left wire, $b_i$ is the i’th right wire and $c_i$ is the i’th output wire. The equation being satified at the i’th gate, depends on the values of $q_{M_i}$, $q_{R_i}$, $q_{L_i}$, $q_{O_i}$, $q_{C_i}$.

Note (can skip)

If we have n gates, we have n equations. In PLONK, these equations are merged together to form polynomials. ie $q_M(x)$ is the polynomial formed by merging each $q_{M_i}$ at each gate. $q_M(x)$, $q_L(X)$, $q_R(X)$, $q_O(X)$,$q_C(X)$ are called the selector polynomials. The set of selector polynomials is the circuit description.

Lookahead

We briefly note that the equation for the i’th gate, has access to the wires in the i+1’th gate.

Program

Observations

• The i’th equation will be applied to the i’th gate. We can think of PLONK as a collection of tuples $(equation_i, (a_i, b_i,c_i))$
• If each tuple is satisfied then our circuit is satisfied.

Below I will write out the tuples in a row.

Table2: Shows a PLONK program without the equations being applied to them

In Table2:

• Column A denotes all of the left wires for the circuit and so forth. ie $a_1$ is the first left wire in the first gate.
• Row 1 denotes the wires that are used in the first gate. This is the row that $equation_1$ will be applied to.
• The PLONK program is satisfied if $equation_i(a_i,b_i,c_i) = 0$ for all $i$

Definitions

Program width - The program width is the number of columns. The PLONK program in Table2 has a width of 3.

Program depth - The program depth is the number of row. The PLONK program in Table2 has a program depth of 3.

Square Program - If the program width is equal to the program depth, we say the program is square.

Summarising

We can now view PLONK circuits as PLONK programs where the i’th row signifies all of the wires at the i’th gate. A PLONK program is satisfied, if the corresponding equation is satisfied for each row.

Rangeproof Protocol

Goal: We want to prove that x is within the range $[0, 2^8 -1]$

Outline

We first convert x into base-4. We then prove using accumulators that $q_0$, $q_1$,$q_2$ and $q_3$ are base-4 digits that represent x, which means that x must be within the range $[0, 4^4 -1$ = $[0,2^8 -1]$

Preparation Stage

This stage takes a number in binary and converts it to base-4.

Let x be a 8-bit number.

$x = (b_0b_1b_2b_3b_4b_5b_6b_7)_2$ = $(q_0q_1q_2q_3)_4$

Accumulation Stage

In this stage, we accumulate our quaternary digits in such a way that allows us to constrain them to be between 0 and 3.

$n$ = The number of quaternary digits - 1. In our case n is 3.

The equation for the accumulators is as follows:

$a_i = \sum_{j=0}^{i} q_{(n-j)}4^{i-j}$

Checking the Accumulation Stage

This section computes each accumulator $a_i$ for x and makes a few observations that will allow us to assert the digits are indeed quaternary.

$a_0 = q_{3-0} * 4^{0-0} = q_3$

$a_1 = q_{3-0} * 4^{1-0} + q_{3-1} * 4^{1-1} = q_3 * 4 + q_2$

$a_2 = q_{3-0} * 4^{2-0} + q_{3-1} * 4^{2-1} + q_{3-2} * 4^{2-2} = q_3 * 4^2 + q_2 * 4 + q_1$

$a_3 = q_{3-0} * 4^{3-0} + q_{3-1} * 4^{3-1} + q_{3-2} * 4^{3-2} + q_{3-3} * 4^{3-3} = q_3 * 4^3 + q_2 * 4^2 + q_1 * 4 + q_0$

Let’s rewrite it without the algebra:

$a_0 = q_3$

$a_1 = q_3 * 4 + q_2$

$a_2 = q_3 * 4^2 + q_2 * 4 + q_1$

$a_3 = q_3 * 4^3 + q_2 * 4^2 + q_1 * 4 + q_0$

Observations

$q_2$

• Observe that $a_1 - 4 * a_0 = q_2$.
• if $q_2$ is a quaternary digit, then $a_1 - 4 * a_0 \in [0,1,2,3]$.
• This proves that $q_2$ is a base-4 digit.

$q_1$

• Observe that $a_2 - 4 * a_1 = q_1$.
• if $q_1$ is a quaternary digit, then $a_2 - 4 * a_1 \in [0,1,2,3]$.
• This proves that $q_1$ is a base-4 digit.

$q_0$

• Observe that $a_3 - 4 * a_2 = q_0$.
• if $q_0$ is a quaternary digit, then $a_3 - 4 * a_2 \in [0,1,2,3]$.
• This proves that $q_0$ is a base-4 digit.

What about $q_3$?

The easiest way to prove that $q_3$ is also a base-4 digit is to add an extra accumulator $a_{-1}$ whose value is zero.

• Observe that $a_0 - 4 * a_{-1} = q_3$
• If $q_3$ is a quaternary digit, then $a_0 - 4 * a_{-1} \in [0,1,2,3]$
• This proves that $q_3$ is a base-4 digit.

Constraining Stage

This section generalises the observations made when we checked the accumulation stage.

In general we observed that if :

$a_{i+1} - 4 * a_i \in [0,1,2,3]$

Then the digits that were used in the accumulators were all base-4. Since x can be represented with $q_0$, $q_1$, $q_2$, $q_3$$. x \in [0, 4^4 -1$ = $[0,2^8 -1]$

But wait

How do we know that these values represent x?

Notice that the last accumulator $a_3$ is equal to the value of x. ie the value that we are trying to prove is within the desired range. In the next section, we can link the two together by constraining $a_3 = x$ . This will cost an extra gate.

Rangeproof in PLONK

This section will explain how the rangeproof protocol and PLONK merge together.

Goal : We want to prove using our rangeproof protocol in PLONK, that a number x is within the range $[0,2^{32} -1]$

Preparation stage

1. We first initialise a PLONK program with a width of 4.

Table3: Shows a PLONK program with a width of 4

2. Add the value x you want to prove as a witness.

Accumulation stage

We compute the accumulators $(a_{-1},a_0, a_2, a_15)$.

Observe: For a 32 bit number, we will have 16 base-4 digits. Which in turn means, we will have 16+1 accumulators $a_i$ including the $a_{-1}$ accumulator. In general, to constrain a n-bit number, we will require $n/2 + 1$ accumulators.

Observations

For clarity, let’s observe what our program will look like with the accumulators added.

Table4: Shows a PLONK program with a width of 4

Focussing on the first row: We apply $a_{i+1} - 4*a_i$ to the following pairs of accumulators $(a_3, a_2)$ $(a_2, a_1)$, $(a_1, a_0)$ , $(a_0,a_{-1})$.

The only out of place tuple is $(a_3, a_2)$, however remember that PLONK equations have access to the wires in the row below it.

Observe : Each row has enough information to constrain 3 quaternary digits. However, when $a_{i+1} - 4*a_i$ is applied to a row, we can constrain 4 base-4 digits, because the equation has access to the next row. This is seen in Table4 where for a 32-bit number, we have 16 quaternary digits, however we need 5 rows, where the last row has unused wire values. In general, for an n-bit range proof, we will need $n/8 + 1$ rows.

How many gates?

Since each row signifies a gate, for a 32-bit range proof, we will require $n/8 + 1$ gates.

Row Equation

One caveat that has been glossed over is the equation that is applied to each row.

• How do we show that a number is either 0,1,2 or 3?
• Doesn’t the equation need to be equal to zero?

Outline

We show that each $A_i = a_{i+1} - 4*a_i$ is one of the roots to the polynomial $A(A-1)(A-2)(A-3)$

First we define 3 convenience variables, by repeatedly applying $a_{i+1} - 4*a_i$

$\delta_1 = c - 4d$

$\delta_2 = b - 4c$

$\delta_3 = a - 4b$

$\delta_3 = d_{next} - 4a$

$d_{next}$ is the d wire in the next row.

The equation for each row is as follows:

$\delta_1(\delta_1 -1)(\delta_1 -2)(\delta_1 -3) + \delta_2(\delta_2 -1)(\delta_2 -2)(\delta_2 -3) + \delta_3(\delta_3 -1)(\delta_3 -2)(\delta_3 -3) = 0$

This equation forces each $\delta_i$ to be either 0,1,2 or 3. This in turn forces each $a_{i+1} - 4*a_i$ to be 0,1,2 or 3.

Last Step

The last step is to constrain $a_{15}$ the last accumulator to the value $x$ where $x$ is the witness value that we were trying to prove was within a range.

Numbers

In order to constrain a 32-bit number in PLONK. It will require 6 gates. 5 gates to constrain the quaternary digits and an extra gate to constrain the last accumulator to the witness value.

Extras

Omissions

• The random challenge $\alpha$ that is applied to the circuit satisfiability equation was omitted.
• The public inputs polynomial $PI(x)$ was omitted from the quotient polynomial equation.

Possible questions

Why is base-4 used and not base-8?

Looking back at the Row Equation, if we use base-8 then the degree of the quotient polynomial will be 8n. This would increase the proof size by adding 5 extra elements. Instead of $t_{low}$, $t_{mid}$, $t_{high}$ we would have $t_1$,$t_2$,$t_3$,$t_4$,$t_5$,$t_6$,$t_7$,$t_8$.

Are there any advantages to using base-8 over base-4?

If we use base-8, there will be less digits. This is because, base-8 will use less digits to represent a number than base-4. This in turn means, that there will be less accumulators since the amount of accumulators will be proportional to the amount of digits we want to show is in base-8. Less accumulators means less witnesses, which means a smaller circuit size. But is this trade-off worth it because we add 5 extra group elements.

What about base-2?

Base-2 will not increase the quotient polynomial as the equation we would need to check for each row would be $A(A-1)=0$. We would however, have more witnesses. The question, I cannot answer is then How was base-4 chosen?

References

1. https://git.io/JI0SF
2. https://eprint.iacr.org/2019/953.pdf