Zero-knowledge proof是广泛应用于区块链中的一个组件，可以帮助提升区块链的对隐私性和可扩展性。接下来就简单科普下Zero-knowledge proof。

概念

Zero-knowledge proof

Zero-knowledge proof(简称 ZKP)是对事实的加密证明，且不会泄露关于该事实的任何信息。也就是说使用ZKP，你可以向别人证明你知道一件事或者做了某件事，而不告诉他这件事的具体细节。比如说你持有一个公钥，此时我要向你证明我持有你公钥对应的私钥。我可以直接将私钥展示给你来证明我确实持有，但这样就暴露了私钥信息，不安全。出于安全和隐私保护，我不直接向你展示私钥，而是让你发送通过公钥的信息给我，我对其解密成明文，并向你提供明文方便你进行验证，验证成功则证明我确实持有私钥。这个过程中我没有向你展示私钥的任何内容，但我向你证明了我持有私钥，这就是Zero-knowledge proof。

ZKP是由prover、verifier和challenge组成。

ZKP的发展历程

在上面的公钥私钥的例子中，如果verifier只提出一次challenge，prover可能会有一定的几率正好给出正确的proof，所以verifier需要多次提出challenge，与prover进行多次交互，从而确保prover确实持有proof。这种证明方式是学术上的interactive zero-knowledge proof。

因为其prover和verifier存在多次证明，带来大量的计算。对其进行改进之后，提出了non-interactive zero-knowledge proofs，与interactive zero-knowledge proof不同，non-interactive zero-knowledge proofs只需要在参与者(prover和verifier)之间进行一轮通信。prover将秘密信息传递给一种特殊算法，以计算零知识证明。该proof被发送给verifier，verifier使用另一种算法检查证明者是否知道秘密信息。

non-interactive zero-knowledge proofs主要有Zero-Knowledge Succinct Non-Interactive Argument of Knowledge(ZK-SNARKs) 和 Zero-Knowledge Scalable Transparent Argument of Knowledge(ZK-STARKs)。

non-interactive zero-knowledge proofs之所以可以做到一轮通信，是因为在prover和verifier之间有一个共享的key，共享的key指的是prover和verifier同意在生成和验证证明时使用的公共参数，这个公共参数(Common Reference String (CRS))在整个证明系统中非常重要，而这个共享的key生成方式就是ZK-SNARKs和ZK-STARKs的区别。

ZK-SNARKs是通过多方计算(MPC)来降低生成公共参数风险的。多方参与时需要进行trusted setup，每个人贡献一些随机值生成CRS。
ZK-STARKs则是依靠可公开验证的随机性生成用于证明和验证的公共参数，而不是trusted setup。因此，与ZK-SNARK相比，更加透明。

名词

  • prover 是持有某种信息，向verifier出示proof的一方
  • verifier 是验证proof是否合法
  • challenge 是verifier为了规避prover提前生成proof，而挑选的一个随机问题
  • witness prover想要证明对某些隐藏信息的了解，这些秘密信息就是wintness
  • trusted setup 是一个涉及多方参与的过程，其目的是生成证明系统或类似加密协议所依赖的标准参数。在这一设置过程中，随机数（秘密）会被生成、加密、用于生成数据，然后被删除，以确保协议始终防伪。人们把这些随机数值称为有毒废物，因为它们需要被永久删除。由于需要信任参与者才能实现设置的目的，因此这一过程被称为可信设置。

ZKP流程

  1. 生成电路

将需要证明的问题转换成多项式，再将次多项式转化成电路circuit。

  1. 可信设置

根据随机数和电路进行可信设置，会生成一个用于生成proof的private key 和一个用于验证proof的public key。
可信设置

  1. 生成witness

将需要隐藏的信息生成witness

  1. 生成proof

prover根据公共输入、witness和private key生成proof。
生成proof

  1. 验证proof

verifier根据公共输入、proof和public key来验证proof是否合法。
验证proof

ZKP开发

ZKP开发一般涉及两部分，一是电路开发，另一部分是电路证明。电路开发一般使用circom，电路证明针对不同的语言都有开源的实现，比如snarkjs、gnark。

下面看一个例子zksnarks-example(不过需要注意的是，这个例子的比较老，需要使用对应版本的circom@0.0.24和snarkjs@0.1.11)。
首先编写了一个电路程序circuit.circom，用于证明prover知道a和b，使a*b=c。代码如下：

1
2
3
4
5
6
7
8
template Multiplier() {
  signal private input a;
  signal private input b;
  signal output c;
  c <== a*b;
}

component main = Multiplier();

然后对其电路进行编译

1
circom circuit.circom -o circuit.json

接下来根据对其电路进行电路证明。

  • 针对电路进行可信设置snarkjs setup --circuit=circuit.json，该命令将生成证明密钥和验证密钥，分别为proving_key.json 和 verification_key.json。
  • 生成witness，执行snarkjs calculatewitness --circuit=circuit.json --input=input.json，生成witness.json，其中input.json内容为{"a": 7, "b": 8}
  • 使用证明密钥和witness生成proof，执行snarkjs proof --witness=witness.json --provingkey=proving_key.json，生成proof.json 和 public.json
  • 使用验证密钥验证proof，执行snarkjs verify --proof=proof.json --verificationkey=verification_key.json --public=public.json，成功则输出OK，否则INVALID

如果你使用的snarkjs较新(写文章时是v0.7.0)，snarkjs的使用流程和上面的流程会有所差异。比较明显的是增加了一个powers of tau的过程。

之所以增加powers of tau是因为ZK-SNARKs的安全性很大程度上归结为CRS生成的安全性，其安全性由其随机数是否被丢弃来决定，为了保证其安全性，多采用MPC的方式，而且还需要保证各方互不干预，没有串通。这无疑增加了以应用难度。

因此经过对CRS进行改进，将其分两个阶段生成。第一阶段被称为Powers of Tau，它生成的通用设置参数，可用于该方案的所有电路，并达到给定的规模。第二阶段将**Powers of Tau阶段的输出**转换为特定于 NP 关系的CRS。

这种改进与以前的计划相比，Powers of Tau有几个优点。首先，不需要事先选定贡献者。相反，该协议使用一个随机信标，在设定的时间间隔内产生公开的随机值，从而实现连续的仪式。因此，参与者并不需要始终在线。随机信标还能确保协调者的公开可验证性。因此，该协议理论上可以支持数百甚至数千名参与者。
Powers of Tau

参考

https://github.com/miguelmota/zksnarks-example
https://ethereum.org/en/zero-knowledge-proofs/
https://forum.latticex.foundation/t/topic/6385
https://foresightnews.pro/article/detail/26934
https://learnblockchain.cn/article/1078
https://github.com/iden3/snarkjs
https://medium.com/coinmonks/announcing-the-perpetual-powers-of-tau-ceremony-to-benefit-all-zk-snark-projects-c3da86af8377
https://blog.pantherprotocol.io/a-guide-to-understanding-trusted-setups/
https://www.zkcamp.xyz/blog/lifecycle-of-zkp
https://zkproof.org/2021/06/30/setup-ceremonies/
https://vitalik.ca/general/2022/03/14/trustedsetup.html
https://mirror.xyz/0xmobius.eth/q5g9vWDxbBbSjuiEcc2zIugJIQGtT9SdlznIY3Lgv8k
https://medium.com/coinmonks/simplifying-powers-of-tau-and-the-trusted-setup-ceremony-c9a4f1833dc2
https://zhuanlan.zhihu.com/p/143519030