5.1 组件实例化
CRH,PRF,COMM from SHA256
记$\mathcal H$为SHA256压缩函数，将$512 bit$输入压缩为$256 bit$输出，本文大多数时候依赖于$\mathcal H$，而不是完全散列（full hash）
接下来（在$\mathcal H$的适当的假设下）将$CRH,PRF,COMM$三个算法进行实例化
- 将CRH实例化为$\mathcal H(z)$，其中$z\in\{0,1\}^{512}$，该函数将$2 bit$压缩为$1 bit$，因此可用于Merkle Tree的构造
- 将伪随机函数$PRF_x(z)$实例化为$\mathcal H(x||z)$，其中$x\in \{0,1\}^{256}$作为伪随机函数的种子，$z\in \{0,1\}^{256}$为函数输入，然后进一步推导出下列三个函数
$$ PRF_x^{addr}(z)=\mathcal H(x||00|z),PRF_x^{sn}(z)=\mathcal H(x||01|z),PRF_x^{pk}(z)=\mathcal H(x||10|z) $$
其中$x\in \{0,1\}^{256},z\in \{0,1\}^{254}$（$z$中分出来两位）
- 对于承诺方案，只在下列两个情况使用
$$ k=COMM_r(a_{pk}||\rho),cm=COMM_s(v||k) $$
根据上面PRF的实例化，$a_{pk}$长度为$256 bit$，因此$\rho$长度也为$256 bit$，则$r$为$256+128=384 bit$，所以得到
$$ k=COMM_r(a_{pk}||\rho),\mathcal H(r||[\mathcal H(a_{pk}||\rho)]_{128}) $$
$[\cdot]_{128}$表示将输出截断并保留前$128 bit$，截断并保留其他位数类似
对于一个串$z\in \{0,1\}^{128}$，由$\mathcal H(r||z)$得到的分布为$2^{-128}$，近似于均匀分布，从而构成了统计隐藏性质的基础
为了计算币承诺$cm$，令币值$v$为长度为$64 bit$的无符号整数，因此有$v_{max}=2^{64}-1$，然后计算币承诺如下
$$ cm=COMM_s(v||k),\mathcal H(k||0^{192}||v) $$
注意到上面的介绍中忽略了承诺的随机性$s$，因为$k$作为统计隐藏性承诺的输出，其可以作为下一个承诺的随机性
Instantiating the NP statement POUR
具体而言，对于于$i\in\{1,2\}$，$\mathtt {POUR}$检查下列各项
- 对关于树根$rt$的叶节点$cm_i^{old}$，检查$path_i$是一个合法的验证路径
- $a_{pk,i}^{old}=\mathcal H(a^{old}_{sk,i}||0^{256})$
- $sn_i^{old}=\mathcal (a^{old}_{sk,i}||01||[\rho^{old}_i]_{254})$
- $cm_i^{old}=\mathcal H(\mathcal H(r^{old}_i||[\mathcal H(a^{old}_{pk,i}||\rho_i^{old})]_{128})||0^{192}||v_i^{old})$
- $cm_i^{new}=\mathcal H(\mathcal H(r^{new}_i||[\mathcal H(a^{new}_{pk,i}||\rho_i^{new})]_{128})||0^{192}||v_i^{new})$
- $h_i=\mathcal H(a^{old}_{sk,i}||10||b_i||[h_{sig}]_{253})$，其中$b_1=0,b_2=1$
此外还需要检查平衡性是否满足，也即检查$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}=2^{64}-1)$
定义Merkle树深度最大为64，因此最多可以有$2^{64}$个币
Instantiating Sig
对于签名方案，采用ECDSA来维持与现有比特币源码的一致性和兼容性，不过标准的ECDSA是可扩展的，也即$(r,s),(r,-s)$两者都是合法的签名，本文的方案采用不可扩展的变体，其中限制$s$于域元素的低半部分
尽管本文不知道该变体正式的$SUF-1CMA$证明，但其使用与解决比特币交易可塑性[Wui14]的建议一致（在实践中，可以用满足$SUF-1CMA$安全性的EC-Schnorr签名替换ECDSA变体，并对椭圆曲线的域元素进行适当编码后也可以达到类似的效果）
Instantiating Enc
对于加密方案，利用密钥保密的椭圆曲线加密方案ECIES[Cer00]，因为其是为数不多的具有可用实现的标准密钥专用加密方案之一
5.2 Arithmetic circuit for pouring coins
根据第四章提到的DAP方案的构造，其是通过在算术电路$C_{\mathtt {POUR}}$上调用zk-SNARK以获得算术电路可满足性，该$C_{\mathtt {POUR}}$验证NP语句$\mathtt {POUR}$
本文依靠[BCTV14]中的实现来实现基本的zk-SNARK，并将其应用于电路$C_{\mathtt {POUR}}$，其具体结构描述如下
5.2.1 An arithmetic circuit for verifying SHA256's compression function
$\mathtt {POUR}$中主要是验证压缩函数$\mathcal H$的计算，因此首先讨论用于验证SHA256计算的算术电路$C_{\mathcal H}$，5.2.2节中给出该电路的构造
因此需要构建一个算术电路，满足对于任意的$256 bit$长度的hash值$h$及其$512 bit$的输入$z$，当且仅当$h=\mathcal H(z)$时，有$(h,z)\in R_{C_{\mathcal H}}$
根据zk-SNARK的间接性，显然希望将电路$C_{\mathcal H}$最小化，本文通过严格遵守SHA256的标准，逐块构建$C_{\mathcal H}$，对于SHA256的每个子计算，通过引入不确定性和域运算，并使用尽可能少的门来验证子计算
Overview of SHA256's compression function
回顾一下SHA256，其基本单元为一个$32 bit$的字，所有子运算都是基于字的子运算，包括位运算（and/or/xor），右移/循环右移，模$2^{32}$加法
压缩函数内部保存一组状态（包含八个$32bit$字），其初始化为固定值，然后按照64字的消息列表（由输入$z$推导而来）在64轮中进行状态转换，得到的$256 bit$的输出为最终八个$32bit$字的拼接
Representing a state
若每个字的操作（除了模$2^{32}$加法），其输入被表示为单独的线时，验证操作更有效（因为每个线都仅携带一个位），因此$C_{\mathcal H}$将八个$32bit$字保持为256根独立的线，此时64字的消息列表保持$为64\cdot 32=2048$根线
Addition modulo 32
为了验证模$2^{32}$加法，本文采用之前工作中使用的技术[PGHR13、BCG+13、BCTV14]
对于给定的两个字A,B，计算$\alpha=\sum_{i=0}^{31}2^i(A_i+B_i)$，由于域$\mathbb F$的特征大于$2^{33}$，因此因此不存在线的环绕（循环），此时域上加法与整数加法一致
之后对$\alpha$的各个位（包含进位，共33 bit）$\alpha_i$进行非确定性预测，并要求$\alpha=\sum_{i=0}^{32}2^i\alpha_i$来加强一致性，以确保每个$a_i\in\{0,1\}$，然后采用一个包含33个门的子电路来计算$\alpha_i(\alpha_i-1)$，当所有这些计算均为0时子电路才满足要求
总而言之，验证只需要34个门，该方法可以扩展到两个或以上的项的求和
Verifying the SHA256 message schedule
消息列表的前16个字$W_i$为512 bit的输入$z$，剩余的48字计算如下
$$ W_t=\sigma_1(W_{t-2})+W_{t-7}+\sigma_0(W_{t-15})+W_{t-16} $$
其中加法为模$2^{32}$加法，$\sigma_0(W)=rotr_7(W)\oplus rotr_{18}(W)\oplus shr_3(W)$，$rotr$为循环右移，$shr$为右移，$\sigma_1$操作类似，区别在于移位数不一样，且$\sigma_0$和$\sigma_1$中两个移位操作的移位数都是常数，因此循环移位和移位可以通过与先前计算的位进行适当的拼接来实现（右移只需要在高位补0即可）
因此，$3 bit$的xor需要两个门，从而可以在64个门的电路中实现$\sigma_0$和$\sigma_1$，然后计算（准确的说时猜测和验证）模$2^{32}$加法
Verifying the SHA256 round function
轮函数通过修改8字状态中的其中两个来修改整个8字状态
每次修改的两个字为下列模$2^{32}$加法的结果
- 由轮数指定的加法常量字$K_t$
- 消息列表中的字$W_t$
- 将简单函数作用于当前状态得到的字
然后是两个函数
$$ \begin{aligned}&Maj(A,B,C)_i=0 \ if \ A_i+B_i+C_i\leq 1,else =1\\ &Ch(A,B,C)_i=B_i \ if A_i=1,else C_i\end{aligned} $$
利用两个门来验证$Maj$函数每个输出位的正确性，$Ch$函数只需要一个门
对于剩余的六个不变的状态字，不将其直接复制，而是通过使用之前子计算的输出线作为当前子计算的输入，从而将置换隐含在电路中
Performance
综上，可以得到了一个算术电路$C_{\mathcal H}$，用于验证SHA256的压缩功能，其算术门数少于30000个，门的数量详见下图
Comparison with generic approaches
接下来从头开始构建电路$C_{\mathcal H}$，我们本可以选择更通用的方法：用更高级的语言实现SHA256的压缩函数，并使用电路生成器获得相应的电路，然而对于本文的应用程序来说，通用方法的成本要高得多
从PolarSSL（一种流行的密码库）[Pol13]中的SHA256实现开始，编写计算$\mathcal H$的C程序相当简单，因此本文编写了这样一个程序，并将其作为[PGHR13]的电路生成器的输入，但是其输出电路有58160个门，比上面提到的方案大两倍多
还可以将相同的C程序编译到TinyRAM，这是[BCG+13]中支持的体系结构，此时可以获得一个包含5371条指令的汇编代码，该代码在TinyRAM上执行需要5704个周期，若对这个TinyRAM程序加以时间限制时，此时可以调用[BCG+13]中的电路生成器，但是每个TinyRAM周期的成本约为1000个门，因此该方案产生的电路至少有$5.7\cdot 10^6$个门，比上面提到的方案大190倍以上
类似的计算适用于[BCTV14]中的电路生成器，它支持更灵活的体系结构，总而言之本文从零开始构建$C_{\mathcal H}$确实要好得多（不过SHA256计算几乎是一种“电路计算”，无需复杂的程序流或者访问内存等）
5.2.2 Arithmetic circuit for $\mathtt {POUR}$
接下来介绍一下$C_{\mathcal H}$电路的构造
NP语句$\mathtt {POUR}$需要验证基于$\mathcal H$的Merkle树中的成员身份、几个额外的$\mathcal H$调用以及整数加法和比较，我们通过组合不同的子电路来验证每一个$\mathcal H$调用，从而构建用于$\mathtt {POUR}$的电路$C_{\mathtt {POUR}}$
此外还需要讨论用于验证Merkle树中成员身份的子电路（使用前述子电路$C_{\mathcal H}$验证$\mathcal H$的调用），以及整数加法和比较
Merkle tree membership
需要构造一个算术电路，在给定根$rt$、认证路径和币承诺$cm$的情况下，当且仅当路径是叶节点$cm$相对于根$rt$的有效认证路径时，该电路才满足要求
认证路径包括下列内容
对于每个层$i$，辅助哈希值$h_i$和位$r_i$，若$h_i$为父节点的左子节点，则$r_i=0$，否则$r_i=1$，然后通过验证$\mathcal H$的调用来自下而上的检查Merkle树中的成员身份
对于树的深度$d=64$，设置$k_{d-1}=cm$，然后对于$i=d-1,...,1$，若$r_i=0$，则令$B_i=h_i||k_i$，否则令$B_i=k_i||h_i$，然后计算$k_{i-1}=\mathcal H(B_i)$，最后检查根$k_0$是否与给定的根$rt$一致，也即检查$k_0==rt$
Integer addition
我们需要构造一个算术电路，在给定$64 bit$整数$A,B,C$（以二进制字符串表示）的情况下，当且仅当$C=A+B$在整数上时满足该电路
依赖于域$\mathbb F$足够大且没有环绕线路的特性，因此通过检查域$\mathbb F$上的运算$\sum^{63}_{i=0}2^ic_i=\sum^{63}_{i=0}2^i(b_i+a_i)$足矣
Integer comparison
我们需要构造一个算术电路，给定两个$64 bit$整数$A,B$（以二进制字符串表示），当且仅当$A+B<2^{64}$时满足该电路
需要检查$\sum ^{63}_{i=0}2^i(b_i+a_i)=\sum^{63}_{i=0}c_i(c_i\in \{0,1\})$，显然，若有$A+B<2^{64}$，则$c_i$表示$A+B$的每一个二进制位足矣，若有$A+B\geq2^{64}$，在没有任何一个$c_i$可以满足$\sum^{63}_{i=0}c_i\leq2^{64}-1$
该检查需要65个门，64个为布尔值$c_0,...,c_{63}$，剩余的一个门为比较门
这个部分没看懂，不知道等式$\sum ^{63}_{i=0}2^i(b_i+a_i)=\sum^{63}_{i=0}c_i$的左侧需要乘一个$2^i$，不确定是自己没理解还是原论文有误
Overall circult sizes
见下图，上述方案中超过99%的门都用于检查$\mathcal H$的调用
