姚期智的百万富翁问题

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s weath. How can they carry out such a conversation?

假如有两位富翁想知道他俩谁更有钱，但是又不愿意暴露自己有多少钱，那么是否存在一种沟通方式完成这件事呢？这个问题就是著名的姚的百万富翁问题。1982年，在加州伯克利分校任教的姚期智发布了一篇题为《安全计算的协议》（Protocols for Secure Computations）论文[1]，不仅解决了这个问题，同时还开创了密码学的崭新领域，多方安全计算（Secure Multiple-Party Computation），简称为 MPC 或 SMC。

两位富翁分别叫 Alice 和 Bob，Alice 有 i 百万元，Bob 有 j 百万元，假设 A 和 B 的资产都在一百万到一千万之间，也就是 0 < i, j < 10。

要解决这个问题，我们可以用一个名为带锁的建议箱的隐喻。富翁 Alice 有10只带锁的箱子并且她有一枚解锁的钥匙，并且 Bob 没有钥匙。Alice 将箱子从左到右依次排列。假设她有 6 百万财富值，即 i = 6，于是她从左往右数到第 6 号箱子，并且往第 6 号箱子之前的所有箱子，即 1-5 号箱子，放入标记为 0 的纸条，从第 6 号开始放入标记为 1 的纸条。然后全部上锁离开。这时，Bob 过来看箱子，由于他没有钥匙，所以对箱子中的纸条上的信息一无所知。假设他有 4 百万财富值，即 j = 5，他唯一能做的就是从左往右数到第 4 号箱子，同时将剩下的 9 只箱子全部焚毁。接下来，他将这只箱子交给 Alice，因为 Alice 有钥匙，所以她可以打开箱子。打开箱子后有两种纸条，相应地对应着两种结果。如果纸条是 0 ，那说明 Alice 比 Bob 有钱。反之，若纸条是 1，那说明 Bob 要么比 Alice 有钱，要么和 Alice 一样有钱。在我们的假设中，Alice 打开箱子之后，纸条上标记的是 0，所以 Alice 比 Bob 有钱，而事实确实如此，因为 Alice 有 6 百万元，而 Bob 只有 4 百万元。通过使用这种方法，Alice 和 Bob 除了获得谁更有钱的信息之外，都不知道对方财富值。这种让两方或者多方在保证输入私密的情况下计算某个函数的方法被称为多方安全计算。

当然，我们稍微花费点心思不难发现这个例子中存在泄露秘密的风险。如果 Alice 放入箱子中的是标记 1 - 10 的纸条，那么 Bob 的资产数量就被 Alice 知晓了。这是 MPC 研究的 honest 问题，暂不讨论。

实际中，这个解法具体是怎么工作的？在密码学中，钥匙和带锁的建议箱对应就是非对称密码学体系。Alice 有钥匙，即 Alice 拥有私钥。

对于 Bob 来说，他没有私钥，但是可以使用公钥，他进行下列计算
Bob 选择一个大数 x，并且加密 E(x) = k。
计算 k-j+1 = m，其中 j 是 Bob 的资产
Bob 公开 m 给 Alice，并且告知 m 包含自己的财富值

对于 Alice 来说，她有私钥，需要进行下列计算
计算 m, m+1, m+2, m+3, …, m+j-1=k, …, m+9
也即计算 k-j+1, k-j+2, k-j+3, …, k-j+j, …, k-j+10
使用私钥解密 y[u] = D(k-j+u), 有 y[j] = D(k) = x
求模 z[u] = y[u] mod P，P是质数
z[i] 之前的 z[u] 不变，之后的 z[u] 都+1
Alice 公开所有的 z[u] 给 Bob

Bob 进行检验
若 x mod P = z[j]，那么说明没有进行+1的操作，j <= i
若 x mod P != z[j]，那么说明进行了+1的操作，j > i

社会主义百万富翁问题[2]

两位员工，名叫 Alice 和 Bob。他们做着同样水平的工作，但是怀疑老板优待他们其中一位，所以想知道自己的薪水是否公平。他们不想暴露自己的工资，也不信任第三方机构，那么他们该如何知道自己是否被公平地对待呢？

假设 Alice 和 bob 的薪水在 10, 20, 30, 40 时薪范围内。我们假设 Alice 的时薪是 30 元，Bob 则是 20 元。我们依然使用带锁建议箱的隐喻打比方。

首先，Alice 拿到 4 只带锁的箱子，每个箱子的钥匙都不同。他依次将箱子排开，从左到右的位置表示时薪，即1号箱对应10元时薪，以此类推。然后，Alice 把第 3 号箱子的钥匙保留，代表她的时薪是 30 元，其余的钥匙全部销毁。然后她把打开的箱子交给 Bob。Bob 依次在箱子里放入标记 0 或 1 的纸条。0 代表不是自己的时薪，1 代表是自己的时薪。结果就是他在第 2 号箱子中放入了标记为 1 的纸条，其余的纸条都是 0。然后他把上锁的箱子交给 Alice。Alice 用唯一的钥匙打开了第 3 号箱子，发现里面的纸条是 0。所以她知道了他们两人的时薪并不公平。但是除了这个信息之外，他们对彼此的时薪究竟是多少一无所知。

实际上，这个解法在密码学中被称为不经意传输（Oblivious Transfer，简称 OT）。Bob 给 Alice 发送了多条关于自己时薪是多少的信息，但是 Bob 只能打开那条和自己时薪相关的信息。与此同时，Bob 并没有意识到（Oblivious） Alice 到底想要哪条信息。更一般的定义，不经意传输是一种密码学协议，发送者传输多条消息给接收方，其中只有一条是潜在的消息，但是发送者没法知晓传达到的是哪条消息。不经意传输是由 Maichael O. Robin 在 1981 年首次提出来的。

密码学家 Kilian[3] 已经证明，MPC 和 OT 在理论层面是等价的：给定 OT，可以在不引入其它任何额外假设的条件下构造 MPC，类似地，可以直接应用 MPC 构造 OT。

基本原语

密码学原语是密码学已经广泛认可的低级别的加密算法，比如单向哈希函数和对称加密、非对称加密和数字签名等。这些原语会时常被用于构建加密协议。 比如说，对称加密和哈希函数就能组成消息验证码这种既保密又完整的协议。

MPC 有个基本原语，秘密分享（secret sharing），秘密分享是很多 MPC 协议的核心构造块。

我们在电影中经常看到这样的场景，若想要开启银行保险柜，需要几个人同时按下指纹。这里所有指纹组成一把开门的钥匙，而每个指纹就是这把钥匙的分片，我们把这种手段叫做密钥分割，秘密分享就可以实现密钥分割。秘密分享简单定义：一个 (t, n) 的秘密分享协议可以将秘密值 s 分成 n 个份额，通过任意 t 个秘密份额都可以完整重建出秘密值 s。少于 t 个秘密份额都无法得到和 s 相关的任何信息。前面提到的银行的例子中 t 就等于 n。秘密分享是 Adi Shamir（RSA 中的 S ） 和 George Blakley 于 1979 年独立发明出来的。

一个关于秘密分享隐喻是带锁的嵌套箱子。假设有 5 只带锁的箱子，分别对应不同的钥匙，分属于 5 个人。他们要分享一条消息 X，于是把消息放进最小的箱子里锁起来，然后把小箱子放到大箱子里依次锁起来。最终得到一个加了 5 把锁的嵌套箱子。如果想要获取 X，就必须一层一层地从外层开始解锁，只有 5 个人的钥匙都用上了全部的箱子才能打开。这样的手段就是一种安全的秘密分享。

实际中，这个问题的解法之一是 Shamir 算法。这个算法用到了 (t-1) 次多项式需要 t 个点的坐标才能求解的特性。举个例子，一次多项式 y(x) = kx+b，这个函数代表一条直线，我们都知道两点确定一条直线，只有知道了两个点的坐标才能求解。于是，我们可以令秘密 s 为 b，假设为 5。然后选定斜率为 1。那么这条直线的方程就是 x + 5，此时任取直线上的两个坐标点 (1, 6), (2, 7) 分别给两个人 Alice 和 Bob。Alice 和 Bob 各自拿着坐标点，无法单独推断出方程，所以也就不能获取 s。而只有将两个点合并列方程一起计算，才能得到 s 的值：
k+b=6
2k+b=7
得到，k = 1, b = 5，而 b 就是秘密 s。如果是分享给 3 个人，那么只要在该直线上任意找 3 个点就可以完成任何两方都能获取秘密的计算。

推而广之，(t, n) 的秘密共享，那么就需要 t-1 次的多项式。也就是说，为了满足任意三人能够获取秘密，则需要一条抛物线方程（二次方程）。

安全计算

其实，秘密分享完成了多方安全计算的一部分重要的工作，即保证输入的隐秘性。也就是说，Alice 可以将自己的输入参数以秘密分享的方式分享给 Bob，此时 Bob 只是拿到了 Alice 输入参数的一个份额并不知道原始输入是什么。同理，Bob 也可以将自己的输入一秘密分享的方式公布给 Alice。如果想要完成安全计算，那么还剩下一个问题：如何将这些份额组合起来并运行一个函数，最终得出结果。

加法门

以加法为例。假设 Alice 的隐私输入是 5，Bob 的隐私输入是 8，我们首先将 5 和 8 分别进行秘密分享。为了方便计算，我们将直线的斜率都设为 -1。也就是说，Alice 的直线为 y=5-x, Bob 的直线为 y=8-x，因此只需要分别给出两处纵坐标即可。即 Alice 的秘密值 5 可以分成 (2, 3) 和 (3, 2) 简写成纵坐标 3 和 2，而 Bob 的秘密值 8 可以分成 9 和 -1。然后他们之间交换份额，得到：
Alice：a[0] = 3, b[0] = 9
Bob：a[1] = 2, b[1] = -1
此时，Alice 拥有了 Bob 的份额 b[0]=9，Bob 也有了 Alice 的份额 a[1]=2。

直线的加法比较简单，计算过程可以描述成如下形式：
a+b = (a[0]+a[1]) + (b[0]+b[1])
由于满足加法的结合律，故有 a+b=(a[0]+b[0]) + (a[1]+b[1])=12+1=13。
其实，Alice 和 Bob 的直线方程相加之后得到 y=13-2x，13 就是秘密值 5 和 8 相加的结果。

乘法门

乘法相对而言比较复杂，原因在于计算的过程中，需要获取对方保留在本地不对外公布的份额，这就违背了安全计算的定义。如下：
a b = (a[0] + a[1]) (b[0] + b[1]) = (a[0] b[0]) + (a[0] b[1]) + (a[1] b[0]) + (a[1] b[1])
其中， (a[0] b[0]) 和 (a[1] b[1]) 都可以顺利在 Alice 和 Bob 本地完成，但是 (a[0] b[1]) 和 (a[1] b[0]) 会要求对方保留的份额，而这部分是不能够共享的，否则就会暴露各自的输入。

为了应对这个问题，我们需要进行遮掩（Masking）处理。此时，需要引入一个第三方来生成一组数用于遮掩彼此不想分享的数据。对于 Alice 而言，就得遮掩 b[1]，对于 Bob 而言，就得遮掩 a[1]。

第三方首先生成一个三元组(s, t, st)，其中 st=s*t。例如：s=7, t=11, st=77。然后分别将这三个元素进行秘密分享。
对于 s，我们有 s[0]=4, s[1]=3；对于 t，t[0]=5, t[1]=6；而 st，则有 st[0]=44, st[1]=33。接下来，第三方将 s[0] 和 t[0] 发送给 Alice，而将 s[1] 和 t[1] 发送给 Bob。
Alice 需要计算一个算式，我们记为 z[0]：

z[0] = st[0] + (s[0] beta) + (alpha t[0]) + (alpha beta)
Bob 需要计算另一个算式，记为 z[1]：
z[1] = st[1] + (s[1] beta) + (alpha * t[1])

其中，最为有意思的事情发生了，
alpha = (a[0]-s[0]) + (a[1]-s[1])
beta = (b[0]-t[0]) + (b[1]-t[1])
由于，Alice 只有 s[0] 和 t[0]，所以她可以计算 alpha 和 beta 式子左边的算式。同理，Bob 可以计算右边的算式。之后，他们双方可以分享这个各自的结果，注意此过程中，a 和 b 的任何信息都没有暴露。在本例中，alpha = -2, beta=-3.

