一文说透密码学历史、工作原理、零知识证明及潜在影响 - 区块链前沿 - BitMere

密码学历史可以被分成两个时间段：经典和现代。
在经典密码学世界中，信息是通过密钥组合或者说是一组字母或数字来加密，然后由同一组密钥解密。一个简单的例子是「凯撒密码」，字母只是按字母表的顺序进行位移，就可以加密或解密。值得注意的是，一旦搞清楚私密密钥，此前所有的加密信息就都被解开了。整体而言，到第二次世界大战期间，虽然加密技术不断进步，但加密手段仍然未有超越，无非是一连串的字母位移和配置，最终都被手工或借助计算机而破解。
在贝尔实验室从事密码学研究的美国数学家克劳德·香农（Claude Elwood Shannon）于 1948 年创立了信息论，他在信息论中声称，最好的加密方法应该不显示关于被加密的明文的任何信息。要知道信息论正是要量化信息，使其能被分享。
信息现在被定义为「熵」，或者叫一个变量所涉及的不确定性的度量。譬如，想象一下你在记录抛硬币的结果，硬币头像朝上的可能是 50%，记为数字 1，硬币头像朝下的可能是 50%，记为数字 0。你把一连串 1 和 0 的结果记录下来，这个序列不能被压缩成一个更短的字符串——因为 1 和 0 出现的几率均等，那么我们怎么可能缩短这个字符串呢？办不到的。但想象一下，如果头像朝上的概率为 80%，朝下的概率为 20%，你所得到的字符串中， 1 的数量会远多于 0，这样我们就可以压缩字符串来代表一个真实的、更大数量的 1 和 0。这种关于某种可能性的表达就是「信息」，也是关于压缩如何工作的原理。
香农知道，要隐藏信息，一个好的加密方法应该制造随机性，这样一来原始信息就无法溯源出来。譬如，我们对 COLOR 和 COLOUR 两个英文单词进行加密，我们知道这两个词很相似。不过，如果我们用一种加密机制来加密，结果却完全不同，那就堪称完美的加密。
这意味着，即便要被加密的原初消息只有极小的变化，也应翻译成迥然不同的加密消息，和原始消息的加密消息之间没有丝毫相像。有趣的是，目前还没有任何一种加密技术可以做到一丁点的变化就能影响到加密信息的全部。密码学还在追求完美的保密性。
接着，伴随计算机的诞生，1970 年代迎来了现代密码学，即利用复杂性理论来发展加密方法，用户可以轻松地加密、解密或验证消息，而在不知道私密密钥的情况下，「暴力破解」这一方法所需的算力被证明相当之高，要达到量子计算的难度。
因此，与经典密码学中加密方法必须保密这一条件不同，现代密码学的方法和算法都可以被共享。即便提前知道相应的理论和算法，也几乎不会给你「破解它们」提供什么优势。
以下两个里程碑式的突破把世界带入现代密码学时代：
数字加密标准（DES）公开密钥密码学（譬如：RSA 算法和 Diffie-Helman 算法）

DES （Data Encryption Standard）规范了电子数据的加密方法，这推动了对密码学更广泛的研究。（题外话，美国政府干预 DES 的开发，助长了人们对政府通过后门干预加密技术的不信任，等等。关于启用后门技术的优缺点的争论一直持续到今天。）言归正传，DES 在 2002 年已被高级加密标准 (AES) 所取代。
至于公开密钥密码学，其工作原理如下：

1 O0 Y+ ^- a: M" m' D用户 A 生成一个 ⑴ 私密密钥（私钥）和一个 ⑵ 公开密钥（公钥）
, n+ z A$ f3 V+ t# o7 E7 M
一个「密钥」的定义是什么呢？密钥是一段信息，可以决定一个算法的输出。举个非常简化的例子，假设用户 A 有一个算法 F(x,k)，其中她想用密钥 k「掩饰」一个数字 x，然后发送给另一个用户 B，公式如下：
, ^- @) w& P2 ?4 B9 e
F(x, k) = x * k * 7$ g4 s' O! ~! Z$ Y

