zekrom：面向零知识证明电路的算术化构造库 - 第一部分：arkworks-rs

zekrom 是一个开源的、面向 zkSNARK 电路的算术化构造库。它由 Kudelski Security 研究团队的 Laurent Thoeny 在其硕士论文工作中创建。zekrom 的目标是使用现代库（如 arkworks-rs 和 Halo2）分析电路中新构造的性能。本文描述 zekrom 在 arkworks-rs 中的实现，提供 Griffin、Neptune 和 Rescue Prime 哈希构造，还包括认证加密原语 Ciminion，以及使用最近提出的 SAFE API 实现的 Neptune 和 Griffin 的认证加密构造。

引言

zkSNARK（零知识简洁非交互式知识论证）允许我们向他人证明某个陈述为真，而无需透露任何相关信息。它们通常适用于需要证明一方（通常不被信任）的问责和合规性的领域。

zkSNARK 在许多领域都有应用。在金融领域，zkSNARK 被提议用于向雇主报告投资组合持仓、以私有方式汇总投资者信息、进行私有盲房地产拍卖，以及更广泛的私有监管解决方案。此外，zkSNARK 在数字支付应用中很受欢迎，支持私有交易（例如在 Zcash 网络中），并通过压缩分布式账本的大小来扩展其规模。

zkSNARK 还被提议用于电子投票、机器学习、证明某些漏洞的存在以及检测虚假信息。

这类解决方案通常使用构建块实现，如 Merkle 树证明、私有集合交集协议，以及为 zkSNARK 电路优化的哈希、加密和认证加密原语。

为什么选择 zekrom？

过去，我们描述了如何在 Circom、Aleo 和 gnark 等电路的 DSL 中实现面向算术化的构造。这次，我们专注于基于 Rust 的现代库（如 arkworks-rs 和 Halo2）来设计电路。在此过程中，我们实现了最近的哈希提案（如 Rescue Prime 和 Neptune），并探索了 SAFE API，以使用新颖的置换和海绵构造实现认证加密。

近年来提出了不同的证明系统（如 Groth16、Marlin、PLONK、Halo、Gemini 等），其主要目标是：减少证明大小、减少证明/验证时间，并最小化可信设置的需求。

此外，实现 zkSNARK 有多种方式，但它们的共同思想是构造必须在有限域上的算术电路中表示。这可以通过最新的领域特定语言（如 Circom 或 Leo）或使用库（如 gnark、Halo2 或 arkworks-rs）来实现。

在上述应用中，有时需要加密和哈希算法。然而，传统设计（如 SHA256 或 BLAKE2）在电路中的性能并不最优（主要是因为操作比特比操作域元素更昂贵）。这导致了面向算术化的构造的出现，这些新设计在本地架构和电路中都有更好的性能。我们创建 zekrom 的原因有三：

在许多情况下，面向算术化的方案的性能是基于理论约束数分析的，这些约束数将用于在目标证明系统中表示它们。这种方法没有考虑在特定证明系统中实现方案时可能遇到的困难。它们通常既没有在领域特定语言中实现，也没有在最先进的库中实现。另一个问题是，现有库中没有提供最新的方案（例如，Halo2 中的 Poseidon，circomlib 中的 Poseidon 和 MIMC）。因此，需要实现它们以进一步研究其性能。
这类构造通常需要生成参数以实现。为了帮助实践者，我们提供了可以帮助生成这些参数的代码。
通过提供 SAFE API 的通用实现，我们可以支持未来设计的新颖置换，并比较它们与其他提议构造在哈希和认证加密方面的性能。

构造

我们过去已经描述过 Griffin 和 Ciminion。

Rescue Prime：在 sponge 状态大小为三个域元素的情况下，它使用 Rescue-XLIX 置换。非线性层通过幂映射执行：首先使用小值 α，随后使用其逆 α^{-1}。其次，使用 MDS 矩阵作为线性层，最后，为了区分每一轮，向状态添加轮常数。

