浅谈区块链

1
2
3
4
5
笔者目前在上海工作,平安集团,涉及到银行、保险、投资、贷款等行业,虽然也是身处金融信息化行业,但集团瞎扯什么“互联网+金融”,具体执行起来却仍旧是一家偏保守的传统金融公司;并且身处中国大陆,各方面的监管、审查,限制太多了。我的很多设想都无法实现。

所以期待有一天可以去香港这样的国际金融中心,开发出合规、安全、高效的区块链应用。

以下都是瞎写的,没什么格式,随心所欲。

区块链思想的诞生

特点

  • 分布式容错性:分布式网络极其鲁棒,能够容忍部分节点的异常状态
  • 不可篡改性:一致提交后的数据会一直存在,不可被销毁或修改
  • 隐私保护性:密码学保证了数据隐私,即使数据泄露,也无法解析
  • 可信任性:区块链技术可以提供天然可信的分布式账本平台,不需要额外第三方中介机构参与
  • 降低成本:跟传统技术相比,区块链技术可能需要的时间、人力和维护成本更少
  • 增强安全:区块链技术将有利于安全、可开的审计管理和账目清算,减少犯罪风险

核心技术概览

定义与原理

  • 交易(transaction):一次对账本的操作,导致账本状态的一次改变
  • 区块(block):记录一段时间内发生的所有交易和状态结果,是对当前账本状态的一次共识
  • 链(chain):由区块按照发生顺序串联而成,是整个账本状态变化的日志记录

如果把区块链作为一个状态机,则每次交易就是试图改变一次状态,而每次共识生成的区块,就是参与者对于区块中交易导致状态改变的结果进行确认。

技术的演化与分类

演化

  • 比特币:数字货币系统,公信的数字货币,区块链1.0。
  • 以太坊:智能合约,公信的交易处理,区块链2.0。
  • 超级账本:商业处理,带权限的分布式账本处理,区块链3.0。

分类

  • 公有链:任何人都可以参与使用和维护,信息完全公开。
  • 私有链:由集中管理者进行管理限制,只有内部少数人可以使用,信息不公开。
  • 联盟链:由若干组织一起合作维护一条区块链,该区块链的使用必须是带有权限的限制访问,相关信息会得到保护。

目前来看,公有链更容易吸引市场和媒体的眼球,但更多的商业价值会在联盟链和私有链上落地。

关键问题和挑战

  • 抗抵赖与隐私保护
1
2
3
4
5
6
7
怎么防止交易记录被篡改?
怎么证明交易双方的身份?
怎么保护交易双方的隐私?
密码学的发展为解决这些问题提供了不少手段。传统方案包括 Hash 算法、加解密算法、数字证书和签名(盲签名、换签名)等。
随着区块链技术的应用,新出现的需求将刺激密码学的进一步发展,包括更高效的随机数产生、更高强度的加密、更快速的加解密处理等。
同时,量子计算等新技术的出现,也会带来更多的挑战,例如,RSA 算法等目前商用的加密算法,在未来可能无法提供足够的安全性。
能否满足这些新的需求,将依赖于数学科学的进一步发展和新一代计算技术的突破。
  • 分布式共识
1
2
3
4
问题的核心在于如何解决某个变更在分布式网络中得到一致的执行结果,是被参与多方都承认的,同时这个信息是被确定的,不可推翻的。
该问题在公开匿名场景下和带权限管理的场景下需求差异较大,从而导致了基于概率的算法和确定性算法两类思想。
比特币:PoW,工作量证明,通过概率模型。
超级账本:PBFT,拜占庭算法,确定性的共识机制,解决快速确认的问题。
  • 交易性能
1
2
3
4
5
6
虽然一般来说,区块链不适用于高频交易的场景,但由于金融系统的需求,业界目前十分关心如何提高区块链系统交易的吞吐量,同时降低交易的确认延迟。
目前,公开的比特币区块链只能支持平均每秒约7笔的吞吐量,一般认为对于大额交易来说,安全的交易确认时间为一个小时左右。
以太坊区块链的吞吐量略高一些,但交易性能也被认为是较大的瓶颈。
总之,高性能、安全、稳定性、硬件辅助加解密能力,都将是考察节点性能的核心要素。
为了提高处理性能,一方面可以提升单个节点的性能(如采用高配置的硬件),同时设计优化的策略和算法;另一方面试图将大量高频的交易放到链外来,只用区块链记录最终交易信息,如比特币社区提出的“闪电网络”等设计。
类似地,侧链(side chain)、影子链(shadow chain)等思路在当前阶段也有一定的借鉴意义。
  • 扩展性
1
2
3
4
5
常见的分布式系统可以通过增加节点来横向扩展整个系统的处理能力。
对于区块链网络系统来说,根据共识机制的不同,这个问题往往并非那么简单。
例如,对于比特币和以太坊区块链而言,网络中每个参与维护的核心节点都要保持一份完整的存储,并且进行智能合约的处理。此时,整个网络的总存储量和计算能力取决于单个节点的能力。甚至当网络中节点数过多时,可能会因为一致性的达成过程延迟降低整个网络的性能。尤其在公有网络中,由于存在大量低性能处理节点,导致这个问题将更加明显。
要解决这个问题,根本上是放松对每个节点都必须参与完整处理的限制,这个思路已经在超级账本中得到应用;同时尽量减少核心层的处理工作。
在联盟链模式下,还可以专门采用高性能的节点作为核心节点,相对较弱的节点仅作为代理访问节点。
  • 安全防护
1
2
3
4
5
6
7
8
世界上没有绝对安全的系统。
系统是由人设计的,也是由人来运营的。只要有人参与的系统,就难免出现漏洞。
如下几个方面很难避免。
立法:对区块链系统如何进行监管?攻击区块链系统是否属于犯罪?目前还没有任何法律保护区块链(特别是公有链)以及基于它的实现。
软件实现的潜在漏洞:源代码完全开放,是否更容易被人找到漏洞呢?
隐私保护:公有链所有交易记录都是公开可见的,这意味着所有的交易几十被匿名化和加密处理,但总会在未来某天被破解。安全界一般认为,只要物理上可接触就不是彻底的安全。
系统维护:作为一套完全分布式的系统,公有区块链缺乏有效的调整机制,一旦运行起来,出现问题难以修正以及升级;即使是让它变得更高效、更完善的修改,只要部分既得利益者联合起来反对,就无法得到实施。
监管审核:智能合约应用五花八门,有些可能存在潜在的漏洞,但是无法进行有效安全管控。
  • 数据库和存储系统
1
“块数据库”(BlockDB),专门服务类似于区块链这样的新型数据业务,其中每条记录将包括一个完整的区块信息,并天然地跟历史信息进行关联,一旦写入确认则无法修改。所有操作的最小单位将是一个块。为了实现这种结构,需要原生支持高效的签名和加解密处理。
  • 集成和运营
1
2
3
即便大量企业系统准备迁移到区块链平台上,但在相当长的一段时间内,基于区块链的新业务系统必将与已有的中心化系统集成共存。
两种系统如何共存,如何分工,彼此的业务交易如何进行合理传递?出现故障如何排查和隔离?已有数据如何在不同系统之间进行迁移和灾备?区块链系统自身又该如何进行运营(如网络的设计选择、状态监控、灾备等)?
这些都是迫切需要解决的实际问题。若解决不好,将是区块链技术落地的不小阻碍。

认识上的误区

目前,由于区块链自身仍是一种相对年轻的技术,不少人对区块链的认识还存在一些误区。
下面是需要注意的一些问题:

区块链不等于比特币。虽说区块链的基本思想诞生于比特币的设计中,但发展至今日,比特币和区块链已经俨然成为了两个不太相关的技术。前者更侧重从数字货币角度发掘比特币的实验性意义;后者则从技术层面探讨和研究可能带来的商业系统价值,试图在更多的场景下释放智能合约和分分布式账本带来的科技潜力。

区块链不等于数据库。虽然区块链也可以用来存储数据,但它要解决的核心问题是多方的互信问题。单纯从存储数据角度,它的效率可能不高,也不推荐把大量的原始数据放到区块链系统上。当然,现在已有的区块链系统中,数据库相关的技术十分关键,直接决定了区块链系统的吞吐性能。

区块链并非一门万能的颠覆性技术。作为融合多项已有技术而出现的新事物,区块链跟现有技术的关系是一脉相承的。它在解决多方合作和可信处理上向前多走了一步,但并不意味着它是万能的,更不会彻底颠覆已有的商业模式。很长一段时间里,区块链所适用的场景仍需不断摸索,并且跟已有系统也必然是长期合作共存的关系。

典型应用场景

应用场景概览

区块链技术已经从单纯的技术讨论走向了应用落地的阶段。

实际上,要找到合适的应用场景,还是要从区块链自身的特性出发进行分析。

区块链在不引入第三方中介机构的前提下,可以提供去中心化、不可篡改、安全可靠等特性保证。因此,所有直接或间接依赖于第三方担保机构的活动,均可能从区块链技术中获益。

区块链自身维护着一个按时间顺序持续增长、不可篡改的数据记录,当现实或数字世界中的资产可以生成数字摘要时,区块链便成为确权类应用的完美载体,提供包含所属权和时间戳的数字证据。

可编程的智能合约使得在区块链上登记的资产可以获得在现实世界中难以提供的流动性,并能够保证合约规则的透明和不可篡改。这就为区块链上诞生更多创新的经济活动提供了土壤,为社会资源价值提供更加高效且安全的流动渠道。

此外,还需要思考区块链解决方案的合理辩解。面向大众消费者的区块链应用需要做到公开、透明、可审计,既可以部署在无边界的公有链,也可以部署在应用生态内多中心节点共同维护的区块链;面向企业内部或多个企业间的商业区块链场景,则可将区块链的维护节点和可见性限制在联盟内部,并用智能合约重点解决联盟成员间的信任或信息不对等问题,以提高经济活动效率。

金融服务

区块链带来的潜在优势包括降低交易成本、减少跨组织交易风险等。该领域的区块链应用目前最受关注,全球不少银行和金融交易机构都是主力推动者。部分投资机构也在应用区块链技术降低管理成本和管控风险。从另一方面,要注意可能引发的问题和风险。

银行业金融管理

银行从角色上一般可分为中央银行(央行)和普通银行。

中央银行的两大职能是“促进宏观经济稳定”和“维护金融稳定”,主要手段就是管理各种证券和利率。中央银行,为整个社会的金融体系提供了最终的信用担保。

普通银行业则往往基于央行的信用,作为中介和担保方,来协助完成多方的金融交易。

银行活动主要包括发行货币、完成存贷款等功能。银行必须确保交易的确定性,必须确立自身的可靠信用地位。传统的金融系统为了完成上述功能,采用了极为复杂的软件和硬件方案,建设和维护成本都十分昂贵。即便如此,这些系统仍然存在诸多缺陷,例如某些场景下交易时延过大;难以避免利用系统漏洞进行的攻击和金融欺诈等。

此外,在目前金融系统流程中,商家为了完成交易,还常常需要经由额外的支付企业进行处理。这些实际上都极大增加了现有金融交易的成本。

区块链技术的出现,被认为是有可能促使这一行业发生革命性变化的“奇点”。除了众所周知的比特币等数字货币实验之外,还有诸多金融机构进行了有意义的尝试。

欧洲央行评估区块链在证券交易后结算的应用

目前,全球证券交易后的处理过程十分复杂,清算行为成本约 50 亿 ~ 100 亿美元,交易后分析、对账和处理费用超过 200 亿美元。

来自欧洲央行的一份报告显示,区块链作为分布式账本技术,可以很好地节约对账的成本,同时简化交易过程。相对原先的交易过程,可以近乎实时地变更证券的所有权。

中国人民银行投入区块链研究

前不久,中国人民银行对外发布消息,称深入研究了数字货币涉及的相关技术,包括区块链技术、移动支付、可信可控云计算、密码算法、安全芯片等,是积极关注区块链技术的发展的。实际上,央行对于区块链技术的研究很早便已开展。

2014 年,央行成立发行数字货币的专门研究小组对基于区块链的数字货币进行研究,次年形成研究报告。

2016 年 1 月 20 日,央行专门组织了“数字货币研讨会”,邀请了业内的区块链技术专家就数字货币发行的总体框架、演进以及国家加密货币等话题进行了研讨。会后,发布对我国银行业数字货币的战略性发展思路,提出要早日发行数字货币,并利用数字货币相关技术来打击金融犯罪活动。

2016 年 12 月,央行成立数字货币研究所。初步公开设计为由央行主导,在保持实物现金发行的同时发行以加密算法为基础的数字货币,M0(流通中的现金)的一部分由数字货币构成。为充分保障数字货币的安全性,发行者可采用安全芯片为载体来保护密钥和算法运算过程的安全。

加拿大银行提出新的数字货币 CAD

2016 年 6 月,加拿大央行公开了正在开发基于区块链技术的数字版加拿大元(名称为CAD币),以允许用户使用加元来兑换该数字货币。经过验证的对手方将会处理货币交易;另外,如果需要,银行将保留销毁 CAD 币的权利。

发行 CAD 币是更大的一个探索型科技项目 Jasper 的一部分。除了加拿大央行外,蒙特利尔银行、加拿大帝国商业银行、加拿大皇家银行、加拿大丰业银行、多伦多道明银行等多家机构也都参与了该项目。

英国央行实现 RSCoin

英国央行在数字化货币方面进展十分突出,已经实现了基于分布式账本平台的数字化货币系统,RSCoin。旨在强化本国经济及国际贸易。

