鄢倩

(conj clojurians me)

前言

Neal Ford 在《函数式编程思想》(Functional Thinking)中提到面向对象编程是通过封装可变因素控制复杂性(makes code understandable),而函数式编程是通过消除可变因素控制复杂性的。

封装和消除,哪种好理解?

封装是为了构造抽象屏障(Abstract Barrier),到达隐藏信息的目的。任何编程范式都不会缺少封装,因为这是人类简化理解事物的方式。只不过在面向对象编程语言中,封装、继承和多态(polymorphism)被拔到了一种必须充分理解的高度,而 Bob 在函数式设计中挑明了态度,他认为多态比其他两者高出一筹。原因在于进行高层次策略设计时,多态是调整依赖关系行之有效的方法。我认为他说得有一定道理,但是弱化封装这个性质倒和他的中心思想相背离,因为在这本书里,面向对象的封装和函数式的消除是棋逢对手的关键性质,费点笔墨解释清楚,很有必要。

Bob 大叔在第五章里列举了两段伪代码,如下。

image.png{:height 442, :width 780}

image.png

如果你看过我之前写的文章,不难理解这里发生了什么,无非用尾递归消除了 x 的赋值。在 Bob 大叔的眼中,赋值等同于可变性。所以,函数式设计的精髓就是消除可变性。

可是,除了赋值,第一段程序跟封装有什么关系呢?别急,我们稍微重构一下它。

refactor-f.png

refactor-getInput.png

refactor-getInput-f.png

Input x 是一个对象,所以我们就把所有依赖其本身的行为通通封装进它的体内,希望你能感受到封装的力量。这里面有一点洞察,面向对象尽量会把行为放进对象体内,以符合数据内聚性的需要。也因此,对象的状态会原地改变,相当于赋值。

函数式则不然,它的状态无法原地改变,也就意味着它必须以递归或管道的方式自旋或流动起来,那些状态就保持在不可变的外部数据结构当中。

所以 Bob 大叔下了个结论:在状态可变的语言中,行为流过了对象;而在函数式语言中,对象流过行为。

行为流过对象,指的是行为在对象中迭代发生;而对象流过行为则是说行为在对象外顺序发生。或者说面向对象中的赋值(状态变化)在对象里发生,而函数式中的状态变化在对象外发生。所以从做事的横向流程上看,函数式更加清爽明了。而纵向结构上,面向对象则更加边界清晰,粒度合适。究其原因,函数式是一种“以终为始”的思考方式,其定义的每个阶段的产物都是比较完整的;而面向对象则是子问题划分,在子问题中寻求差异化解决方案。

函数式编程的过程与结构

函数式编程是一种管道式的编程风格,Bob 大叔说它更像是铺设和修改数据流的管道,管道中的每道工序更像是包含尾递归的状态转移。

image.png

如果转化成 Clojure 代码,就像是用上了 Thread 宏的管道风格。

image.png

数据起源于物理世界,从一头流向另一头,最后汇入到有副作用的物理世界。

控制住复杂性?

没有那么简单。回到最初的原则,编程范式是对编程方式的规范和约束,而方法的孰优孰劣取决于问题的规模和复杂性,也取决于方法固有的复杂性。遇到非状态机(随时序变化)的问题时,两种方法差异不大;遇到状态机的问题,就要根据规模和复杂度琢磨一下。后续,我们在深入对比分析。

大家好,我是鄢倩,我是 Bob 大叔的《架构整洁之道》中文版的技术审校,也是他的扛鼎之作《敏捷软件开发:原则、模式和实践》重制版的译者。当然,再次有幸参与了大叔的新作《函数式设计》的技术审校,我非常高兴能在这里和大家分享我在审校过程中所学所想。

111724213567_.pic.jpg

FD 发布会.jpeg

有限与无限的游戏

