85/666 区块链技术漫游指南 by ArcBlock par

这是666计划的第85篇笔记

本文摘录整理自11月20日在微软研发总部ArcBlock陈天分享的区块链技术漫游.

我们为什么要谈区块链？

image

我们的内容存在中心化服务器上， 依赖于域名， 依赖于网络， 即使隔壁的同事下载过一个视频我们也仍然再下载一次。

image

对物理距离的法则无法突破， 距离越远， 传输的时间越久.

image

想象下星际旅行， 按照光速前进， 从地球到土星要71分钟

decentralization is our destiny 去中心化是必然

问自己， 这可能吗？

让我们带着一系列的问题来探索。

Problem 1: How to verify things?? 第一个需要解决的问题：如何验证一个东西

[图片上传失败...(image-3272e1-1543234233312)]

现有政府的手段

你是谁：通过你的身份证， 居住地址， 个人档案

证明你是谁：脸部识别， 手印， 签名， DNA

对应到我们技术的手段：

你是谁： 哈希值

防伪： 公钥

image

借助公钥加密实现消息的公开可验证。

Alice用私钥实现数字签名， Bob用Alice的公钥实现验证。

单个message可以实现公开可验证了， 那么如何让一系列相关联的messages实现公开可验证呢？

How to make a series, related messages public verifiable? 让一系列相关联的消息实现公开可验证

首先说明几个概念：

• event: message itself, the source of the information

  代表一个message， information的源头

• state: the result after the event is being applied

  对event作出响应和处理后得到的状态

• transformation: the “machine” that applies the event to the previous state

  计算从event到state的过程， 称之为transformation.

  直译：『将事件应用于先前状态的“机器”』

一个银行转账例子：

image

初始状态： alice 30元， bob 20元

第一个event： alice给bob转20元， 得到的新状态是： (alice 10, bob 40)

第二个event: bob给alice 5元， 得到的新状态是： (alice 15, bob 35)

第三个event：alice给bob15元， 得到的新状态是： (alice 0, bob 50)

现在， 如何让上面的转账实现公开可验证？

我们开始尝试吧。

第一个尝试， 让每一个event都被发送者签名

image

只要拥有发送者的公钥， 就可以验证这个event

只要我知道当前的状态， 我就能验证一个event是否合法 『how to?』

具体用如下模型来定义event：

message Event {
    //发送人
    string from = 1;

    //接受者
    string to = 2;

    //总额
    uint64 total = 3;

    //公钥， 用来验证签名是否正确
    bytes public_key = 4;  

    //签名， 消息哈希值的签名（排除签名自身）
    bytes signature = 5; 
  }

下面用代码来实现验证过程：

//签名 （私钥签名）
def sign(msg, private_key), do: msg |> sha3() |> ecdsa_sign(private_key)

//发送消息 （发送消息以及签名）
def send(msg, signature), do: p2p_send(%{msg|signature: signature})

//验证消息 （从消息中提取签名， 并结合公钥验证）
def verify(msg) do
    %{public_key: key, signature: sig} = msg
    hash = sha3(%{msg|signature: <<>>})
    ecdsa_verify(hash, sig, key)
end

Problems 碰到的问题

• How can I ensure that my state is not accidentally (or purposely) mutated?

  如何确保状态不会突然甚至故意被改变？

  • my code to apply event to state may have bugs

    写的代码可能有bug

  • hacker or my employees may mutate the current state

    黑客或者员工会修改当前状态

  • a wrong state will lead to following state inconsistency and make things public unverifiable

    错误的状态会导致接后续状态不一致， 从而达不到公开可验证

• How can I ensure the events I got are ordered correctly as anyone else got?

  如何确保不同的人接收到的event都是按照相同的顺序？

  • a wrong order of events will lead to state inconsistency

    错误的顺序会导致状态不一致

第二个尝试 识别顺序和状态

image

如何识别一个大的data？ 使用哈希

解决状态不一致问题：让我们假设我们有一个魔术可以将帐户状态描述为哈希，所以我们在每个事件中都会这样做

为解决event排序问题， 我们使用『链』来将event组合在一起。

再看一下模型：

message Event {
    string from = 1;
    string to = 2;
    uint64 total = 3;
    bytes public_key = 4;
    bytes signature = 5;
    
    //带上头部信息
    Header header = 6;
  }
  
message Header {
    //当前event的哈希
    bytes hash = 1; 

    //前一个event的哈希，目的： 保持『链』的顺序
    bytes prev_hash = 2;

    // 前一个状态的哈希
    bytes state_root = 3; 
}

现在达到公开可验证的效果了么？ 还没有。

谁来确定顺序？

Problem 2: Consensus 解决第二个问题： 共识

即， 谁来决定顺序

