思维之海

——在云端,寻找我的星匙。

阅《Untangling Blockchain A Data Processing View of Blockchain Systems》

《Untangling Blockchain A Data Processing View of Blockchain Systems》在 2018 年发表于 TKDE 期刊。区块链技术近年来快速发展。区块链是什么呢?它应用于缺乏信任的群体中,保存一个分布式账本,并在账本中记载一系列全局性的信息。群体则在其存在性、价值和历史状态上达成一个共识。但是区块链的技术栈事实上是在不断扩张的,我们需要理解其中最核心的机制。尤其是数据处理的部分。(这句话显得就很强行的感觉

这篇论文首先做了一个对私链最新研究成果的 survey。他们从产业界和学术界两方面分析出了几个最关键的技术概念:分布式账本(distributed ledger)、密码学(cryptography)、共识协议(consensus protocol)、智能合约(smart contract)。(这篇文章实际上花了一半以上的篇幅写survey)

接着,他们提供了一个区块链的跑分框架:BLOCKBENCH,来评估私有链在应对数据处理工作量时的性能。他们在实验中采用了三个主流的区块链系统来测试BLOCKBENCH,分别是:Ethereum,Parity,Hyperledger Fabric。结果显示,在设计区块链时存在很多trade-off,同时还有区块链和数据库系统之间的巨大性能差异——于是他们根据数据库系统的若干设计原则,指出了未来提升区块链性能的若干研究方向。

本篇论文来自于《赛博智能经济与区块链》课程论文列表,属于 理论研究 专题。

References

Untangling Blockchain: A Data Processing View of Blockchain Systems

基本概念

append-only:只可追加的(意味着已经存在的不能修改)

miner & nonce: some information about the creator of the block (see PoW)

TKDE 期刊

全称:IEEE Transactions on Knowledge and Data Engineering (TKDE)。

TKDE是数据挖掘领域的顶级期刊。

TKDE期刊的审稿周期较长,一般在3-6个月(中途会有major revision,那时就差不多可以算中了),但是某些也会到1、2年……

在搜索这个期刊的时候,第二个搜索结果竟然是软件学院的某位老师:龙明盛。在看了简介之后,了解到他是TKDE的一位审稿人。并且他的5篇期刊论文有4篇都发表在TKDE,均是迁移学习方面的研究。

龙明盛老师也是机器学习理论方向的研究组。

Our team is interested in developing foundational theories, effective algorithms, and reliable systems of machine learning to enable systematic generalization in data representation, inference, and decision making. We focus on industrial applications of AI and data science, including text, sequence, image, video, and scientific data analysis and understanding.

Sybil Attacks 女巫攻击

女巫攻击(Sybil Attack)

在一个P2P网络上,由于节点任意进出,同一份数据通常需要有若干的冗余备份(数据冗余机制)。

女巫攻击是攻击数据冗余机制的一种有效手段。节点通过伪装自己,伪造一系列新的节点身份,这些节点什么都将可以申请对数据的备份,但真正的有效备份只对应一个真实备份——如果备份是唯一的,那么对信息的篡改就存在可能了。这样的攻击破坏了系统的冗余策略,能够获得对网络的不成比例的控制水平

如何解决女巫攻击?

  • 工作量证明(PoW):你必须消耗巨大的算力证明你是一个真正的节点。增加攻击成本。
  • 身份认证:
    • 第三方认证:节点需要与第三方节点进行身份认证
    • 分布式认证:新节点需要获得网络中所有可靠节点的认证

Eclipse Attacks 日蚀攻击

什么是日蚀攻击(Eclipse Attack)丨金色百科

什么是日蚀攻击(Eclipse Attack)?

攻击者通过使节点从整个网络上消失,从而完全控制特定节点对信息的访问。

在流行的对等式网络(例如比特币和以太坊)中,攻击者可通过确保受害者节点不再从网络的其余部分接收正确的信息,而只接收由攻击者操纵的信息来执行日蚀攻击(Eclipse Attack)。

换言之,当网络上的大多数对等节点都是恶意的时候,并且正在控制特定节点的连接时,就会发生这类攻击。控制此类连接的攻击者,可确保此特定节点被恶意节点包围

日蚀攻击的目标是单个节点,而女巫攻击的目标是整个网络范围,旨在篡改网络协议的信誉体系。

日蚀攻击可以称为其它类型攻击的前奏,攻击者一旦成功发动日蚀攻击,那么他有可能通过远低于全网51%的算力发动51%攻击。

DAO Attack 以太坊DAO攻击事件

Understanding The DAO Attack

震惊全球的The DAO黑客事件全程回顾

TheDAO被攻击事件考察报告

DAO Attack 特指以太坊智能合约相关的某次攻击事件。

Introduction

传统的数据库假设了:

  • 安全的运行环境
  • 用常用的并行方法来排序交易

相比这些正在被使用的数据库系统,区块链则提供了一个更加安全的解决方案。

区块链的简单架构和低人力成本,使得像Oracle或者MySQL这样的企业数据库系统的业务受到挑战。

Applications such as security trading and settlement [6], asset and finance management [7], [8], banking and insurance [9] are being built and evaluated.

区块链的不可篡改性、透明性,让人工操作错误的影响降到最低。

区块链可以让流式处理商业(streamline business processes)从数据管理中解放出来,减少他们的重复性工作。


如何深入理解区块链技术?(A quest for understanding blockchain must ultimately answer the following questions:)

  • 什么是区块链?它有什么样的特性可以让当前和未来的应用受益?
  • 不同的区块链项目之间有什么区别?包括架构设计的定性分析,以及性能表现的定量分析。
  • 当前的挑战是什么?未来的区块链应该长什么样?

为了回答以上的问题,论文中解释了四个关键技术概念:分布式账本(distributed ledger)、密码学(cryptography)、共识协议(consensus protocol)、智能合约(smart contract)。

接着详述了BLOCKBENCH框架。(这些部分跟Introduction一模一样

The results show that current blockchains’ performance is limited, far below what a state-of-
the-art database system can offer.

论文主要贡献

1) We provide an in-depth survey of blockchain systems. We discuss state of the art, and categorize current systems along four dimensions: distributed ledger, cryptography, consensus protocol and smart contract.

2) We describe our benchmarking framework, BLOCKBENCH, that is designed for understanding performance of private blockchains against data processing workloads.