美国哲学家詹姆斯·卡斯写过一本书《有限与无限的游戏》,向我们展示了世界上至少有两种类型的“游戏”。有限的游戏,具有明确的开始和结束,其目的在于赢得胜利;无限的游戏,没有固定的开始和结束,旨在让游戏永远进行下去。有限的游戏在边界内玩,无限的游戏玩的就是边界。

Bob 大叔在解释函数式的惰性时,翻出了那款经典的保龄球游戏。今时不同往日,他玩起了无限的游戏。

我们先把保龄球的游戏规则过目一遍,头脑中有个怎么玩的印象就好。

保龄球每个玩家每局有 10 个计分格(frame)。每个计分格玩家最多有 2 次投球(roll)机会,但第 10 个计分格最多有 3 次投球机会。每个计分格的得分,是击倒的球瓶总数,再加上全中(strike)或补中(spare)的奖励分。全中,指第一球就击倒了所有 10 个球瓶;得分为 10 分,再加上接下来的 2 次投球(属于下一个或之后的计分格)所击倒的球瓶数。补中,指在一个计分格中,用两次投球才击倒所有 10 个球瓶;得分为 10 分,再加上接下来的 1次投球(属于下一个计分格)所击倒的球瓶数。第 10 个计分格有点不同。如果在第 10 个计分格投出全中或补中,则能获得额外的投球机会来完成这个计分格;如果是全中,能获得 2 次额外投球;如果是补中,则能获得 1 次额外投球。这些额外的投球,只用于计算第 10 个计分格的得分。

BowlingGameJava.png

在上面 Java 版本的代码中,几乎是无意识地,我们把得分计算 score +=和投球的次序 frameIndex++揉到了一处。这是自然思考的结果,因为累积 frameIndex 就重现了投球的时序,得分跟着时序在规则(isStrike, isSpare?)的安排下一步步累加。但是事实上,因为不得不识别出影响每个计分格的所有投球,真正时序耦合的是 frameIndex 和当前计分格的得分计算,而不是总得分。所以,这段代码可以重构下,将总得分的计算放到了最后。

BowlingGameRefactorJava.png

重构方式很简单,新增一个 scoresInEachFrame 列表,把每一个计分格的得分加进去,最后做求和。

这样的代码几乎可以很容易地写成像下面一样 Clojure 的 loop...recur 形式。

BowlingGameRefactorClj.png

转换成这种形式之后,我们至少能知道两件事情。第一,frameIndex 这类索引让代码显得很难读;第二,frame 这是个控制量,它不参与实际的计分运算。

对于第一种坏味道,我们可以用列表的解构来解决。这里面凸显一种思想,新的列表是从旧的列表演变出来的,正如 map 函数所做的那样。

BowlingGameFramesClj.png{:height 437, :width 476}

代码中 (loop [remaining-rolls frames]...)正是这种思想的延续,在每次递归调用中,remaining-rolls 减少了,而 frames 增加了,它们之间的演化(映射)逻辑就是游戏的计分规则(Strike等)。当然,这段代码和上面的代码并不等价,原因是它没有提前计算每个计分格的得分,而是保留下所有计分格,例如在 Stirke 情况下,frame 是 [10 X Y] 这种形状。

对于第二个问题,既然不参与计分格的计算,最好是忘得越远越好。也就是说,假如我们想永远玩下去,那么这种程序最好也能正确计算出得分,直到我们想终止为止。

BowlingGameClj.png

在无限游戏的场景下,rolls 可以无限投掷,我们就可以无限地推迟从计分格中获得总分的决定。遗憾的是,保龄球游戏中有一条定胜负的终止规则,每局只有 10 个计分格,所以它不是无限游戏。在程序计算总分的最后,取出了 10 个计分格。

惰性,无限可能!

Bob 大叔分析说惰性之所以需要,是因为这样做可以把需要做的事情和需要做的量分离开来。延迟需要多少量这个决定到最终用户的手上。

惰性是实现无限游戏的手段,而无限是帮我们扫清聚焦计算(厌恶那些 indexes 吧)障碍的思维方式。试想,列表元素都无限多了,你还会思考越界吗?你只会想我该怎么这个游戏一直玩下去。