RSCoin 目标是提供一个由中央银行控制的数字货币,采用了双层链架构、改进版的两阶段提交(Two Phase Commitment,2PC)提交,以及多链之间的交叉验证机制。该货币具备防篡改和伪造的特性。

因为该系统主要是央行和下属银行之间使用,通过提前建立一定的信任基础,可以提供较好的处理性能。

英国央行对 RSCoin 进行了推广,希望能尽快普及该数字货币,以带来节约经济成本、促进经济发展的效果。同时,英国央行认为,数字货币相对于传统货币更适合国际贸易等场景。

日本政府取消比特币消费税

2017 年 3 月 27 日,日本国会通过《2017税务改革法案》,该法案将比特币等数字货币定义为货币等价物,可以用于数字支付和转账。

法案于 2017 年 7 月 1 日生效,销售数字货币不必再缴纳 8% 的消费税。

中国邮储银行将区块链技术应用到核心业务系统

2016 年 10 月,中国邮储银行宣布携手IBM推出基于区块链技术的资产托管系统,是中国银行业首次将区块链技术成功应用于核心业务系统。

新的业务系统免去了重复的信用校验过程,将原有业务环节缩短了约 60% ~ 80% 的时间,提高了信用交易的效率。

各种新型支付业务

基于区块链技术,出现了大量的创新支付企业,这些支付企业展示了利用区块链技术带来的巨大商业优势。

  • Abra:区块链数字钱包,以近乎实时的速度进行跨境支付,无需银行账户和手续费,融资超过千万美元;

  • Bitwage:基于比特币区块链的跨境工资支付平台,可以实现每小时的工资支付,方便跨国企业进行工资管理;

  • BitPOS:澳大利亚创业企业,提供基于比特币的低成本的快捷线上支付;

  • Circle:由区块链充当支付网络,允许用户进行跨币种、跨境的快速汇款。Circle 获得了来自 IDG、百度的超过 6000 万美元的 D 轮投资;

  • Ripple:实现跨境的多币种、低成本、实时交易,引入了网关概念(类似于银行),结构偏中心化。

证券交易

证券交易包括交易执行环节和交易后处理环节。

交易环节本身相对简单,主要是由交易系统(高性能实时处理系统)完成电子数据库中内容的变更。中心化的验证系统往往极为复杂和昂贵。交易指令执行后的结算和清算环节也十分复杂,需要大量的人力成本和时间成本,并且容易出错。

目前来看,基于区块链的处理系统还难以实现海量交易系统所需要的性能(典型性能为每秒一万笔以上成交,日处理能力超过五千万笔委托、三千万笔成交)。但在交易的审核和清算环节,区块链技术存在诸多的优势,可以极大降低处理时间,同时减少人工的参与。

咨询公司 Oliver Wyman 在给 SWIFT(环球同业银行金融电讯协会)提供的研究报告中预计,全球清算行为成本约 50 亿 ~ 100 亿美元,结算成本、托管成本和担保物管理成本 400 亿 ~ 450 亿美元(390亿美元为托管链的市场主体成本),而交易后流程数据及分析花费200亿~250亿美元。

2015 年 10 月,美国纳斯达克(Nasdaq)证券交易所推出区块链平台 Nasdaq Linq,实现主要面向一级市场的股票交易流程。通过该平台进行股票发行的发行者将享有“数字化”的所有权。

其他相关案例还包括:

  • BitShare 推出基于区块链的证券发行平台,号称每秒达到 10 万笔交易;

  • DAH 为金融市场交易提供基于区块链的交易系统。获得澳洲证交所项目;

  • Symbiont 帮助金融企业创建存储于区块链的智能债券,当条件符合时,清算立即执行;

  • Overstock.com 推出基于区块链的私有和公开股权交易“T0”平台,提出“交易即结算”(The trade is the settlement)的理念,主要目标是建立证券交易实时清算结算的全新系统;

  • 高盛为一种叫做“SETLcoin”的新虚拟货币申请专利,用于为股票和债券等资产交易提供“近乎立即执行和结算”的服务。

众筹投资

作为去中心化的众筹管理的代表,DAO(Decentralized Autonomous Organization)曾创下历史最高的融资记录,数额超过 1.6 亿美元。

值得一提的是,DAO 的组织形式十分创新,也造成其在受到攻击后的应对缺乏经验。项目于 2016 年 4 月 30 日开始正式上线。6 月 12 日,有技术人员报告合约执行过程中存在软件漏洞,但很遗憾并未得到组织的重视和及时修复。四天后,黑客利用漏洞转移了 360 万枚以太币,当时价值超过 5000 万美元。

虽然,最后相关组织采用了一些技术手段来挽回损失,但该事件毫无疑问给以太币带来了负面影响,也给新兴技术在新模式下的业务流程管理敲响了警钟。

除了 DAO 这种创新组织形式之外,传统风投基金也开始尝试用区块链募集资金。Blockchain Capital 在 2017 年发行的一支基金创新地采用了传统方式加 ICO(Initial Coin Offering)方式进行募资,其中传统部分规模 4000 万美元,ICO 部分规模 1000 万美元。4 月 10 日,ICO 部分 1000 万美元的募集目标在启动后六小时内全部完成。

用 ICO 方式进行众筹可以降低普通投资者对早期项目的参与门槛,并提高项目资产流动性。目前对于 ICO 的众筹模式缺少明确的法律法规,对项目的商业模式也很难按照传统方法进行估值与代币定价。但随着项目发起人开始重视对底层技术、资金使用和项目发展的信息披露,大众投资者开始加深理解区块链技术及其可行的应用场景,将有助于促进这种新兴模式的健康发展。

征信和权属管理

征信和权属的数字化管理师大型社交平台和保险公司都梦寐以求的。目前该领域的主要问题包括缺乏足够的数据和分析能力;缺乏可靠的平台支持以及有效的数据整合管理等。区块链被认为可以促进数据交易和流动,提供安全可靠的支持。征信行业的门槛比较高,需要多方资源共同推动。

征信管理

征信管理是一个巨大的潜在市场,据称超过千亿规模,也是目前大数据应用领域最有前途的方向之一。

目前,与征信相关的大量有效数据集中在少数机构手中。由于这些数据太过敏感,并且具备极高的商业价值,往往会被严密保护起来,形成很高的行业门槛。

虽然现在大量的互联网企业(包括各类社交网站)尝试从各种维度获取了海量的用户信息,但从征信角度看,这些数据仍然存在若干问题。这些问题主要包括:

  • 数据量不足:数据量越大,能获得的价值自然越高,数据量过少则无法产生有效价值;

  • 相关度较差:最核心的数据也往往是最敏感的。在隐私高度敏感的今天,用户都不希望暴露过多数据给第三方,因此企业获取到数据中有效成分往往很少;

  • 时效性不足:企业可以从明面上获取到的用户数据往往是过时的,甚至存在虚假信息,对相关分析的可信度造成严重干扰;

  • 数据孤岛:数据过于分散,没有能将不同类型数据联系在一起的纽带。

区块链天然存在着无法篡改、不可抵赖的特性。同时,区块链平台将可能提供前所未有规模的相关性极高的数据,这些数据可以在时空中准确定位,并严格关联到用户。因此,基于区块链提供数据进行征信管理,将大大提高信用评估的准确率,同时降低评估成本。

另外,跟传统依靠人工的审核过程不同,区块链中交易处理完全遵循约定自动化执行。基于区块链的信用机制将天然具备稳定性和中立性。

目前,包括 IDG、腾讯、安永、普华永道等都已投资或进入基于区块链的征信管理领域,特别是跟保险和互助经济相关的应用场景。

2016 年 7 月,德勤、Stratumn 和 LemonWay 共同推出一个为共享经济场景设计的“微保险”概念平台,称为 LenderBot。针对共享经济活动中临时交换资产可能产生的风险,LenderBot 允许用户在区块链上注册定制的微保险,并为共享的资产(如相机、手机、电脑)投保。区块链在其中扮演了可信第三方的角色。

权属管理

区块链技术可以用于产权、版权等所有权的管理和追踪。其中包括汽车、房屋、艺术品等各种贵重物品的交易等,也包括数字出版物,以及可以标记的数字资源。

目前权属管理领域存在的几个难题是:

  • 所有权的确认和管理;

  • 交易的安全性和可靠性保障;

  • 必要的隐私保护机制。

以房屋交易为例。买卖双方往往需要依托中介机构来确保交易的进行,并通过纸质的材料证明房屋所有权。但实际上,很多时候中介机构也无法确保交易的正常进行。

而利用区块链技术,物品的所有权是写在数字链上的,谁都无法修改。并且一旦出现合同中约定情况,区块链技术将确保合同能得到准确执行。这能有效减少传统情况下纠纷仲裁环节的人工干预和执行成本。

例如,公正通(Factom)尝试使用区块链技术来革新商业社会和政府部门的数据管理和数据记录方式。包括审计系统、医疗信息记录、供应链管理、投票系统、财产契据、法律应用、金融系统等。它将待确权数据的指纹存放到基于区块链的分布式账本中,可以提供资产所有权的追踪服务。

区块链账本共享、信息可追踪溯源且不可篡改的特性同样可用于打击造假和防范欺诈。Everledger 自 2016 年起就研究基于区块链技术实现贵重资产检测系统,将钻石或者艺术品等的权属信息记录在区块链上,并于 2017 年宣布与 IBM 合作,实现生产商、加工商、运送方、零售商等多方之间的可信高效协作。

其他项目

在人力资源和教育领域,MIT研究员朱莉安娜·纳扎雷(Juliana Nazaré)和学术创新部主管菲利普·施密特(Philipp Schmidt)发表了文章《MIT Media Lab Uses the Bitcoin Blockchain for Digital Certificates》,介绍基于区块链的学历认证系统。基于该系统,用人单位可以确认求职者的学历信息是否真实可靠。

此外,还包括一些其他相关的应用项目:

  • Chronicled:基于区块链的球鞋鉴定方案,为正品球鞋添加电子标签,记录在区块链上;

  • Mediachain:通过metadata协议,将内容创造者与作品唯一对应。

  • Monegraph:通过区块链保障图片版权的透明交易;

  • Mycelia:区块链产权保护项目,为音乐人实现音乐的自由交易;

  • Tierion:将用户数据锚定在比特币区块链上,并生成“区块链收据”。

资源共享

当前,以 Uber、Airbnb 为代表的共享经济模式正在多个垂直领域冲击传统行业。这一模式鼓励人们通过互联网的方式共享闲置资源。资源共享目前面临的问题主要包括:

  • 共享过程成本过高;

  • 用户行为评价难;

  • 共享服务管理难。

区块链技术为解决上述问题提供了更多的可能性。相比于依赖于中间方的资源共享模式,基于区块链的模式有潜力更直接地连接资源的供给方和需求方,其透明、不可篡改的特性有助于减小摩擦。

有人认为区块链技术会成为新一代共享经济的基石。笔者认为,区块链在资源共享领域是否存在价值,还要看能否比传统的专业供应者或中间方形式实现更高的效率和更低的成本,同时不能损害用户体验。以 Airbnb 为代表的分享经济公司将欢迎去中心化应用,可以降低管理成本。该领域主题相对集中,设计空间大,受到大量的投资关注。

短租共享

大量提供短租服务的公司已经开始尝试用区块链来解决共享中的难题。高盛在报告《Blockchain:Putting Theory into Practice》中宣称:

Airbnb 等 P2P 住宿平台已经开始通过利用私人住所打造公开市场来变革住宿行业,但是这种服务的接受程度可能会因人们对人身安全以及财产损失的担忧而受到限制。而如果通过引入安全且无法篡改的数字化资质和信用管理系统,我们认为区块链就能有助于提升 P2P 住宿的接受程度。

该报告还指出,可能采用区块链技术的企业包括 Airbnb、HomeAway 以及 OneFineStay 等,市场规模为 30 亿 ~ 90 亿美元。

社区能源共享

在纽约布鲁克林的一个街区,已有项目尝试将家庭太阳能发的电通过社区的电力网络直接进行买卖。具体的交易不再经过电网公司,而是通过区块链执行。

与之类似,ConsenSys 和微电网开发商 LO3 提出共建光伏发电交易网络,实现点对点的能源交易。

这些方案的主要难题包括:

  • 太阳能电池管理;

  • 太阳能电池管理;

  • 电力储备系统搭建;

  • 低成本交易系统支持。

现在已经有大量创业团队在解决这些问题,特别是硬件部分已经有了不少解决方案。而通过区块链技术打造的平台可以解决最后一个问题,即低成本地实现社区内的可靠交易系统。

电商平台

传统情况下,电商平台起到了中介的作用。一旦买卖双方发生纠纷,电商平台会作为第三方机构进行仲裁。这种模式存在着周期长、缺乏公证、成本高等缺点。OpenBazaar 试图在无中介的情形下,实现安全电商交易。OpenBazaar 提供的分布式电商平台,通过多方签名机制和信誉评分机制,让众多参与者合作进行评估,实现零成本解决纠纷问题。

大数据共享

大数据时代里,价值来自于对数据的挖掘,数据维度越多,体积越大,潜在价值也就越高。一直以来,比较让人头疼的问题是如何评估数据的价值,如何利用数据进行交换和交易,以及如何避免宝贵的数据在未经许可的情况下泄露出去。

区块链技术为解决这些问题提供了潜在的可能。利用共同记录的共享账本,数据在多方之间的流动将得到实时的追踪和管理。通过对敏感信息的脱敏处理和访问权限的设定,区块链可以对大数据的共享授权进行精细化管控、规范,促进大数据的交易与流通。

减小共享风险