3) We present a comprehensive evaluation of Ethereum, Parity and Hyperledger. The results show the limitation of blockchains as data processing platforms. They identify several performance bottlenecks, and therefore can serve as a baseline for future blockchain research and development.

区块链

一个典型的区块链系统通常包含大量互不信任的节点。

所有节点共同保存全局状态,通过加入交易区块来修改全局状态。

一个区块总是记载一个hash pointer指向它前面的区块,知道创世(genesis)区块。

公有链

所有节点自由进出,区块链是完全分布式的,类似于P2P系统。

Bitcoin:

  • 状态:比特币数字货币
  • 交易:将数字货币在若干地址间转移
  • 矿工:收集和验证交易并发布到挖出的区块上
  • 共识协议:工作量证明机制(PoW)
    • 通过复杂的随机计算找到合适的nonce放到区块链的头部
  • 只有一个区块之后接了6个以上的区块时,该区块才能被确认

大多数公有链都采用PoW作为公式协议,因为它可以有效的抵抗女巫攻击(Sybil attacks)。但是,由于其中的随机性和计算的巨大消耗,它不适用于银行业、金融等需要决定性的大交易量的应用场景。

私有链

限制参与人,只有得到许可的节点才可以加入。

Hyperledger算是最受欢迎的私有区块链项目了。

流行的私有共识协议:Zab,Raft,Paxos,PBFT。

Hyperledger早期版本(v0.6.0)使用的就是PBFT。

PBFT是一个三步(three-phase)的协议:

  1. 前准备(pre-prepare):领导节点广播一个值,并让其它节点们commit
  2. 准备(prepare):节点们广播将要commit的值
  3. 提交(commit):确保2/3以上的节点在上一步同意,然后确认commit值

PBFT存在通信上的缺陷 / bound,但是它在非完全同步的网络(partially synchronous networks)中实现了安全性和活跃性。

私有链上还支持智能合约,并可以在智能合约中定义各种复杂的交易逻辑。这些特性在商业和金融领域中尤为重要。

四大核心

分布式账本 Distributed Ledger

一个账本就是一个记载着一系列有顺序的交易记录的数据结构。

在区块链中,每个节点都需要保存一份分布式账本的copy。

分布式账本是append-only的。

区块链从初始状态开始,账本中则记录了所有在之后对状态进行更新的操作。

