计算机科学

计算机科学 ›› 2020, Vol. 47 ›› Issue (10): 282-289.doi: 10.11896/jsjkx.191000057

所属专题： 信息安全 虚拟专题

• 信息安全 • 上一篇    下一篇

区块链新技术综述:图型区块链和分区型区块链

张长贵, 张岩峰, 李晓华, 聂铁铮, 于戈   

  1. 东北大学计算机科学与工程学院 沈阳110169
  • 收稿日期:2019-10-11 修回日期:2020-03-23 出版日期:2020-10-15 发布日期:2020-10-16
  • 通讯作者: 于戈(yuge@mail.neu.edu.cn)
  • 作者简介:741454897@qq.com
  • 基金资助:
    国家自然科学基金项目(61672141,61672142,61991404,U1811261),中央高校基本科研业务费(N171606005,N181605017,N181604016),辽宁省科学技术基金(20180550321)

Survey of New Blockchain Techniques:DAG Based Blockchain and Sharding Based Blockchain

ZHANG Chang-gui, ZHANG Yan-feng, LI Xiao-hua, NIE Tie-zheng, YU Ge   

  1. School of Computer Science and Engineering,Northeastern University,Shenyang 110169,China
  • Received:2019-10-11 Revised:2020-03-23 Online:2020-10-15 Published:2020-10-16
  • About author:ZHANG Chang-gui,born in 1996,postgraduate.His main research interests include blockchain technology and storage system.
    YU Ge,born in 1962,professor,is a member of China Computer Federation.His main research interests include distributed system and big data management.
  • Supported by:
    National Natural Science Foundation of China(61672141,61672142,61991404,U1811261),Fundamental Research Funds for the Central Universities (N171606005,N181605017,N181604016) and Science and Technology Foundation of Liaoning Pro-vince,China(20180550321)

PDF (PC)

4037

摘要： 区块链是一种创新性分布式账本技术,在金融、征信、审计等众多重要领域具有广泛的应用前景。但是,现有的基于比特币风格的分布式账本系统在可伸缩性、吞吐率、交易确认延迟等方面遇到了提升瓶颈。为此,业界提出了基于有向无环图(Directed Acyclic Graph,DAG)结构和基于分区(Sharding)的两种新型区块链技术,它们通过改变系统的数据结构和存储结构来弥补区块链的原生缺陷,从而得到更高的伸缩性和更大的吞吐量。文中综述了典型的DAG型区块链系统(如NXT,Byteball等)和分区型区块链系统(Elastico,RapidChain等),分别介绍了这两种新型区块链技术的发展现状,详细分析了系统模型、数据结构以及共识机制等关键技术,总结和比较了现有各类区块链技术的特点,指出了有待解决的技术挑战与未来的研究方向。

关键词: DAG型区块链, 分布式账本, 分区型区块链, 共识机制, 区块链

Abstract: Blockchain is an innovative distributed ledger technology with wide application prospects in many important fields such as finance,credit reporting and auditing.However,the existing bitcoin-style distributed ledger systems have already encountered bottlenecks in terms of scalability,throughput,and transaction confirmation latency.To address these problems,researchers have proposed two new blockchain techniques.One is based on Directed Acyclic Graph(DAG) structure,and the other one is based on Shardind.They employ new data structure and new storage structure to overcome the native limitations and get better scalability and higher throughput.This paper reviews the state-of-the-art DAG-based blockchain systems (e.g. NXT,Byteball,etc)and sharding-based blockchain systems (e.g.,Elastico,RapidChain,etc).It analyzes the key components of these systems,including system storage structures,data structures,and consensus protocols.It also compares these blockchain techniques,and summarizes the challenges and future research directions.

Key words: Blockchain, Consensus mechanism, Directed acyclic graph blockchain, Distributed ledger, Sharding-based blockchain

中图分类号: 

  • TP315
