区块链札记

• 分布式
  
  • 共识算法
    
    • Raft
    • Paxos
    • PBFT
    • Kafka
• 加密
  
  • 对称加密和非对称加密
  • 椭圆加密
  • 圆锥曲线加密
  • SHA-256
• 数据结构
  
  • Merkle Tree
  • Merkle Patricia Tree(MPT)
• 区块链系统
  
  • 公链
    
    • Bitcoin
    • Ethereum
  • 联盟链
    
    • Hyperledger Fabric
  • 私链

1. 分布式

1.1 共识算法

1.1.1 Raft

1.1.1.1 几个概念

三个状态
  在一个由Raft协议组织的集群中存在三种角色：

• Leader：领导人，负责整个集群与外界客户端的交互；
• Candidate：候选人，Follower节点想要变为Leader节点要经过的中间状态；
• Follower：群众，所有节点在初始化时都是Follower；

一个任期

• Term：任期，其实是一个编号，标志现在有某个Leader进行“统治”。当发生Leader变化的时候，Term会加一。

两个过程

• Leader Election：Follower竞选变为Leader的过程；
• Log Replication：Leader节点对客户端发来的消息进行全网共识的过程；

两个timeout

• Election timeout：是follower变成candidate需要等待的一段时间，是一个介于150ms~300ms之间的随机数；
• Heartbeet timeout：Leader会每隔heartbeat timeout向所有follower发送Append Entries消息来维持其任期；

两个消息

• Request Vote：Candidate节点向其他节点发出的请求为自己投票的消息；
• Append Entries：Leader节点向其他节点定时发送的用来维护自己任期的消息，防止其他节点的electin timeout耗尽而变为Candidate；

1.1.1.2 具体过程

  如上所示，Raft算法包含两个过程，下面具体分析。
  Leader Election：在raft中有两个可以控制选举的timeout，第一个叫election timeout，election timeout是follower变成candidate需要等待的一段时间，是一个介于150ms~300ms之间的随机数。当election timeout时间结束后，follower变为candidate并且发起一次选举（谁的timeout先结束谁变成candidate，如果出现两个或多个节点同时变成candidate的情况，后面再说）。
  Candidate为自己投一票并且发送Request Vote消息给其他节点，如果当前term中的节点还没有进行投票，它们就会为该candidate投票（每个节点只能投一次票）并且重置自己的election timeout。当等待投票的时候，candidate可能会收到另一个server宣称自己为Leader的 Append Entries RPC消息，这时，该candidate就会进行比较，如果该server的term比自己的大，它就会承认该server作为leader并且退为follower模式，否则就会拒绝并继续保持candidate模式。
  一旦某个candidate收到了大多数节点的投票，它就会变成leader，其他节点变为follower。Leader会每隔heartbeat timeout向所有follower发送Append Entries消息，follower会响应所有的Append Entries消息，一旦某个follower没有收到heartbeats消息，就会变成candidate并且发起一次选举。如果同时有两个节点变为candidate，就会发生split vote。这时，两个节点同时发起选举，并且它们发出的Request Vote消息刚好分别先一步到达剩余一半的节点，那么它们得到的选票数也是一致的，那么所有节点都会重置election timeout消息并且进行下一轮的选举。
  Log Replication：某个client发送了一个change给leader，leader会将这个变化加入到自己的log中（但是该变化并没有被确认），之后这个变化会在下一个heartbeat发送到所有的follower，一旦大多数节点响应了leader，leader中的变化就会被确认。这时，Leader会向client发送确认消息，并且向follower发送日志条目已被确认的消息，follower的消息也被确认。
  如果在Log Replication的过程中出现了网络分区的问题，将原先的 Leader 节点和 Follower 节点分隔开，Follower 收不到 Leader 的心跳将发起选举产生新的 Leader。这时就产生了双 Leader，原先的 Leader 独自在一个区，向它提交数据不可能复制到多数节点所以永远提交不成功。新term中，向新的 Leader 提交数据可以提交成功，网络恢复后旧的 Leader 发现集群中有更新任期（Term）的新 Leader 则自动降级为 Follower 并从新 Leader 处同步数据达成集群数据一致。

Leader Election的过程如下图所示

