Bitcoin and Cryptocurrency Technologies - Arvind Narayanan ...

Agreement with Satoshi – On the Formalization of Nakamoto Consensus

Cryptology ePrint Archive: Report 2018/400
Date: 2018-05-01
Author(s): Nicholas Stifter, Aljosha Judmayer, Philipp Schindler, Alexei Zamyatin, Edgar Weippl

Link to Paper


Abstract
The term Nakamoto consensus is generally used to refer to Bitcoin's novel consensus mechanism, by which agreement on its underlying transaction ledger is reached. It is argued that this agreement protocol represents the core innovation behind Bitcoin, because it promises to facilitate the decentralization of trusted third parties. Specifically, Nakamoto consensus seeks to enable mutually distrusting entities with weak pseudonymous identities to reach eventual agreement while the set of participants may change over time. When the Bitcoin white paper was published in late 2008, it lacked a formal analysis of the protocol and the guarantees it claimed to provide. It would take the scientific community several years before first steps towards such a formalization of the Bitcoin protocol and Nakamoto consensus were presented. However, since then the number of works addressing this topic has grown substantially, providing many new and valuable insights. Herein, we present a coherent picture of advancements towards the formalization of Nakamoto consensus, as well as a contextualization in respect to previous research on the agreement problem and fault tolerant distributed computing. Thereby, we outline how Bitcoin's consensus mechanism sets itself apart from previous approaches and where it can provide new impulses and directions to the scientific community. Understanding the core properties and characteristics of Nakamoto consensus is of key importance, not only for assessing the security and reliability of various blockchain systems that are based on the fundamentals of this scheme, but also for designing future systems that aim to fulfill comparable goals.

