区块链中文技术社区 - 零知识证明
type: channel
link: https://bcskill.com/index.php/tag/零知识证明/
items: ZKP（Zero-Knowledge Proofs）技术调研
items: zk-SNARKs 介绍（零知识证明概述以及如何将 zk-SNARK 集成到以太坊中）
items: 零知识证明：STARKs 与 SNARKs
items: 什么是 zk-SNARK？

ZKP（Zero-Knowledge Proofs）技术调研
type: item
date: 2021-08-25T12:26:00+08:00
description: 在之前《隐私/匿名币》中说过Zcash 首次运用 zk-SNARKs 零知识证明技术验证交易有效性，原来的计划是先把基于以太坊的侧链开发完成，再做ZKP（Zero-Knowledge Proofs）的技术跟进，以解决匿名交易以及增强TPS扩容方案（交易指纹上链，交易数据链下存储）。 今天先做一些技术调研和储备，方便后续技术评估时的一些技术方向的把控 技术相关 《什么是 zk-SNARK？》 《零知识证明：STARKs 与 SNARKs》 《zk-SNARKs 介绍（零知识证明概述以及如何将 zk-SNARK 集成到以太坊中）》 https://zokrates.github.io/ https://docs.ethhub.io/ethereum-roadmap/privacy/ https://starkware.co/ https://docs.ethhub.io/built-on-ethereum/infrastructure/aztec-protocol/ https://scrt.network/blog/introducing-secret-network https://ethresear.ch/t/zether-the-first-privacy-mechanism-designed-for-ethereum/5029 https://ethereum.stackexchange.com/questions/49781/can-zksnarks-be-implemented-on-the-ethereum-ecosystem https://github.com/starkware-libs/ https://hackmd.io/@zkteam/gnark https://docs.gnark.consensys.net/en/latest/ 开源代码 https://github.com/zkcrypto/bellman/ https://github.com/matter-labs/bellman https://github.com/zcash/librustzcash (Groth16) https://github.com/zcash/mpc https://github.com/scipr-lab/libsnark https://github.com/Zokrates/ZoKrates https://github.com/AztecProtocol https://github.com/arnaucube/go-snark-study https://github.com/vocdoni/go-snark https://github.com/ConsenSys/gnark (Groth16, PlonK) https://github.com/ConsenSys/gnark-crypto https://github.com/nikkolasg/playsnark （Groth16, PHGR13） https://github.com/ConsenSys/quorum

zk-SNARKs 介绍（零知识证明概述以及如何将 zk-SNARK 集成到以太坊中）
type: item
date: 2021-08-25T11:33:00+08:00
description: 在这篇文章中，我们旨在从实用的角度概述 zk-SNARK。我们会将实际的数学视为一个黑匣子，并尝试围绕如何使用它们建立一些直觉。我们还将给出最近在以太坊中集成 zk-SNARKs 的工作的简单应用。 零知识证明 零知识证明的目标是让验证者能够说服自己，证明者拥有秘密参数的知识，称为见证，满足某种关系，而不会将见证透露给验证者或其他任何人。 我们可以更具体地将其理解为有一个程序，表示为C，接受两个输入：C(x, w)。输入x是公开输入，w是秘密见证输入。该程序的输出是布尔值，即，或者true或false。然后给目标一个特定的公共输入x，证明证明者知道一个秘密输入w，使得C(x,w) == true。 我们将专门讨论非交互式零知识证明。这意味着证明本身是一组数据，无需证明者的任何交互即可对其进行验证。 示例程序 假设 Bob 得到了H某个值的散列，他希望有一个证明 Alice 知道s散列到的值H。通常 Alice 会通过给sBob来证明这一点，之后 Bob 会计算哈希并检查它是否等于H。 但是，假设 Alice 不想向sBob透露该值，而只是想证明她知道该值。她可以为此使用 zk-SNARK。 我们可以使用以下程序来描述 Alice 的场景，这里编写为一个 Javascript 函数： function C(x, w) { return ( sha256(w) == x );} 换句话说：程序接受一个公共散列x和一个秘密值w，true如果w等于SHA-256 散列，则返回x。 使用函数翻译 Alice 的问题，C(x,w)我们看到 Alice 需要创建一个证明，证明她拥有s这样的C(H, s) == true，而不必透露s。这是 zk-SNARKs 解决的一般问题。 zk-SNARK 的定义 甲 ZK-SNARK 包括三个算法 G, P, V 定义如下： 该 密钥生成器 G 需要一个秘密参数 lambda 和程序 C，并产生两个公开可用的按键， 证明键 pk，和一个 验证密钥 vk。这些密钥是公共参数，只需为给定程序生成一次 C。 该 证明 P 作为输入的证明键 pk，公共投入 x 和私人见证 w。该算法生成 证明 prf = P(pk, x, w) 者知道证人 w 并且证人满足程序的证明。 该 验证 V 单位计算 V(vk, x, prf) 其回报率 true ，如果证明是正确的， false 否则。因此，如果证明者知道w 满足 的证人，则此函数返回真 C(x,w) == true。 这里注意lambda 生成器中使用的秘密参数 。该参数有时会使在实际应用中使用 zk-SNARK 变得棘手。这样做的原因是任何知道这个参数的人都可以生成假证明。具体来说，给定任何程序 C 和公共输入， x 一个知道的人 lambda 可以生成一个证明 fake_prf ，以便 V(vk, x, fake_prf) 在true 不知道秘密的情况下 评估为 w。 因此，实际运行生成器需要一个非常安全的过程，以确保没有人知道并将参数保存在任何地方。这就是 Zcash 团队为了生成证明密钥和验证密钥而进行极其复杂的仪式的原因 ，同时确保“有毒废物”参数 lambda 在此过程中被销毁。 我们示例程序的 zk-SNARK Alice 和 Bob 在实践中如何使用 zk-SNARK 来让 Alice 证明她知道上面例子中的秘密值？ 首先，如上所述，我们将使用由以下函数定义的程序： function C(x, w) { return ( sha256(w) == x ); } 第一步是让 Bob 运行生成器 G 以创建证明密钥 pk 和验证密钥 vk。首先，随机生成 lambda 并将其用作输入： (pk, vk) = G(C, lambda) 小心处理参数 lambda，因为如果 Alice 了解 lambda 的值，她将能够创建假证明。Bob 将与 Alice 共享 pk 和 vk。 Alice 现在将扮演证明者的角色。她需要证明她知道哈希到已知哈希 H 的值 s。 她使用输入 pk、H 和 s 运行证明算法 P 以生成证明 prf： prf = P(pk, H, s) 接下来 Alice 向 Bob 提供证明 prf，Bob 运行验证函数 V(vk, H, prf)，在这种情况下会返回 true，因为 Alice 正确地知道秘密 s。Bob 可以确信 Alice 知道这个秘密，但 Alice 不需要向 Bob 透露秘密。 可重复使用的证明和验证密钥 在我们上面的例子中，如果 Bob 想向 Alice 证明他知道一个秘密，则不能使用 zk-SNARK，因为 Alice 无法知道 Bob 没有保存 lambda 参数。鲍勃可能能够伪造证明。 如果一个程序对很多…

