Plonkup 介绍

作者: 雪落无留痕 | 来源:发表于2021-04-23 22:53 被阅读0次

Plonkup 介绍
Plonkup 聚合证明
Matter Labs PLonkup 源码分析
Plonkup中Hash函数设计
Runtime介绍---术语介绍
介绍
介绍😊
介绍
介绍
介绍

Plonkup由Gabizon发表于2020年，利用lookup查找表提升减少计算，可以提升证明者效率。Plonkup可以实现递归证明而无需椭圆曲线对（如Halo等需要椭圆曲线对）。

背景

传统的一些密码基元如Hash函数，为了兼顾安全和在软硬件实现上的高效性，通常处理涉及大量位运算。但这些操作在域内运算上是非常低效的，造成电路门数大幅增加。

例如对于Sha256处理的主要函数：
$maj(x,y,z)=(x\wedge y)\oplus(x\wedge z)\oplus(y\wedge z) \\$
可以构造如下查询表：

$\mathbf{x}$	$y$	$\mathbf{z}$	$maj(x,y,z)$	$x+y+z$
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	2
1	0	0	0	1
1	0	1	1	2
1	1	0	1	2
1	1	1	0	3

对于两个序列 $(f_1, f_2, \cdots, f_n)$ 和 $(t_1,t_2,\cdots,t_d)$ ，满足 $f_i\in \{t_i\}$ ,构造新的序列 $(s_1, s_2,\cdots,s_{n+d})$ , 即 $s_i$ 由 $f_i$ 和 $t_i$ 拼接，并根据 $t$ 排序后得到，需要利用grand product 来证明它们的置换关系。

Plonkup对于函数的输入输出元组 $(input_i, output_i)$ 压缩为单个域元素 $f_i$ , 然后要检查要查询的值在查找表 $(t_1,t_2,\cdots,t_d)$ 中。

随机差分序列

为了证明 $f_i \in \{t_i\}$ , Plonkup引入差分序列的概念。

对于序列 $(f_1, f_2, \cdots, f_n)$ ，定义差分序列为： $(f_2-f_1, f_3-f_2,\cdots, f_n-f_{n-1})$

例如对于序列 $(1,4,8)$ ，若要验证其属于序列 $(1,1,4,8,8,8)$ ，可分别计算其差分序列为： $(3,4)$ 和 $(0,3,4)$ , 其中0代表重复的元素，只需要验证差分序列是否相同即可。

验证差分序列只是必要条件，为了保证充分性，Plonkup引入了随机差分序列的概念，即差分序列的元素为： $f_i + \beta \cdot f_{i+1}$ , 其中随机数 $\beta \in \mathbb{F}$ 。

关键定理

对于序列 $(f_i)_{i\in [n]}$ ， $(t_i)_{i \in [d]}$ ， $(s_i)_{i\in[n+d]}$ :

$\{f_i: i\in [n]\}\subseteq \{t_i: i\in [d]\}$
$s=(f,t)$ , 根据 $t$ 重新排序。

上述成立的条件当且仅当 $F\equiv G$ ，其中
$F(\beta, \gamma):= \prod_{i\in[n]}((1+\beta)(\gamma+f_i))\cdot\prod_{i\in [d-1]}(\gamma(1+\beta)+t_i + \beta t_{i+1}) \\ G(\beta, \gamma):= \prod_{i\in [n+d-1]}(\gamma(1+\beta)+s_i + \beta s_{i+1})$
当 $s_i = s_{i+1}$ 时， $G$ 可以得到因子： $(1+\beta)(\gamma + s_i)$ 。

Plonkup协议

Plonkup将函数计算问题，转变为序列问题。例如对于函数 $f(x,y)=z$ ，验证者选择随机数 $\alpha \in \mathbb{F}$ 给证明者。双方同时计算域元素序列的集合，即 $\{\alpha x + \alpha^2y + \alpha^3 z: f(x,y)=z\}$ , 构造查询表。

以下假设 $d=n+ 1$ , 若 $d\leq n$ ，可以在 $t$ 后面补 $n-d + 1$ 个 $t$ 的最后一个元素。

将 $(f, t)$ 根据 $t$ 排序后得到 $s\in \mathbb{F}^{2n+ 1}$ ，用 $h_1, h_2 \in \mathbb{F}_{<n+1}[X]$ ，定义 $h_1(g^i)=s_i$ , $i \in [n+1]$ ; $h_2(g^i)=s_{n+i}$ , $i \in [n+1]$ 。
${P}$ 计算多项式 $h_1, h_2$ ，并将其发送给第三方 $\mathit{I}$ ；
${V}$ 选择随机数 $\beta, \gamma$ ，并将其发送给 ${P}$ ；
${P}$ 计算多项式 $Z \in \mathbb{F}_{n+1}[X]$ ，聚合 $F(\beta, \gamma)/G(\beta, \gamma)$ 的值，即：

(a) $Z(g)=1$

