ZKP:证明可变长度哈希预图像的知识

Question

目前，我正在尝试使用不同的zkp系统实现来实现对公共散列映像的预映像知识的证明。

有很多例子正是这样做的(请参阅此问题以获得进一步参考。)。但是:所有这些都有一个固定的哈希函数输入大小(通常是两次256位来做merkle树的证明)。现在，虽然这是非常方便的例子，我想让前置图像是可变的长度。

我对此有几个问题：

1. 是否可以在zkSNARK中输入可变长度的输入，其中验证器和验证器键必须事先计算？我可以创建一个允许任意输入长度的prover键吗？据我理解，这是不可能的，并且验证程序必须在可信设置之前显示预图像长度。
2. 在防弹中，我必须将预图像分割成32个字节的块，将它们表示为标量并提交给每个块。有没有办法避免与预图像大小成线性关系的承诺量？

Answer 1

(我写这些的时候，后脑勺都是防弹衣)

可变长度输入

据我所知，不可能实现文字变量/秘密长度输入，除非允许我稍微修改您的定义。如果允许输入长度达到一定数量的n_{max}，那么您可以改变它下面的长度。例如，为了实现这一点，您可以始终提交n_{max}输入，其中将第一个n输入设置为实际输入v_1,\dots,v_n，将最后一个n_{max} - n设置为语义上无意义的输入。那么你的证明协议可以是：

\bigvee_{i=1}^{n_{max}} \text{statement when length = }i\text{ using } \{v_1,\dots,v_i\}

也就是说，你写了一个证明，这是为了证明长度i的语句的分离。当然，这会使你的陈述更加复杂，但是像防弹这样的系统可以很好地压缩它。您需要n_{max}-1附加乘法器来进行分离，因此，如果您的length i语句需要\text{poly}(i)乘法器，那么总的语句长度将类似于\mathcal{O}(\log(n_{max}\cdot \text{poly}(n_{max}))) = \mathcal{O}(\log(n_{max}) + \log(\text{poly}(n_{max}))),，这会给您一个恒定的开销。

常量承诺

与大众的看法相反，防弹证人不一定需要投入承诺。这篇防弹论文实际上为Bootle等人的2016年原始协议做了两件主要事情:降低内部产品论证的复杂性，并增加对Pedersen承诺的支持。后者只是意味着您不必在电路中实现Pedersen承诺(这将大大损害性能)。因此，避免分组和提交的方法是完全避免提交。毕竟，您已经可以将哈希看作是(不完美的隐藏)承诺。

如果您想在主防弹方程(W_L\cdot\vec a_L + W_R\cdot \vec a_R + W_O\cdot \vec a_O = W_V\cdot \vec v + \vec c)中了解这一点，请注意，\vec v并不是整个见证；\vec a_L, \vec a_R \text{ and } \vec a_O也是见证的一部分。

如果您想要一个如何在实践中这样做的例子，请看一看防弹算术电路的出色的锈蚀实现。例如，他们的r1cs.综合范围验证试验将见证号分解为64个不同的位变量，约束比特，然后将其绑定到承诺中。您可以完美地修改该代码，将位绑定到散列输入小工具，并将散列小工具的输出约束为哈希值。

当然，这都需要输入长度的知识，但是上面的技巧可以用来隐藏长度直到某个范围。

希望这对你的案子有帮助！