传统的资源共享平台在遇到经济纠纷时会充当调解和仲裁者的角色。对于区块链共享平台,目前还存在线下复杂交易难以数字化等问题。除了引入信誉评分、多方评估等机制,也有方案提出引入保险机制来对冲风险。

2016 年 7 月,德勤、Stratumn 和 LemonWay 共同推出一个为共享经济场景设计的“微保险”概念平台,称为 LenderBot。针对共享经济活动中临时交换资产可能产生的风险,LenderBot 允许用户在区块链上注册定制的微保险,并为共享的资产(如相机、手机、电脑)投保。区块链在其中扮演了可信第三方和条款执行者的角色。

贸易管理

区块链技术可以帮助自动化国际贸易和物流供应链领域中繁琐的手续和流程。基于区块链设计的贸易管理方案回味参与的多方企业带来极大的便利。另外,贸易中小手和法律合同的数字化、货物监控与检测、实时支付等方向都可能成为创业公司的突破口。

跨境贸易

在国际贸易活动中,买卖双方可能互不信任。因此需要银行作为买卖双方的保证人,代为收款交单,并以银行信用代替商业信用。

区块链可以为信用证交易参与方提供共同账本,允许银行和其他参与方拥有经过确认的共同交易记录并据此履约,从而降低风险和成本。

巴克莱银行用区块链进行国际贸易结算—— 2016 年 9 月,英国巴克莱银行用区块链技术完成了一笔国际贸易的结算,贸易金额 10 万美元,出口商品是爱尔兰农场出产的芝士和黄油,进口商是位于离岸群岛塞舌尔的一家贸易商。结算用时不到 4 小时,而传统采用信用证方式做此类结算需要 7 到 10 天。

在这笔贸易背后,区块链提供了记账和交易处理系统,替代了传统信用证结算过程中占用大量人力和时间的审单、制单、电报或邮寄等流程。

物流供应链

物流供应链是区块链一个很有前景的应用方向。供应链行业往往涉及诸多实体,包括物流、资金流、信息流等,这些实体之间存在大量复杂的协作和沟通。传统模式下,不同实体各自保存各自的供应链信息,严重缺乏透明度,造成了较高的时间成本和金钱成本,而且一旦出现问题(冒领、货物假冒等),难以追查和处理。

通过区块链,各方可以获得一个透明可靠的统一信息平台,可以实时查看状态,降低物流成本,追溯物品的生产和运送整个过程,从而提高供应链管理的效率。当发生纠纷时,举证和追查也变得更加清晰和容易。

例如,运送方通过扫描二维码来证明货物到达指定区域,并自动收取提前约定的费用;冷链运输过程中通过温度传感器实时检测货物的温度信息并记录在链等。来自美国加州的Skuchain公司创建基于区块链的新型供应链解决方案,实现商品流与资金流的同步,同时缓解假货问题。

马士基推出基于区块链的跨境供应链解决方案—— 2017 年 3 月,马士基和IBM宣布,计划与由货运公司、货运代理商、海运承运商、港口和海关当局构成的物流网络合作构建一个新型全球贸易数字化解决方案。该方案利用区块链技术在各方之间实现信息透明性,降低贸易成本和复杂性,旨在帮助企业减少欺诈和错误,缩短产品在运输和海运过程中所花的时间,改善库存管理,最终减少浪费并降低成本。马士基在 2014 年发现,仅仅是将冷冻货物从东非运到欧洲,就需要经过近 30 个人员和组织进行超过 200 次的沟通和交流。类似这样的问题都有望借助区块链进行解决。

一带一路

类似“一带一路”这样创新的投资建设模式,会碰到来自地域、货币、信任等各方面的挑战。

现在已经有一些参与到一带一路中的部门,对区块链技术进行探索应用。区块链技术可以让原先无法交易的双方(例如,不存在多方都认可的国际货币储备的情况下)顺利完成交易,并且降低贸易风险、减少流程管控的成本。

物联网

曾经有人认为,物联网是大数据时代的基础。

笔者认为,区块链技术是物联网时代的基础。

物联网也是很适合应用区块链技术的一个领域,预计未来几年会有大量应用出现,特别是租赁。物流等特定场景,都是很适合区块链技术的场景。但目前阶段,物联网自身的技术局限将造成短期内不会出现大规模应用。

典型应用场景分析

一种可能的应用场景为:物联网络中每一个设备分配地址,给该地址关联一个账户,用户通过向账户中支付费用可以租借设备,以执行相关动作,从而达到租借物联网的应用。

典型的应用包括 PM2.5 监测点的数据获取、温度检测服务、服务器租赁、网络摄像头数据调用,等等。

另外,随着物联网设备的增多、边沿计算需求的增强,大量设备之间形成分布式自组织的管理模式,并且对容错性要求很高。区块链技术所具备的分布式和抗攻击特点可以很好地融合到这一场景中。

IBM

IBM 在物联网领域已经持续投入了几十年的研发,目前正在探索使用区块链技术来降低物联网应用的成本。2015 年的年初,IBM 与三星宣布合作研发“去中心化的 P2P 自动遥测系统”(Autonomous Decentralized Peer-to-Peer Telemetry)系统,使用区块链作为物联网设备的共享账本,打造去中心化的物联网。

Filament

美国的 Filament 公司以区块链为基础提出了一套去中心化的物联网软件堆栈。通过创建一个智能设备目录,Filament 的物联网设备可以进行安全沟通、执行智能合约以及发送小额交易。

基于上述技术,Filament 能够通过远程无线网络将辽阔范围内的工业基础设备沟通起来,其应用包括追踪自动售货机的存货和机器状态、检测铁轨的损耗、基于安全帽或救生衣的应急情况监测等。

NeuroMesh

2017 年 2 月,源自 MIT 的 NeuroMesh 物联网安全平台获得了 MIT 100K Accelerate竞赛的亚军。该平台致力于成为“物联网疫苗”,能够检测和消除物联网中的有害程序,并将攻击源打入黑名单。

所有运行NeuroMesh软件的物联网设备都通过访问区块链账本来识别其他节点和辨认潜在威胁。如果一个设备借助深度学习功能检测出可能的威胁,可通过发起投票的形式告知全网,由网络进一步对该威胁进行检测并做出处理。

公共网络服务

现有的互联网能正常运行,离不开很多近乎免费的网络服务,例如域名服务(DNS)。任何人都可以免费查询到域名,没有 DNS,现在的各种网站将无法访问。因此,对于网络系统来说,类似的基础服务必须要能做到安全可靠,并且低成本。

区块链技术恰好具备这些特点,基于区块链打造的分布式DNS系统,将减少错误的记录和查询,并且可以更加稳定可靠地提供服务。

其他场景

区块链还有一些很有趣的应用场景,包括但不限于云存储、医疗、社交、游戏等多个方面。

云存储

Storj 项目提供了基于区块链的安全分布式云存储服务。服务保证只有用户自己能看到自己的数据,并号称提供高速的下载速度和 99.99999% 的高可用性。用户还可以“出租”自己的额外硬盘空间来获得报酬。

协议设计上,Storj 网络中的节点可以传递数据、验证远端数据的完整性和可用性、复原数据,以及商议合约和向其他节点付费。数据的安全性由数据分片(data sharding)和端到端加密提供,数据的完整性由可复原性证明(proof of retrievability)提供。

医疗

医院与医保医药公司,不同医院之间,甚至医院里不同部门之间的数据流动性往往很差。考虑到医疗健康数据的敏感性,笔者认为,如果能够满足数据访问权、使用权等规定的基础上促进医疗数据的提取和流动,区块链将在医疗行业获得一定的用武之地。

GemHealth 项目由区块链公司 Gem 于 2016 年 4 月提出,其目标除了用区块链存储医疗记录或数据,还包括借助区块链增强医疗健康数据在不同机构不同部门间的安全可转移性、促进全球病人身份识别、医疗设备数据安全收集与验证等。项目已与医疗行业多家公司签订了合作协议。

通信和社交

BitMessage 是一套去中心化通信系统,在点对点通信的基础上保护用户的匿名性和信息的隐私。BitMessage 协议在设计上充分参考了比特币,二者拥有相似的地址编码机制和消息传递机制。BitMessage 也用“工作量证明”机制防止通信网络受到大量垃圾信息的冲击。

类似的,Twister 是一套去中心化的“微博”系统,Dot-Bit 是一套去中心化的 DNS 系统。

投票

Follow My Vote 项目致力于提供一个安全、透明的在线投票系统。通过使用该系统进行选举投票,投票者可以随时检查自己选票的存在和正确性,看到实时记票结果,并在改变主意时修改选票。

该项目使用区块链进行记票,并开源其软件代码供社区用户审核。项目也为投票人身份认证、防止重复投票、投票隐私等难点问题提供了解决方案。

预测

Augur 是一个运行在以太坊上的预测市场平台。使用 Augur,来自全球不同地方的任何人都可发起自己的预测话题市场,或随意加入其他市场,来预测一些事件的发展结果。预测结果和奖金结算由智能合约严格控制,使得在平台上博弈的用户不用为安全性产生担忧。

电子游戏

2017年3月,来自马来西亚的电子游戏工作室Xhai Studios宣布将区块链技术引入其电子游戏平台。工作室旗下的一些游戏将支持与NEM区块链的代币XEM整合。通过这一平台,游戏开发者可以在游戏架构中直接调用支付功能,消除对第三方支付的依赖;玩家则可以自由地将XEM和游戏内货币、点数等进行双向兑换。

小结

以上介绍了大量基于区块链技术的应用案例和场景,展现了区块链以及基于区块链的分布式账本技术所具有的巨大市场潜力。

当然,任何事物的发展都不是一帆风顺的。目前来看,制约区块链技术进一步落地的因素有很多。比如如何来为区块链上的合同担保?特别在金融、法律等领域,实际执行的时候往往还需要线下机制来配合;另外就是基于区块链系统的价值交易,必须要实现物品价值的数字化,非数字化的物品很难直接放到数字世界中进行管理。

这些问题看起来都不容易很快得到解决。但笔者相信,一门新的技术能否站住脚,根本在于它能否最终提高生产力,而区块链技术已经证明了这一点。随着生态的进一步成熟,区块链技术必将在更多领域获得用武之地。

分布式核心问题

随着摩尔定律遇到瓶颈,越来越多情况下要依靠分布式架构,才能实现海量数据处理能力和可扩展计算能力。

区块链系统,首先是一个分布式系统。传统单节点结构演变到分布式系统,碰到的首要问题就是一致性的保障。很显然,如果分布式集群无法保证处理结果保持一致的话,那人和建立于其上的业务系统都无法正常工作。

此处将介绍分布式系统领域的核心问题,包括一致性、共识的定义,基本的原理和算法,另外介绍一些评估分布式系统可靠性的指标。

一致性问题

一致性问题是分布式领域最为基础也是最为重要的问题。如果分布式系统能实现“一致”,对外就可以呈现为一个完美的、可扩展的“虚拟节点”,相对物理节点具备更优越的性能和稳定性。这也是分布式系统希望能实现的最终目标。

问题与挑战

  • 节点之间的网络通信是不可靠的,包括消息延迟、乱序和内容错误等。
  • 节点的处理时间无法保障,结果可能出现错误,甚至节点自身可能发生宕机。
  • 同步调用可以简化设计,但会严重降低分布式系统的可扩展性,甚至使其退化为单点系统。

一致性要求

  • 可终止性(termination):一致的结果在有限时间内能完成
  • 约同性(agreement):不同节点最终完成决策的结果是相同的
  • 合法性(validity):决策的结果必须是某个节点提出的提案

共识算法

共识(consensus)在很多时候会与一致性(consistency)术语放在一起讨论。严谨地讲,两者含义并不完全相同。

一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一直行、线性一致性,描述了多个节点对数据状态的维护能力。而共识则描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。因此,一致性描述的是结果状态,共识则是一种手段。达成某种共识并不意味着就保障了一致性。

实践中,要保障系统满足不同程度的一致性,核心过程我那个网需要通过共识算法来达成。共识算法解决的是对某个天大家达成一致意见的过程。

问题与挑战

如果分布式系统中哥哥单节点都能保证以十分完美的性能(瞬间相应、超高吞吐)无故障运行,节点之间通信瞬时送达,则实现共识过程并不十分复杂,简单地通过广播进行瞬时投票和应答即可。

然而现实中,这样的“理想”情况并不存在。不同节点之间通信存在延迟(光速物理限制,通信处理延迟),并且任意环节都可能存在故障(系统规模越大,发生故障可能性越高)。如通信网络会发生中断、节点发生故障、甚至存在恶意节点故意伪造消息,破坏系统正常工作流程。

一般来说,把出现故障(crash 或 fail-stop,即不响应)但不会伪造信息的情况成为“非拜占庭错误”(non-Byzantine Fault)或“故障错误”(Crash Fault);伪造信息恶意响应的情况称为“拜占庭错误”(Byzantine Fault),对应节点为拜占庭节点。

常见算法

根据解决的是非拜占庭错误情况还是拜占庭错误情况,共识算法可以分为 Crash Fault Tolerance(CFT)类算法和 Byzantine Fault Tolerance(BFT)类算法。

针对常见的非拜占庭错误情况,已经存在一些经典的解决算法,包括 Paxos、Raft 及其变种等。这类容错算法往往性能比较好,处理较快,容忍不超过一半的故障节点。

对于要能容忍拜占庭错误的情况,一般包括 PBFT(Practical Byzantine Fault Tolerance)为代表的确定性系列算法、PoW 为代表的概率算法等。对于确定性算法,一旦达成对某个结果的共识就不可逆转,即共识是最终结果;对于概率类算法,共识结果则是临时的,随着时间推移或某种强化,共识结果被推翻的概率越来越小,成为事实上的最终结果。拜占庭类容错算法往往性能较差,容忍不超过1/3的故障节点。