如上表,一个支持分布式账本的系统可以分为三个维度来描述:

  • the application built on top of the ledger determines the data model of what being stored in the ledger
  • the system may have one or more ledgers which may be connected to each other
  • ledger ownership may vary from completely open to public to strictly controlled by one party

Recall that a system supporting distributed ledgers is characterized by its target applications, by the number of ledgers, and by the ledger ownership.

Crypto-Currency

数字货币是区块链技术最成功的应用。

在数据模型方面分为:transaction-based model,account-based model。

货币的自然性质要求账本的公开性以及唯一性。

Digital Assets

Crypto-currency实际是数字资产的一个实例。

但是有所区别的是,Digital Assets通常会对应到现实中的实体;区块链只负责记录它们的存在性和发生的交易。

General Applications

这里指的就是智能合约。

密码学 Cryptography

在区块链中,密码学用于保证账本的integrity。在没有信任的公链中,这尤为关键(账本必须要具备抵抗双花攻击的能力)。即使在私链中,对已经验证节点有敌意的行为的制约也是很有必要的。

两个层次的integrity protection:

  • First, the global states are protected by a hash (Merkle) tree whose root hash is stored in a block.
    • The tree’s leaves contain the states, the internal nodes contain the hashes of their children.
  • Second, the block history is protected, that is the blocks are immutable once they are appended to the blockchain.(append-only)
    • use hash pointers to link the blocks

密码学对公钥私钥也有很大的作用,如果丢失私钥,那么在区块链系统中会造成不可逆转的经济损失。

也存在很多基于复杂的密码学原理设计的区块链,旨在提高性能和安全性。一些典型的技术如:零知识证明(zero-knowledge proofs),团体签名(group signatures),可信任硬件(trusted hardware)。


Identity Management

区块链中,通过公钥来唯一标识一个用户。公钥由密钥生成,在区块链中公钥又称为地址。

Trusted Hardware

一些区块链系统可能会采用可信任的硬件系统来完成某些记录工作,在损失一小部分安全性的同时,提高整个系统的性能。比如,PoET(proof of elapsed time),这样的系统往往比纯密码学的系统更弱(易受攻击)一些。它们依赖于一些运行在trusted hardware上的TCB(trusted computing base),当这样的TCB形式越精简,安全性则越高。

所有基于trusted hardware的系统,都依赖于remote attestation protocols.(远程验证协议)

Transaction Privacy

大多数区块链只保证交易的稳定性,但不会关注交易中的隐私保护。

一个具有交易隐私的区块链系统应该:

  • 交易不能追踪到另外的交易
  • 交易内容只有参与者知晓

私链中对交易隐私的需求其实不大,而公链则可能有较大需求。一是因为去匿名化攻击实际导致了交易人现实信息的泄露;二是因为交易的连接性可能削弱货币系统的可替代性,从而因为交易历史原因导致部分货币更有价值。

Zerocoin是第一实现去除交易中的连接性的区块链,它是对bitcoin的一种扩展,它通过引入中间货币zerocoins,加入密码学混淆技术,从而使得无法追踪准确的比特币来源。其中需要用到零知识证明的技术。

Advanced Signatures

一般是指多重签名 / 多步验证。提高安全性。

共识机制 Consensus

因为每个节点保存着一份账本的copy,为了修改/更新分布式账本,多个成员之间必须达成一致——这就是共识。

共识机制必须可以忍受Byzantine failures。

共识机制可以分为两类extreme:

  • 纯粹基于算力的协议:通过算力比拼来随机选节点来操作下一步
    • PoW
  • 纯粹基于通信的协议:通过投票和多轮通信来获得共识
    • PBFT

在这两种极端协议之间,很多人想结合它们各自的优点,提出了很多混合式的共识协议。

Some are used in public blockchains to address the inefficiency of PoW. One example is Proof-of-Elapsed-Time (PoET) which replaces PoW with another protocol based on trusted hardware such as Intel SGX. Other examples are Elastico [26] and Algorand [27] which improve PoW by randomly sampling a small set of nodes at each round. Other hybrid protocols, for example Proof-of-Authority (PoA) [28], Stellar [29] and Ripple [6], are used in private blockchains where they improve PBFT by executing consensus in smaller networks called federates


Proof of Work Variants

所有基于工作量证明机制的区块链,都要求矿工去完成某种形式的计算难题,一般是基于某种hash算法。

