实现零知识证明专用哈希方案

在我的上一篇文章中，我描述了面向零知识证明的Ciminion AE（Dobraunig等人，2021）方案，并使用circom2 DSL（领域特定语言）编写了zkSNARK电路来实现它。在本文的第二部分，我将概述过去几年提出的各种哈希结构，从MiMC（Albrecht等人，2016）开始，到Griffin（Grassi等人，2022）结束。这使我们能够探索另一种用于编写SNARK的DSL（Leo），并研究嵌入式DSL。这些库提供了从Go和Rust等语言进行约束定义、编译和证明生成的API。两个例子是gnark和arkworks。最后，我包含了一个小清单，可用于在审计电路时构建检查表。

zkSNARK电路中的哈希

在本系列文章的第一部分中，我们处理了为zkSNARK应用设计的加密方案。例如，它们可用于证明某段敏感数据已使用特定密钥加密（考虑云存储），或证明密文已使用特定加密方案正确加密。

通常，在电路中使用哈希意味着证明者可以说服验证者，在给定x的哈希值（即H(X)）的情况下，她知道值x的原像。具体来说，这一事实可用于证明秘密的知识、敏感值在集合中的成员资格、获取无效符和承诺，以及更常见的是，在Merkle树累加器中实现集合成员证明。在所有这些情况下，所使用的哈希方案的性能至关重要，与基于较少乘法和加法门的方案相比，SHA-256等方案在电路中的性能不同。

零知识证明专用哈希方案的结构

通常，针对ZK电路的哈希方案依赖于相同类型的线性和非线性层（应注意，在本文中，我们主要关注和描述那些部分或主要使用Rank-1二次约束作为指标来优化和测量其方案性能和大小的方案。我们将在其他时间讨论诸如Reinforced Concrete（Grassi等人，2021）等专注于PLONK的方案以及其他基于椭圆曲线操作的方案）。R1CS约束通过多项式描述电路，其中电路的乘法和加法门在配对友好椭圆曲线的素域Fp上操作。由于证明生成的复杂性通常与约束数量相关（主要是乘法门，我们可以说加法是免费的），方案设计者的目标是减少乘法次数。

在这些方案中，在线性层中，我们不能像在常见分组密码和哈希函数中那样操作单个位，而是使用矩阵乘法，通过最大距离可分（MDS）矩阵进行扩散。另一方面，非线性层通常基于幂映射。选择保证可逆性和非线性的最小整数。例如，在MiMC的情况下使用x^3。选择指数d的条件是x^d和x^{1/d}都存在，并且都是置换，其中d是整数。

大多数方案基于一轮函数，该函数应用一个线性层和一个非线性层，引入轮常数和/或子密钥：

[ F(x) = M \cdot S(x + c) + k ]

其中c是轮常数，M是可逆MDS矩阵，S是非线性层，可视为s-box。轮函数以Feistel或SPN结构排列并迭代。对于基于下一节中描述的置换的哈希结构，通常实例化海绵结构。

提出的零知识证明专用哈希方案概述

在过去7年中，提出了许多面向算术化的方案，针对多方计算、全同态加密和零知识证明应用。我们简要概述了专注于素域且其性能主要或部分在R1CS算术化上测量的结构。当分组密码设计和策略被用作创建其他哈希函数的灵感时，我们引用了它们。

最早提出的面向ZK的密码之一是LowMC（Albrecht等人，2016）。自那时起，它受到了密码分析界的广泛关注（例如，参见这里和这里）。受LowMC启发，MiMC提出了一个置换（可以使用Feistel结构）、一个分组密码和一个哈希函数。它依赖于非线性幂映射x^d，其中d=3。MiMC分组密码是GMiMC（Grassi等人，2019）构造和HadesMiMC策略（Grassi等人，2019）改进加密的起点。MiMC在circomlib和gnark等库中实现。

Poseidon哈希方案在MiMC之后提出，提供了两个主要优势：可变长度哈希和专用于Merkle树的实例。它在arkworks和circomlib等库中实现。作者遵循HadesMiMC方法和SPN结构，以及幂映射x^d，其中d>=3（对于配对友好曲线BLS-12-381和BN-254，d=5）。他们基于Hades设计创建了Poseidon-pi置换。它包含部分轮（非线性函数修改状态的一部分）和完整轮（非线性层修改整个状态）。线性层是一个MDS矩阵，其维度基于轮函数处理的域元素数量。

Rescue构造（Aly等人，2019）基于与Poseidon相同的SPN网络。然而，它在同一轮中使用两个非线性层，幂映射x^a和x^{1/a}由线性层分隔，该线性层包括与MDS矩阵的乘法和子密钥加法。Neptune是Poseidon的一个变体，其非线性层减少了乘法次数。首先，作者依赖于使用独立函数的非线性层；其次，他们提出使用两种不同的轮函数：一种用于内部轮，另一种用于外部轮。外部轮基于通过Lai-Massey连接的独立s-box。最后，Griffin构造（Grassi等人，2022）采用受Neptune启发的s-box，并使用所谓的Horst操作模式。在其他候选方案中，当用于处理t>=20个域元素的状态时，它提供了最佳性能。当用于Merkle树累加器中的成员证明时，它具有最小的R1CS约束数。

