通用可更新CRS及其在zk-snark中的应用

1 Abstract

由于Prover只向Verifier发送单条消息的证明系统只能证明BPP类中的语言，为了证明更为复杂的语言，许多较新的NIZK证明系统都采用了CRS模型，但是此类模型中的CRS串都必须包含基于秘密随机掷币的结构，并且在生成CRS后丢弃该秘密值，这意味着此类NIZK系统需要一个固有的可信CRS生成步骤

目前zk-SNARK在Zcash和Ethereum中都有使用，对于这种去中心化的分布式执行环境而言，实际上几乎不可能找到一个可信方来执行上述这个可信步骤

Ben-Sasson等人$[BCG+15]$和Bowe等人$[BGG17]$研究了使用多方计算生成CRS的方法，但是要求所有的参与方要有至少一方是诚实的，且必须提前选定参与方，这意味着系统只能生成具有固定参与方的固定电路的CRS，此时问题就转为了参与方是谁及如何选择参与方的问题，尽管可以用MPC的方式生成CRS，但是CRS仍然作为zk-SNARK实际部署与使用的主要障碍之一

目前提出的一些方案中，要么证明大小会达到上百KB，要么验证时间与电路大小呈线性关系，较大的证明长度和较长的验证时间使得系统不适用于验证一些大型语句，相比之下，基于QAP的zk-SNARK可以做到亚常数的证明大小和十毫秒左右的验证时间，这一方案非常适用于空间和带宽高度受限的区块链环境，并且可以做到在关键过程中多次验证

因此，这篇paper提出并研究了一种新的NIZK证明设置的模型，称为可更新的CRS模型，其中任何参与方都可以在任何时候选择更新CRS，但是需要证明自己正确的完成了更新

只要本次更新的正确性验证通过，且上一个CRS和上一次更新是可信的，则更新后得到的新的CRS被视为可信的（有点类似于区块链的链式信任），此类模型还有一个特点，这个更新可能是由多个用户共同参与的，也即可能会在一个时间段内由不同的人生成一系列的更新，这时需要确保这一系列中的每个更新都是可信的，则得到的新的CRS才是可信的

paper提出的方案中CRS是由单项式构成的，因此本文还讨论了一下对于依赖于在CRS中嵌入非单项式（比如$G^{s^2+s}$）的任何基于配对的NIZK方案，不可能实现可更新的合理性（比如Pinocchio协议就不满足可更新的合理性）

可以将可更新的CRS和通用CRS模型做一个简单的对比：URS模型中，如果可以提供有效证明和URS，Verifier只需要确信URS是随机的即可（比如URS是来自Random Oracle中的Hash函数），而可更新的CRS中允许持怀疑态度的Verifier相信他们自己的更新的CRS的正确性证明，实际上这是一个比URS更弱的属性，因为它无法在更新之前将CRS用于生成证明，此外，可更新的CRS继承了CRS的效率和证明能力，但是消除了对可信设置的依赖，有利于用于不可信的分布式执行环境

2 Related Work

下表给出了基于配对的zk-SNARK的性能、CRS和证明大小之间的比较，同时还比较了Prover和Verifier需要的计算，重点比较了Groth的两个方案和具有代表性的基于QAP的zk-SNARK，以及本文可更新和可专门化的基于QAP的zk-SNARK

可以看到本文的方案在效率上与基于QAP的方案相当，但是通用参考串并不局限于证明预先指定的电路，对于基于QAP的SNARK，可以使用Valiant的通用电路结构$[Val76,LMS16]$来实现通用性，不过会引入$\log n$的乘法开销
此外本文还提出了一个开放问题：是否存在具有较短通用CRS的可更新zk-SNARK

3 Defining Updatable and Universal CRS Schemes

本节介绍一些符号，并重新讨论CRS模型中非交互式零知识证明的基本定义（该模型中CRS必须由可信的第三方生成）

然后再提出了可更新CRS方案的新定义，该方案通过允许敌手完全生成CRS本身，或者至少作为执行更新的一方参与其计算来弱化CRS模型，这一点与抗颠覆证明$[BFS16]$相关

3.1 Notation

• $|x|$：串$x$的长度
• $|S|$：有限集$S$的大小
• $x\larr S$：$S$中均匀选择一个元素并赋值给$x$
• $\lambda \in \mathbb N$：安全参数$\lambda$
• $PPT$：概率多项式时间
• $DPT$：确定性多项式时间（Deterministic Poly Time）
• $y\larr A(x;r)$：算法$A$，输入$x$，随机性为$r$，输出为$y$
• $y\larr A(x)$：省略随机性（或稍后解释随机性）

此外，在安全定义和证明中使用基于代码的游戏$[BR06]$，$Sec_{\mathcal A}(\lambda)$为关于安全定义$Sec$和敌手$\mathcal A$的主程序，其输出为安全游戏的输出，记输出1的概率为$Pr[Sec_{\mathcal A}(\lambda)]$

3.2 NIZK proofs in the CRS model

• $Setup(1^\lambda)$：初始设置算法，输入为$1^\lambda$，输出为公共参考串$crs$，该串满足某个分布$\mathcal D$
• $R$：具有三元组$(crs,\phi,w)$的多项式时间内可判定关系，$w$表示实例$\phi$在$crs$定义下的witness

CRS模型下的NIZK证明和论证包含三个算法$(Setup,Prove,Verify)$，满足完备性，零知识性和（知识）合理性

完美完备性指的是对于$crs\larr Setup(1^\lambda) ,(crs,\phi,w)\in R$，总有$Verify(crs,\phi,Prove(crs,\phi,w))=1$

合理性指的是任意敌手无法为一个不在关系内的实例生成合法的证明，进一步的，知识合理性表示如果任意Prover可以生成一个合法的证明，则存在一个抽取器$\chi$可以抽取该Prover的witness

零知识性表示存在一对模拟器算法$(SimSetup,SimProve)$（模拟器算法可以访问模拟陷门，但是不知道witness），对于诚实的CRS和证明或模拟的CRS和证明，敌手无法区分诚实的情况和模拟的情况

3.3 Updating common reference strings

本文弱化了CRS模型，允许对手完全生成CRS，或者至少作为执行更新的一方参与CRS的计算

说的粗糙一点就是，可以认为允许敌手与Setup算法交互

正式的说就是，定义一个可更新的CRS方案，该方案由PPT算法$Setup,Update$和DPT算法$VerifyCRS$组成，具体如下

