StarCore 1.0: 实现可验证计算

摘要

我们介绍StarCore项目，这是一个致力于实现互联网规模可验证计算的探索。

自1936年图灵引入通用计算机器——一种能够执行任何计算的假设机器以来，世界已经发生了翻天覆地的变化。 这个概念被认为是通用计算机的起源，并被冯·诺依曼用来引入冯·诺依曼架构，这是通用图灵机的物理实例。 这种架构现在几乎为所有现代计算机提供动力。

在本文中，我们介绍StarCore zkVM（零知识虚拟机），一种能够证明任何计算的机器。 也就是说，该机器为任何状态机（例如RISC-V、EVM、Wasm）的正确程序执行生成简洁的零知识证明。 StarCore zkVM专注于证明大型计算（例如超过10亿CPU周期），并设计为支持大规模并行增量证明生成， 非常适合在分布式证明网络中进行并行证明。

zkVM由现代高速递归证明系统（即折叠/累积）提供支持，这些系统允许证明被组合和聚合， 实现增量可验证计算（IVC）的概念及其泛化，即携带证明的数据（PCD）。 此外，我们引入了StarCore虚拟机（NVM），这是一个简单、最小化且可扩展的通用图灵机： 专为最大化证明者性能而设计的虚拟CPU架构。 NVM是StarCore zkVM的核心计算模型，可以通过编译和模拟技术以及指令集扩展（例如SHA-256） 以最小开销模拟任何其他ISA，如RISC-V、EVM、Wasm等。

我们简要描述了StarCore网络，这是一个即将推出的大规模分布式证明网络， 它聚合了异构计算机池的集体CPU/GPU能力，以实例化StarCore zkVM的极其并行化的大规模证明生成系统。 这使zkVM能够以与网络集体计算能力成比例的规模（以每秒证明的CPU周期数衡量）运行。

从根本上讲，StarCore项目寻求通过各种科学、工程和经济技术，将可验证计算的具体成本降低数个数量级， 使其最终成为一种实用的计算形式。该项目建立在密码学、复杂性理论、编译器和高性能计算数十年的科学研究基础上。 我们专注于提供简单的开发者体验和旨在支持生产级应用程序的系统，最初支持Rust程序。

我们设想互联网的未来，计算和数据的完整性将受到证明保护：一个人类合作通过数学真理得到增强的未来。 这构成了我们朝向这一愿景的第一个构建。

1. 概述

1.1 StarCore zkVM

我们介绍StarCore zkVM，一种能够证明任何计算的机器。我们的实现是完全开源的。 zkVM专注于证明非常大的计算（比如超过10亿CPU周期）。它通过极端并行化实现这一点： zkVM实现了轻量级和无界的增量可验证计算（IVC），这是一种允许通过使用现代高速递归零知识证明系统 （即折叠/累积方案）增量计算和更新正确计算证明的原语。这些技术允许高速证明累积， 完全不使用SNARKs。

1.2 StarCore虚拟机

StarCore虚拟机（NVM）是一种简单、最小化且可扩展的指令集架构（ISA）和随机访问机器（RAM）， 具有冯·诺依曼架构，能够进行通用计算。也就是说，它是一个通用图灵机。 NVM受vnTinyRAM和RISC-V ISA的启发，但与后者不同，它被设计为最大化证明者性能。

NVM特点：

• 简单的CPU架构：简单的32位指令集，40条指令，简化的指令解码。
• 简单的内存模型：简单的32位地址空间，单一堆栈和堆，通过Merkle树和Poseidon哈希增量证明。
• 简单的I/O模型：简单的32位输入/输出模型，公共输入(x)、私有输入(w)和公共输出(y)的单一通道。
• 可扩展性：NVM可以通过自定义指令扩展，我们称之为zkVM协处理器。

1.3 StarCore zkVM协处理器

