Shamir’s Secret Explained ... - Bitcoin Insider

Researchers Retract Claim Of Link Between Alleged Silk Road Mastermind And Founder Of Bitcoin

Researchers Retract Claim Of Link Between Alleged Silk Road Mastermind And Founder Of Bitcoin submitted by montseayo to Bitcoin [link] [comments]

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]

Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees

arXiv:1805.11060
Date: 2018-05-28
Author(s): Giulia Fanti, Shaileshh Bojja Venkatakrishnan, Surya Bakshi, Bradley Denby, Shruti Bhargava, Andrew Miller, Pramod Viswanath

Link to Paper


Abstract
Recent work has demonstrated significant anonymity vulnerabilities in Bitcoin's networking stack. In particular, the current mechanism for broadcasting Bitcoin transactions allows third-party observers to link transactions to the IP addresses that originated them. This lays the groundwork for low-cost, large-scale deanonymization attacks. In this work, we present Dandelion++, a first-principles defense against large-scale deanonymization attacks with near-optimal information-theoretic guarantees. Dandelion++ builds upon a recent proposal called Dandelion that exhibited similar goals. However, in this paper, we highlight simplifying assumptions made in Dandelion, and show how they can lead to serious deanonymization attacks when violated. In contrast, Dandelion++ defends against stronger adversaries that are allowed to disobey protocol. Dandelion++ is lightweight, scalable, and completely interoperable with the existing Bitcoin network. We evaluate it through experiments on Bitcoin's mainnet (i.e., the live Bitcoin network) to demonstrate its interoperability and low broadcast latency overhead.

