StarkWare 的使命是将 STARK 带入现实世界。 这是解释 STARK 背后的理论及其实施的系列文章中的第一篇。 我们从轻描淡写开始，并将在后续帖子中逐步提高数学。
介绍
计算完整性 (CI) 是商业的基础属性。 简单来说，就是某个计算的输出是正确的。 CI 使我们能够信任呈现给我们的帐户余额或商店的账单。 这篇文章将深入探讨无许可区块链如何在不需要信任的情况下实现 CI，他们为此在可扩展性和隐私方面付出的巨大代价，以及 STARKs 如何挽救局面。
信任与验证
“旧世界”：信任或委托责任
金融系统（银行、经纪商、交易所等）需要诚信经营才能发挥其社会功能。 什么机制可以激励他们诚信经营？ “旧世界”将信任视为诚信的代名词。 我们相信银行、养老基金等会诚实经营。 让我们走进兔子洞，审视这种信任的基础，忽略“诚信剧院”——高楼大厦和华丽的西装——会给我们留下深刻印象。 从纯粹理性和功利主义的角度来看，阻止金融系统没收我们所有资金的是社会耻辱、监禁和罚款的威胁。 还有一个胡萝卜——声誉，可以吸引未来的客户并产生未来的利润。 通过用自己的名字在财务报表上签名，“旧世界”的人们将个人自由、现有和未来的财务作为诚信的抵押品，而我们公众将信任建立在这种安排之上。 这种完整性的验证委托给会计师、审计师和监管机构等专家。 我们将称之为委托责任。 这不是一个糟糕的系统：它已经忠实地为现代经济服务了很长一段时间。
“旧世界”方法的新变体是可信执行环境 (TEE)。 受信任的硬件制造商（如英特尔）生产的物理机器（如 SGX 芯片）不能偏离指定的计算，并使用只有该物理机器知道的密钥签署正确的状态。 完整性现在基于对硬件及其制造商的信任，并基于不可能从此类物理设备中提取密钥的假设。
“新世界”：核实，或包容问责
区块链提供了一种更直接的方式来实现完整性，其座右铭是“不信任，验证”。 这个“新世界”不需要诚信剧院，它不依赖会计师，它的开发人员和网络维护人员也不需要个人自由来获得公众信任。 完整性由包容性问责制保证：具有标准计算设置的节点（联网笔记本电脑）应该能够验证系统中所有交易的完整性。
在无许可区块链中验证 CI 的普遍方法是通过简单的重放：要求所有节点重新执行（重放）验证每笔交易的计算。 包容性问责制以这种幼稚的形式导致了两个直接的挑战：
- 隐私：如果每个人都可以检查所有交易，那么隐私可能会受到损害。 隐私的缺失阻碍了企业的发展，因为这意味着敏感信息可能无法保持专有。 它也使个人望而却步，因为它侵蚀了人的尊严。
- 可扩展性：要求系统对标准笔记本电脑负责意味着它不能通过简单地移动到更大的计算机和更大的带宽来扩展。 这导致系统的吞吐量受到严重限制。
证明系统（接下来讨论）是应对这两个挑战的绝佳解决方案。 零知识 (ZK) 证明系统现在是解决区块链隐私问题的既定工具，并且在 Zcash [1、2、3] 的几篇文章中得到了很好的解释。 尽管 ZK-STARKs 提供零知识，但本文不会讨论它，而是关注可扩展性和透明性（STARK 中的 S 和 T）。
Proof Systems（证明系统）
Proof Systems 始于 1985 年由 Goldwasser、Micali 和 Rackoff 引入的交互式证明 (IP) 模型。交互式证明是涉及两种实体的协议：证明者和验证者，他们通过发送消息进行多轮交互 消息。 证明者和验证者的目标是相互冲突的：证明者要让验证者相信某个计算的完整性，而验证者是公众委托的可疑守门人，肩负着辨别真假的任务。 证明者和验证者交互通信，轮流向对方发送消息。 这些消息取决于被证明的陈述、先前的消息，并且还可能使用一些随机性。 在证明者方面，随机性用于实现零知识，在验证者方面，需要随机性来生成对证明者的查询。 在交互过程结束时，验证者输出一个决定，要么接受新状态，要么拒绝它。
一个很好的类比是当一方提出索赔而另一方质疑其有效性时在法庭上进行的审查过程。 为了使声明被接受为真实的，声明者（证明者）对审查者（验证者）的查询提供的答案必须一致且有效。 预计检查过程会暴露陈述与现实之间的任何不匹配，从而将其暴露为错误。
如果当系统从状态 A 更新到状态 B 时，以下属性成立，我们说证明系统解决了 CI：
- 完整性：如果证明者确实知道如何以有效的方式将状态从 A 更改为 B，那么证明者将设法说服验证者接受更改。
- 可靠性：如果证明者不知道如何将状态从 A 更改为 B，那么验证者将注意到交互中的不一致并拒绝建议的状态转换。 仍然存在微小的误报概率，即验证者接受无效证明的概率。 该概率是一个系统安全参数，可以将其设置为可接受的水平，例如 1/(2¹²⁸)，类似于连续五次赢得强力球的几率。
这对属性对前面讨论的包容性问责原则具有重要意义。 验证者可以接受证明者建议的状态转换，而无需对证明者的完整性做任何假设。 事实上，证明者可以在有故障的硬件上运行，它可以是闭源的，也可以在恶意实体控制的计算机上执行。 唯一重要的¹是证明者发送的消息导致验证者接受声明。 如果是这样，我们就知道计算完整性成立。
Stark
到目前为止，已经有相当多的证明系统的理论构造以及实现。 有些部署在加密货币中，例如 Zerocash/Zcash 使用的 SNARK，以及部署在 Monero 中的 Bulletproofs (BP)。 （有关证明系统的一般信息，请访问此处。）STARK 的区别在于以下三个属性的组合：可扩展性（STARK 中的 S）、透明度（STARK 中的 T）和精益密码学。
可扩展性——验证的指数级加速
可扩展性意味着两个效率属性同时存在：
- 可扩展的证明者：证明者的运行时间是“近乎线性的”，一台受信任的计算机通过自己重新执行计算并检查结果是否与某人声称的相符来检查 CI 所花费的时间。 “开销”（生成证明所需的时间/仅运行计算所需的时间）的比率仍然相当低。
- 可扩展验证器：验证器的运行时间是简单重放时间的对数多项式。 换句话说，验证者的运行时间比简单地重放计算要小得多（回想一下，“重放”是当前实现包容性问责制的区块链方法）。
![]()
将这种可扩展性概念应用于区块链。 想象一下当区块链转向使用证明系统进行验证时，情况会如何，而不是通过简单重播的当前验证模式。 证明者节点需要生成证明，而不是简单地发送要添加到区块链的交易，但由于可扩展证明者，它的运行时间与原始重放解决方案的运行时间几乎呈线性关系。 可扩展验证器将受益于其验证时间的指数减少。 此外，随着区块链吞吐量的扩大，大部分影响将由证明者节点（可以在专用硬件上运行，如矿工）承担，而构成网络中大部分节点的验证者几乎不会受到影响。
让我们考虑一个具体的假设示例，假设验证者时间（以毫秒为单位）与交易数量 (tx) 的对数平方成比例。 假设我们从 10,000 tx/block 开始。 那么验证者的运行时间为
VTime = (log₂ 10,000)² ~ (13.2)² ~ 177 ms
现在将块大小增加一百倍（到 1,000,000 tx/块）。 验证者的新运行时间为
VTime = (log₂ 1,000,000)² ~ 20² ~ 400 ms
换句话说，交易吞吐量增加 100 倍只会导致验证者的运行时间增加 2.25 倍！
在某些情况下，验证者仍然需要下载并验证数据的可用性，这是一个线性时间的过程，但下载数据通常比检查其有效性更便宜、更快。
透明度：对任何人都没有信任，对所有人都诚实
透明意味着² 没有可信的设置——在系统设置中不使用秘密。 透明度有很多好处。 它消除了构成单点故障的参数设置生成过程。 缺乏可信的设置甚至允许强大的实体——控制“旧世界”金融系统的大公司、垄断企业和政府——证明 CI 并获得公众对其主张的接受，因为没有已知的方法来伪造 STARK 的虚假证明， 即使是最强大的实体。 在更具战术性的层面上，它使部署新工具和基础设施以及更改现有工具和基础设施变得更加容易，而无需精心设计的参数生成仪式。 最重要的是，透明度与“新世界”非常吻合，“新世界”要求在没有信任假设的情况下承担包容性责任。 用亚伯拉罕林肯的话来说，透明的系统允许在不信任任何人的情况下运作，对所有人保持诚信。
精益密码学：安全和快速
STARK 在其安全性基础上具有最小³ 加密假设：存在安全加密和抗碰撞哈希函数。 今天，许多这些原语都以硬件指令的形式存在，精益密码学还带来了两个好处：
- 后量子安全：STARK 对于高效的量子计算机来说似乎是安全的。
- 具体效率：对于给定的计算，STARK 证明者至少比 SNARK 和 Bulletproofs 证明者快 10 倍。 STARK 验证器至少比 SNARK 验证器快 2 倍，比 Bulletproof 验证器快 10 倍以上。 随着 StarkWare 继续优化 STARK，这些比率可能会提高。 然而，STARK 证明长度比相应的 SNARK 大 ~100 倍，比 BulletProofs 大 ~20 倍。
总结
我们首先解释了无许可区块链的“新世界”，其中的座右铭是“不要信任，验证”。 包容性问责原则要求任何人都可以轻松验证金融系统的完整性，这与“旧世界”的委托问责制相反。 为了允许区块链扩展，我们需要允许比简单重放更快的计算完整性验证方法。
STARKs 是一种特殊的证明系统，提供可扩展性和透明度，并基于精益密码学。 它们的可扩展性和透明度允许对 CI 进行廉价且无需信任的验证。 这是 STARKs 的承诺，也是 StarkWare 的使命。
我们的下一篇文章将更深入地探讨构建 STARK 的数学知识。
感谢 Vitalik Buterin 和 Arthur Breitman 审阅这篇博文的草稿。
Michael Riabzev & Eli Ben-Sasson
StarkWare 工业公司
... ...
¹隐私保护（ZK）确实对证明者代码提出了要求，以确保证明者消息不会通过侧通道泄露有关见证人的信息。 但是稳健性不需要信任假设。
²形式上，透明证明系统是一个所有验证者消息都是公共随机字符串的系统。 此类系统也称为 Arthur-Merlin 协议。
³这种最小的密码学假设适用于交互式 STARKs (iSTARKs)。 非交互式 STARKs (nSTARKs) 需要 Fiat-Shamir 启发式算法，这是一种不同的野兽。