Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文
我们谈到了,如何能够做出一些非常有意思且简洁的计算证明,比如通过利用多项式复合和除法技术,证明你算出了第一百万个斐波那契数。但是,它依托于一个非常重要的元素:给定一个集合,里面有很多的点,你必须能够证明集合里的大部分点都在同一个低次多项式上(译者注:本文所译的多项式度数或次数,皆对应 degree 一词)。这个叫做“低次测试”的问题,可能是协议中最为复杂的部分。首先,再次回顾一下我们的问题。假设有一些点,你声称它们都在同一个多项式上,并且该多项式的度少于 D(也就是说,如果度小于 2,意味着这些点在同一直线。如果度小于 3,意味着它们在同一直线或抛物线,等等)。而你想创建一个简洁的概率证明,证明的确如此。左图:所有点都在度小于 3 的多项式上;右图:红色点与蓝色点不在同一个度小于 3 的多项式上如果你想要验证,这些点 全部 都在同一个度小于 D 的多项式上,那么实际上你将不得不对每一个点进行检查,因为哪怕是仅仅漏掉一个点,也可能会出现差错:漏掉的这个点刚好不在这个多项式上,而其他点恰好都在上面。不过,你可以做的是,在所有的这些点中,概率性地检测至少有部分(比如 90%)点都在同一个多项式上。左上:可能足够接近于某一多项式;右上:不够接近某一多项式;左下:同时接近于两个多项式,但是又不足以接近任意一个;右下:显然不够接近任一多项式如果你能够检查多项式上的每一个点,那么问题非常简单。但是,如果你只能够检查几个点呢?——也就是说,你可以要求检查任意几个点,作为协议的一部分,证明者也有义务给你这些点,但是查询次数总数是有所限制的?那么问题来了,你需要检查多少个点,才能在一定程度上进行确认?显然,D 个点是不够的。因为 D 个点恰好可以唯一定义一个度小于 D 的多项式,所以你得到的 任意 的点集合,都只会与某个度小于 D 的多项式相关。从上图可以看出,D+1 或更多的点,肯定 可以给我们带来更多信息。给定一些值,通过 D+1 次查询,检测这些值是否在同一个度小于 D 的多项式上,其算法其实并不十分复杂。首先,从 D 个点中随机挑选一个子集,并用像拉格朗日插值法(在
. I2 c) F6 p& H) N这里搜索 “Lagrange interpolation” 获得更多介绍)来还原这个唯一的度小于 D 的多项式,并且该多项式能够通过这些所有的点。然后,随机再采样一个点,检测该点是否在同一个多项式上。第一步:选 D 个点;第二步:还原度小于 D 的多项式;第三步:再检查一个点注意,这仅仅是一个临近测试(proximity test),因为无可避免地会出现这样一种情况,即虽然大部分点都在同一个低次多项式上,但却有另外一些点不在该多项式上,而第 D+1 个采样点恰好完全地错过了这些点。不过,我们可以对结果进行派生,如果在同一个度小于 D 的多项式上的点低于 90%,那么测试将很大可能失败。具体来说,如果你进行 D+k 次查询,有至少 p% 的点不在同一个多项式上,而其他点却在上面,那么通过测试的概率仅有 (1-p) ^k。但是,如果像上一篇文章的例子那样, D 非常大,而你想要在少于 D 次查询的情况下,验证一个多项式的度,那该怎么办呢?当然,这不太可能直接“对症下药”, 因为上面已作出了简单的论证(即,任意 k 提供辅助数据,间接地进行验证还是非常有可能的,并且能够获得大幅地效率提升。这就是像 2 R( F* p: ]# J2 Q
FRI
' [9 L3 u7 c5 I6 I. d# \1 i" V0 K(“Fast RS IOPP”,RS=“
' r) {: y$ B2 n( s! \+ y$ AReed-Solomon4 m1 \" M* C0 U) M5 Z9 I
”, IOPP = “Interactive Oracle Proofs of Proximity”) 这样的新协议想要做的事情,它与早先叫做近似概率可检验性证明(probabilistically checkable proofs of proximity (PCPPs) )的设计相类似。初识亚线性为了证明这一切都是可行的,我们从一个相对简单的协议开始,虽然有非常粗糙的折衷操作,但是仍然可以达到亚线性验证复杂度的目的——也就是说,你可以通过少于 D 次查询,近似证明一个度小于 D 的多项式(在这里也就是,通过少于 O(D) 次计算来对证明进行验证)=思路如下。假设有 N 个点(比方说 N 等于 10 亿),并且它们都在一个度小于 1,000,000 的多项式 f(x) 上。我们找到一个二元多项式(像 1 + x + xy + x^5*y^3 + x^12 + x*y^11 这样的表达式),表示为 g(x, y),并且 g(x, x^1000) = f(x)。通过如下操作即可完成:对于 f(x) 中第 k 度项(比如,1744 * x^185423),我们将它分解为 x^(k % 1000) * y^floor(k / 1000)(在该例中,1744 * x^423 * y^185)。你可以看到,如果 y = x^1000,那么 1744 * x^423 * y^185 等于 1744 * x^185423。在证明的第一阶段,证明者提交在整个正方形上 [1..N] x {x^1000: 1 然后,验证者可能随机选出几十行和几十列(如果我们想要一个非交互式的证明,可能使用
# m7 N7 \. b1 N& ^. Rthe Merkle root of the square as a source of pseudorandomness
0 t& @8 t+ i2 T$ _1 a: ~),对于所选的每一行或列,比如说,验证者要求从行和列的 1010 个点中采样一个点,以确保在每种情况下,要求的点都在对角线上。证明者必须对这些点作出回应,通过 Merkle 分支,证明它们是给证明者提交原始数据的一部分。验证者检查 Merkle 分支的确相匹配,这表明证明者所提供的这些点确实与 1000 次多项式相关。这给了验证者一个统计证明:大部分行主要被度小于 1000 的多项式上的点所填充大部分列主要被度小于 1000 的多项式上的点所填充对角线大部分都在这些多项式上
( r0 b) x& i4 G6 L/ e# l, _, |
因而,这使得验证者相信在对角线上的大部分点,确实与一个次数小于 1,000,000 的多项式相关。如果我们选出 30 行和 30 行列,验证者需要检测总共 1010 个点 * 60 行+列 = 60600 个点,虽然少于原始的 1,000,000 个点,但仍是差强人意。就计算时间而言,尽管由于多项式插值可以变为次二次(subquadratic),但对度小于 1000 的多项式进行插值,也有其自身的开销,从整体上看,算法验证仍是亚线性的。证明者的复杂度更高了:证明者需要计算并提交整个 N*N 长方形,这总共是 10^18 的计算成本(实际上还要更多一点,因为多项式求值仍然是超线性(superlinear)的)。在所有的这些算法中,对计算进行证明,远比单单执行该计算要复杂的多,但是我们将会看到,其实这些开销并非需要如此地高。模块化数学插曲在深入到更复杂的协议之前,我们需要稍微偏离下主题,讨论一下模块化数学(modular math)。通常,当面对代数表达式和多项式时,我们所面对的是使用的是 +,-,,/(还有求幂,不过它实际只是重复的乘法而已)这样操作符的常规数字和运算,这些都是我们在学校里面就学会的知识:2 + 2 = 4, 72 / 5 = 14.4, 1001 * 1001 = 1002001 等等。但是,数学家们已经意识到,这些定义加法,乘法,减法和除法的方式,并不是唯一*定义这些操作符的自洽(self-consistent)方式。定义这些操作符,另一种可替代也是最简单的例子是,下面定义的模块化数学。% 操作符代表“取余”,15 % 7 = 1, 53 % 10 = 3, 等等(注意答案始终是非负的,比如 -1 % 10 = 9)。对于任意指定的素数 p,我们可以重新定义:x + y   --->   (x + y) % p
: P9 L- G3 L$ Z  Xx * y   --->   (x * y) % p6 @/ }& _- ~2 C
x ^ y   --->   (x ^ y) % p
1 k+ B2 I8 h4 Xx - y   --->   (x - y) % p- {; E! k* y, f. {
x / y   --->   (x * y ^ (p-2)) % p
  Y8 [4 `% L; e* }3 c: ~& |9 E上面的例子都是自洽的。比如,如果 p = 7, 那么:5 + 3 = 1 (as 8 % 7 = 1)1 – 3 = 5 (as -2 % 7 = 5)2 * 5 = 33 / 5 = 2 (as (3 * 55) % 7 = 9375 % 7 = 2)
) z' X9 C* p; e8 A, _
对于像分配律这样更复杂的内容同样成立: (2 + 4)3 和 2 * 3 + 4 * 3 都等于 4。在这种新的数学中,甚至像 (a2-b2)=(a-b)(a+b) 也仍然是成立的。除法是其中最困难的部分:我们无法使用常规除法,因为我们想要结果始终是整数,但是常规除法常常会得到非整数的结果(比如 3/5)。在上面的除法公式中,p-2 次幂是一个使用 . v  e/ r6 y) Z% k5 ^$ e
[color=]费马小定理
$ j. [" ^7 q: M) |1 |2 g 直面该问题的结果,它表示对于任意非零的 x
' L% p$ G6 |& I1 x2 V( A) A4 i[color=]扩展欧几里得算法9 p" u' G' u4 ?) {
,其 Python 实现在
8 I6 I0 O9 K  v* c! Q9 [: I# b[color=]这里' E; N9 |2 ]9 ?7 c6 `
。由于数字“环绕”,模块化数学有时又叫“时钟数学”通过模块化数学,我们已经创立了一个全新的数学系统,因为它与传统数学在各个方面都是自洽的,所以我们在模块化数学里面讨论各种同样的结构,包括我们以“常规数学”论之的多项式。密码学家喜欢用模块化数学(或者,更通俗一点,“有限域”),因为一个数字的大小有界,它可以作为任意一个模块化数学的计算结果——无论你做什么,值都不会“跳出” {0, 1, 2 ... p-1}的范围。费马小定理还有另一个有趣的结论。如果 p-1 是某个数 k 的倍数,那么函数 x -> x^k 有一个小的“像(image)”——也就是,这个函数只能够给出 (p-1)/k + 1 个可能的结果。比如, x -> x^2 在 p=17 时,只有 9 个可能的结果。指数越高,效果越明显:比如,x -> x^8 在 p = 17 时,只有 3 个可能的结果。当然, x -> x^16 在 p=17 是只有 2 个可能的结果。如果是 0,返回 0,其他任何都返回 1.浅谈效率让我们来继续讨论一个稍微复杂点的协议,它的目标在于,将证明者的复杂度从 10^18 降至 10^15,继而降至 10^9。首先,我们并不是针对常规数字进行操作,而是使用模块化数学检查多项式的近似程度。正如在上篇文章所述,在
6 x# [8 G) P: m+ _+ P6 ?" y  ASTARKs 中,我们无论如何都要防止数字增长至 200,000 位。但是在这里,我们将要利用确定的模幂(modular exponentiation)的“小像(small image)”属性,并将其视作为一个副作用,来使得我们的协议更有效率。具体来说,我们将选用 p = 1,000,005,001。之所以选择这个系数(modulus),是因为:它比 10 亿大,因为我们需要它至少是 10 亿,这样才能检测 10 亿个点。它是质数p-1 是 1000 的偶数倍。+ c5 e# X) ~9 r6 d7 i, Q! M: M% o
幂 x^1000 的像大小为 1,000,006 ——也就是说,这个幂只有 1,000,006 个可能的结果。这意味着“对角线”(x, x^1000) 现在变成了一个被包着(with a wraparound)的对角线;因为 x^1000 只可以取 1,000,006 个可能值,所以我们仅需要 1,000,006 行。故而,g(x, x^1000) 的所有取值现在只有 ~10^15 个元素。这表明,我们可以更进一步地:让证明者仅提交在一个单列上 g 的值。关键技巧在于,原始数据本身已经包含了 1000 个点,而这些点在给定的任意行上,所以我们可以简单采样这些点,推导出它们所在的度小于 1000 的多项式,然后检查列上相关的点在同一个多项式上。再接着检查列本身是一个小于 1000 的多项式。虽然验证者复杂度仍然是亚线性的,但是证明者复杂度已经降到了 10^9,并与查询次数成线性关系(尽管在实践中由于多项式求值的开销,仍是超线性的)。二谈效率虽然证明者复杂度现在已经无法再低了,但是我们仍然可以进一步地降低验证者复杂度,即从二次降至对数。我们的方法是让算法递归。从上面谈到的协议开始,但是并非试图将一个多项式嵌入到一个 x 和 y 度相等的二维多项式中,我们将多项式嵌入到一个二维多项式中,该二维多项式的度 x 下界是一个小的常量值。简单来说,我们甚至可以说就是 2 。也就是说,我们表示 f(x) = g(x, x^2),所以行检验仅需每个采样行的 3 个点(2 个来自对角线,还有 1 个来自列)。如果原始多项式的度小于 n,那么行的度小于 2(也就是说,这些行是直线),列的度小于 n/2。因此,我们现在得到的是一个线性时间过程,它将证明一个度小于 n 的近似多项式问题转变为证明度小于 n/2 的问题。进一步地,需要提交的点数,和证明者的计算复杂度,每次会减少 1/2(Eli BenSasson 喜欢将 FRI 的这一点与$ D3 p5 c8 e; c3 g& A: ?
[color=]fast fourier transforms
+ R$ |6 k7 T  t8 b) u9 m9 d相比较,与 FFT 不同的关键在于,每一步递归都只进入一个新的子问题,而不是将问题一分为二
, B( n+ {* }9 D3 e" U)。因此,我们可以简单地继续使用在上一轮协议所创建的列上的协议,直到列变得足够小,小到我们可以简单地直接检查。整体复杂度大概是 n + n/2 + n/4 + … ~= 2n.实际上,协议将需要被重复多次,因为仍有极大的可能,攻击者会在协议的某轮作弊。但是,只要证明不是太大,验证复杂度在量级上仍然是对数级,尽管它会上升到 log^2(n) ,如果你把 Merkle 证明的大小也算进去的话。“真正”的 FRI 协议也有一些其他的修改。比如,它使用一个二分的
4 ~9 A' h/ v+ t, r' VGalois 域
/ H0 f- d# ]! f# e( e(另一种奇怪的有限域。本质上,与我在
2 a) d; Q" P- ?9 J  h& q这里
: j! `0 G: U8 E) X  G0 f1 \ 讨论的第 12 度扩展域是同样的东西,不过素数模是 2
' P, H7 a6 u* ^/ b)。行所使用的指数通常是 4 而不是 2。这些修改提升了效率,并使系统更加友好,在上面更易构建 STARKs。但是,对于理解算法的工作原理,这些修改并非十分必要。如果你真的想要理解算法的话,利用这里所述的基于模块化数学的 FRI,虽然简单了一点,但是应付 STARKs 绝对是够了。可靠性我必须要提醒 计算可靠性(calculating soundness) ——也就是,无论概率有多低,对于给定次数的检查,一个经过优化后的假证明,仍可能会通过测试。——这依旧是这个领域中的“危险”地带。可以简单测试一下,取 1,000,000 + k 个点,有一个简单的下界:如果一个给定的数据集有这样一个属性,对于任意多项式,数据集中至少有 p% 的点没有在多项式上,那么在该数据集通过测试的概率将至多是(1-p)^k。但是,即使下界很低——比如,不可能同时有超过 50% 的点接近两个低次多项式,并且你首先选择的点会是上面最多的点的概率相当低。对于一个成熟的 FRI 来说,仍会涉及各种特定类型攻击的复杂度。7 p" X. H3 v# k: Q2 ^
[color=]这里4 i, t1 y6 |; m* I! |4 z5 H5 U. r
是 Ben-Sasson 等人最近的一篇文章,里面在完整的 STARK fang’an背景下,介绍了 FRI 的可靠性属性。总的来说,“好消息”是,为了在 STARK 上通过 D(x) * Z(x) = C(P(x)) 检查,一个无效方案的 D(x) 将需要是某种意义上的“最坏情况” – 他们需要最大化地远离任意有效的多项式。这表明,我们不需要检查那么近的距离。虽然有已证明的下界,但是这些界限表明一个真正的 STARK 在大小上需要 ~1-3 MB;一个属于推测尚未被证明的更严格界限,减少所需检测次数的 1/4。​第三部分,将讨论构建 STARKs 的最后一个主要的挑战:如何构建约束检查多项式(constraint checking polynomial),才能够证明任意的计算语句,而不仅仅是几个斐波那契数。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

伟大的旭旭yeah 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    1