即,找到满足下面条件的一个random nonce $n$:

$H$ 是一个hash函数,$t$ 是一个阈值(通常对应着难度,$t$ 越小问题越难),$b$ 是当前最新区块的内容。

Bitcoin最早使用SHA-256作作为 $H$。Ethereum则使用Dagger-Hashimoto函数。

一个区块的生成速度取决于上述问题的难度。

为了解决同时找到两个区块(有一定概率发生)的问题,GHOST协议允许在区块链中产生分支,只要这些分支没有包含相互冲突的交易即可。

Proof of Stake

PoW是一个相当消耗资源的策略。它消耗的电力总量可以为一个小国家(丹麦)供电。

PoS则可以减少挖矿的代价。PoS将矿工在节点上质押的货币量作为核心权重。

$s(M)$ 表示矿工质押的stake总量,可以看到,stake越多,挖矿就越容易。

Peercoin是最早开始采用PoS的区块链系统之一。

PBFT Variants

PoW还有一个缺点是,新加入的区块总是要等到足够长的时间以后才能被真正确认(链变得足够长)。

PBFT则是决定性的,一旦区块被加入,它就变得永久化并且无法修改。每轮agreement需要在网络中发送 $O(N^2)$ 的消息,其中 $N$ 是网络中的节点数。

PBFT的性能问题是它最大的缺点。因此它不能扩展到超大规模的网络中。

Trusted Hardware

然后又是trusted hardware。。

Federated

为了让PBFT能够应用到更大规模的场景中,Stellar and Ripple设计了一种联邦机制,每个联邦内部运行一个local的共识协议,因为体量小所以不会产生扩展性的问题。在局部达成agreement之后再广播到全网。

Non-Byzantine

就是没有什么复杂验证的简单机制,这样的机制比较适合小型的私有链,因为代价较小。

Others

IOTA:DAG based区块链,自行设计共识协议。

智能合约 Smart Contracts

智能合约可以看成在一个交易过程中的计算内容,即存储在交易中的一种自动执行的程序。

所有的区块链都有内置的智能合约来实现它们的交易逻辑。

我们可以通过智能合约所使用的编程语言来分类,也可以用它们的运行时环境来作区分。


Scripts

Bitcoin:提供一些预先定义的opcode,用户可以利用这些opcodes实现stack-based的程序。

这样的方式自然能实现的功能有限。

Turing Complete

Ethereum以太坊是最早实现”图灵完备“的智能合约。

也就是说,在以太坊上可以实现非常复杂的智能合约。

实现图灵完备,意味着智能合约中的BUG很难避免(安全性降低)。

Verifiable

在DAO攻击事件发生之前,很多区块链已经拒绝模型中存在无限制的计算行为(unconstrained computations)。它们通过对智能合约的形式化、可解释性、引入纯函数的方法降低智能合约出现漏洞的可能。这样,智能合约的安全性得到一定的保证。

BLOCKBENCH

Designed for quantitative analysis of blockchains as data processing platforms, the framework targets private blockchains with Turing-complete smart contracts.

上图展示了区块链的典型技术栈。

BLOCKBENCH跑分时主要收集数据并做出以下指标上的评估:

  • Throughput(TPS,吞吐量): the number of successful transactions per second. A workload can be configured with multiple clients and threads per clients to saturate the blockchain throughput.
  • Latency(延迟): the response time per transaction. Driver implements blocking transactions, i.e., it waits for one transaction to finish before starting another.
  • Scalability(可扩展性): the changes in throughput and latency when increasing the number of nodes and number of concurrent workloads.
  • Fault tolerance(容错能力): the changes in throughput and latency during node failure. We simulate crashes, network delays and random message corruptions.
  • Security metrics(安全性): the ratio between the total number of blocks included in the main branch and the total number of confirmed blocks. The lower the ratio, the less vulnerable the system is from double spending or selfish mining.

接着就是实验,各种测试了。。

展望

其实这篇文章的创新性几乎 = 0。

无非是做了一个跑分程序。不过survey的质量还是不错的,可以学到和了解到想知道的信息。

最后的Discussion就是畅想了,这里我不再专门记录。其主要内容即是对数据库系统和区块链的比较。

总的来说,如何把数据库的优势和区块链的优势结合起来,或者如何优化区块链,文章并没有给出具体的方案。

所以这一部分应该可以作为一个未来的研究方向。