Neptune：由 Grassi 等人在 2021 年提出，Neptune 是基于广泛使用的 Poseidon 哈希函数研究的新设计。它略微修改了轮数，同时采用了置换中内部和外部轮的相同方法。然而，为了改善置换的乘法成本，两轮的设计都进行了修改。首先，外部轮中的 MDS 矩阵不同。其次，α 层对状态的两个元素应用 α 函数，其中 α 满足 α(x) = x^d 且 d 为整数。

这种外部 α 层的特定设计是 Neptune 能够降低成本的原因，相比之下，Poseidon 的简单外部层需要 d 次幂映射。

SAFE API

域元素海绵 API（SAFE）是 Khovratovich 等人提出的通用 API 提案，旨在统一使用置换的密码原语设计。它使用域元素而不是比特，通过常规海绵模式或双工模式的变体，从置换创建不同的密码原语。

Sponge 示例，吸收 4 个消息元素并挤压 3 个输出元素

SAFE API 通过使用 IOPattern（一种声明对海绵的调用的方式）消除了对填充方案的需求，但代价是要求输入长度已知。

SAFE 通过四种不同的调用使用：

START：使用 IOPattern 和域分隔符的哈希初始化海绵状态。
FINISH：在海绵作业完成时调用，它擦除内存并验证模式是否正确执行。
ABSORB(n) 和 SQUEEZE(n)：用于向海绵添加元素或从中检索信息。

例如，为了哈希一个包含 4 个元素的消息并产生长度为 1 个域元素的哈希，我们会执行：START、ABSORB(4)、SQUEEZE(1)、FINISH()。此外，我们可以使用海绵的双工模式来执行认证加密。

使用 zekrom for arkworks-rs 的示例电路

我们可以使用 zekrom 提供的 Neptune 构造来证明哈希原像的知识，如下电路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


use ark_ff::PrimeField;
use ark_r1cs_std::{
    fields::fp::FpVar,
    prelude::{AllocVar, EqGadget},
};
use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, SynthesisError};

use crate::{
    api::{Sponge, SpongeAPI},
    common::pattern::gen_hash_pattern,
};

use super::chip::*;

#[derive(Clone)]
pub struct NeptuneHashCircuit<F: PrimeField> {
    pub sponge: Sponge<NeptuneChip<F>>,
    pub message: Vec<F>,
    pub hash: F,
}

impl<F: PrimeField> NeptuneHashCircuit<F> {
    /// 使用海绵计算消息的哈希
    ///
    /// 它接受由块组成的消息，其中块是 F 中的域元素
    /// 它返回由 F 中一个元素组成的哈希
    /// 这个原型可以轻松扩展以支持更大的摘要大小
    /// 它遵循 [SAFE API 规范](https://hackmd.io/bHgsH6mMStCVibM_wYvb2w)
    pub fn hash(self, message: &[FpVar<F>]) -> Result<FpVar<F>, SynthesisError> {
        let pattern = gen_hash_pattern(message.len(), 1);

        let mut sponge = self.sponge;

        sponge.start(pattern, None);
        sponge.absorb(message.len() as u32, message);
        let hash = sponge.squeeze(1)[0].clone();
        let res = sponge.finish();
        assert!(res.is_ok(), "The sponge didn't finish properly!");

        Ok(hash)
    }
}

impl<F: PrimeField> ConstraintSynthesizer<F> for NeptuneHashCircuit<F> {
    fn generate_constraints(self, cs: ConstraintSystemRef<F>) -> Result<(), SynthesisError> {
        let mut v = Vec::with_capacity(self.message.len());

        for elem in self.message.iter() {
            v.push(FpVar::new_witness(cs.clone(), || Ok(elem))?);
        }
        let hash = FpVar::new_input(cs, || Ok(self.hash))?;
        let result = self.hash(&v)?;

        result.enforce_equal(&hash)?;

        Ok(())
    }
}

生成新参数

通常，面向算术化的构造需要在实现和部署原语之前生成不同的参数。为了帮助实践者生成它们，我们在 parameters.sage 中添加了不同的辅助函数。

