research-article

Graphchain: a Blockchain-Free Scalable Decentralised Ledger

Authors:

Christopher Carr,

Thomas HainesAuthors Info & Claims

BCC '18: Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts

Pages 21 - 33

https://doi.org/10.1145/3205230.3205235

Published: 22 May 2018 Publication History

Abstract

Blockchain-based replicated ledgers, pioneered in Bitcoin, are effective against double spending, but inherently attract centralised mining pools and incompressible transaction delays.

We propose a framework that forgoes blockchains, building a decentralised ledger as a self-scaling graph of cross-verifying transactions. New transactions validate prior ones, forming a thin graph secured by a cumulative proof-of-work mechanism giving fair and predictable rewards for each participant.

We exhibit rapid confirmation of new transactions, even across a large network affected by latency. We also show, both theoretically and experimentally, a strong convergence property: that any valid transaction entering the system quickly become enshrined in the ancestry of all future transactions.

References

[1]

Simon Barber, Xavier Boyen, Elaine Shi, and Ersin Uzun. 2012. Bitter to Better - How to Make Bitcoin a Better Currency. In FC 2012 (LNCS), Angelos D. Keromytis (Ed.), Vol. 7397. Springer, Heidelberg, 399--414.

[2]

Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized Anonymous Payments from Bitcoin, 459--474.

Digital Library

[3]

Iddo Bentov, Pavel Hubacek, Tal Moran, and Asaf Nadler. 2017. Tortoise and Hares Consensus: the Meshcash Framework for Incentive-Compatible, Scalable Cryptocurrencies. http://eprint.iacr.org/2017/300. (2017).

[4]

Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, and Edward W. Felten. 2015. SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies. In 2015 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 104--121.

Digital Library

[5]

Xavier Boyen, Christopher Carr, and Thomas Haines. 2016. Blockchain-Free Cryptocurrencies: A Framework for Truly Decentralised Fast Transactions. https://eprint.iacr.org/2016/871. (2016).

[6]

Miles Carlsten, Harry A. Kalodner, S. Matthew Weinberg, and Arvind Narayanan. 2016. On the Instability of Bitcoin Without the Block Reward. In ACM CCS 16, Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM Press, 154--167.

Digital Library

[7]

David Chaum. 2016. PrivaTegrity: online communication with strong privacy. Presentation at Real-World Crypto, Stanford University. (2016).

[8]

David Chaum, Amos Fiat, and Moni Naor. 1990. Untraceable Electronic Cash. In CRYPTO'88 (LNCS), Shafi Goldwasser (Ed.), Vol. 403. Springer, Heidelberg, 319--327.

Digital Library

[9]

George Danezis and Sarah Meiklejohn. 2016. Centrally Banked Cryptocurrencies. In NDSS 2016. The Internet Society.

[10]

Christian Decker and Roger Wattenhofer. {n. d.}. A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels. In Stabilization, Safety, and Security of Distributed Systems - 17th International Symposium, SSS 2015, Edmonton, AB, Canada, August 18--21, 2015, Proceedings Andrzej Pelc and Alexander A. Schwarzmann (Eds.), Vol. 9212. Springer.

Digital Library

[11]

Christian Decker and Roger Wattenhofer. {n. d.}. Information propagation in the Bitcoin network. In 13th IEEE International Conference on Peer-to-Peer Computing, IEEE P2P 2013, Trento, Italy, September 9--11, 2013, Proceedings. IEEE.

[12]

Cynthia Dwork and Moni Naor. 1993. Pricing via Processing or Combatting Junk Mail. In CRYPTO'92 (LNCS), Ernest F. Brickell (Ed.), Vol. 740. Springer, Heidelberg, 139--147.

Digital Library

[13]

Ethan Heilman and Neha Narula and Thaddeus Dryja and Madars Virza. 2017. IOTA Vulnerability Report: Cryptanalysis of the Curl Hash Function Enabling Practical Signature Forgery Attacks on the IOTA Cryptocurrency. https://github.com/mit-dci/tangled-curl/blob/master/vuln-iota.md. (2017). {Acc: Jan'18}.

[14]

Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, and Robbert van Renesse. {n. d.}. Bitcoin-NG: A Scalable Blockchain Protocol. In 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016, Santa Clara, CA, USA, March 16--18, 2016, Katerina J. Argyraki and Rebecca Isaacs (Eds.). USENIX Association.

