数据结构 - 机器学习

5.1.1　Hash定义Hash（哈希或散列）算法是非常基础也非常重要的计算机算法，它能将任意长度的二进制明文串映射为较短的（通常是固定长度的）二进制串（Hash值），并且不同的明文很难映射为相同的Hash值。例如计算一段话“helloblockchainworld，thisisyeasy@github”的SHA-256Hash值。$echo"helloblockchainworld,thisisyeasy@github"|shasum-a256db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90这意味着对于某个文件，无需查看其内容，只要其SHA-256Hash计

加解密算法是密码学的核心技术，从设计理念上可以分为两大基本类型，如表5-1所示。表5-1　加解密算法的类型5.2.1　加解密系统基本组成现代加解密系统的典型组件一般包括：加解密算法、加密密钥、解密密钥。其中，加解密算法自身是固定不变的，并且一般是公开可见的；密钥则是最关键的信息，需要安全地保存起来，甚至通过特殊硬件进行保护。一般来说，对同一种算法，密钥需要按照特定算法每次加密前随机生成，长度越长，则加密强度越大。加解密的基本过程如图5-1所示。加密过程中，通过加密算法和加密密钥，对明文进行加密，获得密文。解密过程中，通过解密算法和解密密钥，对密文进行解密，获得明文。根据加解密过程中所使用的密钥是否相同，算法可以分为对称加密（symmetriccryptography，又称公共

消息认证码和数字签名技术通过对消息的摘要进行加密，可用于消息防篡改和身份证明问题。5.3.1　消息认证码消息认证码全称是“基于Hash的消息认证码”（Hash-basedMessageAuthenticationCode，HMAC）。消息验证码基于对称加密，可以用于对消息完整性（integrity）进行保护。基本过程为：对某个消息利用提前共享的对称密钥和Hash算法进行加密处理，得到HMAC值。该HMAC值持有方可以证明自己拥有共享的对称密钥，并且也可以利用HMAC确保消息内容未被篡改。典型的HMAC（K，H，Message）算法包括三个因素，K为提前共享的对称密钥，H为提前商定的Hash算法（一般为公认的经典算法如SHA-256），Message为要处理的消息内容。如果不知

对于非对称加密算法和数字签名来说，很重要的一点就是公钥的分发。理论上任何人可以公开获取到对方的公钥。然而这个公钥有没有可能是伪造的呢？传输过程中有没有可能被篡改掉呢？一旦公钥自身出了问题，则整个建立在其上的安全体系的安全性将不复存在。数字证书机制正是为了解决这个问题，它就像日常生活中的一个证书一样，可以证明所记录信息的合法性。比如证明某个公钥是某个实体（如组织或个人）的，并且确保一旦内容被篡改能被探测出来，从而实现对用户公钥的安全分发。根据所保护公钥的用途，可以分为加密数字证书（EncryptionCertificate）和签名验证数字证书（SignatureCertificate）。前者往往用于保护用于加密信息的公钥；后者则保护用于进行解密签名进行身份验证的公钥。两种类型的公钥

在非对称加密中，公钥可以通过证书机制来进行保护，但证书的生成、分发、撤销等过程并没有在X.509规范中进行定义。实际上，安全地管理和分发证书可以遵循PKI（PublicKeyInfrastructure）体系来完成。PKI体系核心解决的是证书生命周期相关的认证和管理问题，在现代密码学应用领域处于十分基础和重要的地位。需要注意，PKI是建立在公私钥基础上实现安全可靠传递消息和身份确认的一个通用框架，并不代表某个特定的密码学技术和流程。实现了PKI规范的平台可以安全可靠地管理网络中用户的密钥和证书。目前包括多个实现和规范，知名的有RSA公司的PKCS（PublicKeyCryptographyStandards）标准和X.509相关规范等。5.5.1　PKI基本组件一般情况下，

Merkle（默克尔）树，又叫哈希树，是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。在区块链系统出现之前，广泛用于文件系统和P2P系统中，如图5-3所示。图5-3　Merkle树示例其主要特点为：·最下面的叶节点包含存储数据或其哈希值；·非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值。进一步地，默克尔树可以推广到多叉树的情形，此时非叶子节点的内容为它所有的孩子节点内容的哈希值。默克尔树逐层记录哈希值的特点，让它具有了一些独特的性质。例如，底层数据的任何变动，都会传递到其父节点，一层层沿着路径一直到树根。这意味树根的值实际上代表了对底层所有数据的“数字摘要”。目前，默克尔树的典型应用场景有很多，下面分别介绍。1.快速比较大量数据对每组数据排序后构建默克

布隆过滤器（BloomFilter）于1970年由BurtonHowardBloom在论文《Space/TimeTrade-offsinHashCodingwithAllowableErrors》中提出。布隆过滤器是一种基于Hash的高效查找结构，能够快速（常数时间内）回答“某个元素是否在一个集合内”的问题。布隆过滤器因为其高效性大量应用于网络和安全领域，例如信息检索（BigTable和HBase）、垃圾邮件规则、注册管理等。1.基于Hash的快速查找在布隆过滤器之前，先来看基于Hash的快速查找算法。在前面的讲解中我们提到，Hash可以将任意内容映射到一个固定长度的字符串，而且不同内容映射到相同串的概率很低。因此，这就构成了一个很好的“内容→索引”的生成关

1.定义同态加密（homomorphicencryption）是一种特殊的加密方法，允许对密文进行处理得到仍然是加密的结果。即对密文直接进行处理，跟对明文进行处理后再对处理结果加密，得到的结果相同。从抽象代数的角度讲，保持了同态性。同态加密可以保证实现处理者无法访问到数据自身的信息。如果定义一个运算符Δ，对加密算法E和解密算法D，满足：E（XΔY）=E（X）ΔE（Y）则意味着对于该运算满足同态性。同态性来自代数领域，一般包括四种类型：加法同态、乘法同态、减法同态和除法同态。同时满足加法同态和乘法同态，则意味着是代数同态，称为全同态（fullhomomorphic）。同时满足四种同态性，则称为算数同态。对于计算机操作来讲，实现了全同态意味着对于所有处理都可以实现同态性。只能实现

密码学领域涉及的问题还有许多，这里列出一些还在发展和探讨中的相关技术。1.零知识证明零知识证明（zeroknowledgeproof）是这样的一个过程，证明者在不向验证者提供任何额外信息的前提下，使验证者相信某个论断是正确的。例如，Alice向Bob证明自己知道某个数字，在证明过程中Bob可以按照某个顺序提出问题（比如数字加上某些随机数后的变换）由Alice回答，并通过回答确信Alice较大概率确实知道某数字。证明过程中，Bob除了知道Alice确实知道该数字外，自己无法获知或推理出任何额外信息（包括该数字本身），也无法用Alice的证明去向别人证明（Alice如果提前猜测出Bob问题的顺序，存在作假的可能性）。零知识证明的研究始于1985年ShafiGoldwasser

之所以看得更远，是因为站在了巨人的肩膀上。作为区块链思想诞生的源头，比特币项目值得区块链技术爱好者仔细研究。比特币网络是首个得到大规模部署的区块链技术应用，并且是首个得到实践检验的数字货币实现，无论在信息技术历史还是在金融学历史上都具有十分重要的意义。虽然后来的区块链技术应用已经远超越了数字货币的范畴，但探索比特币项目的发展历程和设计思路，对于深刻理解区块链技术的来龙去脉有着重要的价值。本章将介绍比特币项目的来源、核心原理设计、相关的工具，以及关键的技术话题。