共识算法的背景及基本介绍
共识算法是区块链的核心，解决的是在不可信网络下的分布式状态数据的共识计算。区块链的节点网络规模以及执行效率，都取决于采用了什么样的核心共识算法。共识从不同的算法也根据自身的特性采用了不同的一致性协议，从共识属性上，FLP（Fischer, Lynch and Paterson）定义了三个特性，同时认为：Any algorithm that has these three properties can be said to solve the consensus problem。
1）Termination/Liveness: 可终止性
All non-faulty processes eventually decide on a value.
共识算法中每个过程调用都会有固定的结果值，算法不会出现死循环无尽执行下去。
2）Validity：合法性
The value that has been decided must have proposed by some process.
每一轮共识的结果值，都是由网络中的某些节点或者进程提议共识出来后结果。
3）Agreement /Integrity/Safety: 完整性
All processes that decide do so on the same value.
网络中节点或者进程都会对相同的调用执行得到相同的结果集，所有正确的节点都必须在这个结果集上保持一致。
定义1）强一致性：对于系统这种存在的节点集合S（1，2，……n），对于任何状态数据序列D(i ，i+1，i+n)，所有节点的S的序列是一致的。
定义2）弱一致性：对于系统这种存在的节点集合S（1，2，……n），对于任何状态数据序列D(i，i+1，i+n)构成的hash root树，节点子集的S’的序列是一致的。
1. 公链特性
对于区块链分为私有链，联盟链和公链。私有链是某个企业内部应用的一个分布式信息平台，节点的信息不公开，仅限于内部访问；联盟链由多方参与的，联盟之间的节点信息仅限于多方共享，联盟节点加入需要CA中心发放证书，加入后必须保障节点的稳定性，退出对网络共识影响大；公链例如Bitcoin，Ethereum，EOS等主网为代表，节点信息需要通过连接到任意几个节点后查询获取，节点是可以随时加入或者退出网络。对于公链的算法，我们认为需要满足一下特性：
属性1）隔离性：需具备一种应用隔离机制，保证应用之间互不干扰，同台设备同时为多种应用场景服务，让设备自身资源收益最大化，也让应用安全性最大化。
属性2）公平公正：节点信息应该是公开、透明、可追溯、不可篡改的一套记账体系，也是区块链的核心价值之一。入链信息公开全网可见，从而确保信息公正性。应鼓励任何人成为节点、并期望节点越多越好，所有节点拥有者相互独立，尽量分散。
属性3）参与的便利性：节点信息应该是公开、透明、可追溯、不可篡改的一套记账体系，也是区块链的核心价值之一，公链的参与者是可以随时加入退出，不受限制。
属性4）生态自赢性：具有生态特性，拥有挖矿等权利益共识算法，设计让节点拥有者、公链使用者、社区运营者均由经济上的受益。
2. 公链算法介绍
1） 椭圆加密算法
ECC的数据基础是罗巴切夫斯基几何，简称罗氏几何，可以得到的结论是：逻辑上不矛盾的一些公理都有可能提供一种几何学。椭圆几何（黎曼几何）是现存非欧几何的类型中的一种公设，即“一条平行线也不能引”。了解非欧式几何，就可以理解平行线的交点。定义平行线相交于无穷远点P∞，使平面上所有直线都统一为有唯一的交点。 平行线必相交，举个例子地球上赤道处的经度线，在赤道处是平行的，在两极却是相交的。
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合：
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
曲线上的每个点都必须是非奇异的（光滑的），椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点，把椭圆曲线定义在有限域Fp上，即有限域椭圆曲线。
椭圆曲线加密算法（ECC）几乎是区块链的核心，通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)，p、a、b确定一条椭圆曲线（p为质数，(mod p)运算）G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的商的整数部分。国际公认的两套曲线参数体系，secp256k1和secp256r1。目前公链中bitcoin、ethereum、eos等用的是secp256k1曲线，来源于bitcoin开源代码。但这个体系不是SEC2的标准，是为了提高性能，剪裁了很多东西。
secp256k1随机性太差，存在破解的可能性。而secp256r1采用的是随机椭圆曲线，也是SEC2[1]的标准，是将来的趋势。
目前标准采用的是secp256r1体系。其中 q = 2256 - 2224 + 2192 + 296 - 1 。
2） SHA（Secure Hash Algorithm ）
链上的数据几乎所有的信息都要用到hash算法，例如Hash3，sha1，sha3，sha2-256，keccak 等等，地址算法也是对公钥进行sha256之后获取。
我们现在用的sha-256也称作sha-2，是新的散列函数，虽然并没有接受像SHA-1一样的公众密码社区做详细的检验，但至今尚未出现对SHA-2有效的攻击。
定义3）Address是公钥hash之后不可逆的结果值，其中
Address= hexEnc(Arrays.copyOfRange(sha256Encode(pubKeyByte), 0, 20));
同时每个节点都有一套自己的公私钥对，为了对信息进一步混淆、高低字节序转化、校验等，我们提出了bcuid作为节点简化的id，换算如下
定义3）hash混淆器，是根据公钥hash之后不可逆的结果值，再经过混淆获取
bcuid = mixStr(HashUtil.ripemd160(eckey.getPubKey))
bcuid = netid + bcuid + gensum(bcuid)
其中mixStr是一个64进制的映射，是大小写字母+数字的随机组合，可以让节点信息地址长度更小。
gensum是一个crc算法，放在地址最后一位，是校验使用。
Netid是一个大写字母网络标示，目前只有两个Raft和DPoS，例如bcuid的两个例子：DPos层节点DXa9wayKlDlaBOmTVVIF6suxgpVNF；Raft层节点Rqu3zAuB5WForN5YFMW1YeuSdCRU7。
3） Trie验证树
Trie树也叫作Radix树，为了提高效率，以太坊在实现上对其做了一些改进。Merkle Patricia Tree(简称MPT树，实际上是一种trie前缀树)是以太坊中的一种加密认证的数据结构，可以用来存储所有的(key，value)对。在p2p网络上传输的交易是一个简单的列表，它们被组装成一个叫做trie树的特殊数据结构，来计算根hash。值得注意的是，除了校验区块外，这个数据结构并不是必须的，一旦区块被验证正确，那么它在技术上是可以忽略的。但是，这意味着交易列表在本地以trie树的形式存储，发送给客户端的时候序列化成列表。客户端接收到交易列表后重新构建交易列表trie树来验证根hash。
在一般的radix树中，key是从树根到对应value得真实的路径。即从根节点开始，key中的每个字符会标识走那个子节点从而到达相应value。Value被存储在叶子节点，是每条路径的终止。假如key来自一个包含N个字符的字母表，那么树中的每个节点都可能会有多达N个孩子，树的最大深度是key的最大长度。
MPT是对hash验证树的扩展，hash验证树是二叉树，MPT的分支节点能指向16个子树，是一个16叉树。
4） DHT（Distributed Hash Table，分布式哈希表）
DHT全称叫分布式哈希表(Distributed Hash Table)，是一种分布式存储方法。在不需要服务器的情况下，每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。具体实现如Kademlia和Chrod。以Kademlia(简称Kad)实现为例，属于一种典型的结构化P2P覆盖网络(Structured P2P OverlayNetwork)，以分布式的应用层全网方式来进行信息的存储和检索是其尝试解决的主要问题。在Kademlia网络中，所有信息均以哈希表条目形式加以存储，这些条目被分散地存储在各个节点上，从而以全网方式构成一张巨大的分布式哈希表。我们可以形象地把这张哈希大表看成是一本字典：只要知道了信息索引的key，我们便可以通过Kademlia协议来查询其所对应的value信息，而不管这个value信息究竟是存储在哪一个节点之上。在eMule、BitTorrent等P2P文件交换系统中，Kademlia主要充当了文件信息检索协议这一关键角色，但Kad网络的应用并不仅限于文件交换。