References
[AAC+05] Amitanand S Aiyer, Lorenzo Alvisi, Allen Clement, Mike Dahlin, Jean-Philippe Martin, and Carl Porth. Bar fault tolerance for cooperative services. In ACM SIGOPS operating systems review, volume 39, pages 45–58. ACM, 2005.
[ABSFG08] Eduardo A Alchieri, Alysson Neves Bessani, Joni Silva Fraga, and Fab´ıola Greve. Byzantine consensus with unknown participants. In Proceedings of the 12th International Conference on Principles of Distributed Systems, pages 22–40. SpringerVerlag, 2008.
[AFJ06] Dana Angluin, Michael J Fischer, and Hong Jiang. Stabilizing consensus in mobile networks. In Distributed Computing in Sensor Systems, pages 37–50. Springer, 2006.
[AJK05] James Aspnes, Collin Jackson, and Arvind Krishnamurthy. Exposing computationally-challenged byzantine impostors. Department of Computer Science, Yale University, New Haven, CT, Tech. Rep, 2005.
[AMN+16] Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman. Solidus: An incentive-compatible cryptocurrency based on permissionless byzantine consensus. https://arxiv.org/abs/1612.02916, Dec 2016. Accessed: 2017-02-06.
[AS98] Yair Amir and Jonathan Stanton. The spread wide area group communication system. Technical report, TR CNDS-98-4, The Center for Networking and Distributed Systems, The Johns Hopkins University, 1998.
[Bag00] Walter Bagehot. The english constitution, volume 3. Kegan Paul, Trench, Trubner, 1900. ¨
[Ban98] Bela Ban. Design and implementation of a reliable group communication toolkit for java, 1998.
[BBRTP07] Roberto Baldoni, Marin Bertier, Michel Raynal, and Sara Tucci-Piergiovanni. Looking for a definition of dynamic distributed systems. In International Conference on Parallel Computing Technologies, pages 1–14. Springer, 2007.
[Bit] Bitcoin community. Bitcoin-core source code. https://github.com/bitcoin/bitcoin. Accessed: 2015-06-30.
[BJ87] Ken Birman and Thomas Joseph. Exploiting virtual synchrony in distributed systems. volume 21. ACM, 1987.
[BMC+15] Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A Kroll, and Edward W Felten. Sok: Research perspectives and challenges for bitcoin and cryptocurrencies. In IEEE Symposium on Security and Privacy, 2015.
[BO83] Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 27–30. ACM, 1983.
[BPS16a] Iddo Bentov, Rafael Pass, and Elaine Shi. The sleepy model of consensus. https://eprint.iacr.org/2016/918.pdf, 2016. Accessed: 2016-11-08.
[BPS16b] Iddo Bentov, Rafael Pass, and Elaine Shi. Snow white: Provably secure proofs of stake. https://eprint.iacr.org/2016/919.pdf, 2016. Accessed: 2016-11-08.
[BR09] Franc¸ois Bonnet and Michel Raynal. The price of anonymity: Optimal consensus despite asynchrony, crash and anonymity. In Proceedings of the 23rd international conference on Distributed computing, pages 341–355. Springer-Verlag, 2009.
[Bre00] EA Brewer. Towards robust distributed systems. abstract. In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, page 7, 2000.
[BSAB+17] Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis. Consensus in the age of blockchains. arXiv:1711.03936, 2017. Accessed:2017-12-11.
[BT16] Zohir Bouzid and Corentin Travers. Anonymity-preserving failure detectors. In International Symposium on Distributed Computing, pages 173–186. Springer, 2016.
[Can00] Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of CRYPTOLOGY, 13(1):143–202, 2000.
[Can01] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 136–145. IEEE, 2001.
[CFN90] David Chaum, Amos Fiat, and Moni Naor. Untraceable electronic cash. In Proceedings on Advances in cryptology, pages 319–327. Springer-Verlag New York, Inc., 1990.
[CGR07] Tushar D Chandra, Robert Griesemer, and Joshua Redstone. Paxos made live: an engineering perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 398–407. ACM, 2007.
[CGR11] Christian Cachin, Rachid Guerraoui, and Luis Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011.
[CKS00] Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. In Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, pages 123–132. ACM, 2000.
[CL+99] Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173–186, 1999.
[CL02] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002.
[CNV04] Miguel Correia, Nuno Ferreira Neves, and Paulo Verissimo. How to tolerate half less one byzantine nodes in practical distributed systems. In Reliable Distributed Systems, 2004. Proceedings of the 23rd IEEE International Symposium on, pages 174–183. IEEE, 2004.
[Coo09] J. L. Coolidge. The gambler’s ruin. Annals of Mathematics, 10(4):181–192, 1909.
[Cri91] Flaviu Cristian. Reaching agreement on processor-group membrship in synchronous distributed systems. Distributed Computing, 4(4):175–187, 1991.
[CT96] Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. volume 43, pages 225–267. ACM, 1996.
[CV17] Christian Cachin and Marko Vukolic. Blockchain con- ´sensus protocols in the wild. arXiv:1707.01873, 2017. Accessed:2017-09-26.
[CVL10] Miguel Correia, Giuliana S Veronese, and Lau Cheuk Lung. Asynchronous byzantine consensus with 2f+ 1 processes. In Proceedings of the 2010 ACM symposium on applied computing, pages 475–480. ACM, 2010.
[CVNV11] Miguel Correia, Giuliana Santos Veronese, Nuno Ferreira Neves, and Paulo Verissimo. Byzantine consensus in asynchronous message-passing systems: a survey. volume 2, pages 141–161. Inderscience Publishers, 2011.
[CWA+09] Allen Clement, Edmund L Wong, Lorenzo Alvisi, Michael Dahlin, and Mirco Marchetti. Making byzantine fault tolerant systems tolerate byzantine faults. In NSDI, volume 9, pages 153–168, 2009.
[DDS87] Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. volume 34, pages 77–97. ACM, 1987.
[Dei] Wei Dei. b-money. http://www.weidai.com/bmoney.txt. Accessed on 03/03/2017.
[DGFGK10] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Anne-Marie Kermarrec. Brief announcement: Byzantine agreement with homonyms. In Proceedings of the twentysecond annual ACM symposium on Parallelism in algorithms and architectures, pages 74–75. ACM, 2010.
[DGG02] Assia Doudou, Benoˆıt Garbinato, and Rachid Guerraoui. Encapsulating failure detection: From crash to byzantine failures. In International Conference on Reliable Software Technologies, pages 24–50. Springer, 2002.
[DGKR17] Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexan- ˇder Russell. Ouroboros praos: An adaptively-secure, semisynchronous proof-of-stake protocol. Cryptology ePrint Archive, Report 2017/573, 2017. Accessed: 2017-06-29.
[DLP+86] Danny Dolev, Nancy A Lynch, Shlomit S Pinter, Eugene W Stark, and William E Weihl. Reaching approximate agreement in the presence of faults. volume 33, pages 499–516. ACM, 1986.
[DLS88] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. volume 35, pages 288–323. ACM, 1988.
[DN92] Cynthia Dwork and Moni Naor. Pricing via processing or combatting junk mail. In Annual International Cryptology Conference, pages 139–147. Springer, 1992.
[Dol81] Danny Dolev. Unanimity in an unknown and unreliable environment. In Foundations of Computer Science, 1981. SFCS’81. 22nd Annual Symposium on, pages 159–168. IEEE, 1981.
[Dou02] John R Douceur. The sybil attack. In International Workshop on Peer-to-Peer Systems, pages 251–260. Springer, 2002.
[DSU04] Xavier Defago, Andr ´ e Schiper, and P ´ eter Urb ´ an. Total order ´ broadcast and multicast algorithms: Taxonomy and survey. ACM Computing Surveys (CSUR), 36(4):372–421, 2004.
[DW13] Christian Decker and Roger Wattenhofer. Information propagation in the bitcoin network. In Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on, pages 1–10. IEEE, 2013.
[EGSvR16] Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, and Robbert van Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX Security Symposium on Networked Systems Design and Implementation (NSDI’16). USENIX Association, Mar 2016.
[ES14] Ittay Eyal and Emin Gun Sirer. Majority is not enough: Bitcoin ¨ mining is vulnerable. In Financial Cryptography and Data Security, pages 436–454. Springer, 2014.
[Fin04] Hal Finney. Reusable proofs of work (rpow). http://web.archive.org/web/20071222072154/http://rpow.net/, 2004. Accessed: 2016-04-31.
[Fis83] Michael J Fischer. The consensus problem in unreliable distributed systems (a brief survey). In International Conference on Fundamentals of Computation Theory, pages 127–140. Springer, 1983.
[FL82] Michael J FISCHER and Nancy A LYNCH. A lower bound for the time to assure interactive consistency. volume 14, Jun 1982.
[FLP85] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. volume 32, pages 374–382. ACM, 1985.
[Fuz08] Rachele Fuzzati. A formal approach to fault tolerant distributed consensus. PhD thesis, EPFL, 2008.
[GHM+17] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. Cryptology ePrint Archive, Report 2017/454, 2017. Accessed: 2017-06-29.
[GKL15] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Advances in Cryptology-EUROCRYPT 2015, pages 281–310. Springer, 2015.
[GKL16] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol with chains of variable difficulty. http://eprint.iacr.org/2016/1048.pdf, 2016. Accessed: 2017-02-06.
[GKP17] Juan A. Garay, Aggelos Kiayias, and Giorgos Panagiotakos. Proofs of work for blockchain protocols. Cryptology ePrint Archive, Report 2017/775, 2017. http://eprint.iacr.org/2017/775.
[GKQV10] Rachid Guerraoui, Nikola Knezevi ˇ c, Vivien Qu ´ ema, and Marko ´ Vukolic. The next 700 bft protocols. In ´ Proceedings of the 5th European conference on Computer systems, pages 363–376. ACM, 2010.
[GKTZ12] Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam, and Vassilis Zikas. Byzantine agreement with a rational adversary. pages 561–572. Springer, 2012.
[GKW+16] Arthur Gervais, Ghassan O Karame, Karl Wust, Vasileios ¨ Glykantzis, Hubert Ritzdorf, and Srdjan Capkun. On the security and performance of proof of work blockchains. https://eprint.iacr.org/2016/555.pdf, 2016. Accessed: 2016-08-10.
[GL02] Seth Gilbert and Nancy Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. volume 33, pages 51–59. ACM, 2002.
[GRKC15] Arthur Gervais, Hubert Ritzdorf, Ghassan O Karame, and Srdjan Capkun. Tampering with the delivery of blocks and transactions in bitcoin. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 692–705. ACM, 2015.
[Her88] Maurice P Herlihy. Impossibility and universality results for wait-free synchronization. In Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, pages 276–290. ACM, 1988.
[Her91] Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124–149, 1991.
[HKZG15] Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg. Eclipse attacks on bitcoin’s peer-to-peer network. In 24th USENIX Security Symposium (USENIX Security 15), pages 129–144, 2015.
[Hoe07] Jaap-Henk Hoepman. Distributed double spending prevention. In Security Protocols Workshop, pages 152–165. Springer, 2007.
[HT94] Vassos Hadzilacos and Sam Toueg. A modular approach to fault-tolerant broadcasts and related problems. Cornell University Technical Report 94-1425, 1994.
[IT08] Hideaki Ishii and Roberto Tempo. Las vegas randomized algorithms in distributed consensus problems. In 2008 American Control Conference, pages 2579–2584. IEEE, 2008.
[JB99] Ari Juels and John G Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In NDSS, volume 99, pages 151–165, 1999.
[KMMS01] Kim Potter Kihlstrom, Louise E Moser, and P Michael MelliarSmith. The securering group communication system. ACM Transactions on Information and System Security (TISSEC), 4(4):371–406, 2001.
[KMMS03] Kim Potter Kihlstrom, Louise E Moser, and P Michael MelliarSmith. Byzantine fault detectors for solving consensus. volume 46, pages 16–35. Br Computer Soc, 2003.
[KMTZ13] Jonathan Katz, Ueli Maurer, Bjorn Tackmann, and Vassilis ¨ Zikas. Universally composable synchronous computation. In TCC, volume 7785, pages 477–498. Springer, 2013.
[KP15] Aggelos Kiayias and Giorgos Panagiotakos. Speed-security tradeoff s in blockchain protocols. https://eprint.iacr.org/2015/1019.pdf, Oct 2015. Accessed: 2016-10-17.
[KP16] Aggelos Kiayias and Giorgos Panagiotakos. On trees, chains and fast transactions in the blockchain. http://eprint.iacr.org/2016/545.pdf, 2016. Accessed: 2017-02-06.
[KRDO16] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. https://pdfs.semanticscholar.org/1c14/549f7ba7d6a000d79a7d12255eb11113e6fa.pdf, 2016. Accessed: 2017-02-20.
[Lam84] Leslie Lamport. Using time instead of timeout for fault-tolerant distributed systems. volume 6, pages 254–280. ACM, 1984.
[Lam98] Leslie Lamport. The part-time parliament. volume 16, pages 133–169. ACM, 1998.
[LCW+06] Harry C Li, Allen Clement, Edmund L Wong, Jeff Napper, Indrajit Roy, Lorenzo Alvisi, and Michael Dahlin. Bar gossip. In Proceedings of the 7th symposium on Operating systems design and implementation, pages 191–204. USENIX Association, 2006.
[LSM06] Brian Neil Levine, Clay Shields, and N Boris Margolin. A survey of solutions to the sybil attack. University of Massachusetts Amherst, Amherst, MA, 7, 2006.
[LSP82] Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. volume 4, pages 382–401. ACM, 1982.
[LSZ15] Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive block chain protocols. In Financial Cryptography and Data Security, pages 528–547. Springer, 2015.
[LTKS15] Loi Luu, Jason Teutsch, Raghav Kulkarni, and Prateek Saxena. Demystifying incentives in the consensus computer. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 706–719. ACM, 2015.
[Lyn96] Nancy A Lynch. Distributed algorithms. Morgan Kaufmann, 1996.
[Mic16] Silvio Micali. Algorand: The efficient and democratic ledger. http://arxiv.org/abs/1607.01341, 2016. Accessed: 2017-02-09.
[Mic17] Silvio Micali. Byzantine agreement, made trivial. https://people.csail.mit.edu/silvio/SelectedApr 2017. Accessed:2018-02-21.
[MJ14] A Miller and LaViola JJ. Anonymous byzantine consensus from moderately-hard puzzles: A model for bitcoin. https://socrates1024.s3.amazonaws.com/consensus.pdf, 2014. Accessed: 2016-03-09.
[MMRT03] Dahlia Malkhi, Michael Merritt, Michael K Reiter, and Gadi Taubenfeld. Objects shared by byzantine processes. volume 16, pages 37–48. Springer, 2003.
[MPR01] Hugo Miranda, Alexandre Pinto, and Luıs Rodrigues. Appia, a flexible protocol kernel supporting multiple coordinated channels. In Distributed Computing Systems, 2001. 21st International Conference on., pages 707–710. IEEE, 2001.
[MR97] Dahlia Malkhi and Michael Reiter. Unreliable intrusion detection in distributed computations. In Computer Security Foundations Workshop, 1997. Proceedings., 10th, pages 116–124. IEEE, 1997.
[MRT00] Achour Mostefaoui, Michel Raynal, and Fred´ eric Tronel. From ´ binary consensus to multivalued consensus in asynchronous message-passing systems. Information Processing Letters, 73(5-6):207–212, 2000.
[MXC+16] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft protocols. https://eprint.iacr.org/2016/199.pdf, 2016. Accessed: 2017-01-10.
[Nak08a] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf, Dec 2008. Accessed: 2015-07-01.
[Nak08b] Satoshi Nakamoto. Bitcoin p2p e-cash paper, 2008.
[Nar16] Narayanan, Arvind and Bonneau, Joseph and Felten, Edward and Miller, Andrew and Goldfeder, Steven. Bitcoin and cryptocurrency technologies. https://d28rh4a8wq0iu5.cloudfront.net/bitcointech/readings/princeton bitcoin book.pdf?a=1, 2016. Accessed: 2016-03-29.
[Nei94] Gil Neiger. Distributed consensus revisited. Information processing letters, 49(4):195–201, 1994.
[NG16] Christopher Natoli and Vincent Gramoli. The blockchain anomaly. In Network Computing and Applications (NCA), 2016 IEEE 15th International Symposium on, pages 310–317. IEEE, 2016.
[NKMS16] Kartik Nayak, Srijan Kumar, Andrew Miller, and Elaine Shi. Stubborn mining: Generalizing selfish mining and combining with an eclipse attack. In 1st IEEE European Symposium on Security and Privacy, 2016. IEEE, 2016.
[PS16a] Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. http://eprint.iacr.org/2016/916.pdf, 2016. Accessed: 2016-11-08.
[PS16b] Rafael Pass and Elaine Shi. Hybrid consensus: Scalable permissionless consensus. https://eprint.iacr.org/2016/917.pdf, Sep 2016. Accessed: 2016-10-17.
[PS17] Rafael Pass and Elaine Shi. Thunderella: Blockchains with optimistic instant confirmation. Cryptology ePrint Archive, Report 2017/913, 2017. Accessed:2017-09-26.
[PSL80] Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. volume 27, pages 228–234. ACM, 1980.
[PSs16] Rafael Pass, Lior Seeman, and abhi shelat. Analysis of the blockchain protocol in asynchronous networks. http://eprint.iacr.org/2016/454.pdf, 2016. Accessed: 2016-08-01.
[Rab83] Michael O Rabin. Randomized byzantine generals. In Foundations of Computer Science, 1983., 24th Annual Symposium on, pages 403–409. IEEE, 1983.
[Rei96] Michael K Reiter. A secure group membership protocol. volume 22, page 31, 1996.
[Ric93] Aleta M Ricciardi. The group membership problem in asynchronous systems. PhD thesis, Cornell University, 1993.
[Ros14] M. Rosenfeld. Analysis of hashrate-based double spending. http://arxiv.org/abs/1402.2009, 2014. Accessed: 2016-03-09.
[RSW96] Ronald L Rivest, Adi Shamir, and David A Wagner. Time-lock puzzles and timed-release crypto. 1996.
[Sch90] Fred B Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. volume 22, pages 299–319. ACM, 1990.
[SLZ16] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. Spectre: A fast and scalable cryptocurrency protocol. Cryptology ePrint Archive, Report 2016/1159, 2016. Accessed: 2017-02-20.
[SSZ15] Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. Optimal selfish mining strategies in bitcoin. http://arxiv.org/pdf/1507.06183.pdf, 2015. Accessed: 2016-08-22.
[SW16] David Stolz and Roger Wattenhofer. Byzantine agreement with median validity. In LIPIcs-Leibniz International Proceedings in Informatics, volume 46. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
[Swa15] Tim Swanson. Consensus-as-a-service: a brief report on the emergence of permissioned, distributed ledger systems. http://www.ofnumbers.com/wp-content/uploads/2015/04/Permissioned-distributed-ledgers.pdf, Apr 2015. Accessed: 2017-10-03.
[SZ13] Yonatan Sompolinsky and Aviv Zohar. Accelerating bitcoin’s transaction processing. fast money grows on trees, not chains, 2013.
[SZ16] Yonatan Sompolinsky and Aviv Zohar. Bitcoin’s security model revisited. http://arxiv.org/pdf/1605.09193, 2016. Accessed: 2016-07-04.
[Sza14] Nick Szabo. The dawn of trustworthy computing. http://unenumerated.blogspot.co.at/2014/12/the-dawn-of-trustworthy-computing.html, 2014. Accessed: 2017-12-01.
[TS16] Florian Tschorsch and Bjorn Scheuermann. Bitcoin and ¨ beyond: A technical survey on decentralized digital currencies. In IEEE Communications Surveys Tutorials, volume PP, pages 1–1, 2016.
[VCB+13] Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Verissimo. Efficient byzantine fault-tolerance. volume 62, pages 16–30. IEEE, 2013.
[Ver03] Paulo Ver´ıssimo. Uncertainty and predictability: Can they be reconciled? In Future Directions in Distributed Computing, pages 108–113. Springer, 2003.
[Vuk15] Marko Vukolic. The quest for scalable blockchain fabric: ´ Proof-of-work vs. bft replication. In International Workshop on Open Problems in Network Security, pages 112–125. Springer, 2015.
[Vuk16] Marko Vukolic. Eventually returning to strong consistency. https://pdfs.semanticscholar.org/a6a1/b70305b27c556aac779fb65429db9c2e1ef2.pdf, 2016. Accessed: 2016-08-10.
[XWS+17] Xiwei Xu, Ingo Weber, Mark Staples, Liming Zhu, Jan Bosch, Len Bass, Cesare Pautasso, and Paul Rimba. A taxonomy of blockchain-based systems for architecture design. In Software Architecture (ICSA), 2017 IEEE International Conference on , pages 243–252. IEEE, 2017.
[YHKC+16] Jesse Yli-Huumo, Deokyoon Ko, Sujin Choi, Sooyong Park, and Kari Smolander. Where is current research on blockchain technology? – a systematic review. volume 11, page e0163477. Public Library of Science, 2016.
[ZP17] Ren Zhang and Bart Preneel. On the necessity of a prescribed block validity consensus: Analyzing bitcoin unlimited mining protocol. http://eprint.iacr.org/2017/686, 2017. Accessed: 2017-07-20.
submitted by dj-gutz to myrXiv [link] [comments]

