Plookup — An Algorithm Widely Used in zkEVM

In the last series, we analyzed ZKP algorithm Halo and Halo2, which were introduced by the Zcash team. The ZKP algorithm has high performance, provides a scalable architecture for private payments, and does not require trusted settings. Let’s see how the algorithm is designed.

The ZKP algorithm was called Halo at the beginning, and the polynomial IOP scheme mentioned in the Sonic algorithm was adopted. On the basis of this scheme, a recursive proof composition without a trusted setup was realized. However, the Zcash team found that it is not fast enough and a faster polynomial IOP solution should take its place, maybe Marlin? or Plonk?

The most efficient one should be Plonk, and it offers great flexibility to “design based on specific application requirements for high efficient implementation”, which is essential for the development of a more efficient version of Halo. In the Halo2 design manual, the following sentences stood out:

“The arithmetization used by Halo 2 comes from PLONK, or more precisely its extension UltraPLONK that supports custom gates and lookup arguments. We’ll call it UPA (UltraPLONK arithmetization).”

Not surprisingly, there is no such thing as “most effective”, only” more effective”.

“Halo2 uses the following lookup technique, which allows for lookups in arbitrary sets, and is arguably simpler than Plookup.”

So it seems that it is difficult to understand Halo2 without studying Plookup. 

Plookup Principle

First, let’s take a look at the design idea of Plookup:

 “we precompute a lookup table of the legitimate (input, output) combinations; and the prover argues the witness values exist in this table.”

1. Calculate in advance a lookup table composed of valid (input, output);

2. Prover proves that witness exists in this table.

It seems that the prover only needs to prove the existence of a legal witness in a pre-calculated lookup table, rather than prove the existence of a legal witness through circuit calculation. If the former is more efficient, then theoretically the scale of the circuit can be reduced. Next, let us analyze the specific principles of Plookup:

Concept

• Positive integer: n,d
• Vector: f € Fn, t € Fd
• Relationship: f € t  {fi}i€[n] € {ti}i€[d]
  Note: Each element in t appears at least once in f, and there is no repeating element in t
• Cyclic group: H = {g,…,gn+1 = 1}, and the order is n+1 
  Note: For polynomial f € F<n[X], fi = f(gi). f is sorted by t. When f € t, the order of the elements in f is the same as that in t, namely:
  For any i < i`，satisfies fi < fi`
  Then: if tj = fi tj` = fi`
  Then: j < j`
  For: f € Fn, t € Fd, s € Fn+d, define the bivariate polynomial F, G:

F ≡ G, if and only if:

1. f € t, meaning all elements in t appear at least once in f;

2. s is (f, t) sorted by t, i.e., s is the union of f and t, and the order of elements in s is the same as t.

According to the Schwartz-Zippel theorem, it can be known that only when conditions 1 and 2 are satisfied, the polynomials F and G satisfy: F≡G.

Main Scheme

1. Preprocessed polynomials: t € F<n+1[X], as lookup values

2. Inputs: f € F<n[X]

3. Protocol:

• a. Let s: = (f, t) € F2n+1 sorted by t
• b. P set the polynomial h1,h2 € F<n+1[X], satisfying: h1(i) = si, h2(i) = sn+i i € [n+1], and send it to a trusted third party I
• c. V randomly selects the parameters β and γ and sends them to P
• d. P calculates the polynomial Z € F<n+1[X], in the form:

i. Z(g) = 1;
ii. For 2 ≤ i ≤ n Z(g^i^) =(1 + β)^i-1^Πj<i(ϒ + fj)Π1≤j<i(ϒ(1 + β) + tj + βtj+1) / Π1≤j<i (ϒ(1 + β) + sj + βsj+1)(ϒ(1 + β) + sn+j + βsn+j+1)

• e. P sends polynomial Z to If. V check Z and meet the following conditions:

i. L1(x)(Z(x) — 1) = 0 //The first item is 1
ii. (x — gn+1)Z(x) (1 + β)(ϒ + f(x))(ϒ(1 + β) + t(x) + β·t(x·g)) = (x — gn+1)Z(x·g)(ϒ(1 + β) + h1(x) + β·h1(x·g))(ϒ(1 + β) + h2(x) + β·h2(x·g)) // Ensure the valid form of the polynomial Z in the range of 2 ≤ x ≤ n
iii. Ln+1(x)(Z(x) — 1) = 0 // Multiply all the elements in the numerator and denominator, Z(gn+1) = 1  f € t
iv. Ln+1(x)(h1(x) — h2(x·g)) = 0 // Ensure that h1(gn+1) = h2(g) represents the entire s

Extension to Vector Lookups

Assuming that there are multiple polynomials f1,f2,…,fw € F<n[X], and a lookup tables t* € (Fw)d, we want to check that for any j, (f1(j), f2(j),…,fw(j)) € t*.

Approximate process:

1. Express lookup tables t* := {t1, t2,…tw}

2. Compress with random number a, a comes from V

3. Use the compressed f and t to prove f € t, the process is as shown above

4. f € t  j € [n], (f1(j), f2(j),…,fw(j)) € t*

5. Security is guaranteed by Schwartz-Zippel

Extension to Multiple Tables

The previous section showed a scenario where multiple polynomials f=>1 table. Now consider the scenario where multiple polynomials f=>multiple tables. The idea is relatively simple:

1. Integrate multiple tables into one table

2. Add a new column that represents the table index, which is used to indicate which sub-table the value f of the polynomial set is in for different values of i

As shown below:

Better Range Check

It can be observed that if we set the values in the lookup tables to continuous values, such as ti = i -1, then in fact this protocol becomes a verification f € {0, …d — 1}, which proves the complexity is only 5n+2, assuming d=n+1. The specific protocol is not described in detail here. If you have grasped the above protocol, you will find it not difficult to understand the range check part.

Conclusion

This article shows the principle and design ideas of Plookup, a technology that is widely adopted in zkEVM. We will continue to study zkEVM in the follow-up articles.