zkVM协处理器的概念非常强大。虽然理论上任何程序都可以作为CPU指令序列进行证明， 但在这种模型中证明许多类型的简单程序在实际上是不可行的。例如，在虚拟机模型中证明 单个SHA-256哈希将涉及证明大约64,000个CPU周期，这些周期在软件中模拟SHA-256函数。 相比之下，直接在VM抽象外证明手动编写的SHA-256哈希电路（类似于ASIC）只需要证明约30,000个约束， 这需要大约少1000倍的计算。这就是抽象的代价。

StarCore zkVM引入了zkVM协处理器的概念，其中证明NVM指令集自定义协处理器扩展的成本 仅当客户程序执行该特定协处理器时才由证明者支付。这使StarCore zkVM能够维持具有小型图灵完备ISA的 对开发者友好的CPU抽象，同时允许指令集上的类ASIC扩展，只有在实际执行这些指令时才支付其成本。

1.4 StarCore网络

StarCore项目寻求实现互联网规模的可验证计算。为此，我们提出了一个系统， 通过该系统，StarCore zkVM的总吞吐量可以提高几个数量级。 我们称这个系统为StarCore网络，它聚合了异构计算机网络的集体CPU/GPU能力， 以实例化StarCore zkVM的极其并行化的大规模证明生成系统。 这允许zkVM以与网络集体计算能力成比例的规模（以每秒证明的CPU周期数衡量）运行。

互联网上的大规模志愿计算在一些著名项目中取得了巨大成功。这些项目利用数百万志愿者的 集体计算能力解决大规模科学问题，这些系统的总计算能力以FLOPS（每秒浮点运算次数）计量。 例如：

• 1996年的Great Internet Mersenne Prime Search (GIMPS)，在2004年初达到14万亿FLOPS。
• 1999年NASA的SETI@Home，获得了2008年吉尼斯世界纪录，成为历史上最大的计算，达到668万亿FLOPS。
• 2000年斯坦福大学的Folding@Home，达到2.43百亿亿FLOPS，成为第一个百亿亿计算系统。

StarCore网络寻求做同样的事情，但针对的是可验证计算问题。因此，StarCore网络可以被视为 分布式可验证超级计算机，允许zkVM以与网络集体计算能力成比例的方式扩展其吞吐量。

1.5 开源实现

那么已经实现了什么？StarCore zkVM和StarCore网络是完全开源的，两者都用Rust实现。这些包括：

1. 证明累积：Nova、CycleFold和HyperNova - 在2022年微软研究院原始Nova开源实现之后， 我们提供了Nova和后续证明累积系统的第一个生产级实现，全部从头开始在arkworks中构建。
2. StarCore zkVM - StarCore zkVM的实现，以及执行序列中的所有步骤：生成、编译（见证提取）、 执行、折叠和证明压缩。
3. StarCore虚拟机 - NVM的实现及其在R1CS中的算术版本，带有用于内存检查的Merkle证明， 以及RISC-V到NVM的编译器。
4. StarCore网络 - StarCore网络的开源实现，具有三种不同类型的节点。
5. StarCore证明压缩序列 - 我们提供一个Nova友好的zkSNARK和Zeromorph多项式承诺方案的实现。

1.6 示例

#![no_std]
#![no_main]

#[starcore::main]
fn fib(n: u32) -> u32 {
  match n {
    0 => 1,
    1 => 1,
    _ => fib(n - 1) + fib(n - 2),
  }
}

示例1: 可在StarCore zkVM上证明的Rust程序示例。

2. 介绍

图灵机。在他1936年的开创性论文中，图灵引入了图灵机，这是对计算概念的形式化。 他首先观察到通用计算是可能的，并证明了通用图灵机的存在，这是一种可以模拟任何其他机器执行的机器。 同样，Kurt Gödel、Alonzo Church和其他人也在20世纪30年代初期达到了计算的形式定义， 所有这些最终在表达能力上是相同的。

冯·诺依曼架构。通用图灵机的概念很快导致其他科学家，如冯·诺依曼，构建实现。 今天，实质上所有数字计算机都遵循"冯·诺依曼架构"。StarCore VM也遵循冯·诺依曼架构。

