斯巴达人：无需可信设置的快速 zkSNARKs

斯巴达人是一个高速零知识证明系统，是一种密码学原语，允许证明者向验证者证明一个数学陈述的有效性，而不泄露任何除陈述有效性之外的信息。此仓库提供了 libspartan, 一个 Rust 库，实现了零知识简短非交互式知识论证（zkSNARK），这是一种具有简短证明和快速验证时间的零知识证明系统。斯巴达人证明系统的详细情况见我们于 论文，该论文发表在 CRYPTO 2020 上。此库中实现的斯巴达人变体的安全性基于随机预言模型中的离散对数问题。

一个简单的示例应用是证明知道一个秘密 s，使得 H(s) == d 对于一个公共 d，其中 H 是一个加密哈希函数（例如，SHA-256，Keccak）。一个更复杂的应用是支持数据库的云服务，该服务生成正确的状态机转换证明，以供审计。请参阅此 论文 的概述和此 论文 的详细情况。

请注意，此库尚未接受安全审查或审计。

亮点

现在，我们突出斯巴达人的独特特性。

• 无“有毒”废物：斯巴达人是一个 透明 的 zkSNARK，并且不需要可信设置。因此，它不涉及任何必须保密的陷阱门或需要多党仪式来生成公共参数。

• 通用性：Spartan可以生成任意NP语句的证明。libspartan支持将NP语句表达为秩1约束可满足性（R1CS）实例，这是一种流行的语言，它可以从感兴趣的通用程序中高效地转换并构建编译器工具链。

• 亚线性验证成本：Spartan是第一个对于任意NP语句（例如R1CS）具有亚线性验证成本的透明证明系统。

• 标准化安全：Spartan的安全性依赖于随机预言模型中计算离散对数（一个标准的密码学假设）的难度。libspartan使用ristretto255，这是建立在curve25519（一个高速椭圆曲线）之上的素性群抽象。我们使用curve25519-dalek来在ristretto255上进行算术。

• 最先进的性能：在透明SNARK中，Spartan提供了最快的证明者，速度比基准提高了36-152倍，生成的证明短1.2-416倍，并且具有最低的验证时间，速度提高了3.6-1326倍。唯一的例外是Bulletproofs的证明大小，但Bulletproofs在理论性和实际验证速度上都要慢。

实现细节

libspartan使用merlin来自动化Fiat-Shamir转换。我们还引入了一种新类型RandomTape，它扩展了merlin中的Transcript，允许证明者的内部方法在不需要在代码中创建OsRng对象的情况下，使用其私有转录本产生私有随机数。每个由库生成的证明都使用从OsRng的新随机种子初始化一个RandomTape对象。

示例

要将libspartan导入您的Rust项目，请将以下依赖项添加到Cargo.toml

spartan = "0.8.0"

以下示例展示了如何使用libspartan创建和验证一个SNARK证明。我们的一些公共API的风格受到了我们使用的底层crates的启发。

extern crate libspartan;
extern crate merlin;
use libspartan::{Instance, SNARKGens, SNARK};
use merlin::Transcript;
fn main() {
    // specify the size of an R1CS instance
    let num_vars = 1024;
    let num_cons = 1024;
    let num_inputs = 10;
    let num_non_zero_entries = 1024;

    // produce public parameters
    let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);

    // ask the library to produce a synthentic R1CS instance
    let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);

    // create a commitment to the R1CS instance
    let (comm, decomm) = SNARK::encode(&inst, &gens);

    // produce a proof of satisfiability
    let mut prover_transcript = Transcript::new(b"snark_example");
    let proof = SNARK::prove(&inst, &comm, &decomm, vars, &inputs, &gens, &mut prover_transcript);

    // verify the proof of satisfiability
    let mut verifier_transcript = Transcript::new(b"snark_example");
    assert!(proof
      .verify(&comm, &inputs, &mut verifier_transcript, &gens)
      .is_ok());
    println!("proof verification successful!");
}