• $(crs,\rho)\larr Setup(1^\lambda)$：输入安全参数$\lambda$，输出一个公共参考串$crs$和正确性证明$\rho$
• $(crs',\rho')\larr Update(1^\lambda,crs,(\rho_i)^n_{i=1})$：输入为安全参数$\lambda$，公共参考串$crs$和CRS的更新证明列表$(\rho_i)^n_{i=1}$，输出一个更新后的CRS串$crs'$和更新证明$\rho'$
• $b\larr VerifyCRS(1^\lambda,crs,(\rho_i)^n_{i=1})$：输入为安全参数$\lambda$，公共参考串$crs$和CRS的更新证明列表$(\rho_i)^n_{i=1}$，输出为单比特$b$，$b=1$表示接受，否则表示拒绝

• Definition 1：若满足下列条件，则称可更新CRS模型为完美正确的

  • 对于所有的$(crs,\rho)\larr Setup(1^\lambda)$，都有$VerifyCRS(1^\lambda,crs,\rho)=1$
  • 对于所有的$(1^\lambda,crs,(\rho_i)^n_{i=1})$，满足$VerifyCRS(1^\lambda,crs,(\rho_i)^n_{i=1})=1$，都有$(crs',\rho_{n+1})\larr Update(1^\lambda,crs,(\rho_i)^n_{i=1})$，满足$VerifyCRS(1^\lambda,crs,(\rho_i)^{n+1}_{i=1})=1$

标准可信设置是$\rho=\epsilon$的可更新Setup的特例（也即更新的正确性证明为空串），其中验证算法接受任何内容，对于抗颠覆Setup（subversion-resistant setup），证明串$\rho$可被视为CRS中包含的额外元素，且仅用于确保CRS可验证

3.4 Security properties

本小节回顾零知识、合理性和与NIZK证明系统相关的知识合理性的概念

此外，除了考虑具有可信引用字符串的标准设置外，还需要考虑抗颠覆设置，其中由对手生成CRS，并引入了新的可更新CRS设置

对于每个安全属性，图1左列中的游戏类似于零知识、合理性和知识合理性的常见安全游戏，不同之处在于CRS串初始会被置为$\perp$

然后本文将生成CRS的过程建模为敌手和Oracle $\mathcal O_s$之间的交互，并在交互结束时$\mathcal O_s$会设置CRS的值并返回给敌手

原则上，创建CRS的过程可以是可信的，甚至可以是更通用的MPC协议，不过我们主要关注下列三种类型的设置：

1. 可信设置（T）：其中setup生成器在生成CRS时会忽略敌手
2. 可颠覆设置（S）：setup生成器会从敌手那里获取CRS并检查格式，若正确后则使用该CRS
3. 可更新设置（U）：一种介于两者之间的设置，敌手可以自适应的生成CRS序列，并可以任意在其中更新自己恶意行为，唯一的限制条件是要求最终得到的CRS串必须具有正确的格式，且至少有一个诚实的参与方为CRS的更新做出贡献

在零知识的定义中，要求存在一个PPT模拟器，该模拟器由相互共享状态的算法$(SimSetup,SimUpdate,SimProve)$组成，模拟器主要是用于模拟CRS的生成，且需要在不知道对应witness下模拟交互脚本

• Definition 2：令$P=(Setup,Update,VerifyCRS,Prove,Verify)$为一关于关系$R$的非交互式论证，若对于$X\in \{T,U,S\}$，该论证满足下列条件，则称该论证为$X$-安全的

  • $P$满足完备性：对于任意PPT算法$\mathcal A$，其优势$|\ 1-Pr[COMP_{\mathcal A}(\lambda)]\ |=negl$
  • $P$满足$X$-零知识性：对于任意PPT算法$\mathcal A$，存在一个模拟器$Sim_{\mathcal A }=(SimSetup,SimUpdate,SimProver_{\mathcal A})$，算法$\mathcal A$的优势$|\ 2Pr[X-ZK_{\mathcal A,Sim_{\mathcal A}}(1^\lambda)=1] -1\ |=negl$
  • $P$满足$X$-合理性：对于任意PPT算法$\mathcal A$，使得概率$Pr[X-SND_{\mathcal A}(1^\lambda)=1]=negl$
  • $P$满足$X$-知识合理性：对于任意PPT算法$\mathcal A$，存在PPT抽取器$\chi_{\mathcal A}$，使得概率$|\ Pr[X-KSND_{\mathcal A,\chi_{\mathcal A}}(1^\lambda)] \ |=negl$

定义简单来说就是对于关注的三种类型的设置来定义零知识性、合理性与知识合理性（完备性显然不需要区分），此外上述性质区分计算性（Computational）、统计性（Statistically）和完美性（Perfectly）

该模型的主要优点之一是它的灵活性，例如可以定义一个稍微较弱但仍然可信的设置，允许敌手选择一些参数（比如算术电路或特定有限域中门的数量），然后在这些参数上运行设置，除了不同类型的设置假设外，还可以再模型中纳入其他安全概念（比如模拟合理性）

就这些概念的关联而言，可更新安全性意味着可信安全性，而抗颠覆安全性则意味着可更新安全

• Lemma 1：满足具有可更新设置的安全概念的证明系统也满足具有可信设置的安全概念
• Lemma 2：满足具有可颠覆设置的安全概念的证明系统，也满足具有可更新设置的安全概念

证明可以看原文$[1]$

3.5 Specializing common reference strings

接下来看一种特殊的CRS，称为专用CRS

考虑一个通用关系的CRS，它可以用来证明任何算术电路都是可满足的，关系实例可自由指定电路的导线和输入

对于特定的算术电路，需要使用较大的CRS来推导具有固定导线但灵活输入的关系的较小的电路特定CRS，因为这可能会得到更高效的Prover和Verifier算法（这个过程可以视为对大型CRS进行预计算的一种形式，从而获得更好的效率）

接下来正式提出专用CRS的想法

令$\Phi$为一DPT可决定关系集，其中的关系记为$R_\Phi$（该关系是DPT可决定的），$\Phi$的通用关系$R$定义了一种语言，其中实例$\phi=(R_\Phi,u)$，满足当且仅当$R_\Phi\in \Phi$且$(u,w)\in R_\Phi$时，有$((R_\Phi,u),w)\in R$

若存在DPT算法$crs_{R_\Phi}\larr Derive^*(crs,R_\phi)$和算法$Prover,Verify$可以根据算法$\pi\larr Prove^*(crs_{R_\phi},u,w),b\larr Verify^*(crs_{R_\phi},u,\pi)$定义如下，则称该设置生成一个关于关系$R$的特殊通用参考串$crs$

• $Prove(crs,\phi,w)$：算法解析$\phi=(R_\Phi,u)$且断言$R_\phi\in \Phi$，并导出$crs_{R_\phi}\larr Derive^*(crs,R_\phi)$，返回由$Prove^*(crs_{R_\phi},u,w)$生成的证明
• $Verify(crs,\phi,w)$：算法杰西$\phi=(R_\Phi,u)$并检查$R_\phi\in \Phi$，并导出$crs_{R_\phi}\larr Derive^*(crs,R_\phi)$，返回由$Verify^*(crs_{R_\phi},u,\pi)$

用于布尔和算术电路验证的现有zk-SNARK具有不同程度的通用性，$[Gro10b]$是通用的，适用于任何布尔电路，而后续的SNARK（如$[GGPR13]$及其后代）的CRS适用于固定布线的电路

专用CRS的方案旨在实现前者的通用性和后者的性能，由于算法$Derive$仅对公共信息进行操作，因此协议参与者可以在必要时执行该算法，这么做有两个优点

1. 可以将针对使用专用CRS的Prover和Verifier的任何攻击转化为对通用CRS的攻击，因此无需定义任何特殊的安全概念
2. 可以更容易地设计高效的可更新方案，因为此类方案所更新的CRS不依赖于特定的关系（与关系独立），并在更新后公开导出有效的特定于电路的CRS，本文的下半部分对此进行研究

原文的第六节提出了一个可更新的zkSNARK，并使用一个对所有QAP通用的CRS，并对其改进以获得线性阶大小的CRS和线性阶运行时间的Prover

4 Background

令$\mathcal G(1^\lambda)$为DPT双线性群生成器，给定安全参数，输出双线性群参数$bp=(p,\mathbb G_1,\mathbb G_2,\mathbb G_T,e,G,H)$，其中$\mathbb G_1,\mathbb G_2$的阶为$p$，$G\in\mathbb G_1,H\in\mathbb G_2$，映射$e:\mathbb G_1\times \mathbb G_2\rarr \mathbb G_T$满足非退化性

4.1 Knowledge and computational assumptions

Damgard$[Dam91]$引入的指数假设知识（KEA），Bellare和Palacio$[BP04]$将其扩展到了KEA3假设，即给定$G,G^\alpha,G^s,G^{\alpha s}$，在不知道$c_0,c_1$的情况下计算$C,C^\alpha$，使其满足$C=G^{c_0+c_1s}$是不可行的

Abdolmaleki等人$[ABLZ17]$称之为BDH-KE假设的指数假设（B-KEA）的双线性知识进一步推广到非对称群，也即在不知道$s$的情况下，无法计算$C,\hat C$，满足$e(C,\hat G)=e(G,\hat C)$，其中$(C,\hat C)=(G^s,\hat G^s)$，该假设对应于Groth$[Gro10b]$引入的非对称双线性群中的q-PKE假设中$q=0$的特例

本文引入$q$-单项式知识假设（q-monomial knowledge assumption），作为q-PKE对多变量单项式的推广，相关定义如下

• Assumption 1（The $q(\lambda)$-Monomial Knowledge Assumption，$q(\lambda)$-MK）：令$\boldsymbol a=\{a_i(X)\}_{i=1}^{n_a},\boldsymbol b=\{b_i(X)\}_{i=1}^{n_b}$为两个$n$元单项式集，度$n_a,n_b$和变量数$n$的界均为$q(\lambda)$，令$\mathcal A$为敌手，$\chi_{\mathcal A}$为一抽取器，定义优势如下

$$ Adv^{MK}_{\mathcal G,q(\lambda),\boldsymbol a,\boldsymbol b,\mathcal A,\chi_{\mathcal A}}(\lambda)=Pr[MK_{\mathcal G,q(\lambda),\boldsymbol a,\boldsymbol b,\mathcal A,\chi_{\mathcal A}}(\lambda)] $$

其中$MK_{\mathcal G,q(\lambda),\boldsymbol a,\boldsymbol b,\mathcal A,\chi_{\mathcal A}}(\lambda)$如下

如果对于所有PPT敌手$\mathcal A$存在PPT抽取器$\chi_{\mathcal A}$，使得该优势关于$\lambda$可忽略，则称MK假设相对于$\mathcal G$成立

（这个假设没看懂）

下面还有一个假设，多变量计算假设与Ghadafi和Groth$[GG17]$的单变量q-双线性间隙假设密切相关

• Assumption 2（The $q(\lambda)$-Monomial Computational Assumption，$q(\lambda)$-MC）：令$\boldsymbol a=\{a_i(X)\}_{i=1}^{n_a},\boldsymbol b=\{b_i(X)\}_{i=1}^{n_b}$为两个$n$元单项式集，度$n_a,n_b$和变量数$n$的界均为$q(\lambda)$，令$\mathcal A$为PPT算法，定义优势如下

$$ Adv^{MC}_{\mathcal G,q(\lambda),\boldsymbol a,\boldsymbol b,\mathcal A,\chi_{\mathcal A}}(\lambda)=Pr[MC_{\mathcal G,q(\lambda),\boldsymbol a,\boldsymbol b,\mathcal A,\chi_{\mathcal A}}(\lambda)] $$

其中$MC_{\mathcal G,q(\lambda),\boldsymbol a,\boldsymbol b,\mathcal A,\chi_{\mathcal A}}(\lambda)$如下

若对于所有PPT敌手$\mathcal A$，都有该优势关于$\lambda$可忽略，则称MC假设相对于$\mathcal G$成立

这个假设个人理解应该是：PPT敌手$\mathcal A$在知道两个$n$元单项式$\{G\},\{H\}$的情况下，只能计算出$A=G^{a(\boldsymbol x)}$，其中$a(\boldsymbol x)$是$\{a_i(X)\}$的线性组合

4.2 A QAP-based zk-SNARK recipe

本节简单描述QAP构造算术电路可满足性SNARK方案的通用方法（QSP也可以采用类似的方法），这两种情况可以通过确保所有承诺都是随机的来实现协议的零知识性

原文的第六节展示了该方法不太可能直接得到可更新的zkSNARK，不过通过稍微修改第五节中的方法可以构建可更新的zkSNARK

Arithmetic Circuits

算术电路可用于描述仅由域上加法和乘法组成的计算，现考虑域$\mathbb F$上的算术电路，电路具有$n$个乘法门和$m$根导线，门指定一个操作（加法或乘法，分别对应加法门和乘法门），导线为域$\mathbb F$上的值，每个门都有一条左输入导线和一条右输入导线，以及一条输出导线，该电路可以具有拆分（spilt）的导线（拆分的意思是将同一导线输入多个门），如果对于每个门而言，作用到输入线的操作等于输出线，则称该电路是可满足

任何NP关系都可以用一系列算术电路来描述（包括一系列的statement与witness对），在算术电路描述的关系中，实例由$l$根固定输入线的赋值定义，witness是剩余$m-l$根满足算数电路的导线

Fix the circuit

用不同的$n$个值$r_1,...r_n\in \mathbb F$标记每个门，并将算术电路转换为多项式上的方程，这些值用于在表示电路的多项式中求值

将所有的$m$根导线用三个度至多为$n-1$的多项式表示，这些多项式分别确定了每条线作为左输入线、右输入线和输出线的门，还可以用于确定导线是否拆分，用于确定导线输入乘法门之前是否有加法，三个多项式分别为

$$ \begin{aligned} U&=\{u_i(X)\}^m_{i=0}\\ V&=\{v_i(X)\}^m_{i=0}\\ W&=\{w_i(X)\}^m_{i=0}\end{aligned} $$

其中$U$表示门的左输入导线，$V$表示右输入导线，$W$表示输出导线，且有$u_0(X)=v_0(X)=w_0(X)=1$，采用多项式的原因是可以通过某些赋值手段来使得它们在所有对应的乘法门的处取值为1，并且在所有非对应的乘法门处取值为0

为了处理电路中可能出现的各种情况，下面分析一下如何构造CRS来处理对应的情况

Commit to wire values

假设$m$根导线为$(a_1,...,a_m)$，其中witness为导线$\{l+1,...,m\}$，CRS中包含$\{G^{u_i(x)},G^{v_i(x)},G^{w_i(x)}\}^m_{i=l+1}$，其中$x$为一个随机选择的值

左输入、右输入及输出导线的承诺值如下

$$ \begin{aligned} C_L&=G^{\sum^m_{i=l+1}a_iu_i(x)}\\ C_R&=G^{\sum^m_{i=l+1}a_iv_i(x)}\\ C_O&=G^{\sum^m_{i=l+1}a_iw_i(x)}\\ \end{aligned} $$

Prove that repeated wires are consistent

如果一根导线被分成两个左输入（或右输入），由于输入会被转换为多项式，根据多项式的特性，不需要其他额外的操作来检查一致性

不过对于导线拆分为至少一条左输入线和至少一条右输入线的情况，必须检查拆分的线是否一致，此时需要在CRS中包含下列项

$$ \{G^{\alpha_uu_i(x)+\alpha_vv_i(x)}\}^m_{i=l+1} $$

其中$\alpha_u,\alpha_v$未知，且要求Prover提供证明元素$Y$，满足$Y=a_uC_L+\alpha_vC_R$（比如证明$\alpha_0=\alpha_1$）

Prove that output wires are consistent with input wires

电路需要证明输出线与输入线一致，这个步骤可以与证明重复导线的一致性一起完成，实现的方式也很简单，在CRS中包含下列项即可

完成的方式也很简单，在CRS中包含下列项即可

$$ \{G^{\alpha_uu_i(x)+\alpha_vv_i(x)+\alpha_ww_i(x)}\}^m_{i=l+1} $$

其中$\alpha_u,\alpha_v,\alpha_w$未知，要求Prover提供证明元素$Y$，满足$Y=a_uC_L+\alpha_vC_R+\alpha_wC_O$

Prove the commitments are well formed

公共引用字符串中有一些值不应包含在证明程序生成的承诺中，例如与实例相关的$\{a_iu_i(x)\}^l_{i=1}$，这可以使用与上述一致性证明相同的方法进行检查

Prove that gates are evaluated correctly

过确定一个二次多项式方程来检查门的求值是否正确，此时有一个唯一的度为$n$的目标多项式$t(X)$，在所有的门$(r_1,...,r_n)$处的取值均为零

也即，对于$m$根导线为$(a_1,...,a_m)$，当且仅当乘法门被正确计算时，在所有的门$(r_1,...,r_n)$均有下列计算成立

$$ \Big ( \sum^m_{i=0}a_iu_i(X) \Big)\cdot \Big ( \sum^m_{i=0}a_iv_i(X) \Big)- \sum^m_{i=0}a_iw_i(X) =0 $$

该多项式与多项式$t(X)$一样，在$(r_1,...,r_n)$处均为$0$，也即$t(X)$可以整除上述多项式

因此需要Prover在一个未知点$x$处证明下式成立

$$ \Big( G^{\sum^l_{i=0}a_iu_i(x)}C_L \Big) \otimes \Big( G^{\sum^l_{i=0}a_iv_i(x)}C_R \Big)= G^{t(x)+\sum^l_{i=0}a_iw_i(x)}C_O $$

$\otimes$表示哈达玛积

5 An Updatable QAP-Based zk-SNARK

本节给出了一个基于可更新QAP的zk-SNARK的构造，该构造中利用了URS，此外本节还证明了在第四节中介绍的指数假设知识下，方案满足subversion零知识和可更新知识可靠性，接下来看一下如何构造

和之前第三节提到的一样，有四个参数$(d,m,l,bp)$（均由安全参数$1^\lambda$决定），其中$bp=(p,\mathbb G_1,\mathbb G_2,\mathbb G_T,e,G,H)$，$\mathbb G_1,\mathbb G_2,\mathbb G_T$的阶为$p$，$G\in\mathbb G_1,H\in\mathbb G_2$，映射$e:\mathbb G_1\times \mathbb G_2\rarr \mathbb G_T$满足非退化性，$d$表示QAP的度，$m$表示输入变量个数，$l$表示QAP的公共域元素构成的实例的一部分

4.2节中提到了QAP的定义为三个度小于$d$的多项式$\{u_i(x),v_i(x),w_i(x)\}^m_{i=0}$以及一个度为$d$的目标多项式$t(x)$

回顾一下QAP，QAP定义了一个关系$R_{QAP}$，包含一对实例$(a_1,...,a_l)$和witness$(a_{l+1},...,a_m)$，$a_0=1$，实例和witness满足下式

$$ \Big( u_0(x)+\sum^m_{i=1} a_iu_i(x) \Big)\cdot \Big( v_0(x)+\sum^m_{i=1} a_iv_i(x) \Big)\equiv w_0(x) +\sum^m_{i=1}a_iw_i(x) \ mod \ t(x) $$

由安全参数索引的参数序列定义了一个通用关系$R$，包含所有上述描述的QAP实例及其对应的witness

采用3.5节中的表示方法，令$\Phi$表示参数所有可能的QAP，则$\Phi$的通用关系$R$包含实例$\phi=(R_{QAP},u=(a_1,...,a_l))$及其对应的witness $w=(a_{l+1},...,a_m)$

5.1 Reworking the QAP recipe

最终方案在图2和图3中正式给出，本节中介绍一下方案的一些技术思想

原文的第六节中给出了一些不可能的结果，因此基于QAP的方法中许多常见技巧并不适用于本方案，这意味着方案需要引入一些新的东西，这里有一个idea，将原来的单变量方案切换到多变量方案，其中证明元素需要满足由不定元$X,Y,Z$确定的方程，然后可以使用所选witness QAP多项式和的子空间论证来证明证明元素具有正确的格式，一旦证明了证明元素具有正确的格式，则表明证明了其中两个元素的指数相乘可以获得第三个证明元素中的指数，也即下面两点：

1. 所有项的和等于（$Y$给出了幂$j$）$X$中未确定的QAP表达式
2. 值$Y^j$未在CRS中给出

本文的最终方案采用$j=7$（原因后续会介绍）

Fix the circuit

电路仅需要在运行CRS推导算法时固定，此时，电路表示为第4节中描述的QAP，例如对于$a_0=1$，域元素$(a_1,...,a_m)\in R_{QAP}$，当且仅当对于度为$d-2$的多项式$q(X)$，有下式成立

$$ \Big ( \sum^m_{i=0}a_iu_i(X) \Big )\cdot \Big ( \sum^m_{i=0}a_iv_i(X) \Big )= \sum^m_{i=0}a_iw_i(X) +q(X)t(X) $$

Prove the commitments are well formed

为了实现可更新的CRS，诚实Prover需要输出群元素$(A,B,C)$，其中$A,B$具体如下

$$ \log(A)=\log(B)=q(x)y+\sum^m_{i=0}a_i(w_i(x)y^2+u_i(x)y^3+v_i(x)y^4)-y^5-t(x)y^6 $$

确保$\log(A)=\log(B)$可以通过验证配对方程$e(A,H)=e(G,B)$实现，因此我们只需要证明$A$具有正确的格式即可

如第四节所述，通过仅编码CRS中的某些多项式并强制计算使用CRS中元素的线性组合来完成的，由于不能这样做且需要实现更新，因此需要构造了一个新的子空间参数

首先，我们使用Verifier计算的群元素$S$减去实例中的已知元素，以获得具有新的指数的群元素，新的指数如下

$$ q(x)y+\sum^m_{i=l+1}q_i(w_i(x)y^2+u_i(x)y^3+v_i(x)y^4) $$

然后令$M$为$(m+d-l)\times 4d$的矩阵，包含关于单项式$\{x^iy^j\}^{(d-1,4)}_{(i,j)=(0,1)}$中关于$\{(w_i(x)y^2+u_i(x)y^3+v_i(x)y^4)\}^m_{i=l+1}$和$\{x^iy\}^{d-1}_{i=0}$的系数，并将这些系数记为$m_l(x,y)=\sum_{i,j}M_{l,(i,j)}\cdot x^iy^j$（比如$m_1(x,y)=w_{l+1}(x)y^2+u_{l+1}(x)y^3+v_{l+1}(x)y^4$），此外记对应的零矩阵为$N$，也即$MN=0$

我们通过$M$中相应的单项次来处理$N$的行，该矩阵的列定义为多项式$n_k(x,y)=\sum_{i,j}N_{(i,j),k}\cdot x^{d-i}y^{4-j}$，这么做会使得在$m_l(x,y)\cdot n_k(x,y)$时消去度为$(d,4)$的项

如果此时引入变量$z$，并令$\hat N=H^{\sum_kn_k(x,y)z^k}$，则当从正确的子空间中选择$A$时，配对$e(AS,\hat N)$得到的目标群中所有$x^dy^4z^k$的项的系数均为0的元素，从而给定不包含$x^dy^4z^k$（$k>1$）的项的CRS，验证等式可以检查$(\log A+\log S)\cdot \log \hat N=\log C_1$，此时只需要$A$具有正确的格式，Prover只需要计算$C_1$即可

Prove that the QAP is satisfied

假设$A,B$格式均正确，此时有

$$ \log A \cdot \log B=\Big( q(x)y+\sum^m_{i=0} a_i(w_i(x)y^2+u_i(x)y^3+v_i(x)y^4)-y^5-t(x)y^6 \Big)^2 $$

重点观察乘积中包含$y^7$的项，分别来自于$-q(x)y\cdot t(x)y^7$、$u_i(x)v_i(x)y^7$和$-w_i(x)y^7$，因此将$y^7$提出来，可以得到下列式子

$$ -t(x)q(x)-\sum^m_{i=0}a_iw_i(x)+\Big( \sum^m_{i=0}a_iu_i(X) \Big)\cdot \Big( \sum^m_{i=0}a_iv_i(X) \Big) $$

（这里原文在$-t(x)q(x)$这一项项给出的是正号，个人认为原文写错了，因为根据前面的验证等式这一项应该是负号，也即和$w_i(x)$的项同号）

$y$的其他幂次项会在其他证明组件中被抵消

对于特定的多项式$q(X)$，当且仅当QAP满足时才有上述方程成立，因此给定不包含$y^7$的项的CRS和验证方程$\log A\cdot \log B=\log C_2$，确保当且仅当QAP满足时，证明元素$C_2$是可计算的

Derivation of a Linear Common Reference String

不难发现，上述技术要求CRS具有二次单项式集，以便计算零矩阵，这里可以通过提供一个不可信的派生函数来解决这个问题，该函数可以看作是一种预计算形式，以便找到固定关系的线性公共引用字符串，使用线性CRS，可以使得Prover进行群幂运算的数量与电路大小呈线性关系

5.2 Updatability of the universal common reference string

本节描述通用CRS以及如何更新它，然后证明了对于通过设置或更新计算有效CRS的任何敌手都可以提取其使用的随机性

5.3节中展示了本方案中，证明对新生成的CRS进行一次更新的敌手的安全性等同于证明可更新安全性的完整版本（完整版本中的敌手只进行了一次更新）

通用CRS包含元素$G$的指数$\{x^iy^jz^k\}_{(i,j,k)\in S_1}$和元素$H$的指数$\{x^iy^jz^k\}_{(i,j,k)\in S_2}$，其中$S_1,S_2$如下

然后具体的更新流程如下

这里简单分析一下三个算法，也是本篇论文的核心所在

• $Setup$：也即协议第一次运行时生成的CRS，$x,y,z$为域$\mathbb F^*_p$上随机选择的三个数，然后生成一个证明串$\rho$，用于证明CRS是正确生成的，这个证明中$(G^x,G^y,G^z)$出现了两次，这个不是写错了，之后两个算法$Update$和$VerifyCRS$都会用到这个，然后利用$x,y,z$计算CRS中对应的群元素
• $Update$：先将CRS解析为正确的格式，然后选择域$\mathbb F^*_p$上三个新的随机数$\alpha,\beta,\gamma$，生成新的CRS，然后生成新的证明串$\rho$

注意这里$G$有一个下标，因为的指数由$x^iy^jz^k$组成，因此$G_{1,0,0}$表示$G$的指数中$x$的幂为1，$y,z$均为0

然后$Update$算法不仅需要根据上一个$G_{1,0,0}$和$\alpha$计算出$G^\alpha_{1,0,0}$，还需要单独计算一个$G^\alpha$用于在后续的配对中验证，因此$Setup$算法中的$(G^x,G^y,G^z)$出现了两次，这也解释了为什么$Setup$算法证明串$\rho$中$(G^x,G^y,G^z)$出现了两次的原因，不过$Setup$的这两组元素不需要用配对，只需要简单验证他们相等即可，下面的VerifiyCRS也可以看到

• $VerifyCRS$：首先是解析CRS串和从初始证明串$\rho_1$到目前最新的证明串$\rho_n$，接下来完成对应的演算即可

注意到对于$i=1$的情况，因为$Setup$的证明串$\rho$没有经过更新，$(G^x,G^y,G^z)$出现了两次，因此只需要验证$A_1=\bar A_i，B_1=\bar B_i，C_1=\bar C_i$即可，无需使用配对

然后接下来是利用配对验证$2\leq i\leq n$中的每一个证明串$\rho_i$，$e(A_i,H)=e(A_{i-1},\hat A_i)$是确保新的$A_i$的指数正确，$B_i,C_i$同理，$e(\bar A_n,H)=e(G,\hat A_n)$是确保最新的证明串$\rho_n$中的$\bar A_n,\hat A_n$都是由$\alpha$计算来的，$B,C$及其对应的$\beta,\gamma$同理

然后还需要验证$A_n\neq 1$，确保更新后该元素不会变为单位元，要不然后续的更新都是对单位元进行幂运算，任何指数都无法更新单位元，$B_n,C_n$同理

最后就是验证指数分别为$y^j,x^iy^j,x^iy^jz^k$的项正确计算

当上述验证均通过时，意味着CRS被正确更新了

可以看到整个Setup和Update都很简短，但是注意到VerifyCRS中用了大量的配对来验证整个CRS的完备性，因此更新很简单，但是验证是一个开销极大的过程

不过注意到这个CRS是通用CRS，而不是最终用于电路证明的CRS，因此验证的开销稍大一些可以理解

还有一点不太理解，因为前面提到了，只需要CRS的证明串验证正确就意味着当前CRS可用于生成证明，因此按理来说对证明串的验证应当是递归正确的，这里没有理解原文为什么要对$2\leq i\leq n$进行验证

然后这里有一个引理

• Lemma 3（Correctness of the CRS genereation）：上述方案在下列意义上是完全正确的

$$ \begin{aligned} &Pr[(crs,\rho)\larr Setup(1^\lambda):VerifyCRS(1^\lambda,crs,\rho)=1]=1\\ &Pr[(crs',\rho_{n+1})\larr Update(1^\lambda,crs,\{\rho_i\}^n_{i=1}:VerifyCRS(1^\lambda,crs,\{\rho_i\}^n_{i=1}=1\wedge VerifyCRS(1^\lambda,crs',\{\rho_i\}^{n+1}_{i=1})\neq 1]=1 \end{aligned} $$

接下来还有两个相关引理，用来证明构造的完美安全性和每个组件的更新安全性，这些引理确保了即便是不诚实的更新行为，也需要知道它们对模拟陷门的贡献

• Lemma 4（Trapdoor extraction for subvertible CRSs）：假设存在一个PPT敌手$\mathcal A$，其输出$(crs,\rho)$，满足$VerifyCRS(1^\lambda,crs,\rho)=1$的概率不可忽略，则根据0-MK假设（等价于B-KEA假设），存在一个PPT抽取器$\chi$，给定$\mathcal A$的随机纸带作为输入，输出$(x,y,z)$，满足$(crs,\rho)=Setup(1^\lambda;(x,y,z))$

证明可以看原文$[1]$，Lemma 4证明了即使将真实生成的CRS作为输入，更新程序也需要知道它们对陷门的贡献

• Lemma 5 (Trapdoor extraction for updatable CRSs)：假设存在一个PPT敌手$\mathcal A$，给定$(crs,\rho)\larr Setup(1^\lambda)$，$\mathcal A$请求$(final,crs',\{\rho_1,\rho_2\})$上的U-$\mathcal O_s$，满足$VerifyCRS(R,crs',\{\rho_1,\rho_2\})=1$成立的概率不可忽略，则对于$\boldsymbol a=\{X^iY^jZ^k:(i,j,k)\in S_1\},\boldsymbol b=\{X^iY^jZ^k:(i,j,k)\in S_s\}$，q-MK和q-MC假设意味着存在一个PPT抽取器$\chi$，给定$\mathcal A$的随机性作为输入，输出$(\alpha,\beta,\gamma)$，满足$\bar A_2=G^\alpha,\bar B_2=G^\beta,\bar C_2=G^\gamma$

证明可以看原文$[1]$

5.3 Single adversarial updates imply updatable securityThe following lemma relates updatable security to a model in which

现在引入一个新的模型，在该模型中，敌手在诚实的设置之后只能进行一次更新，在这个模型中证明本文提出的方案的安全性要清晰得多（和Lemma 4证明的一样，但是同时又确保了可更新安全性的一般性）

从Lemma 4中我们已经知道，当敌手生成CRS时，可以提取敌手对陷门的贡献，根据Lemma 5，可以在敌手更新诚实的CRS时提取，为了将诚实更新链折叠成诚实设置，本文的方案中，设置和更新对陷门的贡献是便捷的

这里还有一个点，对陷门的贡献不仅可以折叠，还可以合并，这意味着对于陷门$\tau,\tau',\tau''$，有

$$ Update'(1^\lambda,Update'(1^\lambda,Setup'(1^\lambda;\tau);\tau');\tau'')=Setup'(1^\lambda;\tau\otimes \tau'\otimes\tau'')=Update'(1^\lambda,Update'(1^\lambda,Setup'(1^\lambda;\tau'');r');r) $$

