Háskólinn í Reykjavík, Haustönn 2016      
Tölvunarfræðideild [7,8]50-CYCR
Cryptocurrencies

Reykjavik University, Fall 2016
Computer Science [7,8]50-CYCR
Cryptocurrencies

General Information:

Here is a shortcut to the course schedule/homework page.

Class meetings: M-F 9am-12pm and 1pm-4pm in [varies; see the schedule page]

Instructor: Jonathan Poritz     Office: V3??     E-mail: jonathan@poritz.net

Text: No text! We will be using various materials freely available on the Internet plus some supplements written for the course by your instructor.  

 

Possible Supplementary Topics

  1. Secret Sharing: This is about dividing a secret into pieces which are entrusted to several different parties, some fraction of which must work together to reassemble the original secret when it is needed later. There are various models of what kinds of failures can be tolerated and what kinds of actions the actors, both good and bad, are expected to make.

    References are:

    1. Shamir, Adi, How to Share a Secret, Commun. ACM, Vol. 22, No. 11 (1979), Pp. 612—613, online here or here.
    2. Benaloh, Josh Cohen. Secret sharing homomorphisms: Keeping shares of a secret secret, Conf. on the Theory and Appl. of Cryptographic Techniques, Springer Verlag, (1986), Pp. 251—260, online here.
    3. Feldman, Paul, A practical scheme for non-interactive verifiable secret sharing, 28th Annual Symp. on Foundations of Comp. Sci., IEEE, (1987), Pp. 427—438, online here.
    4. Ito, Mitsuru, Akira Saito, and Takao Nishizeki. Secret sharing scheme realizing general access structure, Electronics and Comm. in Japan (Part III: Fundamental Electronic Science), 72.9 (1989), Pp. 56—64, online here.
    5. Simmons, Gustavus J., How to (really) share a secret, Proc. on Adv. in cryptology, Springer-Verlag, (1990), Pp. 390—448, online here.
    6. Pedersen, Torben Pryds, Non-interactive and information-theoretic secure verifiable secret sharing, Annual Internat. Cryptology Conference, Springer Verlag (1991), Pp. 129—140, online here.

    For this project, in addition to a presentation to the class of the ideas, it would be nice to write some high quality code that would implement whichever of the above approaches seems most useful.

  2. Merkle trees: A data structure used in the Bitcoin protocol and in other applications where performanace and high security is important.

    References are:

    1. Becker, Georg, Merkle signature schemes, Merkle trees and their cryptanalysis, (2008), online here.
    2. Devanbu, Premkumar, Gertz, Michael, Martel, Charles, Stubblebine, Stuart G., Authentic third-party data publication, Data and Application Security, Springer Verlag, (2002), Pp. 101—112, online here.
    3. Laurie, Ben, and Doctorow, Cory Computing: Secure the Internet, Nature, 491.7424, (2012), Pp. 325—326, available online at RU.
    4. Merkle, Ralph, Protocols for public key cryptosystems, IEEE Proc. Symp. Security and Privacy, (1980), Pp. 122—133 online here
    5. Merkle, Ralph, A certified digital signature, Conf. on the Th. and Appl. of Cryptology, Springer Veralg, (1989), Pp. 218—238, online here.

  3. Multisignatures: Used in the Bitcoin protocol to spread out responsability for transactions.

    References are:

    1. Bellare, Mihir, and Neven, Gregory, Identity-based multi-signatures from RSA, Cryptographers' Track at the RSA Conference, Springer Verlag, (2007), Pp. 145—162, online here.
    2. Boldyreva, Alexandra, Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme, Internat. Workshop on Public Key Cryptography, Springer Verlag, (2003), Pp. 31—46, online here.
    3. Harn, Lein, Group-oriented (t, n) threshold digital signature scheme and digital multisignature, IEE Proc.-Computers and Digital Techniques, 141.5, (1994), Pp. 307-313, online here.
    4. Petersen, H., P. Horster, and Michels, M., Blind multisignature schemes and their relevance to electronic voting 11th Annual Computer Sec. Appl. Conf., IEEE Press. (1995), Pp. 149—155, online here.

  4. Anonymity Issues: There is a lot of delicate crypto work here, but anonymity and privacy are generally important topics, in cryptocurrencies and elsewhere. A presentation on the Tor would be very interesting and valuable, for example, as would specific discussions of Bitcoin anonymization services, on the practical end, and zero-knowledge proofs on the (much more) theoretical end

    References are:

    1. Bonneau, Joseph, Narayanan, Arvind, Clark, Jeremy, Kroll, Joshua A., and Felten, Edward W., Mixcoin: Anonymity for Bitcoin with accountable mixes, Internat. Conf. on Financial Cryptography and Data Security, Springer Verlag, (2014), Pp. 486—504, online here.
    2. Bonneau, Joseph, Miller, Joseph, Clark, Jeremy, Narayanan, Arvind, Kroll, Joshua A., and Felten, Edward W., SoK: Research perspectives and challenges for bitcoin and cryptocurrencies 2015 IEEE Symp. on Sec. and Privacy, IEEE, (2015), Pp. 104-121, online here.
    3. Camenisch, Jan, and Van Herreweghen, Els, Design and implementation of the idemix anonymous credential system., Proc. of the 9th ACM conf. on Computer and commun. sec., ACM, (2002), Pp. 21—30, online here.
    4. Dingledine, Roger, Mathewson, Nick, and Syverson, Paul, Tor: The second-generation onion router, Naval Research Lab, Washington, DC, USA, (2004), online here.
    5. Goldreich, Oded, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Springer Verlag, 1999.
    6. Goldreich, Oded, Foundations of Cryptography (Fragments of a Book), Draft (long, very preliminary) 1995; The Foundations of Modern Cryptography (Version Nr. 3.2), Draft (much shorter, more polished) 2000; Both superceded by the (non-free) Foundations of Cryptography, Volume 1: Basic Tools and Foundations of Cryptography, Volume 2. Basic Applications.
    7. McCoy, Damon, Bauer, Kevin, Grunwald, Dirk, Kohno, Tadayoshi, and Sicker, Douglas, Shining light in dark places: Understanding the Tor network, Internat. Symp. on Privacy Enhancing Technologies Symposium, Springer Verlag, (2008), Pp. 63—76, online here.
    8. Murdoch, Steven J., and Danezis, George, Low-cost traffic analysis of Tor, IEEE Symp. on Sec. and Privacy (S&P'05), IEEE, (2005), Pp. 183—195, online here.
    9. Narayanan, Arvind, and Shmatikov, Vitaly, Robust de-anonymization of large sparse datasets, 2008 IEEE Symp. on Sec. and Privacy, IEEE, (2008), Pp. 111-125, online here.

  5. Blind Signatures and Chaum's E-Cash: An early approach to electronic currency which placed great importance on replicating the anonymity properties of physical cash — built by Chaum on top of a nice cryptographic primitive.

    References are:

    1. Camenisch, Jan, Hohenberger, Susan and Lysyanskaya, Anna, Compact e-cash, Annual Internat. Conf. on the Theory and Applications of Cryptographic Techniques, Springer Verlag, (2005), Pp. 302—321, online here.
    2. Camenisch, Jan, Hohenberger, Susan, and Lysyanskaya, Anna, Balancing accountability and privacy using e-cash, Internat. Conf. on Sec. and Cryptography for Networks, Springer Verlag, (2006), Pp. 141-155, online here.
    3. Chaum, David, Blind signatures for untraceable payments, Adv. in cryptology, CRYPTO '83, Springer Verlag, (1983), Pp. 199—203, online here.
    4. Chaum, David, Security without identification: Transaction systems to make big brother obsolete, Comm. of the ACM, 28.10, (1985), Pp. 1030—1044, online here.
    5. Chaum, David, The dining cryptographers problem: Unconditional sender and recipient untraceability, J. of cryptology, 1.1, (1988), Pp. 65-75, online here.
    6. Chaum, David, Fiat, Amos, and Naor, Moni, Untraceable electronic cash, Proc. on Adv. in cryptology, Springer Verlag, (1990), Pp. 319—327, online here
    7. Golle, Philippe, and Juels, Ari, Dining cryptographers revisited, Internat. Conf. on the Th. and Appl. of Cryptographic Techniques, Springer Verlag, (2004), Pp. 456&mdash473, online here
    8. see also the Wikipedia pages on Blind signature and Dining cryptographers problem

  6. Paxos, a Consensus Algorithm: A powerful and wide-used algorithm for consensus, where distributed parties must come to some common agreement.

    References are:

    1. Boichat, Romain, Dutta, Partha, Frølund, Svend, and Guerraoui, Rachid, Deconstructing paxos, ACM Sigact News, 34.1, (2003), Pp. 47—67, online here.
    2. De Prisco, Roberto, Lampson, Butler, and Lynch, Nancy, Revisiting the Paxos algorithm, Theoretical Computer Science, 243.1, (2000), Pp. 35—91, online here.
    3. Lamport, Leslie, Paxos made simple, ACM Sigact News, 32.4,(2001), Pp. 18—25, online here.
    4. Lamport, Leslie, Fast paxos, Distributed Computing, 19.2, (2006), Pp. 79—103, online here.
    5. Wattenhofer, Roger, The Science of the Blockchain, Inverted Forest Publishing, 2016. [Note: you can borrow this book from your instructor.]

  7. E-voting Schemes: Voting is another high-value social process which some have tried to move to the Internet, with corresponding concerns about security and privacy.

    References are:

    1. Karlof, Chris, Sastry, Naveen, and Wagner, David, Cryptographic Voting Protocols: A Systems Perspective, USENIX Security., Vol. 5. (2005), Pp. 33—50, online here.
    2. Lee, Yunho, Park, Sangjoon, Mambo, Masahiro, Kim, Seungjoo, and Won, Dongho, Towards trustworthy e-voting using paper receipts, Computer Standards & Interfaces, 32.5, (2010), Pp. 305—311, online here.
    3. Moran, Tal, and Naor, Moni, Receipt-free universally-verifiable voting with everlasting privacy, Annual Internat. Cryptology Conference, Springer Verlag, (2006), Pp. 373—392, online here.
    4. Neff, C. Andrew, A verifiable secret shuffle and its application to e-voting, Proc. of the 8th ACM conf. on Computer and Comm. Sec., ACM, (2001), Pp., 116—125, online here.

  8. Report on Some Failure Modes: To see how well cryptocurrencies may survive in the real world, it is instructive to look at some of the famous failures of the most wide-spread one, Bitcoin. A particularly interest case was the failure of the exchange Mt. Gox.

    References are:

    1. bitcoinwiki, Mt. Gox, page on the bitcoin wiki, (2015), online here.
    2. Christin, Nicolas, Traveling the Silk Road: A measurement analysis of a large anonymous online marketplace, Proc. of the 22nd internat. conf. on World Wide Web, ACM, (2013), Pp. 213-224, online here.
    3. Decker, Christian, and Wattenhofer, Roger, Bitcoin transaction malleability and MtGox, European Symp. on Research in Computer Sec., Springer Verlag, (2014), Pp. 313—326, online here.
    4. Eyal, Ittay, and Sirer, Emin Güaut;n, Majority is not enough: Bitcoin mining is vulnerable, Internat. Conf. on Financial Cryptography and Data Security, Springer Verlag, (2014), Pp. 436—454, online here.
    5. Moore, Tyler, and Christin, Nicolas, Beware the middleman: Empirical analysis of Bitcoin-exchange risk, Internat. Conf. on Financial Cryptography and Data Sec., Springer Verlag, (21013), Pp. 25—33), online here.
    6. Soska, Kyle, and Christin, Nicolas, Measuring the longitudinal evolution of the online anonymous marketplace ecosystem, 24th USENIX Sec. Symp. (USENIX Security 15), (2015), Pp. 33—48, online here.

  9. Your Choice: If there is something of your interest but related [in some small way — and isn't nearly everything in computer science?] to the subject of cryptocurrencies, feel free to propose it. How about Propose a topic to your instructor — and the sooner the better!
 

 

References

  1. General crypto
    1. Chaum, David, Private signature and proof systems, US Patent 5493614 A, 1996.
    2. Ferguson, Niels, Schneier, Bruce, and Kohno, Tadayoshi, Cryptography Engineering: Design Principles and Practical Applications, John Wiley and Sons, 2010.
    3. Goldreich, Oded, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Springer Verlag, 1999.
    4. Goldreich, Oded, Foundations of Cryptography (Fragments of a Book), Draft (long, very preliminary) 1995; The Foundations of Modern Cryptography (Version Nr. 3.2), Draft (much shorter, more polished) 2000; Both superceded by the (non-free) Foundations of Cryptography, Volume 1: Basic Tools and Foundations of Cryptography, Volume 2. Basic Applications.
    5. Johnson, Don, Menezes, Alfred, and Vanstone, Scott, The Elliptic Curve Digital Signature Algorithm (ECDSA), Int. J. Infor. Sec. (2001), pp. 36-63.
    6. Poritz, Jonathan, Yet Another Introductory Number Theory Textbook, number theory and crypto applications, released under a CC license, 2015.
  2. Cryptocurrency technicalities
    1. Antonopoulos, Andreas, Mastering Bitoin: Unlocking Digital Currencies, O'Reilly Media, 1st ed. 2015, 2nd ed. 2016 (for the early release ebook; print expected in 2017).
    2. Koblitz, Neal, and Menezes, Alfred J., Cryptocash, cryptocurrencies, and cryptocontracts, Designs, Codes and Cryptography, 78.1 (2016), Pp. 87—102, online here.
    3. Nakamoto, Satoshi, Bitcoin: A Peer-to-Peer Electronic Cash System, posted to www.cryptovest.co.uk on 31 October 2008.
    4. Narayanan, Arvind, Bonneau, Joseph, Felten, Edward, and Miller, Andrew, and Goldfeder, Steven Bitcoin and Cryptocurrency Technologies, with a preface by Jeremy Clark, Draft version from 9 February 2016. Superceded by the (non-free) Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction 2016, Princeton University Press.
    5. Wattenhofer, Roger, The Science of the Blockchain, Inverted Forest Publishing, 2016.
  3. Cryptocurrency hype (a random but typical selection)
    1. Swan, Melanie, Blockchain: Blueprint for a New Economy, O'Reilly Media, 2015.
    2. Tapscott, Don and Tapscott, Alex, Blockchain Revolution: How the Technology Behind Bitcoin Is Changing Money, Business, and the World, Portfolio, 2016.
    3. Warburg, Bettina, How the blockchain will radically transform the economy, TED talk, 2016.
 

 

Programming Resources

A public key

Here is an RSA public key you should fee free to use (in the near future — it is set to expire 2016-12-27) when sending email to jonathan@poritz.net. Note this key is stored in an "ASCII armored form" as produced by GnuPG.  

 

An entirely random collection of bitcoin/blockchain/cryptocurrency organizations

     Bitcoin.org was "originally registered and owned by Bitcoin's first two developers, Satoshi Nakamoto and Martti Malmi," but "Bitcoin.org is not Bitcoin's official website." "Today the site is an independent open source project with contributors from around the world."
     Institute for Blockchain Studies seems centered on the work of Melanie Swan (of somewhat ambiguous affiliation — she asserts some connection with The New School in NY and Singularity University, although neither connection seems particularly strong), the author of the O'Reilly book →
     Blockchain Futures Lab at the Institute for the Future, an "independent, non-profit research organization with a more than 45-year track record of helping all kinds of organizations make the futures they want," based in Palo Alto, CA, USA.
     MIT Digital Currencty Initiative at the MIT Media Lab
     Centre for Cryptocurrency Research and Engineering at the Imperial College London
     bitcoinref, collection of links, references, etc., operating mainly by a micropayment stream as an Amazon Associate.
Coinsilium, a "Bitcoin startup incubator"
Ethereum, "a decentralized platform that runs smart contracts: applications that run exactly as programmed without any possibility of downtime, censorship, fraud or third party interference."
Centre for Blockchain Technologies at University College London
Bitcoin Institute, "a non-profit association of individual and corporate members devoted to independent research focused on the study of the integration of cryptocurrencies in the society and their impact on the economy."