惰性列表时一个知道如何计算下一个值的对象。惰性列表是伪装成列表的迭代器。

我是 Bob 大叔的《架构整洁之道》中文版的技术审校,也是他的扛鼎之作《敏捷软件开发:原则、模式和实践》重制版的译者。当然,再次有幸参与了大叔的新作《函数式设计》的技术审校,我想谈谈过程中个人的所学所想。

浓眉大眼的 OO 叛变革命?

Bob 大叔成名已久,是面向对象编程领域当之无愧的领军人物。如今,他出一本函数式编程的书籍,我想他的多数读者应该会感到疑惑:没想到你浓眉大眼的,居然也叛变了“革命”。Bob 大叔叛变了吗?他的这本书和他之前的诸多作品文脉想通,有继承也有创新,落脚点还是实用。我用电梯演讲的方式概括了这本书的内容和优势。 对于:Bob 大叔的读者多数是面向对象编程的熟练手

一问三连,一发入魂

决定读不读一本书,最好的方式是带着疑问去检索答案。我拿到这本书,脑子中闪现的一个问题就是函数式设计是作为面向对象设计的对立面提出来的吗?当我翻开前面几页,发现 Bob 大叔居然用了 Clojure 这门 Lisp 的方言来阐述观点,不由得心头一紧,这门编程语言受众很窄,恐怕会劝退很多读者呀!写过如此之多畅销书的 Bob 大叔不会没有意识到这点,那他的目的何在?我把书从头粗粗地翻到末尾,闭目凝神,回想 2010 至 2020 年这十年间函数式编程语言红极一时又式微的过程,叠加 genAI Copilot 辅助编程的滔天巨浪,不免心有戚戚,喟然叹曰:现在再来讨论编程范式,有用吗?

FD 是作为 OOD 对立面提出来的吗?

Bob 大叔为什么要用 Clojure 语言,这种小众语言我又用不上,学了等于白学?

如果我工作中没有用到函数式编程语言,这本书是不是对我帮助就不大了?

真相只有一个!

你觉得函数式编程的本质是什么?一切皆函数(注:纯函数)。这个回答怕是贴着面向对象编程的脸喊出来的。Bob 大叔在书中就不这么说的,他的厉害之处就在于:别整这些玄乎饶舌的概念,给我上代码,拉出来溜溜,拿捏几下,我就知道你姓甚名谁,写下来,完了还给自己的前一本书压个韵。

Bob 大叔在《架构整洁之道》中提出了编程范式的真相 —— 约束程序的执行,告诉我们不能做什么。

为什么要对程序的赋值操作做限制呢?原因在于赋值带来程序的时序耦合,显然时序耦合是让程序复杂(难懂)的诱因之一。我们看看一段计算前十个整数的平方和的 Java 程序,这段程序中包含了两个变量并且都有赋值。仔细看这三段注释的 log 函数,其中第二个记录的 sum 和 i 并不是这轮循环的最终状态(sum累加之后,i 必须自增)。具体来说,调用 sumFirstTenSquareHelper(0, 1),正确的 [sum, i] 状态对是 [0, 1], [1, 2], [5, 3] … [385, 11],但是第二处记录却是错误的状态对,如 [1, 1]。也就是说,赋值的操作给了时间顺序这个坏蛋以可乘之机,让本应是原子化的变量状态出现不一致。假设放到更加混乱的多线程环境中,这段程序时不时会出现错误,这也被称为竞态条件。竞态条件是指多个线程在访问共享资源时,其执行顺序可能导致结果的不确定性或错误。

sumFirstTenSquareHelperJava.png

