OpenZKP Stark

STARK 零知识证明的开源实现。

STARKs 是由 Eli Ben-Sasson、Michael Riabzev、Lior Goldberg 等人和 Starkware Ltd. 开发的一系列协议。实现的特定 Stark 协议变体是（Starkdex alpha 使用的近似）一个。此 Stark 协议具有 "StarkDEX 深度分析" 第 III 部分（见 参考文献）中描述的优化。

示例

use zkp_stark::{*, primefield::*};

struct FibonacciClaim {
    index: usize,
    value: FieldElement,
}

impl Verifiable for FibonacciClaim {
    fn constraints(&self) -> Constraints {
        use RationalExpression::*;

        // Seed
        let mut seed = self.index.to_be_bytes().to_vec();
        seed.extend_from_slice(&self.value.as_montgomery().to_bytes_be());

        // Constraint repetitions
        let trace_length = self.index.next_power_of_two();
        let g = Constant(FieldElement::root(trace_length).unwrap());
        let on_row = |index| (X - g.pow(index)).inv();
        let every_row = || (X - g.pow(trace_length - 1)) / (X.pow(trace_length) - 1.into());

        let mut c = Constraints::from_expressions((trace_length, 2), seed, vec![
            (Trace(0, 1) - Trace(1, 0)) * every_row(),
            (Trace(1, 1) - Trace(0, 0) - Trace(1, 0)) * every_row(),
            (Trace(0, 0) - 1.into()) * on_row(0),
            (Trace(0, 0) - (&self.value).into()) * on_row(self.index),
        ])
        .unwrap()
    }
}

impl Provable<&FieldElement> for FibonacciClaim {
    fn trace(&self, witness: &FieldElement) -> TraceTable {
        let trace_length = self.index.next_power_of_two();
        let mut trace = TraceTable::new(trace_length, 2);
        trace[(0, 0)] = 1.into();
        trace[(0, 1)] = witness.clone();
        for i in 0..(trace_length - 1) {
            trace[(i + 1, 0)] = trace[(i, 1)].clone();
            trace[(i + 1, 1)] = &trace[(i, 0)] + &trace[(i, 1)];
        }
        trace
    }
}

pub fn main() {
    let claim = FibonacciClaim {
        index: 5000,
        value: FieldElement::from_hex_str("069673d708ad3174714a2c27ffdb56f9b3bfb38c1ea062e070c3ace63e9e26eb"),
    };
    let secret = FieldElement::from(42);
    let proof = claim.prove(&secret).unwrap();
    claim.verify(&proof).unwrap();
}

在 /examples 文件夹中还有更多示例

• small_fib 和 large_fib。
• mimc_cubic 由编织工协会提供（来源）。
• mimc_quadratic 由编织工协会提供（来源）。
• vdf 由 Matter Labs 提供（来源）。
• pedersen_merkle 由 Starkware 提供。

功能和限制

功能

简单的接口。 公共接口简单，被认为是 semver-stable。预期未来版本将添加功能而不会破坏此接口。

简洁的证明。 对于给定的安全性参数，证明大小接近最小值。在此处取得重大改进将需要创新约束系统设计或底层加密方式。

良好的性能。 证明的所有步骤都使用渐近最优算法，所有主要步骤都使用多线程。没有硬性内存要求。我们预计通过微调可以获得相当多的性能改进，但我们不期望有数量级的改进。

WebAssembly 支持。 验证器可以在不使用 Rust std 库的 WebAssembly 环境中使用。证明者也可以工作，但不是优先考虑的事项。

限制

无高级语言。 使用它们的代数表达式指定约束。这要求库用户进行复杂且仔细的设计，容易出错，导致不安全的系统。高级语言将有助于简化开发并提高安全性，并促进组件的重用。

无全面的安全审计。 虽然开发时考虑了最佳安全实践，但仍处于早期阶段，尚未达到生产级系统所需的大量专家同行评审。

没有完美的零知识。 当前实现提供简洁的证明，但不是完美的零知识。虽然非平凡，但理论上可能了解一些关于秘密的信息。实现完美零知识是可能的，并且可以实施。

没有抵抗侧信道。 实现优先考虑性能而不是侧信道抵抗。虽然这在零知识证明系统中很常见，但你应该意识到这可能会泄露中间计算。侧信道抵抗可以实施。

硬编码的字段和哈希。 当前实现使用特定的素域和特定的哈希函数。这些是为了在以太坊虚拟机中的验证而优化的。这可以推广到其他针对其他用例优化的原语。

参考文献

• Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev (2018)。"快速Reed-Solomon交互式接近性证明"。 eccc.weizmann.ac.il
• Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev (2018)。"可扩展、透明和后量子安全的计算完整性"。 eprint.iacr.org
• Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf (2019)。"DEEP-FRI：超出框外采样提高正确性"。 arxiv.org
• Starkware的stark math和starkdex系列。
• Starkware的Starkdex 验证合约。
• 由Starkware和Matter Labs提供的资源概述。

相关项目

• Hodor由Matter Labs。
• genSTARK由Guild of Weavers。
• libSTARK由Ben-Sasson等人。
• stark由Computable Labs。
• mimc_stark由Vitalik Buterin。