匿名区块链和零知识证明

2018-03-02 黄毅

比特币有隐私问题。比特币的匿名性只体现在地址没有关联真人身份,但是所有交易信息却是完全公开的。 一旦别人知道你的比特币地址(比如他给你转过帐),他就可以从链上查到你所有的交易历史和余额。 尽管比特币推荐每笔交易都使用新地址,并且HD钱包技术可以自动管理这些地址,不需要用户操心。但是通过观察交易的模式,还是很容易发现这些地址的许多关联。

类零币(zcoin, zcash等)就是尝试解决这个问题。

传统的解决方案是中心化的混币操作,比如充值给交易所,再从交易所提现,因为交易所有许多地址,充值和提现的操作使用的很可能是不同的地址,这使得两笔交易之间在地址上没有关联。如果在余额和操作时间上再做点处理,可以让两笔交易完全没有关联,也就达到了真正的匿名性。这个方法唯一的问题是依赖中心化的交易所。那我们现在要做的就是利用密码学工具在链上解决这个问题。

images/coinmix.png

传统混币模式

类零币解决这个问题的思路大体上和混币类似:

  1. 先做一笔铸币交易(充值到零币):消耗一定的比特币,产生一个零币。
  2. 再做一笔使用交易(从零币提现): 消耗一个零币,产生一定比特币到目标账户。
images/zerocoin.png

零币模式

这里的关键就在于,从零币提现时你不需要指定具体是哪一个零币(否则就暴露隐私了),你只需要证明这个零币在里面,没用过,并且你有权限使用。要实现这一点就涉及到所谓的零知识证明。

零知识证明顾名思义,就是在不泄漏具体信息的前提下,向别人证明你知道某个信息。举一个例子:

战争中你被俘了,敌人拷问你情报。你是这么想的:如果我把情报都告诉他们,他们就会认为我没有价值了,就会杀了我省粮食,但如果我死活不说,他们也会认为我没有价值而杀了我。怎样才能做到既让他们确信我知道情报,但又一丁点情报也不泄露呢?

这的确是一个令人纠结的问题,但阿里巴巴想了一个好办法,当强盗向他拷问打开山洞石门的咒语时,他对强盗说:“你们离我一箭之地,用弓箭指着我,你们举起右手我就念咒语打开石门,举起左手我就念咒语关上石门,如果我做不到或逃跑,你们就用弓箭射死我。”

强盗们当然会同意,因为这个方案不仅对他们没有任何损失,而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题。阿里巴巴也没损失,因为处于一箭之地的强盗听不到他念的咒语,不必担心泄露了秘密,而且他确信自己的咒语有效,也不会发生被射死的杯具。

这种证明方式称为交互式的,因为证明方和验证方需要进行多次交互才能完成证明。但是在区块链上,我们要向所有矿工进行证明,只能使用非交互式的方式。也就是,我把证明内容提交给区块链网络后,矿工可以独立完成验证,不用再问我问题。显然,非交互式的零知识证明才是真正的黑科技。

和很多密码学工具一样,非交互式的零知识证明也依赖一些神奇的数学工具:

注解

存在加密函数 E(x) 使得:

  1. 如果x, y不同,那E(x), E(y)也不同。
  2. 根据E(x)很难反推x的值。
  3. 根据E(x)和E(y),可以计算一些表达式的加密值,比如E(x+y)

前面两条性质是哈希函数就满足的,重要的是第三条,第三条意味着我们在不知道x和y的情况,可以验证相关多项式的加密值。

比如说我要想你证明,我知道两个数a, b 使得:3 * a + 4 * b = 100,我只需要告诉你 E(a) 和 E(b) ,你就可以验证 E(3 * a + 4 * b) 是否等于 E(100) 。

同时为了防止你结合 E(a), E(b) 的值,以及表达式自身的性质去成功反推a和b,我还可以生成一个随机数r。 因为 3 * (a - r/3) + 4 * (b + r/4) = 100 ,然后告诉你 E(a - r/3) 和 E(b + r/4),你还是可以成功验证,但绝对无法反推a和b的值。 这就是叫做随机偏移。

现在我们再增加一条黑科技:

注解

无论多复杂的验证问题都可以最终简化为一个多项式验证问题!

比如这么一个多项式:

P(x) = a0 + a1 * x + a2 * x^2 + … + ad * x^d

多项式验证问题是说,我要向你证明我知道这个多项式的系数,并且这个多项式的值满足一个公开的性质。

一个方法是,你给我一个随机数r,我算一个P(r)给你,你验证它满足性质。 抛开交互的问题(后面会说),它还存在一个问题:因为性质的公开的,坏人可以根据你给的r,伪造一个能满足性质的值。

按照我们加密函数的性质,你可以发送 E(1), E(r), E(r^2) ... E(r^t) 给我,我就可以计算 E(P(r)) 的值,并且不暴露r。 同样还可以在这基础上加上随机偏移。

这样我们就成功验证了多项式上一个随机点满足要求,两个多项式刚好在这个点相交的概率是很低的, 不过为了加强安全性,你再多发一个随机数k给我,我给你计算一个 E(kP(r)) 给你,按照数学(Knowledge of Coefficient Assumption)的理论, 你可以认为我确实知道这个多项式的系数了。

最终流程就是:你发两组数给我:[E(1), E(s), E(s2), ..., E(sd)], [E(k), E(ks), E(ks2), ..., E(ksd)],我计算 E(P(s)) 和 E(kP(s)) 给你, 你验证 E(P(s)) 满足性质,并且 E(kP(s)) 是正确的即可。

最后还有这个交互的问题需要解决,为了把算法变成非交互式的,我们可以重用你发送给我的这两串数字,我们在区块链初始的时候,举行一个神秘的"仪式", 生成r和k,并且计算出这两串加密数字,随后把r和k分散成n份,存在这个世界不同角落里n个信任的人手上,确保没有人知道r和k的真实值。

了解了这些数学工具,剩下的细节可以直接去看论文了。


blog comments powered by Disqus

转载请注明出处,收藏或分享这篇文章到: