MOEX交易所讯、MOEX交易所内容分享,关于【MOEX交易所】怎么样你了解多少,我们一起来看看MOEX交易所的技术创新在哪。
本系列的第二篇文章,以超市收据为例,描绘了Arithmetization 的具体进程。本文将以另外一个例子为基础,在回顾Arithmetization 进程的一起,将内容引申到多项式的LDT进程。
新的实例
Alice Claim:“我有1000,000个数,他们都在[0,9]规模内”。为了便利验证者Bob验证,Alice首先要对Claim进行Arithmetization转化。进程如下图1所示(图中:黑色箭头代表主流程,赤色箭头代表附加阐明信息,黄色圈对应下面具体阐明的索引)
下面具体阐明一下对应流程:
首先生成履行轨道(EXCUTE TRACE),事实上,它是一张表,一共有1000,000行(实践上,为了到达零常识的意图,还需求在履行轨道后面增加一些随机值,具体数量是由证明者和验证者共同协调决定的,作为一个扩展,不具体叙述);
生成多项式束缚(Polynomial Constrains),多项式束缚满意履行轨道的每一行(个人了解:进程1,2没有必定的先后依靠关系,仅仅习惯上先生成履行轨道,再生成束缚多项式);
对履行轨道进行插值,得到一个度小于1000,000的多项式P(x)、x取值[1,1000,000],并核算更多点上的值,x取值规模扩大到[1,1000,000,000](Reed-Solomen体系编码);假定,证明者有一个值不在[0,9]规模内(图中红线1/2所示),假定便是第1000,000个点,它实践的值是13,大于9,其插值后的曲线G(x)如图所示,图中P(x)为有效曲线,G(x)为无效曲线。能够看出,两条曲线在变量x取值[1,1000,000,000]规模内,最多有1000,000个交点,即有1000,000,000 – 1000,000个点不同,这很重要。
将插值后的多项式P(x)和多项式束缚进行组合改换,终究得到的方式为:
Q(P(x)) = Ψ(x) * T(x),其间T(x) = (x – 1)(x – 2)……(x – 1000,000),x取值[1,1000,000,000]
其间,d(Q(P(x))) = 10,000,000、d(Ψ(x)) = 10,000,000 – 1000,000、d(T(x)) = 1000,000;
至此,问题就转化成了,Alice宣称“多项式等式在变量x取值[1,1000,000,000]规模内建立”的问题。那么验证者Bob该怎么验证呢?具体进程如下(图中红线3/4所示):
证明者Alice在本地核算多项式P(x)、Ψ(x)在所有点上的取值,对!从1至1000,000,000,并形成一个默克尔树;
验证者Bob随机的从[1,1000,000,000]内选取一个值 ρ,并发送给证明者Alice,要求其回来对应的信息(事实上为了到达零常识的意图,只允许从[1000,000,1000,000,000]上随机挑选一点);
证明者Alice回来 P(ρ)、Ψ(ρ)、root、AuthorizedPath(P(ρ)、Ψ(ρ))给验证者Bob;
验证者Bob首先依据默克尔树验证路径验证值P(ρ)、Ψ(ρ)的有效性,然后等式Q(P(ρ)) = Ψ(ρ) * T(ρ),假如建立,则验证经过;
完好性分析:假如验证者Alice是诚实的,那么等式Q(P(x))必定会被目标多项式T(x)整除,因而必定存在一个d(Ψ(x)) = d(Q(P(x))) – d(T(x))的多项式Ψ(x),满意Q(P(x)) = Ψ(x) * T(x),因而关于恣意的x,取值在[1,1000,000,000]之间,等式都会建立;
可靠性分析:假如验证者Alice是不诚实的,即类似于进程3里的假定,在x = 1000,000上,P(x)的取值为13,那么Q(P(1000,000)) != 0,可是等式右边,T(1000,000) = 0,因而Q(P(x)) != Ψ(x) * T(x),即等式两边是不相等的多项式,其交点最多有10,000,000个,因而经过一次随机选取,其验证经过的概率仅为10,000,000/1000,000,000 = 1/100 = 0.01,经过k次验证,其验证经过的概率仅是1- 10(^-2k);
上述的验证进程为交互式的,假如是非交互式的,能够使用Fiat-Shamir heuristic进行改换,以默克尔树的根作为随机源,生成要查询的随机点;
LDT
咱们忽略了一种攻击方法,即针对每一个数x,证明者都随机生成p,然后依据Ψ(x) = Q(p) / T(x),这些点不在任何一个度小于1000,000的多项式上,可是能够经过验证者验证。如下图2所示:
图中:紫色的点为随机生成的点p,这些点大约率不在一个度小于1000,000的多项式上(事实上,能够不考虑前1000,000个点,由于验证者只会从[1000,000,1000,000,000]规模内取值)。由于即便挑选1000,000个点插值出一个度小于1000,000的多项式,也不能保证其他的点在这个多项式上,由于其他的点是随机生成的。因而,需求有一种方法,保证证明者P(x)的度是小于1000,000, Ψ(x)的度小于10,000,000 – 1000,000。这便是LDT的目标,那LDT具体的进程是怎么样的呢?请持续往下看。
举个栗子,假如Alice想证明多项式f(x)的度是小于3的,即有或许是2次的或者是1次的。一般流程如下:
验证者Bob随机选取三个值a,b,c,发送给证明者Alice;
证明者Alice回来f(a),f(b),f(c);
验证者Bob插值出度小于3的多项式g(x),然后再随机选取一个点d,发送给证明者;
证明者Alice回来f(d);
验证者Bob比对f(d)和g(d)的值,假如相等,则证明建立。
回归到一般情况,其进程能够用下图3表明:
能够看出,假如D很大,Alice和Bob交互的次数则为D+k次,复杂度很高;有没有一种办法,使得两者之间交互的次数小于D的情况下,使得验证者信任多项式的度是小于D的,直接回来小于D个点肯定是不可的,由于那不能唯一确定一个度小于D的多项式,因而需求证明者需求额外发送一些辅佐信息。下面咱们以P(x)为例,具体阐述这个进程(事实上,应该是证明P(x)和Ψ(x)的线性组合小于10,000,000 – 1000,000,本文重点是LDT,因而只以P(x)为例,这并不影响对LDT的了解)。
假定P(x) = x + x^999 + x^1001 + x^999999 = x + x^999 + x * x^1000 + x^999*(x^1000)^999;
此刻,咱们找到一个二维多项式G(x, y),取值规模分别是[0, 999999999]、[01000, 9999999991000],满意:
G(x, y) = x + x^999 +x * y + x^999*y^999 能够发现,当y = x^1000时,满意:
G(x, y) = G(x, x^1000) = x + x^999 + x * x^1000 + x999*(x^1000)^999 = P(x)
假如咱们能证明G(x, y)相对的x,y的最高度都是小于1000,由于P(x) = G(x, x^1000)上,因而能够信任P(x)的度小于1000,000;如图4所示:
验证者把所有的点都核算好(没错,一共10^18个点,吓死BB了),形成一颗默克尔树。验证者随机挑选一行和一列,如图中红线1/2所示,关于每一列,它是由关于y的度小于1000的多项式生成,关于每一行,它是由关于x的度小于1000的多项式生成。验证者从行/列中随机挑选1010个点,用来验证对应行/列上的点是否在度小于1000的多项式上,需求留意的是,由于P(x)的点都在上图的对角线上,因而咱们要保证每一行/列对应的对角线上的点也在对应的度小于1000的多项式上,即1010个里边必定要包含对角线的点。
可靠性分析:假如原始多项式的度实践上是小于10^6 +10999,即 P(x) = x + x^999 + x^1001 + x^1010999 ,那么对应的G(x, y)为G(x, y) = x + x^999 +x * y + x^999*y^1010 ,即,关于每一个x,G(x, y)是关于y的一元多项式函数,且度d < 1010,因而下图中的每一列所有点都是在度d < 1010的多项式上,而不在d < 1000的多项式式上。所以假如证明者任然宣称多项式P(x)的度d < 1000,000 ,则会验证失败,其他场景是同样的道理
那有没有或许恶意证明者仍以G(x, y) = x + x^999 +x * y + x^999*y^999 的方式去生成依据呢?这样会验证经过吗?
咱们知道,咱们在验证时着重强调了对角线上的那一点必定要在多项式上,咱们知道,此刻对角线对应的多项式方式是
P(x) = x + x^999 + x1001 + x^999999 ,而实践的P(x),咱们在这里标记为P`(x) ,其方式是:
P`(x) = x + x^999 + x^1001 + x^1010999
因而,假如验证者刚好挑选的点是两个多项式的交点,则会验证经过,事实上,两个多项式最多有1000,000 左右个交点,可是由于随机选取的点不是证明者自己选取,是由默克尔树的根为种子随机生成,因而证明者没有机会作恶,去能够选取那些能经过验证的点。
由于一共由10^9个点,因而随机选取一个点,能验证成功的概率为10^6 / 10^9 = 10^(-3),假如挑选k行,则成功的概率仅为10^(-3k)。
以上能够看出,验证者和证明者只需求交互1010 * 2 * k个点,就能够完成验证,假定k = 10,则1010 * 2 * 10 = 20100 << 10^6。
尽管上述实现了在交互次数小于D的情况下,完好LDT验证,可是证明者的复杂度过于巨大,至少10^18的复杂度远远大于原始的核算,因而需求一些优化方案,下降复杂度。话不多说,直接引入有限域,毕竟在实践项目中,咱们可不期望数值本身过于巨大。直接引用费马小定理的定论:在有限域p内,假如满意(p – 1) 能被k整除,则映射x => x^k的像只要(p -1) / k + 1个。下图5以p = 17,映射x=> x^2为例:
图中,赤色为x^2在有限域p内的象,一共由(p – 1) /2 + 1 = 9个。一起咱们能够发现,9^2和8^2的像共同,10^2和7^2的像共同,以此类推,16^2和1^2的像共同,记住这个现象,对下一张图的了解有协助。
因而,在本例中,咱们挑选一个素数p = 1000,005,001,其满意:
为素数
p – 1 能被1000整除
p要大于10^9
因而,在有限域p内,x => x^1000的像在p内有(p -1) / 1000 = 1000,005个,因而图4能够变成图6的方式:
能够看出,列坐标变成了10^6个元素,对角线变成了平行的线条,一共有1000个。还记得上面费马小定理定论的特别现象吗?这便是对角线这种分布的原因,读者试着去了解(或许读者会觉得,对角线应该是锯齿形,不是这种平行的方式,也许你是对的,可是这并不影响验证流程)。此刻证明者的复杂度现已从10^18 削减到了10^15次方,证明和验证进程和进程3描绘的依然共同。
还能不能持续优化呢?答案是肯定的。回想起前面所述的验证进程,关于每一行/列,验证者都要获取1000个点进行插值得出一个度小于1000的多项式,仔细观察图6,关于每一行,原始数据里不便是有1000个数么?那咱们干脆选这些点插值出一个度小于1000的多项式,然后只需求随机让证明者再核算任何一列,而且证明沿着列上的点都在度小于1000的多项式上,而且列上的点也在对应的使用原始数据插值出的行多项式上。此刻,证明者复杂度从10^15削减到了10^9次方。
总结:个人了解,从进程1到进程5,其实是PCP到IOP的挑选进程。
PCP要求证明者生成悉数的依据,然后验证者多次随机选取其间的某一部分进行验证,可是这样,证明者的复杂度依然很高;
IOP要求证明者不必生成悉数的依据,依据多次的交互,每次生成只需生成部分依据,使得证明的复杂度和D呈近似线性关系;
证明者复杂度现已下降到了与D呈拟线性关系,验证者的复杂度尽管是亚线性,交互次数现已低于D,可是能不能优化到更低呢?基于证明复杂度的最优设置,咱们持续探究验证复杂度的优化之路,回顾P(x) = x + x^999 + x^1001 + x^999999 = x + x*(x^2)^499 + x*(x^2)^500 + x*(x^2)*499999,令G(x, y) = x + x*y^499 + x*y^500 + x*y^499999,则当y = x^2时,有G(x, y) = G(x, x^2) = x + x*(x^2)^499 + x*(x^2)^500 + x*(x^2)*499999 = P(x)。终究的图应如下图7所示:
从图中可知:
证明则复杂度仍为10^9次方;
每一行上的点都在度d < 2的多项式上,由于当y取固定值时,G(x, y)便是关于x的一次多项式;
每一列上的点都在度d < D/2的多项式上,证明者需求证明这个多项式是小于D/2的,假定这个多项式为P1(x),这个时候,并非验证者选取大于D/2个点去验证,由于验证复杂度依然不够低,而是对这一列再一次用到类似于P(x)的处理进程,如图7中下面的图所示,以此循环,直到能够直接判断列上的多项式的度为止,类似于行。
总结
至此,本篇文章就完毕了,总结下来,本文主要阐述了以下几个内容:
怎么转化问题方式 — Arithmetization
为何需求LDT — 为了验证简洁
LDT的大约进程 — 二分法验证,类似于FFT
下降LDT的复杂度 — 有限域+IOP