x 的值根据用户 A 想要共享的数据或数字而变化。然后用户 A 会用密钥 k 乘以 x，以「隐藏」它。
假设用户 A 的密钥是 10，她想把数字 3 发给用户 B。她会用 3 * 10 * 7 = 210 来「加密」数字 3。用户 A 会把 210 发送给用户 B。如果用户 B 知道密钥 k 和算法 F，他只需要把 210 除以 10 和 7 来「解密」这个秘密数字，结果即为 3。不过，在本例中，加密密钥和解密密钥是相同的，或者称为对称加密，即用于加密和解密的是同一个密钥 3。
而在非对称加密中，公钥「加密」和私钥「解密」是两个不同的数字，其算法也要比上面提到的复杂得多。
一般来说，公钥是从私钥派生出来的；不过，要从公钥出发找到私钥，「在计算上是不可行的」。在正规术语中，这被称为陷门函数（trapdoor function）——在一个方向上很容易处理、但在反方向上执行起来极具挑战性。
因此，从私钥生成公钥很容易，但是从公钥计算出私钥非常有挑战性。这种差异性越大，这种方法就被认为越安全。从根本上说，它依赖于计算中的一个事实：乘法计算起来非常快，而除法要慢得多。
继续……
用户 A 把她的公钥发送给用户 B。用户 B 用用户 A 的公钥加密一条要发给 A 的信息。用户 B 给用户 A 发送一条加密的信息。用户 A 利用她的私钥解密这条信息，然后读到用户 B 发给她的信息。