Raft的动画演示

以下内容摘自一篇比较好的博客
  一致性问题可以算是分布式领域的一个圣殿级问题了，关于它的研究可以回溯到几十年前。

拜占庭将军问题
  Leslie Lamport 在三十多年前发表的论文《拜占庭将军问题》（参考[1]）。
拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军必需达成 一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序，在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员不可靠的情况下，其余忠诚的将军在不受叛徒或间谍的影响下如何达成一致的协议，拜占庭问题就此形成。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。
  Lamport 一直研究这类问题，发表了一系列论文。但综合总结一下就是回答下面三个问题：

1. 类似拜占庭将军这样的分布式一致性问题是否有解？
2. 如果有解的话需要满足什么样的条件？
3. 在特定前提条件的基础上，提出一种解法。

  前两个问题 Lamport 在论文《拜占庭将军问题》已经回答，而第三个问题在后来的论文 《The Part-Time Parliament》中提出了一种算法并命名为 Paxos。这篇论文使用了大量的数学证明，而我基本就看不懂了（数学符号都认不全-｡-;），考虑到大家理解起来都比较困难，后来 Lamport 又写了另外一篇论文 《Paxos Made Simple》完全放弃了所有数学符号的证明，使用纯英文的逻辑推导。我勉强逐字看了一遍，然后感觉若有所悟，但你问我搞懂了吗，我的标准应该还是没懂。对我来说理解一个算法有个明确的标准，就是真的懂了会在头脑里能将算法映射为代码，而看完后面一篇论文仅仅是若有所悟还达不到能映射为代码的清晰度。
  虽然 Lamport 认为 Paxos 很 simple，但也许只是针对他的头脑而言。事实是大家理解起来都还是很困难，所以 Raft 就是建立在希望得到一个更易于理解的 Paxos 算法的替代品。把可理解性作为算法的主要目标之一，从论文题目就可看出来《In Search of an Understandable Consensus Algorithm》。
  在进入正题前，我想起一个旧故事可以很直观的感受对一个问题不同的思维视角在可理解性上的差异。

不同视角的可理解性
  依稀记得大约在二十年前，我还在读初中时在一本可能大概叫《数学中的发散思维》（不能很清晰记得书名了）的书中看到这么一个有趣的问题。
  甲乙两人轮流在一张圆桌上平放黑白围棋子，每次放一子，棋子不许重叠，谁先没有地方放就输。
请问怎样放才能赢？
  这个问题有两层意思，第一，有没有一种放法保证必赢？第二，如果有怎么证明？这里先停顿下，思考十秒钟。

  上面的图回答了这个问题，就是先行者必胜，这里使用了三种不同的思维方式。

1. 假如桌子只有一个围棋子那么大。
2. 假如桌子无限大，先行者先占住圆心，由于圆是对称图形，所以只要对手还能找到位置放，你总能在对称的另一面找到位置放。
3. 一个圆中可画单数个直径相等且互切的小圆。

  三种不同的思维方式在可理解性难度上逐渐加深。第一种是极简化思维，但数学上是不严谨的。第二种是极限思维，和第一种结合起来就是数学归纳法了，在数学上是严谨的。第三种是形象思维，使用了几何学概念，但对于没有几何学基础知识的人就很难理解了。

Raft 协议的易理解性描述
  虽然 Raft 的论文比 Paxos 简单版论文还容易读了，但论文依然发散的比较多，相对冗长。读完后掩卷沉思觉得还是整理一下才会更牢靠，变成真正属于自己的。这里我就借助前面黑白棋落子里第一种极简思维来描述和概念验证下 Raft 协议的工作方式。
  在一个由 Raft 协议组织的集群中有三类角色：

1. Leader（领袖）
2. Follower（群众）
3. Candidate（候选人）

  就像一个民主社会，领袖由民众投票选出。刚开始没有领袖，所有集群中的参与者都是群众，那么首先开启一轮大选，在大选期间所有群众都能参与竞选，这时所有群众的角色就变成了候选人，民主投票选出领袖后就开始了这届领袖的任期，然后选举结束，所有除领袖的候选人又变回群众角色服从领袖领导。这里提到一个概念「任期」，用术语 Term 表达。关于 Raft 协议的核心概念和术语就这么多而且和现实民主制度非常匹配，所以很容易理解。三类角色的变迁图如下，结合后面的选举过程来看很容易理解。