既然赋值或称对变量的改变是时序耦合的罪魁祸首,那么明智的做法自然是干掉它。我们解析下赋值的目标是什么?没错,状态的变化。完成状态的变化,通常有两种做法。第一种简单粗暴,用新的直接干掉旧的,让旧的消失于无形,俗称破坏性创新。第二种优雅得多,符合重构(refactoring)十六字心法“旧的不变,新的创建,一键切换,旧的再见”。前者是赋值,后者是替换。说白了,替换不是抹去前任痕迹,而是让旧的依然如故,以旧换新而已。

那么到底该怎么做呢?函数式编程中有两大武器,可以实现以旧换新的便宜操作。第一件是递归函数调用(recursive function call),第二件是持久性数据(persistent data)。我们知道,递归函数调用如果未到达递归出口(一般是 if 条件),那么它的栈桢就会不断累积下去,每一层栈桢都可以看作是一次以旧换新;而持久性数据是一种支持多版本的数据结构,它会尽可能地共享数据结构来避免以旧换新时数据的完全拷贝,毕竟,完全拷贝听上去就很浪费。

我们看看用 Java 程序用这两大武器实现赋值消失术。利用递归,将赋值转换成算出新值,然后作为参数传递给递归函数。因为此处的参数仅是原生类型,对于复合类型,持久性数据的威力才会发挥出来。

sumFirstTenSquareHelperJava-Recursive.png

如此看来,我们已经完成了赋值的历史终结任务,但令人不安的是天边似乎还有一朵乌云——递归的代价。我们用 Clojure 同样实现一遍上面的简短程序。然后用 cider-toggle-trace-ns(如果你用 Emacs + Cider 写 Clojure 的话,顺便说一句,有兴趣的人足够多,那我会分享自己的 Emacs + Cider 配置),一旦调用该函数,就会有深深的调用栈出现。递归会让函数 call 栈桢增长,导致栈溢出。

sum-first-ten-squares-helper-clj.png

sumFirstTenSquareHelper-CljRecursive.png

递归有代价,尾递归来优化。我们把上面的程序略作修改,把内部的函数调用名改成 recur,重新求值,再来观察一下调用栈。你会惊喜地发现,深深的栈不见了,尾递归优化(TCO)复用了栈桢,以此达到了循环的目的。所以,你会在这本书的多数程序中发现这样的结构 (loop...recur)

sum-first-ten-squares-helper-tco-clj.png

sum-first-ten-squares-helper-tco-stack-clj.png

我们用两段伪代码来通观下刚刚到底发生了什么事情。对,我们用尾递归去掉了循环赋值。我们回过头来看看。 尾递归看上去很复杂,但其实很简单。上面程序展示了过程式代码改造成函数式尾递归的过程,其中最大的差异点就是消除了变量的赋值。 其实,搞了这么多新奇的手法,又是尾递归优化又是持久性数据,那都是因为计算机的开山老祖是图灵的图灵机而不是阿隆佐·邱奇的 lambda 演算,我们一直在用图灵机的实现模拟 lambda 演算。所以,总结下来就是持久性数据 (persistent data) 在递归参数中的复制以代替赋值,用 TCO 减少栈桢增长。

state-updates-java.png

state-updates-fp.png

loop-recur-clj.png

归根结底,函数式编程遵循一个朴素的原则,追求不变性。甚至可以说,函数式设计的本质就是拿捏不变性。其余的绝妙功法,我们后续再聊。

姚期智的百万富翁问题

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

前言

技术塑造了我们现在的生活,那么又是什么在塑造技术自身呢?很多人会联想到程序员在其中起到的作用。但是,如果我们把人从技术的整体里分离出来,去探究技术内生的秩序或规律,或许答案就不那么直观了。而且从长远来看,这种方法比争论是人主导技术还是技术主导人更能增强个体的主体意识,因为排除个性的技术能帮我们避免陷入权威和神性的陷阱。

什么是技术

在谈论什么塑造了技术之前,我们不得不回答一个前置问题:技术是什么?布兰恩·阿瑟的《技术的本质》中给出了一个我认为比较合理的定义。

  1. 技术都是由已有的系统组件组合而成的
  2. 技术的每个组件自身也是微缩的技术
  3. 所有的技术都会利用或开发某种效应

