区块链原理与技术笔记

区块链密码学基础

杂凑函数

关于单向性的描述：

任给y，由y=H(x)计算x困难

不严谨，因为$x$的选择会出现特殊情况: $H(1),H(0)$等, 严格定义为

$$Pr[x\leftarrow X_R,y\leftarrow H(x),x'\leftarrow A(y):H(x')=y] \leq neg(n)$$

就是说Challenger在$X_R$集合中均匀随机的选择$x$,计算$H(x)=y$,敌手Adversary由$y$计算出$x'$,$H(x')=y$的概率极小.

零知识证明

零知识证明指证明者P能在不向验证者V提供任何有用信息的情况下，使验证者相信某个论断是正确的。

数学表示

证明者P要证明的关系通常表示为一种NP关系L，对于某一字符串$x$,证明者P知道对应的证据$w$,使得$x\in L$可以被公开验证.

零知识证明应满足的三点性质:

• 完备性(V无法欺骗P) 诚实的证明者P和验证者V,如果$x\in L$且$w$是其证据,则验证者总会接受证明者提供的证明
• 可靠性(P无法欺骗V) $x\notin L$或者P不知道$w$,P就不能找到一个诚实验证者接受他的证明
• 零知识性 V无法获得任何额外的信息