System|分布式|BT&区块链

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 // done

Lookup（二分查找）

这个就是数据结构跳表，跳完再跳，没法跳了再线性查找。

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             // done

Successor 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

限制了加入的节点，一般认为仅仅是分布式数据库，而不是区块链。因为前提被打破了。

应用场景

优势：需要共识，而没有可信的第三方时，保证可信度。

劣势：巨大的时空复杂度开销（每个节点存储的单调增长的链+每次都从链头遍历所有的事务获得当前状态）