【技术贴】从拜占庭问题,谈区块链技术实现及政务应用

本文,作者首先介绍了拜占庭问题和口头消息算法;其次,详细讨论以HyperLedger1.0为基础的系统架构和数据库事务处理流程,并分析该架构与传统中心化数据库的主要区别;最后,以南京政务网建设为例子阐述区块链技术的具体应用。

作者 | 丁艺明

拜占庭问题

探究区块链其源头,我们不得不追溯到“拜占庭将军问题”。它是整个区块链技术核心思想的真正根源,也直接决定了区块链技术的种种与众不同的颠覆性特质。

在2013年获得计算机科学领域最高奖项图灵奖的31年前,莱斯利·兰伯特(Leslie Lamport)加入斯坦福国际研究院(SRI)。在SRI那段岁月里, 有一个项目,要在美国航空航天局建立容错型航电计算机系统。考虑到系统的工作性质,故障是不允许发生的。这段经历孕育了两篇旨在解决一种特殊故障的论文,由兰伯特和SRI同事马歇尔·皮斯(Marshall Pies)及罗伯特·肖斯塔克(Robert Shostak)合作完成。使用计算机术语,普通故障可能会导致信息丢失或进程停止,但系统不会遭到破坏,因为这种普通故障属于一出错就会停下来的故障类型,剩下的备份的、正常的部分照样可以运转,发挥作用。就像战场上的士兵,他们一旦受伤或阵亡就停止战斗,但并不妨碍他人继续作战。然而一旦发生“拜占庭故障”,就会非常麻烦,因为它们不会停下来,还会继续运转,并且给出错误讯息。就像战争中有人成了叛徒,会继续假传军情,惑乱人心。使用三台计算机进行万一其中一台出错的备份工作,并不能完全解决这个问题。三台独立的计算机按照少数服从多数的原则“投票”。要求其中一台机器提供了错误结果的情况下,其他两台仍然会提供正确答案。但是为了证明这种解决“拜占庭故障”方法的有效性,必须拿出证据。而在编写证据的过程中,研究人员遇到了一个问题:“错误”的计算机可能给其他两台计算机发送互不相同的信息,而后者却无法区别正确性。这就需要使用第四台计算机来应对这类“拜占庭故障”。

兰伯特认为把问题以讲故事的形式表达出来更能引起人们的关注。兰伯特还听吉姆·格雷谈论过另一个性质大体相同的问题,这引起了兰伯特有关司令将军和叛徒将军的联想,于是他将这个问题及其解决方案命名为“拜占庭将军问题”。

拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因,这10支军队不能集合在一起单点突破,必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算,除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定其中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下,拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商,从而赢取战斗?这就是著名的拜占庭将军问题。

应该明确的是,拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题,即消息传递的信道绝无问题。兰伯特已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以,在研究拜占庭将军问题的时候,我们已经假定了信道是没有问题的,并在这个前提下,去做一致性和容错性相关研究。

口头消息算法,简称OM(m)

在原始的战争年代,将军与将军、将军与下属间只能采用原始的方式——“出行靠走,通讯靠吼”的口头传输。这对应兰伯特论文提出算法中的第一部分的口头消息算法,简称OM(m)算法。这种情形,真伪很难辨别,只有当叛徒的总数不超过将军总数的1/3,成为一个特殊的“拜占庭容错系统”时,才能在很大的消息验证代价后,实现最终的一致行动。这个结果非常令人惊讶,如果将军们只能发送口头消息,除非超过2/3的将军是忠诚的,否则该问题无解。尤其是,如果只有三个将军,其中一个是叛变者,那么此时无解。但这样的错误,这样的有意、无意的“叛徒”却可能经常出现。

首先,我们明确什么是口头协议。我们将满足以下三个条件的方式称为口头协议:

A1:每个被发送的消息都能够被正确的投递

A2:信息接收者知道是谁发送的消息

A3:能够知道缺少的消息

简而言之,信道绝对可信,且消息来源可知。

