Caulk: Lookup Arguments in Sublinear Time

Abstract

本文提出了向量承诺的位置隐藏链接性（position-hiding linkability），该性质可以在零知识证明中证明构成承诺cm的一个或m个值都属于$C$中承诺的大小为$N$的向量

对于单个和多个成员证明，Caulk协议的效率比Merkle SNARK高一百倍，渐进的，Caulk的Prover Time需要$O(m^2+m\log N)$来证明一批$m$个揭示，证明大小为常数，Verifier Time为$O(\log(\log N))$

作为lookup argument，若预处理时间为$O(N\log N)$，且存储空间为$O(N)$，Caulk为第一个达到PT与表大小呈亚线性关系的方案，该方案可用于各类可验证计算，以显著减少查找开销

1 Introduction

向量承诺是一种基本的密码方案，它是许多构造和协议的基础，向量承诺是一种紧凑的数据结构，它包含可能非常多的元素，并允许证明某个特定元素已被承诺

对于保护隐私的应用程序，证明的零知识性非常重要，例如隐藏声明在承诺中的元素，同时仍然与该元素建立某种关系或链接

若允许你知道一个秘密$s_i$在数学上与$c_i$链接，则称一个向量承诺$c=(c_1,...c_N)$为可链接的

另一个例子是可验证计算中的lookup argument：证明计算中间值$a_1,...,a_m$包含在某个表中，其他应用还包括会员证明、环形签名、匿名证书和其他方案

目前，所有上述示例都是使用涉及大量计算开销的密码原语来解决的，因此也限制了它们的可扩展性和实用性，Zcash加密货币的第一个版本使用基于SHA-2的Merkle树来存储硬币，并使用Groth16-SNARK来证明硬币所有权

另一个值得关注的应用是以Plookup为代表的lookup table，但是Plookup的通用构造中，无论查找多少值，Prover的开销至少与表本身一样大

lookup argument的目的和之前plookup的初衷一样，就是解决一些算法中难以算术化的位运算，因此也是目前的研究热点之一

2 Preliminaries

这篇paper是基于配对来构造lookup的，所以得有一个配对，基本的记法和之前用到配对的文章一样，第一和第二源群分别为$\mathbb G_1,\mathbb G_2$，目标群为$\mathbb G_T$，三个群的阶均为素数$q$，$[1]_1,[1]_2$分别表示两个源群的单位元

此外，本文还需要第一源群中的另一个生成元，记为$[h]_1=h\cdot [1]_1$

然后记$\omega$为单位根，有$\omega^N=1$，并定义集合$\mathbb H=\{1,\omega,...,\omega^{N-1}\}$​

记$\lambda_i(X)$为第$i$个拉氏多项式，集合$\mathbb H$的消失多项式为$z_H(X)=\prod^{N-1}_{i=0}(X-\omega^i)=X^N-1$

2.1 Cryptographic Assumptions

方案的安全性来自于代数群模型（Algebraic Group Model，AGM），密码学假设采用DLOG，q-DHE，q-SFrac和q-SDH的双线性版本

2.2 The KZG Polynimial Commitment Scheme

之前的博客介绍过了，可以看之前的内容

同时KZG还可以用来做向量承诺，也介绍过了

2.3 Subset openings

比如有一个向量$\vec c\in \mathbb F^m$和一个集合$I\sub [m]$，Tomescu等人提出了一个子向量揭示方案，且适用于KZG向量承诺

记子向量为$\vec c_I$，计算与其相关的多项式$C_I(X)=\sum_{i\in I}c_i\tau_i(X)$，其中$\{\tau_i(X)\}$是集合$\{\omega^{i-1}\}_{i\in I}$的拉氏基多项式，与之对应的消失多项式为$z_I(X)=\prod_{i\in I}(X-\omega^{i-1})$

根据KZG方案，有$C(X)-C_I(X)=z_I(X)\cdot H(X)$，因此Prover揭示该子向量的方式是计算$\pi_I=[H]_1=[H(x)]_1$

Verifier的验证过程如下，将消失多项式$z_I(X)$映射到第二源群上的一个点，也即计算$[z_I]_2=[z_I(x)]_2$，将$C_I(X)$映射到第一源群上的一个点，也即计算$C_I=[C_I(x)]_1$，然后用配对验证是否有下列等式成立，若成立则接受Prover

$$ e(C-C_I,[1]_2)=e([H]_1,[z_I]_2) $$

2.4 Multiple Openings

KZG可以在同一个多项式的多个点上揭示，比如令$p(X)$为承诺的多项式，$\vec \alpha\in \mathbb F^m$为揭示的点构成的向量，与多项式在$\vec \alpha$上的求值记为向量$\vec s$，也即$s_i=p(\alpha_i)$

令$C_{\vec \alpha}(X)$为度为$m-1$的多项式，满足$C_{\vec \alpha}(\alpha_i)=s_i$，对于所有的$i\in [m]$，当且仅当存在一个$Q(X)$，使得下面这个等式成立时，有$p(\alpha_i)=s_i$

$$ p(X)-C_{\vec \alpha}(X)=\prod_{i=1}^m(X-\alpha_i)\cdot Q(X) $$

具体而言，Prover计算$z_\alpha(X)=\prod_{i=1}^m(X-\alpha_i),C_{\vec\alpha}(X)=\sum^m_{i=1}p(\alpha_i)\cdot \tau_i(X)$，并计算

$$ Q(X)=\frac{p(X)-C_{\vec\alpha}(X)}{z_\alpha(X)} $$

令$s_i=p(\alpha_i)$，并计算承诺值为$[Q]_1=[Q(X)]_1$​

Verifier在验证过程中，先计算$C_{\vec\alpha}=[C_{\vec\alpha}(x)]_1,[z_\alpha(x)]_2$，并验证配对等式$e(C-C_{\vec\alpha},[1]_2)=e([Q]_1,[z_\alpha(x)]_2)$，若等式成立，则意味着等式$p(X)-C_{\vec \alpha}(X)=Q(X)\cdot z_\alpha(X)$成立

2.5 KZG for Bivariate Polynomials

这篇paper在原文的7.2用到了二元KZG的情况，感兴趣可以看原文

2.6 Proof of Opening of a Pedersen Commitment

本文用Pedersen承诺来隐藏$v$，从而实现零知识性，具体就是用到了之前说的额外的生成元$[h]_1$​

对$v$的Pedersen承诺为$cm=[v+hr]_1$，其中$r$为Prover选择的随机值

可以用基于FS的Sigma协议来证明Prover对$v,r$的知识，也即证明下列关系

$$ R_{ped}=\{(cm;(v,r)):cm=[v+hr]_1\} $$

证明值为一个第一源群的元素$R=[s_1+h\cdot s_2]_1$，其中$t_1=s_1+vc,t_2=s_2+rc$，其中$c=H(cm,R)$，$s_1,s_2$为Verifier提供的随机挑战

Verifier验证等式$R+c\cdot cm=[t_1+h\cdot t_2]_1$，当且仅当等式成立时，Verifier认为Prover知道$v,r$

3 Position-Hiding Linkable Vector Commitments

这篇paper的核心，提出了一个称为位置隐藏的可链接向量承诺（Position-Hiding Linkable Vector Commitments）

简单来说，给定两个向量承诺$C,cm$，Prover可以证明$cm$承诺的向量中的所有元素都是$C$承诺的向量中的元素

PHL的概念可以让Prover从一个公共集合或公共表中以零知识的方式隔离出部分元素，然后再进一步的证明这些元素的属性

PHL最重要的性质就是其链接性（Linkable），简单来说就是$cm$中承诺的元素必然也都在$C$中进行了承诺（大的集合包含了小的集合）

各种性质的定义可以看原文的Def 5.1

4 Linking Vectors with Elements

本节先介绍将一个Pedersen承诺$cm$与一个向量承诺$C$之间的链接，也即$m=1$的情况

具体而言，Prvoer希望向Verifie证明，将$C$在某个位置$i$揭示的值为$v$，且$v$正好是Pedersen承诺$cm$所承诺的值

这个过程需要用到两个单位根构成的群，分别是$\mathbb H=\{1,\omega,...,\omega^{N-1}\},\mathbb V=\{1,\sigma,...,\sigma^{n-1}\}$，其中$\omega^N=1,\sigma^n=1,n=\log (N)+6$，两个群的拉氏基多项式分别为$\{\lambda_i(X)\}^N_{i=1},\{\rho_i(X)\}^n_{s=1}$，消失多项式分别记为$z_H(X),z_{V_n}(X)$

方案可以分为三个步骤

