蒙上眼睛的证明

回想“可验证的科学”章节里，我们通过椭圆函数的单向放大性，设计了椭圆函数签名。在不泄露私钥的情况下，也能够向对方证明该签名是我的私钥完成的。这就是我们需要的“信任的安全传递”。椭圆函数签名太过复杂，我们用相对简单的哈希变换，来实现同样的效果。哈希变换是一种将任意字符串随机转化为另外一种特定长度字符串的编码方式。编码是随机的，但也是固定的。从源码出发，永远都会得到相同的编码，而且不同的源码对应的编码也不冲突。但是从编码出发，却无法反推到源码。就好像一扇单向门，永远只能走一个方向。

One-time Signature 单次签名

现在小北基于这种编码，制作了一个迷宫。迷宫周边有26个向外开放的门口，用字母A~Z表示。迷宫里面有无数连接这些门的通道相互交错。通道上有很多单向门，如果不小心走错了，可能永远都走不出来。小北住在这个迷宫的某一个入口，但是没有人知道。一天小北放了一个信箱在Z出口，她说欢迎大家给她寄信。为了防止有人偷看，小北把Z的门锁上了，只留下投信的小缝，她说她会从住的地方走过来拿信的。小楠听了不相信，你怎么证明这个信箱是你的呢？于是小北把小楠带到了F入口，她说你进去右转右转再左转，就可以看到信箱了。小楠一试果然如此，但是这样F入口就暴露了，难道小北住在这里？小北微微一笑，从F入口到Z是单向门，但是从F入口到不了她家，这只是她取信时候途径的一个地方而已。

其实小北住在S，这个S就是小北的私钥，F就是签名可以用于验证，Z是她的区块链地址。编码的生成过程是从S经过几十次哈希生成F，再从F经过几十次哈希生成Z。但显然这个F一旦用过一次以后，就不能再用了。所以这种基于哈希的签名方法，叫做一次性签名one-time signature 简称OTS。这种算法的一大优点是计算速度快，而且抗量子破解 Quantum Resistant，也就是发明了量子计算机也无法破解出私钥（椭圆函数签名可以被量子破解）。但缺点也很明显了，每一次签名验证，都会暴露哈希链条里的一段，从F到Z的所有点都会一起暴露。当然链条足够长，几十个哈希点可以再往上选出一个来做签名。OTS签名也经过了很长的发展历程，现在IOTA项目里使用的就是相对成熟的winternitz OTS 版本：

用户生成SEED
基于SEED和编号ID一起生成10个区块链私钥:PriKey
私钥经过26次哈希得到公钥: PubKey = Hash^26(PriKey)
    公钥发布到网络用于收款
取款时进行签名
    将交易内容的文本，映射到0~26之间的数值: N = f(TxContent)
    根据该数值对私钥进行N次哈希(N不能为0，否则泄露私钥) 得到签名Sign = Hash^N(PriKey)
矿工对签名验证以确认交易
    基于相同的交易内容，映射到26~0之间的数值: M = 26-f(TxContent)
        可见：M+N=26
    矿工对签名进行M次哈希，数值结果和公钥（一共经过26次哈希）一致则验证成功
        Hash^M(Sign) = Hash^M( Hash^N(PriKey) )
                     = Hash^(M+N)(PriKey)
                     = PubKey
    如果交易内容被篡改，M就会出错，或者签名有问题都无法算出公钥，导致验证失败

这种方便快捷的签名方法，要反复使用也可以。比如IOTA官方节点milestone的签名就使用了Merkle Trees的方案，在保证官方节点地址不变的情况下，还可以反复支付和签名：

milestone节点生成大量私钥，并关联在一棵 Merkle Tree上
milestone公布 Merkle Root，并且始终不变
交易时随机选择 Merkle Trees某个叶子节点对应的私钥来生成签名和公钥
    公钥不直接提供，只提供对应的 authentication path
矿工对签名进行验证
    先计算M，做哈希变换，得到待验证的公钥
    结果按照验证路径，逐一和路径上的节点编码组合哈希，并一路向上传递
    最后获得 Merkle Root则验证成功