此外，在本文的构造中，证明$\rho$仅取决于更新算法的关系和随机性，也即独立于正在更新的引用字符串，这使得我们可以进行以下模拟：给定$crs$的陷门$\widetilde \tau=(x,y,z)$和$crs'$元素$(G_{1,0,0},G_{0,1,0},G_{0,0,1},H_{1,0,0},H_{0,1,0},H_{0,0,1})$，可以模拟$crs'$的证明$\rho_2=(A_2,B_2,C_1,\bar A_2,\bar B_2,\bar C_2,\hat A_2,\hat B_2,\hat C_2)$为$crs$的更新，也即

$$ \begin{aligned} &A_2\larr G_{1,0,0}\\ &B_2\larr G_{0,1,0}\\ &C_2\larr G_{0,0,1}\\ &\bar A_2\larr G^{x^{-1}}_{1,0,0}\\ &\bar B_2\larr G^{x^{-1}}_{0,1,0}\\ &\bar C_2\larr G^{x^{-1}}_{0,0,1}\\ &\hat A_2\larr H^{x^{-1}}_{1,0,0}\\ &\hat B_2\larr H^{x^{-1}}_{0,1,0}\\ &\hat C_2\larr H^{x^{-1}}_{0,0,1}\\ \end{aligned} $$