(b) 对于 $2\leq i \leq n$ ，
$Z(g^{i+1})=Z(g^i)\cdot \frac{(1+\beta)(\gamma + f_i)(\gamma (1+\beta)+t_i+ \beta t_{i+1})}{(\gamma(1+\beta)+s_i + \beta s_{i+1})(\gamma(1+\beta)+s_{n+i}+\beta s_{n+i+1})}$
（c) $Z(g^{n+1})=1$

${P}$ 将 $Z$ 发送给 $\mathit{I}$ ;
$V$ 校验 $Z$ 确实根据上面的形式计算，且 $Z(g^{n+1})=1$ ; 即对所有的 ${x} \in \mathit{H}$ , $V$ 验证下面的恒等式成立：

（a） $L_1({x})(Z({x})-1)=0$ ;

(b)
$({x} - {g}^{n+1})Z({x})(1+\beta)\cdot (\gamma + f({x}))(\gamma + f({x}))(\gamma(1+\beta)+t({x})+\beta t({g}\cdot {x})) \\ = （{x}-\mathbf{g}^{n+1})Z(\mathbf{g}\cdot \mathbf{x})(\gamma(1+\beta)+h_1(\mathbf{x})+\beta h_1(\mathbf{g\cdot x}))(\gamma(1+\beta)+h_2(\mathbf{x})+\beta h_2(\mathbf{g\cdot x}))$
(c) $L_{n+1}({x})(h_1({x})-h_2({g\cdot x}))=0$

(d) $L_{n+1}(Z(\mathbf{x})-1)=0$

上述过程类似于Plonk置换中grand product的验证。若验证通过，则表明所有的 $f_i$ 都在查找表 $(t_1, t_2, \cdots, t_n)$ 中存在。

向量查找表

对于有多个witness 多项式： $f_1, f_2, \cdots, f_w \in \mathbb{F}_{<n}[X]$ , 查找表值 $t^* \in (\mathbb{F^w})^d$ , 需要检验：对于 $j\in [n]$ , $(f_1({g}^j),\cdots, f_w({g}^j))\in t^*$ , 可以利用随机化归为上一节的处理方式。

对于每个 $i\in [w]$ , 引入预处理多项式 $t_i\in \mathbb{F}_{<d}[X]$ , 且 $t_i({g}^j)=t_{i,j}^*$ , $j \in [d]$ ;

验证者随机选择 $\alpha \in \mathbb{F}$ ;

然后定义 $t:=\sum_{i\in [w]}\alpha^i t_i$ , $f:= \sum_{i\in [w]}\alpha^i f_i$

假如对于 $j\in [n]$ , $f_1({g}^j), \cdots, f_w({g}^j)\notin t^*$ , 除非是可忽略的概率，保证 $f({g}^j)\notin t$

对于具有 $w-1$ 个输入的函数 $f$ ，可以验证向量的形式 $(x_1,\cdots, x_{w-1}, f(x_1, \cdots, x_{w-1}))$ 。

多个查找表

假v中有多个查找表 $t_1^*, \cdots,t_l^*$ ，对于每一个 $i\in [n]$ , 检查 $j=j(i)\in [l]$ ， $(f_1({g}^i), \cdots, f_w({g}^i))\in t_j^*$ ，可以创建一个预处理的表 $t_1^*, \cdots, t_l^*$ 作为子表，并添加一列作为表的索引。

对于 $j \in [l], t_j^* \in (\mathbb{F}^w)^{d/l}$ ，构造 $t^* \in (F^{w+1})^d$ ，对每一个 $j \in [l], i\in [d/l]$ ，包括 $(j, (t_j^*)_i)$ 。可以预处理一个多项式 $q\in \mathbb{F}_{<n}[X]$ ，使得 $q_i = j(i)$ ， $j(i)$ 代表第 $j$ 个子表的第 $i$ 个值。

然后可以用上面的向量方法，对每一个 $i\in [n]$ , 检查 $q(\mathbf{g}^i), f_1(\mathbf{g}^i), \cdots,f_w(\mathbf{g}^i)\in t^*$

连续范围的优化方案