这类编码方式还可以用在数据资产的验证上，CarChain项目里，我们可以把车辆行驶轨迹的隐私数据，经过多层哈希压缩后，登记在区块链智能合约里。这样在数据交易和授权使用时，就可以通过OTS签名，在不泄露隐私的情况下，完成蒙上眼睛的证明。

Zero-knowledge Proof 零知识证明

显然只有两方参与的验证太局限了，区块链是交易双方和矿工共同维护的多方验证平台。我们需要一种在不泄露交易双方金额明细的情况下，能够完成区块验证的证明方式。幸运的是密码学里早已有了这样的工具，叫做零知识证明zero-knowledge proof，他的进化版 Non-interactive zero-knowledge proof 是无交互的零知识证明。我们还是用小北的迷宫来举例：

小楠觉得小北的迷宫很神奇，所以打算搬过来和小北一起住。她的母亲不放心，想来照看她。但小楠正值无拘无束的年纪，她不想让母亲知道她的房间，但又要让母亲放心。所以小北帮她重新设计了迷宫。这一次A~Z的门之间，不是路径串联的关系，而是配对映射的关系。从任何一个门进去，都会穿到另外一个门出来。对应关系是未知的，但可以保证，如果从相邻两个门进去，也会从相邻两个门出来。小楠让母亲转过身，她和小北分别回到各自迷宫的入口。大家准备好以后，母亲回过身来，小楠和小北从各自房间穿过迷宫。当他们分别出现在J、K两个出口时，小楠向母亲解释说，她和小北是住在隔壁门的，平时相互照应生活很好，不用家里太担心。

这个证明原理应用在交易领域就好比我不知道你们两个人分别有多少钱，但是我知道你们加起来一共有50元钱。背后用到了数学中的加法同态，以及推广到乘法同态和更加通用的多项式同态：

对于E(x)函数有以下属性：
  1、难求反函数，及无法从E(x)反推x
  2、单调函数，及x≠y,，则E(x)≠E(y)
  3、通过E(x)和E(y)，可以计算E(x+y) 的加法同态
     常用的的非对称加密方式RSA和ECC都支持加法同态
C对于A、B两人账户的加法盲证明：
  A计算自己账户余额E(A)，B计算自己的E(B)
  结果发给C，C通过E(A)和E(B) 计算E(A+B)
  交易前的E(A+B)和交易后的E(A'+B')保持一致，则交易没有作弊
  A、B对各自隐私的收款金额无异议后，区块可以认证该交易

区块链里已经有不少该原理的应用，2016年10月发布的ZCash，优化了交易速度，弥补了部分这个技术的短板，使其更具有实用性。同年以太坊的提案zkSNARKs，目前还在测试阶段，并没有落地。其依赖 “可信启动”，“椭圆曲线”这些重度假设是最大的短板。此外Komodo是SuperNET团队从ZCash做的分叉，使用Delayed Proof of Work (dPoW)把自己的账本和比特币主链对账，借用比特币的算力来做备份防护。最近2018年初又从比特币分叉出了Bitcoin Private (BTCP)，就是合并了ZClassicCoin (ZCL)和BTC主链的一个分叉，采用的也是zkSNARKs。可见该证明机制已在区块链领域广泛应用，在保护隐私的同时，免去了混合交易的中间商，也就加强了信任的流通传递。

为了解决zkSNARKs的短板，最近两年有了新的尝试ZK-STARKs。这里的 T 表示 “transparent”，代表无需“可信启动”。同时也带来了更加简单的密码学假设，避免了使用椭圆曲线，而是完全基于哈希和信息论。这也意味着满足了抗量子计算攻击的能力。新设计的核心是多项式采样验证，假设需要验证的数据被编码在了一个1,000,000次幂的多项式里，那么任意选取1,000,001个点都可以恢复这批数据。但这样验证起来太繁琐，我们把需要证明拥有的多项式P(x)，转化为两个多项式Z(x)和D(x)的乘积，并取x在1~1亿之间随机验证几次。由于原多项式P(x)被保护起来，而且极大的放大了检查空间，所以随便检查1次，作弊者蒙对的概率都不到1%。检查16次后，该方案的欺骗难度和哈希碰撞一样高。具体构造过程如下：