以下是一个使用Spartan证明系统的NIZK变体的示例

extern crate libspartan;
extern crate merlin;
use libspartan::{Instance, NIZKGens, NIZK};
use merlin::Transcript;
fn main() {
    // specify the size of an R1CS instance
    let num_vars = 1024;
    let num_cons = 1024;
    let num_inputs = 10;

    // produce public parameters
    let gens = NIZKGens::new(num_cons, num_vars, num_inputs);

    // ask the library to produce a synthentic R1CS instance
    let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);

    // produce a proof of satisfiability
    let mut prover_transcript = Transcript::new(b"nizk_example");
    let proof = NIZK::prove(&inst, vars, &inputs, &gens, &mut prover_transcript);

    // verify the proof of satisfiability
    let mut verifier_transcript = Transcript::new(b"nizk_example");
    assert!(proof
      .verify(&inst, &inputs, &mut verifier_transcript, &gens)
      .is_ok());
    println!("proof verification successful!");
}

最后，我们提供了一个示例，指定了一个自定义的R1CS实例，而不是使用合成实例

#![allow(non_snake_case)]
extern crate curve25519_dalek;
extern crate libspartan;
extern crate merlin;
use curve25519_dalek::scalar::Scalar;
use libspartan::{InputsAssignment, Instance, SNARKGens, VarsAssignment, SNARK};
use merlin::Transcript;
use rand::rngs::OsRng;

fn main() {
  // produce a tiny instance
  let (
    num_cons,
    num_vars,
    num_inputs,
    num_non_zero_entries,
    inst,
    assignment_vars,
    assignment_inputs,
  ) = produce_tiny_r1cs();

  // produce public parameters
  let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);

  // create a commitment to the R1CS instance
  let (comm, decomm) = SNARK::encode(&inst, &gens);

  // produce a proof of satisfiability
  let mut prover_transcript = Transcript::new(b"snark_example");
  let proof = SNARK::prove(
    &inst,
    &comm,
    &decomm,
    assignment_vars,
    &assignment_inputs,
    &gens,
    &mut prover_transcript,
  );

  // verify the proof of satisfiability
  let mut verifier_transcript = Transcript::new(b"snark_example");
  assert!(proof
    .verify(&comm, &assignment_inputs, &mut verifier_transcript, &gens)
    .is_ok());
  println!("proof verification successful!");
}