1. 证明$cm$关于$v$的知识，也即证明上述2.6节中提到的的关系$R_{ped}$
2. 证明KZG的盲化版本，也即证明$C(\omega^{i-1})=v$，同时不暴露关于$i$和$v$的信息
   具体操作的方式是引入盲因子，之后会介绍
3. 第三步是证明这个盲化的KZG中用到的消失多项式具有正确的形式

第三步具体而言就是证明关系$R_{unity}$如下

$$ R_{unity}=\{(srs,[z]_2;(a,i)):[z]_2=[a(x-\omega^{i-1})]_2 \ \wedge \ (\omega^{i-1})^N=1 \} $$

4.1 Our Blinded Evaluation Construction

对于向量$\vec c$，可以将其编码为一个多项式$C(X)=\sum^N_{i=1}c_i\lambda_i(X)$，若要揭示该向量第$i$个位置的值（假设该值为$v$），可以令$Q(X)=\frac{C(X)-v}{X-\omega^{i-1}}$，然后计算$Q=[Q(x)]_1$

本文的方法是加入一个盲因子$a$来对$w^{i-1}$进行模糊承诺，并将其承诺至多项式$z(X)=aX-b=a(X-\omega^{i-1})$，其中$w^{i-1}=\frac{b}{a}$，对应的群元素为$[z]_2=[z(x)]_2$

由于集合$\{w^{i-1}\}^m_{i=1}$的是一个多项式的集合，在揭示$[x-w^{i-1}]_1$后，敌手可以通过穷举的方式找到这个$i$，从而也就暴露了$v$在向量中的位置

通过引入盲因子的方式来避免此类情况的发生，具体做法是构造两个盲化多项式$T,S$如下（$s$为Prover选择的随机数）

$$ T(X)=\frac{Q(X)}{a}+hs,S(X)=-r-s\cdot z(X) $$

然后计算$[T]_1=[T(x)]_1,[S]_2=[S(x)]_2$即可

这里$\frac{Q(X)}{a}$的目的是在$Q(X)$的分母上凑多项式$z(X)$，然后$[hs]_1$的目的是提供零知识性，$[S]_2$的目的是消除$[T]_1$和$cm$中带$h$的项（$[S]_2$需要与$[h]_1$进行配对，从而消除对应的项）

然后看一下配对的验证等式，验证等式需要验证$cm=[v+hr]_1$和$[z]_2=[ax-b]_2$，分别对应于$R_{ped}$和$R_{unity}$

$$ e(C-cm,[1]_2)=e([T]_1,[z]_2)+e([h]_1,[S]_2) $$

把这个配对展开成多项式，就得到了下面这样

$$ C(X)-v-hr=T(X)\cdot z(X)+h\cdot S(X) $$

把多项式$T,S$带入，可以得到

$$ C(X)-v-hr=(\frac{Q(X)}{a}+hs)\cdot z(X)+h(-r-s\cdot z(X))=\frac{Q(X)}{a}\cdot z(X)-hr $$

两边的$-hr$消去就可以得到$C(X)-v=\frac{Q(X)}{a}\cdot z(X)$

完整协议如下图所示

若AGM上有q-SDH和DLOG假设成立，则上述协议中的$C$和$cm$满足位置隐藏链接性

4.2 Correct computation of $z(X)$

本节主要介绍如何证明$z(X)$计算正确性，也即为关系$R_{unity}$提供零知识证明

关系$R_{unity}$中，需要证明Prover知道一对数$(a,b)$，满足$[z]_2=[ax-b]_2$，且$a^N=b^N$​

从图1中可以看到，该关系是图1中向量承诺链接性的一个子协议

为了在$N$次单位根构成的域上完成证明，利用一个很常用的方法，也即化减为除，之前需要证明的是$a^N-b^N=0$，化为除法就是证明$\frac{a^N}{b^N}=1$

具体的证明如下，构造一个多项式$f$，并将证明分为三个步骤

1. 令$f_0=\frac{a}{b}$
2. 对于$i\in 1,...,\log N$，有$f_i=f^2_{i-1}$
3. $f_{\log N}=1$

不难看出，证明$\frac{a^N}{b^N}=1$的方法用到了快速幂的思想，好处就是可以在$\log N$步内完成证明

但是，为了不在域上揭示$z(X)$，同时给出$f_0=\frac{a}{b}$的证明，这里需要将步骤1细分成五个步骤，具体如下