本文在归约中称之为$\rho(crs')^{\tau^{-1}}$

在这里给出了知识可靠性的相关引理，详细证明可以看原文（全文最复杂的概念），此外，由于知识的可靠性意味着可靠性，这里直接证明了知识的零知识颠覆性（这也是文章中唯一需要的概念）

• Lemma 6（Single adversarial updates imply full updateable knowledge soundness）：若构造对于能够查询$(Setup,\oslash)$仅一次，之后请求$(final,S)$，其中集合$S$满足$|S|\leq 2$，则在引理4和引理5的假设下，该构造为U-KSND安全的

5.4 The zk-SNARK Scheme

本节利用5.2节中的URS构建一个基于QAP的可满足性zk-SNARK

首先需要从URS导出基于QAP的特定CRS，然后再使用该CRS构建有效的证明和验证算法

这里有三个算法，具体如下图

• $Derive$：输入为$crs$（也就是上面那个通用CRS）以及需要证明的QAP，$Derive$算法将QAP解析为对应的多项式，然后这里需要检查一下$G^{y-t(x)y^2}\neq 1$，因为$y-t(x)y^2$这一项需要和随机性$r$相乘，如果$G{y-t(x)y2}=1$，则$G^{r(y-t(x)y^2)}=1^r=1$，相当于没有了随机性，无法得到与真实执行相同的分布，也就无法确保方案的零知识性（这一点具体可以看原文Theorem 3和Theorem 4的证明）

接下来对于$i\in\{0,...,m\}$，令$s_i(X,Y)=w_i(X)Y^2+u_i(X)Y^3+v_i(X)Y^4$，对于$j=1,2,3$，令$s_{m+j}(X,Y)=t(X)Y^{j+1}$，然后计算$3d-m+l$个多项式$n_1(X,Y),...,n_{3d-m+l}(X,Y)$，使得对于所有的$i\in\{l+1,...,m+3\},k\in\{1,...,3d-m+l\}$，都有乘积$s_i(X,Y)\cdot n_k(X,Y)$中$X^dY^4$的项的系数为0，同时对于$p(X,Y)\cdot Y^2\notin\{s_i(X,Y)\}^{m+3}_{i=l+1}$，存在$k\in\{1,...,3d-m+l\}$，使得$p(X,Y)\cdot Y^2\cdot n_k(X,Y)$中$X^dY^4$的项的系数不为0（这里$p(X,Y)$是某一关于$X,Y$的多项式）

然后令$n(X,Y,Z)=Z^{6d}+\sum^{3d-m+l}_{k=1}n_k(X,Y)Z^k$，最终得到上图中的$crs_{QAP}$

• $Prove$：$Prove$算法首先需要检查$H^{y^5}\neq H^{t(x)y^6}$（这一步的目的不清楚，如果相等的话相当于$t(x)=y$，但是好像没什么用），然后解析$u,w$，计算$q(X)$，选择随机性$r\larr \mathbb F_p$，计算$A,B,C$，然后令证明串$\pi=(A,B,C)$
• $Verify$：算法解析证明串$\pi$，首先验证$e(A,h)=e(G,B)$，这一步是确保$a(x,y)=b(x,y)$，然后验证第二个配对即可

这里感觉原文$Verify$算法的第二个验证等式错了，等号左侧的第二个配对应该是$e(AG^{y^5+t(x)y^6},H^{n(x,y,z)})$，如果多减去一个求和号$\sum$的话，就和$c(x,y,z)$不相等了

然后就是针对这个方案的一个引理

• Lemma 7：若QAP满足$t(x)\neq y^{-1}$，则派生算法可在多项式内计算，且证明系统具有完美完备性

本文的另一个重点，这里详细看一下证明，也是URS派生出zk-SNARK的主要流程

• Proof：给定关系$R$和格式正确的$crs$，考虑一个派生算法，在群$\mathbb G_1$中派生算法需要计算一些群元素，这些群元素的指数如下

  • $\{w_i(x)y^2+u_i(x)y^3+v_i(x)y^4\}^m_{i=0}$，其中范围为$\{x^iy^j:i\in [0,d],j\in[2,4]\}$
  • $t(x)y^6$，其中范围为$\{x^iy^j:i\in [0,d],j=6\}$
  • $\{x^iy\cdot n(x,y,z)\}^d_{i=0}$，范围为$\{x^iy^jz^k:i\in[0,2d],j\in[1,4],k\in[1,3d-m+l(i,j)\neq (d,4) \ or \ i\in[0,d],j\in[1,2],k=6d\}$，这里有两种情况，具体取决于$n(x,y,z)$的选择（这里原文写的是$z=6d$，个人认为应该是写错了，应该是$z=6d$）
  • $\{(w_i(x)y^2+u_i(x)y^3+v_i(x)y^4)\cdot n(x,y,z)\}^m_{i=l+1}$，范围为$\{x^iy^jz^k:i\in[0,2d],j\in[2,6],k\in[1,3d-m+l],(i,j)\neq(d,4) \ or \ i\in[0,d],j\in[2,4],k=6d\}$（这里同样写错了，个人认为应该是$z=6d$）

然后在群$\mathbb G_2$中派生算法需要计算下面这些群元素

• $y-t(x)y^2$，范围为$\{x^iy^j:i\in[0,d],j=2 \ or\ i=0,j=1\}$
• $\{w_i(x)y^2+u_i(x)y^3+v_i(x)y^4\}^m_{i=0}$，范围为$\{x^iy^j:i\in [0,d],j\in[2,4]\}$
• $t(x)y^6$，其中范围为$\{x^iy^j:i\in [0,d],j=6\}$
• $n(x,y,z)$，范围为$\{x^iy^jz^k:i\in[0,d],j\in[0,2],k\in[1,3d-m+l]\ or\ (i,j,k)=(0,0,6d)\}$

上述需要的群元素都在URS中，因此可以从URS派生出基于QAP的CRS，此时若Prover有一个witness，则我们可以得到一个度至多为$d-1$的多项式$q(X)$，满足$\sum^m_{i=0}a_iu_i(X)\cdot \sum^m_{i=0}a_iv_i(X)=\sum^m_{i=0}a_iw_i(X)+q(X)t(X)$，此时可得到$A,B$可以从方案中规定的$crs_{QAP}$计算，且满足第一个验证方程，还可以得到的是，如果按照方案计算，则$A,B,C$满足第二个验证方程，但是需要证明$C=G^{c(x,y,z)}$可从$crs_{QAP}$中计算得到

对于$C=G^{c(x,y,z)}$，首先观察$a(x,y)\cdot b(x,y)$，注意到$a(X,Y)\cdot b(X,Y)\in\{X^iY^j\}^{2d,12}_{i=0,j=2}$，根据的$crs_{QAP}$结构，其中没有$X^iY^7$的项，此时可以计算$G^{a(x,y)\cdot b(x,y)}$，然后根据$q(X)$的结构，有

$$ a(X,Y)^2=\Big( q(X)Y+r(Y-t(X)Y^2 )+\sum^m_{i=0}a_i(w_i(X)Y^2+u_i(X)Y^3+v_i(X)Y^4)-Y^5-t(X)Y^6 \Big)^2 $$

这个乘积中$Y^7$的项的系数如下，根据第四节中提到的QAP的验证方程，该项应当为零

$$ \begin{aligned} 2\Big( -q(X)t(X)-r(t(X)-t(X)) - \sum^m_{i=0}a_iw_i(X)+\sum^m_{i=0}a_iv_i(X)\cdot \sum^m_{i=0}a_iv_i(X) \Big)=0 \end{aligned} $$

这意味着$crs_{QAP}$的结构可以计算$G^{c(x,y,z)}$的剩余部分

然后接下来看两个定理

• Theorem 3：若QAP满足$t(x)\neq y^{-1}$，则证明系统具有完美零知识颠覆性
• Theorem 4：若q-MK和q-MC假设对$\boldsymbol a=\{X^iY^jZ^k:(i,j,k)\in S_1\},\boldsymbol b=\{X^iY^jZ^k:(i,j,k)\in S_2\}$成立，则证明系统具有可更新知识合理性

完整证明可以看原文$[1]$

6 Updating a Reference String Reveals the Monomials

本节给出了一个否定结果：也即对于任何可更新的基于配对的NIZK，并将多项式编码到CRS中，必须允许敌手知道构成多项式的单项式的编码，因为从多项式的编码中可以构造一个使用更新算法来抽取单项式的敌手，但是通常不允许敌手知道构成单项式的编码，因此没有办法构造这样的抽取单项式的方式

原文给出了利用单项式提取器攻破基于QAP的zk-SNARK的一个示例，原文采用了Pinocchio协议$[PHGR13]$作为例子，其他基于QSP/QAP的zk-SNARK也可用类似的方法更新

原理比较复杂，具体可以看原文，简单来说就是这种单项式抽取器会破坏大多数基于QAP/QSP的基于配对的NIZK论证，因为这些论证通常取决于实例和witness的多项式，这两个多项式之间是线性独立的，因此可以用单项式抽取器攻破协议的知识合理性

总结

前后看了两天，一篇非常好的paper

这篇paper两个重点吧，一个是构造可更新的URS，一个是从URS导出特定QAP的CRS

主要的思路是抛弃了之前采用多项式的方式，而是引入了单项式来完成URS的构建，然后通过递归验证的方式来确保每次更新后的CRS都是可信的，有点类似于区块链的思想

然后方案利用可更新的URS导出针对QAP的CRS，从表1就可以看到，和目前最好的Groth16比起来，Prover开销仅多了两次配对运算

但是方案的优点在于它是通用可更新的，意味着他不针对于特定的电路和特定的的QAP重新生成CRS，只需要一个简短的更新URS和验证更新正确的步骤即可

从URS导出CRS的方法也很简单，只需要导出对应范围的群元素即可，然后接下来的Prove和Verify和以往的QAP方案大同小异

后记

一个比较妙的paper吧，感觉看完之后对自己的方案有了新的思路

这篇paper讲的可更新的URS，之前不记得在哪里看到了密钥可更新的（不知道有没有这种玩意，也可能是记错了）

看完之后有个idea，结合之前看的那篇RSA门限签名和BLS门限签名，想做一个密钥可更新的零知识签名方案，其中密钥更新的过程是零知识的

自己在想这个方案是否具有可行性，看完这篇paper有了个想法，

如果密钥可更新，是否意味着门限签名中的$t$是可变的，不局限于固定的$t$个人，如果其中有人退出或加入，只需要更新密钥集，然后就可以用一个新的门限值$t'\neq t$完成签名

有这么个想法，但是具体可行性需要问一下导师

References

$[1]$ Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, Ian Miers:Updatable and Universal Common Reference Strings with Applications to zk-SNARKs. CRYPTO (3) 2018: 698-728