定义一个变量vi(为不失一般性,并不要求vi是布尔值),作为其他将军收到的第i个将军的命令值;i将军会将把自己的判断作为vi。可以想象,由于叛徒的存在,各个将军收到的vi值不一定是相同的。之后,定义一个函数来处理向量(v1,v2,…,vn),代表了多数人的意见,各将军用这个函数的结果作为自己最终采用的命令。至此,我们可以利用这些定义来形式化这个问题,用以匹配一致性和正确性。

一致性

条件1:每一个忠诚的将军必须得到相同的(v1,v2,…,vn)指令向量或者指令集合。

这意味着,忠诚的将军并不一定使用i将军送来的信息作为vi,i将军也可能是叛徒。但是仅靠这个条件,忠诚的将军的信息送来的信息也可能被修改,这将影响到正确性。

正确性

条件2:若i将军是忠诚的,其他忠诚的将军必须以他送出的值作为vi。

OM(0)算法

1. 司令将他的命令发送给每个副官。

2. 每个副官采用从司令发来的命令;如果没有收到命令,则默认为撤退命令。

OM(m)算法

1. 司令将他的命令发送给每个副官。

2. 对于每个i,vi是每个副官i从司令收到的命令,如果没有收到命令,则默认为撤退命令。副官i在OM(m-1) 中作为发令者将之发送给另外n-2 个副官。

3. 对于每个i,和每个j ≠ i,vj 是副官i 从第2步中的副官j (使用OM(m-1)算法)发送过来的命令,如果没有收到第2步中副官j 的命令,则默认为撤退命令。最后副官i 使用majority(v1,…,vn-1)得到命令。

其中,majority(v1,…,vn-1)代表了大多数人的命令,若不存在则默认为撤退命令。

口头消息算法实例推演

考虑m=1,n=4的情形:

n=4,意味着一个司令发送命令给三个副官,m=1意味着他们中有一个叛徒。首先考虑司令忠诚而副官3是叛徒的情况。

图1 m=1,n=4中司令忠诚而副官3是叛徒的情形

参考图1,

L1收到:(A,A,R)=》输出共识 majority(A,A,R) = A

L2收到:(A,A,R)=》输出共识 majority(A,A,R) = A

L3收到:(A,A,A)=》输出共识 majority(A,A,R) = A

那么对于副官1(或副官2)来说将会采用A。

倘若司令是叛徒,为方便,我们假设叛徒司令在OM(1)会给三个副官发送的信息是(x,y,z),其中x,y,z都可以是A或R的任意一种。之后,三位忠诚的副官将会按照OM(0)要求的那样,交换他们收到的信息。

图2 m=1,n=4中司令是叛徒的情形

L1收到:(x,y,z)=》输出共识 majority(x,y,z) ;

L2收到:(x,y,z)=》输出共识 majority(x,y,z);

L3收到:(x,y,z)=》输出共识 majority(x,y,z)。

对于副官1,他综合司令、副官2和副官3后得到的消息向量将会是(x,y,z),可以发现对于其他两个忠实的副官,他们得到的消息向量也将是(x,y,z)。不管x,y,z如何变化,majority(x,y,z)对于三人来说都是一样的,所以三个副官将会采用一致的行动。

口头消息算法证明

算法的证明思路其实并不复杂,简单的来说,对于一个递归算法,基于一个叛徒情景下的实例推演,可使用数学归纳法来证明。考虑篇幅,这里未提供完整的证明,可参考相关资料。

HyperLedger1.0系统架构

Hyperledger是被业界非常看到的联盟链的实现,包括IBM、Intel、R3、各个大型商业银行等都参与其中,带给我们关于区块链技术与软件工业、金融、保险、物流等领域碰撞结合的想象空间;在这个联盟中,有超过1/4的成员都来自中国,这更是我们对于它的一举一动都非常关注。很大程度上,Hyperledger和它背后的联盟体系就代表着区块链在产业环境中的未来。