第一点,技术是由已有的系统组件组合而成的,这话不难理解,我们做软件项目也会引用很多外部组件。那么组件又是什么呢?所以他紧接着给出了第二点解释,技术的每个组件自身也是微缩的技术。这才是该定义最有趣的地方——递归解释。我们知道凡是递归总得有个出口,所以他最后给出了第三点解释,所有的技术都会利用或开发某种效应。也就是说,每一个技术都能发挥某种功能。

听完这番解释,是否有一种不明觉厉,又有一种听君一席话如听一席话的感觉?是的话,咱也先别急着否定。看看下面的这张图,它是著名的计算机科学的入门书《计算机程序的构造和解释》,简称SICP,关于解释器工作原理的图示。解释器就是利用 Eval 和 Apply 两个函数相互递归解释的。在软件的世界里,类似的例子还有很多。例如,编译器实现自举——利用老的语言写新的编译器,再用新的编译器编译出新的语言。

Eval_Apply

如果从软件的规模这个角度来考察这个定义,我们就会发现软件可以无限庞大下去。基于这样的假设,我们可以推论出软件并不是一种物理现象。1972年,荷兰计算机科学家迪杰斯特拉(Edsger W. Dijkstra)将软件描述为“分层系统”,因为我们需要用分层来解释和实现我们所构造的现象,而不是经由物理规律来考验这些现象。所以 SICP 一书中将软件称为“程序认知论”(阿贝尔森和萨斯曼)就非常有道理了。

软件工程师常常把分层系统看做是解决某些复杂软件问题的良药,然而事实上,软件其实就是分层系统,基于 OSI(Open System Interconnection) 模型的技术栈就是一种典型的例子。在 OSI 出现之前,曾经有项目尝试适配各种主机以完成各种异构网络之间的联通,但是均以失败告终。而 OSI 引领的标准让世界各地的工程师们协作起来逐步推进了网络技术栈的发展。现如今,我们操作图片时,已经完全无法想象它和比特之间的关联,因为它们已经相差得太远了。远到我们无需考虑有比特这么回事,更不用说底层的半导体控制的电流开关。

技术革命结构里的危机

1962年,美国著名科学哲学家库恩在《科学革命的结构》提到是范式危机引发了科学革命,例如海森堡的测不准原理对物理学的冲击,在经典物理学无法解释微观现象时科学革命发生了。我们承认自工业革命以来,技术发生了巨大的变化。如果假定技术的发展也存在范式革命,那么其中的危机是什么呢?爱德华·阿什福德·李的《柏拉图与技术呆子》一书给出了两点总结,他认为软件日益增加的复杂性和意想不到的功能是技术革命中的危险和机遇。

复杂性体现在以前可以工作良好的工具和模型,在更复杂的情况下,不能很好地工作,甚至崩溃。比如应付几十人并发的系统在面对上万人的并发时很容易就崩溃了。另一个表现则是项目失败的可能性增加了。比如,用瀑布过程开发大型系统,这种管理复杂性的方式会导致在需求设计阶段的异想天开,更可能招致错误和失败。

至于意想不到的功能,就是想常人不敢想、做常人不敢做的事情。2007年,苹果公司推出的苹果手机。它的创新性在于突破了手机是用来打电话的惯性思维,原来手机可以当电脑使用,反而原来打电话的功能才是附加功能。事实上,苹果手机最具革命性的一点是引入了应用程序的开发平台,这就让全球数百万富有创造力的程序员能够为苹果手机开发各种应用程序。程序员、苹果公司的应用商店和用户就形成了良性的服务网络,从此开启了移动互联网的时代。与苹果手机相近的创新就要数区块链网络了。它的意想不到之处在于货币居然可以由个人发行。区块链网络自带生态快速形成了以开发者、投资(ji)者和矿(Miner)工为一体的服务网络。