此外,XFT(Cross Fault Tolerance)等最近提出的改进算法可以提供类似 CFT 的处理响应速度,并能在大多数节点正常工作时提供 BFT 保障。

理论界限

FLP 不可能原理:即便在网络通信可靠情况下,可扩展的分布式系统的共识问题,其通用解法的理论下限是——没有下限(无解)。

FLP 不可能原理

定义

在网络可靠,但允许节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性共识算法。

FLP 不可能原理实际上告诉人们,不要浪费时间,去为异步分布式系统设计在任意场景下都能实现共识的算法。

正确理解

要理解 FLP,首先要搞清楚“异步”的含义。在分布式系统中,同步和异步这两个属于存在特殊的含义。

同步是指系统中的各个节点的时钟误差存在上线;并且消息传递必须在一定时间内完成,否则认为失败;同时各个节点完成处理消息的时间是一定的。对于同步系统,可以很容易地判断消息是否丢失。

异步是指系统中各个节点可能存在较大的时钟差异,同时消息传输时间是任意长的,各节点对消息进行处理的时间也可能是任意长的,这就造成无法判断某个消息迟迟没有响应是哪里出了问题(节点故障还是传输故障?)。不幸的是,现实生活中的系统往往都是异步系统。

FLP不可能性在原始论文中以图论的形式进行了严格证明。要理解这一基本原理并不复杂,一个不严谨的例子如下。

三个人在不同房间进行投票(投票结果是0或者1)。彼此可以通过电话进行沟通,但经常有人会时不时睡着。比如某个时候,A 投票0,B 投票1,C 收到了两人的投票,然后 C 睡着了。此时,A 和 B 将永远无法在有限时间内获知最终的结果,究竟是 C 没有应答还是应答的时间过长。如果可以重新投票,则类似情形可以在每次取得结果前发生,这将导致共识过程永远无法完成。

FLP 原理实际上说明对于允许节点失效情况下,纯粹异步系统无法确保一致性在有限时间内完成。即便对于非拜占庭错误的前提下,包括 Paxos、Raft 等算法也都存在无法达成共识的情况,只是在工程实践中这种情况出现的概率很小。

那么,FLP不可能原理是否意味着研究共识算法压根没有意义?

先别这么悲观。学术界做研究,往往考虑地是数学和物理意义上最极端的情形,很多时候现实生活要美好得多(感谢这个世界如此鲁棒!)。例如,上面例子中描述的最坏情形,每次都发生的概率其实并没有那么大。工程实现上多尝试几次,很大可能就成功了。

科学告诉你什么是不可能的;工程则告诉你,付出一些代价,可以把它变成可行。这就是科学和工程不同的魅力。

那么,退一步讲,在付出一些代价的情况下,我们在共识的达成上,能做到多好?回答这一问题的是另一个很出名的原理:CAP 原理。

提示:科学告诉你去赌场赌博从概率上总会是输钱的;工程则告诉你,如果你愿意接受最终输钱的风险,中间说不定能偶尔小赢几笔呢!

CAP 原理

CAP 原理最早是 2000 年由 Eric Brewer 在 ACM 组织的一个研讨会上提出猜想,后来 Lynch 等人进行了证明。该原理被认为是分布式系统领域的重要原理之一。

定义

CAP 原理:分布式计算系统不可能同时确保以下三个特性:一致性(Consistency)、可用性(Availability)和分区容忍性(Partition),设计中往往需要弱化对某个特性的保证。

这里,一致性、可用性和分区容忍性的含义如下:

  • 一致性:任何操作应该都是原子的,发生在后面的事件能看到前面事件发生导致的结果,注意这里指的是强一致性;

  • 可用性:在有限时间内,任何非失败节点都能应答请求;

  • 分区容忍性:网络可能发生分区,即节点之间的通信不可保障。

比较直观地理解如下,当网络可能出现分区的时候,系统是无法同时保证一致性和可用性的。要么,节点收到请求后因为没有得到其他节点的确认而不应答(牺牲可用性),要么节点只能应答非一致的结果(牺牲一致性)。

由于大多数时候网络被认为是可靠的,因此系统可以提供一致可靠的服务;当网络不可靠时,系统要么牺牲掉一致性(多数场景下),要么牺牲掉可用性。

注意:网络分区是可能存在的,出现分区情况后很可能会导致发生“脑裂”,多个新出现的主节点可能会尝试关闭其他主节点。

应用场景

既然 CAP 三种特性不可同时得到保障,则设计系统时必然要弱化对某个特性的支持。那么可能出现下面三个应用场景。

弱化一致性

对结果一致性不敏感的应用,可以允许在新版本上线后过一段时间才最终更新成功,期间不保证一致性。例如网站静态页面内容、实时性较弱的查询类数据库等,简单分布式同步协议如 Gossip,以及 CouchDB、Cassandra 数据库等,都是为此设计的。

弱化可用性

对结果一致性很敏感的应用,例如银行取款机,当系统故障时候会拒绝服务。MongoDB、Redis、MapReduce 等是为此设计的。Paxos、Raft 等共识算法,主要处理这种情况。在 Paxos 类算法中,可能存在着无法提供可用结果的情形,同时允许少数节点离线。

弱化分区容忍性

现实中,网络分区出现概率较小,但较难完全避免。两阶段的提交算法,某些关系型数据库及 ZooKeeper 主要考虑了这种设计。实践中,网络可以通过双通道等机制增强可靠性,达到高稳定的网络通信。

ACID原则

ACID 原则指的是:Atomicity(原子性)、Consistency(一致性)、Isolation(隔离性)、Durability(持久性),用了四种特性的缩写。

ACID 也是一种比较出名的描述一致性的原则,通常出现在分布式数据库领域。具体来说,ACID 原则描述了分布式数据库需要满足的一致性需求,同时允许付出可用性的代价。

ACID 特征如下:

  • Atomicity:每次操作是原子的,要么成功,要么不执行;

  • Consistency:数据库的状态是一致的,无中间状态;

  • Isolation:各种操作彼此之间互相不影响;

  • Durability:状态的改变是持久的,不会失效。

与 ACID 相对的一个原则是 BASE(Basic Availability,Soft-state,Eventual Consistency)原则,牺牲掉对一致性的约束(但实现最终一致性),来换取一定的可用性。

注意:ACID 和 BASE 在英文中分别是“酸”和“碱”,看似对立,实则是分别对 CAP 三特性的不同取舍。

Paxos 算法与 Raft 算法

Paxos 问题是指分布式的系统中存在故障(crash fault),但不存在恶意(corrupt)节点的场景(即可能消息丢失或重复,但无错误消息)下的共识达成问题。这也是分布式共识领域最为常见的问题。解决 Paxos 问题的算法主要有 Paxos 系列算法和 Raft 算法。

Paxos 算法

1990 年由 Leslie Lamport 在论文《The Part-time Parliament》中提出的 Paxos 共识算法,在工程角度实现了一种最大化保障分布式系统一致性(存在极小的概率无法实现一致)的机制。Paxos 算法被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。Leslie Lamport 作为分布式系统领域的早期研究者,因为相关成果获得了 2013 年度图灵奖。

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决,如何达成统一的结果。他们之间通过服务人员来传递纸条,但法官可能离开或进入大厅,服务人员可能偷懒去睡觉。

Paxos 是第一个广泛应用的共识算法,其原理基于“两阶段提交”算法并进行泛化和扩展,通过消息传递来逐步消除系统中的不确定状态,是后来不少共识算法(如 Raft、ZAB 等)设计的基础。Paxos 算法基本思想并不复杂,但最初论文描述得比较难懂,后来在 2001 年 Leslie Lamport 还专门写了论文《Paxos Made Simple》予以解释。

算法的基本原理是将节点分为三种逻辑角色,在实现上同一个节点可以担任多个角色:

  • Proposer(提案者):提出一个提案,等待大家批准(chosen)为结案(value)。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任该角色;

  • Acceptor(接受者):负责对提案进行投票,接受(accept)提案。往往由服务端担任该角色;

  • Learner(学习者):获取批准结果,并可以帮忙传播,不参与投票过程。可能为客户端或服务端。

算法需要满足Safety和Liveness两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的:

  • Safety 约束:保证决议(value)结果是对的,无歧义的,不会出现错误情况。
1
2
· 只有是被Proposers提出的提案才可能被最终批准;
· 在一次执行中,只批准(chosen)一个最终决议。被多数接受(accept)的结果成为决议;
  • Liveness约束:保证决议过程能在有限时间内完成。
1
· 决议总会产生,并且学习者能获得被批准的决议。

基本过程是多个提案者先争取到提案的权利(得到大多数接受者的支持);得到提案权利的提案者发送提案给所有人进行确认,得到大部分人确认的提案成为批准的结案。

Paxos 不保证系统随时处在一致的状态。但由于每次达成一致的过程中至少有超过一半的节点参与,这样最终整个系统都会获知共识的结果。一个潜在的问题是 Proposer 在此过程中出现故障,可以通过超时机制来解决。极为凑巧的情况下,每次新一轮提案的 Proposer 都恰好故障,又或者两个 Proposer 恰好依次提出更新的提案,则导致活锁,系统永远无法达成一致(实际发生概率很小)。

Paxos 能保证在超过一半的节点正常工作时,系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案,会发现在满足各种约束情况下,算法过程会十分类似于 Paxos 的过程。

下面,由简单情况逐步推广到一般情况来探讨算法过程。

单个提案者+多接受者

如果系统中限定只有某个特定节点是提案者,那么共识结果很容易能达成(只有一个方案,要么达成,要么失败)。提案者只要收到了来自多数接受者的投票,即可认为通过,因为系统中不存在其他的提案。

但此时一旦提案者故障,则系统无法工作。

多个提案者+单个接受者

限定某个节点作为接受者。这种情况下,共识也很容易达成,接受者收到多个提案,选第一个提案作为决议,发送给其他提案者即可。

缺陷也是容易发生单点故障,包括接受者故障或首个提案者节点故障。

以上两种情形其实类似主从模式,虽然不那么可靠,但因为原理简单而被广泛采用。

当提案者和接受者都推广到多个的情形,会出现一些挑战。

多个提案者+多个接受者

既然限定单提案者或单接受者都会出现故障,那么就得允许出现多个提案者和多个接受者。问题一下子变得复杂了。

一种情况是同一时间片段(如一个提案周期)内只有一个提案者,这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生,例如按照时间、序列、或者大家猜拳(出一个参数来比较)之类。考虑到分布式系统要处理的工作量很大,这个过程要尽量高效,满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案,怎么对他们进行区分呢?这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的,提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大(往往意味着是接受新提出的,因为旧提案者故障概率更大)的提案。

如何为提案分配序号呢?一种可能方案是每个节点的提案数字区间彼此隔离开,互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

同时允许多个提案意味着很可能单个提案人无法集齐足够多的投票;另一方面,提案者即便收到了多数接受者的投票,也不敢说就一定通过。因为在此过程中投票者无法获知其他投票人的结果,也无法确认提案人是否收到了自己的投票。因此,需要实现两个阶段的提交过程。

两阶段的提交

提案者发出提案申请之后,会收到来自接受者的反馈。一种结果是提案被大多数接受者接受了,一种结果是没被接受。没被接受的话,可以过会再重试。即便收到来自大多数接受者的答复,也不能认为就最终确认了。因为这些接受者并不知道自己刚答复的提案是否可以构成大多数的一致意见。

很自然,需要引入新的一个阶段,即提案者在第一阶段拿到所有的反馈后,需要再次判断这个提案是否得到大多数的支持,如果支持则需要对其进行最终确认。

Paxos里面对这两个阶段分别命名为准备(Prepare)阶段和提交(Commit)阶段。准备阶段通过锁来解决对哪个提案内容进行确认的问题,提交阶段解决大多数确认最终值的问题。

准备阶段:

  • 提案者发送自己计划提交的提案的编号到多个接收者,试探是否可以锁定多数接收者的支持;

  • 接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到提案号比目前保留的最大提案号还大,则返回自己已接受的提案值(如果还未接受过任何提案,则为空)给提案者,更新当前最大提案号,并说明不再接受小于最大提案号的提案。

提交阶段:

  • 提案者如果收到大多数的回复(表示大部分人听到它的请求),则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案,说明锁定成功。则使用自己的提案内容;如果返回中有提案内容,则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复,则需要再次发出请求;

  • 接受者收到“接受消息”后,如果发现提案号不小于已接受的最大提案号,则接受该提案,并更新接受的最大提案。

一旦多数接受者接受了共同的提案值,则形成决议,成为最终确认。

Raft算法

Paxos 算法的设计并没有考虑到一些优化机制,同时论文中也没有给出太多实现细节,因此后来出现了不少性能更优化的算法和实现,包括Fast Paxos、Multi-Paxos 等。最近出现的 Raft 算法,算是对 Multi-Paxos 的重新简化设计和实现,相对也更容易理解。

Raft 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年在论文《In Search of an Understandable Consensus Algorithm》中提出。Raft 算法面向对多个决策达成一致的问题,分解了 Leader 选举、日志复制和安全方面的考虑,并通过约束减少了不确定性的状态空间。

Raft算法包括三种角色:Leader(领导者)、Candidate(候选领导者)和Follower(跟随者),决策前通过选举一个全局的 Leader 来简化后续的决策过程。Leader 角色十分关键,决定日志(log)的提交。日志只能由 Leader 向 Follower 单向复制。