方案	结构	层	会议
MiMC	Feistel	幂映射 x^3	ASIACRYPT 2016
Poseidon	SPN	幂映射 x^5, MDS	USENIX Security 2021
Rescue	SPN	幂映射 x^d, x^{1/d}, MDS	FSE 2020
Neptune	SPN	独立 s-boxes, MDS	ePrint 2021/1695
Griffin	SPN	独立 s-boxes, MDS	ePrint 2022/403

在Leo中实现MiMC

Leo语言用于在隐私友好的区块链Aleo中创建应用程序。与用Leo编写的电路或应用程序相关的证明作为链上交易发送，因此第三方可以验证我们想要证明的某个陈述的真实性。该结构基于ZEXE。Leo依赖于BLS-12-377配对友好曲线和Marlin（Chiesa等人，2019）证明系统。

MiMC

在分组密码构造中，MiMC使用Fq上的置换多项式作为轮，包括密钥加法、轮常数和应用幂映射函数：

[ F(x) = (x + k + c)^d ]

并迭代轮函数F。

在Feistel网络中使用相同的置换，如果我们将轮数乘以2，可以处理两个域元素。在这种情况下，轮函数是：

[ F(x) = (x + k + c)^d ]

最后，通过设置k=0创建MIMCP置换，并通过使用置换实例化海绵结构来创建哈希函数。

BLS-12-377曲线中的幂映射

Leo使用BLS-12-377曲线的标量域，其中r = 8444461749428370424248824938781546531375899335154063827935233455917409239041。

在我们的例子中，我们选择参数d=11。根据MiMC论文的第5.1节，我们需要轮函数中的立方生成置换，因此gcd(3, p-1)=1，这在BLS-12-377曲线的标量域中不可能。对于d=5和d=7，我们有同样的问题。我们使用轮数估计公式2*(log p / log d)来估计幂映射f(x)=x^d和使用Feistel结构的置换所需的轮数。

在Leo中实现MiMCP置换

Leo开发环境可以从其存储库安装。它只需要安装Rust语言。通过leo命令行工具，我们可以构建、测试、生成和验证给定电路或应用程序的证明。

对于d=11，我们需要2*(log p / log 11)=145轮。我们硬编码轮常数并实现Feistel版本，该版本可用于参数为k的分组密码和k=0的哈希函数，并通过实例化海绵结构。我们从非线性层的设计开始，包括轮常数的加法和d=11的幂映射：

1
2
3
4
5
6
7
8


function non_linear(state: field, constant: field) -> field {    
    let c: field = state + constant;    
    let c2: field = c*c;    
    let c4: field = c2*c2;    
    let c8: field = c4*c4;    
    let c11: field = c8*c2*c;    
    return c11;    
}

在Leo中，我们可以使用字段数据类型创建函数，即曲线标量域的元素。我们添加轮常数并执行幂映射。语法更类似于Rust而不是JS。一轮函数的应用包括更新由两个域元素组成的状态，并添加非线性层应用的结果：

1
2
3
4


function round(state: [field; 2], constant:field) -> [field; 2] {
    state[1] += non_linear(state[0], constant);                                                
    return state;
}

最后，我们可以预先计算轮常数并创建置换：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


function permutation(state: [field; 2]) -> [field; 2] {
    const N_ROUNDS:u32 = 147;
    let RC: [field; 147] = [
        3865702934124093755943890899496595264675194361091768380145853932420267718340,    
        1007157542023399026163733618843871954165432315393358131261818260851607860762,    
        4405765946538921025695035439523237362153599324827654321243952925829102897068,    
        3664456287923997818199382200327273463939055455139573605615804006507349414661,  
        [...]
    ];
    let tmp: field = 0field;
    for i in 0..N_ROUNDS - 1{                                                            
        state = round(state, RC[i]);                                                     
        tmp = state[0];                                                                  
        state[0] = state[1];                                                             
        state[1] = tmp;                                                                  
    }                                                                                    
    state = round(state, RC[N_ROUNDS - 1]);                                              
    return state;                                                                        
}

Leo允许我们在同一文件中创建测试来测试我们的函数，例如，对于非线性层，我们可以这样做：

1
2
3
4
5
6
7
8


@test
function sbox_test() {
    let constant: field = 5943928848779486925441395077146413864173255127001087220085381147547751487102; 
    let state: field = 5324319209727394843353330183529117967230803372202482264714325483223508628524;
    let check: field = 4817246075678656562069386914259487599241369120264717506466034175518663577036;
    let result = sbox(state, constant);
    console.assert(check == result);
}

以及轮函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


@test
function round_test() {
    let state_in: [field; 2] = [
        205590015168576069906775328287417415487799853627397567932093125904979123828,
        6314658282813217945138278251984680094319698463151078319831502705046804707990 
    ];
    let constant: field = 7687545491407243578138660792989370259027838962927279562322213575702987063508;
    let result_0: field = 205590015168576069906775328287417415487799853627397567932093125904979123828;
    let result_1: field = 4768980667092361968239023698012060630723900845915064763583717922931253545522;
    let result = round(state_in, constant);
    console.assert(result_0 == result[0]);
    console.assert(result_1 == result[1]);
}