fn produce_tiny_r1cs() -> (
 usize,
 usize,
 usize,
 usize,
 Instance,
 VarsAssignment,
 InputsAssignment,
) {
  // We will use the following example, but one could construct any R1CS instance.
  // Our R1CS instance is three constraints over five variables and two public inputs
  // (Z0 + Z1) * I0 - Z2 = 0
  // (Z0 + I1) * Z2 - Z3 = 0
  // Z4 * 1 - 0 = 0

  // parameters of the R1CS instance rounded to the nearest power of two
  let num_cons = 4;
  let num_vars = 5;
  let num_inputs = 2;
  let num_non_zero_entries = 5;

  // We will encode the above constraints into three matrices, where
  // the coefficients in the matrix are in the little-endian byte order
  let mut A: Vec<(usize, usize, [u8; 32])> = Vec::new();
  let mut B: Vec<(usize, usize, [u8; 32])> = Vec::new();
  let mut C: Vec<(usize, usize, [u8; 32])> = Vec::new();

  // The constraint system is defined over a finite field, which in our case is
  // the scalar field of ristreeto255/curve25519 i.e., p =  2^{252}+27742317777372353535851937790883648493
  // To construct these matrices, we will use `curve25519-dalek` but one can use any other method.

  // a variable that holds a byte representation of 1
  let one = Scalar::one().to_bytes();

  // R1CS is a set of three sparse matrices A B C, where is a row for every
  // constraint and a column for every entry in z = (vars, 1, inputs)
  // An R1CS instance is satisfiable iff:
  // Az \circ Bz = Cz, where z = (vars, 1, inputs)

  // constraint 0 entries in (A,B,C)
  // constraint 0 is (Z0 + Z1) * I0 - Z2 = 0.
  // We set 1 in matrix A for columns that correspond to Z0 and Z1
  // We set 1 in matrix B for column that corresponds to I0
  // We set 1 in matrix C for column that corresponds to Z2
  A.push((0, 0, one));
  A.push((0, 1, one));
  B.push((0, num_vars + 1, one));
  C.push((0, 2, one));

  // constraint 1 entries in (A,B,C)
  A.push((1, 0, one));
  A.push((1, num_vars + 2, one));
  B.push((1, 2, one));
  C.push((1, 3, one));

  // constraint 3 entries in (A,B,C)
  A.push((2, 4, one));
  B.push((2, num_vars, one));

  let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C).unwrap();

  // compute a satisfying assignment
  let mut csprng: OsRng = OsRng;
  let i0 = Scalar::random(&mut csprng);
  let i1 = Scalar::random(&mut csprng);
  let z0 = Scalar::random(&mut csprng);
  let z1 = Scalar::random(&mut csprng);
  let z2 = (z0 + z1) * i0; // constraint 0
  let z3 = (z0 + i1) * z2; // constraint 1
  let z4 = Scalar::zero(); //constraint 2

  // create a VarsAssignment
  let mut vars = vec![Scalar::zero().to_bytes(); num_vars];
  vars[0] = z0.to_bytes();
  vars[1] = z1.to_bytes();
  vars[2] = z2.to_bytes();
  vars[3] = z3.to_bytes();
  vars[4] = z4.to_bytes();
  let assignment_vars = VarsAssignment::new(&vars).unwrap();

  // create an InputsAssignment
  let mut inputs = vec![Scalar::zero().to_bytes(); num_inputs];
  inputs[0] = i0.to_bytes();
  inputs[1] = i1.to_bytes();
  let assignment_inputs = InputsAssignment::new(&inputs).unwrap();

  // check if the instance we created is satisfiable
  let res = inst.is_sat(&assignment_vars, &assignment_inputs);
  assert_eq!(res.unwrap(), true);

  (
    num_cons,
    num_vars,
    num_inputs,
    num_non_zero_entries,
    inst,
    assignment_vars,
    assignment_inputs,
  )
 }

有关更多示例，请参阅本存储库中的examples/目录。

构建libspartan

安装rustup

使用rustup切换到nightly Rust

rustup default nightly

克隆存储库

git clone https://github.com/Microsoft/Spartan
cd Spartan

构建libspartan的公共API文档

cargo doc

运行测试

RUSTFLAGS="-C target_cpu=native" cargo test

构建libspartan

RUSTFLAGS="-C target_cpu=native" cargo build --release

注意：我们默认启用了curve25519-dalek中的SIMD指令，因此如果构建失败，请从Cargo.toml中移除"simd_backend"功能参数。

支持的功能

• std：启用std功能（默认启用）
• simd_backend：启用curve25519-dalek的simd功能（默认启用）
• profile：启用细粒度的性能分析信息（下面将说明其使用方法）

WASM支持

libspartan 依赖于 rand::OsRng（内部使用 getrandom crate），它对 wasm32-wasi 提供开箱即用的支持。

对于目标 wasm32-unknown-unknown，禁用 spartan 的默认功能，并添加对 getrandom 的直接依赖，同时启用 wasm-bindgen 功能。

[dependencies]
spartan = { version = "0.7", default-features = false }
# since spartan uses getrandom(rand's OsRng), we need to enable 'wasm-bindgen'
# feature to make it feed rand seed from js/nodejs env
# https://docs.rs/getrandom/0.1.16/getrandom/index.html#support-for-webassembly-and-asmjs
getrandom = { version = "0.1", features = ["wasm-bindgen"] }

