零知识证明

奶爸

04 Mar 2024 ·v1 | 👀342

Crypto

最近学习了一下零知识证明 Zero-knowledge proof，看了好多文章，大部分都没有特别清晰的说明他的基本能力和是如何应用的，下面就以奶爸的视角做个简单的总结。

零知识证明最初是由 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 于 1985 年在他们的论文「交互式证明系统的知识复杂性」中提出的，已经存在了较长时间。区块链算是目前零知识证明的最广泛应用。

本文主要探讨非交互式零知识证明 Non-interactive zero-knowledge proof 中的一种：零知识简洁非交互式知识论证 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge（zk-SNARK）。

zk-SNARK 具有以下特点：

零知识性：证明者在证明过程中不会向验证者泄露任何秘密信息。
简洁性：证明的长度很短，可以快速验证。
非交互性：证明者和验证者之间只需要进行一次交互，即可完成证明过程。

zk-SNARK 主要有三个角色：

可信设置：首先，需要进行可信设置，生成一些用于证明和验证的参数。这个过程需要在安全的环境中进行，并且需要保证参数的安全性。
证明者：证明者使用秘密信息和可信设置生成证明。
验证者：验证者使用公开的信息和证明进行验证。

可信设置就是制定一个怎么校验秘密的、证明者和验证者同时接受的验证逻辑，比如需要验证用户的余额大于 100，可信设置就设置检查 balance > 100。下面拿 Consensys 公司的 gnark 作为实例对比说明一下 zk-SNARK 的应用。

gnark

gnark 是一个高性能的 zk-SNARK 库，提供高级 API 来设计电路。他的电路设计非常直观简洁。

下面我们来拿检验「某人资产大于 10000」这个例子来做解释。

这个例子的完整代码在 https://github.com/naiba-archived/use-gnark

电路约束 Circuit

要检验「某人资产大于 10000」，我们在电路中检查要求资产大于 10000。

package circuit

import "github.com/consensys/gnark/frontend"

type CheckBalanceCircuit struct {
	Balance frontend.Variable `gnark:"balance"`
}

func (circuit *CheckBalanceCircuit) Define(api frontend.API) error {
	ret := api.Cmp(10000, circuit.Balance)
	api.AssertIsEqual(ret, -1)
	return nil
}

这样一个简单的电路定义就完成了，Balance 字段是秘密字段，不会被验证者得知。

0x0 可信设置（编译电路）

package main

import (
	"fmt"
	"use-gnark/circuit"
	"use-gnark/utils"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
)

func main() {
	var circuit circuit.CheckBalanceCircuit
	cs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
	if err != nil {
		panic(err)
	}

	pk, vk, err := groth16.Setup(cs)
	if err != nil {
		return
	}

	utils.WriteFile(cs, "01-cs.bin")
	utils.WriteFile(pk, "01-pk.bin")
	utils.WriteFile(vk, "02-vk.bin")

	fmt.Printf("cs sha256: %x\n", utils.FileSHA256("01-cs.bin"))
	fmt.Printf("pk sha256: %x\n", utils.FileSHA256("01-pk.bin"))
	fmt.Printf("vk sha256: %x\n", utils.FileSHA256("02-vk.bin"))
}

因为编译参数每次都随机生成，每次生成的 电路 cs、证明密钥 pk 和 验证密钥 vk 都是不同的。

我们需要将 02-vk 提供给验证者，01-cs 和 01-pk 提供给证明者。

01-cs 是经混淆后的电路约束定义二进制文件，几乎无法去混淆得到电路定义。

0x1 证明者 Prover

当可信设置完成后，拿到了电路定义和证明密钥，加上证明者手中持有的秘密，可以生成一个证明供验证者进行验证。

package main

import (
	"fmt"
	"use-gnark/circuit"
	"use-gnark/utils"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	_ "github.com/consensys/gnark/std/math/bits"
)

func main() {
	cs := groth16.NewCS(ecc.BN254)
	utils.ReadFile(cs, "01-cs.bin")

	pk := groth16.NewProvingKey(ecc.BN254)
	utils.ReadFile(pk, "01-pk.bin")

	assignment := &circuit.CheckBalanceCircuit{
		Balance: 10001,
	}
	witness, err := frontend.NewWitness(assignment, ecc.BN254.ScalarField())
	if err != nil {
		panic(err)
	}

	proof, err := groth16.Prove(cs, pk, witness)
	if err != nil {
		panic(err)
	}
	utils.WriteFile(proof, "02-proof.bin")

	publicWitness, err := witness.Public()
	if err != nil {
		panic(err)
	}
	utils.WriteFile(publicWitness, "02-public_witness.bin")

	fmt.Printf("proof sha256: %x\n", utils.FileSHA256("02-proof.bin"))
	fmt.Printf("public witness sha256: %x\n", utils.FileSHA256("02-public_witness.bin"))
}

证明者将生成的 Proof 加上公开的参数 public_witeness 提供给验证者进行验证。

0x2 验证者 Verifier

验证者通过可信设置提供的 vk 和证明者提供的 proof、public_witeness 三个要素来验证证明是否真实。

package main

import (
	"use-gnark/utils"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/backend/witness"
)

func main() {
	vk := groth16.NewVerifyingKey(ecc.BN254)
	utils.ReadFile(vk, "02-vk.bin")

	proof := groth16.NewProof(ecc.BN254)
	utils.ReadFile(proof, "02-proof.bin")

	publicWitness, err := witness.New(ecc.BN254.ScalarField())
	if err != nil {
		panic(err)
	}
	utils.ReadFile(publicWitness, "02-public_witness.bin")

	if err := groth16.Verify(proof, vk, publicWitness); err != nil {
		panic(err)
	}
}

在智能合约中使用

如果在 gnark 中使用的是 ecc.BN254 曲线加 groth16 算法的搭配，就可以将 vk 导出为一个 Solidity 合约将合约作为一个 verifier 进行验证。

err = vk.ExportSolidity(to_solidity_file_path)

案例：Binance 的 PoR 储备金证明

使用了 Poseidon Hash 来固定执行 CreateUserOperation 前后的 CexAssetInfo 列表，然后通过 Merkel Tree 固定每个 账户+资产 的信息，电路对每个阶段的状态进行了约束。

账户树的深度设置为了 28，大约能容纳 2 亿 6 千万条记录。

源代码：https://github.com/binance/zkmerkle-proof-of-solvency/blob/main/circuit/batch_create_user_circuit.go

扩展阅读

零知识证明 - 去中心化搬砖工 - 2021
Proof of solvency - Binance - 2023