Echoes of the Past: Recovering Blockchain Metrics From Merged Mining

Cryptology ePrint Archive: Report 2018/1134
Date: 2018-11-22
Author(s): Nicholas Stifter, Philipp Schindler, Aljosha Judmayer, Alexei Zamyatin, Andreas Kern, Edgar Weippl

Link to Paper


Abstract
So far, the topic of merged mining has mainly been considered in a security context, covering issues such as mining power centralization or crosschain attack scenarios. In this work we show that key information for determining blockchain metrics such as the fork rate can be recovered through data extracted from merge mined cryptocurrencies. Specifically, we reconstruct a long-ranging view of forks and stale blocks in Bitcoin from its merge mined child chains, and compare our results to previous findings that were derived from live measurements. Thereby, we show that live monitoring alone is not sufficient to capture a large majority of these events, as we are able to identify a non-negligible portion of stale blocks that were previously unaccounted for. Their authenticity is ensured by cryptographic evidence regarding both, their position in the respective blockchain, as well as the Proof-of-Work difficulty.
Furthermore, by applying this new technique to Litecoin and its child cryptocur rencies, we are able to provide the first extensive view and lower bound on the stale block and fork rate in the Litecoin network. Finally, we outline that a recovery of other important metrics and blockchain characteristics through merged mining may also be possible.

References
  1. C. Decker and R. Wattenhofer, “Information propagation in the bitcoin network,” in Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on. IEEE, 2013, pp. 1–10. [Online]. Available: http://diyhpl.us/∼bryan/papers2/bitcoin/Information% 20propagation%20in%20the%20Bitcoin%20network.pdf
  2. A. Gervais, G. O. Karame, K. Wust, V. Glykantzis, H. Ritzdo rf, and S. Capkun, “On the ¨ security and performance of proof of work blockchains,” in Proceedings of the 2016 ACM SIGSAC. ACM, 2016, pp. 3–16.
  3. A. E. Gencer, S. Basu, I. Eyal, R. van Renesse, and E. G. Sirer, “Decentralization in bitcoin and ethereum networks,” in Proceedings of the 22nd International Conference on Financial Cryptography and Data Security (FC). Springer, 2018. [Online]. Available: http://fc18.ifca.ai/preproceedings/75.pdf
  4. I. Eyal and E. G. Sirer, “Majority is not enough: Bitcoin mining is vulnerable,” in Financial Cryptography and Data Security. Springer, 2014, pp. 436–454. [Online]. Available: http://arxiv.org/pdf/1311.0243
  5. K. Nayak, S. Kumar, A. Miller, and E. Shi, “Stubborn mining: Generalizing selfish mining and combining with an eclipse attack,” in 1st IEEE European Symposium on Security and Privacy, 2016. IEEE, 2016. [Online]. Available: http://eprint.iacr.org/2015/796.pdf
  6. A. Sapirshtein, Y. Sompolinsky, and A. Zohar, “Optimal selfish mining strategies in bitcoin,” http://arxiv.org/pdf/1507.06183.pdf, 2015, accessed: 2016-08-22. [Online]. Available: http://arxiv.org/pdf/1507.06183.pdf
  7. J. Bonneau, “Why buy when you can rent? bribery attacks on bitcoin consensus,” in BITCOIN ’16: Proceedings of the 3rd Workshop on Bitcoin and Blockchain Research, February 2016. [Online]. Available: http://fc16.ifca.ai/bitcoin/papers/Bon16b.pdf
  8. K. Liao and J. Katz, “Incentivizing blockchain forks via whale transactions,” in International Conference on Financial Cryptography and Data Security. Springer, 2017, pp. 264–279. [Online]. Available: http://www.cs.umd.edu/∼jkatz/papers/whale-txs.pdf
  9. P. McCorry, A. Hicks, and S. Meiklejohn, “Smart contracts for bribing miners,” in 5th Workshop on Bitcoin and Blockchain Research, Financial Cryptography and Data Security 18 (FC). Springer, 2018. [Online]. Available: http://fc18.ifca.ai/bitcoin/papers/bitcoin18-final14.pdf
  10. A. Zamyatin, N. Stifter, A. Judmayer, P. Schindler, E. Weippl, and W. J. Knottebelt, “(Short Paper) A Wild Velvet Fork Appears! Inclusive Blockchain Protocol Changes in Practice,” in 5th Workshop on Bitcoin and Blockchain Research, Financial Cryptography and Data Security 18 (FC). Springer, 2018. [Online]. Available: https://eprint.iacr.org/2018/087.pdf
  11. Blockchain.com, “Blockchain.com orphaned blocks,” https://www.blockchain.com/btc/orphaned-blocks, Blockchain.com, accessed: 2018-09-25.
  12. BitcoinChain.com, “Bitcoinchain bitcoin block explorer,” https://bitcoinchain.com/blockexplorer, BitcoinChain.com, accessed: 2018-09-25.
  13. ChainQuery.com, “A web based interface to the bitcoin api json-rpc,” http://chainquery.com/bitcoin-api, ChainQuery.com, accessed: 2018-09-25.
  14. L. Project, “Litecoin,” https://litecoin.org/, accessed: 2016-03-29.
  15. Y. Sompolinsky and A. Zohar, “Accelerating bitcoin’s transaction processing. fast money grows on trees, not chains,” p. 881, 2013. [Online]. Available: http://eprint.iacr.org/2013/881.pdf
  16. A. Miller and L. JJ, “Anonymous byzantine consensus from moderately-hard puzzles: A model for bitcoin,” https://socrates1024.s3.amazonaws.com/consensus.pdf, 2014, accessed: 2016-03-09. [Online]. Available: https://socrates1024.s3.amazonaws.com/consensus.pdf
  17. J. Garay, A. Kiayias, and N. Leonardos, “The bitcoin backbone protocol: Analysis and applications,” in Advances in Cryptology-EUROCRYPT 2015. Springer, 2015, pp. 281–310. [Online]. Available: http://courses.cs.washington.edu/courses/cse454/15wi/papers/bitcoin765.pdf
  18. R. Pass and E. Shi, “Fruitchains: A fair blockchain,” http://eprint.iacr.org/2016/916.pdf, 2016, accessed: 2016-11-08. [Online]. Available: http://eprint.iacr.org/2016/916.pdf
  19. R. Pass, L. Seeman, and a. shelat, “Analysis of the blockchain protocol in asynchronous networks,” http://eprint.iacr.org/2016/454.pdf, 2016, accessed: 2016-08-01. [Online]. Available: http://eprint.iacr.org/2016/454.pdf
  20. K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. Kosba, A. Miller, P. Saxena, E. Shi, and E. Gun, “On scaling decentralized blockchains,” in ¨ 3rd Workshop on Bitcoin and Blockchain Research, Financial Cryptography 16, 2016. [Online]. Available: http://www.tik.ee.ethz.ch/file/74bc987e6ab4a8478c04950616612f69/main.pdf
  21. A. Kiayias and G. Panagiotakos, “On trees, chains and fast transactions in the blockchain.” http://eprint.iacr.org/2016/545.pdf, 2016, accessed: 2017-02-06. [Online]. Available: http://eprint.iacr.org/2016/545.pdf
  22. Y. Sompolinsky, Y. Lewenberg, and A. Zohar, “Spectre: A fast and scalable cryptocurrency protocol,” Cryptology ePrint Archive, Report 2016/1159, 2016, accessed: 2017-02-20. [Online]. Available: http://eprint.iacr.org/2016/1159.pdf
  23. Y. Sompolinsky and A. Zohar, “Phantom: A scalable blockdag protocol,” Cryptology ePrint Archive, Report 2018/104, 2018, accessed:2018-01-31. [Online]. Available: https://eprint.iacr.org/2018/104.pdf
  24. Bitcoin community, “Bitcoin-core source code,” https://github.com/bitcoin/bitcoin, accessed: 2018-09-25.
  25. A. Miller, J. Litton, A. Pachulski, N. Gupta, D. Levin, N. Spring, and B. Bhattacharjee, “Discovering bitcoin’s public topology and influential nodes,” http://cs.umd.edu/projects/coinscope/coinscope.pdf, May 2015, accsessed: 2016-03-09. [Online]. Available: http://cs.umd.edu/projects/coinscope/coinscope.pdf
  26. chainz.cryptoid.info/, “Chainz blockchain explorers,” chainz.cryptoid.info/, chainz.cryptoid.info/, accessed: 2018-09-25.
  27. Narayanan, Arvind and Bonneau, Joseph and Felten, Edward and Miller, Andrew and Goldfeder, Steven, “Bitcoin and cryptocurrency technologies,” http://bitcoinbook.cs.princeton.edu/, 2016, accessed: 2016-03-29. [Online]. Available: https://d28rh4a8wq0iu5.cloudfront.net/bitcointech/readings/princeton bitcoin book.pdf
  28. A. Judmayer, A. Zamyatin, N. Stifter, A. G. Voyiatzis, and E. Weippl, “Merged mining: Curse or cure?” in CBT’17: Proceedings of the International Workshop on Cryptocurrencies and Blockchain Technology, Sep 2017. [Online]. Available: https://eprint.iacr.org/2017/791.pdf
  29. M. Jakobsson and A. Juels, “Proofs of work and bread pudding protocols,” in Secure Information Networks. Springer, 1999, pp. 258–272. [Online]. Available: https://link.springer.com/content/pdf/10.1007/978-0-387-35568-9 18.pdf
  30. A. Judmayer, N. Stifter, K. Krombholz, and E. Weippl, “Blocks and chains: Introduction to bitcoin, cryptocurrencies, and their consensus mechanisms,” Synthesis Lectures on Information Security, Privacy, and Trust, 2017.
  31. A. Kiayias, A. Miller, and D. Zindros, “Non-interactive proofs of proof-of-work,” Cryptology ePrint Archive, Report 2017/963, 2017, accessed:2017-10-03. [Online]. Available: https://eprint.iacr.org/2017/963.pdf
  32. Namecoin community, “Namecoin source code - chainparams.cpp,” https://github.com/namecoin/namecoin-core/blob/fdfb20fc263a72acc2a3c460b56b64245c1bedcb/src/chainparams.cpp#L123, accessed: 2018-09-25.
  33. ——, “Namecoin source code - auxpow.cpp,” https://github.com/namecoin/namecoincore/blob/fdfb20fc263a72acc2a3c460b56b64245c1bedcb/src/auxpow.cpp#L177-L200, accessed: 2018-09-25.
  34. I0Coin community, “I0coin source code,” https://github.com/domob1812/i0coin, accessed: 2018-09-25.
  35. S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” https://bitcoin.org/bitcoin.pdf, Dec 2008, accessed: 2015-07-01. [Online]. Available: https://bitcoin.org/bitcoin.pdf
  36. N. T. Courtois and L. Bahack, “On subversive miner strategies and block withholding attack in bitcoin digital currency,” arXiv preprint arXiv:1402.1718, 2014, accessed: 2016-07-04. [Online]. Available: https://arxiv.org/pdf/1402.1718.pdf
  37. J. Gobel, P. Keeler, A. E. Krzesinski, and P. G. Taylor, “Bitcoin blockchain dynamics: the ¨ selfish-mine strategy in the presence of propagation delay,” http://arxiv.org/pdf/1505.05343.pdf, 2015, accessed: 2015-03-01. [Online]. Available: http://arxiv.org/pdf/1505.05343.pdf
  38. N. Developers, “Neo4j,” 2012.
  39. Gavin Andresen, “Bitcoin improvement proposal 34 (bip34): Block v2, height in coinbase,” https://github.com/bitcoin/bips/blob/mastebip-0034.mediawiki, accessed: 2018-09-25. [Online]. Available: https://github.com/bitcoin/bips/blob/mastebip-0034.mediawiki
  40. Matt Corello, “Fast internet bitcoin relay engine,” http://bitcoinfibre.org/, accessed: 2018-09-25. [Online]. Available: http://bitcoinfibre.org/
  41. Suhas Daftuar, “sendheaders message,” https://github.com/bitcoin/bips/wiki/Comments:BIP-0130, accessed: 2018-09-25. [Online]. Available: https://github.com/bitcoin/bips/wiki/Comments:BIP-0130
  42. R. Bowden, H. P. Keeler, A. E. Krzesinski, and P. G. Taylor, “Block arrivals in the bitcoin blockchain,” 2018. [Online]. Available: https://arxiv.org/pdf/1801.07447.pdf
  43. GeistGeld community, “Geistgeld source code,” https://github.com/Lolcust/GeistGeld, accessed: 2018-09-25.
  44. A. P. Ozisik, G. Bissias, and B. Levine, “Estimation of miner hash rates and consensus on blockchains,” arXiv preprint arXiv:1707.00082, 2017, accessed:2017-09-25. [Online]. Available: https://arxiv.org/pdf/1707.00082.pdf
  45. E. Duffield and D. Diaz, “Dash: A payments-focused cryptocurrency,” https://github.com/dashpay/dash/wiki/Whitepaper, Aug 2013, accessed: 2018-09-25. [Online]. Available: https://github.com/dashpay/dash/wiki/Whitepaper
  46. N. Van Saberhagen, “Cryptonote v 2.0,” https://cryptonote.org/whitepaper.pdf, Oct 2013. [Online]. Available: https://cryptonote.org/whitepaper.pdf
  47. G. Hall, “Guide: Merge mining 6 scrypt coins at full hashpower, simultaneously,” https://www.ccn.com/guide-simultaneously-mining-5-scrypt-coins-full-hashpowe, Apr 2014, accessed: 2018-09-25. [Online]. Available: https://www.ccn.com/guide-simultaneouslymining-5-scrypt-coins-full-hashpowe
  48. united-scrypt coin, “[ann][usc] first merged minable scryptcoin unitedscryptcoin,” https://bitcointalk.org/index.php?topic=353688.0, Nov 2013, accessed: 2018-09-25. [Online]. Available: https://bitcointalk.org/index.php?topic=353688.0
  49. J. A. D. Donet, C. Perez-Sola, and J. Herrera-Joancomart ´ ´ı, “The bitcoin p2p network,” in Financial Cryptography and Data Security. Springer, 2014, pp. 87–102. [Online]. Available: http://fc14.ifca.ai/bitcoin/papers/bitcoin14 submission 3.pdf
  50. M. Bartoletti and L. Pompianu, “An analysis of bitcoin op return metadata,” https://arxiv.org/pdf/1702.01024.pdf, 2017, accessed: 2017-03-09. [Online]. Available: https://arxiv.org/pdf/1702.01024.pdf
  51. R. Matzutt, J. Hiller, M. Henze, J. H. Ziegeldorf, D. Mullmann, O. Hohlfeld, and K. Wehrle, ¨ “A quantitative analysis of the impact of arbitrary blockchain content on bitcoin,” in Proceedings of the 22nd International Conference on Financial Cryptography and Data Security (FC). Springer, 2018. [Online]. Available: http://fc18.ifca.ai/preproceedings/6.pdf
  52. M. Grundmann, T. Neudecker, and H. Hartenstein, “Exploiting transaction accumulation and double spends for topology inference in bitcoin,” in 5th Workshop on Bitcoin and Blockchain Research, Financial Cryptography and Data Security 18 (FC). Springer, 2018. [Online]. Available: http://fc18.ifca.ai/bitcoin/papers/bitcoin18-final10.pdf
  53. A. Judmayer, N. Stifter, P. Schindler, and E. Weippl, “Pitchforks in cryptocurrencies: Enforcing rule changes through offensive forking- and consensus techniques (short paper),” in CBT’18: Proceedings of the International Workshop on Cryptocurrencies and Blockchain Technology, Sep 2018. [Online]. Available: https://www.sba-research.org/wpcontent/uploads/2018/09/judmayer2018pitchfork 2018-09-05.pdf
submitted by dj-gutz to myrXiv [link] [comments]

Flux: Revisiting Near Blocks for Proof-of-Work Blockchains

Cryptology ePrint Archive: Report 2018/415
Date: 2018-05-29
Author(s): Alexei Zamyatin∗, Nicholas Stifter, Philipp Schindler, Edgar Weippl, William J. Knottenbelt∗

Link to Paper


Abstract
The term near or weak blocks describes Bitcoin blocks whose PoW does not meet the required target difficulty to be considered valid under the regular consensus rules of the protocol. Near blocks are generally associated with protocol improvement proposals striving towards shorter transaction confirmation times. Existing proposals assume miners will act rationally based solely on intrinsic incentives arising from the adoption of these changes, such as earlier detection of blockchain forks.
In this paper we present Flux, a protocol extension for proof-of-work blockchains that leverages on near blocks, a new block reward distribution mechanism, and an improved branch selection policy to incentivize honest participation of miners. Our protocol reduces mining variance, improves the responsiveness of the underlying blockchain in terms of transaction processing, and can be deployed without conflicting modifications to the underlying base protocol as a velvet fork. We perform an initial analysis of selfish mining which suggests Flux not only provides security guarantees similar to pure Nakamoto consensus, but potentially renders selfish mining strategies less profitable.

