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 , or more precisely its extension UltraPLONK that supports custom gates and lookup arguments. We’ll call it ( ).” PLONK 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 theorem, it can be known that only when conditions 1 and 2 are satisfied, the polynomials F and G satisfy: F≡G. Schwartz-Zippel 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: j<i 1≤j<i j j+1 1≤j<i sj sj+1 n+j sn+j+1 i. Z(g) = 1; ii. For 2 ≤ i ≤ n Z(g^i^) =(1 + β)^i-1^Π (ϒ + fj)Π (ϒ(1 + β) + t + βt ) / Π (ϒ(1 + β) + + β )(ϒ(1 + β) + s + β ) e. P sends polynomial Z to f. V check Z and meet the following conditions: I 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.

Zcash

Exploring Popular zkEVM Solutions:  AppliedZKP, Matter Labs, Hermez, and Sin7Y

Halo Principle Explained

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Too Long; Didn't Read

Make resilience your competitive advantage

Plookup — An Algorithm Widely Used in zkEVM

Plookup — An Algorithm Widely Used in zkEVM

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

How Binius Reduces Computational Complexity with Towers of Binary Fields

10,000 Weddings and an Election: Bringing Blockchain to the Public Sector

10 DeFi Projects to Keep Your Eye On in 2021

10 DAOs You Need to Know About Right Now

10 Best No-Code NFT Avatar Creators

How Binius Reduces Computational Complexity with Towers of Binary Fields

10,000 Weddings and an Election: Bringing Blockchain to the Public Sector

10 DeFi Projects to Keep Your Eye On in 2021

10 DAOs You Need to Know About Right Now

10 Best No-Code NFT Avatar Creators

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps