“I know one thing, and that is that I know nothing” – Socrates
There has been a lot of palpable fervor lately surrounding L2 scaling solutions, and rightfully so. With Optimism releasing a governance token, demand for lower gas fees on ETH mainnet, and a litany of new ideas being produced at back-to-back hackathons, it’s safe to say that L2 2022 is in full swing.
In today’s piece, I’ll be dissecting one of the most powerful, yet often misunderstood, cryptographic tools ever created: zero–knowledge proofs. In addition, I’ll be highlighting use cases and proposals for future implementation, as well as demonstrating why zk proofs hold a key to crypto’s future. This is a continuation of an ongoing series analyzing how blockchains can best scale to meet the needs of billions. If you are unfamiliar with rollups, I suggest this primer.
Simply put, a zk proof is a way for a prover to convince a verifier that something is true without actually revealing any information about it. Let’s illustrate this with an analogy: suppose we have two people, Alice and Bob. Alice has a sealed deck of 52 playing cards. Alice picks a red card in secret and wants to prove to Bob that she has a red card, without actually showing the red card. In order to do this, Alice will need to separate all the black cards from the deck and show them to Bob. Bob counts all 26 black cards, verifying their presence, and determines that the card Alice has must be red. Therefore, Alice was able to prove to Bob that she had the red card, without actually showing it. This analogy is extremely simplified and does not paint the full picture, but the core idea behind the tech remains the same.
Zk proofs are not novel to this decade, or even to this millennia. In fact, the idea was first introduced in the 1980s by abstract mathematics researchers. This solution was developed to solve the problems relating to, at the time, theoretical systems between Provers and Verifiers – interactive proofs.
But what if the Verifier turns out to be malicious? How much extra information is the Prover revealing, besides verifying the truthfulness of a statement? Let’s look at how hashed versions of passwords on centralized servers are stored. Traditionally, upon interacting with the server, the server would learn the cleartext password. This is an awful way to conduct ‘proof of identity’, so researchers turned to a system that proves a statement while revealing no extraneous information.
More concretely, suppose we have some function C, with two inputs C(x,y). Let x be the public input, y be a secret witness, and let the output of the function be either true or false. Given a specific public input x, the prover must show that they know a secret witness y such that C(x,y) == true. From the prover’s perspective, randomness is necessary to realize zero knowledge. On the verifier side, randomness is needed to produce queries to the prover. **The first application widely demonstrated was in the NP – complete class of complexities called the graph three – coloring problem. This was a huge breakthrough, as this application can be applied to any problem in the NP class. That’s like hitting 20 birds with one stone.
In the blockchain space, there are many implementations of zk proofs because of its ability to provide scalability, as well as utility in privacy models. Specifically, the verifier performs exponentially less computational work than without a zk proof system. The prover, on the other hand, requires quite a bit of computational overhead needed to perform the proof. I’ll discuss this in detail later.
While there are a multitude of zk protocols that currently exist, for this piece I’m focusing on SNARKs and STARKs, with deep dives on other protocols to follow in later pieces.
Succinct Non-Interactive Arguments of Knowledge, or SNARK, is a popular proving mechanism that incorporates zero-knowledge proofs that was first introduced in 2011. Under the hood, zk-SNARKs use elliptic curves for security and rely on a trusted setup. Initially, keys are created to develop the proofs required for transactions and for verification of said proofs. These keys contain a reference string linking the verification key and the key sending private information. For this to work, it is vital that the method of creation of the key is deleted, and that the creator of the key is trustworthy (hence the term trusted setup). This reliance on trust in the creation stage remains a big point of criticism in zk-SNARKs. In addition, the reference string is non-upgradable, meaning that if the program needs to be updated, the trusted setup phase needs to be re-run.
In actual practice, however, zk-SNARKs are hard to implement on their own. There are a multitude of steps that need to be checked in a computation, but doing the work to check each step individually takes an unfeasible amount of time. The solution comes in the form of polynomials. Encoding the computation into polynomials saves a tremendous amount of information and time. Instead of having a boundless number of equations between numbers, we can substitute them with polynomial expressions that “stand in” for them.
But wait, there’s more! Typically, equations are verified with polynomials by checking each coefficient, but this again takes too long. Polynomial commitments come into play here. A Polynomial commitment can be viewed as a unique method of “hashing” a polynomial. This allows for verification in a much shorter time, regardless of how large the polynomial is. In addition, polynomial commitments are inherently privacy preserving, as the proof is much smaller than the polynomial itself. The polynomial commitment will not reveal more than a modicum of information from the polynomial, though randomness can be added. For a more mathematical dive into polynomial commitments and verification, check this out.
Polynomial commitments use one of three major protocols: bulletproof, KZG, and FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Comparing and contrasting each will get a bit dense and beyond the scope of this current piece, as they each deserve their own deep dives.
Tired with the status quo, in 2018 a group of researchers sought to include transparency in zk systems. Transparency meant not having to rely on a trusted party for initial setup, which eliminated the threat of an open backdoor. This led to the creation of scalable transparent arguments of knowledge, or STARKs. STARKs use hash functions as their source of security, which differs from the bilinear implementation used by SNARKs. The scalable aspect of the name refers to two things:
Though zk-SNARK pioneers like Zcash have been around for a while, the creation of zk STARKs ushered in an explosion of development in space. The work in zk protocols is not limited to rollups. In fact, some L1s have been built based on zk proofs, as well as budding gaming projects. StarkWare is a pioneer in zk-STARK, developing two core products: StarkNet, a permissionless decentralized zk rollup, and StarkEx, a standalone zk rollup SaaS. Additionally, StarkWare was the first producer of a production-grade zk virtual machine (zkVM) called Cairo. Cairo claims to have done this through implementation of a Turing complete Von Neumann architecture. Each program resides in the VM’s memory, alongside the data processed by it. Cairo can be accessed by anyone today, and is currently being used by prominent StarkEx clients like dydx, Immutable, and DeversiFi. Other novel applications using their own version of zkVM include Polygon Miden and RiscZero, the latter of which is attempting to build a general purpose zkVM.
Contrary to the bootstrapping zkVM ideology, are zkEVMs. zkVMs start from scratch as a new blockchain VM optimized for zk, or simply adapt Solidity tooling and compatibility. On the other hand, zkEVMs implement the full set of EVM opcodes. The usage of the EVM opcodes offers a few benefits:
Unsurprisingly, there seems to be a hard divide between the zkVM and zkEVM camps.
The biggest advantage zkEVMs have over zkVMs is the EVM equivalence. Targeting the massive existing dApp community through low gas fee incentives and an easy on-boarding experience for developers has historically proven fruitful, which is exactly what zkEVM builders are counting on. The most popular zkEVM project currently is zkSync, which uses zk-SNARKs to validate and scale as a layer 2 solution. In addition, zkSync has chosen to put data availability off-chain, and is secured using proof of stake (zkPorter) by zkSync token stakers (implying an airdrop might be imminent). The design of this implementation falls under a solution developed by StarkWare called Volition.
Finally, a rather newer player to the scene, Scroll is developing a general purpose L2 zkEVM. Scroll takes a new approach to generating zk proofs off-chain using GPU power. Recent breakthroughs in zk proofs like Poseidon hash, Plookup, and PLONK have brought the cost down enough to make zkEVM a reality. Additionally, advancements in GPU and ASIC/FPGA accelerators are improving hardware conditions, bringing the cost further down. Scroll is still in its development phase, with plans on debuting their zkEVM testnet within the coming months.
Zk proofs were initially developed with the idea of maintaining privacy. Though popular media may focus current use cases on ‘greater allowance of TPS’, the fact remains that zk proofs have a much wider range of applications. One such application is a tool that verifies the identity of users by checking assets in wallet or on-chain transactions anonymously via zk circuitry.
Zk identities have the potential to be extremely powerful, and use cases are immediately available in the real world. For instance, suppose I am a debtor who is trying to prove his creditworthiness while still keeping banking information and activity private. I would show that I’ve paid off large loans from multiple trusted banks, but will not reveal the banks or the specifications of those loans.
Four key components to support future zk-identity, source
Another big development in the zk area is efficient private delegation of zk-SNARK provers. As stated earlier, time to prove is quite slow. Hashing 10kb with SHA2 takes 140 seconds, instead of the desired few milliseconds. A solution to this would be to outsource the proving. Unfortunately, this brings up another dilemma: secrets are invariably leaked to the workers. What is needed: outsourcing proving with privacy. Through careful implementation, it is possible to delegate proving to a device like a mobile phone with 26x faster speeds than computing locally. This novel framework was first presented at the zkSummit in April 2022 by Pratyush Mishra.
We are very early in the development of application based zk proofs. Nevertheless, the pace of progress has been rapid. Stages that expert researchers thought would not be reached in 5 years have already come to fruition. That said, there’s still a lot to accomplish. There is still a lot of strife between development communities, as camps are being formed and opinions are being politicized. Only time will tell which party is right. What is certain is that, when historians look back, they will see this period of zk implementations as the seminal part in the spectacular history of cryptocurrency.
This report is not investment or trading advice. Please conduct your own research before making any investment decisions. Past performance of an asset is not indicative of future results. The Author may be holding the cryptocurrencies or using the strategies mentioned in this report.
“我知道一件事，那就是我一无所知”——苏格拉底
最近围绕 L2 扩展解决方案有很多明显的热情，这是理所当然的。随着 Optimism 发布治理代币、对 ETH 主网降低 gas 费用的需求，以及在背靠背黑客马拉松中产生的一连串新想法，可以肯定地说，L2 2022 正在如火如荼地进行。
在今天的文章中，我将剖析有史以来最强大但经常被误解的加密工具之一：零知识证明。此外，我将重点介绍未来实施的用例和建议，并展示为什么 zk 证明是加密未来的关键。 这是正在进行的系列分析的延续，该系列分析了区块链如何最好地扩展以满足数十亿的需求。如果您不熟悉汇总，我建议您阅读此入门。
简而言之，zk 证明是证明者在不实际透露任何信息的情况下说服验证者某事为真的一种方式。让我们用一个类比来说明这一点：假设我们有两个人，Alice 和 Bob。爱丽丝有一副密封的 52 张扑克牌。爱丽丝偷偷拿了一张红牌，想向鲍勃证明她有一张红牌，但实际上并没有出示红牌。为了做到这一点，Alice 需要将所有的黑牌从牌堆中分离出来，然后将它们展示给 Bob。Bob 计算所有 26 张黑卡，验证它们的存在，并确定 Alice 拥有的卡必须是红色的。因此，爱丽丝能够向鲍勃证明她有红牌，而无需实际出示。这个比喻非常简化并没有描绘全貌，但技术背后的核心理念保持不变。
Zk 证明对于这十年甚至几千年来说并不新鲜。事实上，这个想法是在 1980 年代由抽象数学研究人员首次提出的。该解决方案旨在解决当时与证明者和验证者之间的理论系统相关的问题——交互式证明。
但是如果验证者被证明是恶意的怎么办？除了验证陈述的真实性之外，Prover 还透露了多少额外信息？让我们看看集中式服务器上密码的散列版本是如何存储的。传统上，在与服务器交互时，服务器会学习明文密码。这是进行“身份证明”的一种糟糕的方式，因此研究人员转向了一种系统，该系统可以在不泄露任何无关信息的情况下证明声明。
更具体地说，假设我们有一些函数C，有两个输入C(x,y)。令x为公开输入，y为秘密见证，让函数的输出为真或假。给定一个特定的公共输入x，证明者必须证明他们知道一个秘密见证y使得C(x,y) == true。从证明者的角度来看，实现零知识需要随机性。在验证者方面，需要随机性来产生对证明者的查询。 **被广泛展示的第一个应用是在NP 中——完成一类复杂性称为图三着色问题。这是一个巨大的突破，因为这个应用程序可以应用于NP 类中的任何问题。这就像用一块石头击中 20 只鸟。
在区块链领域，由于 zk 证明能够提供可扩展性以及在隐私模型中的实用性，因此有许多实现。具体来说，与没有 zk 证明系统的情况相比，验证者执行的计算工作呈指数级减少。另一方面，证明者需要相当多的计算开销来执行证明。我稍后会详细讨论这个问题。
虽然目前存在大量的 zk 协议，但对于这篇文章，我将重点关注 SNARK 和 STARK，并在后面的文章中深入探讨其他协议。
简洁的非交互式知识论证（SNARK）是一种流行的证明机制，它结合了 2011 年首次引入的零知识证明。在底层，zk-SNARK 使用椭圆曲线来保证安全性并依赖于可信设置。最初，创建密钥以开发交易所需的证明和验证所述证明。这些键包含一个参考字符串链接验证密钥和发送私人信息的密钥。为此，必须删除创建密钥的方法，并且密钥的创建者是可信赖的（因此称为可信设置）。这种在创建阶段对信任的依赖仍然是 zk-SNARKs 的一大批评点。此外，引用字符串是不可升级的，这意味着如果程序需要更新，则需要重新运行受信任的设置阶段。
然而，在实际实践中，zk-SNARK 很难自行实现。在计算中需要检查许多步骤，但是单独检查每个步骤的工作花费的时间是不可行的。解决方案以多项式的形式出现。将计算编码为多项式可以节省大量信息和时间。我们可以用“代替”它们的多项式表达式代替它们，而不是在数字之间有无数个方程。
但是等等，还有更多！通常，通过检查每个系数来使用多项式验证方程，但这又需要太长时间。多项式承诺在这里发挥作用。多项式承诺可以被视为“散列”多项式的独特方法。这允许在更短的时间内进行验证，无论多项式有多大。此外，多项式承诺本质上是隐私保护，因为证明比多项式本身小得多。尽管可以添加随机性，但多项式承诺不会显示多项式的少量信息。如需更深入地了解多项式承诺和验证，请查看此内容。
多项式承诺使用三种主要协议之一：防弹、KZG和FRI（Fast Reed - Solomon交互式Oracle Proof of Proximity）。比较和对比每一个都会变得有点密集，超出了本篇文章的范围，因为他们每个人都值得自己深入研究。
厌倦了现状，2018 年，一群研究人员试图在 zk 系统中加入透明度。透明度意味着不必依赖受信任方进行初始设置，从而消除了开放后门的威胁。这导致创建了可扩展的透明知识论据，或STARKs。STARK 使用哈希函数作为其安全来源，这与 SNARK 使用的双线性实现不同。名称的可扩展性方面指的是两件事：
与 SNARK 相比，证明者的运行时间在复杂性上要便宜得多。
验证时间的大小是多对数。STARKs利用
FRI，提升信息存储量和效能。
尽管像Zcash这样的 zk-SNARK 先驱已经存在了一段时间，但 zk STARK 的创建却迎来了太空发展的爆炸式增长。zk 协议中的工作不仅限于汇总。事实上，一些 L1已经基于 zk 证明构建，以及萌芽的游戏项目。 StarkWare是 zk-STARK 的先驱，开发了两个核心产品：StarkNet，一个无需许可的去中心化 zk rollup，以及 StarkEx，一个独立的 zk rollup SaaS。此外，StarkWare 是名为 Cairo 的生产级 zk 虚拟机 (zkVM) 的第一家生产商。Cairo 声称通过实现图灵完备的冯诺依曼实现了这一点建筑学。每个程序与它处理的数据一起驻留在 VM 的内存中。今天任何人都可以访问开罗，目前正被著名的 StarkEx 客户使用，如dydx、Immutable和DeversiFi。其他使用他们自己版本的 zkVM 的新应用程序包括Polygon Miden和RiscZero，后者正在尝试构建通用 zkVM。
与引导式 zkVM 意识形态相反的是 zkEVM。zkVMs 从头开始作为针对 zk 优化的新区块链 VM，或者只是适应 Solidity 工具和兼容性。另一方面，zkEVM 实现了完整的 EVM操作码集。使用 EVM 操作码有几个好处：
不出所料，zkVM 和 zkEVM 阵营之间似乎存在很大的分歧。
zkEVM 相对于 zkVM 的最大优势是 EVM 等效性。历史证明，通过低 gas 费激励和为开发人员提供轻松的入职体验来瞄准庞大的现有 dApp 社区是卓有成效的，这正是 zkEVM 建设者所指望的。 目前最流行的 zkEVM 项目是zkSync，它使用 zk-SNARKs 作为第 2 层解决方案进行验证和扩展。此外，zkSync 选择将数据可用性置于链下，并由 zkSync 代币质押者使用权益证明 (zkPorter) 进行保护（这意味着空投可能迫在眉睫）。此实现的设计属于 StarkWare 开发的名为Volition的解决方案。
最后，一个相当新的参与者，Scroll正在开发一个通用的 L2 zkEVM。Scroll 采用了一种新方法来使用 GPU 能力在链下生成 zk 证明。最近在 zk 证明方面的突破，如Poseidon hash、Plookup和PLONK ，已经将成本降低到足以使 zkEVM 成为现实。此外，GPU 和 ASIC/ FPGA 加速器的进步正在改善硬件条件，进一步降低成本。Scroll 仍处于开发阶段，计划在未来几个月内推出他们的 zkEVM 测试网。
Zk 证明最初是为了维护隐私而开发的。尽管流行媒体可能将当前的用例集中在“更大的 TPS 许可”上，但事实仍然是 zk 证明具有更广泛的应用范围。 一个这样的应用程序是一种工具，它通过 zk 电路匿名检查钱包中的资产或链上交易来验证用户的身份。
Zk 身份具有极其强大的潜力，并且在现实世界中可以立即使用用例。例如，假设我是一名债务人，他试图证明自己的信誉，同时仍将银行信息和活动保密。我会证明我已经从多家受信任的银行偿还了大笔贷款，但不会透露银行或这些贷款的规格。
支持未来 zk-identity、source的四个关键组件
zk 领域的另一个重大发展是zk-SNARK 证明者的高效私人委托。如前所述，证明的时间相当缓慢。使用 SHA2 散列 10kb 需要 140 秒，而不是所需的几毫秒。解决这个问题的方法是外包证明。不幸的是，这带来了另一个困境：秘密总是泄露给工人。需要什么：外包隐私证明。通过仔细实施，可以将证明委托给手机等设备，其速度比本地计算快 26 倍。这个新颖的框架由Pratyush Mishra在 2022 年 4 月的 zkSummit 上首次提出。
我们在开发基于应用程序的 zk 证明方面处于非常早期的阶段。尽管如此，进展的步伐还是很快的。专家研究人员认为在 5 年内无法达到的阶段已经实现。也就是说，还有很多事情要做。发展社区之间仍然存在很多冲突，因为营地正在形成，意见正在被政治化。只有时间会证明哪一方是正确的。可以肯定的是，当历史学家回顾过去时，他们会将这一时期的 zk 实施视为加密货币壮观历史中的开创性部分。
本报告不是投资或交易建议。在做出任何投资决定之前，请进行自己的研究。资产的过往表现并不代表未来的结果。作者可能持有加密货币或使用本报告中提到的策略。