Leader 选举过程
  在极简的思维下，一个最小的 Raft 民主集群需要三个参与者（如下图：A、B、C），这样才可能投出多数票。初始状态 ABC 都是 Follower，然后发起选举这时有三种可能情形发生。下图中前二种都能选出 Leader，第三种则表明本轮投票无效（Split Votes），每方都投给了自己，结果没有任何一方获得多数票。之后每个参与方随机休息一阵（Election Timeout）重新发起投票直到一方获得多数票。这里的关键就是随机 timeout，最先从 timeout 中恢复发起投票的一方向还在 timeout 中的另外两方请求投票，这时它们就只能投给对方了，很快达成一致。

  选出 Leader 后，Leader 通过定期向所有 Follower 发送心跳信息维持其统治。若 Follower 一段时间未收到 Leader 的心跳则认为 Leader 可能已经挂了再次发起选主过程。

Leader 节点对一致性的影响
  Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。数据的流向只能从 Leader 节点向 Follower 节点转移。当 Client 向集群 Leader 节点提交数据后，Leader 节点接收到的数据处于未提交状态（Uncommitted），接着 Leader 节点会并发向所有 Follower 节点复制数据并等待接收响应，确保至少集群中超过半数节点已接收到数据后再向 Client 确认数据已接收。一旦向 Client 发出数据接收 Ack 响应后，表明此时数据状态进入已提交（Committed），Leader 节点再向 Follower 节点发通知告知该数据状态已提交。

  在这个过程中，主节点可能在任意阶段挂掉，看下 Raft 协议如何针对不同阶段保障数据一致性的。

1. 数据到达 Leader 节点前
  这个阶段 Leader 挂掉不影响一致性，不多说。

2. 数据到达 Leader 节点，但未复制到 Follower 节点
  这个阶段 Leader 挂掉，数据属于未提交状态，Client 不会收到 Ack 会认为超时失败可安全发起重试。Follower 节点上没有该数据，重新选主后 Client 重试重新提交可成功。原来的 Leader 节点恢复后作为 Follower 加入集群重新从当前任期的新 Leader 处同步数据，强制保持和 Leader 数据一致。

3. 数据到达 Leader 节点，成功复制到 Follower 所有节点，但还未向 Leader 响应接收
  这个阶段 Leader 挂掉，虽然数据在 Follower 节点处于未提交状态（Uncommitted）但保持一致，重新选出 Leader 后可完成数据提交，此时 Client 由于不知到底提交成功没有，可重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性，也就是要实现内部去重机制。

4. 数据到达 Leader 节点，成功复制到 Follower 部分节点，但还未向 Leader 响应接收
  这个阶段 Leader 挂掉，数据在 Follower 节点处于未提交状态（Uncommitted）且不一致，Raft 协议要求投票只能投给拥有最新数据的节点。所以拥有最新数据的节点会被选为 Leader 再强制同步数据到 Follower，数据不会丢失并最终一致。

5. 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在 Leader 处于已提交状态，但在 Follower 处于未提交状态
  这个阶段 Leader 挂掉，重新选出新 Leader 后的处理流程和阶段 3 一样。

6. 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在所有节点都处于已提交状态，但还未响应 Client
  这个阶段 Leader 挂掉，Cluster 内部数据其实已经是一致的，Client 重复重试基于幂等策略对一致性无影响。

7. 网络分区导致的脑裂情况，出现双 Leader
  网络分区将原先的 Leader 节点和 Follower 节点分隔开，Follower 收不到 Leader 的心跳将发起选举产生新的 Leader。这时就产生了双 Leader，原先的 Leader 独自在一个区，向它提交数据不可能复制到多数节点所以永远提交不成功。向新的 Leader 提交数据可以提交成功，网络恢复后旧的 Leader 发现集群中有更新任期（Term）的新 Leader 则自动降级为 Follower 并从新 Leader 处同步数据达成集群数据一致。

  综上穷举分析了最小集群（3 节点）面临的所有情况，可以看出 Raft 协议都能很好的应对一致性问题，并且很容易理解。

