PLOOKUP代码解析

1. 引言

Aztec团队Gabizon和Williamson 2020年论文 plookup: A simplified polynomial protocol for lookup tables。

代码实现参见：

• https://github.com/kevaundray/plookup 【Rust语言实现】
• https://github.com/neidis/plonk-plookup 【C/C++实现】

本文主要关注的是https://github.com/kevaundray/plookup库代码，由于其中scipr/zexe库已重构为arkworks-rs系列库，本人已fork修改为可兼容最新的arkworks-rs系列库，具体见：

• https://github.com/3for/plookup

代码基本结构为：

• kzg10 polynomial commitment scheme：具体见src/kzg10.rs目录，详细实现也可参看https://github.com/arkworks-rs/algebra/src/poly/。相比于 Dusk network的Plonk代码解析，arkworks-rs/algebra/src/poly/中增加了blinding属性，引入了random polynomial。
• multiset 定义及证明：具体见src/multiset目录。
• lookup table 定义及证明：具体见src/lookup目录。

2. multiset 证明

multiset 定义为：

/// A MultiSet is a variation of a set, where we allow duplicate members
/// This can be emulated in Rust by using vectors
#[derive(Clone, Eq, PartialEq, Debug)]
pub struct MultiSet(pub Vec);

其中：【令 d = n + 1 d=n+1 d=n+1】

• 将 s = ( f , t ) ∈ F 2 n + 1 s=(f,t)\in\mathbb{F}^{2n+1} s=(f,t)∈F2n+1 sort by t t t 的实现为：【若 f = ( 1 , 2 ) , t = ( 2 , 1 , 2 ) f=(1,2), t=(2,1,2) f=(1,2),t=(2,1,2)，则 s = ( 2 , 2 , 1 , 1 , 2 ) s=(2,2,1,1,2) s=(2,2,1,1,2)。】

/// Performs a element-wise insertion into the second multiset
    /// Example: f {1,2,3,1} t : {3,1,2,3} => 结果为$(3,3,1,1,1,2,2,3)$
    /// We now take each element from f and find the element in `t` then insert the element from `f` into right next to it's duplicate
    /// We are assuming that `f` is contained in `t`
    pub fn concatenate_and_sort(&self, t: &MultiSet) -> MultiSet {
        assert!(self.is_subset_of(t));
        let mut result = t.clone();

        for element in self.0.iter() {
            let index = result.position(element);
            result.0.insert(index, *element);
        }

        result
    }

• 将 s s s 平分，以便于多项式 h 1 h_1 h1表示前半部分，多项式 h 2 h_2 h2表示后半部分。由于 s s s的元素个数 2 n + 1 2n+1 2n+1为奇数，因此第 n + 1 n+1 n+1个元素为 h 1 h_1 h1的最后一个元素，为 h 2 h_2 h2的第一个元素。

/// Splits a multiset into halves as specified by the paper
    /// If s = [1,2,3,4,5,6,7], we can deduce n using |s| = 2 * n + 1 = 7
    /// n is therefore 3
    /// We split s into two MultiSets of size n+1 each
    /// s_0 = [1,2,3,4] ,|s_0| = n+1 = 4
    /// s_1 = [4,5,6,7] , |s_1| = n+1 = 4
    /// Notice that the last element of the first half equals the first element in the second half
    /// This is specified in the paper
    pub fn halve(&self) -> (MultiSet, MultiSet) {
        let length = self.0.len();

        let first_half = MultiSet::from_slice(&self.0[0..=length / 2]);
        let second_half = MultiSet::from_slice(&self.0[length / 2..]);

        (first_half, second_half)
    }

• 将FFT点值表示法 转换为 系数表示法：【将multiset中的元素看成是evaluations，转换为多项式系数表示。】

/// Treats each element in the multiset as evaluation points
    /// Computes IFFT of the set of evaluation points
    /// and returns the coefficients as a Polynomial data structure
    pub fn to_polynomial(&self, domain: &GeneralEvaluationDomain) -> Polynomial{
        Polynomial::from_coefficients_vec(domain.ifft(&self.0))
    }

• Lagrange base 表示为：对 i ∈ [ n + 1 ] i\in[n+1] i∈[n+1]，有 L i ( g i ) = 1 L_i(\mathbf{g}^i)=1 Li(gi)=1；对任意的 j ≠ i j\neq i j=i，有 L i ( g j ) = 0 L_i(\mathbf{g}^j)=0 Li(gj)=0，对应代码表示为：

// Computes the n'th lagrange poly for a particular domain
// Easiest way is to compute the evaluation points, which will be zero at every position except for n
// Then IFFT to get the coefficient form
// Note: n=0 is the first lagrange polynomial and n = domain.size() -1 is the last lagrange polynomial
pub fn compute_n_lagrange_poly(domain: &GeneralEvaluationDomain, n: usize) -> DensePoly{
    assert!(n <= domain.size() - 1);
    let mut evaluations = compute_n_lagrange_evaluations(domain.size(), n);
    domain.ifft_in_place(&mut evaluations);
    DensePoly::from_coefficients_vec(evaluations)
}
fn compute_n_lagrange_evaluations(domain_size: usize, n: usize) -> Vec{
    let mut lagrange_evaluations = vec![Fr::zero(); domain_size];
    lagrange_evaluations[n] = Fr::one();
    lagrange_evaluations
}

• “单个多项式 f ∈ F < n [ X ] f\in\mathbb{F}_{