我们开始计算 z[0] 和 z[1]
z[0] = st[0] + (s[0] beta) + (alpha t[0]) + (alpha beta) = 44 + (4 -3) + (-2 5) + (-2 -3) = 28
z[1] = st[1] + (s[1] beta) + (alpha t[1]) = 33 + (3*-3)+(-2*6)=12

最终的结果就是 z[0]+z[1] = 40。也就是我们想计算 5 * 8 的结果。这种乘法也被叫做 Beaver 乘法。

代码演示

我们使用 HoneyBadgerMPC 的 Python 代码来实现乘法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

async def beaver_multiply(ctx, x: Share, y: Share):
  """The hello world of MPC: beaver multiplication  
Linear operations on Share objects are easy
Shares of random values are available from preprocessing
Opening a Share returns a GFElementFuture
  
  """  
  
  s, t, st = ctx.preproc.get_triples(ctx)  
  
  Alpha = await (x - s).open()  
  
  Beta = await (y - t).open()  
# Alpha*Beta is multiplying GFElements
# Alpha*t, Beta*s are multiplying GFElement x Share -> Share
# st is a Share
# overall the sum is a Share
  
  xy = (Alpha * Beta) + (Alpha * t) + (Beta * s) + st  
  
  return xy

调用的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

x = ctx.Share(5) + ctx.preproc.get_zero(ctx)
y = ctx.Share(7) + ctx.preproc.get_zero(ctx)

xy = await beaver_multiply(ctx, x, y)

# Check openings of the multiplied values

X = await x.open()

Y = await y.open()

XY = await xy.open()

assert XY == X * Y

print(f"[{ctx.myid}] Beaver Multiplication OK")

beaver_multiply 函数中进行了封装，我们可以拆解还原计算过程。
s, t, st = ctx.preproc.get_triples(ctx)
这里就是获取 s, t 和 st 的步骤，代码中省略了初始化三元组的过程。
Alpha = await (x - s).open()
对应上面说到的算式

1

alpha = (a[0]-s[0]) + (a[1]-s[1])

需要注意的是，(a[1]-s[1]) 来自 Bob，所以需要异步通信获取 Bob 计算的结果，即 await..open.
Beta = await (y - t).open()
对应的算式是

1

beta = (b[0]-t[0]) + (b[1]-t[1])

计算过程同 alpha 一致。

接着我们观察乘法门中算式：

1

z[0]+z[1] = st[0] + (s[0] * beta) + (alpha* t[0]) + (alpha * beta) + st[1] + (s[1] * beta) + (alpha * t[1])

然后对比代码中的算式
(Alpha * Beta) + (Alpha * t) + (Beta * s) + st
不难发现，(Alpha t) 对应了(alpha t[0]) + (alpha t[1]) 的算式，而 (Beta s) 对应了算式 (s[0] beta) + (s[1] beta) 的结果，而 st 则是 st[0] + st[1] 的结果。顺便计算下这里面到底沟通了多少次?

1
2
3
4
5
6
7
8
9
10
11

x: 1
y: 1
s: 2
t: 2
st: 2
Alpha: 1
Beta: 1
(Alpha * Beta): 1
(Alpha * t): 1
(Beta * s): 1
st: 1

总计有 14 次来自三方的通信。不过，至此我们理解了 beaver_multiply 和我们在乘法门中分析的算法一致。

小结

MPC 的基本原语除了秘密分享之外，还有随机预言机（Random Oracle，简称RO）以及混淆（乱码 Garbled Circuit）电路。另外，构造 MPC 协议的功能函数还有几种广泛的应用，例如前文提及的不经意传输和零知识证明等。严格意义上讲，零知识证明并不是 MPC 的必要组成成分，加密学中将零知识证明划归为外包计算（Outsourced Computation），原因是相较于 MPC，因为零知识证明只需要一方提供加密数据，而另一方进行计算，最后将计算的结果返回给数据所有方，而 MPC 则要求多方输入数据，协同完成计算。不过全同态加密依然可以用来实现 MPC。

参考链接

1. Protocols for Secure Computation
2. Socialist millionaires’ Problem
3. Kilian, J. 1988 Founding Cryptography on Oblivious Transfer
4. Secret sharing
5. HoneyBadgerMPC

• 缘起
• 实践出真知
  • 快速获取
  • 澄清概念
    • Ownership
    • Move
    • Reference
    • Mutable reference
  • 解释错误
  • 数据竞态条件
  • 构建树状结构
  • 渲染树状结构
• 总结
• 源码 Github

缘起

做区块链的基本几乎没有人不知道 Rust 这门编程语言，它非常受区块链底层开发人员的青睐。说来也奇怪，Rust 起源于 Mazilla，唯一大规模应用就是 Firefox，作为小众语言却在区块链圈子里火了。这其中应该和以太坊的发起人 Govin Wood 创建的 Parity 项目有关，Parity 是一款用 Rust 编写的以太坊客户端。

最初接触 Rust 的时间大概是 2015 年，当年有同事发了一封“是否对 Rust 编程语言感兴趣的”的邮件。当时年少不懂事热血，觉得这门语言因为它小众很酷，所以特别适合拿来练功，所以就激情地回应了邮件，结果之后就没有了下文，想必那位同事也因为响应的人数太少而兴致缺缺。

第二次关注 Rust 是因为陈天在自己的公众号中提到了这门语言。我比较欣赏陈天，当初学习 Elixir 也是受他影响，所以也跟着他的步伐去听了张汉东的知乎Live，然后加入了他的读者群（魅力Rust），在这个群中潜水了大半年，一直很惊叹这个群的活跃度。

2019年，区块链圈中的一次大事件是 Facebook 要发非主权货币 Libra，随之而来是基于 Rust 之上的 Move 编程语言。这个 Move 说白了就是 Move 的一种 DSL，用比较学术的话说是指称（denotational）语义，用简单的编译器把 Move 的语法翻译成 Rust 的语法然后借助 Rust 的编译器生成二进制码。这个过程没有什么惊喜，不过 Move 语言显然是借鉴了 Rust 中移交（Move）主权（Ownership）的概念，它表征了这样一种事实——数字资产只能有一个主人，一旦移动，就会发生主权转移，以前的主人就丧失了该主权。这种想法和 Rust 中主权管理非常契合，所以不难理解为什么 Libra 的开发团队把名字也照搬过来了。当然，Libra 的底层区块链也用的是 Rust。这个大事件加上以太坊 Parity 的珠玉在前，对于程序员这群天生喜欢新鲜事物的人类而言，学习 Rust 的热情必然水涨船高。

大概就是在这种契机下，我开始学习 Rust 的。依照老规矩，我还是会从 tree 这个命令行程序入手，在试错中逐步学习 Rust 这门语言。包含它的基本数据类型，组合数据类型，控制流，模块（函数）以及文件和集合操作，还有最关键的 Ownership 的应用。

实践出真知

学习 Rust 最深刻的体验莫过于和编译器较劲，这也是我听到过最多的抱怨。我想许多新手看到这么多警告或者错误，嘴上不说，心里应该很不是滋味。但是这也是 Rust 引以为豪的设计哲学，每一门新进的语言都有自己的本质原因（Rationale）或者设计哲学，比如 Lisp 家族的 Clojure 就有 Elegance and familiarity are orthogonal 的玄言妙语；往远古追溯，Java 的 Write Once, Run Anywhere 豪言壮语；而 Rust 的基本设计哲学是 If it compiles, then it works，这个条件有多苛刻我们稍微想一想就能知道——动态弱类型语言向静态强类型语言的逐步趋同态势，基本已经宣告了类型系统的胜利，但即便如此，现代软件工程也还是处处强调程序员要手写各种测试确保代码运行时的正确性——从单元测试到集成测试，从冒烟测试到回归测试，从 Profiling 到性能测试。这些测试方法和工具已经深入到软件工程的方方面面，然而各类软件还是漏洞百出。Rust 发出这种高调宣言，不免有夜郎自大之嫌疑。不过程序届是个能造概念也能落地概念的神奇圈子，高调的牛吹着吹着也就实现了。况且，Rust 充分诠释了现代编程语言的核心思想——约束程序员，不是劝劝你的意思，是憋死你的意思。

我在《我是如何学习新的编程语言》中说过学习的最好方式是有目的地试错，我时常拿来练手的程序叫tree - list contents of directories in a tree-like format. 这段程序需要用到的 Rust 基本构件有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

基础概念
1. 变量 - let
2. ownership borrow - &
3. 可变性 - mut
4. 可变引用 - &mut


复合数据类型
1. String - String::from("") // 非基本类型
2. Slice - "" or vec[..]
2. struct - struct {}

集合及其操作
1. Vec<_> - Vec::new() // 考虑到集合需要自动扩展
2. iter()
3. .map()
4. .enumerate()
5. .flatten()
6. .collect()
7. .extend() //集合拼接

控制语句
1. if Expressions - if {} else {}
2. recursions

模块
1. fn - fn x(s: String) -> Vec<String>

功能组件
1. Path
2. fs
3. env

当尝试寻找这些元素时，我发现 Rust 或者诸如此类的编译型语言都有一个让人不舒服的地方——验证的前置步骤耗时太长。因为没有repl，所以想去了解一些概念的使用方法，就不得不另外创建一个项目（我可不想污染当前项目的代码），在它的 main 函数里编写试验程序，这比起具有快速反馈能力的repl，着实太慢了。不过这里的慢也是相对的，Rust 也有一个显著的优势，在出现编译错误时，编译器不仅能向你解释原因，还能推荐潜在的修改方式，这就比 Javascript 一类的动态语言要清晰和高明得多。再利用内置的 assert_eq! 等断言函数预判结果，又比单独写测试省事。所以，总体而言，学习的过程还是很愉悦的。

快速获取

这里举个例子，为了解如何拼接两个集合时，需要事先搞明白几个问题：

1. 集合的构造？
2. 集合的拼接？
3. 结果的断言？

在没有repl的条件下，唯一快速上手的工具就是文档，在 https://doc.rust-lang.org/std/ 的官方标准库中，可以搜到Struct std::vec::Vec的详细解释。

通过例子程序，可以很快知道集合的构造方式如下：

1
2
3

let mut v = vec![1, 2, 3];
v.reverse();
assert_eq!(v, [3, 2, 1]);

vec! 宏可以快速构造出一个集合来，顺便试验下它的reverse方法。那么集合如何拼接呢？为了解答这个问题，我一般会用搜索引擎，或者深入文档，查找如 concat，append等关键字，每每总有收获。

在不考虑非功能需求的前提下，我们先用最直接的方式实现，例如：文档中给出的样例extend方法

1
2

let v = vec![1, 2, 3];
v.extend([1, 2, 3].iter().cloned()); // 编译错误

注意，这里编译失败。Rust 编译器会直截了当地给出错误信息。

1
2
3
4
5
6
7

error[E0596]: cannot borrow `v` as mutable, as it is not declared as mutable
  --> src/main.rs:13:5
   |
12 |     let v = vec![1, 2, 3];
   |         - help: consider changing this to be mutable: `mut v`
13 |     v.extend([1, 2, 3].iter().cloned());
   |     ^ cannot borrow as mutable

错误信息中透露出我们的程序在尝试借用（borrow）一个不可变的变量。borrow和 mutable都是新的概念。对于新的概念，我们会习惯地用熟知的知识去类比。如果套用函数式编程中不可变的特性，大体可以猜到 Rust 中的变量默认是不可变的。但是 cannot borrow as mutable 中 borrow 确实是有点超出认知范围。那么此时弄清定义是非常有必要的。

澄清概念

学习语言的过程中最需要注意的事项就是澄清概念。当遇到崭新的概念时，我们得停下先去补充这部分的知识，然后再回过头来理解和解决实际遇到的问题。因为每一门编程语言都有本门派的哲学原理，它本身就萃取了多种理论和实践的成果，所以必须学习这些概念。学习的过程其实就是逐步澄清概念的过程。

在学习（尝试定义）borrow 的过程中，我又先后接触到了 ownership, move, reference, mutable reference 等概念。所以我定义了这些概念：

Ownership

变量拥有它指称的值的所有权。
在 Rust 当中，变量拥有它指称的值，即变量（variable）是它指称值（value）的主人（owner），值一次只能有一个主人，一旦主人离开作用域它的值就会被销毁。