Digital Library

[15]

Ittay Eyal and Emin Gun Sirer. 2014. Majority Is Not Enough: Bitcoin Mining Is Vulnerable. In FC 2014 (LNCS), Nicolas Christin and Reihaneh Safavi-Naini (Eds.), Vol. 8437. Springer, Heidelberg, 436--454.

[16]

Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2015. The Bitcoin Backbone Protocol: Analysis and Applications. In EUROCRYPT 2015, Part II (LNCS), Elisabeth Oswald and Marc Fischlin (Eds.), Vol. 9057. Springer, Heidelberg, 281--310.

[17]

Arthur Gervais, Ghassan O. Karame, Vedran Capkun, and Srdjan Capkun. 2014. Is Bitcoin a Decentralized Currency? IEEE Security & Privacy 12, 3 (2014), 54--60.

[18]

Benjamin Johnson, Aron Laszka, Jens Grossklags, Marie Vasek, and Tyler Moore. 2014. Game-Theoretic Analysis of DDoS Attacks Against Bitcoin Mining Pools. In FC 2014 Workshops (LNCS), Rainer Bohme, Michael Brenner, Tyler Moore, and Matthew Smith (Eds.), Vol. 8438. Springer, Heidelberg, 72--86.

[19]

Ari Juels and John G. Brainard. 1999. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks. In NDSS'99. The Internet Society.

[20]

Ghassan Karame, Elli Androulaki, and Srdjan Capkun. 2012. Double-spending fast payments in bitcoin. In ACM CCS 12, Ting Yu, George Danezis, and Virgil D. Gligor (Eds.). ACM Press, 906--917.

Digital Library

[21]

Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. {n. d.}. Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing. In 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10--12, 2016., Thorsten Holz and Stefan Savage (Eds.). USENIX Association.

Digital Library

[22]

Sergio Demian Lerner. 2015. DagCoin Draft. https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf. (2015). {Acc: Jan'18}.

[23]

Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. 2015. Inclusive Block Chain Protocols. In FC 2015 (LNCS), Rainer Bohme and Tatsuaki Okamoto (Eds.), Vol. 8975. Springer, Heidelberg, 528--547.

[24]

Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M. Voelker, and Stefan Savage. 2016. A fistful of Bitcoins: characterizing payments among men with no names. Commun. ACM 59, 4 (2016).

Digital Library

[25]

Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin. 2013. Zerocoin: Anonymous Distributed E-Cash from Bitcoin. In 2013 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 397--411.

Digital Library

[26]

Andrew Miller, Ari Juels, Elaine Shi, Bryan Parno, and Jonathan Katz. 2014. Permacoin: Repurposing Bitcoin Work for Data Preservation, 475--490.

Digital Library

[27]

Andrew Miller, Ahmed E. Kosba, Jonathan Katz, and Elaine Shi. 2015. Nonoutsourceable Scratch-Off Puzzles to Discourage Bitcoin Mining Coalitions. In ACM CCS 15, Indrajit Ray, Ninghui Li, and Christopher Kruegel: (Eds.). ACM Press, 680--691.

Digital Library

[28]

Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008). Available at https://bitcoin.org/bitcoin.pdf.

[29]

Arvind Narayanan, Joseph Bonneau, Edward W. Felten, Andrew Miller, and Steven Goldfeder. 2016. Bitcoin and Cryptocurrency Technologies - A Comprehensive Introduction. Princeton University Press. ISBN: 978-0--691--17169--2.

Digital Library

[30]

Ethereum Network. 2013. Ethereum: Smart Contract and Decentralized Application Platform. https://github.com/ethereum/wiki/wiki/White-Paper. (2013). {Acc: Jan'18}.

[31]

Sunoo Park, Krzysztof Pietrzak, Albert Kwon, Joel Alwen, Georg Fuchsbauer, and Peter Gazi. 2015. Spacemint: A Cryptocurrency Based on Proofs of Space. Cryptology ePrint Archive, Report 2015/528. (2015). http://eprint.iacr.org/2015/528.

[32]