若需要检查 $f\subset \{0, \cdots, d-1\}, d< n$ ，可以使用上述协议，设定 $t_i = i-1, i\in [d]$ 。当 $d=n+1$ 的时候，可以检查 $f\subset \{0, \cdots, n\}$ 。这个协议还可以推广到范围 $\{0, \cdots, c(n-1)\}$ 范围的检查，设定 $s_1=0,s_{2n+1}=c\cdot(n-1), i\in [2n]$ ， $s_{i+1}-s_i\leq c$ , 可以推导 $s_i\in \{0,\cdots, c(n-1), i \in [2n+1]$ 。

设查找表 $t$ 为： $t_i= c\cdot (i-1), i\in [n]$ . ${H}$ 为阶为 $n+1$ 的乘法群，生成元为 ${g}$ 。

协议参数 $c$ 为一个正整数，多项式 $P(X):=\prod_{i=0}^c(X-i)$ ，用来约束 $s_{i+1}-s_i\leq c$ 。

协议步骤如下：

设 $s\in \mathbb{F}^{2n+1}$ 为 $(f, t)$ 根据 $t$ 排序后得到的向量，利用多项式 $h_1, h_2 \in \mathbb{F}_{<n+1}[X]$ 来表示 $s$ ，即 $h_1({g}^i)=s_i i \in [n+1]$ , $h_2({g}^i)=s_{n+i}$ , $i\in [n]$ 且 $h_2({g}^{n+1})=c(n-1)$ ；
$P$ 计算多项式 $h_1, h_2$ ，并将其发送给 ${I}$
验证者 $V$ 选择随机数 $\gamma \in \mathbb{F}$ ，并将其发送给 ${P}$ ;
${P}$ 计算多项式 $Z\in \mathbb{F}_{<n+1}[X]$ ，聚合 $F(\beta, \gamma)/G(\beta,\gamma)$ 的值，即

（a） $Z(g)=1$

(b) 对于 $2\leq i \leq n$ ，
$Z({g}^i) = \frac{\prod_{j<i}(\gamma+ f_i)\cdot\prod_{1\leq j <i}(\gamma+t_j)}{\prod_{1\leq j< i}(\gamma+s_j)(\gamma +s_{n+j})}$
(c) $Z({g}^{n+1})=1$

${P}$ 将 ${Z}$ 发送给 ${I }$ 。
${V}$ 检查以下恒等式对所有的 ${x}\in H$ 成立。

(a) $L_1({x})(h_1({x}))=0$

(b) $P(h_1({g\cdot x})-h_1({x}))=0$

(c) $P(h_2(\mathbf{g\cdot x})-h_2(\mathbf{x}))=0$

(d) $L_{n+1}({x})(h_1({x})-h_2({{g\cdot x}}))=0$

(e) $L_{n+1}(\mathbf{x})(h_2(\mathbf{x}))= c\cdot (n-1)$

(f) $L_1({x})(Z({x})-1)=0$

(g)
$(\mathbf{x}-\mathbf{g}^{n+1})(Z(\mathbf{x})(\gamma +f(\mathbf{x}))= (\mathbf{x}-\mathbf{g}^{n+1})\cdot Z(\mathbf{g\cdot x})(\gamma + h_1(\mathbf{x}))(\gamma + h_2(\mathbf{x}))$
(h) $L_{n+1}({x})(Z({x})-1)\equiv 0$

参考

https://github.com/kevaundray/plookup

https://research.metastate.dev/on-plonk-and-plookup/

https://github.com/Fluidex/awesome-plonk

https://hackmd.io/xfgP5_uMTZyaEJJG4EJoRQ?view

https://hackmd.io/@arielg/ByFgSDA7D

Plonkup 介绍
Plonkup[https://eprint.iacr.org/2020/315.pdf]由Gabizon发表于2...
Plonkup 聚合证明
本文主要对Matter Labs 聚合证明理论和源代码进行解析，参考： Github: https://githu...
Matter Labs PLonkup 源码分析
本文对Matter Labs Plonkup 零知识证明源码分析，它可以用在聚合证明中。主要参考： https:...
Plonkup中Hash函数设计
本文主要介绍如何结合Plonk的数值电路和 looup 门电路以最小的约束条件实现Hash函数。电路示例通过...
Runtime介绍---术语介绍
1. 什么是Runtime Runtime又叫运行时，是一套C语言的API。我们平时编写的OC代码，底层都是基于...
介绍
万物终有一天会消失殆尽，诸神出卖黎明，光明为黑暗所湮灭，日月皆痕，海潮鸣泣，幼雏嚎啕，生灵涂炭。托里奥世纪第20...
介绍😊
大家好，我是beth，初入简书，不邀自来，还请各位见谅！先说说我是怎么想着来的吧？这不是刚过了一个寒假嘛...
介绍
在这个世界上还有三个家族他们不受各个国家联合国管。但他们身上有着使命分别是帝国家族曲国家族圣国家族。他们隐藏在一个...
介绍
云轩：主角，星罗帝国的二皇子。从小就不能练气，被人们称为废物。直到12岁的时候，自己的武魂觉醒才能练气，双...
介绍
万花阁神秘至极的组织，亦正亦邪。万花阁的人行动隐秘，至今未被发现所在地。听说组成成员均以花来命名。所到之处，皆留...

Plonkup 介绍

背景

随机差分序列

关键定理

Plonkup协议

向量查找表

多个查找表

连续范围的优化方案

参考

相关文章

Plonkup 介绍

Plonkup 聚合证明

Matter Labs PLonkup 源码分析

Plonkup中Hash函数设计

Runtime介绍---术语介绍

介绍

介绍😊

介绍

介绍

介绍

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读