零知识证明：STARKs 与 SNARKs
type: item
date: 2021-08-25T11:15:00+08:00
description: 新技术之间的冲突 纵观历史，总是有类似的技术大约在同一时间进入市场，寻求类似的结果，但以不同的方式解决问题。当这种市场现象发生时，采用者应该尝试客观地评估每一项技术。 由于 STARK 阵营和 SNARK 阵营都对各自的技术充满热情，我们认为对这两种技术进行客观比较会很有趣。 STARKs 与 SNARKs 快速复习一下，零知识证明技术使一方能够向另一方证明他们知道某些事情，而证明者不必自己传达信息来证明他们的知识。它们既是一种隐私增强技术，因为它们减少了用户之间需要提供的信息量，又是一种扩展技术，因为它们可以允许以更快的速度验证证明，因为它们不包含全部信息非私有系统的信息。 当今市场上最引人注目的两种零知识技术是 zk-STARKs 和 zk-SNARKs。两者都是双方证明知识的方法的首字母缩写词：zk-STARK代表零知识可扩展的透明知识论证，zk-SNARK代表零知识简洁非交互式知识论证。本文将深入探讨从文化和技术的角度分析这两种不同的零知识技术之间的核心差异。此外，这两种零知识技术本质上都是非交互式的，这意味着代码可以部署并自主运行。 下面，我们有几个表格描述了两种技术之间的一些高级差异。我们还将深入研究段落格式的差异。 资料来源：物质实验室 SNARK 2012 年 1 月，加州大学伯克利分校一位名叫 Alessandro Chiesa 的教授与人合着了一篇论文，为他们首次构建的零知识证明创造了术语 zk-SNARK。Zk-SNARK 在其基础上依赖于椭圆曲线来保证安全性。密码学中的椭圆曲线在基本假设下运行，即找到相对于公知基点的随机椭圆曲线元素的离散对数是不可行的。 虽然关于椭圆曲线随机数生成器是否存在后门一直存在很大争议，但整个算法通常仍然是安全的。尽管侧信道攻击中有几个流行的漏洞，但可以通过多种技术轻松缓解。量子攻击确实笼罩在基于椭圆曲线的密码学上，但打破其安全模型所需的量子计算尚未广泛应用。 除了基于椭圆曲线之外，zk-SNARK 还需要可信设置。可信设置是指密钥的初始创建事件，用于创建私人交易所需的证明以及这些证明的验证。最初，当这些密钥被创建时，在验证密钥和发送私人交易的密钥之间有一个隐藏的参数链接。如果用于在可信设置事件中创建这些密钥的秘密没有被破坏，则可以利用这些秘密通过虚假验证来伪造交易，从而使持有者能够执行诸如凭空创建新令牌并使用它们等操作用于交易。由于 zk-SNARKs 的隐私特性，将无法验证凭空创建的代币实际上是凭空创造。话虽如此，信任设置仅在最初需要 因此，基于 SNARK 的网络的用户必须依赖于正确执行可信设置的事实，这意味着与可信设置密钥相关的秘密已被销毁，并且不会由监督仪式的个人持有。对可信设置的依赖一直是 SNARK 批评者最关注的领域之一。话虽如此，开发人员只需要最初使用可信设置，而不是持续使用。 SNARK 的另一个重要批评领域是它们不具有量子抗性。一旦量子计算在很大程度上可用，SNARKs 背后的隐私技术将被打破。当然，SNARKs 的支持者正确地指出，当使用量子计算机时，我们将面临更多问题，例如破坏 RSA 和大多数钱包基础设施。 话虽如此，尽管存在与可信设置相关的问题，但实际上 SNARK 的采用速度比 STARK 快得多的原因有很多。SNARKs 比 STARKs 早几年被发现，这使该技术在采用方面取得了重要的领先优势。Zcash 是较早的数字资产项目之一，它在区块链开发社区中普及了 SNARK 的使用。由于 Zcash 和其他 SNARKs 的采用者，SNARKs 拥有最多的开发人员库、已发布的代码、项目和积极致力于该技术的开发人员。除了 Zcash，新兴的 DEX Loopring 也使用了 SNARK。如果开发人员想开始使用零知识技术，他们在使用 SNARK 方面将比 STARK 获得更多支持。 此外，据估计 SNARK仅需要 STARK 所需气体的 24%，这意味着与 SNARK 进行交易对最终用户来说要便宜得多。最后，SNARKs 的证明大小比 STARKs 小得多，这意味着它需要更少的链上存储。 STARKs 虽然 SNARKs 在文档和开发人员支持方面比 STARKs 有一些明显的优势，但 STARKs 确实提供了一些独特的好处。但首先，让我们从技术角度深入了解 STARK 是什么。 Eli Ben-Sasson、Iddo Bentov、Yinon Horeshy 和 Michael Riabzev 在2018 年撰写了第一篇描述 STARK 的论文。与 SNARK 不同，STARK 的基础技术依赖于哈希函数。马上，依靠散列函数提供了一些好处，例如抗量子。此外，开始在网络中使用 STARK 不需要可信设置。 话虽如此，STARKs 的证明尺寸远大于 SNA…