看一下参与共识有哪些场景：

Order of the events （events的顺序决定方式）

• monopoly: I made every decision. e.g. a single database node

  垄断机构： 我自己做出所有决定， 比如单个数据库节点

• oligopoly: We (small group) make every decision. e.g. a database cluster

  寡头： 我们一个小的组织做出所有决定， 比如数据库集群

• perfect competition: everyone makes (part of if not every) decision.

  自由竞争情况： 所有人做决策， 或者所有人中的部分做决策。

image

寡头模式下如何达成共识？

1、 两阶段提交

2、paxos

3、raft

两阶段提交

(skip)

image

Paxos是基于消息传递的通讯模型的。它的假设前提是，在分布式系统中进程之间的通信会出现丢失、延迟、重复等现象，但不会出现传错的现象。Paxos算法就是为了保证在这样的系统中进程间基于消息传递就某个值达成一致。

角色分为proposers，Acceptors，和learners（允许身兼数职）。

proposers提出提案，提案信息包括提案编号和提议的value；

Acceptor收到提案后可以接受（accept）提案，若提案获得多数Acceptors的接受，则称该提案被批准（chosen）；

learners只能“学习”被批准的提案。

这一块有点难度， 需要进一步理解。

Paxos具体可以参考这篇论文： Paxos Made Simple

image

Raft 通过random timeout来选出master

但是， 以上共识不适用于自由竞争的环境， 比如处理拜占庭容错问题

以上情况， 网络里如果有作恶节点就不work了。

The original Byzantine problem

• 9 armies surround Byzantine. They would form a consensus to attack or retreat simultaneously. However they can only communicate with messengers.

  9支部队要围攻拜占庭， 他们需要达成共识， 决定是同时进攻还是同时撤退， 然而， 他们只能通过与信使沟通的方式来作出决定

• One possible solution:

  方案一

  • each side can vote for attack or retreat, and everyone follows the majority of votes.

    每支部队对仅供和撤退统计， 按投票数量执行少数服从多数原则

  • The problem: if their’s one disloyal army, when the vote is 4v4, he can send attack to those who votes attack and send retreat to those who votes retreat. Thus 4 armies will attack and 4 will retreat, leading the battle failed.

    存在的问题： 当9支部队中有一个部队是叛军， 此时投票的比例为4：4， 即4支部队赞成进攻， 4支部队赞成撤退。

    此时， 叛军的策略是， 投其所好， 给那些投赞成的军队发送消息也是『赞成』， 给哪些投撤退的部队发送消息也是『撤退』， 导致的结果就是4支投『赞成』进攻的部队发动进攻， 但是其他人都没有和他们一起进攻， 这4支部队沦陷。

• Another solution:

  方案二

  • Each side tries to solve the same hard problem independently, whoever 1st solve it put her vote inside the resolution and everyone else follows that

    每支部队各自独立解决一个相同难度的问题， 谁先解出来谁就说了算

  • The problem: hard to define a problem that hard to resolve but easy to verify

    存在的问题： 很难定义一个， 足够难解， 还容易验证。

下面该轮到PoW出场了:

PoW: a solution to Byzantine problem

PoW: 针对拜占庭问题的解决方案

• problem to solve: tune a nonce to calculate the hash for the message with number of leading 0s.

  需要解决的问题： 给定一个message和不断调整的nonce值， 计算他们的哈希值， 看看得到的结果是否有若干个前导0， 若是则成功。

  • For the competitors: brute force

    竞争者方式： 暴力破解

  • For the verifier: just hash the event and verify if the hash is correct

    验证者： 对event做哈希计算， 并验证哈希是否正确

• Possible situation - forks:

  可能存在的情形： 分叉

  • Alice and Bob solved the problem and put event A and event B into the event chain, and 40% of nodes got Alice’s result, 60% of nodes got Bob’s result
  • Next round Cynthia solved the problem based on Alice’s chain, and her result propagated to 90% of nodes. Now most nodes will give up their solution and rebase to Alice’s chain. Enough time later, everyone inherits from Alice’s chain.

  分叉的解决方案， 最长链原则。

image

我们继续修改event模型， 加上PoW

message Event {
    //发送人
    string from = 1;

    //接受者
    string to = 2;

    //总额
    uint64 total = 3;

    //公钥， 用来验证签名是否正确
    bytes public_key = 4; // 

    //签名， 消息哈希值的签名（排除签名自身）
    bytes signature = 5; 
  
    //带上头部信息
    Header header = 6;
  }
  
message Header {
    //当前event的哈希
    bytes hash = 1; 

    //前一个event的哈希，目的： 保持『链』的顺序
    bytes prev_hash = 2;

    // 前一个状态的哈希
    bytes state_root = 3; 
    
    // nonce值， 满足event的哈希值满足PoW的要求
    uint64 nonce = 4; 
}