Move

把一个变量的值重新赋值给另一个变量的行为。
根据 Ownership 的定义，值一次只能有一个主人，所以此时该值的所有权会被转移给另一个变量，原来的变量就丧失了对这个值的所有权，导致的直接影响就是这个变量此后不再可用。

Reference

一个变量指向（refer to）值而非拥有该值的所有权的状态。
在很多赋值的场景，包括变量赋值或者函数参数赋值，我们并不希望之后原来的变量不再可用，此时可以通过&(ampersands创建一个指向值的引用，将引用进行赋值时不会发生 Move，所以原来的变量依旧可用。这种赋值行为被称为borrow（借用）。结合实际，我们拥有的物品可以出借给别人，别人享有该物品的使用权（Possession），而非所有权（Ownership）。

Mutable reference

标识该引用的值是可变的。

很多场景下，我们希望引用传递的值是可以改变的。此时我们就必须通过&mut标识该引用，否则不允许修改操作发生。值得注意的是，&mut标识要求原来的变量也必须是mut的，这很好理解，可变的变量的引用也得可变。而且为了防止数据竞态条件的发生，在同一个作用域下，&mut的引用只能有一个，因为一旦出现多个可变引用，就可能遭遇不可重复读风险（注意，Rust 保证这里没有并行修改的风险）。而且同一个值的&mut和&的引用不能共存，因为我们不希望一个只读&的值同时还能被写&mut，这样会导致歧义。

解释错误

澄清了必要概念以后，我们再来回顾上面的代码。先去看一下这个extend函数的定义：

1
2
3
4

fn extend<I>(&mut self, iter: I)
where
    I: IntoIterator<Item = T>, 
Extends a collection with the contents of an iterator...

原来v.extend只是一个语法糖，真正的方法调用会把self作为第一个参数传递到extend(&mut self, iter: I)当中。可变引用作为函数参数赋值，那么自然原来的变量也必须声明成可变的。

所以我们照着它的指示修正如下：

1
2

let mut v = vec![1, 2, 3]; // 加上一个mut修饰符
v.extend([1, 2, 3].iter().cloned());

这回编译器消停了，利用assert_eq!，我们来验证extend操作的正确性。

1

assert_eq!(v, [1, 2, 3, 1, 2, 3]);

另外，值得注意的是，Rust 和我们熟悉的函数式编程有些不同，集合的拼接不会产生一个新的集合，而是对原有的集合进行修改。一般情况下，我们都会警惕可能会出现数据的竞态条件——多个线程对该集合进行写入操作怎么办？带着这个问题，我们反思一下什么是数据的竞态条件。

数据竞态条件

数据竞态条件发生的必要条件有：

1. 多个引用同时指向相同的数据；
2. 至少有一个引用在写数据；
3. 对于数据的访问没有同步机制。

考察1和2：
假如此处有两个引用指向同一个集合，如下：

1
2
3
4

let mut v = vec![1, 2, 3];
let r1 = &mut v;
let r2 = &mut v;
assert_eq!(r1, r2);

编译器会立即给出编译错误

1
2
3
4
5
6
7
8
9

error[E0499]: cannot borrow `v` as mutable more than once at a time
--> src/main.rs:13:10
|
12 | let r1 = &mut v;
|          ------ first mutable borrow occurs here
13 | let r2 = &mut v;
|          ^^^^^^ second mutable borrow occurs here
14 | assert_eq!(r1, r2);
| ------------------- first borrow later used here

也就是说，在指定的作用域下只能有一个可变引用。为什么要如此设计呢？在单线程下，这好像并不会出现数据竞争的问题^1。不过考虑到下面这种场景的语义，我们思考一下。

1
2
3
4
5
6

let mut v = vec![1, 2, 3];
let r1 = &mut v;
let r2 = &mut v;
assert_eq!(r2[1], 2);
*r1 = vec![0]
assert_eq!(r2[1], 2); // 失效

一旦允许r1改变数据，那对于r2而言，它先前持有的数据就已经发生改变甚至失效，再拿来使用就有问题了，在上面这个例子当中，*r1解除引用后被重新赋值，导致v的值随之改变，但是r2并不知情，依旧使用r2[1]导致此处越界。这个问题和数据库中事务的不可重复读（提交读）的隔离级别类似，但是在单线程下这并不能算作充分的理由，只是说在语义层面有细微的不自然，留待后续研究。

蹊跷的是，如果我将两个可变引用放到不同的函数中，同样的逻辑却可以绕过编译器错误。

1
2
3
4
5
6
7
8
9
10
11
12
13

fn main() {
    let mut v = vec![1, 2, 3];
    mut1(&mut v);
    mut2(&mut v);
}

fn mut1(v: &mut Vec<i32>) {
    *v = vec![0];
}

fn mut2(v: &mut Vec<i32>) {
    println!("{}", v[1]); // panicked at 'index out of bounds' 运行时错误
}

可见，上述的论述并没有解释清楚在单线程下同一个作用域下限制多个可变引用的根本原因。

对于&mut和&其实也可以做同样的解释。所以&mut和&在 Rust 同一个作用域中无法共存。

考察3：
至于在多线程的环境下，是否会出现数据竞态条件，我们得看 Rust 在线程使用方面的限制。在 Rust 的上下文里，使用Thread::spawn的线程时必须 Move 所有权^2，因为在 Rust 看来，Thread 的 LifeTime（生命周期）会比调用它的函数的生命周期的长，如果不 Move 所有权，那么线程中数据就会在调用函数结束后释放掉变量的内存，导致线程中的数据无效。所以，这样的限制是很有必要的，但反过来想，一旦数据的所有权发生转移，那么多个线程并行修改同样数据的可能性也就不复存在。

构建树状结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

struct Entry {
    name: String,
    children: Vec<Entry> 
}

fn tree(path: &Path) -> Entry {
    Entry{
        name: path.file_name()
            .and_then(|name| name.to_str())
            .map_or(String::from("."), |str| String::from(str)),
       
        children: if path.is_dir() {
            children(path)
        } else {
            Vec::new()
        }
    }
}

既然是树状结构，定义的结构体就是递归的。这里的struct Entry {}就是一种递归的结构。我想实现的树状结构大致如下：

1
2

entry :: {name, [child]}
child :: entry

Rust 中没有显式的return，最后一个表达式的结果会被当成返回值，所以此处整个Entry结构体会被返回。

1
2
3

path.file_name()
 .and_then(|name| name.to_str())
 .map_or(String::from("."), |str| String::from(str)),

这段代码看上去很复杂，但实现的功能其实很简单，目的是为了获取当前文件的文件名。那么逻辑为何如此绕呢？这是由于 Rust 中的多种字符串表示导致的问题，暂按不表。先去看看各个函数的定义。

Path.file_name 的定义

1

pub fn file_name(&self) -> Option<&OsStr>

and_then是我们常见的flat_map操作在 Rust 中的命名，其目的是为了在两个Option之间实现转换。

OsStr.to_str 的定义

1

pub fn to_str(&self) -> Option<&str>

上面的path.file_name().and_then(|name| name.to_str())最终转变成了Option<&str>，在其上调用Option.map_or方法并提供默认值：字符串"."。为什么要提供默认值呢？这和OsStr到Str的转换密切相关，当我们传入参数"."时，Path.file_name返回的其实是一个None。

构建了父级的树状结构，我们需要把子级的树状结构也一并完成，最终通过递归，构建出一棵内存中的目录树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

fn children(dir: &Path) -> Vec<Entry> {
    fs::read_dir(dir)
        .expect("unable to read dir")
        .into_iter()
        .map(|e| e.expect("unable to get entry"))
        .filter(|e| is_not_hidden(&e))
        .map(|e| e.path())
        .map(|e| tree(&e))
        .collect()
}

fn is_not_hidden(entry: &DirEntry) -> bool {
    entry
         .file_name()
         .to_str()
         .map(|s| !s.starts_with("."))
         .unwrap_or(false)
}

这里也存在挺多的转换操作，我们一一解释。

1

fs::read_dir(dir).expect("unable to read dir")

使用expect是因为fs::read_dir返回的是一个Result<ReadDir>，在其上调用expect会尝试解开其中的值，如果有错则会抛出错误。解开的结果类型是ReadDir，它是io::Result<DirEntry>的迭代器，也就是一个目录下的所有类目，可以在上面调用into_iter()创建出可以被消费的迭代器。

1
2
3
4

.map(|e| e.expect("unable to get entry"))
.filter(|e| is_not_hidden(e))
.map(|e| e.path())
.map(|e| tree(&e))

接着，解开Result<DirEntry>之后，我们把隐藏文件过滤掉，因为filter接收的一个闭包，这个闭包的类型声明是P: FnMut(&Self::Item) -> bool，所以filter接收的所有元素都是引用类型，故调用时无需需声明成is_not_hidden(&e)。

然后利用e.path()获取每个文件的全路径，并依次交给tree去递归构建。经过tree和children两个函数的交替递归，内存中的一棵目录树就被构建出来了。

有了内存中的树状结构，我们接下来就可以渲染这个结构了。具体的做法如下：

1. 对于第一层目录名，如果它是最后一个目录，则前缀修饰为L_branch = "└── "；反之，装饰成 T_branch = "├── " 。
2. 对于有子目录，如果是其父目录是父级最后一个目录，则前缀装饰为SPACER = " "；反之，前缀装饰成 I_branch = "│ "。

渲染树状结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14

fn render_tree(tree: &Entry) -> Vec<String> {
    let mut names = vec![tree.name]; // error
    let children = &tree.children;
    let children: Vec<_> = children
        .iter()
        .enumerate()
        .map(|(i, child)| decorate(children.len() - 1 == i, render_tree(child)))
        .flatten()
        .collect();
    
    names.extend(children);

    names
}

这里会有编译错误，错误信息如下：

1
2
3
4
5

error[e0507]: cannot move out of `tree.name` which is behind a shared reference
  --> src/main.rs:48:26
   |
48 |     let mut names = vec![tree.name];
   |                          ^^^^^^^^^ move occurs because `tree.name` has type `std::string::string`, which does not implement the `copy` trait

由于tree.name不是标量类型（Scalar Type），它没有实现copy trait（见提示），又因为tree本身是复合类型（Compound Type），tree.name如果发生 Move 的话，包含它的tree就有问题了。为了避免发生这种情况，我们不得不去引用&tree.name。但是一旦加上引用，又会出现类型不匹配的编译错误。

1
2
3
4
5

59 |     names
   |     ^^^^^ expected struct `std::string::String`, found reference
      |
         = note: expected type `std::vec::Vec<std::string::String>`
                       found type `std::vec::Vec<&std::string::String>`

我们期待的是Vec<String>而不是Vec<&String>，所以需要重新构建出一个String出来。可以使用String::from(&String)方法

1

let mut names = vec![String::from(&tree.name)];

这样修改下来，才能保证编译完全通过。但事实上，Rust 给我们提供了一个更加便捷的写法

1

let mut names = vec![tree.name.to_owned()]

使用to_owned()表示重新拷贝了一份数据，和重新构建一个String出来别无二致。

组合调用

1
2
3
4
5
6
7
8

use std::env;
use std::path::Path;
use std::fs::{self, DirEntry};

fn main() {
    let args: Vec<String> = env::args().collect();
    println!("{}", render_tree(&tree(Path::new(&args[1]))).join("\n"));
}

render_tree 返回的是Vec<String>，所以为了打印出来，我们将所有元素用"\n" join到一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

.
├── Cargo.toml
├── target
│   └── debug
│       ├── tree
│       ├── incremental
│       │   ├── tree-emhx2ztsyouq
│       │   │   ├── s-fg6t1j15rq-rcdkil.lock
│       │   │   └── s-fg6t1j15rq-rcdkil-2guhg58bq8usk
│       │   │       ├── 2y5hmosay7v21uaa.o
│       │   │       ├── 3bc30huj642htvsl.o
│       │   │       ├── os4trg3bosufhmz.o
│       │   │       ├── 24gploi4fp7jtlzq.o
│       │   │       ├── query-cache.bin
│       │   │       ├── dep-graph.bin
│       │   │       ├── 4x450fwi8c4bpcw1.o
│       │   │       └── work-products.bin
│       │   └── tree-145pnmzdafxnt
│       │       ├── s-fg7zukct1x-1q6vl1v.lock
│       │       └── s-fg7zukct1x-1q6vl1v-2bl7ybv3bt926
│       │           ├── 1hr1ye57pnkjmrbq.o
│       │           ├── 27h2hp0z2xow1ues.o
│       │           ├── 5ed0wukafi4fahkg.o
│       │           ├── 2f0ihwts74qcmxow.o
│       │           ├── 330o0ei85brt7kr4.o
│       │           ├── 4v9apptkodzb8xa6.o
│       │           ├── 1g9e2frs3e2z69pv.o
│       │           ├── 37b06wzocgbel481.o
│       │           ├── 4l05de8rviyudi4f.o
│       │           ├── h6fn9swczh7498b.o
│       │           ├── 316xpau62mt4is8d.o
│       │           ├── 5ekvjec2kf4lmbtt.o
│       │           ├── 1futuyfy32uf6fso.o
│       │           ├── 2h1ucudwsaw3ps8a.o
│       │           ├── 1gotohk3wwy2f6dy.o
│       │           ├── 3b9tgf3uo9qj9m4l.o
│       │           ├── 11nu5z6vt7pkotko.o
│       │           ├── 1iwt54u59d6ic7px.o
│       │           ├── 2knnbzs842y8uh0j.o
│       │           ├── 3ifvzvvypros5ggf.o
│       │           ├── 2z2hec5yokv1i4dp.o
│       │           ├── ya9r48v2sak0pg6.o
│       │           ├── 155em2p8h2hm19ng.o
│       │           ├── 32v7dlio50845m8.o
│       │           ├── 4c1hc1pxl75vi07x.o
│       │           ├── 2yqijaid0vje1zn1.o
│       │           ├── 4vjgrzm4xto1375t.o
│       │           ├── 21iztlljbl6euh9m.o
│       │           ├── 20v9k1fk8kja961x.o
│       │           ├── 4z53k2t8wxm10fyq.o
│       │           ├── bhyzck3ll360qet.o
│       │           ├── 1y3hdwm9ww9b9y5i.o
│       │           ├── 3c44aga3rejf73f6.o
│       │           ├── rj0yv7mdi9un1aq.o
│       │           ├── 50x9vm1j7pl93o9s.o
│       │           ├── 217lokaaxwdhlrx9.o
│       │           ├── 4wnp20b81q6iaxux.o
│       │           ├── 3r82h5ttm93ejtxf.o
│       │           ├── 3ot3q95g45ci1vo6.o
│       │           ├── query-cache.bin
│       │           ├── 39sf80jvxavwpxo3.o
│       │           ├── 8oeuahm3962nobh.o
│       │           ├── cik7i0re2dlsxhk.o
│       │           ├── 1waoie6zpkzqj4ct.o
│       │           ├── 19luckbhcaquztt8.o
│       │           ├── 3g7vkdnj0ai0qhcm.o
│       │           ├── 1rp337sq8mpirnfu.o
│       │           ├── 1b3x8y2m27htwxg6.o
│       │           ├── 41wp4wr46haq7yo6.o
│       │           ├── gupfi67uepu20cm.o
│       │           ├── dep-graph.bin
│       │           ├── 5btmoqde9gzs48ku.o
│       │           ├── 4vmtr5p2n2ar0hfj.o
│       │           ├── work-products.bin
│       │           ├── 2jd13r5ry01uwce0.o
│       │           ├── 54om8xu4dcwmt36o.o
│       │           ├── 3pjvdh4zm61wtvac.o
│       │           ├── 21mzfl756r7eb753.o
│       │           ├── 57o4bjq3o18zq3ji.o
│       │           ├── 4lh6qwni3j9cdda6.o
│       │           └── 4rj8jramt231qg09.o
│       ├── native
│       ├── tree-e27a55060278e1c5.dSYM
│       │   └── Contents
│       │       ├── Resources
│       │       │   └── DWARF
│       │       │       └── tree-e27a55060278e1c5
│       │       └── Info.plist
│       ├── tree.dSYM
│       │   └── Contents
│       │       ├── Resources
│       │       │   └── DWARF
│       │       │       └── tree-5fa2575d1085e7f2
│       │       └── Info.plist
│       ├── tree-e27a55060278e1c5.d
│       ├── examples
│       ├── tree-e27a55060278e1c5
│       ├── deps
│       │   ├── tree-5fa2575d1085e7f2.dSYM
│       │   │   └── Contents
│       │   │       ├── Resources
│       │   │       │   └── DWARF
│       │   │       │       └── tree-5fa2575d1085e7f2
│       │   │       └── Info.plist
│       │   ├── tree-5fa2575d1085e7f2.d
│       │   ├── tree-e27a55060278e1c5.dSYM
│       │   │   └── Contents
│       │   │       ├── Resources
│       │   │       │   └── DWARF
│       │   │       │       └── tree-e27a55060278e1c5
│       │   │       └── Info.plist
│       │   ├── tree-5fa2575d1085e7f2
│       │   ├── tree-e27a55060278e1c5.d
│       │   └── tree-e27a55060278e1c5
│       ├── build
│       └── tree.d
├── Cargo.lock
└── src
    └── main.rs

总结

学习下来的一些主观感觉是 Rust 中的概念繁杂，有些地方的设计确实让人有些迷惑。再加上类型众多（如：OsStr, String），代码很难通过直觉判断写出，需要大量查阅文档才能让编译器消停。所以学习曲线相对陡峭。

不过，语言约束的越多，某种程度上讲，对于程序员而言却是福音。If it compiles, then it works. 的哲学理念在前。学习道阻且长，努力加餐饭。

提示
一般标量类型都实现了copy trait.

• 所有的整，如：u32
• 布尔类型，如：true 或 false
• 字符类型，如：char
• 浮点数类型，如：f64
• 当且仅当所有元素都是Copy的元组，如：(i32, i32)是Copy，但是(i32, String)就不是Copy的。

于2019年9月22日

embark是什么

embark是一款特定于Ethereum区块链平台的DApp开发环境，辅助开发者创建、构建编译、测试和部署DApp，可无缝集成计算（EVM）、存储（IPFS/Swarm）和网络（Whisper）资源。

embark的便捷之处

在尝试embark并和truffle框架进行对比之后，我总结以下几个方面的优势：功能全面，上手迅速，反馈快速，可视化程度高，合约可调试。

功能全面

正如embark概览所言，embark并不仅仅是一款只提供构建编译、测试部署功能的开发工具，还是一整套的开发环境。它包含了智能合约自动部署，客户端(UI)开发，测试，DApp分布式托管（IPFS/Swarm），点对点通信（Whipser）和组件监控、在线IDE及代码调试（Cockpit）等功能。

如果和truffle框架比较，embark几乎包含了它提供的所有功能。不过，embark缺失了truffle在migration方面的功能，基于对不可变基础设施的考量，embark有必要拥抱这项标准实践。

embark考虑了单独开发智能合约的可能性，所以允许开发者在创建项目时只创建智能合约项目结构，通过启用 --contracts-only选项。而且在构建编译时，也可以指定embark build --contracts命令单独构建智能合约。

上手迅速

这个维度虽然有点主观，但是很值得拿出来说。一般学习新的工具，需要花很多时间看文档学习基本概念和操作流程，最恼火的就是熟悉各种配置项，当你左支右绌，手忙脚乱让工具程序跑起来，除了浪费时间，也侧面证明该工具不够成熟、对开发者不友好。

很意外的是，本来以为这么一个大而全的开发环境设置起来一定得耗费不少时间，结果却是除了用yarn global add embark报出一个compiler和yarn不兼容后，改成了npm install -g embark安装，就再没有特别恼人的问题出现了。

注意：
上面的安装错误其实是因为embark对于yarn的版本有一定的要求，从embark源码中可以得到如下前置条件。

1
2
3
4
5

"engines": {
  "node": ">=8.12.0",
  "npm": ">=6.4.1",
  "yarn": ">=1.12.3"
},

我当前的yarn版本是1.6.0，使用brew upgrade yarn升级到1.15.2就可以全局安装了。

1
2
3
4

yarn global add embark
...
embark version
4.0.2

embark run会启动一个命令行中可视化界面，里面会告诉你当前Dapp的状态，包括智能合约是否部署，哪些组件服务可用，最最重要的是它会告诉你接下来你该做什么！在Logs视窗中，embark试图告诉你开发环境确实哪些依赖服务，比如geth节点没有启动（事实上，可以用gananche-cli代替），ipfs节点未侦测到，Cockpit Web UI所在端口还有Dapp服务的入口等等。而console视窗则是命令交互入口，一条help命令就能展示很多有用信息。

以上这些信息都无需查看文档便可以获得，个人觉得从尝试中学习是特别有趣的事情。

我一般拿从零到写出第一行程序的时间作为上手快慢的标准。这行程序是用来试验，未必得手写，所以我选用了truffle自带的样例MetaCoin.sol和ConvertLib.sol。

1
2
3
4
5
6
7
8

// ConvertLib.sol
pragma solidity ^0.5.0;

library ConvertLib{
  function convert(uint amount,uint conversionRate) public pure returns (uint convertedAmount) {
    return amount * conversionRate;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// MetaCoin.sol
pragma solidity ^0.5.0;
import "./ConvertLib.sol";

contract MetaCoin {
  mapping (address => uint) balances;

  event Transfer(address indexed _from, address indexed _to, uint256 _value);

  constructor() public {
    balances[msg.sender] = 10001;
  }

  function sendCoin(address receiver, uint amount) public returns(bool sufficient) {
    if (balances[msg.sender] < amount) return false;
    balances[msg.sender] -= amount;
    balances[receiver] += amount;
    emit Transfer(msg.sender, receiver, amount);
    return true;
  }

  function getBalanceInEth(address addr) public view returns(uint) {
    return ConvertLib.convert(getBalance(addr), 4);
  }

  function getBalance(address addr) public view returns(uint) {
    return balances[addr];
  }
}

当把这两个智能合约文件放到项目根目录下contracts/目录中后，合约代码被自动编译，并在Contracts视窗中展示出来，状态为Deployed，这表明智能合约已经被部署到区块链网络里。之后，我进入Cockpit Web UI，惊喜地发现这个服务俨然就是一个高配版的etherscan.io，通过它不仅可以查看部署之后的合约，甚至还可以调用合约方法。

估算下来，我用embark写完第一行代码的时间基本可以忽略不计。

反馈快速

写程序都希望其可行性能被快速验证，因为只有这样才能方便快速地迭代出正确功能的程序。我所知道的前端开发者是把这个过程做到极致的群体，比如Liveloading；embark对于智能合约也提供了一致的功能。当修改合约文件并保存时，embark会自动检测变更同时重新编译再部署，这个过程非常快速（当然，embark对于哪些修改的合约需要重新部署是有一定限制的，而且据我观察，这里面有些潜在的bug，比如修改合约constructor中的内容就不会触发重新构建，即便用embark reset也不行，这个和文档的描述有些出入，值得花时间研究下）。

自动重新构建和部署合约对程序员的效率提升很有帮助，但是无法快速验证同样达不到目的。所幸的是，embark不仅提供了Cockpit这样的可视化工具辅助验证合约的正确性，而且还提供embark console，在console中可以调用部署合约的实例，比如：输入Embark (Development) > MetaCoin <ENTER>就能获取部署好的实例，有了合约实例就可以调用其上的方法进行数据校验。

同样重要的是，embark支持js和sol版本测试，我可以像使用truffle一样使用TDD的方式开发DApp了。

可视化程度高

当在终端中运行embark run时，embark会自动进入可视化界面（dashboard）。这里面监控的信息会实时告诉你DApp开发的状态。除此之外，embark还提供了DApp的Web server，Cockpit Web UI页面，这些绝对是开发DApp极大的助力。

如果不想使用dashboard，可以通过embark run --nodashboard禁用。不过，根据我的经验，禁用dashboard的结果是没法直接拿到进入Cockpit的访问token，还需要运行embark console进入命令行单独获取。

从上面这点来看，embark在组件化方面做得相当出色，虽然功能大而全，但是并没有限制你删减不必要的组件、独立启用感兴趣的组件

合约可调试

调试合约在以前的开发过程中还是比较难的，不过借助于Cockpit，embark也提供了在线调试的能力。Cockpit内置一个编辑器，它和本地的开发目录保持一致，该编辑器就提供了debug功能。另外，进入Explorer页，我们甚至可以对某次的tx进行debug验证这次合约调用的真实数据流转情况。

小结

总的来说，embark是一款优秀的区块链开发环境。相比较truffle的专注于合约工程化的努力，embark的功能更加丰富，而且各组件组合性很强。对于开发者而言，快速开发出DApp才是真的诉求，而embark显然在这一方面具备很大的优势。

怎么快速玩转embark

工具版本号

1
2
3
4
5
6
7
8

yarn --version
1.15.2
npm -v
6.4.1
node -v
v10.15.3
embark version
4.0.2

快速使用DApp

embark默认开发时都是 development 环境，为了对接正确的ganache-cli（模拟以太坊客户端）端口，我们需要修改config/contract.js文件中development/port到ganache-cli默认的8545端口。

先执行embark build --pipeline development，然后启动embark run，此时就可以在http://localhost:8000查看DApp的界面了。

IPFS分布式托管

首先得安装IPFS的客户端，然后运行如下命令：

1
2
3
4

ipfs init
ipfs daemon
...
Daemon is ready

当ipfs启动完成后，embark的dashboard会显示ipfs节点已连接。此时执行embark upload，构建出来的dist目录就会被分发到ipfs网络，然后就可以通过内容寻址（content-addressed）的方式访问这个静态网站了。

BIP39解释

定义

BIP39^1定义了一种将计算机产生的随机数翻译成人类可读的方式，初衷很简单：结合BIP32^2，辅助人类记忆产生主密钥的种子。

主要概念

1. initial entropy (ENT)
2. check sum (CS)
3. mnemonic sentence (MS)
4. wordlists

这三者的长度关系如下：

1
2

CS = ENT/32
MS = (ENT + CS)/11 化简成 MS = 3 * CS

举个例子，如果初始熵长度为 128，ENT/CS/MS组成的关系表格填充如下：

初始熵 initial entropy

初始熵可以通过随机数生成器生成，允许的大小在 128-256 bits 范围之内。

校验码 check sum

校验码利用初始熵经过哈希得出，而且长度必须是$ENT/32$。

助记词 mnemonic sentence

助记词需要将初始熵和校验码拼接，然后切分成每11位为一组，每一组二进制数转换成十进制数作为索引wordlists的下标，以便提取对应的词汇。以128位的ENT为例，它最终会产生12个词汇。

词汇表 wordlists

词汇表的构成是有原则可遵守的，其一，词汇之间可辨识性强，英文的词汇在前4个词汇就能有很快速的区分；其二，避免相似的词语，人毕竟是健忘的；其三，词汇应该排过序，便于二分查找。

代码解释

下面利用Nodejs版本的BIP39^3解释

1
2
3
4
5
6
7

function generateMnemonic (strength, rng, wordlist) {
  strength = strength || 128
  if (strength % 32 !== 0) throw new TypeError(INVALID_ENTROPY)
  rng = rng || randomBytes

  return entropyToMnemonic(rng(strength / 8), wordlist)
}

generateMnemonic(...)函数的参数rng全称是random number generator，即随机数发生器，默认是randomBytes。此处，ENT的默认长度是128位，运行randomBytes(128/8)将产生了16字节的随机数。然后调用entropyToMnemonic(...)函数生成助记词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function entropyToMnemonic (entropy, wordlist) {
  if (!Buffer.isBuffer(entropy)) entropy = Buffer.from(entropy, 'hex')
  wordlist = wordlist || DEFAULT_WORDLIST

  // 128 <= ENT <= 256
  if (entropy.length < 16) throw new TypeError(INVALID_ENTROPY)
  if (entropy.length > 32) throw new TypeError(INVALID_ENTROPY)
  if (entropy.length % 4 !== 0) throw new TypeError(INVALID_ENTROPY)

  var entropyBits = bytesToBinary([].slice.call(entropy))
  var checksumBits = deriveChecksumBits(entropy)

  var bits = entropyBits + checksumBits
  var chunks = bits.match(/(.{1,11})/g)
  var words = chunks.map(function (binary) {
    var index = binaryToByte(binary)
    return wordlist[index]
  })

  return wordlist === JAPANESE_WORDLIST ? words.join('\u3000') : words.join(' ')
}

entropyBits是entropy的二进制表示；checksumBits是entropy经由SHA256计算得到的哈希值再截断到CS的长度得来的，调用deriveChecksumBits(...)函数产生checksumBits的逻辑如下：

1
2
3
4
5
6
7

function deriveChecksumBits (entropyBuffer) {
  var ENT = entropyBuffer.length * 8
  var CS = ENT / 32
  var hash = createHash('sha256').update(entropyBuffer).digest()

  return bytesToBinary([].slice.call(hash)).slice(0, CS)
}

这里的计算和前面长度关系规则完全吻合，checksumBits通过slice(0, CS)截断得到4位的二进制数。

计算得到entropyBits和checksumBits之后，把它们拼接到一起，得到一组bits，然后按每组11bits分隔，这里使用了正则表达式 bits.match(/(.{1,11})/g)，正则表达式(.{1,11})表示对任意1-11个bit进行分组，由于正则默认是最长匹配，所以每11位就被分成了一组。最终，每组二进制数都会被转成十进制数，进而作为词汇表的下标索引对应的词汇，详细见上文的chunks.map(function (binary) ... 过程。

中文词汇表

BIP39其实并没有定义词汇表，所以不同的自然语言都可以自行实现自己的词汇表。NodeJS版本的BIP39^3就支持中文的词汇表。

1
2
3

var mnemonic = bip39.generateMnemonic(160, null, bip39.wordlists.chinese_simplified)
->
'定 过 丘 搭 斥 紫 遍 官 寿 穿 贯 别 讯 卵 符'

除了中文的词汇表，它还支持下列词汇，如：繁体中文等。

1
2
3
4
5
6
7
8
9
10
11

export const wordlists: {
    EN: string[];
    JA: string[];
    chinese_simplified: string[];
    chinese_traditional: string[];
    english: string[];
    french: string[];
    italian: string[];
    japanese: string[];
    spanish: string[];
};

生成BIP32种子

拿到助记词之后，就可以从助记词生成种子。这里其实使用了pbkdf2算法，不过有趣的是，参数mnemonic反而是pdkdf2算法中的password参数：

1
2
3
4
5
6

function mnemonicToSeed (mnemonic, password) {
  var mnemonicBuffer = Buffer.from(unorm.nfkd(mnemonic), 'utf8')
  var saltBuffer = Buffer.from(salt(unorm.nfkd(password)), 'utf8')

  return pbkdf2(mnemonicBuffer, saltBuffer, 2048, 64, 'sha512')
}

BIP 全称是 Bitcoin Improvement Proposals，相当于互联网中RFC (Request for Comments)，它是用来记录草案或者标准的。

BIP32解释

定义

BIP32定义了Hierarchical deterministic wallets (HD Wallets)，HD指出了这类钱包的两大特征。

第一点特征是层级结构，钱包一般会存储一组key-pair对，这组key-pair对是链状存储，但是HD钱包是树状存储，也就是说它的结构中有根节点，根节点会派生出子节点，子节点又可以派生出子节点。这样做的优势是它可以有选择的把某个层级的一组key-pair对分配出去，这样就可以和组织结构匹配，比如：总部保留根密钥，其它分部用总部派生的密钥；也可以和用途匹配，比如：花钱的和收钱的地址可以分开。

第二点特征是确定性，因为所有的key-pair对都是从同一个根派生出来的，所以只要妥善保管好根（主密钥）就可以在其它的系统中快速地恢复钱包。

层级结构和确定性如下图示：

主要概念

1. Master key
2. Chain Code
3. Extended key

主密钥及其生成

主密钥是从一串长度在128到256位的比特序列（种子）中生成的，然后使用HMAC-SHA512计算出64字节序列（称为I），左边32字节（称为IL）作为主私钥，右边32字节（称为IR）作为主Chain Code。

大致步骤如下：

1. 生成熵为128 - 256bit 的种子
2. I = HMAC-SHA512(key=”Bitcoin seed”, data = seed)
3. <<IL :: bytes(32), LR :: bytes(32) >> = I
4. MasterSecretKey = IL & MasterChainCode = IR

这里有个问题值得探讨，这样生成的 MasterSecretKey 是符合 secp256k1 定义的利用ECDSA算法生成的私钥吗？我们可以利用secp256k1.privateKeyVerify(…)方法验证，结果是正确的。

额外的熵 Chain Code

因为每个父密钥都可以派生出很多子密钥，所以为了避免子密钥直接依赖父密钥，需要引入额外的熵（chain code）去增强父密钥，这个额外的熵，或者说，随机的256位的比特序列就是 Chain Code。

扩展密钥 Extended Key

根据定义，父密钥和Chain Code的组合 (k, c) 就是扩展私钥，而扩展公钥则是 (K, c)，其中的 K 是通过 secp256k1 计算私钥 k 得到的。

Extended Key 在序列化的地方也值得关注，具体的规则，可以细读BIP32。

举个例子：

1
2
3
4

// publicKey
03795fd38bbffdddb24b72af417cf3fa540db8f60783dd32f61f0ca5af464fd492
// ExtendedPublicKey
xpub6GmbjntbdLF4JNhBxwoRBrdw2BBujvJ514tRHFMQaoFA5eSRaWwr6CQSGq1HtirLGSTT8SHqMGWQk4rbZLJsVFA4NLZZYUR25ZEdhnGJ7R1

序列化之后的publicKey的首部4比特是版本号，比如此处的xpub就是mainnet的意思。

每个扩展密钥都有$2^{31}$个普通子密钥和$2^{31}$个Hardened子密钥，一般会用i+$2^{31}$表示Hardened子密钥，记为$I_H$。

代码解释

这里，我们使用hdkey[^1]进行代码解释。

主密钥及其生成

1
2
3
4
5
6
7
8
9
10
11
12
13

var MASTER_SECRET = Buffer.from('Bitcoin seed', 'utf8')

HDKey.fromMasterSeed = function (seedBuffer, versions) {
  var I = crypto.createHmac('sha512', MASTER_SECRET).update(seedBuffer).digest()
  var IL = I.slice(0, 32)
  var IR = I.slice(32)

  var hdkey = new HDKey(versions)
  hdkey.chainCode = IR
  hdkey.privateKey = IL

  return hdkey
}

seedBuffer是128-256bit的随机序列作为种子，然后利用HMAC-SHA512生成I值，分割出的IL和IR分别赋值给privateKey和chainCode。

Chain code

Chain code 会在派生子密钥的时候起作用，derive(path) -> deriveChild(index) 是派生子密钥的过程：

1
2
3
4
5
6
7
8
9

var data = Buffer.concat([this.publicKey, indexBuffer])
var I = crypto.createHmac('sha512', this.chainCode).update(data).digest()
var IL = I.slice(0, 32)
var IR = I.slice(32)

var hd = new HDKey(this.versions)
// Private parent key -> private child key
// ki = parse256(IL) + kpar (mod n)
hd.privateKey = secp256k1.privateKeyTweakAdd(this.privateKey, IL)

从上面的代码可以看到，chainCode用来作为HMAC-SHA512的密钥对data进行了哈希处理。最终子密钥privateKey通过secp256k1.privateKeyTweakAdd(…)生成，这个函数来自secp256k1[^2]库，主要功能是拼接，如下：

1
2
3
4
5
6
7
8
9
10

exports.privateKeyTweakAdd = function (privateKey, tweak) {
  var bn = BN.fromBuffer(tweak)
  if (bn.isOverflow()) throw new Error(messages.EC_PRIVATE_KEY_TWEAK_ADD_FAIL)

  bn.iadd(BN.fromBuffer(privateKey))
  if (bn.isOverflow()) bn.isub(BN.n)
  if (bn.isZero()) throw new Error(messages.EC_PRIVATE_KEY_TWEAK_ADD_FAIL)

  return bn.toBuffer()
}

值得一提的是，在derive(path)函数中，我们会看到Hardened判断的条件是是否带有单引号，例如：44'

1
2
3
4
5
6

var hardened = (c.length > 1) && (c[c.length - 1] === "'")
var childIndex = parseInt(c, 10) // & (HARDENED_OFFSET - 1)
assert(childIndex < HARDENED_OFFSET, 'Invalid index')
if (hardened) childIndex += HARDENED_OFFSET

hdkey = hdkey.deriveChild(childIndex)

在后续介绍BIP44的过程中，我们会明白这样处理的含义，Path为m/44'/60'/0'/0/0在BIP44中有特定的含义，这种表示法和BIP32的结合点就在这里。

Extended key

Extended key 可以分为 privateExtendedKey 和 publicExtendedKey，这里以 privateExtendedKey 为例：

1

cs.encode(serialize(this, this.versions.private, Buffer.concat([Buffer.alloc(1, 0), this.privateKey])))

其中versionls.private，默认值是0x0488ADE4，encode操作可以忽略，具体的序列化逻辑发生在serialize中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function serialize (hdkey, version, key) {
  // => version(4) || depth(1) || fingerprint(4) || index(4) || chain(32) || key(33)
  var buffer = Buffer.allocUnsafe(LEN)

  buffer.writeUInt32BE(version, 0)
  buffer.writeUInt8(hdkey.depth, 4)

  var fingerprint = hdkey.depth ? hdkey.parentFingerprint : 0x00000000
  buffer.writeUInt32BE(fingerprint, 5)
  buffer.writeUInt32BE(hdkey.index, 9)

  hdkey.chainCode.copy(buffer, 13)
  key.copy(buffer, 45)

  return buffer
}

常量LEN为78，这就是序列化的结构大小。需要注意的点是，按照定义这里的字节序都是大端（Big Endian，也成为网络字节序）。

BIP44解释

定义

BIP44 定义了逻辑上的层级结构，所谓逻辑，就是人为赋予意义。BIP44综合了BIP32的HD Wallet设计和BIP43[^3]的Purpose约定，使得HD Wallet能够表达多币种，多账号，账号的外部或内部key-pair对构成的组，外部指的是地址对外可见，专门用来接收或发送数字货币的地址；而内部则是对外不可见，多用来表达找零 (change) 的概念。

主要概念

BIP44在BIP32的路径中定义了5个层级：

1

m / purpose' / coin_type' / account' / change / address_index

• Purpose: 44'or 0x8000002C 这表明后面的子密钥都遵从BIP44的约定
• Coin type: 0' 代表比特币，60' 代表以太币
• Account: 代表不同的用户身份，比如：储蓄或者收款账户，以及各种开支账户
• Change: 0 表示外部key-pair组；1 代表内部key-pair组，比如专门用来找零的地址
• Address_index: 根据BIP32，地址会生成多个，可以从0开始索引

Purpose, Coin type以及Account都有单引号，意味着它们都是Hardened密钥，而Change和Address_index则是Normal的密钥。这样做是为了安全，BIP32中提到了一个事实，如果知道了父级的ExtendedPublicKey及其派生出来的Non-hardened private key，就等于知道了父级的ExtendedPrivateKey，这就是Hardened密钥存在的理由。引文如下：

One weakness that may not be immediately obvious, is that knowledge of a parent extended public key plus any non-hardened private key descending from it is equivalent to knowing the parent extended private key (and thus every private and public key descending from it). This means that extended public keys must be treated more carefully than regular public keys. It is also the reason for the existence of hardened keys, and why they are used for the account level in the tree. This way, a leak of account-specific (or below) private key never risks compromising the master or other accounts.

代码解释

继续使用hdkey[^1]来解释

1
2
3
4
5
6

let hdWallet = hdkey.fromMasterSeed(seed)
let key = hdWallet.derivePath("m/44'/60'/0'/0/0")
console.log("publicKey:", key1._hdkey._publicKey.toString("hex"), "\nextendPublicKey:", key1.publicExtendedKey())
->
publicKey: 03795fd38bbffdddb24b72af417cf3fa540db8f60783dd32f61f0ca5af464fd492 
extendPublicKey: xpub6GmbjntbdLF4JNhBxwoRBrdw2BBujvJ514tRHFMQaoFA5eSRaWwr6CQSGq1HtirLGSTT8SHqMGWQk4rbZLJsVFA4NLZZYUR25ZEdhnGJ7R1

依据前面提到的定义，通过路径m/44'/60'/0'/0/0派生出了以太坊某个外部账户下的第一个地址。

[^1]: NodeJS - hdkey

[^2]: NodeJS - secp256k1

[^3]: BIP43 - Purpose scheme

椭圆曲线数字签名算法生成私钥

Secp256k1
通过椭圆曲线数字签名算法生成私钥和公钥，其中SEC（Standards for Efficient Cryptography）是专门利用ECDSA或者其可选项Schnorr算法来产生高效的加密方法。
特点是生成密钥很快。

Scep256k1 基本特性

• secp256k1 ECDSA signing/verification and key generation.
• Adding/multiplying private/public keys.
• Serialization/parsing of private keys, public keys, signatures.
• Constant time, constant memory access signing and pubkey generation.
• Derandomized DSA (via RFC6979 or with a caller provided function.)
• Very efficient implementation.

讲解代码

步骤

1. 生成私钥
2. 加密私钥
3. 生成 keyObject 对象
4. 从keyObject对象中恢复私钥

生成私钥

下面利用 keythereum[^1] 产生符合以太坊的密钥，并产生keyObject文件

1
2

const params = { keyBytes: 32, ivBytes: 16 };
let {privateKey, salt, iv} = keythereum.create(params);

keythereum可以产生私钥，以及后面加密私钥所用的PBKDF2算法需要的salt，和加密aes-128-ctr私钥的iv值。

得到私钥之后，我们可以通过私钥生成公钥。

1
2
3

let privateKeyBuffer = Buffer.from(privateKey, "hex") // or "base64"
let publicKey = secp256k1.publicKeyCreate(privateKeyBuffer, false).slice(1);
let address = "0x" + keccak256(publicKey).slice(-20).toString("hex");

加密私钥

利用KDF算法基于password派生出密钥，然后利用这个密钥加密我们的私钥。

1
2
3
4
5
6
7
8
9
10
11

const password = "Hello,Ethereum"
const options = {
    kdf: "pbkdf2",
    cipher: "aes-128-ctr",
    kdfparams: {
        c: 262144,
        dklen: 32,
        prf: "hmac-sha256"
    }
};
const keyObject = keythereum.dump(password, privateKey, salt, iv, options);

这就是产生keyObject基本思路。我们在看看dump函数到底做了什么

1

this.marshal(this.deriveKey(password, salt, options), privateKey, salt, iv, options);

deriveKey(…) 的源码如下：

1
2
3
4
5
6
7

this.crypto.pbkdf2Sync(
        password,
        salt,
        options.kdfparams.c || this.constants.pbkdf2.c,
        options.kdfparams.dklen || this.constants.pbkdf2.dklen,
        prf //hmac-sha256
      );

这里基于password生成的derivedKey，这个密钥并不是我们要用的私钥，而是用来加密先前生成的privateKey的，加密的过程在marshal函数中调用的encrypt函数里。

1

let ciphertext = this.encrypt(privateKey, derivedKey.slice(0, 16), iv, algo).toString("hex");

encrypt函数，如下：

1
2
3
4
5
6
7
8
9

var cipher, ciphertext;
algo = algo || this.constants.cipher;
if (!this.isCipherAvailable(algo)) throw new Error(algo + " is not available");

//加密过程
cipher = this.crypto.createCipheriv(algo, this.str2buf(key), this.str2buf(iv));
ciphertext = cipher.update(this.str2buf(plaintext));

return Buffer.concat([ciphertext, cipher.final()]);

此处的ciphertext代表的是privateKey，而key则是derivedKey

生成 keyObject 对象

得到了加密后的ciphertext之后，开始组装keyObject对象并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

keyObject = {
      address: this.privateKeyToAddress(privateKey).slice(2),
      crypto: {
        cipher: options.cipher || this.constants.cipher,
        ciphertext: ciphertext,
        cipherparams: { iv: iv.toString("hex") },
        mac: this.getMAC(derivedKey, ciphertext)
      },
      id: uuid.v4(), // random 128-bit UUID
      version: 3
    };
keyObject.crypto.kdf = "pbkdf2";
      keyObject.crypto.kdfparams = {
        c: options.kdfparams.c || this.constants.pbkdf2.c,
        dklen: options.kdfparams.dklen || this.constants.pbkdf2.dklen,
        prf: options.kdfparams.prf || this.constants.pbkdf2.prf,
        salt: salt.toString("hex")
      };    

privateKeyToAddress(…)方法里首先通过privateKey产生publicKey，然后使用keccak256哈希publicKey得到地址。

具体实现如下：

1
2
3

let privateKeyBuffer = Buffer.from(privateKey);
let publicKey = secp256k1.publicKeyCreate(privateKeyBuffer, false).slice(1);
let address = "0x" + keccak256(publicKey).slice(-20).toString("hex");

keccak256(publicKey) 产生了32bytes，截取尾部20bytes转换成十六进制之后就是40字符，加上前导0x之后，就是42个字符的以太坊地址，比如：0x0f645438395206b408e52be4fcf4bc21c330bfa2

从keyObject对象中恢复私钥

有了keyObject和密码就可以恢复原来的私钥

1

let privateKey = keythereum.recover(password, keyObject)

可以想到，recover方法中，首先会利用password和keyObject中的salt派生出当初的密钥derivedKey，然后把加密过的私钥ciphertext和derivedKey, iv作为原来加密算法aes-128-ctr的输入参数，成功解密后返回明文的私钥。

具体代码如下：

1

verifyAndDecrypt(this.deriveKey(password, salt, keyObjectCrypto), salt, iv, ciphertext, algo)

这里首先得到了derivedKey，然后验证并解密kyeObject中的ciphertext，如下：

1
2
3
4
5
6
7
8
9
10
11
12

function verifyAndDecrypt(derivedKey, salt, iv, ciphertext, algo) {
  var key;
  if (self.getMAC(derivedKey, ciphertext) !== keyObjectCrypto.mac) {
    throw new Error("message authentication code mismatch");
  }
  if (keyObject.version === "1") {
    key = keccak256(derivedKey.slice(0, 16)).slice(0, 16);
  } else {
    key = derivedKey.slice(0, 16);
  }
  return self.decrypt(ciphertext, key, iv, algo);
}

注意这里的mac值比较，确保了ciphertext没有被人篡改才有解密的必要。

参考实现

1. NodeJS
2. Bitcoin-core
   [^1]: Keythereum

KDF 的定义

实现 key stretching [^1] 的方法，具体就是从一个 master key，password 或者 passphrase 派生出一个或者多个密钥，派生的过程，使用PRF（Pseudo Random Function 伪随机函数）可以是某种哈希算法。

[Key stretching]
密钥延长算法（一种更慢的哈希算法），用于将初始密钥转换成增强密钥，在计算过程中刻意延长时间或者消耗空间，这样有利于保护弱密码。

两种密钥派生算法

PBKDF2 (CPU-Hard algorithm)

PBKDF2是基于密码派生出密钥的算法，需要消耗很多算力，为了是防止暴力破解加密。

Scrypt (Memory-Hard algorithm)

Scrypt 也是一种 password-base KDF 算法，比起 PBKDF2 需要消耗更多的资源，从而有效防止了专有硬件 ASIC/ FPGA 的暴力破解。Scrypt 内部用的还是 PBKDF2 算法，不过内部会长时间地维护一组比特数据，这些数据会在生成复杂的 salt 的过程中反复加密（Salsa20，一种流密码^3）得到。网上流行说，以太坊的PoW共识算法是利用Scrypt实现的，但事实上，以太坊自己实现了一套哈希算法，叫做Ethash^2.

区别

一言以蔽之，PBKDF2是算力型，而Scrypt是资源消耗型的。

Both PBKDF2 and scrypt are key derivation functions (KDFs) that implement key stretching by being deliberately slow to compute and, in particular, by having an adjustable parameter to control the slowness.
The difference is that scrypt is also designed to require a large (and adjustable) amount of memory to compute efficiently. The purpose of this is to make cracking it harder to parallelize using devices like GPGPUs or custom ASIC / FPGA hardware. Such devices may have hundreds or even thousands of parallel processing units, each capable of hashing a different password using traditional KDFs like PBKDF2, which don’t require much memory. However, it turns out that, at least using current technology, providing each of these parallel units with large amounts of memory space is a lot more difficult and expensive than making the units themselves.

密钥派生原理

PBKDF2 运行的原理

1
2
3

passphrase -> [dklen, salt, c] > 1000] -> hash

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

其中：

1. PRF(Pseudorandom function)：伪随机数产生的密钥，如：hmac-sha256
2. dklen：派生所产生的密钥的长度
3. salt（盐值）：是一串随机生成的比特，加载密钥的固定位置做哈希后，可以防止彩虹表攻击导致的密码泄露
4. c：迭代的次数
5. DK：期望的密钥 derived key

例子：WPA2 (WiFi Protected Access)

1

DK = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)

术语

Password
密码就是用于证明身份，获取和身份相称的访问权限。

Passphase
用于用户认证或者加密程序的操作步骤，特别是KDF算法就是从passphrase中派生出来的。

[^1]: Key stretching

关于组件聚合张力图的讨论

周三的午休时间，我在ThoughtWorks北京办公室分享了一场《架构整洁之道导读》。当谈到分享组件聚合原则的时候，很多同事表示难以理解。究其缘由，是我们无法将组件违反原则的后果对应到真实项目的问题上，这就导致原则和实践之间的不一致。讨论的过程异常激烈，但是很遗憾地最终并没有得到一个服众的结论。所以为了进一步澄清这些争议点，我决定专门组织一场针对组件聚合原则张力图的讨论会。在吴大师的鼓动下，时间定在下周四晚上的8点半，与会人员大多是咨询团队的技术教练，也有我们项目上的客户。

在这场长达两个半小时的讨论会上，没想到首先出现争议的点居然是组件的定义。

组件是软件部署的最小单元，是整个软件系统在部署过程中可以独立完成部署的最小实体。

对于这样的定义，大魔头提出了质疑：library（库）并不能独立部署。但凡出现明显的逻辑漏洞的时候，我们最好的方式是抛开译文回去看原文。

Components are the units of deployment. They are the smallest entities that can be deployed as part of a system.

阅读原文之后，我们发现“组件是软件部署的最小单元。”这句话翻译得并没有太大问题，但是第二句就有损原意了，原意是说可以作为系统的一部分被部署的最小实体，而没有强调部署过程这种动态的概念，否则就和前一句是同义反复。所以这个定义里面并没有说组件可以独立部署。后面提到组件可以被链接到一个独立可执行文件或者归档文件，又或者，可以被打包成.jar、.dll或者.exe文件，并以动态加载的插件形式实现独立部署。

解读组件的定义

来自原文：

Components can be linked together into a single executable. Or they can be aggregated together into a single archive, such as a .war file. Or they can be independently deployed as separate dynamically loaded plugins, such as.jar or .dll or .exe files.

来自讨论：

20:56:56 From tianjie : These dynamically linked files, which can be plugged together at runtime, are the software components of our architectures.

联系上下文理解之后，我们知道：组件可以被设计成独立部署的，但是并不是所有的组件都是可以独立部署的。这是要澄清的，不然讨论聚合原则的时候容易出现偏差。

吴大师接着解释说，组件应该是个逻辑单元，而不是物理单元。强制某个代码模块就是一个物理的部署单元是不合适的。另外，鲍勃大叔在介绍架构边界时，也表明了一样的观点：架构的边界并不是服务的边界。

解读REP原则

我按照自己的思路解释过REP、CCP和CRP原则[^1]之后，讨论的焦点很快聚集到REP原则的解读和实践意义上。

吴大师认为REP原则如果简单解读成没有发布过程就不能复用，它就和CCP、CRP原则的排斥力量不均衡，无法形成稳定的三角关系，那么这个张力图就显得有点鸡肋。

尚奇受到CAP（分布式系统基本原理，一致性，可用性和分区容错性）原则的启发提出了另一个解读方向。他说，CAP原则在分布式系统的实践里，都会先站住P原则，然后在C和A中权衡。那么在REP、CCP和CRP三角关系里，REP原则就相当于这里的P原则，必须先满足然后再去取舍CCP和CRP。

大魔头理解REP的意思是可复用性就是组件是独立可复用的。假如回到没有Maven这些工具，没有依赖管理的年代，如果我们所依赖的包还依赖其它第三方包，那么这个包就不能叫做独立可复用。

21:13:04 From YangYun : 我倒是理解REP的意思是你发布出来的一个可重用的包就是独立可重用的，你不能让我必须带着别的jar包才能用它。
21:14:04 From YangYun : The granule of reuse is the granule of release

他接着说，假如有两个提供同样功能的包，其中一个没有第三方的依赖，而另一个有，那我当然选择前者。

技术教练Sara举出了一个相对复杂但是很有启发性的例子。

21:46:35 From Qian Ping : 假设项目包含sub module ABC
 - 如果ABC单纯sub module没有打成jar，又互相直接复用了，就是违反了REP
 - 如果每个sub module，打成jar，互相复用的时候是通过对方特定版本的jar（如snapshot版本），就是符合REP
 - 如果符合REP了，而所有sub module是跟随整个项目一起升级版本，就是符合CCP因为他们是一体一起发布的
 - 这时假如A依赖B和C，我这次单纯想改C，他们一起升版本了。但其实B的Jar完全没有变化，这个对B来说就是一个不必要的发布，B又貌似应该分离出去，但如果它分离出去了，就又离REP和CCP远了

对于最后一句的表述，她澄清道：

之前有遇到一个情况，比如组件A，然后它里面需要用到一个common library, lib里面其实包含了比如3个sub module（1/2/3），全部都是A需要复用的, 这时候如果要改1/2/3里面任意的东西，都会一起升级lib，然后在A里面对应升级版本。

后来，有一些新组件B，它只需要用到common lib里面的3，不需要1/2，于是3一直被改和打包版本。 此时1/2会跟着升版本号，但其实1/2内容本身是完全没有变化的，只是版本号升了。

这个场景中引入了两个组件A和B分别依赖common library的某些模块。在我们讨论一个组件依赖时，面临的约束要简单很多，但是复用的初衷就是给多个组件去依赖，所以这个假设是很有价值。

Sara分析的思路如下：

如果分离出去，等于我有两个common lib（1/2 和 3）, 对于B来说，B只需要3这么一个lib是比较完美的，反正改了3再改B就好了。

但对于A来说，它就需要同时升级1/2的lib和3的lib，等于要3个发布，而它原来只需要2个发布（1/2/3 + A），所以离CRP远了，同时它也要分别维护两个lib分别的版本升级，所以CCP也比原来差了。

在她的分析下，我们发现CRP和CCP不单是互相排斥的，还有可能两者都无法满足。造成这种结果的原因在于1/2/3模块形成的这个common library对于A组件而言都符合CCP和CRP原则，但是对于B组件而言，是不满足REP和CRP原则的，因为每次想要依赖3模块，就得全部依赖1/2/3整个common library（复用困难）。反之，如果我们将3从1/2/3中拆出来成为独立的组件，那就几乎宣告对于A组件而言势必违反CCP和CRP原则，但是B组件却获得了符合REP和CRP原则的好处。

她接着补充道：

其实后来说起对应微服务的时候有另外一个想法，就是比如说我系统里面多个组件需要用计提（Mark to market[^2]）这么一个功能，说白了就是一条公式，那通常可以有几个做法

• 直接把这个公式复制到要用的组件，code level的复用，没有版本 -> REP bad, CCP bad, but CRP not bad (因为要更改时候发布次数还是一样的）
• 把公式写到一个common lib里面再进行复用 -> REP good, CCP good, CRP bad(多发布一次）
• 把公式放在一个独立service -> REP good, CCP bad(因为要维护多一个服务）, CRP good

这个观点就上升到不同层次的复用性上，可以算是对组件聚合原则的普适性的探索。

当话题再次被聚焦到复用性时，技术教练MoMo提出一个观点：我们现在讨论就是可复用组件应该遵循的原则，而REP是对复用粒度的定义。至于那些那些常年采用SNAPSHOT（Java项目里Maven常用的开发版本号），没有发布概念的组件，就不该纳入复用的考虑范围内，那些也就不是REP的反模式。

与此同时，阎王指出了一个翻译上的失误。组件粘合张力图中REP原则的简短描述是“为复用性而组合”，而原文其实是”Group for reusers”，翻译过来应该是为了复用者而组合，复用性的英文是 Reusability。所以为了复用者发布，考虑的就是对外部的承诺。

外部资料

大魔头在加班写方案和讨论的间隙，快速查阅了一些资料，比如wiki上对于REP原则的定义：

21:45:05 From YangYun : Reuse-release Equivalence Principle (REP)
REP essentially means that the package must be created with reusable classes – “Either all of the classes inside the package are reusable, or none of them are”. The classes must also be of the same family. Classes that are unrelated to the purpose of the package should not be included. A package constructed as a family of reusable classes tends to be most useful and reusable. - wiki百科里

在wiki的定义里，可以看到REP原则包含CRP和CCP原则的成分，如此看来，这三大原则并不符合MCME分类原则，就连鲍勃大叔在书中也是模棱两可的态度——REP维护共同的大主题，组件中的类和模块也必须紧密相关，这基本是CCP和CRP的简版描述。

然后大魔头查找到“粒度”这个词在软件设计中详细定义，这是对REP原则定义（软件复用的最小粒度等同于其发布的最小粒度）的分解和再认知。

21:57:03 From YangYun : http://condor.depaul.edu/dmumaugh/OOT/Design-Principles/granularity.pdf

21:58:29 From YangYun : https://fi.ort.edu.uy/innovaportal/file/2032/1/design_principles.pdf

这些观点和学术建议很有代表性，值得大家反复揣摩和思考。

反模式

软件工程师一般有个“正难则反”的习惯。原则较抽象，但是模式很具体，反模式更能指导实践。接下来，大家开始讨论哪些是违反了REP原则的反模式。

首当其冲的就是git submodule，在某些项目中，这种通过源代码划分模块并共享的方式还是挺常见的。因为共享的是代码，所以每次共享代码更新，势必要让依赖方重新编译，发布和部署。这种做法对于复用是痛苦的。

其次是常年使用SNAPSHOT版本的某些项目。这些项目的特点一般都是某个产品团队底下，内部团队之间有复用的要求。缺点其实也很明显，常年SNAPSHOT等于没有版本和发布的流程。使用者并不知道SNAPSHOT中哪些是稳定的，哪些是修改的，拿到的版本到底是最新的还是遗留的，我需要的功能在这个功能有包含，还是你包含了太多我不需要的升级。这种也是复用痛苦的。

REP原则小结

综合以上两个例子以及其它讨论，我们得出了一个好玩的结论：软件工程发展到现在，REP原则已经是基本的要求，它的存在有可能是鲍勃大叔年代感老了的体现。

[^1]: 架构整洁之道导读（二）组件聚合 
[^2]: Mark to market 按市值计价

[1] 架构整洁之道导读（一）编程范式
[2] 架构整洁之道导读（二）组件聚合
于 2018-11-12

组件聚合

组件的定义

组件是软件部署的最小单元，是整个软件系统在部署过程中可以独立完成部署的最小实体。比如，对于Java应用程序而言，Jar包就是组件；Ruby中的组件则是Gem文件；Python中的Egg或Wheel文件以及.Net下的DLL文件。

上回我们说到，编程范式的本质是约束。子过程、类或函数是我们编程过程中的基本元素，所以说编程范式是程序的基础构件。如果将这些基本构件比作建筑里的泥沙石，那么程序中的组件就可以类比成砖头。砖头的工艺注重材料配比，组件也是如此，恰如其分的基础构件配比是组件稳定的基础。组件的内容配比较难定量，但是在实践上，仍然受到指导原则的约束。

软件工程中的约束三角

在软件工程中，我们会看到很多约束条件都能由三角形的方式体现出来。这是因为三角形除了具有稳定的特性以外，还能体现出一种张力。

比如在敏捷项目管理中，我们常会听到时间，资源和成本的约束三角；在分布式计算中，著名的CAP（一致性，可用性和分区容错性）原理也是如此；还有区块链中的不可能三角（性能，安全和去中心化）。这些三角都在反映一种现实中的约束——因为不能全部同时满足，所以需要权衡。

组件聚合张力图

组件的内容配比，最终反映在组件的实践上就是基本构件的拆与合。鲍勃大叔给出了三个拆合的指导原则：REP（复用/发布等同原则），CCP（共同闭包原则）和CRP（共同复用原则）。

1. REP（复用/发布等同原则）：软件复用的最小粒度应该等同于其发布的最小粒度（注：只有那些通过版本追踪系统发布的组件才能被高效地复用）
2. CCP（共同闭包原则）：将同时修改，目的相同的类放到同一个组件；不会同时修改，目的不同的类放到不同的组件
3. CRP（共同复用原则）：不要强迫一个组件的用户依赖他们不需要的东西

这些原则乍看上去是全新的理念，细细品来又好像“新瓶装旧酒”的老把戏。CCP不就是SRP（单一职能原则）？CRP不就是ISP（接口隔离原则）？REP，等等，这个原则不言自明地像个公理呀！难怪有些架构师朋友说，鲍勃大叔老了，又拿着SOLID那一套概念出来忽悠骗钱。

其实，不妨换个思路想想，通常当谈论SOLID、高内聚低耦合、稳定依赖、稳定抽象系列原则的时候，我们是处于软件系统生命周期的哪一环？不出意外，大家都是从编写源代码，即开发（Development）的角度出发的。但是，我们又清晰地了解，软件系统的生命周期其实还包含除开发之外的部署、发布，运行和维护环节。那么问题来了，在这些环节里，哪些指导原则是适用的呢？

在跳脱了开发的思维桎梏之后，我们通过两种手段分析下这三条原则。

分开看

REP原则阐述了一个简单的道理：软件复用是基本要求。在追求软件复用的过程中，逐步形成了标准的发布流程，如：版本号（语义化版本），发布时间，变更内容等。这要求组件中所包含的模块和类都必须同时可发布，而可发布的深层含义既是对用户的承诺，也是对作者的约束。组件是否向后兼容？是否包含破坏性的变更？升级的注意事项？

CCP原则是指尽量把变更频率相同的模块和类放到同一个组件当中。这样做的好处是，当相关功能更新时，我们可以把源代码的变更局限在某一个组件当中，而不需要横跨多个组件，从而减少了部署，验证和发布的次数。概括来说，这是局部化影响的优势。CCP和OCP（开闭原则）中强调的“闭包”也有关联，所谓封装可变因素就是形成闭包的过程，CCP要求将同一时间变更的点聚合起来，达到闭包的效果。

CRP原则是说组件和组件之间的依赖应该达成一种默契——如果不需要完全使用某个组件中所有的模块和类，那么就不要依赖它。这看上去不太可能，但是有一点意义，它指导我们：不是紧密相连的模块和类不应该被放到同一个组件里。因为我们知道一旦某个组件变更升级之后，依赖它的组件往往也会被动的变更升级，即便是和自己那些无关的变更也是如此。而每次变更都意味着重新编译，部署验证和发布。

合起看

REP原则说明软件复用是基础，复用是通过发布流程规范的。在复用和发布的上下文中，CCP原则为了便于后期维护，需要尽可能地将变更频率相同的模块和类放到相同的复用单元——组件中；CRP原则为了避免频繁发布，应该将每个组件分割的足够小，减少无关变更导致依赖链条的连锁发布反应。

如果我们只兼顾REP和CCP原则，那么就可能由于连锁发布反应，出现很多不必要的发布；如果只兼顾REP和CRP原则，那么就可能因为实现一个功能需要横跨多个组件修改，造成过多的组件变更；如果只兼顾CCP和CRP，那我们可能就忘记了复用这档子事儿，这在先前我们批判鲍勃大叔的时候已经体现出来了。

小结

软件系统的生命周期里处处充斥着约束条件，每多一个环节往往就会多一种矛盾，进而衍生出多个方向的约束。组件聚合张力图反映的是发布和开发之间的矛盾，需要尽量遵循REP，CCP和CRP原则，满足其约束，才能减少变更成本。

组件构建过程中，除了聚合原则，还有耦合原则——描述的是组件的依赖关系。聚合原则告诉我们的是软件系统中的最小元素，耦合原则说的是元素之间的关系，当这两者和系统的功能结合到一起，就构成一个运行着的系统^1。系统是逐渐演化出来，即便我们熟知REP，CCP和CRP原则，也没有办法说，在系统构建之初，遵循这些原则就能画出完美的组件结构图。这便是“自顶而下”的设计不靠谱的基本解释。

“自顶而下”的设计不靠谱还有更深层次的原因。本书的第14章“组件耦合”会有答案，且听下回分解。

[1] 架构整洁之道导读（一）编程范式
[2] 架构整洁之道导读（二）续 组件聚合张力图
于2018-10-28

我是《架构整洁之道》(Clean Architecture) 中文版的技术审校者，在审校的过程当中略有感悟，所以希望通过撰写导读的方式分享给大家。

书名的由来

《架构整洁之道》是Clean Architecture的中文译名。看似简单地延续了《代码整洁之道》(Clean Code)的翻译传统，但事实上，对于取中文名字这件事，我们还是花了不少气力的。拿到译文初稿时，编辑提供了几个备选的译名：《架构简洁之道》，《架构至洁》和《Clean Architecture》，这些名字各有各的考量，在没有了解这本书的核心思想之前，我也没有办法给出恰当的判断。所以在通读了原作和译作之后，我在ThoughtWorks咨询群里发起提案，讨论的过程很精彩，最终在骨灰级架构师新哥的建议下，结果大致趋向了整洁架构。

新哥说：“整本书在说依赖治理（管理），也就是如果降低依赖复杂度，和DDD中分离子域分层架构等想法是一致的；如同你整理你的房间，把东西分门别类放好，从这个角度，整齐比简单更合适，或者清晰也可。”

除此之外，对于《架构至洁》这个候选项，大魔头的态度是不要至洁，总感觉脏脏的。言下之意，自行体会。而读MBA的岳岳和XR（XR说他没读过MBA）从用户思维出发，认为《代码整洁之道》和《架构整洁之道》可以相互增强记忆，更容易激发用户的购买行为。

即便敲定了“整洁架构”，大家对“之道”也有不同的看法。《代码整洁之道》对应的原标题和副标题分别是Clean Code - A handbook of Agile Software Craftsmanship，而《架构整洁之道》对应的原标题和副标题分别是Clean Architecture - A Craftsman’s Guide to Software Structure and Design。我们知道“道”是一种形而上的精神层面，老实讲，把Craftsman（手艺人）译做“道”是有点夸张的。

形而上是精神方面的宏观范畴，用抽象（理性）思维，形而上者道理，起于学，行于理，止于道，故有形而上者谓之道；形而下是物质方面的微观范畴，用具体（感性）思维，形而下者器物，起于教，行于法，止于术，故有形而下者谓之器。

道法术器择其一？其实凡事总有权衡，遵循前人的译法往往不会太坏。就像鲍勃大叔书中总结的稳定依赖原则，当我们依赖一种译法次数越多，它就更加稳定，这种稳定先不说能否形成品牌效应，单是SEO就能省去不少功夫，那么何乐而不为呢？

鲍勃大叔的文字平铺直叙、浅显易懂，尤其喜欢用他自己生活中的经验做例子。而且这本书是没有知识断层的，即便是初级程序员，也能在鲍勃大叔的循循善诱下，完成对软件架构认知的转变。因为他总是从最基础的知识点切入，自下而上，一步步地搭起架构的形状。

范式的实质是约束

编程范式是程序员喜闻乐见的话题，就像Vim和Emacs编辑器地位的旷日之争。它们的沉浮过往俨然就是风云诡谲的江湖。结构化编程英雄迟暮逐渐淡出程序员的视野，觊觎已久的面向对象编程（OOP）以迅雷之势称霸武林，独居一隅的函数式编程（FP）隐忍多年终于等来了一次机会。2012-2014年，江湖唱衰OOP的声音不绝于耳，FP就像一名拯救程序员于水火的侠士想要撼动这片天地。硝烟过后，眼前却不是你死我亡的惨状，而是你中有我、我中有你的大团圆结局。当Java这位OOP的保守党融汇了FP的特性lambda表达式，这场范式的冲突之争也算落下了帷幕。

程序员谈编程范式，喜欢党同伐异，作为FP的拥趸，我也不例外。可是鲍勃大叔却娓娓道来，所谓编程范式不过是约束程序的执行，告诉我们什么不能做而已。

1. 结构化编程是对程序控制权的直接转移的规范和限制
2. 面向对象编程是对程序控制权的间接转移的规范和限制
3. 函数式编程是对程序赋值操作的规范和限制

Goto considered harmful

学习C语言编程的第一天，老师就告诉我们不要在程序中使用goto语句，因为goto会破坏程序的结构化。Dijkstra在论文Go To Statement Considered Harmful中证明了goto语句阻止了将大程序递归分解成更小的可证明的单元，这意味着大量使用goto语句的程序是不能被证明的。这里，不能被证明的语义是不可判定，类似说谎者悖论——“我在说谎”这句话不能被证明和证伪，所以不用goto其实是在保证小的程序单元可判定。可惜的是，Dijkstra并没有证明程序单元，这项工作被科学方法——测试取代了。在保证程序单元可判定的前提下，测试是一种可以对其可证伪的科学方法。命题“天下乌鸦一般黑”就是可以证伪的，我们不可能枚举天下所有的乌鸦，等到哪天找到了一只白乌鸦，我们就可以说这个命题是错误的，这就是证伪。Dijkstra说的“测试只能说明bug存在，而不能证明不存在。”是同样的道理。

测试可以保证，在当前已知情况下，程序单元是正确的。一旦有新的测试用例导致程序单元出错，那么我们就可以修正程序，让程序更加接近真相。这或许就是TDD（测试驱动开发）的妙处所在吧。

去除了goto语句之后，我们发现具备顺序，循环和分支判断能力的计算过程还是图灵完备的，也就是说goto的有无并不会影响计算能力。那么goto的在程序中的作用便是弊大于利的。再加上goto的滥用会导致程序结构容易混乱，不利于程序员理解，这更得尽力避免。所以结构化编程限制了对程序直接转移的控制权。

Pointer considered harmful

人人都知道面向对象编程有三大特征：封装，继承和多态。

封装是为了构造抽象屏障（Abstract Barrier），到达隐藏信息的目的。任何编程范式都不会缺少封装，因为这是人的需求，是人类简化问题认知的方式。

继承是一种函数（过程或者API）复用的方式，以前我们想在多个结构相似的数据上使用同样的函数，需要通过强制转换到函数可接收的数据类型（结构体指针）上，这必然存在风险。面向对象的世界里，我们不再需要手动强制转换，只要通过显式地表明继承关系，编程语言就能在运行时自动做到这点。

多态（polymorphism）是一种将不同的特殊行为和单个泛化记号相关联的能力，和多态概念对应的参考实现——运行哪段代码的决策叫做分派，大部分分派基于类型，也可以基于方法参数的个数及其类型，而分派的具体执行过程则仰仗函数指针。当作为单个泛化记号的函数被声明出来，它的具体实现可以多样化。通过这样的记号，事实上，我们解耦声明和实现，而这种解耦的过程恰恰是通过函数指针间接地找到目标函数完成的。所以面向对象编程限制了对程序间接转移的控制权。

Mutability considered harmful

Neal Ford在《函数式编程思想》（Functional Thinking）中提到面向对象编程是通过封装可变因素控制复杂性（makes code understandable），而函数式编程是通过消除可变因素控制复杂性的。函数式的一个显著的特点就是不可变性。不可变性意味着更多的内存消耗，更差的性能？其实不尽然。像Scala，Clojure这些基于JVM上的函数式编程语言大量使用了持久化结构（如：Persistent Vector，见脚注1)，在不损失效率的前提下，实现了不可变的数据结构。这样的数据结构在高并发的环境下具有非常巨大的优势，尤其相对于面向对象编程中为人所诟病的临界区和竞态条件。

不可变的数据结构是无法重复赋值的，所以函数式编程限制了对程序的赋值操作。

小结

鲍勃大叔一针见血地指出，我们过去50年学到的东西主要是——什么不应该做。这等于给全书奠定了基调。可以类比，良好的架构也在传达同样的道理。

为什么从编程范式开始谈起？在审阅完整本书之后，我慢慢发现鲍勃大叔其实在传递一种设计理念：架构设计里，自顶向下的设计往往是不靠谱的。就像本书的目录，从程序的基础构件，谈到组件，最后谈到架构，这个过程非常符合系统自组织的特征。

为什么自顶向下的设计往往不靠谱？本书的第4部分“组件构建原则”会有答案，有需要，且听下回分解。

[1] 函数式编程简介
于 2018-10-21