Zcash中的zk-SNARK statements

1. 引言

zero-knowledge proving system为a cryptographic protocol，用于证明：

• a particular statement，dependent on primary and auxiliary inputs, in zero knowledge —— 即，不需要reveal auxiliary inputs信息的情况下，可证明该statement。

Zcash中使用的zero-knowledge proving system类型为：

• preprocessing zk-SNARK [BCCGLRT2014-Zerocash: Decentralized Anonymous Payments from Bitcoin (extended vesion)]

preprocessing zk-SNARK instance中定义了如下类型：

• Z K . P r o v i n g K e y ZK.ProvingKey ZK.ProvingKey
• Z K . V e r i f y i n g K e y ZK.VerifyingKey ZK.VerifyingKey
• Z K . P r i m a r y I n p u t ZK.PrimaryInput ZK.PrimaryInput
• Z K . A u x i l i a r y I n p u t ZK.AuxiliaryInput ZK.AuxiliaryInput
• Z K . P r o o f ZK.Proof ZK.Proof
• Z K . S a t i s f y i n g i n p u t s ⊆ Z K . P r i m a r y I n p u t × Z K . A u x i l i a r y I n p u t ZK.Satisfyinginputs\subseteq ZK.PrimaryInput \times ZK.AuxiliaryInput ZK.Satisfyinginputs⊆ZK.PrimaryInput×ZK.AuxiliaryInput
• Z K . G e n : ( ) → R Z K . P r o v i n g K e y × Z K . V e r i f y i n g K e y ZK.Gen:()\rightarrow_R ZK.ProvingKey\times ZK.VerifyingKey ZK.Gen:()→R​ZK.ProvingKey×ZK.VerifyingKey
• Z K . P r o v e : Z K . P r o v i n g K e y × Z K . S a t i s f y i n g I n p u t s → Z K . P r o o f ZK.Prove: ZK.ProvingKey\times ZK.SatisfyingInputs\rightarrow ZK.Proof ZK.Prove:ZK.ProvingKey×ZK.SatisfyingInputs→ZK.Proof
• Z K . V e r i f y : Z K . V e r i f y i n g K e y × Z K . P r i m a r y I n p u t × Z K . P r o o f → B ZK.Verify: ZK.VerifyingKey\times ZK.PrimaryInput\times ZK.Proof\rightarrow \mathbb{B} ZK.Verify:ZK.VerifyingKey×ZK.PrimaryInput×ZK.Proof→B

zk-SNARK应满足如下安全属性：

• completeness
• knowledge soundness
• statistical zero knowledge

Zcash中采用了2种proving system：

• BCTV14，采用BN-254 pairing来prove and verify Sprout JoinSplit statement。
• Groth16，采用BLS12-381 pairing来prove and verify Sapling Spend Statement和Output Statement。

Zcash中涉及的zk-SNARK statements主要有：

• JoinSplit Statement (Sprout)——ZKJoinSplit
• Spend Statement (Sapling)——ZKSpend
• Output Statement (Sapling)——ZKOutput

2. Spend Statement (Sapling)

Spend Statement π Z K S p e n d \pi_{ZKSpend} πZKSpend​ 中的primary input 有：【即public input】

• r t S a p l i n g : B [ l M e r k l e S a p l i n g ] rt^{Sapling}:\mathbb{B}^{[l_{Merkle}^{Sapling}]} rtSapling:B[lMerkleSapling​]：为anchor。
• c v o l d cv^{old} cvold：为 V a l u e C o m m i t S a p l i n g . O u t p u t ValueCommit^{Sapling}.Output ValueCommitSapling.Output，为 J \mathbb{J} J类型。
• n f o l d nf^{old} nfold：为 B Y [ l P R F n f S a p l i n g / 8 ] \mathbb{B}^{\mathbb{Y}^{[l_{PRFnfSapling}/8]}} BY[lPRFnfSapling​/8]。
• r k rk rk：为 S p e n d A u t h S i g S a p l i n g . P u b l i c SpendAuthSig^{Sapling}.Public SpendAuthSigSapling.Public，为 J \mathbb{J} J类型。

仅Prover知道的auxiliary input有：【即witness】

• p a t h path path：为 B [ l M e r k l e S a p l i n g ] [ M e r k l e D e p t h S a p l i n g ] \mathbb{B}^{[l_{Merkle}^{Sapling}][MerkleDepth^{Sapling}]} B[lMerkleSapling​][MerkleDepthSapling]
• p o s pos pos：取值范围为 { 0.. 2 M e r k l e D e p t h S a p l i n g − 1 } \{0..2^{MerkleDepth^{Sapling}}-1\} {0..2MerkleDepthSapling−1}
• g d g_d gd​： J \mathbb{J} J
• p k d pk_d pkd​： J \mathbb{J} J
• v o l d v^{old} vold：取值范围为 { 0.. 2 l v a l u e − 1 } \{0..2^{l_{value}}-1\} {0..2lvalue​−1}
• r c v o l d rcv^{old} rcvold：取值范围为 { 0.. 2 l s c a l a r S a p l i n g − 1 } \{0..2^{l_{scalar}^{Sapling}}-1\} {0..2lscalarSapling​−1}
• c m o l d cm^{old} cmold： J \mathbb{J} J
• r c m o l d rcm^{old} rcmold：取值范围为 { 0.. 2 l s c a l a r S a p l i n g − 1 } \{0..2^{l_{scalar}^{Sapling}}-1\} {0..2lscalarSapling​−1}
• α \alpha α：取值范围为 { 0.. 2 l s c a l a r S a p l i n g − 1 } \{0..2^{l_{scalar}^{Sapling}}-1\} {0..2lscalarSapling​−1}
• a k ak ak：为 S p e n d A u t h S i g S a p l i n g . P u b l i c SpendAuthSig^{Sapling}.Public SpendAuthSigSapling.Public，为 J \mathbb{J} J类型。
• n s k nsk nsk：取值范围为 { 0.. 2 l s c a l a r S a p l i n g − 1 } \{0..2^{l_{scalar}^{Sapling}}-1\} {0..2lscalarSapling​−1}

π Z K S p e n d \pi_{ZKSpend} πZKSpend​ 需证明以下关系：

• 1）Note commitment integrity，即： c m o l d = N o t e C o m m i t r c m o l d S a p l i n g ( r e p r J ( g d ) , r e p r J ( p k d ) , v o l d ) cm^{old}=NoteCommit_{rcm^{old}}^{Sapling}(repr_{\mathbb{J}}(g_d),repr_{\mathbb{J}}(pk_d),v^{old}) cmold=NoteCommitrcmoldSapling​(reprJ​(gd​),reprJ​(pkd​),vold)。【注意，不会check that r c m o l d < r J rcm^{old}