危机是技术革命结构重要的组成部分,但是如何清晰、准确和精准地界定危机依然是个麻烦的问题。当事物发展到复杂难懂的地步时,我们应当回到最初的基本假设上重新思考,这个过程也被称为第一性原理思维。在信息技术的历史学脉络中,我们能迅速地把握到几个关键的定律。

首先是摩尔定律。1965年,八叛徒之一、英特尔的联合创始人戈登、摩尔做出一个著名的预测,集成电路中的元件的数量将在未来每18个月翻一番。这一定律就一直是半导体行业的指导原则,而且延续至今。不过,大家有没有思考过一个问题,那就是既然摩尔定律一直起作用,那么要么硬件逐渐便宜下去,我们怎么还没有实现硬件自由呢?

因此,我们不得不提到另一个安迪-比尔定律。这个定律的原话是安迪所给的,比尔全都拿走。其中的安迪就是今天全球最大的个人计算机零件和CPU制造商英特尔公司的创始人兼当时的 CEO 安迪·格鲁夫,而比尔就是比尔盖茨。这条定律的意思是微软等软件公司的新软件总是比从前的软件更加耗费资源,以至于完全抵消了英特尔等硬件公司带来的性能提升。我们的切身体验也是,你拿着老旧的手机去运行现在的软件会感觉慢得不要不要的。

摩尔定律和安迪-比尔定律带来的最直接影响就是在产业上规定了技术的发展会越来越复杂。

另一个比较关键的定律就是梅特卡夫定律。 1980年,3com公司的联合创始人罗伯特·梅特卡夫提出一个现在被称为梅特卡夫的定律,该定律认为,网络的价值与网络上兼容的通信设备的数量的平方成正比。如果单台设备的价格为1块钱,那么一个连接10台设备的网络的价值就是 100 块,100台就是1w块,以此类推。

梅特卡夫定律在经济层面上肯定了网络的规模效应,互联网或区块链行业都是这一定律的实践者。

技术发展的 Z 字模型

如图所示。Z 字模型,其上层是技术革命的危与机,下层是技术发展的基本定律,而中间这条线就是从基础规律寻求技术革命的攀爬梯。如果把技术发展比作修仙小说,底下三条定律就是筑基,上面那条线就是羽化成仙,也就是凡人的终极目标。

在 Z 字模型中,危机并不是一蹴而就的,虽然三条基本定律告诉我们危机迟早会发生,但是依然需要做很多的工作,而这些工作都是由工程师完成的。

工程师们的日常工作到底是什么呢?我知道有人会说写代码,但更为清晰的描述是《技术的本质》中的标准工程:

标准执行一个新项目时,在已知可接受的原则下聚集方法和设备的过程,是对已有技术的新的计划、试制和集成过程。

这个描述比较拗口,我实例化一下。以敏捷软件工程为例,我们在执行一个新项目时,在时间、资源和成本的约束原则之下,通过 Discovery、Inception 等方法快速识别问题并启动项目,购买云服务资源,整备环境,管理和配置持续集成服务器,使用 DDD 建模,TDD 持续交付可工作的软件。整个过程中,我们会评估和选择满足功能及跨功能需求依赖的技术组件,试验和探究新的技术组件,并且集成遗留的系统、多个代码分支、多套测试和发布环境。

根据康威定律,当项目较大时,标准工程就演变成了一种企业组织形式,此时项目的成败会更加依赖围绕其周遭的利益关系网:技术团队、业务部门、财务预算、部门领导以及其他利益相关者。

总而言之,技术发展要求工程师处理的事务更加多元化,也更加复杂。优秀的工程师是什么样的呢?这就不得不提《浪潮之巅》的作者吴军划分出的工程师的五个等级说。

工程师的五个等级

Pyramid Of Engineers