• $f_0=z(1)=a-b$
• $f_1=z(\sigma)=a\cdot \sigma-b$
• $f_2=\frac{f_0-f_1}{1-\sigma}=\frac{a(1-\sigma)}{1-\sigma}=a$
• $f_3=\sigma\cdot f_2-f_1=\sigma\cdot a-\sigma \cdot a+b=b$
• $f_4=\frac{f_2}{f_3}=\frac{a}{b}$

然后修改上面三个步骤的后两个，如下

1. 对于$i=0,...,\log N-1$，有$f_{5+i}=f^2_{4+i}$
2. $f_{4+\log N}=1$

然后将所有的这些约束，利用$\mathbb V_n$的拉氏基多项式整合到一个多项式$f(x)$中，也即$f(\sigma^i)=f_i$，然后得到了下面这个引理

Lemma 1：令$z(X)$为一个度为1的多项式，$n=\log (N)+6$，且对于根$\sigma$，有$\sigma^n=1$，若存在一个多项式$f(X)\in \mathbb F[X]$，满足下列六个条件，则有$z(X)=aX-b$，且$\frac{a}{b}$为N次根

1. 对于$X=1,\sigma$，有$f(X)=z(X)$
2. $f(\sigma^2)(1-\sigma)=f(1)-f(\sigma)$
3. $f(\sigma^3)=\sigma\cdot f(\sigma^2)-f(\sigma)$
4. $f(\sigma^4)\cdot f(\sigma^3)=f(\sigma^2)$
5. 对于所有的$i=0,...,\log (N)-1$，有$f(\sigma^{4+i+1})=f^2(\sigma^{4+i})$
6. $f(\sigma^{5+\log (N)-1})=1$

上述引理的证明在原文的附录C，引理中假设$n=\log (N)+6$，若不等的话可以通过填充的方式补齐

图2给出了多项式$f(X)$的约束条件的比较形象的图解

具体而言，Prover构造下列这个多项式，并以零知识的方式对该多项式进行承诺

$$ f(X)=(a-b)\rho_1(X)+(a\sigma-b)\rho_2(X)+a\rho_3(X)+b\rho_4(X)+\sum^{\log N}_{i=0}(\frac{a}{b})^{2^i}\cdot \rho_{5+i}(X) $$

之后通过计算$f(\sigma^i)$来验证引理1中的六个约束的正确性

具体而言，Verifier选择一个随机值$\alpha$发送给Prover，然后Prover令$\alpha_1=\sigma^{-1}\cdot \alpha,\alpha_2=\sigma^{-2}\cdot \alpha$，并在两个点$\alpha_1,\alpha_2$揭示多项式$v_1=f(\alpha_1),v_2=f(\alpha_2)$

对于给定的$v_1,v_2$，若引理1中的六个约束均满足，则下面这个多项式$p_\alpha(X)$在点$\alpha$处的值为0，这个多项式可以由Verifier自己计算，也可以由Prover揭示

懒狗懒得打字了，就这样截个图吧

利用$v_1,v_2$，对$h(X),f(X)$的承诺，$\rho_i(\alpha),i=1,2,3,4,n-1$以及$\prod_{i\notin [5,...,4+\log N]}(\alpha -\sigma^i)$，Verifier计算$p_\alpha(X)$的承诺值$[P]_1$，并验证下列三项

1. $v_1,v_2$为$f(X)$在$\alpha_1=\sigma^{-1}\cdot \alpha,\alpha_2=\sigma^{-2}\cdot \alpha$处的正确揭示
2. $p_\alpha(\alpha)=0$
3. $[z]_2$的度为1

前两个可以通过配对验证，第三个比较麻烦，需要让Prover在$h(X)$中加入一个额外的项$X^{d-1}\cdot z(X)$，这样Verifier可以在无需$z(X)$的情况下计算承诺值$[P]_1$，具体的协议在图3中

图3协议的证明在原文的附录D

5 Lookup tables for hiding values

第4节介绍了查找一个元素的情况（$m=1$），本节介绍查找一个向量的情况，也即KZG向量承诺方案的位置隐藏链接性算法，目的是证明承诺$cm$所承诺的向量是承诺$C$承诺的向量的一个子集

注意，这里指的是子集，而不是子向量，也即仅确保$cm$所承诺的元素都在$C$中承诺了，但不确保元素的顺序和元素是否重复，因此本质上就是将$C$作为查找表，然后用$cm$进行查找

Concrete efficiency