Rafael Pass, Lior Seeman, and Abhi Shelat. 2017. Analysis of the Blockchain Protocol in Asynchronous Networks. In EURO-CRYPT 2017, Part II (LNCS), Jean-Sebastien Coron and Jesper Buus Nielsen (Eds.), Vol. 10211. Springer, 643--673.

[33]

Joseph Poon and Thaddeus Dryja. 2016. The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments. https://lightning.network/lightning-network-paper.pdf. (2016). {Acc: Jan'18}.

[34]

Serguei Popov. 2017. IOTA: The tangle. http://iotatoken.com/IOTAWhitepaper.pdf. (2017). {Acc: Jan'18}.

[35]

David Schwartz, Noah Youngs, and Arthur Britto. 2014. The Ripple protocol consensus algorithm. (2014). {Acc: Jan'18}.

[36]

Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. 2016. SPECTRE: A Fast and Scalable Cryptocurrency Protocol. Cryptology ePrint Archive, Report 2016/1159. (2016). http://eprint.iacr.org/2016/1159.

[37]

Yonatan Sompolinsky and Aviv Zohar. 2013. Accelerating Bitcoin's Transaction Processing. Fast Money Grows on Trees, Not Chains. Cryptology ePrint Archive, Report 2013/881. (2013). http://eprint.iacr.org/2013/881.

[38]

Douglas Stebila, Lakshmi Kuppusamy, Jothi Rangasamy, Colin Boyd, and Juan Manuel Gonzalez Nieto. 2011. Stronger Difficulty Notions for Client Puzzles and Denial-of-Service-Resistant Protocols. In CT-RSA 2011 (LNCS), Aggelos Kiayias (Ed.), Vol. 6558. Springer, Heidelberg, 284--301.

Digital Library

[39]

Florian Tschorsch and Bjorn Scheuermann. 2016. Bitcoin and Beyond: A Technical Survey on Decentralized Digital Currencies. IEEE Communications Surveys and Tutorials 18, 3 (2016), 2084--2123.

Digital Library

[40]

Web. 2011. Litecoin. https://litecoin.org/ (2011). {Acc: Jan'18}.

[41]

Web. 2013. Dogecoin. http://dogecoin.com/ (2013). {Acc: Jan'18}.

[42]

Web. 2014. Dan Goodin Ars Technica. http://arstechnica.com/security/2014/06/bitcoin-security-guarantee-shattered-by-anonymous-miner-with-51-network-power (2014). {Acc: Jan'18}.

[43]

Web. 2014. Stellar. https://www.stellar.org/ (2014). {Acc: Jan'18}.

[44]

Web. 2016. IOTA. http://iota.org/ (2016). {Acc: Jan'18}.

[45]

Web. 2017. Hashgraph: The future of decentralised technology. https://hashgraph.com (2017). {Acc: Jan'18}.

Cited By

Bhumichai DSmiliotopoulos CBenton RKambourakis GDamopoulos D(2024)The Convergence of Artificial Intelligence and Blockchain: The State of Play and the Road AheadInformation10.3390/info1505026815:5(268)Online publication date: 9-May-2024
https://doi.org/10.3390/info15050268
Xiao X(2024)Accelerating Tip Selection in Burst Message Arrivals for DAG-Based Blockchain SystemsIEEE Transactions on Services Computing10.1109/TSC.2024.335713017:2(392-405)Online publication date: Mar-2024
https://doi.org/10.1109/TSC.2024.3357130
Zhang ZLiu XFeng KWan MLi MDong JZhu L(2024)Phantasm: Adaptive Scalable Mining Toward Stable BlockDAGIEEE Transactions on Services Computing10.1109/TSC.2023.332220317:3(1084-1096)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3322203
Show More Cited By

Index Terms

Graphchain: a Blockchain-Free Scalable Decentralised Ledger

Recommendations

State of Public and Private Blockchains: Myths and Reality
SIGMOD '19: Proceedings of the 2019 International Conference on Management of Data

It has been a decade since the concept of blockchain was invented as the underlying core data structure of the permissionless or public Bitcoin cryptocurrency network. Since then, several cryptocurrencies, tokens and ICOs have emerged. After much ...
The effects of individual-level espoused national cultural values on the willingness to use Bitcoin-like blockchain currencies
Abstract
Some have called bitcoin a real bubble, while, according to others, it is the most radical invention of the twenty-first century. Nevertheless, there is a consensus regarding the disruptive potential of blockchain technology, which is ...
Highlights
- Espoused national cultural values affect the use of blockchain currencies.
- ...
Blockchain and crypto forensics: Investigating crypto frauds
Abstract
In the past few years, cryptocurrency has gained widespread acceptance because of its decentralized nature, quick and secure transactions, and potential for investment and speculation. But the increased popularity has also led to increased ...

Taxonomy of Crypto Forensics: Investigating Crypto Frauds image image

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

BCC '18: Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts

May 2018

69 pages

ISBN:9781450357586

DOI:10.1145/3205230

Program Chairs:
Satya Lokam
Microsoft Research, India
,
Sushmita Ruj
Indian Statistical Institute, India
,
Kouichi Sakurai
Kyushu University, Japan

Copyright © 2018 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2018

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASIA CCS '18

Sponsor:

SIGSAC

ASIA CCS '18: ACM Asia Conference on Computer and Communications Security

June 4, 2018

Incheon, Republic of Korea

Acceptance Rates

BCC '18 Paper Acceptance Rate 5 of 21 submissions, 24%;

Overall Acceptance Rate 18 of 40 submissions, 45%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
915
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)6

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhumichai DSmiliotopoulos CBenton RKambourakis GDamopoulos D(2024)The Convergence of Artificial Intelligence and Blockchain: The State of Play and the Road AheadInformation10.3390/info1505026815:5(268)Online publication date: 9-May-2024
https://doi.org/10.3390/info15050268
Xiao X(2024)Accelerating Tip Selection in Burst Message Arrivals for DAG-Based Blockchain SystemsIEEE Transactions on Services Computing10.1109/TSC.2024.335713017:2(392-405)Online publication date: Mar-2024
https://doi.org/10.1109/TSC.2024.3357130
Zhang ZLiu XFeng KWan MLi MDong JZhu L(2024)Phantasm: Adaptive Scalable Mining Toward Stable BlockDAGIEEE Transactions on Services Computing10.1109/TSC.2023.332220317:3(1084-1096)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3322203
Zhang ZLiu XLi MYin HZhu LKhoussainov BGai K(2024)HCA: Hashchain-Based Consensus Acceleration Via Re-VotingIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.326228321:2(775-788)Online publication date: Mar-2024
https://doi.org/10.1109/TDSC.2023.3262283
Raikwar MPolyanskii NMüller S(2024)SoK: DAG-based Consensus Protocols2024 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)10.1109/ICBC59979.2024.10634358(1-18)Online publication date: 27-May-2024
https://doi.org/10.1109/ICBC59979.2024.10634358
Platt MMcBurney P(2023)Sybil in the Haystack: A Comprehensive Review of Blockchain Consensus Mechanisms in Search of Strong Sybil Attack ResistanceAlgorithms10.3390/a1601003416:1(34)Online publication date: 6-Jan-2023
https://doi.org/10.3390/a16010034
Kumar YGupta S(2023)Effectiveness of Machine and Deep Learning for Blockchain Technology in Fraud Detection and PreventionBlockchain Technology in Healthcare - Concepts, Methodologies, and Applications10.2174/9789815165197123010015(214-236)Online publication date: 26-Nov-2023
https://doi.org/10.2174/9789815165197123010015
Wang QYu JChen SXiang Y(2023)SoK: DAG-based Blockchain SystemsACM Computing Surveys10.1145/357689955:12(1-38)Online publication date: 3-Mar-2023
https://dl.acm.org/doi/10.1145/3576899
Antonenko OGrybniak SGuzey DNashyvan OShanin R(2023)Waterfall: Salto Collores. BFT Based PoS on BlockDAG2023 IEEE 1st Ukrainian Distributed Ledger Technology Forum (UADLTF)10.1109/UADLTF61495.2023.10548638(1-6)Online publication date: 27-Oct-2023
https://doi.org/10.1109/UADLTF61495.2023.10548638
Vincent MGeorge AS CJayapandian N(2023)Systematic Review on Decentralised Artificial Intelligence and Its Applications2023 International Conference on Innovative Data Communication Technologies and Application (ICIDCA)10.1109/ICIDCA56705.2023.10100017(241-246)Online publication date: 14-Mar-2023
https://doi.org/10.1109/ICIDCA56705.2023.10100017
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents