| 编辑推荐: |
文章主要介绍了区块链的数据结构，Merkle树结构，哈希函数以及一些加密算法等，希望对您能有所帮助。
本文来自于jianshu，由火龙果软件Luca编辑、推荐。 |
|
数据层是最底层的技术，主要实现了两个功能：数据存储、账户和交易的实现与安全。数据存储主要基于Merkle树，通过区块的方式和链式结构实现，大多以KV数据库的方式实现持久化，比如比特币和以太坊采用的leveldb。账户和交易的实现与安全这个功能基于数字签名、哈希函数和非对称加密技术等多种密码学算法和技术，保证了交易在去中心化的情况下能够安全的进行。
数据层的系统模型有很多，比如比特币的UTXO 模型、迅雷链的账户模型等。
(1) 数据存储系统--数据库
数据层的一大功能是存储，存储系统的选择原则是性能和易用性。一个网络系统的整体性能，主要取决于网络或本地数据存储系统的I/O性能，比如比特币用的是谷歌的LevelDB，据说这个数据库读写性能很好，但是很多功能需要开发者自己实现。
数据库的历史：在IT界，其实一个特别古老的研究领域。从最初的文件系统，到后来的ER实体关系模型。实体关系模型的提出催生了一系列伟大的数据库公司和软件，例如IBM的DB2，
Sybase，Oracle，微软的SQLServer，MySQL等等。以及，由此引发了传统数据库的三大成就，关系模型、事务处理、查询优化。再到后来随着互联网的盛行，MangoDB为典型代表的NOSQL数据库崛起。数据库技术本身在不停的演进，且一直是热门的方向，也包括XML为代表的半结构化，基于文本、语音和图像的非结构化数据处理等。
伴随着现实的需求不断升级，数据库也在不断发展的，我们通过ER实体关系模型、通过NOSQL，能很好的解决数据存储和数据访问的Scalability问题。我们通过NOSQL数据库、云存储等技术解决了互联网海量数据的处理问题后，下一个问题接踵而至。那就是如何以一种规模化的方式解决数据真实性和有效性的问题。
区块链的数据库和传统分布式数据库的比较。
从图中可以看出，区块链的数据库使用技术还是数据库，知识在管理权限、数据节点分布、去中心化等部分有差异。区块链的不可篡改数据，必然伴随着数据存储的膨胀，这个会不会是一个问题呢？
(2) 区块数据（Block）
区块数据主要是保存交易数据，不同的系统采用的结构不同，下面以比特币的区块结构为例做介绍。
比特币的交易记录会保存在数据区块之中，比特币系统中大约每10分钟会产生一个区块，每个数据区块一般包含区块头（Header）和区块体（Body）两部分，如图2-1所示。
区块结构：
区块头的结构说明：
区块链的数据结构成员分散存储在底层数据库，最终存储形式是[k,v]键值对，使用的[k,v]型底层数据库是LevelDB；与交易操作相关的数据，其呈现的集合形式是Block；如果以Block为单位链接起来，则构成更大粒度的BlockChain。
(3) 链式结构（chain）
从上面的区块结构中可以看到，每一个区块都保存了上一个区块的hash值，这样就将这些区块连接起来。
(4) Merkle树
默克尔树（Merkle tree，MT）是一种哈希二叉树，1979年由Ralph Merkle发明。在计算机科学中，二叉树是每个节点最多有两个子树的树结构，每个节点代表一条结构化数据。通常子树被称作“左子树”（left
subtree）和“右子树”（right subtree）。二叉树常被用于实现数据快速查询。二叉树如下图所示。
A、Merkle树结构
由一个根节点（root）、一组中间节点和一组叶节点（leaf）组成。叶节点（leaf）包含存储数据或其哈希值，中间节点是它的两个孩子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。所以Merkle树也称哈希树。
B、哈希树的特点
叶节点存储的是数据文件，而非叶节点存储的是其子节点的哈希值（Hash，通过SHA1、SHA256等哈希算法计算而来），这些非叶子节点的Hash被称作路径哈希值（可以据其确定某个叶节点到根节点的路径）,
叶节点的Hash值是真实数据的Hash值。因为使用了树形结构, 其查询的时间复杂度为 O(logn)，n是节点数量。
默克尔树的另一个特点是，底层数据的任何变动，都会传递到其父节点，一直到树根。
C、应用模式
默克尔树的典型应用场景包括：
l 快速比较大量数据：当两个默克尔树根相同时，则意味着所代表的数据必然相同（哈希算法决定的）。
l 快速定位修改：例如上例中，如果 D1 中数据被修改，会影响到Hash0-0，Hash0 和 Root。因此，沿着
Root --> 0 --> 0-0，可以快速定位到发生改变的 D1；
l 零知识证明：例如如何证明某个数据（D0……D3）中包括给定内容 D0，很简单，构造一个默克尔树，公布
N0，N1，N4，Root，D0拥有者可以很容易检测 D0 存在，但不知道其它内容。
相对于 Hash List，MT的明显的一个好处是可以单独拿出一个分支来（作为一个小树）对部分数据进行校验，这个很多使用场合就带来了哈希列表所不能比拟的方便和高效。正是源于这些优点，MT常用于分布式系统或分布式存储中
D、在分布式存储系统中的应用原理
为了保持数据一致，分布系统间数据需要同步，如果对机器上所有数据都进行比对的话，数据传输量就会很大，从而造成“网络拥挤”。为了解决这个问题，可以在每台机器上构造一棵Merkle
Tree，这样，在两台机器间进行数据比对时，从Merkle Tree的根节点开始进行比对，如果根节点一样，则表示两个副本目前是一致的，不再需要任何处理；如果不一样，则沿着hash值不同的节点路径查询，很快就能定位到数据不一致的叶节点，只用把不一致的数据同步即可，这样大大节省了比对时间以及数据的传输量。
E、比特币中的Merkle Tree
比特币区块链系统中的采用的是Merkle二叉树，它的作用主要是快速归纳和校验区块数据的完整性，它会将区块链中的数据分组进行哈希运算，向上不断递归运算产生新的哈希节点，最终只剩下一个Merkle根存入区块头中，每个哈希节点总是包含两个相邻的数据块或其哈希值。
在比特币系统中使用Merkle树有诸多优点：首先是极大地提高了区块链的运行效率和可扩展性，使得区块头只需包含根哈希值而不必封装所有底层数据，这使得哈希运算可以高效地运行在智能手机甚至物联网设备上；其次是Merkle树可支持“简化支付验证协议”（SPV），即在不运行完整区块链网络节点的情况下，也能够对交易数据进行检验。所以，在区块链中使用Merkle树这种数据结构是非常具有意义的。
(5) 哈希函数
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
哈希能够实现数据从一个维度向另一个维度的映射，通常使用哈希函数实现这种映射。通常业界使用y = hash(x)的方式进行表示，该哈希函数实现对x进行运算计算出一个哈希值y。
A、哈希算法的特点
l 哈希算法接受一段明文后，以一种不可逆的方式，将其转化为一段长度较短、位数固定的散列数据，计算高效。
l collision-free 即冲突概率小，如果两个哈希值是不相同的（根据同一函数），那么这两个哈希值的原始输入也是不相同的；如果两个哈希值相同，两个输入值很可能是相同的，但不绝对肯定二者一定相等（可能出现哈希碰撞）。
l 能够隐藏原始信息：例如区块链中各个节点之间对交易的验证只需要验证交易的信息熵，而不需要对原始信息进行比对，节点间不需要传输交易的原始数据只传输交易的哈希即可，常见算法有SHA系列和MD5等算法。
l 加密过程不可逆，即无法通过输出的散列数据倒推原本的明文是什么。
l 输入的明文与输出的散列数据一一对应，任何一个输入信息的变化，都必将导致最终输出的散列数据的变化，冲突的概率非常小。
B、哈希的用法
哈希在区块链中用处广泛，其一我们称之为哈希指针（Hash Pointer），哈希指针是指该变量的值是通过实际数据计算出来的且指向实际的数据所在位置，即其既可以表示实际数据内容又可以表示实际数据的存储位置。如下图所示：
HashPointer在区块链中主要有两处使用，第一个就是构建区块链数据结构，从上面的区块数据结构中就可以知道，每个区块都包含了上一个区块的hash值（即hash
pointer），这样的好处在于后面区块可以查找前面所有区块中的信息，而且区块的HashPointer的计算包含了前面区块的信息从而一定程度上保证了区块链的不易篡改的特性。第二个就是用于构建Merkle
Tree.，Merkle Tree的各个节点使用HashPointer进行构建。
哈希还在其他技术中有所应用例如:交易验证以及数字签名等等。
(6) 加密算法
加密就是通过一种算法将原始信息进行转换，接收者能够通过密钥对密文进行解密还原成原文的过程。加密算法的典型组件有加解密算法、加密密钥和解密密钥。其中加解密算法是固定不变和公开可见的；密钥则不固定而且需要保护起来，一般来说，对同一种算法，密钥长度越长，则加密强度越大。
加密过程即通过加密算法和加密密钥，对明文进行加密，获得密文。
解密过程即通过解密算法和解密密钥，对密文进行解密，获得明文。
根据加解密的密钥是否相同，算法可以分为对称加密（symmetric cryptography，又称公共密钥加密，common-key
cryptography）和非对称加密（asymmetric cryptography，又称公钥加密，public-key
cryptography）。两种模式适用于不同的需求，恰好形成互补，很多时候也可以组合使用，形成混合加密机制。
并非所有加密算法的强度都可以从数学上进行证明。公认的高强度加密算法是在经过长时间各方面实践论证后，被大家所认可，不代表其不存在漏洞。但任何时候，自行发明加密算法都是一种不太明智的行为。
A、对称加密
用相同的密钥来加密和解密，对称加密的优点是加解密效率高（速度快，空间占用小），加密强度高。缺点是参与多方都需要持有密钥，一旦有人泄露则安全性被破坏，如何在不安全通道下分发密钥是关键问题。
加密过程：原文+密钥=》密文；解密过程：密文-密钥=》原文。
对称密码从实现原理上可以分为两种：分组密码和序列密码。前者将明文切分为定长数据块作为加密单位，应用最为广泛。后者则只对一个字节进行加密，且密码不断变化，只用在一些特定领域，如数字媒介的加密等。
代表算法包括：
l DES（Data Encryption Standard）：经典的分组加密算法，1977年由美国联邦信息处理标准（FIPS）所采用FIPS-46-3，将64位明文加密为64位的密文，其密钥长度为56位+8位校验。现在已经很容易被暴力破解。
l 3DES：三重DES操作：加密解密加密，处理过程和加密强度优于DES，但现在也被认为不够安全。
l AES（Advanced Encryption Standard）：美国国家标准研究所（NIST）采用取代DES成为对称加密实现的标准，1997~2000年NIST从15个候选算法中评选Rijndael算法（由比利时密码学家Joan
Daemon和Vicent Rijmen发明）作为AES，标准为FIPS-197。AES也是分组算法，分组长度为128、192、256位三种。AES的优势在于处理速度快，整个过程可以数学化描述，目前尚未有有效的破解手段。
适用于大量数据的加解密；不能用于签名场景；需要提前分发密钥。其中分组加密每次只能处理固定长度的明文，因此过长的内容需要采用一定模式进行加密，《使用密码学》中推荐使用密文分组链接（Cipher
Block Chain,CBC）、计数器（Counter,CTR）模式。
B、非对称加密
非对称加密是现代密码学历史上最为伟大的发明，可以很好的解决对称加密需要的提前分发密钥问题。加密密钥和解密密钥是不同的，分别称为公钥和私钥。公钥一般是公开的，人人可获取的，私钥一般是个人自己持有，不能被他人获取。公钥用于加密，私钥用于解密。公钥由私钥生成，私钥可以推导出公钥，从公钥无法推导出私钥。
它的优点是公私钥分开，不安全通道也可以使用。缺点是加解密速度慢，一般比对称加解密算法慢2到3个数量级；同时加密强度相比对称加密要差。
加密过程：原文+接收方公钥=》密文；解密过程：密文+接收方私钥=》原文
非对称加密算法的安全性往往需要基于数学问题来保障，目前主要有基于大数质因子分解、离散对数、椭圆曲线等几种思路。
代表算法包括：
l RSA：经典的公钥算法，1978年提出。算法利用了对大数进行质因子分解困难的特性，但目前还没有数学证明两者难度等价，或许存在未知算法在不进行大数分解的前提下解密。
l Diffie-Hellman密钥交换：基于离散对数无法快速求解，可以在不安全的通道上，双方协商一个公共密钥。
l ElGamal：利用了模运算下求离散对数困难的特性。被应用在PGP等安全工具中。
l 椭圆曲线算法（Elliptic curve cryptography,ECC）：现代备受关注的算法系列，基于对椭圆曲线上特定点进行特殊乘法逆运算难以计算的特性。最早在1985年提出。ECC系列算法一般被认为具备较高的安全性，但加解密计算过程往往比较费时。
一般适用于签名场景或密钥协商，不适于大量数据的加解密。 其中RSA算法等已被认为不够安全，一般推荐采用椭圆曲线系列算法。
C、混合加密机制
这种方式将加密过程分为两个阶段，阶段一使用非对称加密进行秘钥的分发使得对方安全地得到对称加密的秘钥，阶段二使用对称加密对原文进行加解密，如下图所示。
典型的场景是现在大家常用的HTTPS机制。
建立安全连接具体步骤如下：
l 客户端浏览器发送信息到服务器，包括随机数R1，支持的加密算法类型、协议版本、压缩算法等。注意该过程为明文。
l 服务端返回信息，包括随机数R2、选定加密算法类型、协议版本，以及服务器证书。注意该过程为明文。
l 浏览器检查带有该网站公钥的证书。该证书需要由第三方CA来签发，浏览器和操作系统会预置权威CA的根证书。如果证书被篡改作假（中间人攻击），很容易通过CA的证书验证出来。
l 如果证书没问题，则用证书中公钥加密随机数R3，发送给服务器。此时，只有客户端和服务器都拥有R1、R2和R3信息，基于R1、R2和R3，生成对称的会话密钥（如AES算法）。后续通信都通过对称加密进行保护。
D、常见加密算法的对比
E、比特币中加密算法的使用
比特币系统中使用的就是一种非常典型的非对称加密算法——椭圆曲线加密算法（ECC）。比特币系统一般从操作系统底层的一个密码学安全的随机源中取出一个256位随机数作为私钥，私钥总数为2256
个，所以很难通过遍历所有可能的私钥得出与公钥的对应的私钥。用户使用的私钥还会通过SHA256和Base58转换成易书写和识别的50位长度的私钥，公钥则首先由私钥和Secp256k1椭圆曲线算法生成65字节长度的随机数。
(7) 数字签名
数字签名又称之为公钥数字签名，是一种类似于写在纸上的物理签名。数字签名主要用于数据更改的签名者身份识别以及抗抵赖。数字签名包含三个重要特性：
l 只有自己可以签署自己的数字签名，但是他人可以验证签名是否是你签发；
l 数字签名需要和具体的数字文档绑定，就好比现实中你的签名应该和纸质媒介绑定；
l 数字签名不可伪造；
通过非对称加密机制可以较容易实现上述三种特性。首先，需要生成个人的公私钥对：(sk, pk) :=
generateKeys(keysize)，sk私钥用户自己保留，pk公钥可以分发给其他人其次，可以通过sk对一个具体的message进行签名：sig
:= sign(sk, message) 这样就得到了具体的签名sig最后，拥有该签名公钥的一方能够进行签名的验证：isValid
:= verify(pk, message, sig)在区块链体系中每一条数据交易都需要签名，在比特币的设计过程中直接将用户的公钥来表征用户的比特币地址。这样在用户发起转账等比特币交易时可以方便的进行用户交易的合法性验证。
数字签名就是在信息后面加上另一段内容，作为发送者的证明并且证明信息没有被篡改。一般是发送者将信息用哈希算法处理得出一个哈希值，然后用私钥对该哈希值进行加密，得出一个签名。然后发送者再将信息和签名一起发送给接收者。接收者使用发送者的公钥对签名进行解密，还原出哈希值，再通过哈希算法来验证信息的哈希值和解密签名还原出来的哈希值是否一致，从而可以鉴定信息是否来自发送者或验证信息是否被篡，如下图所示。
相关知识：数字证书和认证中心
数字证书（Digital Certificate）又称“数字身份证”、“网络身份证”是经认证中心授权颁发并经认证中心数字签名的包含公开秘钥拥有者及公开秘钥相关信息的电子文件，可以用来判别数字证书拥有者身份。数字证书包含：公钥、证书名称信息、签发机构对证书的数字签名以及匹配的私钥证书可以存储在网络中的数据库中。用户可以利用网络彼此交换证书。当证书撤销后，签发此证书的CA仍保留此证书的副本，以备日后解
决可能引起的纠纷。
认证中心（Certificate Authority） 一般简称CA, CA一般是一个公认可信的第三方机构，其作用主要是为每个用户颁发一个独一无二的包含名称和公钥的数字证书。CA解决了电子商务中公钥的可信度问题：负责证明“我确实始我”，CA是受信仟的第三方，公钥的合法性检验，CA证书内容包括：证书持有人的公钥、证书授权中心名称、证书有效期、证书授权中心的数字签名。
CA证书用例-Https访问网站：
*客户端通过https向服务器发安全链接请求
*服务器用私钥加密网页内容，同CA证书一并发给客户端
*客户端会根据CA证书验证是否合法：
*如果验证失败，客户端弹出警告信息
*如果验证通过，客户端使用CA证书中的公钥向服务器发送加密信息
|