有了PoW就足够了么？ 仍然没有。

如果就每一个Event都需要达成一次共识， 速度会很慢

image

用区块作为容器

一个区块可以包含0到n个Event

节点以区块为单位达成共识

message Block {
    //计算特定哈希值需要的数值
    uint64 nonce = 1;   

    //区块链世界的时钟
    uint64 number = 2;  

    //现实世界的时间
    google.protobuf.Timestamp time = 3;  

    //链到上一个区块
    bytes previous_hash = 4;    

    //本区块的哈希值
    bytes events_root = 5;  

    // state hash that after applying events inside this block 
    //sequentially, what the state hash looks like
    bytes states_root = 6;     
  
    //每一个Event
    repeated Event events = 15;
  }

image

新的Event， 需要加入一个number做为序列号来防止重放攻击。

为什么之前我们的Event里没有加这个？ 因为之前Event是链起来的， 已经有了顺序。 而现在我们打包在一个区块里， 需要序号来避免重放攻击。

message Event {
    //发送人
    string from = 1;

    //接受者
    string to = 2;

    //total
    uint64 total = 3;

    //公钥
    bytes public_key = 4;

    //签名
    bytes signature = 5;

    //Event序号
    uint64 number = 10; 
}

Let’s stop here and conceptualize things 回顾下概念

First of all, in blockchain world, an event is called transaction.

首先， 在区块链的世界里Event被称为transaction(事务)

• block: a container contains a list of transactions.

  区块： 是一系列transaction的容器

• state: the up to date data that meaningful to an application. e.g. for a bank account, its state is the account owner and balance. state_root is the root hash of the entire merkle-tree based states.

  状态： 对应用有意义的最新数据。 比如对于银行账号来说， 就是账号的所有者和帐户余额

• transaction: an event that happened for a purpose, which could be applied to current state and generate new state. e.g. A transfer transaction could lead to the change of account balance.

  事务: 为某个特定目的而发生的事件， 可以作用于当前状态然后产生新的状态。 比如， 转账的事务可以产生帐户余额的变化。

• consensus: agreement on the order of transactions

  共识： 就事务发生的顺序达成的一致认可。

• miner: the node who solved PoW problem and distributed the block she generated.

  旷工： 一个解决PoW算法问题的节点， 并将其产生的区块传播到网络。

• merkle tree: a tree which every leaf node is labelled with hash of data and every none leaf node is labelled with the hash of the labels of its child nodes.

  默克树： 是一棵树， 其叶子节点是数据的哈希值， 每一个非叶子结点是其子节点的哈希值

Thinking in block

• A block is the minimum unit for consensus

  区块是共识的最小单位

• A block is a tick in the blockchain world, it moves the blockchain world forward - so block number is the second for blockchain world

  区块， 是区块链世界的时钟， 它推动着区块链世界向前迈进。 区块号， 则是区块链世界的秒。

  • in bitcoin, a “second” ~= 600 seconds human time

    在比特比里， 一秒是人类时间的600秒左右

  • in ethereum, a “second” ~= 15 seconds human time

    在以太坊里， 一秒是人类时间的15秒左右

• And what is time?

  那么什么是时间呢？

  • Time is a strict progression of cause to effect

    时间是因果关系的严格进展

  • Time is irreversible: past events and states are there unchangeable

    时间不可逆转： 过去的事件和状态是不可改变的。

• What is blockchain time?

  什么是区块链时间？

  • Block number (or height) is a strict progression of cause to effect. En + Sn-1 -> Sn

    区块编号(或高度)是因果关系的严格进展

  • Block number is irreversible: past transactions and states are unchangeable*

    区块编号不可逆转： 过去的事务和状态是不可改变的。

Public verifiable: recap 公开可验证回顾

• hashing to the public key made sender/receiver of the event addressible

  对公钥的哈希使得事件的发送者/接受者可寻址

• asymmetric encryption allows the event public verifiable

  非对称加密允许事件公开可验证

• state_root in the events makes the internal state public verifiable

  事件中的根状态使得内部状态公开可验证

• consensus algorithm like PoW make the order of the events public verifiable

  类似PoW这样的共识算法， 使得事件发生的顺序公开可验证.

• moving consensus to the block level made it practical to be public verifiable

  将共识算法从事件粒度移到区块粒度， 使得公开可验证变得切实可行

We’ve made digital data public verifiable, so what’s the usage? 将数据变得公开可验证， 有什么用呢？

用途有三个：

• 去中心化账本， 比如比特币
• 世界计算机， 比如以太坊
• 去中心化文件系统， 比如IPFS

欢迎来到区块链世界

见第二部分。