Bitcoin and Cryptocurrency Technologies Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Goldfeder with a preface by Jeremy Clark Draft — Feb 9, 2016 Feedback welcome! Email [email protected] For the latest draft and supplementary materials including programming assignments, see our Coursera course. The official version of this book will be published by Princeton University Press in 2016. If you’d like to be notified when it’s available, please sign up here.
Introduction to the book There’s a lot of excitement about Bitcoin and cryptocurrencies. Optimists claim that Bitcoin will fundamentally alter payments, economics, and even politics around the world. Pessimists claim Bitcoin is inherently broken and will suffer an inevitable and spectacular collapse. Underlying these differing views is significant confusion about what Bitcoin is and how it works. We wrote this book to help cut through the hype and get to the core of what makes Bitcoin unique. To really understand what is special about Bitcoin, we need to understand how it works at a technical level. Bitcoin truly is a new technology and we can only get so far by explaining it through simple analogies to past technologies. We’ll assume that you have a basic understanding of computer science — how computers work, data structures and algorithms, and some programming experience. If you’re an undergraduate or graduate student of computer science, a software developer, an entrepreneur, or a technology hobbyist, this textbook is for you. In this book we’ll address the important questions about Bitcoin. How does Bitcoin work? What makes it different? How secure are your bitcoins? How anonymous are Bitcoin users? What applications can we build using Bitcoin as a platform? Can cryptocurrencies be regulated? If we were designing a new cryptocurrency today, what would we change? What might the future hold? Each chapter has a series of homework questions to help you understand these questions at a deeper level. In addition, there is a series of programming assignments in which you’ll implement various components of Bitcoin in simplified models. If you’re an auditory learner, most of the material of this book is also available as a series of video lectures. You can find all these on our Coursera course. You should also supplement your learning with information you can find online including the Bitcoin wiki, forums, and research papers, and by interacting with your peers and the Bitcoin community. After reading this book, you’ll know everything you need to be able to separate fact from fiction when reading claims about Bitcoin and other cryptocurrencies. You’ll have the conceptual foundations you need to engineer secure software that interacts with the Bitcoin network. And you’ll be able to integrate ideas from Bitcoin into your own projects. A note of thanks We’re immensely grateful to the students who helped develop programming assignments and to everyone who provided feedback on the drafts of this book. Princeton students Shivam Agarwal, Miles Carlsten, Paul Ellenbogen, Pranav Gokhale, Alex Iriza, Harry Kalodner, and Dillon Reisman, and Stanford students Allison Berke, Benedikt Bünz, and Alex Leishman deserve special praise. We’re also thankful to Dan Boneh and Albert Szmigielski. 2
Preface — The Long Road to Bitcoin The path to Bitcoin is littered with the corpses of failed attempts. I’ve compiled a list of about a hundred cryptographic payment systems, both e-cash and credit card based technologies, that are notable in some way. Some are academic proposals that have been well cited while others are actual systems that were deployed and tested. Of all the names on this list, there’s probably only one that you recognize — PayPal. And PayPal survived only because it quickly pivoted away from its original idea of cryptographic payments on hand-held devices! There’s a lot to learn from this history. Where do the ideas in Bitcoin come from? Why do some technologies survive while many others die? What does it take for complex technical innovations to be successfully commercialized? If nothing else, this story will give you an appreciation of how remarkable it is that we finally have a real, working payment mechanism that’s native to the Internet. Table 1: Notable electronic payment systems and proposals 3
Traditional financial arrangements Back in time before there were governments, before there was currency, one system that worked for acquiring goods was barter. Let’s say Alice wants a tool and Bob wants medicine. If each of them happen to have what the other person needs, then they can swap and both satisfy their needs. On the other hand, let’s say Alice has food that she’s willing to trade for a tool, while Bob, who has a tool, doesn’t have any need for food. He wants medicine instead. Alice and Bob can’t trade with each other, but if there’s a third person, Carol, who has medicine that she’s willing to trade for food, then it becomes possible to arrange a three-way swap where everyone gets what they need. The drawback, of course, is coordination — arranging a group of people, whose needs and wants align, in the same place at the same time. Two systems emerged to solve coordination: credit and cash. Historians, anthropologists, and economists debate which of the two developed first, but that’s immaterial for our purposes. In a credit-based system, in the example above, Alice and Bob would be able to trade with each other. Bob would give Alice the tool and Bob gets a favor that’s owed to him. In other words, Alice has a debt that she needs to settle with Bob some time in the future. Alice’s material needs are now satisfied, but she has a debt that she’d like to cancel, so that’s her new “want”. If Alice encounters Carol in the future, Alice can trade her food for Carol’s medicine, then go back to Bob with the medicine and cancel the debt. On the other hand, in a cash-based system, Alice would buy the tool from Bob. Later, she might sell her food to Carol, and Carol can sell her medicine to Bob, completing the cycle. These trades can happen in any order, provided that the buyer in each transaction has cash on hand. In the end, of course, it’s as if no money ever changed hands. Neither system is clearly superior. A cash-based system needs to be “bootstrapped” with some initial allocation of cash, without which no trades can occur. A credit-based system doesn’t need bootstrapping, but the drawback is that anyone who’s owed a debt is taking on some risk. There’s a chance that the other person never comes back to settle the debt. Cash also allows us to be precise about how much something is worth. If you’re bartering, it’s hard to say if a tool is worth more than medicine or medicine is worth more than food. Cash lets us use numbers to talk about value. That’s why we use a blended system today — even when we’re using credit, we measure debt in the amount of cash it would take to settle it. These ideas come up in many contexts, especially online systems where users trade virtual goods of some kind. For example, peer-to-peer file-sharing networks must deal with the problem of “freeloaders,” that is, users who download files without sharing in turn. While swapping files might 4
work, there is also the issue of coordination: finding the perfect person who has exactly the file you want and wants exactly the file you have. In projects like MojoNation and academic proposals like Karma, users get some initial allocation of virtual cash that they must spend to receive a file and earn when they send a copy of a file to another user. In both cases, one or more central servers help keep track of users’ balances and may offer exchange services between their internal currency and traditional currency. While MojoNation did not survive long enough to implement such an exchange, it became the intellectual ancestor of some protocols used today: BitTorrent and Tahoe-LAFS. The trouble with credit cards online Credit and cash are fundamental ideas, to the point that we can sort the multitude of electronic payment methods into two piles. Bitcoin is obviously in the “cash” pile, but let’s look at the other one first. Credit card transactions are the dominant payment method that is used on the web today. If you’ve ever bought something from an online seller such as Amazon, you know how the arrangement goes. You type in your credit card details, you send it to Amazon, and then Amazon turns around with these credit card details and they talk to the “system”—a financial system involving processors, banks, credit card companies, and other intermediaries. On the other hand, if you use something like PayPal, what you see is an intermediary architecture. There’s a company that sits between you and the seller, so you send your credit card details to this intermediary, which approves the transaction and notifies the seller. The intermediary will settle its balance with the seller at the end of each day. What you gain from this architecture is that you don’t have to give the seller your credit card details, which can be a security risk. You might not even have to give the seller your identity, which would improve your privacy as well. The downside is that you lose the simplicity of interacting directly with the seller. Both you and the seller might have to have an account with the same intermediary. Today most of us are comfortable with giving out our credit card information when shopping online, or at least we’ve grudgingly accepted it. We’re also used to companies collecting data about our online shopping and browsing activity. But in the 1990s, the web was new, standards for protocol-level encryption were just emerging, and these concerns made consumers deeply uncertain and hesitant. In particular, it was considered crazy to hand over your credit card details to online vendors of unknown repute over an insecure channel. In such an environment, there was a lot of interest in the intermediary architecture. A company called FirstVirtual was an early payment intermediary, founded in 1994. Incidentally, they were one of the first companies to set up a purely virtual office with employees spread across the country and communicating over the Internet — hence the name. 5
FirstVirtual’s proposed system was a little like PayPal’s current system but preceded it by many years. As a user you’d enroll with them and provide your credit card details. When you want to buy something from a seller, the seller contacts FirstVirtual with the details of the requested payment, FirstVirtual confirms these details with you, and if you approve your credit card gets billed. But two details are interesting. First, all of this communication happened over email; web browsers back in the day were just beginning to universally support encryption protocols like HTTPS, and the multi-party nature of payment protocol added other complexities. (Other intermediaries took the approach of encoding information into URLs or using a custom encryption protocol on top of HTTP.) Second, the customer would have ninety days to dispute the charge, and the merchant would receive the money only after three months! Today the merchant does get paid immediately, but, there still is the risk that the customer will file a chargeback or dispute the credit card statement. If that happens, the merchant will have to return the payment to the credit card company. In the mid ‘90s there was a competing approach to the intermediary architecture which we’ll call the SET architecture. SET also avoids the need for customers to send credit card information to merchants, but it additionally avoids the user having to enroll with the intermediary. In SET, when you are ready to make a purchase, your browser passes your view of the transaction details to a shopping application on your computer which, together with your credit card details, encrypts it in such a way that only the intermediary can decrypt it, and no one else can (including the seller). Having encrypted your data it this way, you can send it to the seller knowing that it’s secure. The seller blindly forwards the encrypted data to the intermediary — along with their own view of the transaction details. The intermediary decrypts your data and approves the transaction only if your view matches the seller’s view. SET was a standard developed by VISA and MasterCard, together with many technology heavyweights of the day: Netscape, IBM, Microsoft, Verisign, and RSA. It was an umbrella specification that unified several existing proposals. One company that implemented SET was called CyberCash. It was an interesting company in many ways. In addition to credit card payment processing, they had a digital cash product called CyberCoin. This was a micropayment system — intended for small payments such as paying a few cents to read an online newspaper article. That meant that you’d probably never have more than $10 in your CyberCoin account at any time. Yet, amusingly, they were able to get U.S. government (FDIC) insurance for each account for up to $100,000. There’s more. Back when CyberCash operated, there was a misguided — and now abandoned — U.S. government restriction on the export of cryptography, which was considered a weapon. That meant software that incorporated meaningful encryption couldn’t be offered for download to users in other countries. However, CyberCash was able to get a special exemption for their software from the Department of State. The government’s argument was that extracting the encryption technology out of CyberCash’s software would be harder than writing the crypto from scratch. 6
Finally, CyberCash has the dubious distinction of being one of the few companies affected by the Y2K bug — it caused their payment processing software to double-bill some customers. They later went bankrupt in 2001. Their intellectual property was acquired by Verisign who then turned around and sold it to PayPal where it lives today. Why didn’t SET work? The fundamental problem has to do with certificates. A certificate is a way to securely associate a cryptographic identity, that is, a public key, with a real-life identity. It’s what a website needs to obtain, from companies like Verisign that are called certification authorities, in order to show up as secure in your browser (typically indicated by a lock icon). Putting security before usability, CyberCash and SET decided that not only would processors and merchants in their system have to get certificates, all users would have to get one as well. Getting a certificate is about as pleasant as doing your taxes, so the system was a disaster. Over the decades, mainstream users have said a firm and collective ‘no’ to any system that requires end-user certificates, and such proposals have now been relegated to academic papers. Bitcoin deftly sidesteps this hairy problem by avoiding real-life identities altogether. In Bitcoin, public keys themselves are the identities by which users are known, as we’ll see in Chapter 1. In the mid 90s, when SET was being standardized, the World Wide Web Consortium was also looking at standardizing financial payments. They wanted to do it by extending the HTTP protocol instead so that users wouldn’t need extra software for transactions—they could just use their browser. In fact, they had a very general proposal for how you might extend the protocol, and one of the use cases that they had was doing payments. This never happened -- the whole extension framework was never deployed in any browsers. In 2015, almost two decades later, the W3C has announced that it wants to take another crack at it, and that Bitcoin will be part of that standardization this time around. Given all the past failures, however, I won’t be holding my breath. From Credit to (Crypto) Cash Now let’s turn to cash. We compared cash and credit earlier, and noted that a cash system needs to be “bootstrapped,” but the benefit is that it avoids the possibility of a buyer defaulting on her debt. Cash offers two additional advantages. The first is better anonymity. Since your credit card is issued in your name, the bank can track all your spending. But when you pay in cash, the bank doesn’t come into the picture, and the other party doesn’t need to know who you are. Second, cash can enable offline transactions where there’s no need to phone home to a third party in order to get the transaction approved. Maybe later, they go to a third party like a bank to deposit the cash, but that’s much less of a hassle. Bitcoin doesn’t quite offer these two properties, but comes close enough to be useful. Bitcoin is not anonymous to the same level as cash is. You don’t need to use your real identity to pay in Bitcoin, but it’s possible that your transactions can be tied together based on the public ledger of transactions 7
with clever algorithms, and then further linked to your identity if you’re not careful. We’ll get into the messy but fascinating details behind Bitcoin anonymity in Chapter 6. Bitcoin doesn’t work in a fully offline way either. The good news is it doesn’t require a central server, instead relying on a peer-to-peer network which is resilient in the way that the Internet itself is. In Chapter 3 we’ll look at tricks like “green addresses” and micropayments which allow us to do offline payments in certain situations or under certain assumptions. The earliest ideas of applying cryptography to cash came from David Chaum in 1983. Let’s understand this through a physical analogy. Let’s say I start giving out pieces of paper that say: “The bearer of this note may redeem it for one dollar by presenting it to me” with my signature attached. If people trust that I’ll keep my promise and consider my signature unforgeable, they can pass around these pieces of paper just like banknotes. In fact, banknotes themselves got their start as promissory notes issued by commercial banks. It’s only in fairly recent history that governments stepped in to centralize the money supply and legally require banks to redeem notes. I can do the same thing electronically with digital signatures, but that runs into the annoying “double spending” problem — if you receive a piece of data representing a unit of virtual cash, you can make two (or more) copies of it and pass it on to different people. To stick with our analogy, let’s stretch it a little bit and assume that people can make perfect copies and we have no way to tell copies from the original. Can we solve double spending in this world? Here’s a possible solution: I put unique serial numbers into each note I give out. When you receive such a note from someone, you check my signature, but you also call me on the phone to ask if a note with that serial number has already been spent. Hopefully I’ll say no, in which case you accept the note. I’ll record the serial number as spent in my ledger, and if you try to spend that note, it won’t work because the recipient will call me and I’ll tell them the note has already been spent. What you’ll need to do instead is to periodically bring me all the notes you’ve received, and I’ll issue you the same number of newnotes with fresh serial numbers. This works. It’s cumbersome in real life, but straightforward digitally provided I’ve set up a server to do the signing and record-keeping of serial numbers. The only problem is that this isn’t really cash any more, because it’s not anonymous — when I issue a note to you I can record the serial number along with your identity, and I can do the same when someone else later redeems it. That means I can keep track of all the places where you’re spending your money. This is where Chaum’s innovation comes in. He figured out to both keep the system anonymous and prevent double-spending by inventing the digital equivalent of the following procedure: when I issue a new note to you, youpick the serial number. You write it down on the piece of paper, but cover it so that I can’t see it. Then I’ll sign it, still unable to see the serial number. This is called a “blind signature” in cryptography. It’ll be in your interest to pick a long, random serial number to ensure that it will most likely be unique. I don’t have to worry that you’ll pick a serial number that’s already been picked — you can only shoot yourself in the foot by doing so and end up with a note that can’t be spent. 8
This was the first serious digital cash proposal. It works, but it still requires a server run by a central authority, such as a bank, and for everyone to trust that entity. Moreover, every transaction needs the participation of this server to go through. If the server goes down temporarily, payments grind to a halt. A few years later, in 1988, Chaum in collaboration with two other cryptographers Fiat and Naor proposed offlineelectronic cash. At first sight this might seem to be impossible: if you try to spend the same digital note or coin at two different shops, how can they possibly stop this unless they’re both connected to the same payment network or central entity? The clever idea is to stop worrying about preventing double-spending and focus on detecting it, after the fact, when the merchant re-connects to the bank server. After all, this is why you’re able to use your credit card on an airplane even if there is no network connection up in the skies. The transaction processing happens later when the airline is able to re-connect to the network. If your card is denied, you’ll owe the airline (or your bank) money. If you think about it, quite a bit of traditional finance is based on the idea of detecting an error or loss, followed by attempting to recover the money or punish the perpetrator. If you write someone a personal check, they have no guarantee that the money is actually in your account, but they can come after you if the check bounces. Conceivably, if an offline electronic cash system were widely adopted, the legal system would come to recognize double spending as a crime. Chaum, Fiat, and Naor’s idea for detecting double spending was an intricate cryptographic dance. At a high level, what it achieved was this: every digital coin issued to you encodes your identity, but in such a way that no one except you, not even the bank, can decode it. Every time you spend your coin, the recipient will require you to decode a random subset of the encoding, and they’ll keep a record of this. This decoding isn’t enough to allow them to determine your identity. But if you ever double spend a coin, eventually both recipients will go to the bank to redeem their notes, and when they do this, the bank can put the two pieces of information together to decode your identity completely, with an overwhelmingly high probability. You might wonder if someone can frame you as a double spender in this system. Say you spend a coin with me, and then I turned around and tried to double-spend it (without redeeming it with the bank and getting a new coin with my identity encoded). This won’t work — the new recipient will ask me to decode a random subset, and this will almost certainly not be the same as the subset you decoded for me, so I won’t be able to comply with their decoding request. Over the years, many cryptographers have looked at this construction and improved it in various ways. In the Chaum-Fiat-Naor scheme, if a coin is worth $100, and you wanted to buy something that cost only $75, say, there’s no way to split that coin into $75 and a $25. All you could do is go back to the bank, cash in the $100 coin, and ask for a $75 coin and a $25 coin. But a paper by Okamoto and Ohta uses “Merkle trees” to create a system that does allow you to subdivide your coins. Merkle trees would show up in Bitcoin as well, and we’ll meet them in Chapter 1. The Chaum-Fiat-Naor scheme also leaves a lot of room for improvements in efficiency. In particular, the application of something called zero-knowledge proofs to this scheme (most notably by Brands; and Camenisch, Hohenberger, 9
and Lysyanskaya) was very fruitful—zero-knowledge proofs have also been applied to Bitcoin as we will see in Chapter 6. But back to Chaum: he took his ideas and commercialized them. He formed a company in 1989 called DigiCash, probably the earliest company that tried to solve the problem of online payments. They had about a five-year head start on other companies like FirstVirtual and CyberCash that we just discussed. The actual cash in Digicash’s system was called Ecash and they had another system called cyberbucks. There were banks that actually implemented it — a few in the US and at least one in Finland. This was in the 1990s, long before Bitcoin, which might come as surprise to some Bitcoin enthusiasts who view banks as tech-phobic, anti-innovative behemoths. Ecash is based on Chaum’s protocols. Clients are anonymous, so banks can’t trace how they’re spending their money. But merchants in ecash aren’t anonymous. They have to return coins as soon as they receive them, so the bank knows how much they’re making, at what times, and so on. Figure 2: Screenshot of DigiCash Figure 2 shows a screenshot from the software. As you can see, it shows you your balance as well as all the coins that you have that have been issued to you from the bank. Since there’s no way to split your coins, the bank issues you a whole set of coins in denominations of a cent, two cents, four cents, 10
and so on — powers of two. That way, you (or your software, on your behalf) can always select a set of coins to pay for the exact amount of a transaction. When you want to make a transaction, say, as in this example, you want to make a donation to the non-profit privacy group EPIC, you’d click on a donation link that takes you to the Digicash website. That would then open a reverse web connection back to your computer. That means your computer had to have the ability to accept incoming connections and act as a server. You’d have to have your own IP address and your ISP would have to allow incoming connections. If the connection was successful, then the ecash software would launch on your computer and you’d be able to approve the transaction and send the money. Chaum had several patents on Digicash technology, in particular, the blind-signature scheme that it used. This was controversial, and it stopped other people from developing ecash systems that used the same protocol. But a bunch of cryptographers who hung out on what was called the cypherpunks mailing list wanted an alternative. Cyperpunks was the predecessor to the mailing list where Satoshi Nakamoto would later announce Bitcoin to the world, and this is no coincidence. We’ll talk about the cypherpunk movement and the roots of Bitcoin in Chapter 7. The cypherpunk cryptographers implemented a version of of ecash called MagicMoney. It did violate the patents, but was billed as being only for experimental use. It was a fun piece of software to play with. The interface was all text-based. You could send transactions by email. You would just copy and paste the transactions into your email and send it to another user. Hopefully, you’d use end-to-end email encryption software such as PGP to protect the transaction in transit. Then there’s a proposal called Lucre by Ben Laurie with contributions from many other people. Lucre tries to replace the blind-signature scheme in ecash with a non-patent-encumbered alternative, with the rest of the system largely the same. Yet another proposal, by Ian Goldberg, tries to fix the problem of not being able to split your coins to make change. His idea was that the merchant could send you coins back if they had some coins, so that you might overpay for the item if you didn’t have exact change, and then you’d get some coins back. But notice that this introduces an anonymity problem. As we saw earlier, in ecash, senders are anonymous but merchants aren’t. When the merchant sends cash back, technically, they’re the sender, so they’re anonymous. But you, as someone who has to return this cash to the bank, aren’t anonymous. There’s no way to design this system without breaking the anonymity of users trying to buy goods. So Goldberg came up with a proposal where there were different types of coins that would allow these transactions to occur, allow you to get change back, and still preserve your anonymity. Now, why did DigiCash fail? The main problem with DigiCash was that it was hard to persuade the banks and the merchants to adopt it. Since there weren’t many merchants that accepted ecash, users didn’t want it either. Worse, it didn’t support user-to-user transactions, or at least not very well. It was really centered on the user-to-merchant transaction. So if merchants weren’t on board, there was 11
no other way to bootstrap interest in the system. So at the end of the day, DigiCash lost and the credit card companies won. As a side note, Bitcoin allows user-to-merchant and user-to-user transactions. In fact, the protocol doesn’t have a notion of merchant that’s separate from the notion of user. The support for user-to-user transactions probably contributed to Bitcoin’s success. There was something to do with your bitcoins right from the beginning: send it to other users, while the community tried to drum up support for Bitcoin and get merchants to accept it. In the later years of the company, DigiCash also experimented with tamper-resistant hardware to try to preventdouble-spending rather than just detecting it. In this system, you’d get a small hardware device that was usually called a wallet, or some sort of card. The device would keep track of your balance, which would decrease when you spent money and increase if you loaded the card with more money. The point of the device is that there should be no way to physically or digitally go in and tamper with its counter. So if the counter hits zero, then the card stops being able to spend money until it’s re-loaded. There were many other companies that had electronic cash systems based on tamper-resistant hardware. DigiCash later worked with a company called CAFE which was based in Europe. Another company formed around this idea was called Mondex and it was later acquired by Mastercard. Visa also had their own variant called VisaCash. Figure 3: Mondex system, showing user card and wallet. 12
Figure 3 shows the user side of the Mondex system. There’s a smart card and there’s a wallet unit, and you can load either of them with cash. And if you wanted to do user-to-user swap of money, the giver user would first put their card into the wallet and move money off of the card onto the wallet. Then the receiver would stick their card in the wallet then you’d move the money onto the second card. This was a way to exchange digital cash, and it was anonymous. Mondex trialled their technology in a bunch of communities. One community happened to be a city very close to where I grew up: Guelph, Ontario. You’ve probably already guessed that it didn’t really catch on. A major problem with Mondex cards is that they’re like cash — if you lose them or they get stolen, the money’s gone. Worse, if there’s some sort of malfunction with the card, if the card reader wouldn’t read it, there’s no way to figure out if that card had balance on it or not. In these scenarios, Mondex would typically eat the cost. They’d assume that the card was loaded and reimburse the user for that lost money. Of course, that can cost a company a lot of money. Further, the wallet was slow and clunky. It was much faster to pay with a credit card or with cash. And retailers hated having several payment terminals; they wanted just one for credit cards. All these factors together did Mondex in. However, these cards were smart cards, which means that they have small microcontrollers on them, and that technology has proved successful. In many countries today, including Canada, where I live, every single credit card and every single debit card now has smart card technology in it. It’s used for a different purpose, though. It’s not used to prevent double-spending — the problem doesn’t arise since it’s not a cash-based technology. The bank, rather than your card, keeps track of your balance or available credit. Instead the chip is used for authentication, that is, to prove that you know the PIN that’s associated with your account. But Mondex was using it long before this technology was adopted widely by the banking industry. Minting Money out of Thin Air In the DigiCash system, if you have a digital cash object that’s worth $100, what makes it actually worth $100? The answer is simple: in order to obtain ecash worth $100, you’d have to take $100 out of your bank account and give it to the bank that was issuing you the ecash. But there were a bunch of different proposals for how to do this and different companies did it differently. One far-fetched possibility: what if the government of a particular country actually authorized services to mint digital money, creating new cash out of thin air? That was the idea behind NetCash, although it never got beyond the proposal stage. A different system, used by e-Gold, was to put a pile of gold in a vault and to issue digital cash only up to the value of the gold. Another company called Digigold wasn’t fully backed by gold, but had partial reserves. All of these ideas ultimately peg the value of digital cash to the dollar or a commodity. If the dollar’s value goes up or down, the value of your digital money holdings will change along with it. A radically 13
different possibility is to allow digital money to be it own currency, issued and valued independently of any other currency. To create a free-floating digital currency that is likely to acquire real value, you need to have something that’s scarce by design. In fact, scarcity is also the reason why gold or diamonds have been used as a backing for money. In the digital realm, one way to achieve scarcity is to design the system so that minting money requires solving a computational problem (or “puzzle”) that takes a while to crack. This is what happens in Bitcoin “mining”, which we’ll look at in Chapter 5. The basic idea — that solutions to computational puzzles could be digital objects that have some value — is pretty old. It was first proposed by cryptographers Dwork and Naor as a potential solution to email spam back in 1992. What if, every time you sent an email, your computer would have to solve one of these puzzles that would take a few seconds to solve? To enforce this requirement, the recipient’s email program would simply ignore your email you didn’t attach the solution to the computational puzzle. For the average user, it wouldn’t be that much of a barrier to sending emails because you’re not sending emails very frequently. But if you’re a spammer, you’re trying to send out thousands or millions of emails all at once, and solving those computational puzzles could become prohibitive. A similar idea was later discovered independently by Adam Back in 1997 in a proposal called Hashcash. These computational puzzles need to have some specific properties to be a useful spam deterrent. First, it should be impossible for a spammer to solve one puzzle and attach the solution to every email he sends. To ensure this, the puzzle should be specific to the email: it should depend on the sender and receiver, the contents of the email, and the approximate time at which it’s sent. Second, the receiver should be able to easily check the puzzle solution without having to repeat the process of solving the puzzle. Third, each puzzle should be totally independent of the others, in the sense that solving one puzzle does not decrease the amount of time it takes to solve any other puzzle. Finally, since hardware improves with time and solving any given computational puzzle gets faster and cheaper, recipients should be able to adjust the difficulty of the puzzle solutions that they will accept. These properties can be achieved by using cryptographic hash functions to design the puzzles, and we’ll study this in Chapter 1. Bitcoin uses essentially the same computational puzzle as Hashcash, but with some minor improvements. Bitcoin does a lot more than Hashcash does, though — after all, it takes a whole book to explain Bitcoin! I only mention this because Hashcash inventor Adam Back has said, “Bitcoin is Hashcash extended with inflation control.” I think that’s overreaching a bit. It’s sort of like saying, “a Tesla is just a battery on wheels.” As with any good idea in cryptography, there are many variants of computational puzzles that aim to achieve slightly different properties. One proposal comes from Rivest and Shamir, the R and the S in the RSA cryptosystem. Observe that in Hashcash, your cost to solve a number of puzzles is simply the sum of the individual costs, by design. But this is different from the cost structure for a government to mint money. If you think about how anti-counterfeiting technology in a paper currency, there’s a huge 14
initial cost to acquire all the equipment, create the security features, and so on. But once they’ve done all that, their costs go down, and it doesn’t matter much if they print one bill or a hundred bills. In other words, minting paper money has a huge fixed cost but low marginal cost. Rivest and Shamir wanted to design computational puzzles that would mimic these properties, so that minting the first coin is massively computationally challenging, but minting subsequent coins is a lot cheaper. Their proposal also utilized hash functions, but in a different way. We won’t get into the details of their solution, but the problem they were trying to solve is interesting at a high level. Why did Hashcash never catch on for its intended purpose of preventing spam? Perhaps spam just wasn’t a big enough problem to solve. For most people spam as a nuisance, but not something that they want to spend their computing cycles on combatting. We have spam filters today that work pretty well at keeping spam out of our inboxes. It’s also possible Hashcash wouldn’t have actually stopped spammers. In particular, most spammers today send their spam using ‘botnets’, large groups of of other people’s computers that they take control of using malware. They might just as well use those computers to harvest Hashcash. That said, the idea of using computational puzzles to limit access to resources is still an idea that’s kicking around. You can see it in some proposals for replacing network protocols, such as MinimaLT. Recording Everything in a Ledger Another key component of Bitcoin is the block chain: a ledger in which all Bitcoin transactions are securely recorded. The ideas behind the block chain are again quite old, and trace back to a paper by Haber and Stornetta in 1991. Their proposal was a method for secure timestamping of digital documents, rather than an digital money scheme. The goal of timestamping is to give an approximate idea of when a document came into existence. More importantly, timestamping accurately conveys the order of creation of these documents: if one came into existence before the other, the timestamps will reflect that. The security property requires that a document’s timestamp can’t be changed after the fact. In Haber and Stornetta’s scheme, there’s a timestamping service to which clients send documents to timestamp. When the server receives a document, it signs the document together with the current time and as well as a link or a pointer to the previous document, and issues a “certificate” with this information. The pointer in question a special type pointer which links to a piece of data instead of a location. That means that if the data in question changes, the pointer automatically become invalid. In Chapter 1 we’ll study how we can create such pointers using hash functions. What this achieves is that each document’s certificate ensures the integrity of the contents of the previous document. In fact, you can apply this argument recursively: each certificate essentially fixes the entire history of documents and certificates up until that point. If we assume that each client in the system keeps track of at least a few certificates — their own documents’ certificates, and those of 15
the previous and following documents — then collectively the participants can ensure that the history cannot be changed after the fact. In particular, the relative ordering of documents is preserved. Figure 4: linked timestamping.To create a certificate for a document, the timestamp server includes a hash pointer to the previous document’s certificate, the current time, and signs these three data elements together. A later paper proposed an efficiency improvement: instead of linking documents individually, we can collect them into blocks and link blocks together in a chain. Within each block, the documents would again be linked together, but in a tree structure instead of linearly. This decreases the amount of checking needed to verify that a particular document appears at a particular point in the history of the system. Visually, this hybrid scheme looks like Figure 5. Figure 5: efficient linked timestamping.Arrows represent hash pointers and dotted vertical lines indicate time intervals. This data structure forms the skeleton of Bitcoin’s block chain, as we’ll see in Chapter 3. Bitcoin refines it a subtle but important way: a Hashcash-esque protocol is used to delay how fast new blocks are added to the chain. This modification has profound and favorable consequences for Bitcoin’s security model. There is no longer the need for trusted servers; instead, events are recorded by a collection of untrusted nodes called “miners”. Every miner keeps track of blocks, rather than having to rely on regular users to do it. Anyone can become a miner by solving computational puzzles to create blocks. Bitcoin also gets rid of signatures, relying only on hash pointers to ensure the integrity of the data structure. Finally, the actual timestamps aren’t of much importance in Bitcoin, and the point of 16
the system is to record the relative ordering of transactions in a tamper-resistant way. In fact, Bitcoin blocks aren’t created in a fixed schedule. The system ensures that a new one is created every 10 minutes on average, but there’s considerable variation in the time between successive blocks. In essence, Bitcoin combines the idea of using computational puzzles to regulate the creation of new currency units with the idea of secure timestamping to record a ledger of transactions and prevent double spending. There were earlier, less sophisticated proposals that combined these two ideas. The first is called b-money, and it was by Wei Dai in 1998. In b-money, anyone can create money using a hashcash-like system. There’s a peer-to-peer network, sort of like in Bitcoin. Each node maintains a ledger, but it’s not a global ledger like in the Bitcoin block chain. Each node has its own ledger of what it thinks everyone’s balance is. Another similar proposal, by Nick Szabo, is called Bitgold. Szabo says he had the idea for Bitgold as early as 1998, but didn’t get around to blogging about it until 2005. The reason I mention this is that there’s a minor conspiracy theory popularized by Nathaniel Popper, a New York Times reporter who wrote a very good book on the history of Bitcoin. Popper notes that the blog post timestamps were changed after Satoshi posted the Bitcoin whitepaper so that the Bitgold proposal looks like it was written up about two months after Bitcoin was released. Popper believes, like many other observers, that Szabo could be Satoshi, and he cites the timestamp change as evidence of Szabo/Satoshi trying to cover up the fact that he invented Bitgold before he knew about Bitcoin. The problem with this explanation is that if you actually read the contents of the blog posts, Szabo is very clear about having had this idea in 1998, and he doesn’t try to change those dates. So a more reasonable explanation is that he just bumped the post to the top of his blog after Bitcoin popularized similar ideas, to make sure that people were aware of his prior proposal. Bitcoin has several important differences from b-money and Bitgold. In those proposals, computational puzzles are used directly to mint currency. Anyone can solve a puzzle and the solution is a unit of money itself. In Bitcoin, puzzle solutions themselves don’t constitute money. They are used to secure the block chain, and only indirectly lead to minting money for a limited time. Second, b-money and Bitgold rely on timestamping services that sign off on the creation or transfer of money. Bitcoin, as we’ve seen, doesn’t require trusted timestamping, and merely tries to preserve the relative order of blocks and transactions. Finally, in b-money and Bitgold, if there is disagreement about the ledger among the servers or nodes, there isn’t a clear way to resolve it. Letting the majority decide seems to be implicit in both authors’ writings. But since anyone can set up a node — or a hundred, hiding behind different identities — these mechanisms aren’t very secure, unless there is a centralized gatekeeper who controls entry into the network. In Bitcoin, by contrast, for an attacker to change history, they must solve computational puzzles at a faster rate than the rest of the participants combined. This is not only more secure, it allows us to quantify the security of the system. 17
B-money and Bitgold were informal proposals — b-money was a post on a mailing list and Bitgold was a series of blog posts. Neither took off, or was even implemented directly. Unlike the Bitcoin white paper, there wasn’t a full specification or any code. The proposals gloss over issues that may or may not be solvable. The first, as we’ve already mentioned, is how to resolve disagreements about the ledger. Another problem is determining how hard the computational puzzle should be in order to mint a unit of currency. Since hardware tends to get dramatically cheaper over time for a fixed amount of computing power, Bitcoin incorporates a mechanism to automatically adjust the difficulty of the puzzles periodically. B-money and Bitgold don’t include such a mechanism, which can result in problems since coins may lose their value if it become trivially easy to create new ones. Hints about Satoshi You may know that Satoshi Nakamoto is the pseudonym adopted by the creator of Bitcoin. While his identity remains a mystery, he communicated extensively in Bitcoin’s early days. Let’s use this to dig a little bit into questions like when he started working on Bitcoin, to what extent he was influenced by the prior ideas we’ve looked at, and what motivated him. Satoshi says he started coding Bitcoin around May 2007. I’ll take him at his word; the fact that he’s anonymous is not a reason to think he’d lie about things like that. He registered the domain bitcoin.org in August 2008. And at that time, he started sending private emails to a few people who he thought might be interested in the proposal. Then a little later in October 2008, he publicly released a white paper that described the protocol, and then soon after, he released the initial code for Bitcoin as well. Then he stuck around for about two years, during which he posted lots of messages on forums, emailed with lots of people, and responded to people’s concerns. On the programming side, he submitted patches to the code. He maintained the source code in conjunction with other developers, fixing issues as they arose. By December 2010, others had slowly taken over the maintenance of the project, and he stopped communicating with them. I’ve been referring to Satoshi Nakamoto as a “he,” but I have no particular reason to believe Satoshi is a man and not a woman. I’m just using the male pronoun since Satoshi is a male name. I’ve also been referring to him as a single individual. There is a theory that Satoshi Nakamoto might be a collection of individuals. I don’t buy this theory — I think Satoshi is probably just one person. The reason is that if we look at the entirety of the online interactions undertaken under the Satoshi pseudonym, if we think about the two years that Satoshi spent replying to emails and patching code, it’s hard to imagine that this could be multiple people sharing user accounts and passwords, responding in a similar style and a similar voice, and making sure they didn’t contradict each other. It just seems a much simpler explanation that at least this portion of Satoshi’s activity was done by a single individual. Furthermore, it’s clear from his writings and patches that this individual understood the full code base of Bitcoin and all its design aspects. So it’s very reasonable to assume that the same individual wrote the original code base and the white paper as well. Finally, it’s possible that Satoshi had help with the 18
original design. However, after Bitcoin’s release, we can see for ourselves that Satoshi was quick to attribute any help he received from other contributors. It would be out of character for him to mislead us about inventing something by himself if he had had help from other people. Next, we might ask ourselves, “What did Satoshi know about the history of ecash?” To understand this better, we can start by looking at what he cites in his white paper as well as the references that existed on early versions of the Bitcoin website. In the white paper he cites some papers on basic cryptography and probability theory. He also cites the time-stamping work that we saw earlier, and it’s very natural to think that he based the design of the block chain on these references since the similarities are so apparent. He also cites the Hashcash proposal whose computational puzzle is very similar to the one that’s used in Bitcoin. He also has a reference to b-money. Later, on the website, he added references to Bitgold and as well to a scheme by Hal Finney for reusing computational puzzle solutions. But, if we look at the email exchanges that were made public by people who corresponded with Satoshi Nakamoto in the early days, we find that the b-money proposal was actually added after-the-fact, at the suggestion of Adam Back. Satoshi then emailed Wei Dai who created b-money and apparently, Dai was the one that told him about Bitgold. So these proposals weren’t probably inspirations for the original design. He later corresponded a lot with Hal Finney, and that’s quite a reasonable explanation for why he cites Finney’s work, at least on the website. Based on this, it seems plausible that when creating Bitcoin, Hashcash and time-stamping were the only things from the history of ecash that Satoshi knew about or thought were relevant. After he came to know of b-money and Bitgold, however, he seems to have appreciated their relevance. In mid-2010, the Wikipedia article on Bitcoin was flagged for deletion Wikipedia’s editors because they thought it wasn’t noteworthy. So there was some discussion between Satoshi and others about how to word the article so that Wikipedia would accept it. To that end, Satoshi suggested this description of Bitcoin: “Bitcoin is an implementation of Wei Dai’s b-money proposal on Cypherpunks in 1998 and Nick Szabo’s Bitgold proposal.” So Satoshi, by this point, did see positioning Bitcoin as an extension of these two ideas or an implementation of these two prior systems as a good explanation of how it worked. But, what about everything else — the Chaumian ecash schemes and the credit card proposals that we looked at? Did Satoshi know any of that history when designing Bitcoin? It’s hard to tell. He didn’t give any indication of knowing that history, but it’s just as likely that he didn’t reference this because it wasn’t relevant to Bitcoin. Bitcoin uses a completely different decentralized model and so there’s no compelling reason to dwell on old centralized systems that failed. Satoshi himself makes this point, by mentioning Chaumian ecash in passing, in one of his posts to the Bitcoin forums. Writing about another proposal called opencoin.org, he notes that they seem to be “talking about the old Chaumian central mint stuff, but maybe only because that was the only thing available. Maybe they would be interested in a new direction. A lot of people automatically dismiss e-currency as a lost cause because of all the companies that failed since the 1990’s. I hope it’s obvious 19
it was only the centrally controlled nature of those systems that doomed them. I think this is the first time we’re trying a decentralized, non-trust-based system.” That gives us a pretty good idea what Satoshi thought of the earlier proposals, and specifically how he felt Bitcoin was different. Bitcoin’s decentralization is indeed a defining feature that sets it apart from almost everything we’ve look at. Another interesting quote from Satoshi suggests that he might not be an academic. Most academic researchers think about ideas and write them down immediately, before they build the system. Satoshi says that he took an opposite approach: “I actually did Bitcoin kind of backwards. I had to write all the code before I could convince myself that I could solve every problem, then I wrote the paper. I think I will be able to release the code sooner than I could write a detailed specification.” Since there’s bit of myth around Satoshi, it’s worth mentioning that he made mistakes like everyone else and that wasn’t a perfect oracle of the future. There are bugs and questionable design choices in the original Bitcoin code as well as in its design. For example, there was a feature to send bitcoins to IP addresses that never caught on and, in retrospect, was a bad idea. When he described what Bitcoin was useful for, his scenarios were centered on the idea of using it across the internet. That use case is central to Bitcoin, of course, but it’s not the only one. He didn’t indicate a vision of going into a coffee shop and being able to pay for your coffee with Bitcoin, for example. A final question we may ask ourselves, colored by what we understand from the history of digital cash, is, “Why does Satoshi maintain his anonymity?” There are many possible reasons. To begin with, it might be just for fun. Many people write novels anonymously, and there are graffiti artists like Banksy who maintain their anonymity. In fact, in the community that Satoshi was involved in at that time, the Cypherpunk community and the cryptography mailing list, it was common practice for people to post anonymously. On the other hand, there could have been legal worries behind Satoshi’s choice. Two U.S. companies, Liberty Reserve and e-Gold, ran into legal trouble for money laundering. In 2006, one of the founders of Liberty Reserve fled the United States, fearing that he would be indicted on money laundering charges. E-Gold’s founders, on the other hand, stayed in the United States, and one was actually indicted and eventually pled guilty to the charges. This guilty plea was registered just right before Satoshi set up the Bitcoin website and started emailing people about his proposal. That said, numerous people have invented ecash systems, and nobody else was scared of the legal implications or has chosen to remain anonymous. So this may have been the reason, it may not have been the reason. It’s also worth recalling that certain aspects of ecash were patented, and that members of the Cypherpunk movement were concerned about implementing ecash systems due to these patents. In fact, one post to the cypherpunks mailing list proposed that a group of anonymous coders implement ecash so that if someone were to sue, they wouldn’t be able to find the coders. While it is difficult to think that Bitcoin would violate the ecash patents given how different its design is, perhaps Satoshi was being extra cautious. Or maybe he was just inspired by the idea of an anonymous coder from the cypherpunk community. 20
A final reason that’s often cited is personal security. We know that Satoshi has a lot of bitcoins from his mining early on, and due to Bitcoin’s success these are now worth a lot of money. I think this is a plausible reason. After all, choosing to be anonymous isn’t a decision you make once, it’s something that you do on a continual basis. That said, it probably wasn’t Satoshi’s original reason. The first time Satoshi used the name Satoshi Nakamoto, he hadn’t even released the whitepaper or the codebase for Bitcoin, and it’s hard to imagine that he had any idea that it would be as successful as it was. In fact, at many points in its early history, Satoshi was optimistic but cautious about Bitcoin’s prospects. He seems to have understood that many previous efforts had failed and that Bitcoin might fail as well. Concluding remarks The success of Bitcoin is quite remarkable if you consider all the ventures that failed trying to do what it does. Bitcoin has several notable innovations including the block chain and a decentralized model that supports user-to-user transactions. It provides a practically useful but less-than-perfect level of anonymity for users. In Chapter 6 we’ll take a detailed look at anonymity in Bitcoin. In one sense it’s weaker than the strong anonymity in DigiCash, but in another sense it’s stronger. That’s because in DigiCash, it was only the senders of the money that maintained their anonymity, and not the merchants. Bitcoin gives both senders and merchants (whether users or merchants) the same level of anonymity. Let me conclude with some lessons that we can learn from Bitcoin through the lens of the previous systems that we’ve looked at. The first is to not give up on a problem. Just because people failed for 20 years in developing digital cash doesn’t mean there isn’t a system out there that will work. The second is to be willing to compromise. If you want perfect anonymity or perfect decentralization you’ll probably need to worsen other areas of your design. Bitcoin, in retrospect, seems to have made the right compromises. It scales back anonymity a little bit and requires participants to be online and connected to the peer-to-peer network, but this turned out to be acceptable to users. A final lesson is success through numbers. Bitcoin was able to build up a community of passionate users as well as developers willing to contribute to the open-source technology. This is a markedly different approach than previous attempts at digital cash, which were typically developed by a company, with the only advocates for the technology being the employees of the company itself. Bitcoin’s current success is due in large part to the vibrant supporting community who pushed the technology, got people using it, and got merchants to adopt it. 21
Further Reading An accessible overview of digital cash schemes focused on practical issues: P. Wayner. Digital Cash: commerce on the net (2nd ed). Morgan Kaufmann, 1997. A cryptographically-oriented overview of e-cash systems (Chapter 1) and micropayments (Chapter 7): B. Rosenberg (ed.) Handbook of Financial Cryptography and Security. CRC Press, 2011. Although not Chaum’s earliest paper on e-cash, this is arguably the most innovative, and it formed a template replicated by many other papers: D. Chaum, A. Fiat, M. Naor. Untraceable electronic cash. CRYPTO 1998. Many papers improved the efficiency of Chaum-Fiat-Naor using modern cryptographic techniques, but arguably the most significant is: J. Camenisch, S. Hohenberger, A. Lysyanskaya, Compact e-cash. Theory and Applications of Cryptographic Techniques, 2005 Some practical security observations on the financial industry and proposals, including Mondex: R. Anderson. Security Engineering (2nd ed). Wiley, 2008. An overview of the implementation of Chaum’s ecash proposal: B. Schoenmakers. Basic security of the ecash payment system. State of the Art in Applied Cryptography, 1997. Two papers cited by Satoshi Nakamoto in the Bitcoin whitepaper that are integral to Bitcon’s design: A. Back. Hashcash - A Denial of Service Counter-Measure, Online, 2002. S. Haber, W. S. Stornetta. Secure names for bitstrings. CCS, 1997. 22
Chapter 1: Introduction to Cryptography & Cryptocurrencies All currencies need some way to control supply and enforce various security properties to prevent cheating. In fiat currencies, organizations like central banks control the money supply and add anti‐counterfeiting features to physical currency. These security features raise the bar for an attacker, but they don’t make money impossible to counterfeit. Ultimately, law enforcement is necessary for stopping people from breaking the rules of the system. Cryptocurrencies too must have security measures that prevent people from tampering with the state of the system, and from equivocating, that is, making mutually inconsistent statements to different people. If Alice convinces Bob that she paid him a digital coin, for example, she should not be able to convince Carol that she paid her that same coin. But unlike fiat currencies, the security rules of cryptocurrencies need to be enforced purely technologically and without relying on a central authority. As the word suggests, cryptocurrencies make heavy use of cryptography. Cryptography provides a mechanism for securely encoding the rules of a cryptocurrency system in the system itself. We can use it to prevent tampering and equivocation, as well as to encode the rules for creation of new units of the currency into a mathematical protocol. Before we can properly understand cryptocurrencies then, we’ll need to delve into the cryptographic foundations that they rely upon. Cryptography is a deep academic research field utilizing many advanced mathematical techniques that are notoriously subtle and complicated to understand. Fortunately, Bitcoin only relies on a handful of relatively simple and well‐known cryptographic constructions. In this chapter, we’ll specifically study cryptographic hashes and digital signatures, two primitives that prove to be very useful for building cryptocurrencies. Future chapters will introduce more complicated cryptographic schemes, such as zero‐knowledge proofs, that are used in proposed extensions and modifications to Bitcoin. Once we’ve learnt the necessary cryptographic primitives, we’ll discuss some of the ways in which those are used to build cryptocurrencies. We’ll complete this chapter with some examples of simple cryptocurrencies that illustrate some of the design challenges that we need to deal with. 1.1 Cryptographic Hash Functions The first cryptographic primitive that we’ll need to understand is a cryptographic hash function. A hash function is a mathematical function with the following three properties: ● Its input can be any string of any size. ● It produces a fixed size output. For the purpose of making the discussion in this chapter concrete, we will assume a 256‐bit output size. However, our discussion holds true for any output size as long as it is sufficiently large. ● It is efficiently computable. Intuitively this means that for a given input string, you can figure 23
out what the output of the hash function is in a reasonable amount of time. More technically, computing the hash of an n‐bit string should have a running time that is O(n). Those properties define a general hash function, one that could be used to build a data structure such as a hash table. We’re going to focus exclusively on cryptographic hash functions. For a hash function to be cryptographically secure, we’re going to require that it has the following three additional properties: (1) collision‐resistance, (2) hiding, (3) puzzle‐friendliness. We’ll look more closely at each of these properties to gain an understanding of why it’s useful to have a function that behaves that way. The reader who has studied cryptography should be aware that the treatment of hash functions in this book is a bit different from a standard cryptography textbook. The puzzle‐friendliness property, in particular, is not a general requirement for cryptographic hash functions, but one that will be useful for cryptocurrencies specifically. Property 1: Collision‐resistance. The first property that we need from a cryptographic hash function is that it’s collision‐resistant. A collision occurs when two distinct inputs produce the same output. A hash function H(.) is collision‐resistant if nobody can find a collision. Formally: Collision‐resistance: A hash function H is said to be collision resistant if it is infeasible to find two values, x and y, such that x ≠ y, yet H(x)=H(y). Figure 1.1 A hash collision. x and y are distinct values, yet when input into hash function H, they produce the same output. Notice that we said nobody can find a collision, but we did not say that no collisions exist. Actually, we know for a fact that collisions do exist, and we can prove this by a simple counting argument. The input space to the hash function contains all strings of all lengths, yet the output space contains only strings of a specific fixed length. Because the input space is larger than the output space (indeed, the input space is infinite, while the output space is finite), there must be input strings that map to the same output string. In fact, by the Pigeonhole Principle there will necessarily be a very large number of possible inputs that map to any particular output. 24
Figure 1.2 Because the number of inputs exceeds the number of outputs, we are guaranteed that there must be at least one output to which the hash function maps more than one input. Now, to make things even worse, we said that it has to be impossible to find a collision. Yet, there are methods that are guaranteed to find a collision. Consider the following simple method for finding a collision for a hash function with a 256‐bit output size: pick 2256 + 1 distinct values, compute the hashes of each of them, and check if there are any two outputs are equal. Since we picked more inputs than possible outputs, some pair of them must collide when you apply the hash function. The method above is guaranteed to find a collision. But if we pick random inputs and compute the hash values, we’ll find a collision with high probability long before examining 2256 + 1 inputs. In fact, if we randomly choose just 2130 + 1 inputs, it turns out there’s a 99.8% chance that at least two of them are going to collide. The fact that we can find a collision by only examining roughly the square root of the number of possible outputs results from a phenomenon in probability known as the birthday paradox. In the homework questions at the end of this chapter, we will examine this in more detail. This collision‐detection algorithm works for every hash function. But, of course, the problem with it is that this takes a very, very long time to do. For a hash function with a 256‐bit output, you would have to compute the hash function 2256 + 1 times in the worst case, and about 2128 times on average. That’s of course an astronomically large number — if a computer calculates 10,000 hashes per second, it would take more than one octillion (1027) years to calculate 2128 hashes! For another way of thinking about this, we can say that, if every computer ever made by humanity was computing since the beginning of the entire universe, up to now, the odds that they would have found a collision is still infinitesimally small. So small that it’s way less than the odds that the Earth will be destroyed by a giant meteor in the next two seconds. We have thus seen a general but impractical algorithm to find a collision for any hash function. A more difficult question is: is there some other method that could be used on a particular hash function in order to find a collision? In other words, although the generic collision detection algorithm is not feasible to use, there still may be some other algorithm that can efficiently find a collision for a specific hash function. Consider, for example, the following hash function: 25
H(x) = x mod 2256 This function meets our requirements of a hash function as it accepts inputs of any length, returns a fixed sized output (256 bits), and is efficiently computable. But this function also has an efficient method for finding a collision. Notice that this function just returns the last 256 bits of the input. One collision then would be the values 3 and 3 + 2256. This simple example illustrates that even though our generic collision detection method is not usable in practice, there are at least some hash functions for which an efficient collision detection method does exist. Yet for other hash functions, we don’t know if such methods exist. We suspect that they are collision resistant. However, there are no hash functions proven to be collision‐resistant. The cryptographic hash functions that we rely on in practice are just functions for which people have tried really, really hard to find collisions and haven’t yet succeeded. In some cases, such as the old MD5 hash function, collisions were eventually found after years of work, leading the function to be deprecated and phased out of practical use. And so we choose to believe that those are collision resistant. Application: Message digests Now that we know what collision‐resistance is, the logical question is: What is collision‐resistance useful for? Here’s one application: If we know that two inputs x and y to a collision‐resistant hash function H are different, then it’s safe to assume that their hashes H(x) and H(y) are different — if someone knew an x and y that were different but had the same hash, that would violate our assumption that H is collision resistant. This argument allows us to use hash outputs as a message digest. Consider SecureBox, an authenticated online file storage system that allows users to upload files and ensure their integrity when they download them. Suppose that Alice uploads really large file, and wants to be able to verify later that the file she downloads is the same as the one she uploads. One way to do that would be to save the whole big file locally, and directly compare it to the file she downloads. While this works, it largely defeats the purpose of uploading it in the first place; if Alice needs to have access to a local copy of the file to ensure its integrity, she can just use the local copy directly. Collision‐free hashes provide an elegant and efficient solution to this problem. Alice just needs to remember the hash of the original file. When she later downloads the file from SecureBox, she computes the hash of the downloaded file and compares it to the one she stored. If the hashes are the same, then she can conclude that the file is indeed the one she uploaded, but if they are different, then Alice can conclude that the file has been tampered with. Remembering the hash thus allows her to detect accidental corruption of the file during transmission or on SecureBox’s servers, but also intentional modification of the file by the server. Such guarantees in the face of potentially malicious behavior by other entities are at the core of what cryptography gives us. The hash serves as a fixed length digest, or unambiguous summary, of a message. This gives us a very efficient way to remember things we’ve seen before and recognize them again. Whereas the entire file might have been gigabytes long, the hash is of fixed length, 256‐bits for the hash function in our example. This greatly reduces our storage requirement. Later in this chapter and throughout the book, we’ll see applications for which it’s useful to use a hash as a message digest. 26
Property 2: Hiding The second property that we want from our hash functions is that it’s hiding. The hiding property asserts that if we’re given the output of the hash function y = H(x), there’s no feasible way to figure out what the input, x, was. The problem is that this property can’t be true in the stated form. Consider the following simple example: we’re going to do an experiment where we flip a coin. If the result of the coin flip was heads, we’re going to announce the hash of the string “heads”. If the result was tails, we’re going to announce the hash of the string “tails”. We then ask someone, an adversary, who didn’t see the coin flip, but only saw this hash output, to figure out what the string was that was hashed (we’ll soon see why we might want to play games like this). In response, they would simply compute both the hash of the string “heads” and the hash of the string “tails”, and they could see which one they were given. And so, in just a couple steps, they can figure out what the input was. The adversary was able to guess what the string was because there were only two possible values of x, and it was easy for the adversary to just try both of them. In order to be able to achieve the hiding property, it needs to be the case that there’s no value of x which is particularly likely. That is, x has to be chosen from a set that’s, in some sense, very spread out. If x is chosen from such a set, this method of trying a few values of x that are especially likely will not work. The big question is: can we achieve the hiding property when the values that we want do not come from a spread‐out set as in our “heads” and “tails” experiment? Fortunately, the answer is yes! So perhaps we can hide even an input that’s not spread out by concatenating it with another input that is spread out. We can now be slightly more precise about what we mean by hiding (the double vertical bar ‖ denotes concatenation). Hiding. A hash function H is hiding if: when a secret value r is chosen from a probability distribution that has high min‐entropy, then given H(r ‖ x) it is infeasible to find x. In information‐theory, min‐entropy is a measure of how predictable an outcome is, and high min‐entropy captures the intuitive idea that the distribution (i.e., random variable) is very spread out. What that means specifically is that when we sample from the distribution, there’s no particular value that’s likely to occur. So, for a concrete example, if r is chosen uniformly from among all of the strings that are 256 bits long, then any particular string was chosen with probability 1/2256, which is an infinitesimally small value. Application: Commitments. Now let’s look at an application of the hiding property. In particular, what we want to do is something called a commitment. A commitment is the digital analog of taking a value, sealing it in an envelope, and putting that envelope out on the table where everyone can see it. When you do that, you’ve committed yourself to what’s inside the envelope. But you haven’t opened it, so even though you’ve committed to a value, the value remains a secret from everyone else. Later, you can open the envelope and reveal the value that you committed to earlier. 27
Commitment scheme. A commitment scheme consists of two algorithms: ● com := commit(msg, nonce) The commit function takes a message and secret random value, called a nonce, as input and returns a commitment. ● verify(com, msg, nonce) The verify function takes a commitment, nonce, and message as input. It returns true if com == commit(msg, nonce) and false otherwise. We require that the following two security properties hold: ● Hiding: Given com, it is infeasible to find msg ● Binding: It is infeasible to find two pairs (msg, nonce) and (msg’, nonce’) such that msg ≠ msg’ and commit(msg, nonce) == commit(msg’, nonce’) To use a commitment scheme, we first need to generate a random nonce. We then apply the commit function to this nonce together with msg, the value being committed to, and we publish the commitment com. This stage is analogous to putting the sealed envelope on the table. At a later point, if we want to reveal the value that they committed to earlier, we publish the random nonce that we used to create this commitment, and the message, msg. Now, anybody can verify that msg was indeed the message committed to earlier. This stage is analogous to opening up the envelope. Every time you commit to a value, it is important that you choose a new random value nonce. In cryptography, the term nonce is used to refer to a value that can only be used once. The two security properties dictate that the algorithms actually behave like sealing and opening an envelope. First, given com, the commitment, someone looking at the envelope can’t figure out what the message is. The second property is that it’s binding. This ensures that when you commit to what’s in the envelope, you can’t change your mind later. That is, it’s infeasible to find two different messages, such that you can commit to one message, and then later claim that you committed to another. So how do we know that these two properties hold? Before we can answer this, we need to discuss how we’re going to actually implement a commitment scheme. We can do so using a cryptographic hash function. Consider the following commitment scheme: commit(msg, nonce) := H(nonce ‖ msg) where nonce is a random 256‐bit value To commit to a message, we generate a random 256‐bit nonce. Then we concatenate the nonce and the message and return the hash of this concatenated value as the commitment. To verify, someone will compute this same hash of the nonce they were given concatenated with the message. And they will check whether that’s equal to the commitment that they saw. Take another look at the two properties that we require of our commitment schemes. If we substitute the instantiation of commit and verify as well as H(nonce ‖ msg) for com, then these properties 28
become: ● Hiding: Given H(nonce ‖ msg), it is infeasible to find msg ● Binding: It is infeasible to find two pairs (msg, nonce) and (msg’, nonce’) such that msg ≠ msg’ and H(nonce ‖ msg) == H(nonce’ ‖ msg’) The hiding property of commitments is exactly the hiding property that we required for our hash functions. If key was chosen as a random 256‐bit value then the hiding property says that if we hash the concatenation of key and the message, then it’s infeasible to recover the message from the hash output. And it turns out that the binding property is implied by1 the collision‐resistant property of the underlying hash function. If the hash function is collision‐resistant, then it will be infeasible to find distinct values msg and msg’ such that H(nonce ‖ msg) = H(nonce’ ‖ msg’) since such values would indeed be a collision. Therefore, if H is a hash function that is collision‐resistant and hiding, this commitment scheme will work, in the sense that it will have the necessary security properties. Property 3: Puzzle friendliness. The third security property we’re going to need from hash functions is that they are puzzle‐friendly. This property is a bit complicated. We will first explain what the technical requirements of this property are and then give an application that illustrates why this property is useful. Puzzle friendliness. A hash function H is said to be puzzle‐friendly if for every possible n‐bit output value y, if k is chosen from a distribution with high min‐entropy, then it is infeasible to find x such that H(k ‖ x) = y in time significantly less than 2n. Intuitively, what this means is that if someone wants to target the hash function to come out to some particular output value y, that if there’s part of the input that is chosen in a suitably randomized way, it’s very difficult to find another value that hits exactly that target. Application: Search puzzle. Now, let’s consider an application that illustrates the usefulness of this property. In this application, we’re going to build a search puzzle, a mathematical problem which requires searching a very large space in order to find the solution. In particular, a search puzzle has no shortcuts. That is, there’s no way to find a valid solution other than searching that large space. 1 The reverse implications do not hold. That is, it’s possible that you can find collisions, but none of them are of the form H(nonce ‖ msg) == H(nonce’ ‖ msg’). For example, if you can only find a collision in which two distinct nonces generate the same commitment for the same message, then the commitment scheme is still binding, but the underlying hash function is not collision‐resistant. 29
Search puzzle. A search puzzle consists of ● a hash function, H, ● a value, id (which we call the puzzle‐ID), chosen from a high min‐entropy distribution ● and a target set Y A solution to this puzzle is a value, x, such that H(id ‖ x) ∈ Y. The intuition is this: if H has an n‐bit output, then it can take any of 2n values. Solving the puzzle requires finding an input so that the output falls within the set Y, which is typically much smaller than the set of all outputs. The size of Y determines how hard the puzzle is. If Y is the set of all n‐bit strings the puzzle is trivial, whereas if Y has only 1 element the puzzle is maximally hard. The fact that the puzzle id has high min‐entropy ensures that there are no shortcuts. On the contrary, if a particular value of the ID were likely, then someone could cheat, say by pre‐computing a solution to the puzzle with that ID. If a search puzzle is puzzle‐friendly, this implies that there’s no solving strategy for this puzzle which is much better than just trying random values of x. And so, if we want to pose a puzzle that’s difficult to solve, we can do it this way as long as we can generate puzzle‐IDs in a suitably random way. We’re going to use this idea later when we talk about Bitcoin mining, which is a sort of computational puzzle. SHA‐256. We’ve discussed three properties of hash functions, and one application of each of those. Now let’s discuss a particular hash function that we’re going to use a lot in this book. There are lots of hash functions in existence, but this is the one Bitcoin uses primarily, and it’s a pretty good one to use. It’s called SHA‐256. Recall that we require that our hash functions work on inputs of arbitrary length. Luckily, as long as we can build a hash function that works on fixed‐length inputs, there’s a generic method to convert it into a hash function that works on arbitrary‐length inputs. It’s called the Merkle‐Damgard transform. SHA‐256 is one of a number of commonly used hash functions that make use of this method. In common terminology, the underlying fixed‐length collision‐resistant hash function is called the compression function. It has been proven that if the underlying compression function is collision resistant, then the overall hash function is collision resistant as well. The Merkle‐Damgard transform is quite simple. Say the compression function takes inputs of length m and produces an output of a smaller length n. The input to the hash function, which can be of any size, is divided into blocks of length m‐n. The construction works as follows: pass each block together with the output of the previous block into the compression function. Notice that input length will then be (m‐n) + n = m, which is the input length to the compression function. For the first block, to which there is no previous block output, we instead use an Initialization Vector (IV). This number is reused for every call to the hash function, and in practice you can just look it up in a standards document. The last block’s output is the result that you return. 30
SHA‐256 uses a compression function that takes 768‐bit input and produces 256‐bit outputs. The block size is 512 bits. See Figure 1.3 for a graphical depiction of how SHA‐256 works. Figure 1.3: SHA‐256 Hash Function (simplified). SHA‐256 uses the Merkle‐Damgard transform to turn a fixed‐length collision‐resistant compression function into a hash function that accepts arbitrary‐length inputs. The input is “padded” so that its length is a multiple of 512 bits. We’ve talked about hash functions, cryptographic hash functions with special properties, applications of those properties, and a specific hash function that we use in Bitcoin. In the next section, we’ll discuss ways of using hash functions to build more complicated data structures that are used in distributed systems like Bitcoin. Sidebar: modeling hash functions. Hash functions are the Swiss Army knife of cryptography: they find a place in a spectacular variety of applications. The flip side to this versatility is that different applications require slightly different properties of hash functions to ensure security. It’s proven notoriously hard to pin down a list of hash function properties that would result in provable security across the board. In this text, we’ve selected three properties that are crucial to the way that hash functions are used in Bitcoin and other cryptocurrencies. Even within this space, not all of these properties are necessary for every use of hash functions. For example, puzzle‐friendliness is only important in Bitcoin mining, as we’ll see. Designers of secure systems often throw in the towel and model hash functions as functions that output an independent random value for every possible input. The use of this “random oracle model” for proving security remains controversial in cryptography. Regardless of one’s position on this debate, reasoning about how to reduce the security properties that we want in our applications to fundamental properties of the underlying primitives is a valuable intellectual exercise for building secure systems. Our presentation in this chapter is designed to help you learn this skill. 31
1.2 Hash Pointers and Data Structures In this section, we’re going to discuss hash pointers and their applications. A hash pointer is a data structure that turns out to be useful in many of the systems that we will talk about. A hash pointer is simply a pointer to where some information is stored together with a cryptographic hash of the information. Whereas a regular pointer gives you a way to retrieve the information, a hash pointer also gives you a way to verify that the information hasn’t changed. Figure 1.4 Hash pointer. A hash pointer is a pointer to where data is stored together with a cryptographic hash of the value of that data at some fixed point in time. We can use hash pointers to build all kinds of data structures. Intuitively, we can take a familiar data structure that uses pointers such as a linked list or a binary search tree and implement it with hash pointers, instead of pointers as we normally would. Block chain. In Figure 1.5, we built a linked list using hash pointers. We’re going to call this data structure a block chain. Whereas as in a regular linked list where you have a series of blocks, each block has data as well as a pointer to the previous block in the list, in a block chain the previous block pointer will be replaced with a hash pointer. So each block not only tells us where the value of the previous block was, but it also contains a digest of that value that allows us to verify that the value hasn’t changed. We store the head of the list, which is just a regular hash‐pointer that points to the most recent data block. 32
Figure 1.5 Block chain. A block chain is a linked list that is built with hash pointers instead of pointers. A use case for a block chain is a tamper‐evident log. That is, we want to build a log data structure that stores a bunch of data, and allows us to append data onto the end of the log. But if somebody alters data that is earlier in the log, we’re going to detect it. To understand why a block chain achieves this tamper‐evident property, let’s ask what happens if an adversary wants to tamper with data that’s in the middle of the chain. Specifically, the adversary’s goal is to do it in such a way that someone who remembers only the hash pointer at the head of the block chain won’t be able to detect the tampering. To achieve this goal, the adversary changes the data of some block k. Since the data has been changed, the hash in block k + 1, which is a hash of the entire block k, is not going to match up. Remember that we are statistically guaranteed that the new hash will not match the altered content since the hash function is collision resistant. And so we will detect the inconsistency between the new data in block k and the hash pointer in block k + 1. Of course the adversary can continue to try and cover up this change by changing the next block’s hash as well. The adversary can continue doing this, but this strategy will fail when he reaches the head of the list. Specifically, as long as we store the hash pointer at the head of the list in a place where the adversary cannot change it, the adversary will be unable to change any block without being detected. The upshot of this is that if the adversary wants to tamper with data anywhere in this entire chain, in order to keep the story consistent, he’s going to have to tamper with the hash pointers all the way back to the beginning. And he’s ultimately going to run into a roadblock because he won’t be able to tamper with the head of the list. Thus it emerges, that by just remembering this single hash pointer, we’ve essentially remembered a tamper‐evident hash of the entire list. So we can build a block chain like this containing as many blocks as we want, going back to some special block at the beginning of the list, which we will call the genesis block. You may have noticed that the block chain construction is similar to the Merkle‐Damgard construction that we saw in the previous section. Indeed, they are quite similar, and the same security argument applies to both of them. 33
Figure 1.6 Tamper‐evident log. If an adversary modifies data anywhere in the block chain, it will result in the hash pointer in the following block being incorrect. If we store the head of the list, then even if the adversary modifies all of the pointers to be consistent with the modified data, the head pointer will be incorrect, and we will detect the tampering. Merkle trees. Another useful data structure that we can build using hash pointers is a binary tree. A binary tree with hash pointers is known as a Merkle tree, after its inventor Ralph Merkle. Suppose we have a number of blocks containing data. These blocks comprise the leaves of our tree. We group these data blocks into pairs of two, and then for each pair, we build a data structure that has two hash pointers, one to each of these blocks. These data structures make the next level up of the tree. We in turn group these into groups of two, and for each pair, create a new data structure that contains the hash of each. We continue doing this until we reach a single block, the root of the tree. 34
Figure 1.7 Merkle tree. In a Merkle tree, data blocks are grouped in pairs and the hash of each of these blocks is stored in a parent node. The parent nodes are in turn grouped in pairs and their hashes stored one level up the tree. This continues all the way up the tree until we reach the root node. As before, we remember just the hash pointer at the head of the tree. We now have the ability traverse down through the hash pointers to any point in the list. This allows us make sure that the data hasn’t been tampered with because, just like we saw with the block chain, if an adversary tampers with some data block at the bottom of the tree, that will cause the hash pointer that’s one level up to not match, and even if he continues to tamper with this block, the change will eventually propagate to the top of the tree where he won’t be able to tamper with the hash pointer that we’ve stored. So again, any attempt to tamper with any piece of data will be detected by just remembering the hash pointer at the top. Proof of membership. Another nice feature of Merkle trees is that, unlike the block chain that we built before, it allows a concise proof of membership. Say that someone wants to prove that a certain data block is a member of the Merkle Tree. As usual, we remember just the root. Then they need to show us this data block, and the blocks on the path from the data block to the root. We can ignore the rest of the tree, as the blocks on this path are enough to allow us to verify the hashes all the way up to the root of the tree. See Figure 1.8 for a graphical depiction of how this works. If there are n nodes in the tree, only about log(n) items need to be shown. And since each step just requires computing the hash of the child block, it takes about log(n) time for us to verify it. And so even if the Merkle tree contains a very large number of blocks, we can still prove membership in a relatively short time. Verification thus runs in time and space that’s logarithmic in the number of 35
nodes in the tree. Figure 1.8 Proof of membership. To prove that a data block is included in the tree, one only needs to show the blocks in the path from that data block to the root. A sorted Merkle tree is just a Merkle tree where we take the blocks at the bottom, and we sort them using some ordering function. This can be alphabetical, lexicographical order, numerical order, or some other agreed upon ordering. Proof of non‐membership. With a sorted Merkle tree, it becomes possible to verify non‐membership in a logarithmic time and space. That is, we can prove that a particular block is not in the Merkle tree. And the way we do that is simply by showing a path to the item that’s just before where the item in question would be and showing the path to the item that is just after where it would be. If these two items are consecutive in the tree, then this serves as a proof that the item in question is not included. For if it was included, it would need to be between the two items shown, but there is no space between them as they are consecutive. We’ve discussed using hash pointers in linked lists and binary trees, but more generally, it turns out that we can use hash pointers in any pointer‐based data structure as long as the data structure doesn’t have cycles. If there are cycles in the data structure, then we won’t be able to make all the hashes match up. If you think about it, in an acyclic data structure, we can start near the leaves, or near the things that don’t have any pointers coming out of them, compute the hashes of those, and then work our way back toward the beginning. But in a structure with cycles, there’s no end we can start with and compute back from. So, to consider another example, we can build a directed acyclic graph out of hash pointers. And we’ll be able to verify membership in that graph very efficiently. And it will be easy to compute. Using hash pointers in this manner is a general trick that you’ll see time and again in the context of the distributed data structures and throughout the algorithms that we discuss later in this chapter and 36
throughout this book. 1.3 Digital Signatures In this section, we’ll look at digital signatures. This is the second cryptographic primitive, along with hash functions, that we need as building blocks for the cryptocurrency discussion later on. A digital signature is supposed to be the digital analog to a handwritten signature on paper. We desire two properties from digital signatures that correspond well to the handwritten signature analogy. Firstly, only you can make your signature, but anyone who sees it can verify that it’s valid. Secondly, we want the signature to be tied to a particular document so that the signature cannot be used to indicate your agreement or endorsement of a different document. For handwritten signatures, this latter property is analogous to assuring that somebody can’t take your signature and snip it off one document and glue it onto the bottom of another one. How can we build this in a digital form using cryptography? First, let’s make the previous intuitive discussion slightly more concrete. This will allow us to reason better about digital signature schemes and discuss their security properties. Digital signature scheme. A digital signature scheme consists of the following three algorithms: ● (sk, pk) := generateKeys(keysize) The generateKeys method takes a key size and generates a key pair. The secret key sk is kept privately and used to sign messages. pk is the public verification key that you give to everybody. Anyone with this key can verify your signature. ● sig := sign(sk, message) The sign method takes a message and a secret key, sk, as input and outputs a signature for message under sk ● isValid := verify(pk, message, sig) The verify method takes a message, a signature, and a public key as input. It returns a boolean value, isValid, that will be true if sig is a valid signature for message under public key pk, and false otherwise. We require that the following two properties hold: ● Valid signatures must verify verify(pk, message, sign(sk, message)) == true ● Signatures are existentially unforgeable We note that generateKeys and sign can be randomized algorithms. Indeed, generateKeys had better be randomized because it ought to be generating different keys for different people. verify, on the other hand, will always be deterministic. Let us now examine the two properties that we require of a digital signature scheme in more detail. The first property is straightforward — that valid signatures must verify. If I sign a message with sk, my secret key, and someone later tries to validate that signature over that same message using my public key, pk, the signature must validate correctly. This property is a basic requirement for signatures to be 37
useful at all. Unforgeability. The second requirement is that it’s computationally infeasible to forge signatures. That is, an adversary who knows your public key and gets to see your signatures on some other messages can’t forge your signature on some message for which he has not seen your signature. This unforgeability property is generally formalized in terms of a game that we play with an adversary. The use of games is quite common in cryptographic security proofs. In the unforgeability game, there is an adversary who claims that he can forge signatures and a challenger that will test this claim. The first thing we do is we use generateKeys to generate a secret signing key and a corresponding public verification key. We give the secret key to the challenger, and we give the public key to both the challenger and to the adversary. So the adversary only knows information that’s public, and his mission is to try to forge a message. The challenger knows the secret key. So he can make signatures. Intuitively, the setup of this game matches real world conditions. A real‐life attacker would likely be able to see valid signatures from their would‐be victim on a number of different documents. And maybe the attacker could even manipulate the victim into signing innocuous‐looking documents if that’s useful to the attacker. To model this in our game, we’re going to allow the attacker to get signatures on some documents of his choice, for as long as he wants, as long as the number of guesses is plausible. To give an intuitive idea of what we mean by a plausible number of guesses, we would allow the attacker to try 1 million guesses, but not 280 guesses2. Once the attacker is satisfied that he’s seen enough signatures, then the attacker picks some message, M, that they will attempt to forge a signature on. The only restriction on M is that it must be a message for which the attacker has not previously seen a signature (because the attacker can obviously send back a signature that he was given!). The challenger runs the verify algorithm to determine if the signature produced by the attacker is a valid signature on M under the public verification key. If it successfully verifies, the attacker wins the game. 2 In asymptotic terms, we allow the attacker to try a number of guesses that is a polynomial function of the key size, but no more (e.g. the attacker cannot try exponentially many guesses). 38
Figure 1.9 Unforgeability game. The adversary and the challenger play the unforgeability game. If the attacker is able to successfully output a signature on a message that he has not previously seen, he wins. If he is unable, the challenger wins and the digital signature scheme is unforgeable. We say that the signature scheme is unforgeable if and only if, no matter what algorithm the adversary is using, his chance of successfully forging a message is extremely small — so small that we can assume it will never happen in practice. Practical Concerns. There are a number of practical things that we need to do to turn the algorithmic idea into a digital signature mechanism that can be implemented in practice. For example, many signature algorithms are randomized (in particular the one used in Bitcoin) and we therefore need a good source of randomness. The importance of this really can’t be underestimated as bad randomness will make your otherwise‐secure algorithm insecure. Another practical concern is the message size. In practice, there’s a limit on the message size that you’re able to sign because real schemes are going to operate on bit strings of limited length. There’s an easy way around this limitation: sign the hash of the message, rather than the message itself. If we use a cryptographic hash function with a 256‐bit output, then we can effectively sign a message of any length as long as our signature scheme can sign 256‐bit messages. As we discussed before, it’s safe to use the hash of the message as a message digest in this manner since the hash function is collision 39
resistant. Another trick that we will use later is that you can sign a hash pointer. If you sign a hash pointer, then the signature covers, or protects, the whole structure — not just the hash pointer itself, but everything the chain of hash pointers points to. For example, if you were to sign the hash pointer that was at the end of a block chain, the result is that you would effectively be digitally signing the that entire block chain. ECDSA. Now let’s get into the nuts and bolts. Bitcoin uses a particular digital signature scheme that’s called the Elliptic Curve Digital Signature Algorithm (ECDSA). ECDSA is a U.S. government standard, an update of the earlier DSA algorithm adapted to use elliptic curves. These algorithms have received considerable cryptographic analysis over the years and are generally believed to be secure. More specifically, Bitcoin uses ECDSA over the standard elliptic curve “secp256k1” which is estimated to provide 128 bits of security (that is, it is as difficult to break this algorithm as performing 2128 symmetric‐key cryptographic operations such as invoking a hash function). While this curve is a published standard, it is rarely used outside of Bitcoin, with other applications using ECDSA (such as key exchange in TLS for secure web browsing) typically using the more common “secp256r1” curve. This is just a quirk of Bitcoin, as this was chosen by Satoshi in the early specification of the system and is now difficult to change. We won’t go into all the details of how ECDSA works as there’s some complicated math involved, and understanding it is not necessary for any other content in this book. If you’re interested in the details, refer to our further reading section at the end of this chapter. It might be useful to have an idea of the sizes of various quantities, however: Private key: 256 bits Public key, uncompressed: 512 bits Public key, compressed: 257 bits Message to be signed: 256 bits Signature: 512 bits Note that while ECDSA can technically only sign messages 256 bits long, this is not a problem: messages are always hashed before being signed, so effectively any size message can be efficiently signed. With ECDSA, a good source of randomness is essential because a bad source of randomness will likely leak your key. It makes intuitive sense that if you use bad randomness in generating a key, then the key you generate will likely not be secure. But it’s a quirk of ECDSA3 that, even if you use bad 3 For those familiar with DSA, this is a general quirk in DSA and not specific to the elliptic‐curve variant. 40
randomness just in making a signature, using your perfectly good key, that also will leak your private key. And then it’s game over; if you leak your private key, an adversary can forge your signature. We thus need to be especially careful about using good randomness in practice, and using a bad source of randomness is a common pitfall of otherwise secure systems. This completes our discussion of digital signatures as a cryptographic primitive. In the next section, we’ll discuss some applications of digital signatures that will turn out to be useful for building cryptocurrencies. Sidebar: cryptocurrencies and encryption. If you've been waiting to find out which encryption algorithm is used in Bitcoin, we're sorry to disappoint you. There is no encryption in Bitcoin, because nothing needs to be encrypted, as we'll see. Encryption is only one of a rich suite of techniques made possible by modern cryptography. Many of them, such as commitment schemes, involve hiding information in some way, but they are distinct from encryption. 1.4 Public Keys as Identities Let’s look at a nice trick that goes along with digital signatures. The idea is to take a public key, one of those public verification keys from a digital signature scheme, and equate that to an identity of a person or an actor in a system. If you see a message with a signature that verifies correctly under a public key, pk, then you can think of this as pk is saying the message. You can literally think of a public key as kind of like an actor, or a party in a system who can make statements by signing those statements. From this viewpoint, the public key is an identity. In order for someone to speak for the identity pk, they must know the corresponding secret key, sk. A consequence of treating public keys as identities is that you can make a new identity whenever you want — you simply create a new fresh key pair, sk and pk, via the generateKeys operation in our digital signature scheme. pk is the new public identity that you can use, and sk is the corresponding secret key that only you know and lets you speak for on behalf of the identity pk. In practice, you may use the hash of pk as your identity since public keys are large. If you do that, then in order to verify that a message comes from your identity, one will have to check (1) that pk indeed hashes to your identity, and (2) the message verifies under public key pk. Moreover, by default, your public key pk will basically look random, and nobody will be able to uncover your real world identity by examining pk.4 You can generate a fresh identity that looks random, that looks like a face in the crowd, and that only you can control. Decentralized identity management. This brings us to the idea of decentralized identity management. Rather than having a central authority that you have to go to in order to register as a user in a system, you can register as a user all by yourself. You don’t need to be issued a username nor do you need to 4 Of course, once you start making statements using this identity, these statements may leak information that allows one to connect pk to your real world identity. We will discuss this in more detail shortly. 41
inform someone that you’re going to be using a particular name. If you want a new identity, you can just generate one at any time, and you can make as many as you want. If you prefer to be known by five different names, no problem! Just make five identities. If you want to be somewhat anonymous for a while, you can make a new identity, use it just for a little while, and then throw it away. All of these things are possible with decentralized identity management, and this is the way Bitcoin, in fact, does identity. These identities are called addresses, in Bitcoin jargon. You’ll frequently hear the term address used in the context of Bitcoin and cryptocurrencies, and that’s really just a hash of a public key. It’s an identity that someone made up out of thin air, as part of this decentralized identity management scheme. Sidebar. The idea that you can generate an identity without a centralized authority may seem counterintuitive. After all, if someone else gets lucky and generates the same key as you can’t they steal your bitcoins? The answer is that the probability of someone else generating the same 256‐bit key as you is so small that we don’t have to worry about it in practice. We are for all intents and purposes guaranteed that it will never happen. More generally, in contrast to beginners’ intuition that probabilistic systems are unpredictable and hard to reason about, often the opposite is true — the theory of statistics allows us to precisely quantify the chances of events we’re interested in and make confident assertions about the behavior of such systems. But there’s a subtlety: the probabilistic guarantee is true only when keys are generated at random. The generation of randomness is often a weak point in real systems. If two users’ computers use the same source of randomness or use predictable randomness, then the theoretical guarantees no longer apply. So it is crucial to use a good source of randomness when generating keys to ensure that practical guarantees match the theoretical ones. On first glance, it may seems that decentralized identity management leads to great anonymity and privacy. After all, you can create a random‐looking identity all by yourself without telling anyone your real‐world identity. But it’s not that simple. Over time, the identity that you create makes a series of statements. People see these statements and thus know that whoever owns this identity has done a certain series of actions. They can start to connect the dots, using this series of actions to infer things about your real‐world identity. An observer can link together these things over time, and make inferences that lead them to conclusions such as, “Gee, this person is acting a lot like Joe. Maybe this person is Joe.” In other words, in Bitcoin you don’t need to explicitly register or reveal your real‐world identity, but the pattern of your behavior might itself be identifying. This is the fundamental privacy question in a cryptocurrency like Bitcoin, and indeed we’ll devote the entirety of Chapter 6 to it. 42
1.5 A Simple Cryptocurrency Now let’s move from cryptography to cryptocurrencies. Eating our cryptographic vegetables will start to pay off here, and we’ll gradually see how the pieces fit together and why cryptographic operations like hash functions and digital signatures are actually useful. In this section we’ll discuss two very simple cryptocurrencies. Of course, it’s going to require much of the rest of the book to spell out all the implications of how Bitcoin itself works. GoofyCoin The first of the two is GoofyCoin, which is about the simplest cryptocurrency we can imagine. There are just two rules of GoofyCoin. The first rule is that a designated entity, Goofy, can create new coins whenever he wants and these newly created coins belong to him. To create a coin, Goofy generates a unique coin ID uniqueCoinID that he’s never generated before and constructs the string “CreateCoin [uniqueCoinID]”. He then computes the digital signature of this string with his secret signing key. The string, together with Goofy’s signature, is a coin. Anyone can verify that the coin contains Goofy’s valid signature of a CreateCoin statement, and is therefore a valid coin. The second rule of GoofyCoin is that whoever owns a coin can transfer it on to someone else. Transferring a coin is not simply a matter of sending the coin data structure to the recipient — it’s done using cryptographic operations. Let’s say Goofy wants to transfer a coin that he created to Alice. To do this he creates a new statement that says “Pay this to Alice” where “this” is a hash pointer that references the coin in question. And as we saw earlier, identities are really just public keys, so “Alice” refers to Alice’s public key. Finally, Goofy signs the string representing the statement. Since Goofy is the one who originally owned that coin, he has to sign any transaction that spends the coin. Once this data structure representing Goofy’s transaction signed by him exists, Alice owns the coin. She can prove to anyone that she owns the coin, because she can present the data structure with Goofy’s valid signature. Furthermore, it points to a valid coin that was owned by Goofy. So the validity and ownership of coins are self‐evident in the system. Once Alice owns the coin, she can spend it in turn. To do this she creates a statement that says, “Pay this coin to Bob’s public key” where “this” is a hash pointer to the coin that was owned by her. And of course, Alice signs this statement. Anyone, when presented with this coin, can verify that Bob is the owner. They would follow the chain of hash pointers back to the coin’s creation and verify that at each step, the rightful owner signed a statement that says “pay this coin to [new owner]”. 43
Figure 1.10 GoofyCoin coin. Shown here is a coin that’s been created (bottom) and spent twice (middle and top). To summarize, the rules of GoofyCoin are: ● Goofy can create new coins by simply signing a statement that he’s making a new coin with a unique coin ID. ● Whoever owns a coin can pass it on to someone else by signing a statement that saying, “Pass on this coin to X” (where X is specified as a public key) ● Anyone can verify the validity of a coin by following the chain of hash pointers back to its creation by Goofy, verifying all of the signatures along the way. Of course, there’s a fundamental security problem with GoofyCoin. Let’s say Alice passed her coin on to Bob by sending her signed statement to Bob but didn’t tell anyone else. She could create another signed statement that pays the very same coin to Chuck. To Chuck, it would appear that it is perfectly valid transaction, and now he’s the owner of the coin. Bob and Chuck would both have valid‐looking claims to be the owner of this coin. This is called a double‐spending attack — Alice is spending the same coin twice. Intuitively, we know coins are not supposed to work that way. In fact, double‐spending attacks are one of the key problems that any cryptocurrency has to solve. GoofyCoin does not solve the double‐spending attack and therefore it’s not secure. GoofyCoin is simple, and its mechanism for transferring coins is actually very similar to Bitcoin, but because it is insecure it won’t cut it as a cryptocurrency. ScroogeCoin To solve the double‐spending problem, we’ll design another cryptocurrency, which we’ll call ScroogeCoin. ScroogeCoin is built off of GoofyCoin, but it’s a bit more complicated in terms of data structures. 44
The first key idea is that a designated entity called Scrooge publishes an append‐only ledger containing the history of all the transactions that have happened. The append‐only property ensures that any data written to this ledger will remain forever. If the ledger is truly append‐only, we can use it to defend against double‐spending by requiring all transactions to be written the ledger before they are accepted. That way, it will be publicly visible if coins were previously sent to a different owner. To implement this append‐only functionality, Scrooge can build a block chain (the data structure we discussed before) which he will digitally sign. It’s a series of data blocks, each with one transaction in it (in practice, as an optimization, we’d really put multiple transactions into the same block, as Bitcoin does.) Each block has the ID of a transaction, the transaction’s contents, and a hash pointer to the previous block. Scrooge digitally signs the final hash pointer, which binds all of the data in this entire structure, and publishes the signature along with the block chain. Figure 1.11 ScroogeCoin block chain. In ScroogeCoin a transaction only counts if it is in the block chain signed by Scrooge. Anybody can verify that a transaction was endorsed by Scrooge by checking Scrooge’s signature on the block that it appears in. Scrooge makes sure that he doesn’t endorse a transaction that attempts to double‐spend an already spent coin. Why do we need a block chain with hash pointers in addition to having Scrooge sign each block? This ensures the append‐only property. If Scrooge tries to add or remove a transaction to the history, or change an existing transaction, it will affect all of the following blocks because of the hash pointers. As long as someone is monitoring the latest hash pointer published by Scrooge, the change will be obvious and easy to catch. In a system where Scrooge signed blocks individually, you’d have to keep track of every single signature Scrooge ever issued. A block chain makes it very easy for any two individuals to verify that they have observed the exact same history of transactions signed by Scrooge. In ScroogeCoin, there are two kinds of transactions. The first kind is CreateCoins, which is just like the operation Goofy could do in GoofyCoin that makes a new coin. With ScroogeCoin, we’ll extend the semantics a bit to allow multiple coins to be created in one transaction. 45
Figure 1.12 CreateCoins transaction. This CreateCoins transaction creates multiple coins. Each coin has a serial number within the transaction. Each coin also has a value; it’s worth a certain number of scroogecoins. Finally, each coin has a recipient, which is a public key that gets the coin when it’s created. So CreateCoins creates a bunch of new coins with different values and assigns them to people as initial owners. We refer to coins by CoinIDs. A CoinID is a combination of a transaction ID and the coin’s serial number within that transaction. A CreateCoins transaction is always valid by definition if it is signed by Scrooge. We won’t worry about when Scrooge is entitled to create coins or how many, just like we didn’t worry in GoofyCoin about how Goofy is chosen as the entity allowed to create coins. The second kind of transaction is PayCoins. It consumes some coins, that is, destroys them, and creates new coins of the same total value. The new coins might belong to different people (public keys). This transaction has to be signed by everyone who’s paying in a coin. So if you’re the owner of one of the coins that’s going to be consumed in this transaction, then you need to digitally sign the transaction to say that you’re really okay with spending this coin. The rules of ScroogeCoin say that PayCoins transaction is valid if four things are true: ● The consumed coins are valid, that is, they really were created in previous transactions. ● The consumed coins were not already consumed in some previous transaction. That is, that this is not a double‐spend. ● The total value of the coins that come out of this transaction is equal to the total value of the coins that went in. That is, only Scrooge can create new value. ● The transaction is validly signed by the owners of all of the consumed coins. 46
Figure 1.13 A PayCoins Transaction. If all of those conditions are met, then this PayCoins transaction is valid and Scrooge will accept it. He’ll write it into the history by appending it to the block chain, after which everyone can see that this transaction has happened. It is only at this point that the participants can accept that the transaction has actually occurred. Until it is published, it might be preempted by a douple‐spending transaction even if it is otherwise valid by the first three conditions. Coins in this system are immutable — they are never changed, subdivided, or combined. Each coin is created, once, in one transaction and later consumed in some other transaction. But we can get the same effect as being able to subdivide or combine coins by using transactions. For example, to subdivide a coin, Alice create a new transaction that consumes that one coin, and then produces two new coins of the same total value. Those two new coins could be assigned back to her. So although coins are immutable in this system, it has all the flexibility of a system that didn’t have immutable coins. Now, we come to the core problem with ScroogeCoin. ScroogeCoin will work in the sense that people can see which coins are valid. It prevents double‐spending, because everyone can look into the block chain and see that all of the transactions are valid and that every coin is consumed only once. But the problem is Scrooge — he has too much influence. He can’t create fake transactions, because he can’t forge other people’s signatures. But he could stop endorsing transactions from some users, denying them service and making their coins unspendable. If Scrooge is greedy (as his cartoon namesake suggests) he could refuse to publish transactions unless they transfer some mandated transaction fee to him. Scrooge can also of course create as many new coins for himself as he wants. Or Scrooge could get bored of the whole system and stop updating the block chain completely. 47
The problem here is centralization. Although Scrooge is happy with this system, we, as users of it, might not be. While ScroogeCoin may seem like an unrealistic proposal, much of the early research on cryptosystems assumed there would indeed be some central trusted authority, typically referred to as a bank. After all, most real‐world currencies do have a trusted issuer (typically a government mint) responsible for creating currency and determining which notes are valid. However, cryptocurrencies with a central authority largely failed to take off in practice. There are many reasons for this, but in hindsight it appears that it’s difficult to get people to accept a cryptocurrency with a centralized authority. Therefore, the central technical challenge that we need to solve in order to improve on ScroogeCoin and create a workable system is: can we descroogify the system? That is, can we get rid of that centralized Scrooge figure? Can we have a cryptocurrency that operates like ScroogeCoin in many ways, but doesn’t have any central trusted authority? To do that, we need to figure out how all users can agree upon a single published block chain as the history of which transactions have happened. They must all agree on which transactions are valid, and which transactions have actually occurred. They also need to be able to assign IDs to things in a decentralized way. Finally, the minting of new coins needs to be controlled in a decentralized way. If we can solve all of those problems, then we can build a currency that would be like ScroogeCoin but without a centralized party. In fact, this would be a system very much like Bitcoin. Further Reading Steven Levy’s Crypto is an enjoyable, non‐technical look at the development of modern cryptography and the people behind it: Levy, Steven. Crypto: How the Code Rebels Beat the Government‐‐Saving Privacy in the Digital Age. Penguin, 2001. Modern cryptography is a rather theoretical field. Cryptographers use mathematics to define primitives, protocols, and their desired security properties in a formal way, and to prove them secure based on widely accepted assumptions about the computational hardness of specific mathematical tasks. In this chapter we’ve used intuitive language to discuss hash functions and digital signatures. For the reader interested in exploring these and other cryptographic concepts in a more mathematical way and in greater detail, we refer you to: Katz, Jonathan, and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014. For an introduction to applied cryptography, see: Ferguson, Niels, Bruce Schneier, and Tadayoshi Kohno. Cryptography engineering: design principles and practical applications. John Wiley & Sons, 2012. 48
Perusing the NIST standard that defines SHA‐2 is a good way to get an intuition for what cryptographic standards look like: FIPS PUB 180‐4, Secure Hash Standards, Federal Information Processing Standards Publication. Information Technology Laboratory, National Institute of Standards and Technology, Gaithersburg, MD, 2008. Finally, here’s the paper describing the standardized version of the ECDSA signature algorithm. Johnson, Don, Alfred Menezes, and Scott Vanstone. The elliptic curve digital signature algorithm (ECDSA). International Journal of Information Security 1.1 (2001): 36‐63. Exercises 1. Authenticated Data Structures. You are designing SecureBox, an authenticated online file storage system. For simplicity, there is only a single folder. Users must be able to add, edit, delete, and retrieve files, and to list the folder contents. When a user retrieves a file, SecureBox must provide a proof that the file hasn’t been tampered with since its last update. If a file with the given name doesn’t exist, the server must report that — again with a proof. We want to minimize the size of these proofs, the time complexity of verifying them, and the size of the digest that the user must store between operations. (Naturally, to be able to verify proofs, users must at all times store some nonzero amount of state derived from the folder contents. Other than this digest the user has no memory of the contents of the files she added.) Here’s a naive approach. The user’s digest is a hash of the entire folder contents, and proofs are copies of the entire folder contents. This results in a small digest but large proofs and long verification times. Besides, before executing add/delete/edit operations, the user must retrieve the entire folder so that she can recompute the digest. Alternatively, the digest could consist of a separate hash for each file, and each file would be its own proof. The downside of this approach is that it requires digest space that is linear in the number of files in the system. Can you devise a protocol where proof size, verification time, and digest size are all sublinear? You might need a sub‐protocol that involves some amount of two‐way communication for the user to be able to update her digest when she executes and add, delete, or edit. Hint: use the Merkle tree idea from Section 1.2. 2. Birthday Attack. Let H be an ideal hash function that produces an n‐bit output. By ideal, we mean that as far as we can tell, each hash value is independent and uniformly distributed in {0,1}n. Trivially, 49
we can go through 2n + 1 different values and we are guaranteed to find a collision. If we're constrained for space, we can just store 1 input‐output pair and keep trying new inputs until we hit the same output again. This has time complexity O(2n), but has O(1) space complexity. Alternatively, we could compute the hashes of about O(2n/2) different inputs and store all the input‐output pairs. As we saw in the text, there’s a good chance that some two of those outputs would collide (the “birthday paradox”). This shows that we can achieve a time‐space trade‐off: O(2n/2) time and O(2n/2) space. 1. (Easy) Show that the time‐space trade‐off is parameterizable: we can achieve any space complexity between O(1) and O(2n/2) with a corresponding decrease in time complexity. 2. (Very hard) Is there an attack for which the product of time and space complexity is o(2n)? [Recall the little oh notation.] 3. Hash function properties (again). Let H be a hash function that is both hiding and puzzle‐friendly. Consider G(z) = H(z) ǁ zlast where zlast represents the last bit of z. Show that G is puzzle‐friendly but not hiding. 4. Randomness. In ScroogeCoin, suppose Mallory tries generating (sk, pk) pairs until her secret key matches someone else’s. What will she be able to do? How long will it take before she succeeds, on average? What if Alice’s random number generator has a bug and her key generation procedure produces only 1,000 distinct pairs? 50
Search
Read the Text Version
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
