您现在的位置: ag8亚洲国际 > 网络安全 >
如许的一个还原函数不克不及被看编译器:编译
作者:   ag8亚洲国际   

  留意,正在这里当 2n 小于 m 时,选择元组 a 和 b 仍然是有很大的度的。这就意味着 QSP 只对特定大小的输入是有价值的——这个问题能够通过利用非平均复杂度来处理,非平均复杂度这个话题今天我们不会深切的,我们只需要晓得当输入值很小时,我们的暗码学也能优良运转。

  Non-interactive:没有或者只要很少很少的交互。对于 zkSNARKs 来说就是正在证明者向验证者发送一条消息之后的过程。此外,SNARKs 还常常具有叫做『公共验证者』的属性,万豪娱乐平台,它的意义是正在没有再次交互的环境下任何人都能够验证,这对于区块链来说是至关主要的。

  像 zCash 这种现存的 zkSNARK 系统对每一个使命都利用的是同样的问题,circuit 计较。正在 zCash 中,就是买卖验证。正在 Ethereum 上,zkSNARKs 将不会只单单做一个计较问题,而是让所有的人都可以或许正在不发布一个新的区块链的环境下建立他们本人的 zkSNARK 系统。每一个添加到 Ethereum 上的 zkSNARK 系统都需要进行一个新的私密的可托赖的预备阶段(一些能够复用,一些不克不及),好比生成一个新的 CRS。像为一个『通用虚拟机』添加 zkSNARK 系统将会变的可能。如许的话当你利用一个新的实例时,你就不需要从头设置了,由于你将不再需要为 Ethereum 上新的智能合约发布一个新的区块链。

  所有 NP 问题 L 都有一个正在多项式时间可计较的『还原函数(reduction function)』f:

  为了弄大白如许一个还原的方式,让我们先考虑评估多项式的问题。起首,让我们定义一个由整数常量,变量,加法,减法,乘法和(准确婚配的)括号形成的多项式(雷同于布尔函数)。现正在让我们考虑下面的问题:

  正在 Ethereum 上启用 zkSNARKs 有良多种体例。所有的体例都可认为配对函数和椭圆曲线操做(其他需要的操做都很简单)减小实正在的损耗,因而我们也要减小这些操做耗损的 gas。可是实现起来难度比力大。我们现正在曾经正在对 EVM 添加一些新的功能和了,例如更好的支撑及时编译以及正在现存实现下最小改动的注释器的实现。当然也疑惑除间接用 eWASM 来替代 EVM。

  。凡是来讲,若是你能够互换两个操做的挨次而不影响计较成果,那么我们就说这两个操做是同态的。正在同态加密中,这就是你能够对加密数据进行计较的一个属性。完全同态加密是存正在的,可是现正在还没有使用到现实中,它可以或许对任何基于加密数据的法式完成计较。正在这里对于 RSA 来说,我们只谈论 group multiplication。更精确的说就是:

  我们曾经对零学问这个概念有了必然的领会了,现正在让我们着沉看一下 zkSNARKs 的另一个次要的特征:简明性(succinctness)。之后你会看到这个简明性是 zkSNARKs 更牛逼的部门,由于零学问部门的实现就是由于这一特定编码,而这个特定的编码是一个无限形式的同态编码。

  为了领会 zkSNARKs 能用于哪些问题和计较,我们不得不基于复杂的理论定义一些说法。若是你不晓得什么是 “witness” 的话,那么即便『读』完零学问证明你也不会晓得它是什么,而且你也不会领会到为什么 zkSNARKs 只合用于特定的多项式问题,若是实是如许的话,那么你就能够跳过本节了。

  最初一个等式用来查验能否利用了准确的多项式(这一部门还没有讲到,不外其他的例子会说到它)。要留意的是,我们所有的加密值,证明者只需要晓得 CRS 就能够全数推算出来。

  接下来就是基于论文GGPR12(这里面链接的手艺演讲比原文的干货更多)来谈了,这篇论文的做者发觉了一个叫做 Quadratic Span Programs(QSP)的问题,这个问题完全就是为 zkSNARKs 预备的。一个 Quadratic Span Program 是由一组多项式和寻找给定多项式倍数的线性组合使命形成。此外,输入字符串的每个零丁的 bit 都了你可以或许利用的多项式。细致来说(凡是来讲 GSPs 不是那么严酷,可是我们就是需要这种强的版本,由于后面我们会用到)就是:

  这里的使命很粗拙,就是给多项式乘以一个因子并把它们加起来(也叫做『线性组合』)使得它们的总和是 t 的倍数。对于每一个二进制输入字符串 u 来说,函数 f 了能够被利用的多项式,或者更严酷的讲就是它们必需是线性组合的因子。正式的暗示就是:

  of Knowledge:对于证明者来说正在不晓得一个叫做(witness)(好比一个哈希函数的原象或者一个确定 Merkle-tree 节点的径)的环境下,构制出一组参数和证明是不成能的。

  起首,我们函数只能输出 0 和 1,并称如许的函数为问题(problems)。由于你能够零丁的查询一个长长的成果的每一位(bit),所以这不是一个实正的,可是如许能够让变的简单一点。现正在我们想权衡处理一个给定的问题(计较函数)到底有多『难』。对于一个数学函数 f 的特定机械的实现 M,给定一个输入 x,我们能够计较出这个函数 f 需要的步数 -- 这就叫做 x 正在 M 上的施行时间,这里的『步数』其实不太主要。由于法式对于更大的输入往往会需要更多的步数,而这个施行时间则是用输入值的大小或者说长度(bit 的数量)来权衡。这就是例如『

  就像你正在这些末节中看到的一样,我们的证明由一个群(就是一个椭圆曲线)的 7 个元素构成。并且验证者的工做就是查验一些配对函数的等式能否成立以及计较

  起首让我们先来看一种简单的环境,即一个多项式正在私密点上的加密估值,而不是完整的 QSP 问题。

  )。并且 RSA 的平安性是基于假设:n 不克不及被等闲无效的因式分化,d 不克不及通过 e 计较获得(若是我们晓得 p 和 q 的话,就能够等闲获得我们想要的值)。

  虽然 Ethereum 利用了一个图灵完整的虚拟机,可是当前正在 Ethereum 上实现一个 zkSNARK 仍是不成能的。从概念上讲,验证者的使命似乎很简单,可是配对函数是实的很难计较,并且正在单个区块中还会耗损更多的 gas。椭圆曲线的乘法相对来讲曾经很是复杂了,而配对函数将这个复杂度又添加了一个级别。

  让我们再回到 SAT。这个看起来简单的问题有个风趣的特征就是它并不只是 NP 问题,仍是 NP 完全问题。『完全』这个词正在这里和『图灵完整』是一个意义。这意味着它是 NP 中最难的问题,可是更主要的是 NP 完全的定义——任何 NP 问题的输入都能够用下面的方式转换成一个同样的 SAT 的输入:

  若是你将 NP 问题定义为长度为 0 的 witness strings,那么你会发觉这就是 P 问题。因而 每个 P 问题其实都是 NP 问题。正在复杂性理论研究中有一个次要的使命就是挖掘出这两类问题的分歧 -- 即一个不属于 P 的 NP 问题。正在这里似乎是很明显的,可是若是你能够再一般环境下证明它,那么你能够获得 1 百万美元。额外说一句,若是你能够反向证明,即 P 和 NP 是等价的,也能够获得那笔金。而数字货泉范畴有朝一日可以或许证明的概率很大。我这么说的缘由是,比起一个哈希函数的碰撞或者按照地址找到私钥来说,找到一个工为难题处理法子的证明明显更容易一点。这些都是 NP 问题,由于你刚曾经证了然 P = NP,那么对于这些 NP 问题来说就必然存正在一个多项式时间的法式。可是本文就不会商了,虽然大部门研究者都认为 P 问题和 NP 问题并不是等价的。

  把需要验证的法式编写成一个二次的多项式方程:t(x) h(x) = w(x) v(x),当且仅当法式的计较成果准确时这个等式才成立。证明者需要验证者这个等式成立。

  证明者通过乘以一个数来替代 E(t(s)), E(h(s)), E(w(s)), E(v(s)) 的值,如许验证者就能够正在不晓得实正在的编码值的环境下验证他们准确的布局了。

  验证者会选择一个私密评估点 s 来将多项式乘法和验证多项式函数相等的问题简化成简单乘法和验证等式 t(s)h(s) = w(s)v(s) 的问题。如许做不单能够减小证明的大小,还能够大量地削减验证所需的时间。

  虽然 k 的指数对于一些问题来说确实很是大,可是现实上对于那些制的,k 不大于 4 的 P 问题仍然被认为是能够『处理的』的问题。要确认一笔比特币的买卖就是一个 P 问题,由于颠末评估它需要一个多项式时间(而且只能输出 0 和 1)。简单的说就是,若是你只是计较一些值而不去『搜刮』,那么这个问题就是 P 问题。可是若是你不得不搜刮一些工具,那么你就会进入到另一个叫做 NP 问题的类别中。

  有些人可能会假设将 r((f ∧ g)) 定义为 r(f) + r(g),可是那样的话多项式的成果就会超出调集 {0, 1} 了。

  现正在我们就能够建立出一个从 SAT 到 PolyZero 的还原方式了,同时这也申明了 PolyZero 也是一个 NP 完全问题(验证它能否属于 NP 就当是留给你们的小啦)。

  由于验证计较是 Ethereum 区块链的焦点,所以 zkSNARKs 和 Ethereum 关系慎密相连。有了 zkSNARKs,我们不单能够完成任何人都可的私密的计较,并且还能够高效的完成。

  当然,这些都只是根本的部门,是为了让读者更地的理解 zkSNARKs 的素质,接下来将起头细致这些学问点。

  第二项则能够通过强制所有的 Ethereum 客户端施行一个确定的配对函数和确定的椭圆曲线乘法的叫做预编译合约的工具来实现。如许做的益处就是实现起来既简单又快速。而错误谬误呢则是如许做我们就会固定正在一个确定的的配对函数和一个确定的椭圆曲线上。所有 Ethereum 上新的客户端都不得不再实现一遍这个预编译合约。所有,若是有什么新的进展,或者有人能够找到更好的 zkSNARKs 的方式,更好的配对函数,更好的椭圆曲线,又或者发觉了椭圆曲线,配对函数和 zkSNARK 的一些错误谬误,那么我们就会添加到新的预编译合约中。

  如许的一个还原函数不克不及被当作一个编译器:编译器是能够将一些编程言语写的源代码等价的转换成另一种编程言语的机械,也就是具有语义行为的机械言语。由于 SAT 是 NP 完全的,所以如许一个还原对于任何可能的 NP 问题都是存正在的,好比给定一个合适的 block hash,验证一笔比特币买卖能否。这里还能够将一笔买卖转换成一个布尔函数的还原函数,因而当且仅当这个买卖是的时候这个布尔函数就是可满脚的。

  如许一个跟从输入大小的线性使命。最次要的是,正在这个验证过程中,既不需要 witness 字符串的大小,又不需要计较工做量来验证 QSP(没有 SNARKs)。这就意味着 SNARKs 的校验是个很复杂的问题,而简单的问题往往都是一样的。形成这个成果的次要缘由则是,由于我们只正在一个零丁的点查验了多项式的分歧性,而不是全数的点。多项式能够变的很是很是复杂,可是一个点一直是一个点。而独一能影响到验证成果的参数就是平安性的品级(好比群的大小)和输入值的最大尺寸。

  SNARKs 是succinct non-interactive arguments of knowledge的缩写。一般都通用设置之所以叫做交互式和谈,是由于这里有一个证明者和一个验证者,证明者想要通过互换消息的体例让验证者相信一个表达式(好比 f(x) = y)。一般来说,没有证明者能够让验证者相信一个错误的表达式(靠得住性),并且对于证明者来说必然存正在一个确定的策略让验证者相信赖何实正在的表达式(完整性)。SNARKs 各个部门的的意义如下:

  zkSNARKs(zero-knowledge succint non-interactive arguments of knowledge)的成功实现让我们印象深刻,由于你能够正在不施行,以至正在不晓得施行具体内容的环境下确定某个计较的成果能否准确——而你独一晓得的消息就是它准确地完成了。可是倒霉的是,大大都关于 zkSNARKs 的注释都浮于概况,并暗示只要最伶俐的人才能懂得它的工做道理。现实上,zkSNARKs 能够总结为 4 个简单的手艺,本篇博客将会一一注释这些手艺。任何懂得 RSA 加密系统工做道理的人城市对当前利用的 zkSNARKs 有一个更好的理解和认识。

  弥补(来自白教员):同胚和同态正在数学上不是一个意义。同胚指持续变形下的不变性,同态指映照下代数运算关系的连结性。

  正在上一部门中,我们看到了 NP 问题的计较是若何被彼此化简的,特别是那些 NP 完全问题,那些 NP 完全问题根基上又都再次构成了其他的 NP 问题——包罗买卖验证问题。那么对我们来说找到一个对所有 NP 问题都通用的 zkSNARKs 就变的很容易了:我们只需要选择适合的 NP 完全问题。所以若是我们想展现若何利用 zkSNARKs 来验证买卖的话,那么展现若何处置这个确定的 NP 完全问题就是一个无效的方式,而且比从理论上注释更容易让人接管。

  这里我们不会会商若何将通用计较和线问题简化成 QSP 问题,由于这对于我们领会根基概念没有任何帮帮,我们只需要晓得 QSP 是 NP 完全(或者说比一些非平均分布的像 NP/poly 问题更完全)的就好了。现实上,这个简化是一个『工程』部门——必必要利用一种很伶俐的方式才能让 QSP 问题尽可能的小而且有一些其他的优秀特征。

  从这个例子中你能够看出还原函数只定义了若何转换输入,可是当你细心看的时候(或者阅读完若何完成一个可用的还原之后)你就会晓得若何将一个可用 witness 和 输入一路转换。正在我们的例子中,我们只定义了若何将函数转换为多项式,可是不晓得若何将我们注释的转换成满脚赋值的 witness。这个 witness 正在统一时间转换对于买卖来说不是需要的,可是凡是城市包含。而这对于 zkSNARKs 来说是至关主要的,由于对于证明者来说他独一的使命就是让验证者相信有如许一个 witness 存正在,而且还不会任何相关 witness 的消息。

  这里的这个示例告诉我们验证者并不需要求出完整的多项式来证明这一点,仅仅利用配对函数就能够了。下一步我们就要添加零学问的部门了,如许验证者就不克不及建立任何干于 f(s) 值了,以至连 E(f(s)) 这种加密消息也不可。

  我们利用一个具有一些同态属性的(并不是完全同态的,至多正在现实利用中有一些不是同态的)编码 / 加密函数 E。这个函数答应证明者正在不晓得 s 的环境下计较 E(t(s)), E(h(s)), E(w(s)), E(v(s)),她只晓得 E(s) 和一些其他有用的加密消息。

  好的,现正在我们总算晓得了一点关于正在验证者不晓得阿谁值的环境下,证明者是若何正在一个加密的私密点计较出多项式加密值的。接下来让我们把这些使用到 QSP 问题中吧。

  几乎所有的 NP 类问题都是 zkSNARKs,今天正在现实中利用的 zkSNARKs 正在凡是意义上讲都属于 NP 问题。而我们目前还不晓得的是,有没有不属于 NP 问题的 zkSNARKs 存正在。

  Arguments:验证者只对计较能力无限的证明者无效。具有脚够计较能力的证明者能够创制出关于错误表达式的(留意,只需具有脚够的计较能力,任何公钥加密系统都能够被破解)证明和参数。这也叫做『计较靠得住性』,相对的还有『完满靠得住性』。

  这个同态的特征曾经有一些乘法的零学问证了然:证明者晓得一些私密的数字 x 和 y,并计较出了它们的乘积,可是只给验证者发送加密的版本:a = E(x), b = E(y) 以及 c = E(x y)。验证者查验等式 (a b) % n ≡ c % n 能否成立,此时验证者只晓得加密版的乘积以及乘积能否被准确的计较,可是她不晓得两个乘数和实正的乘积。若是你用加法来替代乘法,那就是一个次要操做为添加余额的区块链标的目的了。

  若是 f 是一个变量都来自于调集 {0, 1} 的多项式,而且此中包含一个零项,那么 PolyZero(f) := 1

  现正在让我们快速回忆一下 RSA 是若何工做的,先不管那些琐碎的细节。想想看,我们经常用一个数字对一些数字取模,而并不是所有的整数。这里的等式 “a + b ≡ c (mod n)” 等价于 “(a + b) % n = c % n”。“(mod n)” 这个部门并不是使用正在 “c” 的,而是使用正在 “≡” 以及不异等式所以其他的 “≡” 。虽然如许很是难以阅读,可是我尽量罕用他们。接着让我们回到 RSA:

  现正在让我们来细致的描述一下 QSP 上的 zkSNARK。它正在起头设置阶段会施行每一个零丁的 QSP。正在 zCash 中,买卖验证者的线是固定的,因而 QSP 的多项式也是固定的,这个 QSP 正在设置阶段只答应被施行一次,然后正在所有的只要输入 u 分歧的买卖上复用。这个起头的设置会生成一个公共参考串(common reference string,CRS),验证者选择一个随机且私密的域元素,并正在这个点加密多项式的值。验证者利用一些特定的加密方式 E 并正在 CRS 中

  关于零学问的部门相对正式的定义(仍然缺乏一些细节)就是:存正在一个模仿器,它能够生成一些设置字段,可是却不晓得私密的 witness,它还能够和验证者交互 -- 可是外部的察看者却不克不及分辩出哪个取验证者进行的交互,哪个是取证明者进行的交互。

  NP 问题是 L(含有多项式时间的法式 V)的一类问题, 这个法式 V 能够正在给定一个多项式标准的叫做因子的 witness 的环境下验证这个因子。更正式的说就是:当且仅当一些多项式标准的字符串 w(被称做witness)满脚 V(x, w) = 1 时,L(x) = 1 成立。

  减小第二个参数是可行的,将输入值的一部门挪动到 witness 中:我们不验证函数 f(u, w),u 是输入,w 是 witness,而是做一次 hash,然后验证:

  如许就意味着我们能够用一个 hash 来代表输入 h(u) 了(如许就会变的更短),除了验证 f(x, w),我们还需要验证某个值 x 的 hash 等于 H(u)(如许的话,那 x 极有可能就等于 u 了)。如许就将原始输入 u 挪动到 witness 字符串中了,如许虽然会增大 witness 的大小,可是输入值的大小就减小为一个了。


上一篇:他们就是要搞“平安”
下一篇:约时报就有报道
】 【打印】 【关闭

版权所有@ < 贵州ag8亚洲国际信息技术产业联盟 >
邮箱:gzitia@163.com
联系地址:贵州省贵阳市云岩区延安中路丰产支路1号振华科技大厦23楼F座