典型的过程包括以下两个主要阶段:

  • Leader 选举:开始所有节点都是 Follower,在随机超时发生后未收到来自 Leader 或 Candidate 消息,则转变角色为 Candidate,提出选举请求。最近选举阶段(Term)中得票超过一半者被选为 Leader;如果未选出,随机超时后进入新的阶段重试。Leader 负责从客户端接收 log,并分发到其他节点;

  • 同步日志:Leader 会找到系统中日志最新的记录,并强制所有的 Follower 来刷新到这个记录,数据的同步是单向的。

注意:此处日志并非是指输出消息,而是各种事件的发生记录。

拜占庭问题与算法

拜占庭问题(Byzantine Problem)更为广泛,讨论的是允许存在少数节点作恶(消息可能被伪造)场景下的一致性达成问题。拜占庭容错(Byzantine Fault Tolerant,BFT)算法讨论的是在拜占庭情况下对系统如何达成共识。

两将军问题

在拜占庭将军问题之前,就已经存在两将军问题(Two Generals Paradox):两个将军要通过信使来达成进攻还是撤退的约定,但信使可能迷路或被敌军阻拦(消息丢失或伪造),如何达成一致?根据 FLP 不可能原理,这个问题无通用解。

拜占庭问题

拜占庭问题又叫拜占庭将军问题(Byzantine Generals Problem),是 Leslie Lamport 等科学家于 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都,由于地域宽广,守卫边境的多个将军(系统中的多个节点)需要通过信使来传递消息,达成某些一致的决定。但由于将军中可能存在叛徒(系统中节点出错),这些叛徒将努力向不同的将军发送不同的消息,试图干扰共识的达成。拜占庭问题即为在此情况下,如何让忠诚的将军们能达成行动的一致。

论文中指出,对于拜占庭问题来说,假如节点总数为N,叛变将军数为F,则当 N ≥ 3F+1 时,问题才有解,由 BFT 算法进行保证。

例如,N = 3,F = 1 时。

提案人不是叛变者,提案人发送一个提案出来,叛变者可以宣称收到的是相反的命令。则对于第三个人(忠诚者)收到两个相反的消息,无法判断谁是叛变者,则系统无法达到一致。

提案人是叛变者,发送两个相反的提案分别给另外两人,另外两人都收到两个相反的消息,无法判断究竟谁是叛变者,则系统无法达到一致。

更一般的,当提案人不是叛变者,提案人提出提案信息 1,则对于合作者来看,系统中会有 N-F 份确定的信息 1,和 F 份不确定的信息(可能为 0 或 1,假设叛变者会尽量干扰一致的达成),N-F > F,即 N > 2F 情况下才能达成一致。

当提案人是叛变者,会尽量发送相反的提案给N-F个合作者,从收到1的合作者看来,系统中会存在(N-F)/2 个信息 1,以及(N-F)/2 个信息 0;从收到 0 的合作者看来,系统中会存在(N-F)/2 个信息 0,以及(N-F)/2 个信息 1;另外存在 F-1 个不确定的信息。合作者要想达成一致,必须进一步对所获得的消息进行判定,询问其他人某个被怀疑对象的消息值,并通过取多数来作为被怀疑者的信息值。这个过程可以进一步递归下去。

Leslie Lamport 等人在论文《Reaching agreement in the presence of faults》中证明,当叛变者不超过 1/3 时,存在有效的拜占庭容错算法(最坏需要 F+1 轮交互)。反之,如果叛变者过多,超过 1/3,则无法保证一定能达到一致结果。

那么,当存在多于 1/3 的叛变者时,有没有可能存在解决方案呢?

设想 F 个叛变者和 L 个忠诚者,叛变者故意使坏,可以给出错误的结果,也可以不响应。某个时候 F 个叛变者都不响应,则 L 个忠诚者取多数即能得到正确结果。当 F 个叛变者都给出一个恶意的提案,并且 L 个忠诚者中有 F 个离线时,剩下的 L-F 个忠诚者此时无法分别是否混入了叛变者,仍然要确保取多数能得到正确结果,因此,L-F > F,即 L > 2F 或 N-F > 2F,所以系统整体规模N要大于3F。

能确保达成一致的拜占庭系统节点数至少为 4,此时最多允许出现 1 个坏的节点。

拜占庭容错算法

拜占庭容错算法(Byzantine Fault Tolerant,BFT)是面向拜占庭问题的容错算法,解决的是在网络通信可靠但节点可能故障情况下如何达成共识。拜占庭容错算法最早的讨论在 1980 年 Leslie Lamport 等人发表的论文《Polynomial Algorithms for Byzantine Agreement》,之后出现了大量的改进工作。长期以来,拜占庭问题的解决方案都存在复杂度过高的问题,直到PBFT算法的提出。

1999 年,Castro和Liskov于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出的 Practical Byzantine Fault Tolerant(PBFT)算法,基于前人工作进行了优化,首次将拜占庭容错算法复杂度从指数级降低到了多项式级,目前已得到广泛应用。其可以在失效节点不超过总数 1/3 的情况下同时保证 Safety 和 Liveness。

PBFT算法采用密码学相关技术(RSA签名算法、消息验证编码和摘要)确保消息传递过程无法被篡改和破坏。

算法的基本过程如下:

  • 首先通过轮换或随机算法选出某个节点为主节点,此后只要主节点不切换,则称为一个视图(View);
  • 在某个视图中,客户端将请求(REQUEST,operation,timestamp,client)发送给主节点,主节点负责广播请求到所有其他副本节点;
  • 所有节点处理完成请求,将处理结果(REPLY,view,timestamp,client,id_node,response)返回给客户端。客户端检查是否收到了至少f+1个来自不同节点的相同结果,作为最终结果。

主节点广播过程包括三个阶段的处理:预准备(pre-prepare)阶段、准备(prepare)阶段和提交(commit)阶段。预准备和准备阶段确保在同一个视图内请求发送的顺序正确;准备和提交阶段则确保在不同视图之间的确认请求是保序的;

  • 预准备阶段:主节点为从客户端收到的请求分配提案编号,然后发出预准备消息(PRE-PREPARE,view,n,digest,message)给各副本节点,其中 message 是客户端的请求消息,digest是消息的摘要;

  • 准备阶段:副本节点收到预准备消息后,检查消息合法,如检查通过则向其他节点发送准备消息(PREPARE,view,n,digest,id),带上自己的 id 信息,同时接收来自其他节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少 2f + 1 个验证过的消息才进入准备状态;

  • 提交阶段:广播 commit 消息,告诉其他节点某个提案n在视图v里已经处于准备状态。如果集齐至少 2f + 1 个验证过的 commit 消息,则说明提案通过。

具体实现上还包括视图切换、checkpoint 机制等,可自行参考论文内容,在此不再赘述。

新的解决思路

拜占庭问题之所以难解,在于任何时候系统中都可能存在多个提案(因为提案成本很低),并且要完成最终一致性确认过程十分困难,容易受干扰。

比特币的区块链网络在设计时提出了创新的 PoW(Proof of Work)概率算法思路,针对这两个环节进行了改进。

首先,限制一段时间内整个网络中出现提案的个数(通过增加提案成本);其次是放宽对最终一致性确认的需求,约定好大家都确认并沿着已知最长的链进行拓展。系统的最终确认是概率意义上的存在。这样,即便有人试图恶意破坏,也会付出相应的经济代价(超过整体系统一半的计算力)。

后来的各种 PoX 系列算法,也都是沿着这个思路进行改进,采用经济上的惩罚来制约破坏者。

可靠性指标

可靠性(availability),或者说可用性,是描述系统可以提供服务能力的重要指标。高可靠的分布式系统往往需要各种复杂的机制来进行保障。

通常情况下,服务的可用性可以用服务承诺(Service Level Agreement,SLA SLA)、服务指标(Service Level Indicator,SLI)、服务目标(Service Level Objective,SLO)等方面进行衡量。

几个9的指标

很多领域里谈到服务的高可靠性,都喜欢用几个9的指标来进行衡量。几个 9,其实是概率意义上粗略反映了系统能提供服务的可靠性指标,最初是电信领域提出的概念。

下表给出同指标下每年允许服务出现不可用时间的参考值。

同指标下,每年允许服务出现不可用时间的参考值

一般来说,单点的服务器系统至少应能满足两个 9;普通企业信息系统三个 9 就肯定足够了(大家可以统计下自己企业内因系统维护每年要停多少时间),系统能达到四个 9 已经是领先水平了(参考 AWS 等云计算平台)。电信级的应用一般需要能达到五个 9,这已经很厉害了,一年里面最多允许出现五分钟左右的服务不可用。六个 9 以及以上的系统,就更加少见了,要实现往往意味着极高的代价。

两个核心时间

一般地,描述系统出现故障的可能性和故障出现后的恢复能力,有两个基础的指标:MTBF 和 MTTR

  • MTBF(Mean Time Between Failures):平均故障间隔时间,即系统可以无故障运行的预期时间;

  • MTTR(Mean Time to Repair):平均修复时间,即发生故障后,系统可以恢复到正常运行的预期时间。

MTBF 衡量了系统发生故障的频率,如果一个系统的MTBF很短,则往往意味着该系统可用性低;而 MTTR 则反映了系统碰到故障后服务的恢复能力,如果系统的 MTTR 过长,则说明系统一旦发生故障,需要较长时间才能恢复服务。

一个高可用的系统应该是具有尽量长的 MTBF 和尽量短的 MTTR。

提高可靠性

如何提升系统的可靠性呢?有两个基本思路:一是让系统中的单个组件都变得更可靠;二是干脆消灭单点。

IT 从业人员大都有类似的经验,普通笔记本电脑,基本上是过一阵可能就要重启一下;而运行 Linux/Unix 系统的专用服务器,则可能连续运行几个月甚至几年时间都不出问题。另外,普通的家用路由器,跟生产级别路由器相比,更容易出现运行故障。这些都是单个组件可靠性不同导致的例子,可以通过简单升级单点的软硬件来改善可靠性。

然而,依靠单点实现的可靠性毕竟是有限的。要想进一步地提升,那就只好消灭单点,通过主从、多活等模式让多个节点集体完成原先单点的工作。这可以从概率意义上改善服务对外的整体可靠性,这也是分布式系统的一个重要用途。

小结

分布式系统是计算机科学中十分重要的一个研究领域。随着现代计算机集群规模的不断增长,所处理的数据量越来越大,同时对于性能、可靠性的要求越来越高,分布式系统相关技术已经变得越来越重要,起到的作用也越来越关键。

分布式系统中如何保证共识是个经典的技术问题,无论在学术上还是工程上都存在很高的研究价值。令人遗憾地是,理想的(各项指标均最优)解决方案并不存在。在现实各种约束条件下,往往需要通过牺牲掉某些需求,来设计出满足特定场景的协议。通过本文的学习,读者可以体会到在工程应用中的类似设计技巧。

实际上,工程领域中不少问题都不存在一劳永逸的通用解法;而实用的解决思路是,合理地在实际需求和条件限制之间进行灵活的取舍。

密码学与安全技术

工程领域从来没有黑科技;密码学不仅是工程。

密码学相关的安全技术在整个信息技术领域的重要地位无需多言。如果没有现代密码学和信息安全的研究成果,人类社会根本无法进入信息时代。区块链技术大量依赖了密码学和安全技术的研究成果。

实际上,密码学和安全领域所涉及的知识体系十分繁杂,本章将介绍密码学领域中跟区块链相关的一些基础知识,包括Hash算法与数字摘要、加密算法、数字签名、数字证书、PKI体系、Merkle树、布隆过滤器、同态加密等。读者通过阅读本章可以了解如何使用这些技术保护信息的机密性、完整性、认证性和不可抵赖性。

Hash算法与数字摘要

Hash定义

Hash(哈希或散列)算法是非常基础也非常重要的计算机算法,它能将任意长度的二进制明文串映射为较短的(通常是固定长度的)二进制串(Hash值),并且不同的明文很难映射为相同的Hash值。

例如计算一段话“hello blockchain world,this is yeasy@github”的 SHA-256 Hash 值。

1
2
$ echo "hello blockchain world, this is yeasy@github"|shasum -a 256
db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90

这意味着对于某个文件,无需查看其内容,只要其 SHA-256 Hash 计算后结果同样为db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90,则说明文件内容极大概率上就是“hello blockchain world,this is yeasy@github”。

Hash 值在应用中又常被称为指纹(fingerprint)或摘要(digest)。Hash 算法的核心思想也经常被应用到基于内容的编址或命名算法中。

一个优秀的 Hash 算法将能实现如下功能:

  • 正向快速:给定明文和 Hash 算法,在有限时间和有限资源内能计算得到 Hash 值;

  • 逆向困难:给定(若干)Hash 值,在有限时间内很难(基本不可能)逆推出明文;

  • 输入敏感:原始输入信息发生任何改变,新产生的 Hash 值都应该出现很大不同;

  • 冲突避免:很难找到两段内容不同的明文,使得它们的 Hash 值一致(发生碰撞)。

冲突避免有时候又称为“抗碰撞性”,分为“弱抗碰撞性”和“强抗碰撞性”。如果给定明文前提下,无法找到与之碰撞的其他明文,则算法具有“弱抗碰撞性”;如果无法找到任意两个发生 Hash 碰撞的明文,则称算法具有“强抗碰撞性”。

很多场景下,也往往要求算法对于任意长的输入内容,可以输出定长的 Hash 值结果。

常见算法