主要模块:

  • 客户端SDK(Client SDK): 协助应用安全管理、和协助处理区块链上交易事务。
  • 节点是网络中的组成部分,负责维护节点的账本和职能合约。
  • 任意多个节点可参与到网络中。
  • 节点类型可以是背书节点(endorser)、或交付节点(committer )。背书节点必然是交付节点。
  • 背书节点执行并对交易事务进行背书。
  • 交付节点验证背书结果并对交易事务进行验证。
  • 节点管理事件集线器(event hub)并发送事件给订阅者。
  • 节点组建成一P2P网络。
  • 节点是无运行状态的,事务与事务间是独立的。
  • 排序服务(Ordering Service):是处于一个非中心化的网络中的一个中心化的节点。其排序服务是一可插拔的组件,例如Kafka、或BFT等。
  • 成员权限管理:通过基于 PKI 的成员权限管理,平台可以对接入的节点和客户端的能力进行限制。

图3 HyperLedger1.0系统结构图

事务交易流程

HyperLedger1.0的共识机制(Consensus)是通过事务背书策略(Transaction Endorsement Policy)、排序服务、和各提交节点Committer的校验这三个措施保证的。

背书(Endorsement): 每个背书节点(stakeholder )决定是否接受或拒绝一事务。

排序服务(Ordering): 对执行后的事务进行排序形成一即将提交的区块。

校验(Validation): 所有提交节点(Committer )都需校验事务的背书是否满足背书政策(Endorsement Policy),同时根据数据库多版本并发控制MVCC,校验事务转换是否有效。

以背书节点n=4、提交节点数p=5为例子。背书策略设置为:4个背书节点中,允许1个拜占庭故障节点情况下,要求有3个以上的有效签名。

图4 事务交易流程

也就是,如果允许m个无效签名的情况下,要求背书节点总数n>=3*m + 1,即需要有效签名数n-m>=2*m+1。如图4所示事务处理流程为:

步骤1:提交事务

客户端SDK提交一报文为Propose的消息的交易事务Transaction到客户端选择的背书节点E0,要求执行一智能合约A。

图5 步骤1提交事务

步骤2:第一个背书节点执行事务

被客户端选中的背书节点E0模拟交易的执行。

图6 步骤2第一个背书节点执行事务

步骤3:其他背书节点执行事务

客户端根据背书策略,要求其他节点E1E2和E3进一步背书。

图7 步骤3其他背书节点执行事务

步骤4:背书签名

背书节点对智能合约的执行结果进行签名,并发送背书签名给客户端。

图8 步骤5提交排序服务

步骤5:提交排序请求

最后,客户端根据背书政策(Endorsement Policy)检查是否满足条件,若满足条件则发送给排序服务。

图9 步骤6交付

步骤6:交付

排序服务集群交付事务执行结果的下个版本的账本数据块给各节点。

图10 步骤7校验并更新

区块链应用于政务网

传统中心化的电子证照技术自2008年发展至今,解决了传统模式下的数据归集和中心化的数据标准与安全问题。但经过近十年的“互联网+政务服务”的应用发展,该技术也凸显它的局限性。

  • 跨部门的政务数据是否可信
  • 信息难以全面归集
  • 信息难以快速检索
  • 信息泄露安全隐患
  • 系统稳定性难度大
  • 金字塔模式效率低下

虽然已有的人口信息、法人信息实现了部分集中管理,但中心化系统存在信息泄露,存储丢失等风险,而且中心化系统的建设、维护成本非常高,无法交互验证,无法实现各个部门真正意义上的信息共享、共建。所以,如何在现有的电子政务基础上,打破部门的数据壁垒,实现各部门之间的高效协作,实现真正意义的“一张网”,为群众提供便利的服务,是政务工作迫切需要解决的问题。

另外,区块链技术具有信息共享、信息透明、难以篡改的优势。利用该优势可打破原有信息传递的壁垒,实现电子证照服务模式的创新,提升用户体验。

目前证照办理过程中,大部分步骤需在线下处理,并且受到地域、时间的限制,需消耗较多的时间;同时纸质证明存在易伪造风险,相关证明接收机构还需核验证明的真伪性。

通过区块链技术打造各类证明的线上认证服务模式,可以提供证明从申请、开立、查询、销毁的全流程服务,打造电子证明生态圈。该创新将带来巨大的社会效益:

