点击“阅读全文”，观看完整视频
https://www.bilibili.com/video/BV1pq4y1G7xv/
本系列课程是清华大学学生区块链协会THUBA推出，由PlatON赞助的区块链课程，涵盖了从区块链基础学习到深度原理研究等方面。
本系列课程从第一章区块链基础介绍开始，第二节是区块链中的密码学基础。
本文主要介绍区块链中常见几类的密码学技术，帮助大家理解在区块链这种无信任、无担保、无中心的系统中，如何利用密码学技术构建用户与用户之间的信任。
主要介绍的内容包括哈希函数、非对称加密、数字签名以及零知识证明等技术。
为了保证本文的可读性，易于广大读者理解，部分描述和例子没有保证密码学上的严格定义。
–无所不在的哈希函数-
哈希函数在计算机系统中经常出现，一般用于快速对内容进行索引。密码学哈希函数则在普通的哈希函数的基础上多了一些特性，以用于校验数据是否被篡改。本文提及的哈希函数均为密码学哈希函数。
哈希函数简介
一般用H表示哈希函数，它接受任意长的输入 M，生成固定长度的哈希值 H(M)。
哈希函数要求具备以下性质
• 单向性：从输入计算输出很容易，从输出求解输入很难
• 强抗碰撞性：很难找出两个不同的输入M1, M2，使得H(M1)=H(M2)
• 随机性：输出的哈希值在一定范围内随机，而且每个 bit 独立随机分布
• 雪崩效应：修改输入中的任何一点数据，都会导致输出大规模变化
这几个特性可以看出，哈希函数能对数据的信息进行压缩时会出现不可逆的破坏。由于输入的范围比输出的范围大，哈希碰撞很难发生（不代表不会发生）。针对特定的哈希函数，研究表明可以找出不同的输入得到相同的输出。王小云教授攻破了MD5和SHA-1的强抗碰撞性[1]，快速找出不同于原始输入但是哈希值相同的输入。
常用的哈希函数包括MD5、SHA-1、SHA-2: SHA-224/ SHA-256/ SHA-512、国密SM3等。
一个伪哈希函数的例子
为了帮助大家更好的理解哈希函数，我们设计了一个非常简单的伪哈希函数。
如上图所示，这个函数能对任意的正整数都输出固定长度的4位数。右边是输入为10时的计算过程。
从哈希函数的性质来看这个函数：
• 单向性：从10计算8769很容易，从8769计算10却很难
• 强抗碰撞性：很难找出两个不同的输入m1, m2，使得 h1=h2
• 随机性：结果存在一定的随机性，当然实际上末位数字并不随机，只会有 0,1,4,5,6,9
• 雪崩效应：修改 m 中的任何一位数据，乘法会导致 h 中若干位的改变。
这个例子并不能成为一个安全可用的哈希函数，但可以从中看出哈希函数主要通过混淆和扩散以致结果的随机性和抗碰撞性。
–在互联网上的应用-
下载文件验证
我们常在联网上下载文件，但互联网上的数据会经过一系列不可信任的节点传输，使用户需要验证下载的文件是否为自己需要的文件。在文件下载的网站上，通常会有文件的MD5或者其他哈希值让用户进行本地验证。
用户密码的传输与存储
互联网上的应用大都需要用户设置密码口令用于验证身份，以防止用户设置的密码明文泄漏，导致用户的账号安全受到威胁。因此，在传输和存储的过程中常采用哈希值而非密码原文。这样一来，尽管某些数据库泄漏，只有用户密码的哈希值发生泄漏，而用户的密码则不被泄漏。
实际系统中对用户密码的传输和存储还有更多的步骤，这里只是体现哈希函数的作用。
-在区块链中的应用-
哈希链
为了保证数据的一致性，我们需要存储全文的哈希值。由于每次数据发生修改都会改变哈希值，所以每次修改都需要重新计算整个数据的哈希值，带来大量计算开销。
因此，我们仅记录修改操作，即每次重新计算原有数据的哈希以及新操作的哈希。这样一来，整个记录变成一个哈希链条的形式。当用户需要验证历史数据是否篡改，他们将从历史数据出发，逐步验证到最新的哈希值。
把每个修改的数据看作一个区块，我们就能得到由哈希链接的若干区块。这就是区块链名字的由来。
默克尔树 Merkle Tree
在一个区块中，交易的存储方式通过哈希二叉树，也称为默克尔树的结构进行存储。它的好处在于当我们需要证明某个交易存在该区块时，不需要将所有数据进行哈希计算，仅需部分数据进行哈希计算即可（参见下图）。
工作量证明
根据哈希函数的随机性，可以发现在期望上计算若干次可以得到前缀为0的哈希值。这一性质用于区块链的共识算法中，具体内容将在下一节比特币课程中介绍。
–非对称加密与数字签名–
对称加密
我们常在电影小说中看到凯撒密码。凯撒密码在加密是对每个英文字母变换为到三位之后的字母，解密的时候将字母变换为三位前的字母。这里将密钥设为3，知道密钥即能完成加密和解密。
这类加密中，加密和解密采用同一密钥，因此称为对称加密。对称加密存的主要问题在于n个用户之间的加密通信需要O(n^2)的密钥。因此，在不安全的互联网上传输密钥需要先对密钥进行加密，难以保证密钥的安全性。
非对称加密
Diffie和Hellman的论文《密码学的新方向》[2] 提出非对称加密技术，实现了在不安全的互联网上安全进地行加密的通信。简单来说，每个用户在本地生成私钥，以这个作为基础计算算出对应的公钥并将其公开。反过来，通过公钥计算私钥却是难以实现的。其他用户可以通过公钥对数据进行加密，然后原用户通过对应的私钥进行解密。
-数字签名-
类似于传统的手写签名，当要证明某段数据由某个用户发出，我们需要附带一个可信的数字签名。为了保证该签名不可伪造和篡改，这里采用了非对称加密的反向应用。用户先用私钥对数据进行计算获得签名，其他用户则可以通过公开的公钥从签名恢复数据，进行对比验证。
在互联网上的应用
网站数字证书
为了提防钓鱼网站，确保自己浏览的是正确的网站，网站一般绑定由权威机构签发的数字证书，证明该网站与某个公钥对应。浏览器可以通过验证该证书并要求对方发送数字签名来证实自己的身份，确保用户浏览的是正确的网站。
在区块链中的应用
在去中心化的区块链中，没有平台机构让用户注册账户，用户均由自己创建账户，即需要自己生成公钥和私钥。当用户向对方转账时，需要在交易中写明对方的公钥所对应地址。此外，用户还需要证明该交易确实为自己发起，需要对交易数据进行数字签名。
这样的好处在于，每个用户可以自由的创建账户。由于可用空间巨大，两个用户创建相同的私钥的概率几乎为0。但在另一方面，一旦用户的私钥丢失，区块链中不存在一个平台能帮助用户找回私钥，账号将不能再打开。
-神奇的零知识证明-
除了上述的密码学技术以外，区块链中还应用了一系列有趣的密码学技术。这里主要介绍神奇的零知识证明技术。该技术使得用户能在不泄漏信息的情况下，仍然可以证明命题的正确性。该技术的具体原理较为复杂，因此这里通过数独游戏作为一个简单的例子给大家介绍[3]。
数独游戏的规则：将数字1-9填入空格，使得每行、每列、每个方块都刚好包含数字1-9，每个数字出现且仅出现一次
小红给小明出了一道数独题，小明花了三天都没有解决这个数独，怀疑该数独无解。小红希望向小明证明该数独有解，但证明时不泄漏与数独答案有关的任何信息。
承诺阶段
小红将数独的答案打印在81个小方格上并放在桌子上，题干中出现的数字正面向上，未出现的数字正面向下。小明不能把卡片翻过来查看答案，所以并没有获得更多信息。
挑战阶段
小明随机选择行/列/方格，要求小红进行验证。
回应阶段
假设小明选择了行，小红将所有卡片按行装入9个纸袋，并进行混匀，然后将9个纸袋交给小明。
验证阶段
小明打开9个纸袋挨个验证，如果有一个纸袋里面不存在 1-9，则验证失败。如果9个纸袋都刚好存在 1-9，说明承诺答案可能合法。此时，承诺答案可能仅满足每行 存在1-9，并不一定满足每列1-9。因此，小明可以要求回到承诺阶段再次挑战。
零知识证明定义及性质
根据上述例子，这里给出零知识证明的一些定义以及性质。
零知识证明中存在两个参与者：证明者 和 验证者，证明者试图向验证者证明一个命题为真（“该数独存在答案”），但不能泄漏任何命题以外的信息给验证者。
过程可以定义为：承诺-挑战-回应-验证
三种性质：
• 正确性: 证明者不能欺骗验证者。如果证明者不知道所用证据证明出的是否命题成立，则证明者能欺骗验证者的概率极小
• 完备性: 验证者不能欺骗证明者。如果证明者知道证据能证明命题成立，则证明者能说服验证者的概率极大
• 完美零知识性: 除了命题是否成立，验证者不能知道其他信息。
在区块链中的应用
区块链上的数据公开透明，攻击者可以通过分析历史数据记录威胁用户隐私。零知识证明技术可以使得用户在证明交易正确性的同时，不泄漏交易相关的隐私数据。
-PlatON的其他密码学技术简介-
为了实现隐私计算和可信验证，PlatON采用一系列密码学技术保障数据计算的安全，这里将简单介绍除了零知识证明以外的其它技术。
安全多方计算
安全多方计算若干参与者希望能共同完成计算，但不泄漏各自的隐私输入。
例如：班级同学希望计算出班级平均分，但每个同学都不希望别人知道自己的成绩。
第一位同学可以自己选择随机数，例如1911，然后将自己的成绩加上该随机数发送给第二位同学。第二位同学将自己的成绩加上收到的数据发送给第三位同学，直到最后一位同学加上自己的成绩后发送给第一位同学。第一位同学减去最初的随机数后即可得到所有同学成绩的总和，用于计算平均数。
可信执行环境
可信执行环境是一种基于硬件和操作系统的安全架构，构建出与外部隔离的安全计算环境，保证内部计算的完备性和隐私性。
全同态加密
对加密后密文的计算等价于对明文执行同样的计算后加密。
例如：
E(92)+E(95)+E(99)+E(98)=E(92+95+99+98)=E(384)
通过全同态加密，也能完成计算所有同学的平均成绩。
-总结-
区块链系统去中心化的特性需要借助各类密码学技术保障系统的可信。正如口号“Don’t trust, verify it!”， 区块链的可信是基于坚固的密码学和数学原理，而且不存在本质上具有风险的企业信誉。
越来越多的密码学技术正在应用于区块链系统中，而且还有更多更加适合用于区块链中的密码学技术不断涌现，例如链上随机数、可验证随机函数等。
[1] Wang, Xiaoyun, et al. “Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD.” IACR Cryptol. ePrint Arch. 2004 (2004): 199.
[2] Diffie, Whitfield, and Martin Hellman. “New directions in cryptography.” IEEE transactions on Information Theory 22.6 (1976): 644-654.
[3] https://medium.com/qed-it/the-incredible-machine-4d1270d7363a
END
文稿&视频 | Zeo
编辑 | 杜立恒
审核 | Celia
本文转载自https://mp.weixin.qq.com/s/oizBxkZ_KPCwQ8PPPeyZLg