先看看效率，查找证明的预处理阶段，若表的大小为$N$，查找子集大小为$m$，承诺$C$需要$N \log N$次$\mathbb G_2$操作，Prover Time为$m\log N$次标量乘法，证明大小为常量，Verifier Time为$\log \log N$次标量乘法和常数次配对，更新证明需要$O(N)$次$\mathbb G_2$操作

Preliminaries

查找一个向量的子集需要三个群，假设查找的子集大小为$m$

1. $\mathbb H=\{1,\omega,...,\omega^{N-1}\}$，拉氏基多项式记为$\{\lambda_i(X)\}^N_{i=1}$，消失多项式记为$z_H(X)$
2. $\mathbb H_I=\{\omega^{i-1}\}_{i\in I}$，其中$I\sub [N]$，该集合的拉氏基多项式记为$\{\tau_i(X)\}_{i\in I}$，拉氏多项式的度为$|I|-1$，消失多项式记为$z_I(X)$
3. $\mathbb V_m=\{1,v,...,v^{m-1}\}$，满足$v^m=1$，拉氏基多项式记为$\{\mu_j(X)\}^m_{j=1}$，消失多项式记为$z_{V_m}(X)$

这里有一点需要注意，$\mathbb H_I$不是$\mathbb H$的子群，因为计算不满足封闭性

5.1 Technical Overview

本节的方案会作为$R_{unity}$关系的NIZK证明的子协议

$$ R_{unity}=\Big \{ (srs,[z_I]_2,N;(I,r)) : I\sub [N] \wedge [z_I]_2=r\prod _{i\in I}[x-\omega^{i-1}]_2 ,s.t.(w^{i-1})^N=1,\forall i\in I \Big \} $$

这个关系分为两部分证明，第一部分是证明下面这个关系$R'_{unity}$

$$ R'_{unity}=\Big \{ (srs,[u]_1,\mathbb H,\mathbb V) : [u]_1=[u(x)]_1 \ for \ u(X) \ s.t. \forall v^j\in \mathbb V,u(v^j)=\omega^i,for \ some \ \omega^i \in \mathbb H \Big \} $$

第二部分为证明存在某个多项式$H(X)$，满足$z_I(u(X))=z_{V_m}H(X)$

和之前一样，将向量$\vec c$编码为多项式$C(X)$，公共参考串为$srs$，查找向量记为$\vec a=(a_1,...,a_{m+1})$，其中前$m$个元素为需要查找的元素，$a_{m+1}$为一个随机域元素，用于实现向量$\vec a$的盲承诺，对$\vec a$的承诺记为$cm$

$$ cm=[\phi(x)]_1=\Big [ \sum^m_{j=1}a_j\mu_j(x)+a_{m+1}\cdot z_{V_m}(x) \Big ]_1 $$

证明的协议如图4所示

证明过程主要分为三个步骤

首先，Prover构造一个子集$I\sub [N]$，令该子集中任意的$j=1,...,m$，都有$a_j=c_i(i\in I)$，同时Prover构造一个向量$\vec c$的子向量$\vec c_I=(c_i)_{i\in I}$，构造关于该子向量的多项式$C_I(X)=\sum_{i\in I}c_i\tau_i(X)$，这么做的目的是从向量$\vec c$中将需要查找的元素隔离出来，从而降低协议处理过程中多项式的度

和之前提到的KZG承诺一样，利用各个多项式的承诺，下列等式可用于验证$C_I(X)$的元素是否都在$C(X)$中

$$ C(X)-C_I(X)=z_I(X)\cdot H_1(X) \tag 1 $$

注意到这个等式中多项式$C(X),H_1(X)$的度都是$N$，因此若向量$\vec c$中的元素更新时，协议需要花大量的开销来更新这两个多项式的承诺，但是如果对元素$c_i$的更新是一个已知的节，可以通过预计算$\tau_i$的揭示，从而在$O(N)$时间内完成更新

先暂时不考虑效率，现在的主要问题是如何隐藏$C_I(X),z_I(X)$，同时还要确保协议的合理性

Prvoer首先需要证明$z_I(X)$是集合$\mathbb H_I$上的消失多项式，也即需要以零知识的方式证明这个多项式具有正确的形式

本文的方案将证明过程分为两步，具体如下

第一步，Prover构造一个多项式$u(X)=\sum^m_{j=1}\omega^{i_j}\cdot \mu_j(X)$，度为$m-1$，多项式的系数为$\{\omega^{i-1}\}_{i\in I}$，并以零知识的方式证明其具有正确的形式