总结
就引用 Raft 论文最后的一节的综述来总结本文吧。
算法以正确性、高效性、简洁性作为主要设计目标。
虽然这些都是很有价值的目标，但这些目标都不会达成直到开发者写出一个可用的实现。
所以我们相信可理解性同样重要。
深以为然，想想 Paxos 算法是 Leslie Lamport 在 1990 年就公开发表在了自己的网站上，想想我们是什么时候才听说的？什么时候才有一个可用的实现？而 Raft 算法是 2013 年发表的，大家在参考[5]上面可以看到有多少个不同语言开源的实现库了，这就是可理解性的重要性。

参考
[1]. LESLIE LAMPORT, ROBERT SHOSTAK, MARSHALL PEASE. The Byzantine General Problem. 1982
[2]. Leslie Lamport. The Part-Time Parliament. 1998
[3]. Leslie Lamport. Paxos Made Simple. 2001
[4]. Diego Ongaro and John Ousterhout. Raft Paper. 2013
[5]. Raft Website. The Raft Consensus Algorithm
[6]. Raft Demo. Raft Animate Demo

1.1.2 Paxos

1.1.3 PBFT

注意，PBFT算法是对消息达成一致，对多数的消息达成共识。它的关注点不是揪出谁是叛徒。当然谁是叛徒可能在时候会被大家知道。

1.1.4 Kafka

2. 加密

2.1 对称加密和非对称加密

2.1.1 对称加密

2.1.1.1 概念

  对称加密是最快速、最简单的一种加密方式，加密（encryption）与解密（decryption）用的是同样的密钥（secret key）。对称加密只有一个秘钥，作为私钥。

2.1.1.2 优缺点

• 优点
    简单快捷，密钥较短，且破译困难。
• 缺点
  
  • 要求提供一条安全的渠道使通讯双方在首次通讯时协商一个共同的密钥。直接的面对面协商可能是不现实而且难于实施的，所以双方可能需要借助于邮件和电话等其它相对不够安全的手段来进行协商；
  • 密钥的数目难于管理。因为对于每一个合作者都需要使用不同的密钥，很难适应开放社会中大量的信息交流；假设两个用户需要使用对称加密方法加密然后交换数据，则用户最少需要2个密钥并交换使用，如果企业内用户有n个，则整个企业共需要n×(n-1)。 个密钥，密钥的生成和分发将成为企业信息部门的恶梦。
  • 对称加密算法一般不能提供信息完整性的鉴别。它无法验证发送者和接受者的身份；
  • 对称密钥的管理和分发工作是一件具有潜在危险的和烦琐的过程。对称加密是基于共同保守秘密来实现的，采用对称加密技术的贸易双方必须保证采用的是相同的密钥，保证彼此密钥的交换是安全可靠的，同时还要设定防止密钥泄密和更改密钥的程序。

  常见的对称加密算法有DES、3DES、Blowfish、IDEA、RC4、RC5、RC6和AES。

2.1.2 非对称加密

