强隐私安全技术——“零知识证明”的前世今生
10
星期四
2020年12月
借助密码算法来保护数据隐私是一种非常安全有效的手段，本文主要介绍安全性极高的密码学算法“零知识证明”的相关概念、应用及存在的问题。
导读
验“金”室
2020年，疫情的冲击使一些传统行业发展受限，但也为线上办公及电商云服务等赛道带来前所未有的发展契机，随之而来的还有一系列的数据安全和隐私泄露事件。
2月，有安全研究人员表示，化妆品公司雅诗兰黛将一个缺乏保护措施的数据库暴露在互联网上，该数据库存储了4.4亿条记录，其中包含大量的审计日志和邮件地址。
3月，有暗网用户发布了一则名为“5.38亿微博用户绑定手机号数据，其中1.72亿有账号基本信息”的交易信息，售价1388美元。其中，绑定手机号数据包括用户ID和手机号，账号基本信息包括昵称、头像、粉丝数、所在地等。
4月，任天堂发现大约有16万个账号被非法登录，结合之前该公司的泄露事件，大约有30万个账号ID里所包含的出生日期、邮件地址等信息存在可能被泄露的风险。
5月，脱口秀艺人池子微博发布长文，表示自己在处理与上海笑果文化传媒有限公司的合约纠纷时收到来自对方的案件材料，中信银行在未经本人允许的情况下，为“配合大客户的需要”，泄露了他的个人信息，严重侵犯客户个人隐私。
注：以上泄露事件案例来源
https://www.iyiou.com/p/129998.html?share_from=f0f44946R7UuaiSr4Y0VhwAKnpafAGzWspnyl5AR0Iawax0pSU9509zweikQ1NY_SNjTxT18WVeTz0B3KrbWNtl4PXSMfV-SSa_2lo9XiN0rV72e6bE5xVpm1Q
”数据安全事件的频发，加剧了公众对于隐私泄露问题的担忧，借助密码算法来保护数据隐私是一种非常安全有效的手段。零知识证明（Zero-Knowledge Proof）是一种安全性极高的密码学算法，也被认为是当今最好的隐私保护方案之一。
一、零知识证明的概念
S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出零知识证明。它指的是证明者能够在不向验证者提供任何有用信息的情况下，使验证者相信某个论断是正确的。顾名思义，零知识证明包括“零知识”“证明”两个基本特点，证明者在证明自己是某种权益的合法拥有者的过程中，并未向外界透出任何有价值的信息，外界对相关知识的掌握度为“zero”。而验证者除了能够验证证明者提供的证明“proof”是合法有效之外，并未了解除“断言为真”之外的任何知识。
零知识证明起源于交互式证明体系。交互证明在人类历史上由来已久，比如法庭上控方律师对被告的诘问，可以看作是被告对自己无罪辩护的一个交互证明，交互和随机性的作用体现得淋漓尽致。被告在无法提前知晓控方律师所有提问的前提下，编造完美谎言使对方完全信服的概率比较小。
交互性的零知识证明由三段式组成：
（1）证明者P发送一个关于秘密的承诺commit给验证者。
（2）验证者V发送随机数挑战challenge。
（3）证明者P回应挑战，验证者V验证response通过后，即认为P确实拥有某个秘密。也就是说P拥有秘密w，需要提供一个与秘密相关的计算值来证明自己知道这个秘密，其他人又无法通过这个计算值来反推出秘密。通常这样的计算被称为“不可逆计算”。
交互证明模型
在此后的很多年里，密码学界都致力于解决零知识证明交互次数多、性能慢的问题。
1986年，Amos Fiat和Adi Shamir两人提出了Fiat-Shamir变换，通过Hash函数的方法来把一个交互式的证明系统变成非交互式的证明系统，零知识证明的研究迎来了重大突破，非交互性零知识证明技术zk-SNARKs(zero-knowledge Succinct Non-interactive Argument of Knowledge)由此得以发展。其区别于交互性零知识证明的一点是没有或者只有很少交互。
非交互性零知识证明由四个部分组成：
（1）多项式问题的转化。将需要证明的问题归约成多项式问题t (x) h (x) = w (x) v (x)，证明者提交证明让验证者确认多项式成立。
（2）随机挑选验证。随机选择验证的数值s，验证 t (s) h (s) = w (s) v (s)。相对于验证多项式相等 ，随机挑选验证较为简单，验证数据少。在确保足够随机的情况下，安全性还是相当高的。
（3）同态隐藏。指通过借助诸如椭圆曲线等函数的“同态”特性，处理明文输入，确保密文状态下的计算同明文保持一致。
（4）零知识。证明者和验证者之间除了 “问题证明与否” 知识外，不知道其他任何知识（不知道随机挑选值及其多项式计算结果等）。
非交互证明模型（NIZK）
二、零知识证明的应用
1.机密交易
零知识证明技术由于其高安全性、公开可验、交互次数少等特性，适用于解决任何非确定多项式（Non-deterministic Polynomial，NP）问题。而区块链恰好可以抽象成多方验证交易是否有效（NP问题）的平台。因此，两者是天然相适应的。零知识证明作为能实现最强匿名性的隐私保护技术，一直是各大区块链项目重点研究和探索的对象。
从应用的角度看，诸如加密货币、电子存证、身份识别、金融结算等典型的区块链应用场景对隐私保护的要求也越来越高。早期的加密货币项目如比特币，仅在交易身份上实现了一定程度的“弱匿名性”，交易相关的收款人和付款人的比特币地址并未与他们各自在真实世界中的身份信息进行关联，但交易金额的机密性并未得到保障。因而，保障交易身份及交易金额的双重隐私也成为了各大加密货币项目发展的重点。
基于以上问题，Maxwell于2016年提出了“机密交易（Confidential Transaction）”的概念，其核心思想是交易金额（即UTXO中各个输入和输出）用承诺算法进行隐藏；同时,为了支持公开可验证性，机密交易会包含一段零知识证明，用来证明交易的输入总和大于输出总和，且所有的输出都是正数。换言之，要保证交易的合法性需要满足两点要求：一是现有余额要大于转账金额，二是转账金额要大于0。
在生成证明及验证交易的过程中，所有数据都是密文形态，因而能有效保证交易的隐私性。著名的加密货币如门罗币（Monero）和大零币（Zcash）等都是基于零知识证明技术实现的隐私性。零知识证明技术在加密货币领域已经得到实践和发展。
除此之外，零知识证明也广泛地应用于链上数据压缩及交易扩容等公链项目，代表项目有Filecoin和Loopring DEX3.0等。
2.链上数据压缩
Filecoin是存储行业比较热门的项目，它搭建的是一个去中心化的存储交易平台。去中心化的存储核心问题是如何证明存储提供方真实有效地存储了指定的数据。Filecoin是通过两种零知识证明算法：PoREP（复制证明算法）、PoST（时空证明算法）来解决上述问题。
PoREP(Proof-of-Replication)复制证明算法来保证存储的可靠性。在数据处理并存储后，存储方通过PoREP算法，证明数据已经正确处理，并提供最后结果的Merkle树的树根。
PoST每隔一段时间，提交存在性证明。验证方随机抽选一个叶子数据，存储提供者在一定的时间内提供从该叶子数据到Merkle树根的路径证明。如果处理完的数据无法在合理的时间内重建整个Merkle树，也就无法提供证明。
3.交易扩容
路印协议是区块链领域另一热门的零知识证明项目，采用和以太一致的“账户”模型，将所有账户的交易“状态”（余额）都记录在链下。所有和状态相关的操作，都是在链下更改，并提交Proof到链上记录。因为存在链上链下状态的同步，账户的任何操作有三个状态：
1/ Committed （操作已经提交）
2/ Verified （该操作已经提供了相应的Proof）
3/ Finalized（之前所有的操作都已经提交正确的Proof）
以一个转账场景为例：
用户转账到路印协议的智能合约，链上完成充值后，该操作的状态就是“Committed”。链下的第三方中继器Relay，监测到“Committed”的状态后，更改链下的状态，生成Proof，并将证明提交到链上，此时该“充值”操作的状态为“Verified”-链下也已经完成充值。如果之前的所有操作都是Verified，那该操作的状态就是Finalized（也就是这个状态是确定的，不会被篡改的）。
在交易足够多的情况下，路印3.0的TPS在目前的以太坊上达到了350。在以太坊完成君士坦丁堡升级后，TPS能达到1400。每笔交易的平均费用大约在1美分（该TPS数据来源于互联网）。链上链下协同处理的模式使得零知识证明技术在保证交易数据隐私的前提下提升了交易的性能。
4.合规性证明
零知识证明也能用于证明合规性，金融机构可以用此来证明用户的合规性，比如是否有偿还贷款的能力。不需要用户提供银行流水等具体信息，就能验证用户的账户流水是否符合贷款条件，同时可以保护隐私。基金投资或借贷平台对于隐私和透明度都有特殊需求。从透明度来说，这类平台需要符合监管规定，并且需要向用户和监管方显示他们的偿付能力。这类金融应用还有隐私的需求，比如说不能公开用户的余额、公司的商业机密、投资过哪些公司等。零知识证明在平衡隐私和透明的需求上有着很大的优势。
三、零知识证明的现存问题
目前主流的零知识证明技术有：zk-SNARKs、zk-STARKs、BulletProofs，其中zk-SNARKs为非交互零知识证明体系中最为成熟的技术。zk-SNARKs算法需要一个中心化的初始化阶段（Trusted setup），用于创建生成零知识证据的证明密钥以及验证零知识证据的验证密钥，而区块链本身是一个去中心化的系统，zk-SNARKs算法的初始化阶段无疑给区块链带来了信任风险，如何保证zk-SNARKs算法可信地构造初始化参数是其应用到区块链中需要克服的关键性技术挑战。
zk-SNARKs算法目前的性能较差，计算复杂度主要来自于底层依赖的椭圆曲线配对运算。虽然优化后的算法在生成证据上可以实现秒级响应，但在高并发的金融应用上可用性仍然有待提高。如何实现快速高效、可信的零知识证明算法以及如何实现能够抵抗量子计算的零知识证明算法，都是今后研究的重点。
往期推荐
FCC30+
长按左边二维码
关注我们不迷路