公共参考串
除了随机预言机，NIZK还能采用「公共参考串」（Common Reference String），简称「CRS」来生成随机challenge c。如果说「随机预言机」是隐式地引入了第三方，那么「公共参考串」就是直接显式引入第三方。
还记得「阿里巴巴和哈密尔顿回路」吗？哈密尔顿回路是图中经过所有节点仅一次的回路，寻找哈密尔顿回路是一个NPC问题。
上图是一个IZK，Alice向Bob证明自己知道图G的哈密尔顿回路，证明的交互过程是：
- Alice随机拖动图G，生成图G’（拖动操作对图来说是「同构」的，不会改变图的哈密尔顿性质），Alice将变换后的图G’加密发送给Bob；
- Bob发出挑战b；
- 如果b为0，Alice发送变换函数Perm 并解密G’，Bob验证G’是否由原图G通过变换函数Perm 得到；
- 如果b为1，Alice计算原本的哈密尔顿回路C在变换之后的位置C’，解密G‘中C’所在的位置，Bob验证解密的是否为一个哈密尔顿回路。
当b为1时，Alice解密的C’属于G’，根据集合的性质!G’应该属于!C’（原图的补集应该属于哈密尔顿回路的补集），所以上图的交互过程也可以更改成：
观察上图，变换之后证明的交互过程是：
- Alice随机拖动哈密尔顿回路C，生成C’，Alice将变换后的哈密尔顿回路C’加密发送给Bob；
- Bob发出挑战b；
- 如果b为0，Alice解密C’，Bob验证C’是否是一个哈密尔顿回路；
- 如果b为1，Alice计算原图G在变换之后的位置G’，发送变换函数Perm 并解密C’中的!G’，Bob验证解密的位置是否全部为0（即!G‘是否属于!C’），同时验证G’是否由原图G通过Perm 变换得到。
这跟「公共参考串」「CRS」有什么关系呢？
我们仔细观察能够发现，交互式证明的第一步「Alice随机拖动哈密尔顿回路C，生成C’」是跟图G无关的。所以完全可以通过第三方生成一个随机的哈密尔顿回路C’，而使用随机的C’和C反向算出变换函数Perm。
由于C’是第三方提供的，所以b为0没有了意义，Bob只需要检验b为1的情况。但第三方生成的C’是不能被Bob看到的，因为一旦Bob看到了C’，又知晓变换函数Perm，是很容易逆向算出原图G的哈密尔顿回路C的，所以C’必须是对Bob的「隐藏比特」。Bob收到Alice发送的!G’后，需要做两个验证，一是验证G’是否由原图G通过变换函数Perm生成，二是验证隐藏比特C’中，!G’位置是否都为0（即验证!G’是否属于!C’）。
该协议同样可以通过模拟证明是ZK的，这里不展开。
但到这一步还没有结束，因为第三方生成的C’是只有Alice能够看到的，而Bob无法看到，因此还不能说C’是「公共」的参考串「CRS」。解决问题的办法是使用「限门置换」：
「限门置换函数」是一个正向很容易计算但反向很难的函数，可以把它理解为一种加密。同时限门置换也可以匹配一个「Hardcore Predicate」，Hardcore Predicate能生成我们需要的隐藏比特，隐藏比特中含有哈密尔顿回路C’。当在哈密尔顿回路NIZK中，Alice需要揭露!G’所对应的某个隐藏比特时，它提供对应位置的x，Bob在收到x后，会通过Hardcore Predicate验证对应的隐藏比特是否为0，同时通过限门置换函数F严重对应的CRS是否正确。
这样就实现了CRS，而哈密尔顿回路又是NPC问题，任何NP问题都能在多项式时间内规约到哈密尔顿回路问题，所以基于NP问题的IZK都能通过使用CRS变成NIZK形式了。
zk-SNARKs
Vitalik在21年写过多篇文章介绍zk-SNARKs，这里认为有必要简述以下。zk-SNARKs，全称「零知识简洁的非交互式知识论证」，zk-SNARKs常常使用随机预言机来实现NIZK（IZK的Fiat-Shamir变换），但他们的IZK形式通常不是Schnorr协议，而是哈希串的多项式比较验证等形式。