目前常见的 Hash 算法包括 MD5 和 SHA 系列算法。

  • MD4(RFC 1320)是 MIT 的 Ronald L.Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已被证明不够安全。

  • MD5(RFC 1321)是 Rivest 于 1991 年对 MD4 的改进版本。它对输入仍以 512 位进行分组,其输出是 128 位。MD5 比 MD4 更加安全,但过程更加复杂,计算速度要慢一点。MD5 已被证明不具备“强抗碰撞性”。

  • SHA(Secure Hash Algorithm)并非一个算法,而是一个 Hash 函数族。NIST(National Institute of Standards and Technology)于 1993 年发布其首个实现。目前知名的 SHA-1 算法在 1995 年面世,它的输出为长度 160 位的 Hash 值,抗穷举性更好。SHA-1 设计时模仿了 MD4 算法,采用了类似原理。SHA-1 已被证明不具备“强抗碰撞性”。

为了提高安全性,NIST 还设计出了 SHA-224、SHA-256、SHA-384 和 SHA-512 算法(统称为SHA-2),跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

目前,MD5 和 SHA1 已经被破解,一般推荐至少使用 SHA2-256 或更安全的算法。

提示:MD5 是一个经典的 Hash 算法,但和 SHA-1 算法一起都被认为安全性已不足应用于商业场景。

性能

Hash 算法一般都是计算敏感型的。意味着计算资源是瓶颈,主频越高的 CPU 运行 Hash 算法的速度也越快。因此可以通过硬件加速来提升 Hash 计算的吞吐量。例如采用 FPGA 来计算 MD5 值,可以轻易达到数十 Gbps 的吞吐量。

也有一些 Hash 算法不是计算敏感型的。例如 scrypt 算法,计算过程需要大量的内存资源,节点不能通过简单地增加更多 CPU 来获得 Hash 性能的提升。这样的 Hash 算法经常用在避免算力攻击的场景。

数字摘要

顾名思义,数字摘要是对数字内容进行 Hash 运算,获取唯一的摘要值来指代原始完整的数字内容。数字摘要是 Hash 算法最重要的一个用途。利用 Hash 函数的抗碰撞性特点,数字摘要可以解决确保内容未被篡改过的问题。

细心的读者可能会注意到,从网站下载软件或文件时,有时会提供一个相应的数字摘要值。用户下载原始文件后可以在本地自行计算摘要值,并与提供的摘要值进行比对,可检查文件内容是否被篡改过。

Hash 攻击与防护

Hash 算法并不是一种加密算法,不能用于对信息的保护。但 Hash 算法常用于对口令的保存上。例如用户登录网站需要通过用户名和密码来进行验证。如果网站后台直接保存用户的口令明文,一旦数据库发生泄露后果不堪设想。大量用户倾向于在多个网站选用相同或关联的口令。

利用 Hash 的特性,后台可以仅保存口令的 Hash 值,这样每次比对 Hash 值一致,则说明输入的口令正确。即便数据库泄露了,也无法从 Hash 值还原回口令,只有进行穷举测试。

然而,由于有时用户设置口令的强度不够,只是一些常见的简单字符串,如 password、123456等。有人专门搜集了这些常见口令,计算对应的 Hash 值,制作成字典。这样通过 Hash 值可以快速反查到原始口令。这一类型以空间换时间的攻击方法包括字典攻击和彩虹表攻击(只保存一条 Hash 链的首尾值,相对字典攻击可以节省存储空间)等。

为了防范这一类攻击,一般采用加盐(salt)的方法。保存的不是口令明文的 Hash 值,而是口令明文再加上一段随机字符串(即“盐”)之后的 Hash 值。Hash 结果和“盐”分别存放在不同的地方,这样只要不是两者同时泄露,攻击者就很难破解了。

加密算法

加解密算法是密码学的核心技术,从设计理念上可以分为两大基本类型,如下表所示。

加解密算法的类型  

加解密系统基本组成

现代加解密系统的典型组件一般包括:加解密算法、加密密钥、解密密钥。其中,加解密算法自身是固定不变的,并且一般是公开可见的;密钥则是最关键的信息,需要安全地保存起来,甚至通过特殊硬件进行保护。一般来说,对同一种算法,密钥需要按照特定算法每次加密前随机生成,长度越长,则加密强度越大。加解密的基本过程如下图所示。

加解密基本过程

加密过程中,通过加密算法和加密密钥,对明文进行加密,获得密文。

解密过程中,通过解密算法和解密密钥,对密文进行解密,获得明文。

根据加解密过程中所使用的密钥是否相同,算法可以分为对称加密(symmetric cryptography,又称公共密钥加密,common-key cryptography)和非对称加密(asymmetric cryptography,又称公钥加密,public-key cryptography)。两种模式适用于不同的需求,恰好形成互补。某些时候可以组合使用,形成混合加密机制。

并非所有加密算法的安全性都可以从数学上得到证明。公认的高强度的加密算法和实现往往经过长时间各方面充分实践论证后,才被大家所认可,但也不代表其绝对不存在漏洞。因此,自行设计和发明未经过大规模验证的加密算法是一种不太明智的行为。即便不公开算法加密过程,也很容易被攻破,无法在安全性上得到保障。

实际上,密码学实现的安全往往是通过算法所依赖的数学问题来提供,而并非通过对算法的实现过程进行保密。

对称加密算法

对称加密算法,顾名思义,加密和解密过程的密钥是相同的。该类算法优点是加解密效率(速度快,空间占用小)和加密强度都很高。缺点是参与方都需要提前持有密钥,一旦有人泄露则安全性被破坏;另外如何在不安全通道中提前分发密钥也是个问题,需要借助 Diffie–Hellman 协议或非对称加密方式来实现。

对称密码从实现原理上可以分为两种:分组密码和序列密码。前者将明文切分为定长数据块作为基本加密单位,应用最为广泛。后者则每次只对一个字节或字符进行加密处理,且密码不断变化,只用在一些特定领域,如数字媒介的加密等。

分组对称加密代表算法包括 DES、3DES、AES、IDEA 等:

  • DES(Data Encryption Standard):经典的分组加密算法,1977 年由美国联邦信息处理标准(FIPS)采用 FIPS-46-3,将 64 位明文加密为 64 位的密文,其密钥长度为 64 位(包含 8 位校验位)。现在已经很容易被暴力破解;详见

  • 3DES:三重DES操作,加密→解密→加密,处理过程和加密强度优于 DES,但现在也被认为不够安全;

  • AES(Advanced Encryption Standard):由美国国家标准研究所(NIST)采用,取代 DES 成为对称加密实现的标准,1997~2000 年 NIST 从 15 个候选算法中评选 Rijndael 算法(由比利时密码学家 Joan Daemon 和 Vincent Rijmen 发明)作为 AES,标准为 FIPS-197。AES 也是分组算法,分组长度为 128、192、256 位三种。AES 的优势在于处理速度快,整个过程可以用数学描述,目前尚未有有效的破解手段;详见

  • IDEA(International Data Encryption Algorithm):1991 年由密码学家 James Massey 与来学嘉联合提出。设计类似于 3DES,密钥长度增加到 128 位,具有更好的加密强度。

  • 序列密码,又称流密码。1949 年,Claude Elwood Shannon(信息论创始人)首次证明,要实现绝对安全的完善保密性(perfect secrecy),可以通过“一次性密码本”的对称加密处理。即通信双方每次使用跟明文等长的随机密钥串对明文进行加密处理。序列密码采用了类似的思想,每次通过伪随机数生成器来生成伪随机密钥串。代表算法包括RC4等。

对称加密算法适用于大量数据的加解密过程;不能用于签名场景;并且往往需要提前分发好密钥。

注意:分组加密每次只能处理固定长度的明文,因此对于过长的内容需要采用一定模式进行分割处理,《实用密码学》一书中推荐使用密文分组链(Cipher Block Chain,CBC)、计数器(Counter,CTR)等模式。

非对称加密算法

非对称加密是现代密码学历史上一项伟大的发明,可以很好地解决对称加密中提前分发密钥的问题。

顾名思义,非对称加密算法中,加密密钥和解密密钥是不同的,分别称为公钥(public key)和私钥(private key)。私钥一般需要通过随机数算法生成,公钥可以根据私钥生成。公钥一般是公开的,他人可获取的;私钥一般是个人持有,他人不能获取。

非对称加密算法的优点是公私钥分开,不安全通道也可使用。缺点是处理速度(特别是生成密钥和解密过程)往往比较慢,一般比对称加解密算法慢 2~3 个数量级;同时加密强度也往往不如对称加密算法。

非对称加密算法的安全性往往需要基于数学问题来保障,目前主要有基于大数质因子分解、离散对数、椭圆曲线等经典数学难题进行保护。

代表算法包括:RSA、ElGamal、椭圆曲线(Elliptic Curve Crytosystems,ECC)、SM2 等系列算法。

  • RSA:经典的公钥算法,1978 年由 Ron Rivest、Adi Shamir、Leonard Adleman 共同提出,三人于 2002 年因此获得图灵奖。算法利用了对大数进行质因子分解困难的特性,但目前还没有数学证明两者难度等价,或许存在未知算法在不进行大数分解的前提下解密;详见

  • Diffie-Hellman 密钥交换:基于离散对数无法快速求解,可以在不安全的通道上,双方协商一个公共密钥;

  • ElGamal:由 Taher ElGamal 设计,利用了模运算下求离散对数困难的特性。被应用在 PGP 等安全工具中;

  • 椭圆曲线算法(Elliptic Curve Cryptography,ECC):现代备受关注的算法系列,基于对椭圆曲线上特定点进行特殊乘法逆运算难以计算的特性。最早在1985年由Neal Koblitz和Victor Miller分别独立提出。ECC系列算法一般被认为具备较高的安全性,但加解密计算过程往往比较费时;

  • SM2(ShangMi 2):国家商用密码算法,由国家密码管理局于2010年12月17日发布,同样基于椭圆曲线算法,加密强度优于RSA系列算法。

非对称加密算法一般适用于签名场景或密钥协商,但不适于大量数据的加解密。

目前普遍认为RSA类算法可能在不远的将来被破解,一般推荐可采用安全强度更高的椭圆曲线系列算法。

选择明文攻击

在非对称加密中,由于公钥是公开可以获取的,因此任何人都可以给定明文,获取对应的密文,这就带来选择明文攻击的风险。

为了规避这种风险,现有的非对称加密算法(如RSA、ECC)都引入了一定的保护机制。对同样的明文使用同样密钥进行多次加密,得到的结果完全不同,这就避免了选择明文攻击的破坏。

在实现上可以有多种思路。一种是对明文先进行变形,添加随机的字符串或标记,再对添加后结果进行处理。另外一种是先用随机生成的临时密钥对明文进行对称加密,然后再对对称密钥进行加密,即混合利用多种加密机制。

混合加密机制

混合加密机制同时结合了对称加密和非对称加密的优点。

先用计算复杂度高的非对称加密协商出一个临时的对称加密密钥(也称为会话密钥,一般相对所加密内容来说要短得多),然后双方再通过对称加密算法对传递的大量数据进行快速的加解密处理。

典型的应用案例是现在大家常用的 HTTPS 协议。HTTPS 协议正在替换掉传统的不安全的 HTTP 协议,成为最普遍的 Web 通信协议。

HTTPS 在传统的 HTTP 层和 TCP 层之间通过引入 Transport Layer Security/Secure Socket Layer(TLS/SSL)加密层来实现可靠的传输。

SSL 协议最早是 Netscape 于 1994 年设计出来实现早期 HTTPS 的方案,SSL 3.0 及之前版本存在漏洞,被认为不够安全。TLS 协议是 IETF 基于 SSL 协议提出的安全标准,目前最新的版本为 1.2(2008年发布)。推荐使用的版本号至少为 TLS 1.0,对应到 SSL 3.1版本。除了 Web 服务外,TLS 协议也广泛应用于 Email、实时消息、音视频通话等领域。

采用 HTTPS 建立安全连接(TLS握手协商过程)的基本步骤如下(可参见图5-2):

TLS握手协商过程

客户端浏览器发送信息到服务器,包括随机数 R1、支持的加密算法类型、协议版本、压缩算法等。注意该过程为明文。
服务端返回信息,包括随机数 R2、选定加密算法类型、协议版本以及服务器证书。注意该过程为明文。
浏览器检查带有该网站公钥的证书。该证书需要由第三方CA来签发,浏览器和操作系统会预置权威 CA 的根证书。如果证书被篡改作假(中间人攻击),很容易通过 CA 的证书验证出来。
如果证书没问题,则客户端用服务端证书中的公钥加密随机数 R3(又叫 Pre-MasterSecret),发送给服务器。此时,只有客户端和服务器都拥有 R1、R2 和 R3 信息,基于随机数 R1、R2 和 R3,双方通过伪随机数函数来生成共同的对称会话密钥 MasterSecret。
后续客户端和服务端的通信都通过对称加密算法(如AES)进行保护。
可以看出,该过程的主要功能是在防止中间人窃听和篡改的前提下完成会话密钥的协商。为了保障前向安全性(perfect forward secrecy),TLS 对每个会话连接都可以生成不同的密钥,避免某次会话密钥泄露之后影响了其他会话连接的安全性。需要注意,TLS 协商过程支持加密算法方案较多,要合理地选择安全强度高的算法,如 DHE-RSA、ECDHE-RSA 和 ECDHE-ECDSA。

示例中对称密钥的协商过程采用了RSA非对称加密算法,实践中也可以通过 Diffie–Hellman 协议来完成。

离散对数与 Diffie–Hellman 密钥交换协议

Diffie–Hellman(DH)密钥交换协议是一个经典的协议,最早发表于 1976 年,应用十分广泛。使用该协议可以在不安全信道完成对称密钥的协商,以便后续通信采用对称加密。