具体而言，需要证明对于所有的$v^j\in \mathbb V$，都有$(u(v^j))^N=1$（这个证明用到了5.2节中的协议，后续介绍）。这个证明可以确保$u(X)$中承诺的元素都来自于$\mathbb H$中

第二步，给出$u(X)$的承诺及其可以通过验证的证明串（记为$\prod_{unity'}$），证明$z_I(X)$具有正确的格式，从而证明$z_I(X)$满足关系$R_{unity}$

注意到多项式$u(X)$的系数为$\omega^{i_j}$，这些系数都来自集合$\{\omega^{i-1}\}_{i\in I}$中，而集合$\{\omega^{i-1}\}_{i\in I}$中的元素都是多项式$z_I(X)$的根，因此Prover可以向Verifier证明，存在一个多项式$H_2(X)$，满足下列等式

$$ z_I(u(X))=z_{V_m}(X)\cdot H_2(X) ]\tag 2 $$

注意到$C_I(X)$的承诺过程用到的拉氏基多项式是Verifier不知道的（$\{\tau_i(X)\}_{i\in I}$），因此论证的最后一步需要将$C_I(X)$与$[\phi(x)]_1$链接起来，因为计算$[\phi(x)]_1$用到的拉氏基多项式为$\{\mu_j(X)\}^m_{j=1}$，这些多项式是Verifier已知的，因此在这一步中，Prover需要证明存在一个多项式$H_3(X)$，满足下列等式

$$ C_I(u(X))-\phi(X)=z_{V_m}(X)\cdot H_3(X) \tag 3 $$

为了确保证明过程的零知识性，Verifier发送一个聚合挑战$\chi$，然后Prover将$H_2(X)$和$H_3(X)$聚合成一个承诺$[H_2]_1+\chi [H_3]_1$，从而可以同时验证式2和式3

注意到，为了确保式1成立，$C_I(X)$不能取$C(X)$的各个系数超过一次，另外，式3确保了$C_I(X),\phi(X)$的链接性，但是协议只能证明构造$\phi(X)$的系数与构造$C_I(X)$的系数相同，但是不能证明他们的顺序和各个元素出现的次数也相同，因为我们希望实现的查找需要满足对于某个向量$\vec a=(a_1,...,a_m)$，对于所有的$j=1,...,m$，都存在一个$i\in I$，满足$a_j=c_i$

协议就是上面的那个图4，与之相关的定理如下，协议的证明在原文的附录E

Thm 3：若图4是关于关系$R_{unity'}$的知识合理性论证，则在基于AGM的不可编程的随机预言机模型中，要么图4的协议满足两个向量承诺$C,cm$的链接性，要么存在一个可以攻破q-SDH假设的敌手

关于图4协议还有一个值得注意的点，该协议可以推出一个子查询表（sub-lookup table），大致意思就是说，对于某个$I\sub [N]$，Prover构造一个多项式$t(X)=\prod_{i\in I}(X-c_i)$，Prover可以证明该多项式具有正确的格式

由于图4协议Prover构造的多项式$C_I(X)$已被证明具有正确的格式，则意味着存在某个多项式$H_3(X)$，满足下列等式

$$ t(\tilde C_I(X))=z_{V_m}(X)\cdot H_3(X) $$

然后，对于任意度为$m-1$的多项式$a(X)$，若存在一个多项式$H_4(X)$，满足下列等式

$$ t(a(X))=z_{V_m}(X)\cdot H_4(X) $$

则$a(X)$的系数与$C_I(X)$的系数一致（不考虑顺序和重复问题）

5.2 Multi-Unity Proof of Proving well formation of $u(X)$

本节解决上一节的一个问题，也即以零知识的方式对$u(X)$进行承诺

$$ u(X)=\sum^m_{j=1}w^{i_j}\cdot \mu_j(X)+r(X)\cdot z_{V_m}(X) $$

其中$w^{i_j}$是$I$中的第$j$个元素，由于多项式的系数都是$\mathbb H$中的元素，因此他们都是$N$次单位根，也即令$w^{i_j}=u_j$，有$\forall j=1,...,m,u_j^N=1$

这一部分没看懂，可以去看看原文，先留个坑，填不填再说

References

$[1]$ Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, Mark Simkin:Caulk: Lookup Arguments in Sublinear Time. IACR Cryptol. ePrint Arch. 2022: 621 (2022)
‍