经典证明。1956年，Gödel给冯·诺依曼写了一封信，他确定如果存在一个能够有效证明数学定理的实用机器， "将会产生最大规模的后果"。正如我们将看到的，这个概念接近于证明计算。Gödel本质上提出了我们今天所知道的 （仍未解决的）P = NP问题，它处理确定性（超多项式时间）证明者（即NP类）、（多项式时间）验证者（即P类） 和证明概念之间的关系。

零知识证明。快进到1985年，（零知识）交互式证明的故事始于麻省理工学院， 在Goldwasser、Micali和Rackoff的论文中，该论文引入了IP类，这是NP的泛化，允许证明者和验证者之间的随机性和交互。 这从根本上改变了证明本身的概念。他们同样引入的零知识定义，考虑除了其有效性外不泄露任何内容的证明。 他们的论文赢得了第一个Gödel奖。

从那时起，一系列研究爆发性地引入了其他证明概念，如亚瑟-梅林协议、MIPs、PCPs、IOPs、NIZK、知识证明、简洁论证和CS证明， 以及（zk）-SNARKs。有关零知识证明历史和现代技术的简短回顾，请参见第3节。

StarCore项目建立在这些工作和自零知识证明发明以来近四十年的研究基础上。我们相信，由于最近的科学进步， 互联网时代真正可扩展的零知识技术已经近在眼前。

2.1 为什么零知识证明仍然不实用？

ASIC方法。当前计算零知识证明的典型方法包括手动编写算术电路（例如R1CS、Plonkish、AIR等）， 通过Bellman或arkworks等库，或通过更高级别的DSL（例如Circom、Zokrates、Noir、Leo等）与DSL到电路编译器一起， 然后用zk-SNARK证明电路。对于zk-SNARK，Groth16由于实际的以太坊兼容性和其小的证明大小而在实践中被最广泛使用， 其次是Halo和Halo2。ASIC方法在概念上类似于为给定计算设计自定义ASIC，然后用zk-SNARK证明ASIC的执行。

缺点。不幸的是，这种方法非常容易出错，需要高度的专业知识。此外，DSL方法对程序施加静态界限 （例如，数组和循环必须具有在编译时已知的固定大小），不支持依赖于输入的控制流和内存访问，并且不允许自修改代码。 这种方法还导致为每个程序生成不同的电路，这需要每次重新部署新的验证器代码，这在实践中是非常不切实际的， 通常也是不希望的操作。

这些在实践中都是很大的限制：即使开发者愿意学习新的DSL或手动编写算术电路（这是一项高度非平凡的任务）， 他们也会发现大多数程序在这个模型中实际上是不可计算的。

CPU方法。2014年引入的现代方法是证明计算机程序而不是算术电路。这是通过模拟CPU或虚拟机（VM）来完成的， 方法是将完整的VM实现为单一通用电路。在这个模型中，通用电路的大小N与指令集中指令大小之和成比例。 然后，通过将许多此类通用电路粘合在一起，证明VM的一系列状态转换，直到程序运行时间的静态界限T， 然后用SNARK证明(N·T)大小的电路。这种方法由TinyRAM引入，并已导致行业应用，如Cairo zkVM和其他zkEVM项目。

优点。这种方法的优点是更好的开发者体验。为预先存在或明确定义的ISA编写程序要简单得多， 因为开发者可以利用工具和编译器基础设施。此外，由于电路是通用的，只需部署单一验证器（这在实践中是重要的优势）。 进一步，为给定VM（如EVM）编写通用电路的大量工作（这需要几个月或几年时间完成）只需完成一次， 然后任何该ISA的程序，直到指定时间界限T，都可以被证明。

缺点。然而，CPU方法有几个缺点，主要与性能和可扩展性有关：

