Ref：CSE, IPADS, SE ,SJTU
分布式系统中，如果中心机器不受绝对信任，或者中心节点一旦崩溃代价很大，存在这样的中心风险很大；此外，中心机器本身的能力局限了网络的scalability。
因此去中心化网络产生。本文的关键在于讨论去中心化机器间的一致性
P2P（Peer-to-peer） Network
问题
- 如何跟踪节点
- 如何找到其他节点
- 数据如何切分
- 如何防止数据丢失
- 如何保证一致性
- 如何确保安全、匿名
BitTorrent
Role
Publisher
publisher发布.torrent文件
.torrent文件本质上是文本文件，包含Tracker信息和文件信息两部分。
- Tracker的address（announce）
- 文件的size，filehash，filename
Role:提供信息
Tracker
组织一群peer，存储动态list，记录谁有哪部分block
Role:查询
Peer
询问Tracker，获得一组随机的peer列表。然后彼此联络具有哪部分，并互相下载。
Role:上传&下载
Seeder
已经下载完成，有全文件备份。告诉Tracker自己的地址。
Role:只上传不下载。
但是，Tracker显然是个中心化的服务器，不具备scalability。因此引入DHT，使得每个节点都具备索引的能力。
DHT（分布式哈希表）
key->value,对此我们需要将key ID(key的SHA-1)映射到对应的node ID(IP的SHA-1）上。
如果直接取模，一旦node增加，那么所有的映射关系都要改变，显然这不切实际。
此外，每个节点不能知道全局，否则存储代价太大。
IPFS就用了这种技术。（一种分布式的文件存储协议）
一致性hash
Lookup（线性查找）
每个节点只知道后继的节点。key存储在ID比keyID大，但是极小的node中。
Lookup(my-id, key-id)
n = my successor
if my-id < n < key-id
call Lookup(id) on node n // next hop
else
return my successor // doneLookup（二分查找）
这个就是数据结构跳表，跳完再跳，没法跳了再线性查找。
Lookup(my-id, key-id)
look in local finger table for
highest node n s.t. my-id < n < key-id
if n exists
call Lookup(id) on node n // next hop
else
return my successor // doneSuccessor List
每一个节点记录一串Successor（目的是提供容错）
根据第一个活着的Successor
节点均匀性
如果节点分布不均，那么无法保证负载均衡。因此MIT提出了一个协议。
先建立大量的Virtual Node，以保证分布均匀，再将Virtual Node平均分给Physical Node，一个Physical Node可能对应多个Virtual Node。
Bitcoin &Blockchain
公钥 作为身份
私钥 签名Tx: transaction（转账记录）
收集足够的Tx之后，block会不断产生随机数nonce（解），直到block的hash满足某个规则，就会开始广播。（俗称挖矿，协议规定每个新增block会创建一个事务，给挖矿者12.5个比特币，并且被其他节点承认；此外，block中记录事务的交易也会提供一定的手续费）
收到广播的所有用户都会在链尾加入此block(因为根据协议，最长的链才是有效的，所以加的越早越好），并且开始继续收集、继续计算下一个block的nonce。
如果有多个等长的blockchain，则随机选择一条，如果有其中一条blockchain增长，则切换到最长的链上。当然也可以头铁继续计算，有可能反超。不过由于算力局限，反超概率不大，如果反超，那么其他链的Tx就会被否认了。
如果有人想对之前的Tx进行修改，那么block的hash就会变动，然而后一block已经记住了之前的hash，因此会检测到篡改。
流程
- 1) 新事务广播给所有节点
- 2) 每个节点将事务记录在最新的block中（检查事务是否有效，否则不承认）
- 3) 每个节点计算block的解
- 4) 当节点找到解时，将block广播给所有节点
- 5) 如果事务有效，那么节点接收这个block
- 6) 节点使用之前block的hash来计算下一个block
智能合同（Smart Contract）
节点存储代码，通过执行代码（比如打赌明天下不下雨）产生新事务，执行更加图灵完备的行为。但是一个问题在于，如果想要执行自定义代码，那么信息可能来自于不可信的链外。而且每个电脑都需要执行代码，代价很大。
Permissioned Chain
限制了加入的节点，一般认为仅仅是分布式数据库，而不是区块链。因为前提被打破了。
应用场景
优势：需要共识，而没有可信的第三方时，保证可信度。
劣势：巨大的时空复杂度开销（每个节点存储的单调增长的链 每次都从链头遍历所有的事务获得当前状态）