我们可以使用leo build构建电路并获取约束数量：

1
2
3
4
5
6


$ leo build                             
     Build Starting...
     Build Compiling main program... 
     Build Number of constraints - 735
     Build Complete
      Done Finished in 23 milliseconds 

以及创建证明和验证密钥，并通过leo run验证证明：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


     Build Starting...
     Build Compiling main program...
     Build Number of constraints - 735
     Build Complete
      Done Finished in 38 milliseconds 

     Setup Starting...
     Setup Saving proving key 
     Setup Complete
     Setup Saving verification key 
     Setup Complete
      Done Finished in 79 milliseconds 

   Proving Starting...
   Proving Saving proof... 
      Done Finished in 54 milliseconds 

 Verifying Starting...
 Verifying Proof is valid
      Done Finished in 2 milliseconds 

在gnark中实现Griffin置换

到目前为止，我们已经使用了circom2和Leo DSL。然而，还有其他选项可以使用嵌入式DSL（如bellman、gnark和arkworks-rs）来描述zkSNARK电路。在本节中，我们将使用BLS-12-381曲线在gnark中实现Griffin置换。这些库在纯R1CS约束和电路中执行的操作（例如，通过API进行模乘法和加法）之间创建了一个接口。

gnark简介

我们可以使用gnark playground或通过go get在我们的项目中安装gnark。在circom2中，所有信号默认都是私有的。在gnark中，信号通过Circuit结构定义。例如，声明3个（输入）私有信号（X0-X2）和3个（输出）公共信号（Y0-Y2）是通过以下方式完成的：

1
2
3
4
5
6
7
8


type Circuit struct {    
    X0 frontend.Variable `gnark:"x"`    
    X1 frontend.Variable `gnark:"x"`    
    X2 frontend.Variable `gnark:"x"`    
    Y0 frontend.Variable `gnark:",public"`    
    Y1 frontend.Variable `gnark:",public"`    
    Y2 frontend.Variable `gnark:",public"`    
}

一旦我们使用gnark前端API的算术操作（例如，通过api.Mul(x, x)）定义了一个电路，我们可以通过以下方式获取电路的R1CS表示，适用于库支持的特定曲线：

1
2
3


var myCircuit Circuit    
// generate R1CS    
r1cs, err := frontend.Compile(ecc.BLS12_381, r1cs.NewBuilder, &myCircuit)

选择证明系统（例如Groth16）后，我们可以执行设置、生成见证和证明以进行验证：

1
2
3
4
5


pk, vk, err := groth16.Setup(r1cs)
witness, err := frontend.NewWitness(&myCircuit, ecc.BLS12_381)
publicWitness, err := witness.Public()
proof, err := groth16.Prove(r1cs, pk, witness)
err = groth16.Verify(proof, vk, publicWitness)

但在创建Griffin置换电路之前，我们需要解释其结构。

Griffin置换非线性层

Griffin通过使用所谓的Horst操作模式和Rescue方法提高了基于SPN的方案的性能。Feistel方案被替换。

Griffin使用三个非线性函数：f0(x)=x^{1/d}，f1(x)=x^d，和f2(x)=x*g(l)，其中g是二次函数。

在我们的例子中，我们选择参数t=3，R=12，d=5，基于BLS-12-381域。我们将置换应用于3个域元素。注意，我们只实现Griffin置换，需要实例化海绵以获得相关的哈希函数。应用于三个输入域元素的变换如下：y0 = f0(x0)，y1 = f1(x1)，和y2 = x2 * g(l)，其中l = y0 + y1。

参数alpha和beta选择为不同的值，其中a^2 - 4*beta是模p的二次非剩余。Li是线性变换。对于t=3，我们得到以下非线性层实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func non_linear(api frontend.API, x0 frontend.Variable, x1 frontend.Variable, x2 frontend.Variable) (frontend.Variable, frontend.Variable, frontend.Variable) {
    alpha, _ := new(big.Int).SetString("20950244155795017333954742965657628047481163604901233004908207073969011285354", 10)            
    beta, _ := new(big.Int).SetString("3710185818436319233594998810848289882480745979515096857371562288200759554874", 10)
    y0 := add_chain_exp_d_inv(api, x0)        
    y1 := exp_d(api, x1)    
    // l for t = 3    
    l := api.Add(y0, y1)    
    lq := api.Mul(l, l)    
    l = api.Mul(l, alpha)    
    l = api.Add(l, lq)     
    l = api.Add(l, beta)    
    y2 := api.Mul(x2, l)     
    return y0, y1, y2    
}

深入探索零知识证明专用哈希方案：从MiMC到Griffin的实现与优化

本文详细分析了专为零知识证明电路设计的哈希方案，包括MiMC、Poseidon、Rescue、Neptune和Griffin的结构与性能比较，并提供了在Leo和gnark中的具体实现示例及电路审计要点。