吴军借鉴了前苏联著名物理学家朗道提出来的朗道等级。朗道曾经根据物理学家的贡献把他们分成了五级,每一级之间的贡献相差一个数量级。对于工程师,也可以做同样的划分。

  1. 第五等工程师,能够独立设计和实现一项功能的人。如果需要别人告诉他怎么做,最多算是助理工程师或者技工,不在工程师之列。
  2. 第四等工程师,需要产品头脑,也就是说他们在做一件事之前,要知道所做出来的东西是否有用、易用,是否便于维护,是否性能稳定,等等。除了要具备产品设计方面的基本知识,还要具有一定的领导才能,能在整个产品的生命周期从头到尾讲一个产品负责到底。
  3. 第三等工程师,可以做出行业里最好的产品。他们与第四等工程师有着质的差别,这不仅反映在技术水平、对市场的了解、对用户心理的了解以及组织能力等诸多方面,而且也反映在悟性的差异上。
  4. 第二等工程师,是那些可以给世界带来惊喜的人。比如:第一台实用化个人电脑的实现者沃兹尼亚克,他们和第三四五等工程师的差别在于其工作的原创性以及对世界的影响力。不过,他们的工作不同于科学研究。
  5. 第一等工程师,是开创一个全新行业的人,历史上有爱迪生、特斯拉、福特,二战后有保时捷(Ferdinand Porsche,1875-1951)博士,本田宗一郎(1906-1991)和硅谷的诺伊斯等人。这些工程师不仅在技术和产品等各个方向上与第二等的工程师有了质的差别,而且在经验和管理上也是好手,他们通常是企业家,并通过自己的产品改变了世界。

从这个等级阶梯上,我们看得出来,成为拔尖的工程师有多难。每个等级的工程师之间的差距是数十倍的。好的企业想要获得第二等甚至第一等的工程师,就需要一个由工程师构建的完整金字塔:要想出几个第一等的工程师,就需要有足够数量的第二等工程师,以此类推。

技术的助产婆

苏格拉底曾经说过“我是思想的助产婆”,他说的是自己能够通过苏格拉底似的提问引发别人积极思考。那么,工程师们则可以理直气壮地说“我们是技术的助产婆”,工程师必须学会迎接软件复杂性的挑战,坚定地不放过任何细小的机遇荡起的涟漪。在标准工程的日常工作中,一脚把新生的技术踹出去。

所以,自信点,我们工程师的使命无上光荣。

  • 缘起
  • 实践出真知
    • 快速获取
    • 澄清概念
      • 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方法。那么集合如何拼接呢?为了解答这个问题,我一般会用搜索引擎,或者深入文档,查找如 concatappend等关键字,每每总有收获。

在不考虑非功能需求的前提下,我们先用最直接的方式实现,例如:文档中给出的样例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)一个不可变的变量。borrowmutable都是新的概念。对于新的概念,我们会习惯地用熟知的知识去类比。如果套用函数式编程中不可变的特性,大体可以猜到 Rust 中的变量默认是不可变的。但是 cannot borrow as mutableborrow 确实是有点超出认知范围。那么此时弄清定义是非常有必要的。

澄清概念

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

在学习(尝试定义)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方法并提供默认值:字符串"."。为什么要提供默认值呢?这和OsStrStr的转换密切相关,当我们传入参数"."时,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去递归构建。经过treechildren两个函数的交替递归,内存中的一棵目录树就被构建出来了。

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

  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命令就能展示很多有用信息。

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

我一般拿从零到写出第一行程序的时间作为上手快慢的标准。这行程序是用来试验,未必得手写,所以我选用了truffle自带的样例MetaCoin.solConvertLib.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验证这次合约调用的真实数据流转情况。

Explorer & 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)的方式访问这个静态网站了。

IPFS distribution of static pages

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组成的关系表格填充如下:

ENT CS MS
128 4 12

初始熵 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对都是从同一个根派生出来的,所以只要妥善保管好根(主密钥)就可以在其它的系统中快速地恢复钱包。

层级结构和确定性如下图示:
HD Wallets

主要概念

  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
0%