Griffin

对于素数 p，轮常数、α 和 β 参数可以通过以下方式获取：

1
2
3
4
5
6
7
8


def get_params_griffin(p, seed, m, n):
    shake = SHAKE128.new()
    shake.update(bytes("Griffin", "ascii"))
    for v in seed:
        shake.update(bytes(v));
    consts = get_n_random_elements(p, n*m, shake)
    alpha, beta = get_alpha_beta(p, shake)
    return alpha, beta, consts

Neptune

对于素数 p，Neptune 的轮常数可以通过以下方式获取：

1
2
3
4
5
6
7
8
9


def get_round_constants_neptune(p, seed, m, n):
    shake = SHAKE128.new()
    shake.update(bytes("Neptune", "ascii"))
    for v in seed:
        shake.update(bytes(v))
    consts = get_n_random_elements(p, n*m, shake)
    gamma = get_random_element(p, shake)
    int_matrix = get_n_random_elements(p, m, shake)
    return consts, gamma, int_matrix

此外，对于幂映射指数 d、素数 p、t 个域元素和安全级别 s，外部和内部轮数可以通过以下方式获取：

1
2
3
4
5
6


def get_nb_rounds_neptune(d, p, t, s):
    re = 6    
    ri_p_1 = ceil((min(s, math.log(p,2)) - 6)/math.log(d, 2) + 3 + t + log(t, d))
    ri_p_2 = ceil((s/2) - 4*t - 2)
    
    return re, ceil(1.125 * max(ri_p_1, ri_p_2))

Ciminion

对于 n 轮 Ciminion，轮常数可以通过以下方式获取：

1
2
3
4


def get_round_constants_ciminion(p, n):
    shake = SHAKE256.new()
    shake.update(bytes(f"GF({p})", "ascii"))
    return get_n_random_elements(p, 4*n, shake, True)

Rescue Prime

对于素数 p、海绵容量、安全级别和 n 轮，轮常数可以通过以下方式生成：

1
2
3
4


def get_round_constants_rescue(p, m, capacity, security_level, n):
    shake = SHAKE256.new()
    shake.update(bytes("Rescue-XLIX (%i,%i,%i,%i)" % (p, m, capacity, security_level), "ascii"))
    return get_n_random_elements(p, m*n, shake)

轮数可以通过以下方式估算：

1
2
3
4
5
6
7
8
9


def get_number_of_rounds_rescue(p, m, c, s, d):
    r = m - c
    def dcon(N): return floor(0.5 * (d-1) * m * (N-1) + 2)
    def v(N): return m*(N-1)+r
    target = 2 ** s
    for l1 in range(1, 25):
        if binomial(v(l1) + dcon(l1), v(l1)) ** 2 > target:
            break
    return ceil(1.5*max(5, l1))

性能分析

为了公平比较哈希和认证加密原语的性能，我们获取了每个构造所需的 R1CS 约束数。

在 arkworks-rs 中，Rescue Prime 中 α 逆的域指数运算似乎是 R1CS 约束数增加的原因，因此，我们可以预期在 Groth16 等证明系统中的证明生成性能以及 Halo2 中的整体操作性能较差。

Neptune 对 Poseidon 哈希的改进在 arkworks-rs 中提供了最佳的整体性能，无论是哈希还是使用 SAFE API 的 AE 操作。

在哪里找到 zekrom for arkworks-rs

您可以在 https://github.com/kudelskisecurity/zekrom-arkworks 下载 arkworks-rs 的实现。

请继续关注本博客文章的第二部分，包括 Halo2 和 Reinforce Concrete 哈希构造。

zekrom：面向零知识证明电路的算术化构造库详解 - 第一部分：arkworks-rs

zekrom是一个开源的、面向zkSNARK电路的算术化构造库，支持Griffin、Neptune、Rescue Prime哈希及Ciminion认证加密，基于arkworks-rs实现，提供SAFE API集成和参数生成工具，提升零知识证明应用的性能和开发效率。