DH 协议的设计基于离散对数问题(Discrete Logarithm Problem,DLP)。离散对数问题是指对于一个很大的素数 p,已知 g 为 p 的模循环群的原根,给定任意 x,求解 X = g^x mod p 是可以很快获取的。但在已知 p、g 和 X 的前提下,逆向求解 x 目前没有多项式时间实现的算法。该问题同时也是 ECC 类加密算法的基础。

DH 协议的基本交换过程如下:

  • Alice 和 Bob 两个人协商密钥,先公开商定 p,g;
  • Alice 自行选取私密的整数x,计算 X = g^x mod p,发送 X 给 Bob;
  • Bob 自行选取私密的整数 y,计算 Y = g^y mod p,发送 Y给 Alice;
  • Alice 根据 x 和 Y,求解共同密钥 Z_A = Y^x mod p;
  • Bob 根据 X 和 y,求解共同密钥 Z_B = X^y mod p。

实际上,Alice 和 Bob 计算出来的结果将完全相同,因为在 mod p 的前提下,Y^x = (g^y)^x = g^(xy) = (g^x)^y = X^y。而信道监听者在已知 p、g、X、Y 的前提下,无法求得 Z。

消息认证码与数字签名

消息认证码和数字签名技术通过对消息的摘要进行加密,可用于消息防篡改和身份证明问题。

消息认证码

消息认证码全称是“基于 Hash 的消息认证码”(Hash-based Message Authentication Code,HMAC)。消息验证码基于对称加密,可以用于对消息完整性(integrity)进行保护。

基本过程为:对某个消息利用提前共享的对称密钥和 Hash 算法进行加密处理,得到 HMAC 值。该 HMAC 值持有方可以证明自己拥有共享的对称密钥,并且也可以利用 HMAC 确保消息内容未被篡改。

典型的 HMAC(K,H,Message)算法包括三个因素,K 为提前共享的对称密钥,H 为提前商定的 Hash 算法(一般为公认的经典算法如SHA-256),Message 为要处理的消息内容。如果不知道 K 或 H 的任何一个,则无法根据 Message 得到正确的 HMAC 值。

消息认证码一般用于证明身份的场景。如 Alice、Bob 提前共享和 HMCA 的密钥和 Hash 算法,Alice 需要知晓对方是否为 Bob,可发送随机消息给 Bob。Bob 收到消息后进行计算,把消息 HMAC 值返回给 Alice,Alice 通过检验收到 HMAC 值的正确性可以知晓对方是否是 Bob。注意这里并没有考虑中间人攻击的情况,假定信道是安全的。

消息认证码使用过程中主要问题是需要共享密钥。当密钥可能被多方拥有的场景下,无法证明消息来自某个确切的身份。反之,如果采用非对称加密方式,则可以追溯到来源身份,即数字签名。

数字签名

与在纸质合同上签名确认合同内容和证明身份类似,数字签名基于非对称加密,既可以用于证实某数字内容的完整性,又同时可以确认来源(或不可抵赖,Non-Repudiation)。

一个典型的场景是,Alice 通过信道发给 Bob 一个文件(一份信息),Bob 如何获知所收到的文件即为 Alice 发出的原始版本?Alice 可以先对文件内容进行摘要,然后用自己的私钥对摘要进行加密(签名),之后同时将文件和签名都发给 Bob。Bob 收到文件和签名后,用 Alice 的公钥来解密签名,得到数字摘要,与收到文件进行摘要后的结果进行比对。如果一致,说明该文件确实是 Alice 发过来的(别人无法拥有 Alice 的私钥),并且文件内容没有被修改过(摘要结果一致)。

知名的数字签名算法包括 DSA(Digital Signature Algorithm)和安全强度更高的 ECSDA(Elliptic Curve Digital Signature Algorithm)等。

除普通的数字签名应用场景外,针对一些特定的安全需求,产生了一些特殊数字签名技术,包括盲签名、多重签名、群签名、环签名等。

盲签名

盲签名(blind signature)是在 1982 年由 David Chaum 在论文《Blind Signatures for Untraceable Payment》中提出。签名者需要在无法看到原始内容的前提下对信息进行签名。

盲签名可以实现对所签名内容的保护,防止签名者看到原始内容;另一方面,盲签名还可以实现防止追踪(unlinkability),签名者无法将签名内容和签名结果进行对应。典型的实现包括RSA盲签名算法等。

多重签名

多重签名(multiple signature)即 n 个签名者中,收集到至少 m 个( n ≥ m ≥ 1)的签名,即认为合法。其中,n 是提供的公钥个数,m 是需要匹配公钥的最少的签名个数。

多重签名可以有效地被应用在多人投票共同决策的场景中。例如双方进行协商,第三方作为审核方。三方中任何两方达成一致即可完成协商。

比特币交易中就支持多重签名,可以实现多个人共同管理某个账户的比特币交易。

群签名

群签名(group signature)即某个群组内一个成员可以代表群组进行匿名签名。签名可以验证来自于该群组,却无法准确追踪到签名的是哪个成员。

群签名需要存在一个群管理员来添加新的群成员,因此存在群管理员可能追踪到签名成员身份的风险。

群签名最早于 1991 年由 David Chaum 和 Eugene van Heyst 提出。

环签名

环签名(ring signature),由 Rivest、Shamir 和 Tauman 三位密码学家在 2001 年首次提出。环签名属于一种简化的群签名。

签名者首先选定一个临时的签名者集合,集合中包括签名者自身。然后签名者利用自己的私钥和签名集合中其他人的公钥就可以独立地产生签名,而无需他人的帮助。签名者集合中的其他成员可能并不知道自己被包含在最终的签名中。

环签名在保护匿名性方面有很多的用途。

安全性

数字签名算法自身的安全性由数学问题进行保障,但在使用上,系统的安全性也十分关键。目前常见的数字签名算法往往需要选取合适的随机数作为配置参数,配置参数不合理的使用或泄露都会造成安全漏洞,需要进行安全保护。

2010 年,SONY公司因为其 PS3 产品上采用安全的 ECDSA 进行签名时,不慎采用了重复的随机参数,导致私钥被最终破解,造成重大经济损失。

数字证书

对于非对称加密算法和数字签名来说,很重要的一点就是公钥的分发。理论上任何人可以公开获取到对方的公钥。然而这个公钥有没有可能是伪造的呢?传输过程中有没有可能被篡改掉呢?一旦公钥自身出了问题,则整个建立在其上的安全体系的安全性将不复存在。

数字证书机制正是为了解决这个问题,它就像日常生活中的一个证书一样,可以证明所记录信息的合法性。比如证明某个公钥是某个实体(如组织或个人)的,并且确保一旦内容被篡改能被探测出来,从而实现对用户公钥的安全分发。

根据所保护公钥的用途,可以分为加密数字证书(Encryption Certificate)和签名验证数字证书(Signature Certificate)。前者往往用于保护用于加密信息的公钥;后者则保护用于进行解密签名进行身份验证的公钥。两种类型的公钥也可以同时放在同一证书中。

一般情况下,证书需要由证书认证机构(Certification Authority,CA)来进行签发和背书。权威的证书认证机构包括 DigiCert、GlobalSign、VeriSign 等。用户也可以自行搭建本地 CA 系统,在私有网络中进行使用。

X.509证书规范

一般来说,一个数字证书内容可能包括基本数据(版本、序列号)、所签名对象信息(签名算法类型、签发者信息、有效期、被签发人、签发的公开密钥)、CA的数字签名,等等。

目前使用最广泛的标准为 ITU 和 ISO 联合制定的 X.509 的 v3 版本规范(RFC 5280),其中定义了如下证书信息域:

  • 版本号(Version Number):规范的版本号,目前为版本 3,值为 0x2;

  • 序列号(Serial Number):由 CA 维护的为它所颁发的每个证书分配的唯一的序列号,用来追踪和撤销证书。只要拥有签发者信息和序列号,就可以唯一标识一个证书,最大不能超过 20 个字节;

  • 签名算法(Signature Algorithm):数字签名所采用的算法,如 SHA256WithRSAEncryption 或 ecdsa-with-SHA256;

  • 颁发者(Issuer):颁发证书单位的标识信息,如“C=CN,ST=Beijing,L=Beijing,O=org.example.com,CN=ca.org.example.com”;

  • 有效期(Validity):证书的有效期限,包括起止时间;

  • 主体(Subject):证书拥有者的标识信息(Distinguished Name),如“C=CN,ST=Beijing,L=Beijing,CN=person.org.example.com”;

  • 主体的公钥信息(Subject Public Key Info):所保护的公钥相关的信息;

  • 公钥算法(Public Key Algorithm):公钥采用的算法;

  • 主体公钥(Subject Public Key):公钥的内容;

  • 颁发者唯一号(Issuer Unique Identifier):代表颁发者的唯一信息,仅 2、3 版本支持,可选;

  • 主体唯一号(Subject Unique Identifier):代表拥有证书实体的唯一信息,仅 2、3 版本支持,可选;

  • 扩展(Extensions,可选):可选的一些扩展。v3 中可能包括:

1
2
3
4
5
6
7
8
9
· Subject Key Identifier:实体的密钥标识符,区分实体的多对密钥;

· Basic Constraints:一般指明是否属于 CA;

· Authority Key Identifier:证书颁发者的公钥标识符;

· CRL Distribution Points:撤销文件的发布地址;

· Key Usage:证书的用途或功能信息。

此外,证书的颁发者还需要对证书内容利用自己的公钥添加签名,以防止别人对证书内容进行篡改。

证书格式

X.509 规范中一般推荐使用 PEM(Privacy Enhanced Mail)格式来存储证书相关的文件。证书文件的文件名后缀一般为 .crt 或 .cer,对应私钥文件的文件名后缀一般为 .key,证书请求文件的文件名后缀为 .csr。有时候也统一用 .pem 作为文件名后缀。

PEM 格式采用文本方式进行存储,一般包括首尾标记和内容块,内容块采用 Base64 进行编码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
-----BEGIN CERTIFICATE-----
MIICMzCCAdmgAwIBAgIQIhMiRzqkCljq3ZXnsl6EijAKBggqhkjOPQQDAjBmMQsw
CQYDVQQGEwJVUzETMBEGA1UECBMKQ2FsaWZvcm5pYTEWMBQGA1UEBxMNU2FuIEZy
YW5jaXNjbzEUMBIGA1UEChMLZXhhbXBsZS5jb20xFDASBgNVBAMTC2V4YW1wbGUu
Y29tMB4XDTE3MDQyNTAzMzAzN1oXDTI3MDQyMzAzMzAzN1owZjELMAkGA1UEBhMC
VVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcTDVNhbiBGcmFuY2lzY28x
FDASBgNVBAoTC2V4YW1wbGUuY29tMRQwEgYDVQQDEwtleGFtcGxlLmNvbTBZMBMG
ByqGSM49AgEGCCqGSM49AwEHA0IABCkIHZ3mJCEPbIbUdh/Kz3zWW1C9wxnZOwfy
yrhr6aHwWREW3ZpMWKUcbsYup5kbouBc2dvMFUgoPBoaFYJ9D0SjaTBnMA4GA1Ud
DwEB/wQEAwIBpjAZBgNVHSUEEjAQBgRVHSUABggrBgEFBQcDATAPBgNVHRMBAf8E
BTADAQH/MCkGA1UdDgQiBCBIA/DmemwTGibbGe8uWjt5hnlE63SUsXuNKO9iGEhV
qDAKBggqhkjOPQQDAgNIADBFAiEAyoMO2BAQ3c9gBJOk1oSyXP70XRk4dTwXMF7q
R72ijLECIFKLANpgWFoMoo3W91uzJeUmnbJJt8Jlr00ByjurfAvv
-----END CERTIFICATE-----

可以通过 OpenSSL 工具来查看其内容:

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
# openssl x509 -in example.com-cert.pem -noout -text
Certificate:
Data:
Version: 3 (0x2)
Serial Number:
22:13:22:47:3a:a4:0a:58:ea:dd:95:e7:b2:5e:84:8a
Signature Algorithm: ecdsa-with-SHA256
Issuer: C=US, ST=California, L=San Francisco, O=example.com,
CN=example.com
Validity
Not Before: Apr 25 03:30:37 2017 GMT
Not After : Apr 23 03:30:37 2027 GMT
Subject: C=US, ST=California, L=San Francisco, O=example.com,
CN=example.com
Subject Public Key Info:
Public Key Algorithm: id-ecPublicKey
Public-Key: (256 bit)
pub:
04:29:08:1d:9d:e6:24:21:0f:6c:86:d4:76:1f:ca:
cf:7c:d6:5b:50:bd:c3:19:d9:3b:07:f2:ca:b8:6b:
e9:a1:f0:59:11:16:dd:9a:4c:58:a5:1c:6e:c6:2e:
a7:99:1b:a2:e0:5c:d9:db:cc:15:48:28:3c:1a:1a:
15:82:7d:0f:44
ASN1 OID: prime256v1
X509v3 extensions:
X509v3 Key Usage: critical
Digital Signature, Key Encipherment, Certificate Sign,
CRL Sign
X509v3 Extended Key Usage:
Any Extended Key Usage, TLS Web Server Authentication
X509v3 Basic Constraints: critical
CA:TRUE
X509v3 Subject Key Identifier:
48:03:F0:E6:7A:6C:13:1A:26:DB:19:EF:2E:5A:3B:79:86:
79:44:EB:74:94:B1:7B:8D:28:EF:62:18:48:55:A8
Signature Algorithm: ecdsa-with-SHA256
30:45:02:21:00:ca:83:0e:d8:10:10:dd:cf:60:04:93:a4:d6:
84:b2:5c:fe:f4:5d:19:38:75:3c:17:30:5e:ea:47:bd:a2:8c:
b1:02:20:52:8b:00:da:60:58:5a:0c:a2:8d:d6:f7:5b:b3:25:
e5:26:9d:b2:49:b7:c2:65:af:4d:01:ca:3b:ab:7c:0b:ef