2.1.2.1 概念

  与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。
  公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。
  常见的非对称加密算法有：RSA、ECC（移动设备用）、Diffie-Hellman、El Gamal、DSA（数字签名用）`。

2.1.2.2 优缺点

• 优点
    比对称加密安全。
• 缺点
    比非对称加密耗费时间。

2.1.2.3 数字签名、数字证书和哈希算法

  哈希算法(摘要算法)：Hash算法的特点是单向不可还原，用户可以通过Hash算法对目标信息生成一段特定长度的唯一Hash值，却不能通过这个hash值重新获得目标信息。因此Hash算法常用在不可还原的密码存储、信息完整性校验等。只要源数据不同，算法得到的摘要必定不同。
  常见的Hash算法有MD2、MD4、MD5、HAVAL、SHA。

  数字签名(digital signature)和数字证书(digital certificate)：可以通过以下例子清楚地了解这两个概念。

• 鲍勃有两把钥匙，一把是公钥，另一把是私钥。
• 鲍勃把公钥送给他的朋友们----帕蒂、道格、苏珊----每人一把。
• 苏珊要给鲍勃写一封保密的信。她写完后用鲍勃的公钥加密，就可以达到保密的效果。
• 鲍勃收信后，用私钥解密，就看到了信件内容。这里要强调的是，只要鲍勃的私钥不泄露，这封信就是安全的，即使落在别人手里，也无法解密。
• 鲍勃给苏珊回信，决定采用"数字签名"。他写完后先用Hash函数，生成信件的摘要（digest）。
• 然后，鲍勃使用私钥，对这个摘要加密，生成"数字签名"（signature）。
• 鲍勃将这个签名，附在信件下面，一起发给苏珊。
• 苏珊收信后，取下数字签名，用鲍勃的公钥解密，得到信件的摘要。由此证明，这封信确实是鲍勃发出的。
• 苏珊再对信件本身使用Hash函数，将得到的结果，与上一步得到的摘要进行对比。如果两者一致，就证明这封信未被修改过。
• 复杂的情况出现了。道格想欺骗苏珊，他偷偷使用了苏珊的电脑，用自己的公钥换走了鲍勃的公钥。此时，苏珊实际拥有的是道格的公钥，但是还以为这是鲍勃的公钥。因此，道格就可以冒充鲍勃，用自己的私钥做成"数字签名"，写信给苏珊，让苏珊用假的鲍勃公钥进行解密。
• 后来，苏珊感觉不对劲，发现自己无法确定公钥是否真的属于鲍勃。她想到了一个办法，要求鲍勃去找"证书中心"（certificate authority，简称CA），为公钥做认证。证书中心用自己的私钥，对鲍勃的公钥和一些相关信息一起加密，生成"数字证书"（Digital Certificate）。
• 鲍勃拿到数字证书以后，就可以放心了。以后再给苏珊写信，只要在签名的同时，再附上数字证书就行了。
• 苏珊收信后，用CA的公钥解开数字证书，就可以拿到鲍勃真实的公钥了，然后就能证明"数字签名"是否真的是鲍勃签的。

  由上面可以看出，数字签名可以证明消息是不是由某个人发出的，而配合哈希算法，则可以证明消息在传输过程中是否被篡改或丢失。而数字证书则相当于在公钥外面又“套了一层盒子”，保证公钥不会被其他人篡改。
  下面，我们看一个应用"数字证书"的实例：https协议。这个协议主要用于网页加密。待整理

• 首先，客户端向服务器发出加密请求。
  
• 服务器用自己的私钥加密网页以后，连同本身的数字证书，一起发送给客户端。
  
• 客户端（浏览器）的"证书管理器"，有"受信任的根证书颁发机构"列表。客户端会根据这张列表，查看解开数字证书的公钥是否在列表之内。
  
• 如果数字证书记载的网址，与你正在浏览的网址不一致，就说明这张证书可能被冒用，浏览器会发出警告。
  
• 如果这张数字证书不是由受信任的机构颁发的，浏览器会发出另一种警告。
  
• 如果数字证书是可靠的，客户端就可以使用证书中的服务器公钥，对信息进行加密，然后与服务器交换加密信息。
  

2.1.2.4 公钥、私钥和地址

  刚才已经知道公钥和私钥的概念了，在区块链中还有一个地址的概念，三者关系如下：
  私钥是由随机种子生成的，公钥是将私钥通过算法推导出来。由于公钥太长，为了简便实用，就出现了“地址”，地址是公钥推导出来的。这些推导过程是单向不可逆的。也就是地址不能推出公钥，公钥不能推出私钥。
  从中我们可以看出，公钥与私钥是成对存在的。它们的用处用16个字来概括：公钥加密，私钥解密；私钥签名，公钥验签。
  公钥加密，私钥解密。也就是用公钥加密原数据，只有对应的私钥才能解开原数据。这样能使得原数据在网络中传播不被窃取，保护隐私。
  私钥签名，公钥验签。用私钥对原数据进行签名，只有对应的公钥才能验证签名串与原数据是匹配的。
比特币中公钥 私钥 和 钱包地址的关系

2.2 椭圆加密

2.3 圆锥曲线加密

2.4 SHA-256加密

2.5 RSA加密

RSA加密
各种加密算法java实现

区块链可扩展技术
可扩展技术
可扩展技术