19个不稳定版本 (8个破坏性)
| 0.9.0 | 2024年5月9日 |
|---|---|
| 0.8.3 | 2024年3月15日 |
| 0.8.1 | 2024年2月21日 |
| 0.7.1 | 2023年10月29日 |
| 0.2.0 | 2021年8月24日 |
#530 in 密码学
10,204 每月下载量
在 21 个crate中使用（4 个直接使用）
1MB
17K SLoC
Winterfell STARK证明器
此crate包含Winterfell STARK证明器。
此证明器可以使用STARK协议生成计算完整性的证明。证明器支持多线程证明生成（包括多线程执行跟踪生成），但限于单台机器。
使用方法
要生成一个证明来证明计算执行正确，您需要执行以下操作
- 为您的计算定义代数中间表示（AIR）。这可以通过实现
Air特质来完成（有关更多信息，请参阅air crate）。 - 为您的计算定义执行跟踪。这可以通过实现
Trace特质来完成。或者，您可以使用已实现Trace特质的TraceTable结构体，在通用实现适用于您的用例的情况下。 - 执行您的计算并记录其执行跟踪。
- 通过实现
Prover特质来定义您的证明器（#Prover）。然后执行Prover::prove()函数，将前一步生成的跟踪作为参数传递给它。该函数将返回一个Proof实例。
生成的Proof对象可以被序列化并发送到验证器进行验证。证明的大小取决于给定计算的具体情况，但对于大多数计算，它应该在15 KB（对于非常小的计算）和300 KB（对于非常大的计算）之间。
证明生成时间也高度依赖于特定计算的细节，同时也取决于用于生成证明的机器的能力（即CPU核心数和内存带宽）。有关一些高级基准测试，请参阅根README中的性能部分。
验证者
为了为某个计算定义一个验证者，你需要实现Prover特质。这个特质指定了计算的AIR（通过Air关联类型）以及其执行迹形的形状（通过Trace关联类型）。这个特质还要求指定几个其他关联类型，但对于其中大部分，Winterfell都提供了默认实现。除此之外，验证者必须为三个方法提供实现
get_pub_inputs()，它描述了如何从一个执行迹形的实例中提取一组公共输入。这些输入需要与验证者共享，以便它们可以验证证明。new_trace_lde()，它构建一个新的迹形低度扩展实例。除非你的验证者需要实现执行低度扩展的专用优化，否则此方法可以仅返回Winterfell提供的默认迹形低度扩展。new_evaluator()，它构建一个新的AIR约束评估器实例。除非你的验证者需要实现评估约束的专用优化，否则此方法可以仅返回Winterfell提供的默认约束评估器。options()，它定义了在证明生成期间使用的STARK协议参数。这些参数包括查询数、膨胀因子、研磨因子、在证明生成期间使用的哈希函数等。这些参数的值直接影响证明生成时间、证明大小和证明安全级别。有关更多信息，请参阅air crate。
验证者公开了一个prove()方法，可以使用它使用给定的执行迹形作为证据生成一个STARK证明。
执行迹形
执行迹形是一个二维矩阵，其中每一行表示计算在特定时间点的状态，每一列对应于在整个计算步骤中跟踪的代数寄存器。定义计算AIR的大部分工作是如何高效地表示计算的执行迹形。有关更多信息，请查看examples crate。
在Winterfell中，执行迹形可以通过实现Trace特质的任何结构来表示。这个特质定义了一些属性访问器（例如，宽度和长度）并定义了将结构转换为列向量的方法。
在大多数情况下，为执行迹形定义自定义结构可能是过度设计的。因此，Winterfell还提供了一个已实现Trace特质的TraceTable结构。有三种方式来实例化这个结构。
首先，您可以使用 TraceTable::init() 函数，该函数接受一组向量作为参数，其中每个向量包含跟踪给定列的值。这种方法允许您按需构建执行跟踪，只要它满足基本执行跟踪要求。这些要求包括
- 执行跟踪中所有列的长度必须相同。
- 列的长度必须是2的某个幂。
另一种方法是使用 TraceTable 结构体，通过 TraceTable::new() 函数实例化，该函数接受跟踪宽度和长度作为参数。此函数将为跟踪分配内存，但不会用数据填充它。要填充执行跟踪，您可以使用 fill() 方法，该方法接受两个闭包作为参数
- 第一个闭包负责初始化计算的第一个状态（执行跟踪的第一行）。
- 第二个闭包接收执行跟踪的先前状态作为输入，并必须将其更新为计算的下一个状态。
此第二种选项通常更易于使用，并且也便于实现并发跟踪生成。
特性功能
此crate可以编译以下特性
std- 默认启用并依赖于Rust标准库。concurrent- 意味着启用std并启用多线程证明生成。no_std- 不依赖于Rust标准库，并启用编译到WebAssembly。async- 将Prover特性定义的所有函数转换为async函数。
要使用 no_std 编译，请通过 --no-default-features 标志禁用默认功能。
并发证明生成
当此crate编译时启用 concurrent 特性，证明生成将在多个线程中执行。线程数可以通过 RAYON_NUM_THREADS 环境变量配置，通常默认为机器上的逻辑核心数。
对于由许多小型独立计算组成的计算，我们可以通过并行构建跟踪的片段来生成整个计算的执行跟踪，然后将这些片段连接起来。
为此，TraceTable 结构体公开了 fragments() 方法，该方法接受片段长度作为参数，将执行跟踪分解为大小相等的片段，并返回这些片段的迭代器。然后，您可以使用片段的 fill() 方法并行填充所有片段。片段的 fill() 方法的语义与执行跟踪的 fill() 方法相同。
许可
此项目是 MIT 许可。
依赖关系
~4.5MB
~87K SLoC