1. 有界计算。这种方法需要对所有可能程序执行的运行时间决定一个静态界限T。 证明超过T周期需要生成新的公共参数并部署新的验证器，或进行SNARK递归。
2. SNARK递归的高成本。第二个选项包括证明T大小的执行块， 并通过将完整的SNARK验证器本身写为电路，并证明SNARK验证器在步骤i接受来自步骤i-1的SNARK证明， 从而"粘合"证明。这种方法非常昂贵，众所周知在实践中是不切实际的。
3. 由于模拟导致性能低下。VM抽象导致比不使用VM的电路大得多。此外，证明T个通用电路的副本 需要大型证明者机器，具有非常大的内存。
4. 实际安全性。这些技术很难审计。即使实现了整个VM作为电路和完整的SNARK验证器作为电路， 仍然很难说服自己电路实际上是正确实现的，没有漏洞。

2.2 StarCore系统

StarCore系统解决了上述可扩展性限制：

• StarCore网络。该网络通过无界的无SNARK递归和高速证明聚合解决了问题(1)和(2)。 换句话说，StarCore zkVM可以连接到StarCore网络，在分布式证明者网络中执行无界计算的大规模并行证明， 该网络对证明进行分区并增量聚合。
• StarCore zkVM。StarCore zkVM通过NVM和zkVM协处理器的使用解决了问题(3)和(4)， 这允许NVM指令集中加速指令的类ASIC性能。这允许StarCore zkVM维持具有小型图灵完备ISA的对开发者友好的CPU抽象， 同时允许指令集上的类ASIC扩展。此外，NVM非常简单，可审计且高度模块化。

我们希望这两个系统结合起来，将使开发者能够专注于以任何编程语言声明性地编写他们想要证明的内容， 并在几秒钟内收到证明。

我们相信用户不应该思考复杂的（且高度非平凡的）安全性和性能属性，这些属性隐藏在40多年的零知识研究 和相关高性能工程背后，而这些正是驱动StarCore系统的动力。

理论核心

StarCore的理论核心建立在零知识证明和可验证计算的基础上，融合了多项创新技术：

零知识证明基础

零知识证明允许一方（证明者）向另一方（验证者）证明某个陈述是真实的，而无需透露除了该陈述为真这一事实之外的任何信息。 StarCore采用了最先进的零知识证明技术，包括递归证明系统和高效的多项式承诺方案。

增量可验证计算

增量可验证计算（IVC）是StarCore的关键创新，它允许证明被增量构建和更新，无需重新计算整个证明。 这使得StarCore能够处理无界计算，并实现前所未有的证明生成效率。

分布式证明生成

StarCore网络采用分布式证明生成架构，将证明任务分解为可并行执行的子任务，然后通过高效的证明聚合机制 将这些子证明组合成完整的证明。这种方法显著提高了系统的吞吐量和可扩展性。

思维导图：StarCore技术架构

StarCore系统
 ├── StarCore zkVM
 │   ├── 核心组件
 │   │   ├── NVM (Native Virtual Machine)
 │   │   │   ├── 简化的32位指令集
 │   │   │   ├── 优化的内存模型
 │   │   │   └── I/O通道
 │   │   ├── 证明生成引擎
 │   │   │   ├── 递归证明系统
 │   │   │   ├── 多项式承诺方案
 │   │   │   └── 证明压缩
 │   │   └── zkVM协处理器
 │   │       ├── 密码学原语
 │   │       ├── 哈希函数
 │   │       └── 自定义扩展
 │   └── 开发工具
 │       ├── Rust编译器
 │       ├── 调试工具
 │       └── 性能分析器
 └── StarCore网络
     ├── 节点类型
     │   ├── 证明生成节点
     │   ├── 聚合节点
     │   └── 验证节点
     ├── 网络协议
     │   ├── 任务分配
     │   ├── 证明聚合
     │   └── 共识机制
     └── 经济模型
         ├── 激励机制
         ├── 资源定价
         └── 安全保障

StarCore系统思维导图 - 展示核心组件及其关系