你需要什么:
- 计算机科学背景
- 以太坊的基础
- 微积分的基础知识(约束优化)
你会得到什么:
- 零知识SNARK的基础
- 默克尔树的基础知识
- 借助SNARK,以太坊如何扩展到每秒数千笔交易
SNARK允许证明者向验证者证明她/他具有共享/已知输入X的问题F的解决方案W,而无需透露W。
找到问题的解决方案可能需要大量的计算能力和内存。
因此,验证者基本上可以100%确认验证者已正常运行(并找到了解决方案), 既不自己做自己的工作来检查解决方案,也不知道解决方案。 这是魔法!
该过程包括3个步骤:
- 设置 —为SNARK准备了问题F(需要用二次算术程序表示,见下文)。 根据问题的复杂性(→输入和约束的数量→约束满足问题矩阵的维数),此过程的内存和计算量非常大。 进行安装的玩家(可能是验证者本身)必须得到各方的信任,因为在下一阶段将使用安装程序的输出。 设置通常使用 库斯纳克C ++库,它是zkSNARK的最流行的实现。
- 验算 —证明者,使用共享输入X(也许他/他花费了大量的CPU和内存来找到它),为问题F拥有解决方案W,他使用 库斯纳克 和的输出 设置 阶段创建证明𝚷。 此过程肯定是高内存和计算密集型的(取决于问题的复杂性,如上所述)。 相反,输出的大小(即证明instead)简洁而恒定,与问题的复杂性无关。 证明者需要信任谁完成了设置阶段,因为她/他使用了它的输出…
- 验证中 —验证器—提供设置阶段的输出作为输入,共享输入X和证明𝚷 –检查证明。 如果验证成功,则证明者设法向验证者证明她/她已找到问题F的解决方案W…,而无需透露W! 令人高兴的是,不仅证明简洁明了,而且长度始终相同。.,验证过程非常快捷,并且根本不占用存储/计算资源。 与前两个阶段不同……使用智能手机可以在几毫秒内轻松完成验证!
总结一下(资源):
怎么会这样 好吧,这是梅林魔术! 如果您想获得数学依据, 从这里开始.
如何将我的软件转换为二次算术程序?
如上所述,设置阶段的问题F必须是二次算术程序。 游戏规则很严格:
- 您的软件输入应为数字。 将您的东西(数组,字符串等)转换为数字。 没什么。
- “方程的二次约束系统”表示:
其中x是输入的n维向量,m是约束的数量(即系统方程式的数量),C是n×n系数矩阵Matrix,q是n维系数向量。 如果您不喜欢矩阵和向量,则这是n = 3和m = 2的情况(3个输入,2个约束):
- 该实现是一个算术电路,这意味着结果是 问题解决了 (系统已求解,即所有多项式均等于0)或 问题未解决 (所有其他情况)。 换句话说:“这些输入/不是该问题的解决方案之一”。
- C 2393,C 5647,...,C XNUMX,q XNUMX,q XNUMX,...,q XNUMX系数是系统的约束。 这基本上就是定义您的软件的原因。 更改它们……您将获得另一个软件! 回到SNARK的工作原理:C XNUMX,C XNUMX,…,C XNUMX,q XNUMX,q XNUMX,…,q XNUMX是设置阶段的输入。 因此,设置阶段的输出(您需要进行证明和验证)与CXNUMX,CXNUMX,…,CXNUMX,qXNUMX,qXNUMX,…,q q严格相关,并且仅适用于该问题。 如果您更改它们,那么您正在定义另一个软件/问题,您需要重新运行安装阶段! x₁,x²,…,x𝗇是变量(即,您必须猜测才能得到系统的解)。 因此,当我们说“亲爱的证明人,请问您能找到带有共享/公共输入X的问题F的秘密解决方案W”时,我们的意思是例如“亲爱的证明者,您能找到解决系统的x₁,x²,…,x𝗇值吗?例如,x₇= XNUMX,x₅XNUMX₆= XNUMX?” 您可以对所有x𝗇进行所需的操作,但x₇和x₅XNUMX₅除外,它们受共享/公共输入的约束。
这是艰苦的生活,但您可以生存……如果您需要循环,可以展开它们,重复多次相同的操作。 或者,例如,如果需要x₁⁴x₁⁴,则定义一个新输入x₃=x₁⁴x⁵,并在约束中使用x₃。 这都是关于添加变量和约束的…… 即使是非常简单的软件,也很容易达到数亿或数十亿的输入和约束!
想知道更多? 读 此处。 还要看看这个基本 代码到r1cs.py 来自以太坊/研究。
什么是默克尔树?
哈希函数是将任意大小的输入映射到固定大小的输出的规则。 我们可以发明一个非常无用的哈希函数“将前两个字母与最后两个字母连接起来”,该函数将“伍迪·艾伦”转换为“沃恩”,并将“保罗·麦卡特尼”转换为“佩伊”。
Merkle树是一种数据结构,其中每个父级都是其两个儿子的哈希。 在顶部找到根,它是第1级两个儿子的哈希。在底部,每个叶子都是外部输入的哈希。
使用我们的虚构的“伍迪·艾伦”→“沃恩”哈希函数:
当叶子发生更改时,修改将传播到根。 如果ANTHONY更改,则ANNY(叶),CENY和CECO(根)也会更改。 不论哪个叶子改变,根也改变。
您不需要整个树来重新计算根。 在我们的示例中,如果ANTHONY发生更改并且您同时知道JACO和CECILY,则即使您完全忽略JAMES,MARCO,JAES和MACO,也可以轻松地重新计算Root。 对于大树,这可以节省大量时间!
还等什么?
Merkle树非常适合数据完整性检查。 通常:您知道哪个是有效的根,然后检查接收到的数据是否与该根匹配。 例如:一个无法向您提供地球上所有人的完整数据集(没有时间,没有带宽或者她/他根本没有数据)的受信任方只会为您提供根(例如“ CECO”)。 后记:成千上万的不信任方收到数百万个关于叶子的名字。 好吧,由于您拥有正确的根目录,因此您可以检查可以依靠的人,谁在为您提供虚假数据……
默克尔树也是您生活的一部分! 当您下载3GB的Torrent文件时,您的文件会分成数百万个小块。 每个块的哈希存储在叶中。 由于您知道哪个是树的有效根,因此每次有人收到文件块时,您都可以检查它是否正确。 如果不是,您可以向其他人询问相同的块。
即使尚未下载整棵树/所有叶子,也可以执行此操作:如果您知道根是CECO并且您信任JACO…当您收到ANTHONY块时,即使您尚未下载,也可以对其进行验证但还有MARCO和JAMES。
为什么Merkle树在分布式分类帐技术中有用的原因很简单:您仅使用共识协议(缓慢,昂贵)来达成关于根的共识。 这样,通过与Root进行完整性检查,网络中不受信任的节点就可以高效且直接地共享数据……并且可以安然入睡。
当上帝要求以太坊在安全性,可扩展性和分散性中选择两个超级大国时,以太坊牺牲了可扩展性。 实际上,“每秒事务数”没有严格的上限:该上限涉及每个块的用气量,也就是简化了我在每个块中可以执行的操作量。 此限制为2万汽油。 这可能意味着很多“微小”的事务(没有附加到事务的数据,没有对该数据执行的操作)或很少的大事务。 取决于提交交易的以太坊节点和以太坊的矿工,后者在区块中包含支付更多费用的交易。
挖了一块 每周 约15秒。 这意味着每分钟约有32万个汽油,如果我们希望以太坊的dapp成为主流,这绝对是不够的。
顺便说一句:停止以太坊和Visa之间的繁琐比较。 集中式系统将 时刻 比以太坊更快……设计! 他们做不同的事情,您在不同情况下需要它们。 如果您不需要权力下放和不信任的环境……当然,您应该选择Visa。 简而言之: 搅拌器旋转速度比洗衣机快的事实并不意味着您将在搅拌器中清洁裤子!
让我们把难题放在一起! 想象一下,借助SNARK,您可以在一个大交易中“压缩”许多小交易。 如果此大笔交易所花费的天然气少于小笔交易所花费的天然气之和,则意味着您可以节省天然气。
节省气体意味着:
- 用户在整体交易上的支出减少→这将推动整个生态系统
- 能够将更多的东西放到一块→以太坊的旋转速度比搅拌机快!
我们如何运作?
有用户,一个汇总交易的中继器(或多个中继器)和一个智能合约。
- 愿意玩此游戏的用户将其以太币(或代币)发送到经过公共审核的智能合约。 对于每个新玩家,都会在Merkle树中创建新叶子。 该叶子包含有关以太坊所有者(他/他的地址,也是公钥),以太坊和随机数(该帐户的交易计数器,添加该叶子时为0)的信息。
- 当A想要将以太币发送给B时(他们都需要在智能合约中拥有一个叶子/账户),A打包了一笔交易,其中包括交易的地址。 止帐户 至 帐户 教廷大使 来自“帐户”的 量 要转移的以太币和 签名 交易的费用(显然是用“发件人”帐户的私钥签名的)。 然后,他/他将打包的事务发送给中继器。
- 中继器汇总给定时间窗口(例如一小时)内收到的所有交易,用新余额的金额更新Merkle树,并创建SNARK证明,以证明所有签名和新Merkle树的根均有效。 中继器最终将新状态和证明发送到智能合约。
- 智能合约会验证链上的证明。 如果有效,它将New状态的Merkle树根保存在合同的内部存储器中。
基本上,默克尔树根表示所有帐户的整个状态。 除非您能证明签名的有效性导致签名的交易导致您提交的新根汇总了“新”状态,否则您就不能更改它(=窃取金钱)。
简而言之:用户可以像Coinbase上那样快速而几乎免费地进行交易,而无需信任中继器,而中继器却无能为力,这与Coinbase一样,没有您的签名。
这是一个非保管侧链,其状态由Merkle树根概括。
让我们将上面了解的有关SNARK的知识与我们刚刚讨论的有关缩放的知识联系起来。 有不同的方法可以做到这一点。 我将比较两种食谱:Vitalik的 版本 和BarryWhiteHat的 版本.
设置是通过...完成的
启动项目的人,他还创建智能合约。 可审核的越多越好。您应该信任她/他……这是一个 受信任的设置!
智能合约可以节省……
2个Merkle根(bytes32值):第一棵树包含帐户的地址(公共签名),第二棵树包含帐户的余额和随机数
证明由…完成
中继器
中继器发送到智能合约…
- 新状态的2个Merkle根(地址树和天平+随机数树)
- 没有签名的交易清单。 “每笔交易每字节花费68汽油。 因此,对于常规转移,我们可以预期边际成本为68 * 3(从)+ 68 * 3(至)+ 68 * 1(费用)+ 68 * 4 + 4 * 2(金额)+ 68 * 2 (立即)或892汽油”
证明过程的已知输入是…
- 2老州默克尔的根源
- 2个新州Merkle的根源
- 交易清单
证明过程证明……
特定
- 2个旧州Merkle根(已存储在合同中)
- 2个新状态Merkle根(在总事务中发送)
- 交易清单(在总交易中发送)
…中继器具有有效的签名,可以从那些具有两个旧根的状态迁移到具有两个新根的状态。
验证是通过…
智能合约(根据您的喜好,以坚固性,编码方式编码!)
验证过程的已知输入是…
显然,同一PROVING的过程知道输入内容!
限制可扩展性
每笔交易总计使用650万天然气进行SNARK验证(固定成本)加900瓦斯的 边际成本 每笔交易(发送数据的费用!)。 因此,使用整个块,中继器最多可以聚合:
意思是 每秒约544 tx
巴里·怀特(BarryWhiteHat) 版本
设置是通过...完成的
启动项目的人。
智能合约可以节省……
1 Merkle根与当前状态。 每个叶子都是帐户的哈希状态。
要 创建信息图 一个帐户?
状态= AccountState(公钥,余额,随机数)
state.index = self._tree.append(state.hash())
证明由…完成
中继器
中继器发送到智能合约…
- 证明𝚷
- 新州默克尔根
- 证明𝚷
证明过程的已知输入是…
- 旧州默克尔根
- 新州默克尔根
证明过程证明……
特定
- 老默克尔根(已存储在合同中)
- 新Merkle根(总事务中的前哨)
…中继器具有带有有效签名的事务列表,可从具有旧根的状态转移到具有新根的状态
验证是通过…
智能合约(根据您的喜好,以坚固性,编码方式编码!)
验证过程的已知输入是…
显然,同一PROVING的过程知道输入内容!
限制可扩展性
中继器没有将交易数据发送到智能合约(这很昂贵),因此限制实际上是用于验证SNARK证明的天然气量。
提到霍华德·吴的 工作 关于在分布式系统barryWhiteHat上运行SNARK的PROVING阶段 乐观地 指出有可能以庞大的SNARK(16666亿个约束!)确认1个交易。
barryWhiteHat也 想 可以用500k的气体在链上验证证明,,这意味着您可以在每个区块中放置16个SNARK(8万/ 500k),即 每秒约1.07 SNARK…意味着每秒约17,832 tx (16,666 * 1.07)。
超越无限
- 所有闪闪发光的东西都不是黄金/1。在证明阶段需要的计算能力和内存实在令人震惊。 特别是在barryWhiteHat的版本中,部分复杂性已从链下转移。 巴里写道 “在具有7 GB内存和20 GB交换空间的笔记本电脑上,它很难每秒聚合20个事务”。 好吧,如果目标是每秒17,832 tx…大声笑。 这引入了非平凡的并行计算挑战。 但是,如果每笔交易的平均$费用比普通的no-SNARKs选项便宜得多,那么这款游戏就值得了。
- 所有闪闪发光的不是黄金/2。有一个相关的数据可用性问题! 由于合同中仅保存树的根,因此您必须确保树的整个版本(或相同的是整个交易历史记录)始终可用。 如果没有可用数据,则中继器即使具有有效的已签名事务也无法执行任何操作,因为她/他无法证明旧状态→事务→新状态。
- 为了使中继器不受信任,并使合同中的以太币在外部具有相同的价值(流动性问题)……用户应该可以在需要时从智能合约中提取资金,而不必依赖(特定的)中继器。 怎么样? 这不在此101帖子的范围内,但是您可以在随附的链接中阅读有关此内容的信息。
- 想更多地了解如何使用Merkle树处理当前状态(地址,余额和现时值)吗? 添加叶子,更新叶子等? 查看 这个图书馆 (测试文件 此处)使用此基础 模块。 谢谢HarryR!
- 想建立您的个人以太坊-SNARKs环境吗? 让我们从C ++(设置,验证,验证)开始脱链。 此处。 然后您可以使用Zokrates(以太坊(别忘了,只有验证是在链上完成的!)。回购是, 文档入门).
- 使用RSA累加器代替Merkle树怎么样? 谷歌 “ rsa累加器以太坊” 开始…
尽情享受您的购物之旅!
Twitter @marco_derossi
- 7
- 账号管理
- 所有类型
- 其中
- 可用性
- 基础
- 亿
- 例
- 更改
- 支票
- coinbase
- 计算
- 共识
- 合同
- 成本
- 电流
- 当前状态
- DApps
- data
- 数据集
- 权力下放
- 尺寸
- 分布式帐簿
- 分布式分类帐技术
- 环境
- 以太币
- 复仇
- EU
- EV
- 假
- 终于
- 姓氏:
- Free
- 功能
- 游戏
- 天然气
- GitHub上
- 给予
- 黄金
- 非常好
- 谷歌
- 大
- 指南
- 哈希
- 此处
- 高
- 历史
- 创新中心
- hr
- HTTPS
- 巨大
- 数百
- ia
- 指数
- 信息
- IP
- IT
- 工作
- 键
- 笔记本电脑
- 大
- 铅
- 莱杰
- Level
- LG
- 自学资料库
- 流动性
- 清单
- 主流
- 地图
- 中等
- 百万
- 矿工
- 钱
- 个月
- 最受欢迎的产品
- 移动
- 名称
- 网络
- 节点
- 数字
- 运营
- 秩序
- 其他名称
- 业主
- 员工
- 播放机
- 热门
- 功率
- 私立
- 私钥
- 曲目
- 项目
- 证明
- 证明
- 国家
- 公钥
- 概括
- RSA
- 定位、竞价/采购和分析/优化数字媒体采购,但算法只不过是解决问题的操作和规则。
- 运行
- 安全
- 保存
- 可扩展性
- 鳞片
- 缩放
- 科学
- 保安
- 集
- Share
- 共用的,
- 短
- 简易
- 尺寸
- 睡觉
- 智能
- 聪明的合同
- 智能手机
- So
- 软件
- 坚固
- 解决方案
- 解决
- 太空
- 花费
- 开始
- 开始
- 州/领地
- 州
- 成功
- 系统
- 产品
- 专业技术
- test
- 次
- 令牌
- 最佳
- 激流
- 交易
- 交易
- 信任
- 最新动态
- 用户
- 折扣值
- 企业验证
- 签证
- W
- WHO
- 话
- 工作
- 合作
- 价值
- X