在 RSA 算法中，简单说来，私钥和公钥是基于两个大素数相乘形成的半素数而生成的。前面讲过，因式分解（除法）在计算上比乘法困难得多。不过，RSA 作为一种密码学完整性的方法正在衰落。
Global Security 指数是一种量化加密系统的安全性的标准，它将破解一个加密系统所需的算力翻译成「烧开水」所需的能量。基于这个指数， 288 位的 RSA 加密，可用烧开不到一茶匙水所用的算力破解。目前，大多数 RSA 密码术使用 2048 位的密钥。
我们可以对比来看一种新型的私 / 公钥密码术 —— 椭圆曲线密码术（Elliptic Curve Cryptography，ECC）。破解一个 288 位的 ECC 系统，所需的能量可以煮沸地球上所有的水。因此，后者正在快速取代 RSA，成为区块链和零知识证明中使用的密码学系统的基础。这是关于 ECC 与 RSA 对比的一个相当综合的概括。
在继续讲下去之前，我想提醒一下密码学的使用在历史上有多么重要。
从恺撒大帝到现在，一个国家或一个民族能够安全交流的价值，以人类生命和经济价值计算都是不可估量的。早在巴比伦人占领以色列时期的《耶利米书》中，巴比伦人被以色列人掳到巴比伦时，巴比伦就被称为代表暗码式翻译的「示沙克」 (耶利米书 25 章 26 小节），有可能是指保护先知不受惩罚。甚至托马斯·杰斐逊也参与过密码学，他制作了美国军队使用的杰斐逊圆盘，这个发明一直延用到 20 世纪。后来，英国科学家艾伦·图灵破解德军 Enigma 密码学的工作，被认为缩短了二战的时间。毫无疑问，密码学改变了历史。
为什么需要零知识
在前面演示的私钥 / 公钥示例中，请注意，用户 A 永远不应该暴露她的私钥，因为任何获得她的私钥的恶意方都能够解密其获得的每一条加密消息。
我们来考虑另一种情况：常规密码在大部分数据库中都存储为哈希（hash），而不是明文。哈希是一个函数，会把一个输入转换成另一个惟一的字符串数据，从而掩饰或隐藏原始数据。
在哈希函数中，实际上「不可能」从哈希函数创建的惟一数据字符串反推出原始数据。例如，系统可以使用 keccak256 哈希算法，将密码「3nY82$pwt4」哈希为 0xc24ea779490258728751c1789aa30fa007261f5c052e22914599b46ae13ccc5a。看看这种字母和数字的组合，即使知道哈希算法并使用强大的算力，也无法倒推出原始密码 3nY82$pwt4。重要的是，哈希函数在定义上是决定性的，这意味着相同的输入总是会得到相同的输出。因此，如果一个网站将您的密码存储为 0xc24ea779490258728751c1789aa30fa007261f5052e22914599b46ae13ccc5a，那么当您输入「3nY82$pwt4」时，该网站可以通过对其哈希，并与存储在数据库中的哈希进行比较，来检查您是否输入了正确的密码。
在上面的例子中，请注意：虽然网站不会存储您的明文密码，但您仍然需要通过一个安全通道与网站共享密码，这样才能证明你知道你的正确密码。
如果您可以向网站证明您知道正确的密码，而又不向他们共享或透露该密码，那不是更好吗？或者做的更出色，证明以前的那个你就是现在你说的这个你 ?
总体来说，这种方法是当今大多数行业验证信息的方式 —— 需要提供信息来验证它，需要重新执行计算来验证它是否完整地正确执行。比如，如果银行想批准一笔从您的帐户到另一账户的电汇，银行必须在转账前检查你的账户，来确认你的帐户中有足够的钱，来证明您不是在花费你实际不拥有的钱。同样，如果你想证明自己的身份，你必须提供你的社会安全号码或政府签发的其他身份证明。
而在另一些情况下，不需要知道知识的细节就可以检查结果。例如，供应商 A 的出价是否高于供应商 B ? 供应商 B 不应该看到供应商 A 的出价，同样，很可能双方都不想向客户以外的第三方披露自己的出价。不过，零知识证明可以向一个监管或审计机构证明，供应商 A 的出价低于供应商 B 。
这就是零知识证明所提供的东西：一方（证明者）能够向另一方（验证者）证明，他们拥有某一条特定的信息，而又无需披露该信息是什么。
零知识证明（Zero Knowledge Proof）系统
零知识证明系统是 1989 年由 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 在《交互证据系统的知识复杂性》（The Knowledge Complexity of Interactive Proof Systems）论文中首次提出的。（值得注意的是，这篇论文在最终发表之前被拒绝了大约三四年。）
这些最初的零知识证明系统是交互的，意味着数学证明的完成，需要验证者和证明者几方的交互才能完成。这意味着验证者不能独立操作，而证明者必须在场或可以出场才能完成证明。现在，我们已经发展到非交互式的证据系统，在这种系统中，证明者可以发布一个证据，并将其留给验证者进行检查。
零知识证明的验证方法强调的是可靠性和完备性。可靠性的原则是指，证明者不能说服验证者接受一个错误的陈述。事实上，这基于一种可能性，即证明者生产一个假的证据的可能性非常、非常、非常低，这一点与几十年来我们一直信任的当前的加密机制没有什么不同。完备性的原则是指，一个证明者能够说服验证者接受一条正确的陈述。
很明显，零知识证明的一个主要特征是，它们能够在保证隐私的同时证明信息被知晓，但是零知识证明系统系统更有趣的地方在于，它们越来越简洁，这一点经常被忽视。零知识证明系统能够比其他方法更简洁地证明信息。验证一个证据的时间，比重演一个计算以验证其正确性所需的时间要指数级的短得多，而后者是目前各种变动中的计算所最常用的方法。
重演计算代价高昂，需要时间和资源。 (请注意，这与验证算法或程序的正确性不同 —— 验证计算的完整性则完全是另一个范畴。更重要的是，这意味着执行计算本就效率低下的区块链，应该被用于验证计算的证据，而不是用于一般的计算本身。
快进到今天的大环境，我们有几种不同的零知识证明系统的实用案例：
在此，我们将简要讨论 :
ZK-SNARKsZK-STARKs防弹证明

ZK-SNARKs
ZK-SNARKs 是「零知识简洁的非交互式知识论证」（zero knowledge succinct non-interactive arguments of knowledge）的缩写，Zcash采纳了这种方法，Zcash 现在叫 Electric Coin Company，用这种方法将加密货币的支付匿名化。（注：Zcash 区块链实际上是比特币区块链的一个分叉。）
在 Zcash 区块链中，矿工不需要知道：
谁在发送 Zcash （因此也无需知道他们拥有多少 Zcash）。谁在收取 Zcash。被传递的 Zcash 的数量。

不过，矿工依然能够证实交易。
使用 ZK-SNARKs，矿工证实的事情包括，没有发送者发送或创建比他们当前拥有的 Zcash 更多的 Zcash，接收方只收到发送方试图发送的金额。以这种方式，Zcash 成了一个真正的匿名系统。在比特币和包括以太坊在内的大多数公共区块链上，所有交易信息都是公开的，发送地址、接收地址和金额都是已知的。此外，每个单独帐户中持有的币都是已知的。
（应该提醒的是，实际上 Zcash 有两种不同的地址格式。T 地址是公开的，从这些地址发送和接收的信息可以被视为比特币区块链。Z 地址是私密的，如果一个 Z 地址将 Zcash 发送到另一个 Z 地址，那么该信息将完全保持私密状态。不过，如果一个 Z 地址将 Zcash 发送到一个 T 地址，信息将成为公共状态。据估计，Zcash 区块链上只有 1% 的交易使用完全私密交易。在 2018 年底 Sapling 升级之前，由于规模和内存等要求，Zcash 区块链上的私人交易只能在笔记本电脑上进行。现在，私人交易只需要 2 - 3 秒 , 理论上可以从移动设备上完成交易，这是相当惊人的。想一想，不到两年前的 2017 年 Scarbrough 感恩节时，我和我从事网络安全的兄弟展开过一次隐私大辩论，我们都没有想到，零知识交易在如此短的时间可以发展到如此快的交易速度。我输掉了那场辩论，但公平地说，只是对方获得的支持人数比我多。）
ZK-SNARKs 具体如何运作？
ZK-SNARKs 背后的数学理论是精细和密集的，但是可以（稍微）用正确的原理和定理进行浓缩。以下是 Christian Reitweissner 的「SNARKs in a Nutshell」论文的一个压缩版本。
首先，问题被编码并压缩成一组多项式等式，作为一个二次运算程序。

" J3 r4 [/ v8 \t(x)h(x) = w(x)v(x)# w$ W5 e& R, W3 V

利用这些方程，证明者的目标是使验证者相信等式成立。
这些多项式可以是好几个项，如果对大量的点进行等式检查，效率会相当低。为了引入简洁性，ZK-SNARKs 依赖于 Schwartz-Zippel 辅助定理，即不同的多项式在大多数点的求值是不同的，因此只要检查少量的点，其实就可验证证明者使用的多项式是否正确。这样，求值只需要在点的一个子集来证明等式，而这些求值点是随机和秘密的。随机性和秘密点通常被称为 ZK-SNARKs 可信设置的有毒废物。设置阶段生成一个公共引用字符串 (common reference string ，CRS)，该字符串生成一个随机点 s，从该点求值多项式，并生成一个秘密数字 α，来「移位」多项式的值以保持机密性。s 和 α在设置阶段之后立即销毁，于是恶意行为者就不会得到它们，从而只能在自己的基础上构造出错误的证据。
验证者现在可以检查，在一个随机点 s 处下列多项式保持相等：

0 x" ~0 s* _( x( d/ u# E4 V" nt(s)h(s) = w(s)v(s); k- y8 e# s4 z2 {1 c* G/ R) \

接下来，就是掩盖随机性、秘密求值点，并允许验证者将使用同态加密形式的证据拼成完整拼图。在同态加密中，值的加密方式是这样的：可以对这些值执行数学运算，然后解密以显示一个值，就好像最初的数字被用在求值中一样。换句话说，它允许您隐藏数字、执行一次求值并取消隐藏，就像您对原初的、未隐藏的数字进行操作一样 (在本例中不是所有的数学操作，而是某一些)。
证明者只知道 E(s)，但能够计算 E(t(s))， E(h(s))， E(w(s)) 和 E(v(s))。
通过乘以另一个秘密值 k 来混淆同态加密值，证明者也能够隐藏其原始信息。
本质上，验证者是在检查下面这个形式的等式，t(s)h(s)k = w(s)v(s)k
ZK-SNARKs 如何设置 ?
对于上面提到的如何生成「多项式等式」和随机设置，有一些人表示怀疑。
关于多项式等式的质疑，我能给出的最短版本是，最初要被证明的等式（比如 A > B 吗 ? 或者 A + B =C 吗 ? ）被压缩到一个回路中，即约束条件被用于创建这些多项式。
另外，你是如何选择随机数的呢 ?
在 Zcash 的第一个版本中，最初的创始成员使用了一种精心设计的方法，通过他们所谓的「仪式」来制造这种随机产生的有毒废物。
「仪式」最终是一个产生随机结果的多方计算 (MPC)。换句话说，仪式的每个成员 (总共六方 ) 都产生了各自独特的随机密钥，这些密钥被组合成一个再次随机的密钥。最近，在 Zcash 的最新版本 Sapling 中，他们为 MPC 实施了一种新的方法论 —— 80 多名参与者一起生成了 ZK-SNARKs 的随机私钥。在这种新方法中，只需要一方保持忠诚，私钥就不会被复制 —— 换一种说法，这意味着仪式的所有参与方都必须变节，才能颠覆这个系统。
ZK-STARKs
相比之下，STARKs （简洁透明知识论证，succinct transparent arguments of knowledge）则因其透明和简洁密码学而被称赞。和 ZK-SNARKs 不同，STARKs 不需要一个可信的设置，因此也不需要 ZK-SNARKs 中出现的有毒废物那种事情 —— 因此具有透明性。STARKs 能够通过使用 Arthur-Merlin 协议消除对可信设置的需要。在该协议中，验证者 Arthur 为每个问题生成随机性，而证明者 Merlin 则通过解决问题来提供证据。STARKs 还通过使用最小的密码假设和在安全和抗冲突的哈希函数之间取得平衡，而使其密码术更简洁。这留下了潜在的后量子时代的安全风险。最小密码假设适用于交互式 STARKs，而非交互式 STARKs 则需要 Fiat-Shamir 启发式。
Starkware 正在与 0x 合作进行一个非常棒的项目，在去中心化和中心化的通证交易所中使用 ZK-STARKs，他们就此主题发表的文章相当清晰，有兴趣的读者可以了解一下。
STARK 证明和验证的速度都比 SNARKs 和防弹证明快，只不过这个领域的第一个 STARK 项目和开发工具才刚刚浮现。
防弹证明（Bulletproof）
防弹是另一种形式的零知识系统，它不需要可信设置，但它确实比 SNARKs 和 STARKs 需要更长的证明时间。这些证明方法目前已经在门罗币中实施 —— 实现速度快得令人咂舌，学术论文发表才 6 个月左右就开始实施。
防弹基于现有的 range proof 方法，可将多个 range proof 合为一个，且其数据比以往方法还要小。
有趣的是，防弹允许证据聚合，这意味着您可以通过多方计算，在同一时间收集和验证来自不同方的多个证据。在最近发表的文章中，Zether 防弹，被部署于智能合约隐私，而最近，摩根大通在其私有的、许可型的区块链Quorum中添加了这些功能。
零知识证明系统面临的挑战
零知识证明要被广泛采用，还面临如下一些主要挑战：
证据设置时间（开发者工具 / 劳动力准备）
对于每个计算或场景，必须生成一组数学证明来实现编码。到目前为止，市面上出现了几种开发工具；不过这仍然需要一种具有挑战性的专业技能。零知识领域（在很大程度上密码学也如此）面临的技能差距与量子计算领域相似，因为在广泛采用之前，必须培训更多开发人员了解如何把一项应用组合起来。
证据生成和验证时间 / 规模要求
零知识要求证明方生成一个证据供验证方验证。这两项活动都需要时间，近年来（实际上是近几个月）这方面所需的时间已大大缩短，但这仍是大规模采用需要考虑的一个问题。
证据的标准化
本文已经解释了生成证据的不同方法论，但每个方法都有相似的起点。标准化是必要的，它可以使零知识证明从临时处理特定问题，发展到处理更大范围的相关问题和场景。ZK 标准组织正在致力于解决相关问题。
ZK-SNARK 可信设置需求
ZK-SNARKs 需要考虑的另一个因素是：在加密世界需要建立一个可信的设置，或者称为「有毒废物」。
前文讲过，在可信设置中，会生成一个随机生成的「私钥」，该私钥是作为被保护的秘密，以便系统根据需要生成零知识证明，它是可信设置建立的基础。然而，如果私钥 / 有毒废物被泄露，那么拥有私钥的任何人都可以提供错误的证据 —— 这意味着他们可以提供证据，声称他们知道某条信息，而实际上他们并不知道，这就是脆弱性所在。
记得吧，我们说过 ZK-STARKs 和防弹证明不需要可信设置，但今年刚发布的Sonic是一个新的方法论，它可为 ZK-SNARKs 的可信设置提供一个通用的、可更新的引用字符串，这是针对更大的证据系统而提出的一种简化可信设置的解决方案。
一点感触
在私人产业，我们几乎还没有开始评估和理解零知识证明系统最适合在什么地方使用，以及哪种类型的证据最适合在什么情况下使用。要知道，行业的大部分精力仍在研究网络安全从哪里开始着手，更不用说如何将零知识纳入这一战略了。
在公共领域，零知识证明在速度和规模方面的快速发展，无疑会给关注相关领域的受众留下深刻印象，但在加密货币领域，更大范围的受众迄今为止并没有对这种隐私解决方案进行资源投入，这一点可以从保护隐私的区块链的低参与度而得到证明。
当然，公平地说，智能合约的隐私解决方案仍处于非常初级的阶段（简单交易还好一点），人们期望，这将使公共区块链加速采用隐私保护方法。
结论
上面详细介绍的零知识证明系统，只是密码学领域正在发生的故事的一部分。还有其他形式的零知识证明，如 ZK-SHARKs 和 Mimblewimble。在密码学的其他领域也有一些有趣的发展，比如完全同态加密和量子密码学。
零知识证明和密码术所提供的隐私和保密性，在某种程度上是叠加的，它在社会中的作用取决于你如何衡量它。
对于希望保护个人资料的个人或保护商业秘密的公司，它是一种权利，给那些不想伤害它的机构一种义务，就像那些享有言论自由的人被恳求不要用它来伤害他人一样。
对政府而言（理想情况下），它是一种责任，因为涉及到大多数公民的权利，公民希望并相信，政府将用一种方式既允许我们保护自己的隐私，又保护我们免受恶意行为者滥用隐私的侵害；然而在现实中，我们知道这种情况在今天是不可能存在的。
尽管如此，密码学的目标在这两个领域都是存在的，这样一个社会才能真正实现自由：自由地保护信息的隐私，同时又不用担心滥用隐私造成伤害。考虑到密码学在过去几个世纪的历史，未来某一天，伴随着将被理解的恰当的数学和科学进展，密码学或许能帮助世界实现这样的目标，这一期望似乎并不疯狂。