性能

端到端基准测试

libspartan 包含两个基准测试：benches/nizk.rs 和 benches/snark.rs。如果您在研究论文中报告 Spartan 的性能，我们建议使用这些基准测试以提高准确性，而不是使用以下列出的细粒度分析。

运行端到端基准测试

RUSTFLAGS="-C target_cpu=native" cargo bench

细粒度分析

使用 profile 功能构建 libspartan。它创建两个分析器：./target/release/snark 和 ./target/release/nizk。

这些分析器报告的性能如以下所示（对于不同的 R1CS 实例大小）。报告的性能是在 Windows 10 上的 WSL2 中运行的 Ubuntu 20.04 上，使用英特尔酷睿 i7-1065G7 单个 CPU 核心的 Microsoft Surface Laptop 3 运行分析器得出的。参见我们论文的第 9 节，了解这与文献中其他 zkSNARK 的比较。

$ ./target/release/snark
Profiler:: SNARK
  * number_of_constraints 1048576
  * number_of_variables 1048576
  * number_of_inputs 10
  * number_non-zero_entries_A 1048576
  * number_non-zero_entries_B 1048576
  * number_non-zero_entries_C 1048576
  * SNARK::encode
  * SNARK::encode 14.2644201s
  * SNARK::prove
    * R1CSProof::prove
      * polycommit
      * polycommit 2.7175848s
      * prove_sc_phase_one
      * prove_sc_phase_one 683.7481ms
      * prove_sc_phase_two
      * prove_sc_phase_two 846.1056ms
      * polyeval
      * polyeval 193.4216ms
    * R1CSProof::prove 4.4416193s
    * len_r1cs_sat_proof 47024
    * eval_sparse_polys
    * eval_sparse_polys 377.357ms
    * R1CSEvalProof::prove
      * commit_nondet_witness
      * commit_nondet_witness 14.4507331s
      * build_layered_network
      * build_layered_network 3.4360521s
      * evalproof_layered_network
        * len_product_layer_proof 64712
      * evalproof_layered_network 15.5708066s
    * R1CSEvalProof::prove 34.2930559s
    * len_r1cs_eval_proof 133720
  * SNARK::prove 39.1297568s
  * SNARK::proof_compressed_len 141768
  * SNARK::verify
    * verify_sat_proof
    * verify_sat_proof 20.0828ms
    * verify_eval_proof
      * verify_polyeval_proof
        * verify_prod_proof
        * verify_prod_proof 1.1847ms
        * verify_hash_proof
        * verify_hash_proof 81.06ms
      * verify_polyeval_proof 82.3583ms
    * verify_eval_proof 82.8937ms
  * SNARK::verify 103.0536ms

$ ./target/release/nizk
Profiler:: NIZK
  * number_of_constraints 1048576
  * number_of_variables 1048576
  * number_of_inputs 10
  * number_non-zero_entries_A 1048576
  * number_non-zero_entries_B 1048576
  * number_non-zero_entries_C 1048576
  * NIZK::prove
    * R1CSProof::prove
      * polycommit
      * polycommit 2.7220635s
      * prove_sc_phase_one
      * prove_sc_phase_one 722.5487ms
      * prove_sc_phase_two
      * prove_sc_phase_two 862.6796ms
      * polyeval
      * polyeval 190.2233ms
    * R1CSProof::prove 4.4982305s
    * len_r1cs_sat_proof 47024
  * NIZK::prove 4.5139888s
  * NIZK::proof_compressed_len 48134
  * NIZK::verify
    * eval_sparse_polys
    * eval_sparse_polys 395.0847ms
    * verify_sat_proof
    * verify_sat_proof 19.286ms
  * NIZK::verify 414.5102ms

许可证

请参阅 LICENSE

贡献

请参阅 CONTRIBUTING