数据结构 - 机器学习

密码算法在区块链系统中的重要性，相当于整个体系的骨骼，如果没有骨骼会怎样？毫无疑问，整个大厦将会坍塌，我们来举一些例子，看看都起哪些作用。（1）账户地址生成这个其实就是对公开密钥算法的巧妙使用，首先生成一对密钥，即私钥和公钥，由于公钥是可以公开的，因此可以作为自己对外的一个账号，而又由于公钥必须和对应的私钥匹配才能验证通过，因此这种方式生成的地址，先天就具备可验证性。（2）价值转移保卫我们不展开对价值转移本身经济意义的论述，就说实现方式，这又是公开密钥算法的一个用武之地了。无论是比特币、以太坊、超级账本Fabric还是其他区块链系统，要想在一个分布式的公网上发送一笔代表价值的数据（比如数字货币、证券、资产所有权等），必须解决掉两个基本的问题：1）证明这笔数据确实是发出者的，不是篡改或

区块链是一种去中心化的分布式账本系统，它可以用于登记和发行数字化资产、产权凭证、积分等，并以点对点的方式进行转账、支付和交易。区块链系统与传统的中心化账本系统相比，具有完全公开、不可篡改、防止多重支付等优点，并且不依赖于任何的可信第三方。由于点对点网络下存在较高的网络延迟，各个节点所观察到的事务先后顺序不可能完全一致。因此区块链系统需要设计一种机制对在差不多时间内发生的事务的先后顺序进行共识。这种对一个时间窗口内的事务的先后顺序达成共识的算法被称为“共识机制”目前主要有几大类共识机制：Pow、Pos、DPos、Pool、PBFT1、Pow工作量证明，就是大家熟悉的挖矿，通过与或运算，计算出一个满足规则的随机数，即获得本次记账权，发出本轮需要记录的数据，全网其它节点验证后一起存储；优点：完全去

所谓一致性，就是指数据要完整、要同步。比如，我们在网上下了个订单，付了款，商城系统会记录下这些数据，之后无论我们在哪里访问自己的订单，都能看到同样的结果，即便商城系统出了故障，那一般也会返回一个错误提示而不是给我们一个不一样的结果。再比如银行，我们存了一笔钱进去，无论到哪里，我们查询银行账户的时候金额也不会变。也就是说，在这些系统中，数据的结果总是一致而同步的，即便这些系统的服务器不止一台，但都属于同一个中心集群，在内部是可以高效一致同步的。区块链系统本质就是一个分布式应用软件。分布式系统的首要问题就是如何解决一致性的问题，也就是如何在多个独立的节点之间达成共识。要注意的是，这里说的是要达成一致，而没有说保证一定要结果正确，比如所有的节点都达成失败状态也是一种一致，说白了就是

首先，Paxos算法解决的是非拜占庭将军问题，也就是说仅仅是指分布式系统中的节点存在故障，但是不存在恶意节点的场景，在这种情况下如何达成共识。1998年Lamport提出Paxos算法，后续又增添多个改进版本的Paxos，形成Paxos协议家族。Paxos协议家族有一个共同的特点就是不易于工程实现，Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。除了经典Paxos（又名BasicPaxos），以下均为Paxos的变种，基于CAP定律，侧重了不同方向。·CheapPaxos·EgalitarianPaxos·FastPaxos·Multi-Paxos·ByzanetinePaxosPaxos算法实在是太晦涩难懂，上面所列的Paxos算法分支就不详细介绍了。如

由于Paxos太难懂、太难以实现，Raft算法应运而生。其目的是在可靠性不输于Paxos的情况下，尽可能简单易懂。斯坦福大学的DiegoOngaro和JohnOusterhout以易理解为目标，重新设计了一个分布式一致性算法Raft，并于2013年底公开发布。Raft既明确定义了算法中每个环节的细节，也考虑到了整个算法的简单性与完整性。与Paxos相比，Raft更适合用来学习以及做工程实现。下面，笔者将以通俗易懂的方式来描述这个过程。百花村村长一人负责对外事务。比如，县和乡两级的公文来往，公粮征收，工务摊派，税收等。Raft是一个强Leader的共识协议。我们想象百花村是一个服务器集群，而这个集群的Leader就是村长，村里的每户人家（follower）对应一个服务器，每

1999年Castro和Liskov提出的PBFT（PracticalByzantineFaultTolerance）是第一个得到广泛应用的BFT算法。在PBFT算法中，至多可以容忍不超过系统全部节点数量的1/3的拜占庭节点“背叛”，即如果有超过2/3的节点正常，整个系统就可以正常工作。早期的拜占庭容错算法或者基于同步系统的假设，或者由于性能太低而不能在实际系统中运作。PBFT算法解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。也许就是出于效率的考虑，央行推出的区块链数字票据交易平台用的就是优化后的PBFT算法。腾讯的区块链用的也是PBFT。在PBFT算法中，每个副本有3个状态：pre-prepar

工作量证明（ProofofWork，以下简称PoW）机制随着比特币的流行而广为人知。PoW协议简述如下：1）向所有的节点广播新的交易；2）每个节点把收到的交易放进块中；3）在每一轮中，一个被随机选中的节点广播它所保有的块；4）其他节点在验证块中的所有的交易正确无误后接受该区块；5）其他节点将该区块的哈希值放入下一个它们创建的区块中，表示它们承认这个区块的正确性。节点们总是认为最长的链为合法的链，并努力去扩大这条链。如果两个节点同时广播各自挖出的区块，其他节点以自己最先收到的区块为准开始挖矿，但同时会保留另一个区块。所以就会出现一些节点先收到A的区块并在其上开始挖矿，同时保留着B的区块以防止B的区块所在的分支日后成为较长的分支。直到其中某个分支在下一个工作量证明中变得更长，之前那些

股权权益证明（ProofofStack，以下简称PoS）现在已经有了很多变种。最基本的概念就是选择生成新的区块的机会应和股权的大小成比例。股权可以是投入的资金，也可以是预先投入的其他资源。PoS算法是针对PoW算法的缺点的改进。PoS由QuantumMechanic2011年在bitcointalk首先提出，后经Peercoin和NXT以不同思路实现。PoS不像PoW那样，无论什么人，买了矿机，下载了软件，就可以参与。PoS要求参与者预先放一些代币（利益）在区块链上，类似将财产存储在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。用户只有将一些利益放进链里，相当于押金，用户才会更关注，做出的决定才会更理性。同时也可以引入奖惩机制，使节点的运行更可控，同时更

委托权益人证明机制（DelegatedProofofStake，以下简称DPoS）机制是PoS算法的改进。笔者试着以通俗易懂的方式来说明这个算法。假设以下的场景：百花村旁有一座山叫区块链山，属村民集体所有。村外的A公司准备开发区块链山的旅游资源。A公司和村民委员会联合成立了百花旅游开发有限公司，签了股份制合作协议。以下是春节假期期间发生在村民李大和柳五之间的对话：李大：关于旅游开发区块链山，村民委员会和A公司签约了。柳五：那我们有什么好处？李大：我们都是区块链旅游有限公司的股东了。由于村民都是股东，所有村民就是区块链山的权益所有人。柳五：股东要干什么工作呢？李大：关于区块链的开发的重要决定，股东都要投票的。柳五：那可不成。春节后我要出去打工，在哪儿还不一定呢。哪有时间回来投票。李大：不