对于证明所有者,无须在证明开立方和证明使用方来回传递纸质证明,省却了物理地点(如异地)对证明开立及使用的限制;

对于证明提供方的权威机构,可通过自动化审批替代目前的人工审批,大大提高了工作效率和服务水平;

对于证明需求方,基于区块链的电子证明难以伪造及篡改,大大降低了虚假证明的风险。

图11 “我的南京”App政务办理

在南京政府多部门的支持下,率先上线全国第一批基于区块链接技术的电子证照共享平台。参见图11,市民可通过“我的南京”App进行政务的办理,“我的南京”App是该电子证照共享平台的数据访问终端。电子证照共享平台由政府职能部门共同组成的电子证照区块链网络,建立起政府部门之间点对点的可信网络。采用区块链的去中心化同步记帐、交易身份认证、数据不可篡改、以及数据加密等多种技术手段。参见图12电子证照政务网结构图,网络由信息中心、公安、民政、社保、税务、卫生等多个节点组成。共享账本中存储公民信息和数据归集记录。在智能合约中实现了数据目录规则、和数据隐私管理规则。现有电子证照网络只支持南京市的数据,考虑到扩展性支持,通过全国索引节点,不同城市不同省份的数据索引到不同的电子证照区块链子网。

图12 电子证照政务网结构图

基于区块链技术的电子证照共享平台与传统的电子证照库相比,具有更好的真实现、安全性、稳定性及可行性,解决了传统中心化架构的电子证照库采集和应用过程中权责不分的问题,彻底解决了数据被篡改的可能性,并通过激励机制提升数据相关方共享数据的积极性,且具备数据不被篡改、去中心化、数据加密及信任传递的特征,创新实现电子证照在全省、全市范围内跨区域的信息归集、快速检索和结果应用。透过任意职能部门提供照证证明服务,提高政务工作效率,提高市民、企业的办事效率。对进一步推进南京“互联网+政务服务”,深化简政放权、放管结合,实现各部门、各层级间政务服务数据共享,促进政府高效施政,提供了强有力的支持。

区块链弱并发问题

在应用区块链解决方案于政务网工程建设过程中,发现不少区别于传统关系型数据库的区块链特点。

HyperLedger其设计目标主要包括一致性(共识)、保密性、可扩展性和安全性,但是对高并发写事务的支持并不其主要目标。HyperLedger采用乐观锁(多版本并发控制)机制来支持并发,当交付节点(Submitter Peers)提交事务之前,如果发现ReadSet和WriteSet已经不一致了,将回滚事务。客户端需要尽可能避免同一关键字的写冲突,如果写冲突,需要多次提交事务。

假设在同一时刻有10个事务同时提交,当时这10个事务读取到的账本的数据一致。第一阶段,各背书节点执行事务,计算每个事务的读集合ReadSet0~9(K,V)和写集合WriteSet0~9(K,V),并提交到排序服务;第二阶段,排序服务对10个事务进行排序,并依次提交到所有的交付节点(Submitter Peers),交付节点会根据当前账本中的值检查对应于某一事务的读集合和写集合。如果对于同一个键Key,被前一个事务修改了,则该事务的读集合与当前账本的读集合不一致,则该事务不得不回滚。

为了避免并行执行的事务读写冲突,提升事务的并发执行效率。对于出现读写冲突的事务,采用拆分事务成为两个阶段的方法,在背书阶段记录事务的明细账,在提交阶段才进行汇总。例如对于会员积分变更的应用场景,在背书阶段,记录会员积分的变化明细,+ x1 + ... + xi 和 - y1 - ... - yi,在提交阶段才进行汇总积分的变更 D += + x1 + ... + xi - y1 - ... - yi 。

关系型数据建模的支持

区块链的底层数据模型为比较简单的键值对Key/Value模型,对于现实中的结构化数据的建模一般采用关系数据模型,如果采用Key/Value模型,开发人员需要耗费很多精力用于各种应用场景下数据模型的建设,和数据的索引、查询、统计等常规处理;同时存储在区块链中的数据需要进行进一步的大数据分析和数据挖掘工作,需要支撑区块链中的数据的导入导出到关系型数据库。另外现有区块链还没有支持数据的隐私保护、数据的提交维护和访问的权限管理。需要一完善的区块链数据建模基础框架来解决这些基于区块链的应用开发问题。