什么是 zk-SNARK？
type: item
date: 2021-08-25T10:16:00+08:00
description: Zcash 是 zk-SNARKs 的第一个广泛应用，zk-SNARKs 是一种新颖的零知识密码学形式。Zcash 强大的隐私保证源于这样一个事实，即 Zcash 中的屏蔽交易可以在区块链上完全加密，但仍然可以通过使用 zk-SNARK 证明在网络的共识规则下验证其有效性。 首字母缩略词 zk-SNARK 代表“零知识简洁的非交互式知识论证”，指的是一种证明结构，在这种结构中，人们可以证明拥有某些信息，例如一个秘密密钥，而无需透露该信息，并且之间没有任何交互证明者和验证者。 “零知识”证明允许一方（证明者）向另一方（验证者）证明一个陈述是真实的，而不会透露超出陈述本身有效性的任何信息。例如，给定一个随机数的散列，证明者可以说服验证者确实存在一个具有该散列值的数字，而无需透露它是什么。 在零知识“知识证明”中，证明者不仅可以说服验证者该数字存在，而且他们实际上知道这样一个数字——同样，无需透露有关该数字的任何信息。“Proof”和“Argument”之间的区别是非常技术性的，我们不在这里讨论。 “简洁”的零知识证明可以在几毫秒内得到验证，即使是关于非常大的程序的语句，证明长度也只有几百字节。在第一个零知识协议中，证明者和验证者必须来回通信多轮，但在“非交互式”结构中，证明由从证明者发送到验证者的单个消息组成。目前，生成非交互式且足够短以发布到区块链的零知识证明的最有效的已知方法是具有初始设置阶段，该阶段生成在证明者和验证者之间共享的公共参考字符串。我们将这个公共引用字符串称为系统的公共参数。 如果有人可以访问用于生成这些参数的秘密随机性，他们将能够创建对验证者来说看起来有效的虚假证明。对于 Zcash，这意味着恶意方可以制造假币。为了防止这种情况发生，Zcash 通过精心设计的多方仪式生成了公共参数。要了解有关我们的参数生成仪式的更多信息，并查看我们为防止暴露 Zcash 所必需的秘密随机性（例如，计算机被喷灯）而采取的预防措施，请访问我们的Paramgen 页面。要了解有关参数生成协议背后的数学原理的更多信息，请阅读我们关于该主题的博客文章或白皮书 ( 1 , 2 )。 如何在 Zcash 中构建 zk-SNARK 为了在 Zcash 中实现零知识隐私，根据网络的共识规则确定交易有效性的函数必须返回交易是否有效的答案，而不会泄露其执行计算的任何信息。这是通过在 zk-SNARKs 中编码一些网络的共识规则来完成的。在高层次上，zk-SNARK 的工作原理是首先将您想要证明的内容转换为关于了解某些代数方程的解的等效形式。在下一节中，我们简要概述了如何将确定有效交易的规则转换为方程，然后可以对候选解决方案进行评估，而无需向验证方程的各方透露任何敏感信息。 Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK 将我们的交易有效性函数转化为数学表示的第一步是将逻辑步骤分解为尽可能小的操作，从而创建一个“算术电路”。类似于布尔电路，其中程序被编译成离散的单步，如 AND、OR、NOT，当程序被转换为算术电路时，它被分解为由加法、减法等基本算术运算组成的单步，乘法和除法（尽管在我们的特殊情况下，我们将避免使用除法）。 以下是用于计算表达式 (a+b)(bc) 的算术电路的示例： 看看这样的电路，我们可以将输入值 a、b、c 视为在电线上从左到右“行进”到输出电线。我们的下一步是构建所谓的 1 级约束系统或 R1CS，以检查值是否“正确移动”。在这个例子中，R1CS 将确认，例如，从 b 和 c 进入的乘法门出来的值是 b*c。 在这个 R1CS 表示中，验证器必须检查许多约束——几乎电路的每条线路都有一个约束。（由于技术原因，事实证明我们只对来自乘法门的电线有约束。）在 2012 年关于该主题的论文中，Gennaro、Gentry、Parno 和 Raykova 提出了一种“将所有这些约束捆绑在一起”的好方法. 此方法使用称为二次算术程序 (QAP) 的电路表示。需要检查的单个约束现在在多项式之间而不是在数字之间。多项式可能非常大，但这没关系，因为当多项式之间不存在同一性时，它在大多数情况下都不会成立。因此，您只需检查两个多项式是否在随机选择的一个点上匹配 以便以高概率正确验证证明。 如果证明者事先知道验证者会选择检查哪一点，他们可能能够制作无效的多项式，但仍然满足该点的身份。与ZK-SNARKs，复杂的数学技术，如同态加密和配对的椭圆曲线的用于评价多项式“盲目地” -即在不知道哪个点正被评估。上面描述的公共参数用于确定将检查哪个点，但采用加密形式，以便证明者和验证者都不知道它是什么。 到目前为止的描述主要解决了如何获得“SNARKs”中的 S 和 N——如何获得一个简短的、非交…