需要注意,用户自行生成私钥情况下,私钥文件一旦丢失,CA 方由于不持有私钥信息,无法进行恢复,意味着通过该证书中公钥加密的内容将无法被解密。

证书的撤销

证书超出有效期后会作废,用户也可以主动向 CA 申请撤销某证书文件。

由于 CA 无法强制收回已经颁发出去的数字证书,因此为了实现证书的作废,往往还需要维护一个撤销证书列表(Certificate Revocation List,CRL),用于记录已经撤销的证书序号。

因此,通常情况下,当第三方对某个证书进行验证时,需要首先检查该证书是否在撤销列表中。如果存在,则该证书无法通过验证。如果不在,则继续进行后续的证书验证过程。

Merkle树结构

Merkle(默克尔)树,又叫哈希树,是一种典型的二叉树结构,由一个根节点、一组中间节点和一组叶节点组成。在区块链系统出现之前,广泛用于文件系统和 P2P 系统中,如下图所示。

Merkle树示例

其主要特点为:

最下面的叶节点包含存储数据或其哈希值;

非叶子节点(包括中间节点和根节点)都是它的两个孩子节点内容的哈希值。

进一步地,默克尔树可以推广到多叉树的情形,此时非叶子节点的内容为它所有的孩子节点内容的哈希值。

默克尔树逐层记录哈希值的特点,让它具有了一些独特的性质。例如,底层数据的任何变动,都会传递到其父节点,一层层沿着路径一直到树根。这意味树根的值实际上代表了对底层所有数据的“数字摘要”。

目前,默克尔树的典型应用场景有很多,下面分别介绍。

快速比较大量数据

对每组数据排序后构建默克尔树结构。当两个默克尔树根相同时,则意味着两组数据必然相同。否则,必然存在不同。

由于 Hash 计算的过程可以十分快速,预处理可以在短时间内完成。利用默克尔树结构能带来巨大的比较性能优势。

快速定位修改

例如上图中,如果 D1 中数据被修改,会影响到 N1、N4 和 Root。

因此,一旦发现某个节点如 Root 的数值发生变化,沿着 Root→N4→N1,最多通过 O(logn)时间即可快速定位到实际发生改变的数据块 D1。

零知识证明

仍以上图为例,如何向他人证明拥有的某组数据(D0……D3)中包括给定某个内容D0而不暴露其他任何内容。

很简单,构造如图所示的一个默克尔树,公布 N1、N5、Root。D0 拥有者通过验证生成的 Root 是否跟提供的值一致,即可很容易检测 D0 存在。整个过程中验证者无法获知其他内容。

布隆过滤器

布隆过滤器(Bloom Filter)于 1970 年由 Burton Howard Bloom 在论文《Space/Time Trade-offs in Hash Coding with Allowable Errors》中提出。布隆过滤器是一种基于Hash的高效查找结构,能够快速(常数时间内)回答“某个元素是否在一个集合内”的问题。

布隆过滤器因为其高效性大量应用于网络和安全领域,例如信息检索(BigTable和HBase)、垃圾邮件规则、注册管理等。

基于Hash的快速查找

在布隆过滤器之前,先来看基于 Hash 的快速查找算法。在前面的讲解中我们提到,Hash 可以将任意内容映射到一个固定长度的字符串,而且不同内容映射到相同串的概率很低。因此,这就构成了一个很好的“内容→索引”的生成关系。

试想,如果给定一个内容和存储数组,通过构造 Hash 函数,让映射后的 Hash 值总不超过数组的大小,则可以实现快速的基于内容的查找。例如,内容“hello world”的 Hash 值如果是“100”,则存放到数组的第 100 个单元上去。如果需要快速查找任意内容,如“hello world”字符串是否在存储系统中,只需要将其在常数时间内计算 Hash 值,并用 Hash 值查看系统中对应元素即可。该系统“完美地”实现了常数时间内的查找。

然而,令人遗憾的是,当映射后的值限制在一定范围(如总数组的大小)内时,会发现 Hash 冲突的概率会变高,而且范围越小,冲突概率越大。很多时候,存储系统的大小又不能无限扩展,这就造成算法效率的下降。为了提高空间利用率,后来人们基于Hash算法的思想设计出了布隆过滤器结构。

更高效的布隆过滤器

布隆过滤器采用了多个 Hash 函数来提高空间利用率。对同一个给定输入来说,多个 Hash 函数计算出多个地址,分别在位串的这些地址上标记为 1。进行查找时,进行同样的计算过程,并查看对应元素,如果都为 1,则说明较大概率是存在该输入。如下图所示。

布隆过滤器

布隆过滤器相对单个 Hash 算法查找,大大提高了空间利用率,可以使用较少的空间来表示较大集合的存在关系。

实际上,无论是 Hash 算法,还是布隆过滤器,基本思想是一致的,都是基于内容的编址。Hash 函数存在冲突,布隆过滤器也存在冲突。这就造成了两种方法都存在着误报(false positive)的情况,但绝对不会漏报(false negative)。

布隆过滤器在应用中误报率往往很低,例如,在使用 7 个不同 Hash 函数的情况下,记录 100 万个数据,采用 2 MB 大小的位串,整体的误判率将低于 1%。而传统的 Hash 查找算法的误报率将接近 10%。

同态加密

定义

同态加密(homomorphic encryption)是一种特殊的加密方法,允许对密文进行处理得到仍然是加密的结果。即对密文直接进行处理,跟对明文进行处理后再对处理结果加密,得到的结果相同。从抽象代数的角度讲,保持了同态性。

同态加密可以保证实现处理者无法访问到数据自身的信息。

如果定义一个运算符 Δ,对加密算法E和解密算法D,满足:

E(XΔY) = E(X) Δ E(Y)

则意味着对于该运算满足同态性。

同态性来自代数领域,一般包括四种类型:加法同态、乘法同态、减法同态和除法同态。同时满足加法同态和乘法同态,则意味着是代数同态,称为全同态(full homomorphic)。同时满足四种同态性,则称为算数同态。

对于计算机操作来讲,实现了全同态意味着对于所有处理都可以实现同态性。只能实现部分特定操作的同态性,称为特定同态(somewhat homomorphic)。

问题与挑战

同态加密的问题最早是由 Ron Rivest、Leonard Adleman 和 Michael L.Dertouzos 在 1978 年提出,同年提出了 RSA 加密算法。但第一个“全同态”的算法直到 2009 年才被克雷格·金特里(Craig Gentry)在论文《Fully Homomorphic Encryption Using Ideal Lattices》中提出并进行数学证明。

仅满足加法同态的算法包括 Paillier 和 Benaloh 算法;仅满足乘法同态的算法包括 RSA 和 ElGamal 算法。

同态加密在云计算和大数据的时代意义十分重大。目前,虽然云计算带来了包括低成本、高性能和便捷性等优势,但从安全角度讲,用户还不敢将敏感信息直接放到第三方云上进行处理。如果有了比较实用的同态加密技术,则大家就可以放心地使用各种云服务了,同时各种数据分析过程也不会泄露用户隐私。加密后的数据在第三方服务处理后得到加密后的结果,这个结果只有用户自身可以进行解密,整个过程第三方平台无法获知任何有效的数据信息。

另一方面,对于区块链技术,同态加密也是很好的互补。使用同态加密技术,运行在区块链上的智能合约可以处理密文,而无法获知真实数据,极大地提高了隐私安全性。

目前全同态的加密方案主要包括如下三种类型:

基于理想格(ideal lattice)的方案:Gentry 和 Halevi 在 2011 年提出的基于理想格的方案可以实现 72 bit 的安全强度,对应的公钥大小约为 2.3 GB,同时刷新密文的处理时间需要几十分钟;

基于整数上近似 GCD 问题的方案:Dijk 等人在 2010 年提出的方案(及后续方案)采用了更简化的概念模型,可以降低公钥大小至几十MB量级;

基于带扰动学习(Learning With Errors,LWE)问题的方案:Brakerski 和 Vaikuntanathan 等在 2011 年左右提出了相关方案;Lopez-Alt A 等在 2012 年设计出多密钥全同态加密方案,接近实时多方安全计算的需求。

目前,已知的同态加密技术往往需要较高的计算时间或存储成本,相比传统加密算法的性能和强度还有差距,但该领域被关注度一直很高,笔者相信,在不远的将来会出现接近实用的方案。

函数加密

与同态加密相关的一个问题是函数加密。

同态加密保护的是数据本身,而函数加密保护的是处理函数本身,即让第三方看不到处理过程的前提下,对数据进行处理。

该问题已被证明不存在对多个通用函数的任意多密钥的方案,目前仅能做到对某个特定函数的一个密钥的方案。

其他问题

密码学领域涉及的问题还有许多,这里列出一些还在发展和探讨中的相关技术。

零知识证明

零知识证明(zero knowledge proof)是这样的一个过程,证明者在不向验证者提供任何额外信息的前提下,使验证者相信某个论断是正确的。

例如,Alice 向 Bob 证明自己知道某个数字,在证明过程中 Bob 可以按照某个顺序提出问题(比如数字加上某些随机数后的变换)由 Alice 回答,并通过回答确信 Alice 较大概率确实知道某数字。证明过程中,Bob 除了知道 Alice 确实知道该数字外,自己无法获知或推理出任何额外信息(包括该数字本身),也无法用 Alice 的证明去向别人证明(Alice如果提前猜测出Bob问题的顺序,存在作假的可能性)。

零知识证明的研究始于 1985 年 Shafi Goldwasser 等人的论文《The Knowledge Complexity of Interactive Proof-Systems》,目前一般认为至少要满足三个条件:

  • 完整性(Completeness):真实的证明可以让验证者成功验证;

  • 可靠性(Soundness):虚假的证明无法让验证者保证通过验证,但允许存在小概率例外;

  • 零知识(Zero-Knowledge):如果得到证明,无法从证明过程中获知除了所证明信息之外的任何信息。

量子密码学

量子密码学(quantum cryptography)随着量子计算和量子通信的研究而受到越来越多的关注,将会对已有的密码学安全机制产生较大的影响。

量子计算的概念最早是物理学家费曼于1981年提出,基本原理是利用量子比特可以同时处于多个相干叠加态,理论上可以同时用少量量子比特来表达大量的信息,并同时进行处理,大大提高计算速度。如 1994 年提出的基于量子计算的 Shor 算法,理论上可以实现远超经典计算速度的大数因子分解。这意味着大量加密算法包括 RSA、DES、椭圆曲线算法等都将很容易被破解。但量子计算目前离实际可用的通用计算机还有一定距离。

量子通信则提供对密钥进行安全分发的机制,有望实现无条件安全的“一次性密码”。量子通信基于量子纠缠效应,两个发生纠缠的量子可以进行远距离的实时状态同步。一旦信道被窃听,则通信双方会获知该情况,丢弃此次传输的泄露信息。该性质十分适合进行大量的密钥分发,如 1984 年提出的 BB84 协议,结合量子通道和公开信道,可以实现安全的密钥分发。

提示:一次性密码:最早由香农提出,实现理论上绝对安全的对称加密。其特点为密钥真随机且只使用一次;密钥长度跟明文一致,加密过程为两者进行二进制异或操作。

社会工程学

密码学与安全问题,一直是学术界和工业界都十分关心的重要话题,相关的技术也一直在不断发展和完善。然而,即便存在理论上完美的技术,也不存在完美的系统。无数例子证实,看起来设计十分完善的系统最后被攻破,并非是因为设计上出现了深层次的漏洞,而问题往往出在事后看来十分浅显的某些方面。

例如,系统管理员将登录密码贴到电脑前;财务人员在电话里泄露用户的个人敏感信息;公司职员随意运行来自不明邮件的附件;不明人员借推销或调查问卷的名义进入办公场所窃取信息……

著名计算机黑客和安全顾问 Kevin David Mitnick 曾在 15 岁时成功入侵北美空中防务指挥系统,其著作《The Art of Deception》大量揭示了如何通过社交工程学的手段轻易获取各种安全信息的案例。

小结

此部分主要总结了密码学与安全领域中的一些核心问题和经典算法。

通过阅读本章内容,相信读者已经对现代密码学的发展状况和关键技术有了初步了解。掌握这些知识,对于帮助理解区块链系统如何实现隐私保护和安全防护都很有好处。

现代密码学安全技术在设计上大量应用了十分专业的现代数学知识,如果读者希望成为这方面的专家,则需要进一步学习并深入掌握近现代的数学科学,特别是数论、抽象代数等相关内容。可以说,密码学安全学科是没有捷径可走的。

另外,从应用的角度来看,一套完整的安全系统除了核心算法外,还包括协议、机制、系统、人员等多个方面。任何一个环节出现漏洞都将带来巨大的安全风险。因此,要实现高安全可靠的系统是十分困难的。

区块链技术中大量利用了现代密码学的已有成果,包括哈希、加解密、签名、Merkle 树数据结构等。另一方面,区块链系统和诸多新的场景也对密码学和安全技术提出了很多新的需求,反过来也将促进相关学科的进一步发展。

打赏
  • © 2020 Shadowalker
  • Powered by Hexo Theme Ayer
    • PV:
    • UV:

请我喝杯咖啡吧~

支付宝
微信