基于键值数据模型为基础进行关系型数据建模,其支持的特征包括:

基于键值数据模型,选择一取值唯一的字段作为键,包括多个属性字段的记录作为值,记录用独立于语言的轻量级数据交换格式JSON进行编码。

支持表结构、索引结构数据字典的维护;属性字段支持数值类型、字符串类型、日期类型。这些类型的字段是有序的、可建索引的;支持属性索引,索引类型包括唯一索引、非唯一索引。索引的维护与记录的增删改同步,同时索引数据结构的维护对模型的使用者透明。对于复杂结构的字段例如结构数组,可用JSON编码,只是该JSON类型字段不支持索引。另外利用索引支持数据约束,例如属性字段取值的唯一性约束。

支持丰富的数据查询方式,例如根据键的某一取值查询记录;根据键的取值范围查询多条记录;根据已建立唯一索引的属性字段的某一取值查询记录;根据已建立非唯一索引的属性的某一取值,或属性字段的取值范围查询多条记录;支持分组统计,例如基于属性字段的非唯一索引进行分组统计,统计函数包括个数统计、取分组的最大值、最小值、平均值;支持分页查询和分页统计;支持区块链数据的导入导出到关系型数据库,用于支撑数据分析。

后续丰富的政务网应用

本电子证照共享平台还将实现更多政务事项在线办理功能,如:“购车资格证明在线办理”、“户口在线迁入”、“社保在线转移”、“公积金在线提取”、“护照在线办理”、“出入境自助签注”等。

原文发布于微信公众号 - 区块链大本营(blockchain_camp)

原文发表时间:2018-02-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏All in Tech

Enecuum链

生态链之所以存在,主要是用于过滤不执行有用操作的交易(垃圾交易,垃圾邮件,过载信息,对区块链系统进行Dos攻击的尝试等)

45870
来自专栏大数据文摘

泄露数据中的秘密:中国网民的密码设置习惯

17120
来自专栏星汉技术

计算机基础(二)

26080
来自专栏FreeBuf

域名背后的真相,一个黑产团伙的沦陷

前言 很多小伙伴溯源一般只追查到whois信息,但个人认为该信息未必是真实有效的,挖掘背后的信息才是正章。 起因 今天在朋友圈,看到朋友发了一条信息,说收到带病...

597100
来自专栏农夫安全

信息安全等级保护基础知识普及

计算机信息系统 computer information system ? 计算机信息系统是由计算机及其相关的和配套的设备、设施(含网络)构成的,按照...

46880
来自专栏FreeBuf

揭秘:黑客反击战APT-on-APT分析报告

电影《古惑仔》中,我们常常看到黑社会团体之间的暴力冲突。而在网络空间里,你见过APT(高级持续性威胁)黑客组织互掐吗? 黑客组织Naikon Naikon是活跃...

25750
来自专栏Netkiller

以太坊·代币开发详解

本文节选自《Netkiller Blockchain 手札》

679110
来自专栏FreeBuf

Ledger硬件钱包存在漏洞,通过MITM可篡改钱包地址

近日,刚获得7500万美元B轮融资的加密货币硬件钱包“Ledger”被曝存在漏洞,且已经由匿名安全研究员确认,网络犯罪分子可利用该漏洞向Ledger使用者展示欺...

23150
来自专栏Albert陈凯

2018-07-14 代码中的人文故事:从一个Java的“Bug”说起

I like this kind of story , can not type in chinese character using ubuntu . so ...

12420
来自专栏MYSQL轻松学

一组漫画告诉你Linux 系统有什么

今天,看到一组漫画,主要介绍Linux内核构成,可以帮助大家对Linux内核有个初步认知。TurnOff.us 是一个极客漫画网站,作者Daniel Stori...

26750

扫码关注云+社区

领取腾讯云代金券