[1] NAKAMOTO S.Bitcoin:A peer-to-peer electronic cash system[EB/OL].https://bitcoin.org/bitcoin.pdf.
[2] WOOD G.Ethereum:A secure decentralized generalised trans-action ledger[J].Ethereum project yellow paper,2014,151:1-32.
[3] BUTERIN V.A next-generation smart contract and decentral-ized application platform[EB/OL].https://cryptorating.eu/whitepapers/Ethereum/Ethereum_white_paper.pdf,2014,3:37.
[4] ANDROULAKI E,BARGER A,BORTNIKOV V,et al.Hy-perledger fabric:a distributed operating system for permissioned blockchains[C]//Proceedings of the Thirteenth EuroSys Conference.ACM,2018:30.
[5] YUAN Y,WANG F Y.Blockchain:The State of the Art andFuture Trends.[J].Acta Automaticsa Sinica,2016,42(4):481-494.
[6] BENI F M,ŽARKO I P.Distributed ledger technology:block-chain compared to directed acyclic graph[C]//2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS).IEEE,2018:1569-1570.
[7] ZHANG K,JACOBSEN H A.Towards dependable,scalable,and pervasive distributed ledgers with blockchains[C]//38th IEEE International Conference on Distributed Computing Systems (ICDCS).2018.
[8] SUDHIR Khatwani.How Long Does It Take To Transfer Bitcoins And Why?[EB/OL].[2019-4-23].https://coinsutra.com/bitcoin-transfer-time/.
[9] O’DWYER K J,MALONE D.Bitcoin mining and its energyfootprint[C]//25th IET Irish Signals & Systems Conference 2014 and 2014 China-Ireland International Conferenceon Information and Communications Technologies (ISSC 2014/CIICT 2014).2014:280-285.
[10]BEALL A.Bitcoin mining uses more energy than Ecuador-butthere’s a fix[EB/OL].[2019-4-29].https://www.newscientist.com/article/2151823-bitcoin-mining-uses-more-energy-than-ecuador-but-theres-a-fix/.
[11]维基百科.Directed_acyclic_graph[EB/OL].[2019-05-06].https://en.wikipedia.org/wiki/Directed_acyclic_graph.
[12]CAO Y,ZHANG C.Blockchain Technology:Principles andPractice[M]//Mechanical Industry Press.2018:1-2.
[13]LEMAHIEU C.RaiBlocks:A feeless distributed cryptocurrency network[EB/OL].https://nano.org/en/whitepaper.
[14]CHURYUMOV A.Byteball:A decentralized system for storage and transfer of value[EB/OL].https://obyte.org/Byteball.pdf.
[15]LERNER S D.DagCoin:a cryptocurrency without blocks[EB/OL].https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf.
[16]POPOV S.The tangle[EB/OL].http://www.tangleblog.com/wp-content/uploads/2016/11/IOTA_Whitepaper.pdf.
[17]KING S,NADAL S.Ppcoin:Peer-to-peer crypto-currency with proof-of-stake[EB/OL].https://www.chainwhy.com/upload/default/20180619/126a057fef926dc286accb372da46955.pdf,August,2012,19.
[18]VITALIK Buterin.Vitalik Non-giver of Ether[EB/OL].[2019-05-02].https://twitter.com/VitalikButerin/status/1072162014498148355.
[19]LEMAHIEU C.Nano:A feeless distributed cryptocurrency network[EB/OL].https://nano.org/en/whitepaper.
[20]GRIGG I.Eos-an introduction[EB/OL].Whitepaper iang.org/papers/EOS_An_Introduction.pdf,2017.
[21]LUU L,NARAYANAN V,ZHENG C,et al.A secure sharding protocol for open blockchains[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.ACM,2016:17-30.
[22]DOUCEUR J R.The sybil attack[C]//International workshop on peer-to-peer systems.Berlin:Springer,2002:251-260.
[23]ZILLIQA T.The ZILLIQA Technical Whitepaper[EB/OL].https://docs.zilliqa.com/whitepaper.pdf.
[24]KOKORIS-KOGIAS E,JOVANOVIC P,GASSER L,et al.Omniledger:A secure,scale-out,decentralized ledger via sharding[C]//2018 IEEE Symposium on Security and Privacy (SP).IEEE,2018:583-598.
[25]KOGIAS E K,JOVANOVIC P,GAILLY N,et al.Enhancingbitcoin security and performance with strong consistency via collective signing[C]//25th {USENIX} Security Symposium ({USENIX} Security 16).2016:279-296.
[26]ZAMANI M,MOVAHEDI M,RAYKOVA M.RapidChain:Scaling blockchain via full sharding[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security.ACM,2018:931-948.
[27]WANG J,WANG H.Monoxide:Scale out Blockchains with A-synchronous Consensus Zones[C]//16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19).2019:95-112.
[28] DRESCHER D.Blockchain Basics:A Non-Technical Introduction in 25 Steps[M].Apress; 1st ed.2017.
[29]CASTRO M,LISKOV B.Practical Byzantine fault tolerance[C]//OSDI.1999,99:173-186.
[30]JAKOBSSON M,JUELS A.Proofs of work and bread pudding protocols[M]//Secure Information Networks.Springer,Boston,MA,1999:258-272.
[31]DWORK C,NAOR M.Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference.Springer,Berlin,Heidelberg,1992:139-147.
[32]ZHENG Z,XIE S,DAI H,et al.An overview of blockchaintechnology:Architecture,consensus,and future trends[C]//2017 IEEE International Congress on Big Data (BigData Congress).IEEE,2017:557-564.
[33]Nxt Whitepaper[EB/OL].[2019-04-20].https://whitepaperdatabase.com/nxt-nxt-whitepaper/.
[34]SWARTZ A.Squaring the triangle:Secure,decentralized,hu-man-readable names[J].Retrieved,2011,11(30):2015.
[35]WILCOX-O’HEARN Z.Names:Decentralized,secure,human-meaningful:Choose two[J/OL].https://web.archive.org/web/20011020191610/http://zooko.com/distnames.html.
[36]WANG S,DINH T T A,LIN Q,et al.Forkbase:An efficient storage engine for blockchain and forkable applications[J].Proceedings of the VLDB Endowment,2018,11(10):1137-1150.
[37]XU Z,HAN S,CHEN L.CUB,a consensus unit-based storage scheme for blockchain system[C]//2018 IEEE 34th International Conference on Data Engineering (ICDE).IEEE,2018:173-184.
[38]SHARMA A,SCHUHKNECHT F M,AGRAWAL D,et al.Blurring the Lines between Blockchains and Database Systems:the Case of Hyperledger Fabric[C]//Proceedings of the 2019 International Conference on Management of Data.ACM,2019:105-122.
[39]AMIRI M J,AGRAWAL D,ABBADI A E.CAPER:a cross-application permissioned blockchain[J].Proceedings of the VLDB Endowment,2019,12(11):1385-1398.
[40]AMIRI M J,AGRAWAL D,ABBADI A E.Parblockchain:Leveraging transaction parallelism in permissioned blockchain systems[J].arXiv preprint arXiv:1902.01457,2019.
[41]XU C,ZHANG C,XU J.vChain:Enabling verifiable boolean range queries over blockchain databases[C]//Proceedings of the 2019 International Conference on Management of Data.ACM,2019:141-158.
[42]XU C,ZHANG C,XU J.vChain:Enabling verifiable booleanrange queries over blockchain databases[C]//Proceedings of the 2019 International Conference on Management of Data.ACM,2019:141-158.
[43]RUAN P,CHEN G,DINH T T A,et al.Fine-grained,secure and efficient data provenance on blockchain systems[J].Proceedings of the VLDB Endowment,2019,12(9):975-988.
[1] 王子凯, 朱健, 张伯钧, 胡凯.
区块链与智能合约并行方法研究与实现
Research and Implementation of Parallel Method in Blockchain and Smart Contract
计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102
[2] 周航, 姜河, 赵琰, 解相朋.
适用于各单元共识交易的电力区块链系统优化调度研究
Study on Optimal Scheduling of Power Blockchain System for Consensus Transaction ofEach Unit
计算机科学, 2022, 49(6A): 771-776. https://doi.org/10.11896/jsjkx.210600241
[3] 傅丽玉, 陆歌皓, 吴义明, 罗娅玲.
区块链技术的研究及其发展综述
Overview of Research and Development of Blockchain Technology
计算机科学, 2022, 49(6A): 447-461. https://doi.org/10.11896/jsjkx.210600214
[4] 高健博, 张家硕, 李青山, 陈钟.
RegLang:一种面向监管的智能合约编程语言
RegLang:A Smart Contract Programming Language for Regulation
计算机科学, 2022, 49(6A): 462-468. https://doi.org/10.11896/jsjkx.210700016
[5] 毛典辉, 黄晖煜, 赵爽.
符合监管合规性的自动合成新闻检测方法研究
Study on Automatic Synthetic News Detection Method Complying with Regulatory Compliance
计算机科学, 2022, 49(6A): 523-530. https://doi.org/10.11896/jsjkx.210300083
[6] 李博, 向海昀, 张宇翔, 廖浩德.
面向食品溯源场景的PBFT优化算法应用研究
Application Research of PBFT Optimization Algorithm for Food Traceability Scenarios
计算机科学, 2022, 49(6A): 723-728. https://doi.org/10.11896/jsjkx.210800018
[7] 王思明, 谭北海, 余荣.
面向6G可信可靠智能的区块链分片与激励机制
Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence
计算机科学, 2022, 49(6): 32-38. https://doi.org/10.11896/jsjkx.220400004
[8] 孙浩, 毛瀚宇, 张岩峰, 于戈, 徐石成, 何光宇.
区块链跨链技术发展及应用
Development and Application of Blockchain Cross-chain Technology
计算机科学, 2022, 49(5): 287-295. https://doi.org/10.11896/jsjkx.210800132
[9] 阳真, 黄松, 郑长友.
基于区块链与改进CP-ABE的众测知识产权保护技术研究
Study on Crowdsourced Testing Intellectual Property Protection Technology Based on Blockchain and Improved CP-ABE
计算机科学, 2022, 49(5): 325-332. https://doi.org/10.11896/jsjkx.210900075
[10] 任畅, 赵洪, 蒋华.
一种量子安全拜占庭容错共识机制
Quantum Secured-Byzantine Fault Tolerance Blockchain Consensus Mechanism
计算机科学, 2022, 49(5): 333-340. https://doi.org/10.11896/jsjkx.210400154
[11] 冯了了, 丁滟, 刘坤林, 马科林, 常俊胜.
区块链BFT共识算法研究进展
Research Advance on BFT Consensus Algorithms
计算机科学, 2022, 49(4): 329-339. https://doi.org/10.11896/jsjkx.210700011
[12] 王鑫, 周泽宝, 余芸, 陈禹旭, 任昊文, 蒋一波, 孙凌云.
一种面向电能量数据的联邦学习可靠性激励机制
Reliable Incentive Mechanism for Federated Learning of Electric Metering Data
计算机科学, 2022, 49(3): 31-38. https://doi.org/10.11896/jsjkx.210700195
[13] 张潆藜, 马佳利, 刘子昂, 刘新, 周睿.
以太坊Solidity智能合约漏洞检测方法综述
Overview of Vulnerability Detection Methods for Ethereum Solidity Smart Contracts
计算机科学, 2022, 49(3): 52-61. https://doi.org/10.11896/jsjkx.210700004
[14] 杨昕宇, 彭长根, 杨辉, 丁红发.
基于演化博弈的理性拜占庭容错共识算法
Rational PBFT Consensus Algorithm with Evolutionary Game
计算机科学, 2022, 49(3): 360-370. https://doi.org/10.11896/jsjkx.210900110
[15] 范家幸, 王志伟.
基于门限环签名的分级匿名表决方案
Hierarchical Anonymous Voting Scheme Based on Threshold Ring Signature
计算机科学, 2022, 49(1): 321-327. https://doi.org/10.11896/jsjkx.201000032
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发