References
[1] Bitcoin Cash. https://www.bitcoincash.org/. Accessed: 2017-01-24.
[2] P2pool. http://p2pool.org/. Accessed: 2017-05-10.
[3] G. Andersen. Comment in ”faster blocks vs bigger blocks”. https://bitcointalk.org/index.php?topic=673415.msg7658481#msg7658481, 2014. Accessed: 2017-05-10.
[4] G. Andersen. [bitcoin-dev] weak block thoughts... https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-Septembe011157.html, 2015. Accessed: 2017-05-10.
[5] E. Androulaki, S. Capkun, and G. O. Karame. Two bitcoins at the price of one? double-spending attacks on fast payments in bitcoin. In CCS, 2012.
[6] J. Becker, D. Breuker, T. Heide, J. Holler, H. P. Rauer, and R. Bohme. ¨ Can we afford integrity by proof-of-work? scenarios inspired by the bitcoin currency. In WEIS. Springer, 2012.
[7] I. Bentov, R. Pass, and E. Shi. Snow white: Provably secure proofs of stake. https://eprint.iacr.org/2016/919.pdf, 2016. Accessed: 2016-11-08.
[8] Bitcoin community. OP RETURN. https://en.bitcoin.it/wiki/OP\RETURN. Accessed: 2017-05-10.
[9] Bitcoin Wiki. Merged mining specification. [https://en.bitcoin.it/wiki/Merged\](https://en.bitcoin.it/wiki/Merged)) mining\ specification. Accessed: 2017-05-10.
[10] Blockchain.info. Hashrate Distribution in Bitcoin. https://blockchain.info/de/pools. Accessed: 2017-05-10.
[11] Blockchain.info. Unconfirmed bitcoin transactions. https://blockchain.info/unconfirmed-transactions. Accessed: 2017-05-10.
[12] J. Bonneau, A. Miller, J. Clark, A. Narayanan, J. A. Kroll, and E. W. Felten. Sok: Research perspectives and challenges for bitcoin and cryptocurrencies. In IEEE Symposium on Security and Privacy, 2015.
[13] V. Buterin. Ethereum: A next-generation smart contract and decentralized application platform. https://github.com/ethereum/wiki/wiki/White-Paper, 2014. Accessed: 2016-08-22.
[14] C. Decker and R. Wattenhofer. Information propagation in the bitcoin network. In Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on, pages 1–10. IEEE, 2013.
[15] J. R. Douceur. The sybil attack. In International Workshop on Peer-toPeer Systems, pages 251–260. Springer, 2002.
[16] I. Eyal, A. E. Gencer, E. G. Sirer, and R. Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX Security Symposium on Networked Systems Design and Implementation (NSDI’16). USENIX Association, Mar 2016.
[17] I. Eyal and E. G. Sirer. Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security, pages 436–454. Springer, 2014.
[18] J. Garay, A. Kiayias, and N. Leonardos. The bitcoin backbone protocol: Analysis and applications. In Advances in Cryptology-EUROCRYPT 2015, pages 281–310. Springer, 2015.
[19] A. E. Gencer, S. Basu, I. Eyal, R. Renesse, and E. G. Sirer. Decentralization in bitcoin and ethereum networks. In Proceedings of the 22nd International Conference on Financial Cryptography and Data Security (FC). Springer, 2018.
[20] A. Gervais, G. Karame, S. Capkun, and V. Capkun. Is bitcoin a decentralized currency? volume 12, pages 54–60, 2014.
[21] A. Gervais, G. O. Karame, K. Wust, V. Glykantzis, H. Ritzdorf, ¨ and S. Capkun. On the security and performance of proof of work blockchains. https://eprint.iacr.org/2016/555.pdf, 2016. Accessed: 2016-08-10.
[22] M. Jakobsson and A. Juels. Proofs of work and bread pudding protocols. In Secure Information Networks, pages 258–272. Springer, 1999.
[23] A. Judmayer, A. Zamyatin, N. Stifter, A. G. Voyiatzis, and E. Weippl. Merged mining: Curse or cure? In CBT’17: Proceedings of the International Workshop on Cryptocurrencies and Blockchain Technology, Sep 2017.
[24] G. O. Karame, E. Androulaki, M. Roeschlin, A. Gervais, and S. Capkun. ˇ Misbehavior in bitcoin: A study of double-spending and accountability. volume 18, page 2. ACM, 2015.
[25] A. Kiayias, A. Miller, and D. Zindros. Non-interactive proofs of proof-of-work. Cryptology ePrint Archive, Report 2017/963, 2017. Accessed:2017-10-03.
[26] A. Kiayias, A. Russell, B. David, and R. Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Annual International Cryptology Conference, pages 357–388. Springer, 2017.
[27] Y. Lewenberg, Y. Sompolinsky, and A. Zohar. Inclusive block chain protocols. In Financial Cryptography and Data Security, pages 528–547. Springer, 2015.
[28] Litecoin community. Litecoin reference implementation. https://github.com/litecoin-project/litecoin. Accessed: 2018-05-03.
[29] G. Maxwell. Comment in ”[bitcoin-dev] weak block thoughts...”. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-Septembe011198.html, 2016. Accessed: 2017-05-10.
[30] S. Micali. Algorand: The efficient and democratic ledger. http://arxiv.org/abs/1607.01341, 2016. Accessed: 2017-02-09.
[31] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf, Dec 2008. Accessed: 2015-07-01.
[32] Namecoin community. Namecoin reference implementation. https://github.com/namecoin/namecoin. Accessed: 2017-05-10.
[33] Narayanan, Arvind and Bonneau, Joseph and Felten, Edward and Miller, Andrew and Goldfeder, Steven. Bitcoin and cryptocurrency technologies. https://d28rh4a8wq0iu5.cloudfront.net/bitcointech/readings/princeton bitcoin book.pdf?a=1, 2016. Accessed: 2016-03-29.
[34] K. Nayak, S. Kumar, A. Miller, and E. Shi. Stubborn mining: Generalizing selfish mining and combining with an eclipse attack. In 1st IEEE European Symposium on Security and Privacy, 2016. IEEE, 2016.
[35] K. J. O’Dwyer and D. Malone. Bitcoin mining and its energy footprint. 2014.
[36] R. Pass and E. Shi. Fruitchains: A fair blockchain. http://eprint.iacr.org/2016/916.pdf, 2016. Accessed: 2016-11-08.
[37] C. Perez-Sol ´ a, S. Delgado-Segura, G. Navarro-Arribas, and J. Herrera- ` Joancomart´ı. Double-spending prevention for bitcoin zero-confirmation transactions. http://eprint.iacr.org/2017/394, 2017. Accessed: 2017-06-
[38] Pseudonymous(”TierNolan”). Decoupling transactions and pow. https://bitcointalk.org/index.php?topic=179598.0, 2013. Accessed: 2017-05-10.
[39] P. R. Rizun. Subchains: A technique to scale bitcoin and improve the user experience. Ledger, 1:38–52, 2016.
[40] K. Rosenbaum. Weak blocks - the good and the bad. http://popeller.io/ index.php/2016/01/19/weak-blocks-the-good-and-the-bad/, 2016. Accessed: 2017-05-10.
[41] K. Rosenbaum and R. Russell. Iblt and weak block propagation performance. Scaling Bitcoin Hong Kong (6 December 2015), 2015.
[42] M. Rosenfeld. Analysis of hashrate-based double spending. http://arxiv.org/abs/1402.2009, 2014. Accessed: 2016-03-09.
[43] R. Russel. Weak block simulator for bitcoin. https://github.com/rustyrussell/weak-blocks, 2014. Accessed: 2017-05-10.
[44] A. Sapirshtein, Y. Sompolinsky, and A. Zohar. Optimal selfish mining strategies in bitcoin. http://arxiv.org/pdf/1507.06183.pdf, 2015. Accessed: 2016-08-22.
[45] E. B. Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized anonymous payments from bitcoin. In Security and Privacy (SP), 2014 IEEE Symposium on, pages 459–474. IEEE, 2014.
[46] Satoshi Nakamoto. Comment in ”bitdns and generalizing bitcoin” bitcointalk thread. https://bitcointalk.org/index.php?topic=1790.msg28696#msg28696. Accessed: 2017-06-05.
[47] Y. Sompolinsky, Y. Lewenberg, and A. Zohar. Spectre: A fast and scalable cryptocurrency protocol. Cryptology ePrint Archive, Report 2016/1159, 2016. Accessed: 2017-02-20.
[48] Y. Sompolinsky and A. Zohar. Secure high-rate transaction processing in bitcoin. In Financial Cryptography and Data Security, pages 507–527. Springer, 2015.
[49] Suhas Daftuar. Bitcoin merge commit: ”mining: Select transactions using feerate-with-ancestors”. https://github.com/bitcoin/bitcoin/pull/7600. Accessed: 2017-05-10.
[50] M. B. Taylor. Bitcoin and the age of bespoke silicon. In Proceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems, page 16. IEEE Press, 2013.
[51] F. Tschorsch and B. Scheuermann. Bitcoin and beyond: A technical survey on decentralized digital currencies. In IEEE Communications Surveys Tutorials, volume PP, pages 1–1, 2016.
[52] P. J. Van Laarhoven and E. H. Aarts. Simulated annealing. In Simulated annealing: Theory and applications, pages 7–15. Springer, 1987.
[53] A. Zamyatin, N. Stifter, A. Judmayer, P. Schindler, E. Weippl, and W. J. Knottebelt. (Short Paper) A Wild Velvet Fork Appears! Inclusive Blockchain Protocol Changes in Practice. In 5th Workshop on Bitcoin and Blockchain Research, Financial Cryptography and Data Security 18 (FC). Springer, 2018.
[54] F. Zhang, I. Eyal, R. Escriva, A. Juels, and R. Renesse. Rem: Resourceefficient mining for blockchains. http://eprint.iacr.org/2017/179, 2017. Accessed: 2017-03-24.
submitted by dj-gutz to myrXiv [link] [comments]

Personalized Difficulty Adjustment for Countering the Double-Spending Attack in Proof-of-Work Consensus Protocols

arXiv:1807.02933
Date: 2018-07-09
Author(s): Chi-Ning Chou, Yu-Jing Lin, Ren Chen, Hsiu-Yao Chang, I-Ping Tu, Shih-wei Liao

Link to Paper


Abstract
Bitcoin is the first secure decentralized electronic currency system. However, it is known to be inefficient due to its proof-of-work (PoW) consensus algorithm and has the potential hazard of double spending. In this paper, we aim to reduce the probability of double spending by decreasing the probability of consecutive winning. We first formalize a PoW-based decentralized secure network model in order to present a quantitative analysis. Next, to resolve the risk of double spending, we propose the personalized difficulty adjustment (PDA) mechanism which modifies the difficulty of each participant such that those who win more blocks in the past few rounds have a smaller probability to win in the next round. To analyze the performance of the PDA mechanism, we observe that the system can be modeled by a high-order Markov chain. Finally, we show that PDA effectively decreases the probability of consecutive winning and results in a more trustworthy PoW-based system.

References
[1] Satoshi Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” Consulted, vol. 1, no. 2012.
[2] Ephraim Feig, “A framework for blockchain-based applications,” arXiv preprint arXiv:1803.00892, 2018.
[3] Marta Piekarska Harry Halpin, “Introduction to security and privacy on the blockchain,” in Symposium on Security and Privacy Workshops, 2017 IEEE European Symposium on. IEEE, 2017.
[4] Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar, “Optimal selfish mining strategies in bitcoin,” in Financial Cryptography and Data Security. 2017, pp. 515–532, Springer.
[5] Ghassan Karame, Elli Androulaki, and Srdjan Capkun, “Two bitcoins at the price of one? double-spending attacks on fast payments in bitcoin.,” IACR Cryptology ePrint Archive, vol. 2012.
[6] Ghassan O Karame, Elli Androulaki, Marc Roeschlin, Arthur Gervais, and Srdjan Capkun, “Misbehavior in bitcoin: A study ˇ of double-spending and accountability,” ACM Transactions on Information and System Security (TISSEC), vol. 18, no. 1.
[7] Tobias Bamert, Christian Decker, Lennart Elsen, Roger Wattenhofer, and Samuel Welten, “Have a snack, pay with bitcoins,” in Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on. IEEE, 2013, pp. 1–5.
[8] Chrysoula Stathakopoulou, “A faster bitcoin network,” 2015.
[9] Adrian E Raftery, “A model for high-order markov chains,” Journal of the Royal Statistical Society. Series B (Methodological), pp. 528–539, 1985.
[10] Andre Berchtold and Adrian E Raftery, “The mixture tran- ´sition distribution model for high-order markov chains and non-gaussian time series,” Statistical Science, pp. 328–356, 2002.
[11] Waiki Ching, Michael K Ng, and Shuqin Zhang, “On computation with higher-order markov chains,” in Current Trends in High Performance Computing and Its Applications, pp. 15–24. Springer, 2005.
[12] Michael K Ng and WK Ching, Markov Chains: Models, Algorithms and Applications, Springer, 2006.
[13] Wen Li and Michael K Ng, “On the limiting probability distribution of a transition probability tensor,” Linear and Multilinear Algebra, vol. 62, no. 3.
[14] Jen-Hung Tseng, Yen-Chih Liao, Bin Chong, and Shih-Wei Liao, “Governance on the drug supply chain via gcoin blockchain,” International Journal of Environmental Research and Public Health, 2018.
[15] Shih-Wei Liao, Boyu Lin, and En-Ran Zhou, “Gcoin:wiki, code and whitepaper,” https://g-coin.org and github.com/OpenNetworking/gcoin-community/wiki/Gcoinwhite-paper-English, 2014.
[16] Meni Rosenfeld, “Analysis of hashrate-based double spending,” arXiv preprint arXiv:1402.2009, 2014.
[17] Joshua A Kroll, Ian C Davey, and Edward W Felten, “The economics of bitcoin mining, or bitcoin in the presence of adversaries,” in Proceedings of WEIS, 2013, vol. 2013.
submitted by dj-gutz to myrXiv [link] [comments]

Pitchforks in Cryptocurrencies: Enforcing rule changes through offensive forking- and consensus techniques

Cryptology ePrint Archive: Report 2018/836
Date: 2018-09-05
Author(s): Aljosha Judmayer, Nicholas Stifter, Philipp Schindler, Edgar Weippl

Link to Paper


Abstract
The increasing number of cryptocurrencies, as well as the rising number of actors within each single cryptocurrency, inevitably leads to tensions between the respective communities. As with open source projects, (protocol) forks are often the result of broad disagreement. Usually, after a permanent fork both communities ``mine'' their own business and the conflict is resolved. But what if this is not the case? In this paper, we outline the possibility of malicious forking and consensus techniques that aim at destroying the other branch of a protocol fork. Thereby, we illustrate how merged mining can be used as an attack method against a permissionless PoW cryptocurrency, which itself involuntarily serves as the parent chain for an attacking merge mined branch of a hard fork.

References
  1. J. Bonneau. Why buy when you can rent? bribery attacks on bitcoin consensus. In BITCOIN ’16: Proceedings of the 3rd Workshop on Bitcoin and Blockchain Research, February 2016.
  2. J. Bonneau. Hostile blockchain takeovers (short paper). In 5th Workshop on Bitcoin and Blockchain Research, Financial Cryptography and Data Security 18 (FC). Springer, 2018.
  3. K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. Kosba, A. Miller, P. Saxena, E. Shi, and E. G¨un. On scaling decentralized blockchains. In 3rd Workshop on Bitcoin and Blockchain Research, Financial Cryptography 16, 2016.
  4. I. Eyal, A. E. Gencer, E. G. Sirer, and R. van Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX Security Symposium on Networked Systems Design and Implementation (NSDI’16). USENIX Association, Mar 2016.
  5. I. Eyal and E. G. Sirer. Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security, pages 436–454. Springer, 2014.
  6. A. Gervais, G. O. Karame, K. W¨ust, V. Glykantzis, H. Ritzdo rf, and S. Capkun. On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC, pages 3–16. ACM, 2016.
  7. A. Judmayer, A. Zamyatin, N. Stifter, A. G. Voyiatzis, and E. Weippl. Merged mining: Curse or cure? In CBT’17: Proceedings of the International Workshop on Cryptocurrencies and Blockchain Technology, Sep 2017.
  8. A. Kiayias, A. Miller, and D. Zindros. Non-interactive proofs of proof-of-work. Cryptology ePrint Archive, Report 2017/963, 2017. Accessed:2017-10-03.
  9. J. A. Kroll, I. C. Davey, and E. W. Felten. The economics of bitcoin mining, or bitcoin in the presence of adversaries. In Proceedings of WEIS, volume 2013, page 11, 2013.
  10. K. Liao and J. Katz. Incentivizing blockchain forks via whale transactions. In International Conference on Financial Cryptography and Data Security, pages 264–279. Springer, 2017.
  11. P. McCorry, A. Hicks, and S. Meiklejohn. Smart contracts for bribing miners. In 5th Workshop on Bitcoin and Blockchain Research, Financial Cryptography and Data Security 18 (FC). Springer, 2018.
  12. Narayanan, Arvind and Bonneau, Joseph and Felten, Edward and Miller, Andrew and Goldfeder, Steven. Bitcoin and cryptocurrency technologies. http://bitcoinbook.cs.princeton.edu/, 2016. Accessed: 2016-03-29.
  13. K. Nayak, S. Kumar, A. Miller, and E. Shi. Stubborn mining: Generalizing selfish mining and combining with an eclipse attack. In 1st IEEE European Symposium on Security and Privacy, 2016. IEEE, 2016.
  14. J. Teutsch, S. Jain, and P. Saxena. When cryptocurrencies mine their own business. In Financial Cryptography and Data Security (FC 2016), Feb 2016.
  15. Y. Velner, J. Teutsch, and L. Luu. Smart contracts make bitcoin mining pools vulnerable. In International Conference on Financial Cryptography and Data Security, pages 298–316. Springer, 2017.
  16. A. Zamyatin, N. Stifter, A. Judmayer, P. Schindler, E. Weippl, and W. J. Knottebelt. (Short Paper) A Wild Velvet Fork Appears! Inclusive Blockchain Protocol Changes in Practice. In 5th Workshop on Bitcoin and Blockchain Research, Financial Cryptography and Data Security 18 (FC). Springer, 2018.
submitted by dj-gutz to myrXiv [link] [comments]

Edward W. Felten, 'TMI: Information, Identity, and Privacy' Reality of Bitcoin Mining - Nicehash - HINDI - PART 1 Best Bitcoin Mining Software of 2020 Bitcoin Miner V 1 9 2020 Bitcoin Miner Pool Deutsch - Erklärungsvideo

Edward Felten; Andrew Miller; Steven Goldfeder [NBF + 16] Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven Goldfeder. Bitcoin and Cryptocurrency Technologies. Princeton ... Edward Felten is director of Princeton's Center for Information Technology Policy. Andrew Miller is a PhD student in computer science at the University of Maryland. Steven Goldfeder is a PhD student in computer science at Princeton. Innehållsförteckning PREFACE vii FOREWORD The Long Road to Bitcoin ix Jeremy clark 1 Introduction to Cryptography and Cryptocurrencies 1 2 How Bitcoin Achieves ... Crypto Mining; Top Crypto Coins; Storage; Books; Gifts; Blog; Home →Tags Edward Felten. Tag Archives: Edward Felten. Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Posted on September 23, 2018 by CryptoGuy October 17, 2018. Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction (9780691171692): Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew ... CiteSeerX - Document Details (Isaac Councill, Lee Giles, Pradeep Teregowda): The Bitcoin digital currency depends for its correctness and stability on a combination of cryptography, distributed algorithms, and incentivedriven behavior. We examine Bitcoin as a consensus game and determine that it relies on separate consensus about the rules and about game state. The Economics of Bitcoin Mining, or Bitcoin in the Presence of Adversaries Joshua A. Kroll, Ian C. Davey, and Edward W. Felten Princeton University Abstract The Bitcoin digital currency depends for its correctness and stability on a combination of cryptography, distributed algorithms, and incentive-driven behavior. We examine Bitcoin as a consensus game and deter-mine that it relies on ...

[index] [47200] [44513] [28443] [49733] [51344] [35103] [21807] [2525] [24501] [2124]

Edward W. Felten, 'TMI: Information, Identity, and Privacy'

Our clandestine Bitcoin mine with independent exhaust and a/c cooling including 400amps of power and Camera system!! Now we're Mining. Ok. #BTC #Bitcoin #Bitcoin_Free #Bitcoin_hack #Bitcoin_software #Bitcoin_mining bitcoin mining, bitcoin ben, bitcoin news, bitcoin cash, bitcoin song, bitcoin and friends, bitcoin atm, bitcoin 2019 ... Mining bitcoin using nicehash. Graphic Cards - ZOTAC GeForce GTX 1070 MINI 8GB 256-Bit GDDR5 NOTE: This is not a financial advice. Kindly do your own research before making any investment. All the ... The right to be anonymous and privacy issues with social media; specifically Facebook. Felten is the founding director of the Center for Information Technology Policy at Princeton University ... bitcoin go to moon, new g bitcoin, g edward griffin bitcoin, bitcoin halving, bitcoin hack 2019, bitcoinhex, bitcoin history, bitcoin hacked, bitcoin hyperwave, bitcoin heist, bitcoin hardware ...

#