你有一个多项式P，对于从 1~1百万 之间的所有x，P(x)是一个整数
    这个P(x)相当于私钥，可以把某些数据编码进去，也可以本身就是某种计算规则
    你想要在不公布P的情况下，证明P的函数特性
        比如 0 <= P(x) <= 9
构造一个检查多项式C(x)，使得C(P(x))在P满足特性的情况下，恒等于0
    范围约束的检查多项式可以简单构造为 C(x) = x·(x-1)·(x-2)...(x-9) 
        如果P(x)的范围超过0~9 那C(P(x))则肯定不为0
    关联约束比如斐波那契的检查多项式要引入多变量： C(x1, x2, x3) = x3 - x2 - x1
        则 C(P(x)) = C(P(x), P(x+1), P(x+2)) = 0
任何等于零的多项式都可以分解为 Z(x)和一个乘积，所以原证明转变为 C(P(x)) = Z(x) * D(x)
    x的检查空间在 1~10亿 之间
    Z(x)是由C(P(x))的根组成的多项式，需要提供给验证者，类似加密“公钥”的作用
        Z(X)数据量庞大，所以一般公开编码进Merkle Tree，客户端只保存Merkle root
    D(x)由多项式除法 C(P(x)) / Z(x) 得到，基于傅里叶变换
    P(X)和D(x)由证明者自己编码Merkle Tree，同样公开Merkle root的哈希
        这里令等式成立的有效值只有 100万/10亿 = 0.001 的命中率
验证者在1~10亿间随机选择16个x
证明者提供这16个x在P(x)和D(x) Merkle Tree的分支
验证者检查：
    分支与之前提供的 Merkle 根相匹配
    C(P(x)) 在所有 16 种情况下都等于 Z(x) * D(x)
    一个坏的p(x)通过检查的概率，在经过16次检查后会缩小到 1- 10^-32

除了例子里的情况，其他不同的多项式特征，都要对应不同的检查多项式。有些还需要对特定值进行边缘检查。遇到特别大的数值，还需要使用有限域（finite field）的算数规则。这些都使得这种证明变得复杂，一个zk证明的大小将从 288 bytes 上升到几百kb。此外还需要对一些非多项式的逆工程攻击做防御，最后推广到一般特性的证明。详情可以看Vtalik博客的翻译版本（Part1，Part2)，还有未翻译的Part3。zk-STARKs是一种数学构造，并没有标准解法，在实际应用前还需要很多的优化。

Ring signature 环签名&群签名

零知识证明主要保护交易金额的匿名，但交易双方的地址是公开的。以Monero为代表的隐私链使用Gregory Maxwell的环形机密交易（Ring Confidential Transactions）算法，把交易双方进一步隐藏起来，实现完全的隐私。这种签名机制其实有两个版本：

有管理员的版本是群签名（Group signature），由群管理者生成群公钥（Group Public Key）、私钥（Group Private Key）。加入该群的成员获得群管理者颁发的群证书（Group Certificate），就可以生成群签名。利用群公钥可以对签名做验证，但是无法定位到具体的签名者。在争议爆发的时候，就需要群私钥解开签名提取真正的签名者。

加强版的环签名（Ring signature）则没有管理者。签名者利用自己的私钥和集合中其他成员的公钥就能独立完成签名，不需要其他人的帮助，集合中的其他成员可能都不知道自己被包含在其中。具体过程：签名者用自己的私钥和任意n个环成员的公钥为消息m生成签名a；验证者根据环签名和消息m，验证签名是否是环中成员所签。最初这种设计是用来保护wikileaks这类泄密者的。比如多名白宫官员通过环签名，公布棱镜门的秘密后，政府无法罪责到具体个人。现在Monero使用该机制来保护数字货币的交易者隐私：加上key image对币的染色，矿工可以验证该数字币的唯一性（类似序列号，检查是否被注册过）并防止double spending。再加上RingCT对金额的加密，功能已经齐全了。加拿大滑铁卢大学团队搞的Iotex项目也是同时使用了零知识证明和环签名，该技术正在逐渐成为区块链隐私保护的主流。