4.1 Cryptogrraphic buliding blocks
首先介绍一些要用到的标准密码学中的组件，和之前一样，假设$\lambda$为安全参数
Collision-resistant hashing
抗碰撞Hash函数，记为$CRH:\{0,1\}^*\rightarrow \{0,1\}^{O(\lambda)}$
Pseudorandom functions
采用为随机函数族$PRF:\{PRF_x:\{0,1\}^*\rightarrow \{0,1\}^{O(\lambda)}\}_x$，其中$x$表示PRF的种子
然后从$PRF_x$中导出三个非重叠的伪随机函数，分别为
- $PRF_x^{addr}(z)=PRF_x(00||z)$
- $PRF_x^{sn}(z)=PRF_x(01||z)$
- $PRF_x^{pk}(z)=PRF_x(10||z)$
此外假设$PRF_x^{sn}(z)$是抗碰撞的（也即无法找到$(x,z)\neq (x',z')$，满足$PRF_x^{sn}(z)=PRF_{x'}^{sn}(z')$
Statistically-hiding commitments
承诺方案，满足计算绑定性和统计隐藏性，记为$COMM_x:\{0,1\}^*\rightarrow \{0,1\}^{O(\lambda)}$，其中$x$表示承诺陷门（若有对$z$的承诺$cm=COMM_x(z)$，提供$z$和陷门$x$就可以验证承诺是否正确被揭示）
One-time strongly-unforgeable digital signatures
数字签名方案，记为$Sig=(\mathcal G_{sig},\mathcal K_{sig},\mathcal S_{sig},\mathcal V_{sig})$，具体如下
- $\mathcal G_{sig}(1^\lambda)\rightarrow pp_{sig}$：给定安全参数$\lambda$，算法输出公共参数$pp_{sig}$，用于加密方案
- $\mathcal K_{sig}(pp_{sig})\rightarrow (pk_{sig},sk_{sig})$：给定公共参数，算法输出用户的公私钥对
- $\mathcal S_{sig}(sk_{sig},m)\rightarrow \sigma$：给定安全参数和待签名的消息，算法输出签名值$\sigma$
- $\mathcal V_{sig}(pk_{sig},m,\sigma)\rightarrow b$：给定公钥，消息$m$，签名值$\sigma$，若签名验证通过，则算法输出$b=1$，否则算法输出$b=0$
Key-private public-key encryption
密钥保密的公钥加密方案，记为$Enc=(\mathcal G_{enc},\mathcal K_{enc},\mathcal E_{enc},\mathcal D_{enc})$
- $\mathcal G_{enc}(1^\lambda)\rightarrow pp_{enc}$：以安全参数$\lambda$作为输入，算法输出公共参数$pp_{enc}$，用于加密方案
- $\mathcal K_{enc}(pp_{enc})\rightarrow (pk_{enc},sk_{enc})$：对于给定的公共参数，算法为单个用户输出加密密钥对
- $\mathcal E_{enc}(pk_{enc},m)\rightarrow c$：给定公钥和消息，算法输出密文$c$
- $\mathcal D_{enc}(sk_{enc},c)\rightarrow m$：给定私钥和密文，算法输出明文$m$（解密失败时输出$\bot$）
加密方案$Enc$需要满足两个安全特性（具体可以看$[BBDP01]$）
- IND-CCA
- IK-CCA（简单来说就是要求密文不能与加密该密文的公钥关联起来，或关联到使用相同公钥加密的其他密文）
4.2 zk-SNARKs for pouring coins
回顾一下1.3节的内容，当时提到了需要构造一个特定的NP语句$\mathtt {POUR}$来生成zk-SNARK，接下来详细定义一下
首先回顾一下$\mathtt {POUR}$，当用户$u$将旧币$c_1^{old},c_2^{old}$pour到新币$c_1^{new},c_2^{new}$时，生成对应的pour交易
$$ tx_{Pour}=(rt,sn_1^{old},sn_2^{old},cm_1^{new},cm_2^{new},v_{pub},info,*) $$
这里需要在pour交易中提供证据$*$，使其满足下列条件
- 用户$u$拥有旧币$c_1^{old},c_2^{old}$
- 旧币的承诺正确的出现在了账本上
- 旧币有对应的序列号$sn_1^{old},sn_2^{old}$
- 新币的承诺$cm_1^{new},cm_2^{new}$正确
- 满足平衡性
通过在语句$\mathtt {POUR}$中包含zk-SNARK证明$\Pi_{POUR}$来实现这一点，该语句检查上述不变量（以及非延展性所需的其他不变量）
The statement $\mathtt {POUR}$
接下来看一下NP语句$\mathtt {POUR}$的定义
- NP语句形式：表示为$x=(rt,sn_1^{old},sn_2^{old},cm_1^{new},cm_2^{new},v_{pub},h_{sig},h_1,h_2)$，也即$x$指定了一个基于CRH的Merkle树根$rt$（包含了到目前为止的承诺的列表），两个已消耗的旧币的序列号$sn_1^{old},sn_2^{old}$，两个新币的承诺$cm_1^{new},cm_2^{new}$，公共值$v_{pub}$，三个用于非延展性的字段$h_{sig},h_1,h_2$
- 证据：表示为$a=(path_1,path_2,c_1^{old},c_2^{old},addr_{sk,1}^{old},addr_{sk,2}^{old},c_1^{new},c_2^{new})$，其中对于$i\in\{1,2\}$，有
$$ \begin{aligned} c_i^{old}&=(addr_{pk.i}^{old},v_i^{old},\rho_i^{old},r_i^{old},s_i^{old},cm_i^{old})\\ c_i^{new}&=(addr_{pk.i}^{new},v_i^{new},\rho_i^{new},r_i^{new},s_i^{new},cm_i^{new})(cm_i^{new}和实例x中的一致)\\ addr_{pk,i}^{old}&=(a^{old}_{pk,i},pk_{enc,i}^{old})\\ addr_{pk,i}^{new}&=(a^{new}_{pk,i},pk_{enc,i}^{new}) \\ addr_{sk,i}^{old}&= (a^{old}_{sk,i},sk_{enc,i}^{old}) \end{aligned} $$
证据$a$指定了两个新币的承诺的认证路径、关于旧币和新币的全部信息、旧币的地址密钥
对于给定的$\mathtt {POUR}$实例$x$，若有下列条件成立，则称证据$a$是合法的证据：
对于$i\in\{1,2\}$，有
(a)$cm_i^{old}$正确出现在了账本上，如path_i为$cm_i^{old}$的一个关于树根rt的合法的验证路径 (b)旧币$c_i^{old}$的地址私钥$a^{old}_{sk,i}$与旧币的地址公钥$a^{old}_{pk,i}$匹配，也即$a_{pk,i}^{old}=PRF^{addr}_{a^{old}_{sk,i}}(0)$ (c)旧币的序列号$sn_i^{old}$计算正确，也即$sn_I^{old}=PRF^{sn}_{a^{old}_{sk,i}}(\rho_i^{old})$ (d)旧币格式正确，也即$cm^{old}_i = COMM_{s^{old}_i} (COMM_{r^{old}_i} (a^{old}_{pk,i}||\rho^{old}_i )||v^{old}_i )$ (e)新币格式正确 (f)地址私钥$a^{old}_{sk,i}$将签名值$h_{sig}$绑定至$h_i$，也即$h_i=PRF^{pk}_{a^{old}_{sk,i}}(i||h_{sig})$- 平衡性成立$v_1^{new}+v_2^{new}+v_{pub}=v_1^{old}+v_2^{old}(v_1^{old},v_2^{old}\geq0,v_1^{old}+v_2^{old}\leq v_{max})$
回顾第二章中的内容，文章的方案采用的zk-SNARK与算术电路可满足性语言有关，因此接下来会引入名为$C_{POUR}$的算术电路来表示$\mathtt {POUR}$中的检查
4.3 Algorithm Constructions
接下来描述DAP方案中的六个算法，下图列出了4.1和4.2节中六种算法的伪代码
构造中硬编码了两个量：币的最大值$v_{max}$和Merkle树的深度$d_{tree}$
这里有三个点需要注意
- 可信设置：$\Pi$的安全性依赖于可信方运行的Setup来产生公共参数，此类可信设置是交易的不可扩展性和平衡性所需要的，但是账本不可区分性不需要可信设置，因此即便是一个强大的间谍机构尝试破坏这个可信设置，匿名性仍然会成立
此外，若希望减少该步骤的新人要求，可以使用安全多方计算进行可信设置（未来可能会完成）
- 公共参数$pp$：回顾第三章对DAP方案的定义，公共参数在六个算法中都作为输入使用（上面那个图也可以看到），不过本文的方案中，公共参数实际上等价于一个四元组$(pk_{\mathtt {POUR}},vk_{\mathtt {POUR}},pp_{enc},pp_{sig})$，且不是所有的算法都需要这四个参数
比如CreateAdres算法，只需要$pp_{enc}$，Mint算法只需要安全参数$\lambda$，Pour只需要$pk_{\mathtt {POUR}}$和$pp_{sig}$，VerifyTransaction只需要$vk_{\mathtt {POUR}}$，Receive只需要$\lambda$
注意到方案依赖于zk-SNARKs来证明或验证$\mathtt {POUR}$，因此第一个参数实际上是个常量，但是其大小很大，因此只会在Pour算法中使用，$pp$中另外三个参数都很小
- 在账本上检查收到的币：算法Receive测试收到的硬币的序列号是否已经出现在分类账上，以便不输出用户已经收到并花费的硬币，在任何情况下其他用户都无法使用发送给该用户的硬币