References
[1] [n. d.]. AWS Regions and Endpoints. ([n. d.]). http://docs.aws.amazon.com/general/latest/grande.html.
[2] [n. d.]. Bitcoin Core integration/staging tree. ([n. d.]). https://github.com/bitcoin/bitcoin.
[3] [n. d.]. Chainalysis. ([n. d.]). https://www.chainalysis.com/.
[4] [n. d.]. The Kovri I2P Router Project. ([n. d.]). https://github.com/monero-project/kovri.
[5] [n. d.]. Monero. ([n. d.]). https://getmonero.org/home.
[6] 2015. Bitcoin Core Commit 5400ef6. (2015). https://github.com/bitcoin/bitcoin/commit/5400ef6bcb9d243b2b21697775aa6491115420f3.
[7] 2016. reddit/monero. (2016). https://www.reddit.com/Monero/comments/4aki0k/what_is_the_status_of_monero_and_i2p/.
[8] Elli Androulaki, Ghassan O Karame, Marc Roeschlin, Tobias Scherer, and Srdjan Capkun. 2013. Evaluating user privacy in bitcoin. In International Conference on Financial Cryptography and Data Security. Springer, 34–51.
[9] Maria Apostolaki, Aviv Zohar, and Laurent Vanbever. 2016. Hijacking Bitcoin: Large-scale Network Attacks on Cryptocurrencies. arXiv preprint arXiv:1605.07524 (2016).
[10] Krishna B Athreya and Peter E Ney. 2004. Branching processes. Courier Corporation.
[11] Alex Biryukov, Dmitry Khovratovich, and Ivan Pustogarov. 2014. Deanonymisation of clients in Bitcoin P2P network. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 15–29.
[12] Alex Biryukov and Ivan Pustogarov. 2015. Bitcoin over Tor isn’t a good idea. In Symposium on Security and Privacy. IEEE, 122–134.
[13] John Bohannon. 2016. Why criminals can’t hide behind Bitcoin. Science (2016).
[14] Shaileshh Bojja Venkatakrishnan, Giulia Fanti, and Pramod Viswanath. 2017. Dandelion: Redesigning the Bitcoin Network for Anonymity. POMACS 1, 1 (2017), 22.
[15] D. Chaum. 1988. The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of cryptology 1, 1 (1988).
[16] Ramnath K Chellappa and Raymond G Sin. 2005. Personalization versus privacy: An empirical examination of the online consumer’s dilemma. Information technology and management 6, 2 (2005), 181–202.
[17] H. Corrigan-Gibbs and B. Ford. 2010. Dissent: accountable anonymous group messaging. In CCS. ACM.
[18] George Danezis, Claudia Diaz, Emilia Käsper, and Carmela Troncoso. 2009. The wisdom of Crowds: attacks and optimal constructions. In European Symposium on Research in Computer Security. Springer, 406–423.
[19] George Danezis, Claudia Diaz, Carmela Troncoso, and Ben Laurie. 2010. Drac: An Architecture for Anonymous Low-Volume Communications.. In Privacy Enhancing Technologies, Vol. 6205. Springer, 202–219.
[20] R. Dingledine, N. Mathewson, and P. Syverson. 2004. Tor: The second-generation onion router. Technical Report. DTIC Document.
[21] G. Fanti, P. Kairouz, S. Oh, and P. Viswanath. 2015. Spy vs. Spy: Rumor Source Obfuscation. In SIGMETRICS Perform. Eval. Rev., Vol. 43. 271–284. Issue 1.
[22] Giulia Fanti and Pramod Viswanath. 2017. Anonymity Properties of the Bitcoin P2P Network. arXiv preprint arXiv:1703.08761 (2017).
[23] M.J. Freedman and R. Morris. 2002. Tarzan: A peer-to-peer anonymizing network layer. In Proc. CCS. ACM.
[24] Sam Frizell. 2015. Bitcoins Are Easier To Track Than You Think. Time (January 2015).
[25] Adam Efe Gencer and Emin Gün Sirer. 2017. State of the Bitcoin Network. Hacking Distributed, http://hackingdistributed.com/2017/02/15/state-of-the-bitcoin-network/. (February 2017).
[26] S. Goel, M. Robson, M. Polte, and E. Sirer. 2003. Herbivore: A scalable and efficient protocol for anonymous communication. Technical Report.
[27] P. Golle and A. Juels. 2004. Dining cryptographers revisited. In Advances in Cryptology-Eurocrypt 2004.
[28] Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro, and Sharon Goldberg. 2016. TumbleBit: An untrusted Bitcoin-compatible anonymous payment hub. Technical Report. Cryptology ePrint Archive, Report 2016/575.
[29] TE Jedusor. 2016. Mimblewimble. (2016).
[30] Philip Koshy. 2013. CoinSeer: A Telescope Into Bitcoin. Ph.D. Dissertation. The Pennsylvania State University.
[31] Philip Koshy, Diana Koshy, and Patrick McDaniel. 2014. An analysis of anonymity in bitcoin using p2p network traffic. In International Conference on Financial Cryptography and Data Security. Springer, 469–485.
[32] Greg Maxwell. 2013. CoinJoin: Bitcoin privacy for the real world. In Post on Bitcoin Forum.
[33] Dave McMillen. 2017. Mirai IoT Botnet: Mining for Bitcoins? SecurityIntelligence (April 2017).
[34] Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M Voelker, and Stefan Savage. 2013. A fistful of bitcoins: characterizing payments among men with no names. In Proceedings of the 2013 conference on Internet measurement conference. ACM, 127–140.
[35] Marc Mezard and Andrea Montanari. 2009. Information, physics, and computation. Oxford University Press.
[36] Andrew Miller, James Litton, Andrew Pachulski, Neal Gupta, Dave Levin, Neil Spring, and Bobby Bhattacharjee. 2015. Discovering Bitcoin’s public topology and influential nodes. (2015).
[37] Prateek Mittal, Matthew Wright, and Nikita Borisov. 2013. Pisces: Anonymous communication using social networks. In NDSS. ACM.
[38] Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008).
[39] Micha Ober, Stefan Katzenbeisser, and Kay Hamacher. 2013. Structure and anonymity of the bitcoin transaction graph. Future internet 5, 2 (2013), 237–250.
[40] Larry L Peterson and Bruce S Davie. 2007. Computer networks: a systems approach. Elsevier.
[41] P. C. Pinto, P. Thiran, and M. Vetterli. 2012. Locating the source of diffusion in large-scale networks. Physical review letters 109, 6 (2012), 068702.
[42] Fergal Reid and Martin Harrigan. 2013. An analysis of anonymity in the bitcoin system. In Security and privacy in social networks. Springer, 197–223.
[43] Michael K Reiter and Aviel D Rubin. 1998. Crowds: Anonymity for web transactions. ACM Transactions on Information and System Security (TISSEC) 1, 1 (1998), 66–92.
[44] Dorit Ron and Adi Shamir. 2013. Quantitative analysis of the full bitcoin transaction graph. In International Conference on Financial Cryptography and Data Security. Springer, 6–24.
[45] Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. 2014. CoinShuffle: Practical decentralized coin mixing for Bitcoin. In European Symposium on Research in Computer Security. Springer, 345–364.
[46] Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized anonymous payments from bitcoin. In Symposium on Security and Privacy. IEEE, 459–474.
[47] Alexander Schrijver. 2002. Combinatorial optimization: polyhedra and efficiency. Vol. 24. Springer Science & Business Media.
[48] Rob Sherwood, Bobby Bhattacharjee, and Aravind Srinivasan. 2005. P5: A protocol for scalable anonymous communication. Journal of Computer Security 13, 6 (2005), 839–876.
[49] Jelle van den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. [n. d.]. Scalable Private Messaging Resistant to Traffic Analysis. ([n. d.]).
[50] Zhaoxu Wang, Wenxiang Dong, Wenyi Zhang, and Chee Wei Tan. 2014. Rumor source detection with multiple observations: Fundamental limits and algorithms. In ACM SIGMETRICS Performance Evaluation Review, Vol. 42. ACM, 1–13.
[51] David Isaac Wolinsky, Henry Corrigan-Gibbs, Bryan Ford, and Aaron Johnson. 2012. Dissent in Numbers: Making Strong Anonymity Scale.. In OSDI. 179–182.
[52] M. Zamani, J. Saia, M. Movahedi, and J. Khoury. 2013. Towards provably-secure scalable anonymous broadcast. In USENIX FOCI.
[53] Bassam Zantout and Ramzi Haraty. 2011. I2P data communication system. In Proceedings of ICN. Citeseer, 401–409.
[54] Kai Zhu and Lei Ying. 2014. A robust information source estimator with sparse observations. Computational Social Networks 1, 1 (2014), 3.
submitted by dj-gutz to myrXiv [link] [comments]

Why do I believe it was BCN destiny to be born in 2012?

Why do I believe it was BCN destiny to be born in 2012? Just look at this and see yourself:
1983 - Blind signatures were invented by David Chaum link 1997 - HashCash (proof of work system) was invented by Adam Back link
2001 - Ring signatures were invented by Ron Rivest, Adi Shamir, and Yael Tauman link
2003 - Mart n Abadi, Michael Burrows, and Ted Wobber presented "Moderately hard, memory-bound functions"link
2004 - Patrick P. Tsang and Victor K. Wei presented their paper "Short linkable ring signatures for e-voting, e-cash and attestation" link
2005 - Matthew Franklin and Haibin Zhang with "Unique Group Signatures" study link
2005 - Exponential memory-bound functions for proof of work protocols by Fabien Coelho link +2006 - "Traceable Ring Signature" by Fujisaki and Suzuki link
2008 - Bitcoin whitepaper by Satoshi Nakamoto link
2009 - Stronger key derivation via sequential memory-hard functions by Colin Percival link
2009 - First Bitcoin block was generated
2010 -2012 - Bitcoin Anonymity Problem Discussions link
2011 - An Analysis of Anonymity in the Bitcoin System, Fergal Reid and Martin Harrigwere link
5/15/2012 - Dorit Ron and Adi Shamir made Quantitative Analysis of the Full Bitcoin Transaction Graph link
6/8/2012 - Bytecoin Wiki started link
6/30/2012 - Bytecoin launch announcement link- first news
7/4/2012 - First BCN block was generated link
8/6/2012 - Destination Address Anonymization in Bitcoin (one-time addresses in BCN) link
10/19/2012 - Evaluating User Privacy in Bitcoin by Elli Androulaki, Ghassan O. Karame, Marc Roeschlin, Tobias Scherer, Srdjan Capkun. link
12/12/2012 -CryptoNote whitepaper v 1.0 link
12/13/2012 - Analysis of hashrate-based double-spending, Meni Rosenfeld link
10/17/2013 - CryptoNote whitepaper v 2.0 link
Here we see how the technology logically came to the advent of cryptocurrencies with ring signature and memory-bound function PoW implementation. Soon after Bitcoin's release the community started to raise concerns about its anonymity with multiple solutions and propositions. High concentration of theoretical papers on these topics in 2009-2011 most probably spurred the brightest minds to make attempts of practical e-cash with ring signatures realization. Therefore, BCN couldn't but appear in 2012.
Based on https://bitcointalk.org/index.php?topic=512747.msg7093354#msg7093354
submitted by joethejudge77 to BytecoinBCN [link] [comments]

Let's contact Ron and Shamir asking them to help us fully map MtGox presence on the blockchain.

Some time ago there was a really good paper studying the blockchain. In this they studied the whole blockchain and connected the accounts that sent money together as coming from the same wallet.
Quantitative Analysis of the Full Bitcoin Transaction Graph from Dorit Ron and Adi Shamir
By doing this they could identify several whales.
Now, I think that with the situation with MtGox we should ask the help from those two researchers, and fully map MtGox activity. If we all share the entry point and the exit address in which we sent money and received money from MtGox it should be quite easy to just map the whole animal out. This would be divided, I suppose, in entry address, exit address, inside address never used but only rarely to store coins, in between address. And then maybe we can start to see exactly from which address some bitcoins have been siphoned out.
It's just a simple unidirectional graph. I don't know how many nodes will it have, but probably we should be able to even draw it.
Any comments before contacting them?
submitted by pietrosperoni to Bitcoin [link] [comments]

Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials IOHK  Consensus protocols - efficiency Adi Shamir: Micali: IOHK  Consensus protocols - algorithmic weight

Adi Shamir's 257 research works with 60,436 citations and 13,612 reads, including: Consistent High Dimensional Rounding with Side Information Yevgeniy Dodis Adi Shamir Noah Stephens-Davidowitz Daniel Wichs. 2014 JOFC Improved Practical Attacks on Round-Reduced Keccak. Itai Dinur Orr Dunkelman Adi Shamir. 2014 JOFC A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony. Orr Dunkelman Nathan Keller Adi Shamir. 2014 ASIACRYPT Cryptanalysis of Iterated Even-Mansour Schemes with Two Keys. Itai Dinur ... Shamir’s Secret is a cryptographic method created by the Israeli cryptographer Adi Shamir. The mathematically proven method allows people to secure a secret in a distributed fashion. The secret sharing technique takes an original secret and divides it into parts and each part is either hidden in different locations or parts of the secret is given to trusted participants of the scheme. The ... Bitcoin How & Why to Set Up a Shamir Backup on Trezor Model T. The Shamir backup combines the simplicity of a BIP 39 seed phrase with some advantages of multisig setups. Here’s how and why you should set it up. By. Vlad Costea. Published. 8 seconds ago. A year ago, Trezor has once again brought open-source innovation in the hardware wallet industry by creating a user-friendly adaptation of ... Dorit Ron and Adi Shamir Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Israel {dorit.ron,adi.shamir}@weizmann.ac.il Abstract. The Bitcoin scheme is a rare example of a large scale global payment system in which all the transactions are publicly accessible (but in an anonymous way). We downloaded the full history of this scheme, and analyzed many ...

[index] [25572] [24096] [40039] [32967] [45070] [25699] [694] [11445] [21504] [14957]

Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials

Leading cryptographers at the conference included Whitfield Diffie, pioneer of the public key cryptography that made Bitcoin possible, and Ron Rivest, Adi Shamir, and Leonard Adleman, who came up ... Talk at FSE 2013. Itai Dinur and Orr Dunkelman and Adi Shamir. See http://www.iacr.org/cryptodb/data/paper.php?pubkey=25067 Leading cryptographers at the conference included Whitfield Diffie, pioneer of the public key cryptography that made Bitcoin possible, and Ron Rivest, Adi Shamir, and Leonard Adleman, who came up ... The BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category goes, in this tenth edition, to Shafi Goldwasser, Silvio Micali, Ronald Rivest and Adi ... The BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category goes, in this tenth edition, to Shafi Goldwasser, Silvio Micali, Ronald Rivest and Adi ...

#