4 |
4 |
5 \begin{document} |
5 \begin{document} |
6 |
6 |
7 \section*{Handout 7 (Bitcoins)} |
7 \section*{Handout 7 (Bitcoins)} |
8 |
8 |
9 In my opinion Bitcoins are a Ponzi |
9 In my opinion Bitcoins are an elaborate Ponzi |
10 scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still |
10 scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still |
11 the ideas behind them are really beautiful and not too |
11 the ideas behind them are really beautiful and not too |
12 difficult to understand. Since many colourful claims about |
12 difficult to understand. Since many colourful claims about |
13 Bitcoins float around in the mainstream media, it will be |
13 Bitcoins float around in the mainstream media, it will be |
14 instructive to re-examine such claims from a more technically |
14 instructive to re-examine such claims from a more technically |
15 informed vantage point. For example, it is often claimed that |
15 informed vantage point. For example, it is often claimed that |
16 Bitcoins are anonymous and free from any potential government |
16 Bitcoins are anonymous and free from any potential government |
17 meddling. It turns out that the first claim ignores a lot of |
17 meddling. It turns out that the first claim ignores a lot of |
18 research in de-anonymising social networks, and the second |
18 research in de-anonymising social networks, and the second |
19 underestimates the persuasive means a government has at their |
19 underestimates the persuasive means a government has at their |
20 disposal. Below I will follow the very readable explanations |
20 disposal. |
21 about Bitcoins from |
21 |
22 |
22 There are a lot of articles, blogposts and so on available |
23 \begin{center} |
23 about Bitcoins. Below I will follow closely the very readable |
24 \url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/}\smallskip\\ |
24 explanations from |
|
25 |
|
26 \begin{center} |
|
27 \url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/} \;\;and\smallskip\\ |
25 \url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html} |
28 \url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html} |
26 \end{center} |
29 \end{center} |
27 |
30 |
|
31 \noindent |
|
32 The latter also contains a link to a nice youtube video. |
28 |
33 |
29 Let us start with the question who invented Bitcoins? You |
34 Let us start with the question who invented Bitcoins? You |
30 could not make up the answer, but we actually do not know who |
35 could not make up the answer, but we actually do not know who |
31 is the inventor. All we know is that the first paper |
36 the inventor is. All we know is that the first paper |
32 |
37 |
33 \begin{center} |
38 \begin{center} |
34 \url{https://bitcoin.org/bitcoin.pdf} |
39 \url{https://bitcoin.org/bitcoin.pdf} |
35 \end{center} |
40 \end{center} |
36 |
41 |
37 \noindent is signed by Satoshi Nakamoto, which however is |
42 \noindent is signed by Satoshi Nakamoto, which however is |
38 likely only a pen name. There is a lot of speculation who |
43 likely only a pen name. There is a lot of speculation who |
39 could be the inventor, or inventors, but we simply do not |
44 could be the inventor, or inventors, but we simply do not |
40 know. This part of Bitcoins is definitely anonymous. The first |
45 know. This part of Bitcoins is definitely anonymous. The first |
41 Bitcoin transaction was made in January 2009. The rules in |
46 Bitcoin transaction was made in January 2009. The rules in |
42 Bitcoin are set up so that there will only be 21 Million |
47 Bitcoin are set up so that there will ever only be 21 Million |
43 Bitcoins with the maximum reached around year 2140. Contrast |
48 Bitcoins with the maximum reached around the year 2140. |
44 this with other fiat currencies where money can be printed |
49 Contrast this with traditional fiat currencies where money can |
45 almost at will. The smallest unit of a Bitcoin is called a |
50 be printed almost at will. The smallest unit of a Bitcoin is |
46 Satoshi which is the $10^{-8}$ part of a Bitcoin. Remember a |
51 called a Satoshi which is the $10^{-8}$th part of a Bitcoin. |
47 Penny is the $10^{-2}$ part of a Pound. |
52 Remember a Penny is the $10^{-2}$th part of a Pound. |
48 |
53 |
49 The two main cryptographic building blocks of Bitcoins are |
54 The two main cryptographic building blocks of Bitcoins are |
50 cryptographic hashing (SHA-256) and public-private keys using |
55 cryptographic hashing (SHA-256) and public-private keys using |
51 elliptic-curve encryption for digital signatures. Hashes are |
56 the elliptic-curve encryption scheme for digital signatures. |
52 used to generate `fingerprints' of data that ensures its |
57 Hashes are used to generate `fingerprints' of data that ensure |
53 integrity. Public-private keys are used for signatures. For |
58 integrity. Public-private keys are used for signatures. For |
54 example sending a message, say $msg$, together with the |
59 example sending a message, say $msg$, together with the |
55 encrypted version |
60 encrypted version |
56 |
61 |
57 \[ |
62 \[ |
58 msg, \{msg\}_{K^{priv}} |
63 msg, \{msg\}_{K^{priv}} |
59 \] |
64 \] |
60 |
65 |
61 \noindent allows everybody with access to the public key to |
66 \noindent allows everybody with access to the public key to |
62 verify the message came from the person who knew the private |
67 verify the message came from the person who knew the private |
63 key. Signatures are used in Bitcoins for verifying the |
68 key. Signatures are used in Bitcoins for verifying the |
64 addresses where the Bitcoins come from. Addresses in Bitcoins |
69 addresses where the Bitcoins are sent from. Addresses in |
65 are essentially the public keys. There are $2^{160}$ possible |
70 Bitcoins are essentially the public keys. There are $2^{160}$ |
66 addresses, which is such a vast amount that there is not test |
71 possible addresses, which is such a vast amount that there is |
67 for duplicates\ldots{}or already used addresses. |
72 not even a check for duplicates, or already used addresses. If |
68 |
73 you start with a random number to generate a public-private |
69 Traditional banking involves a central ledger which specifies |
74 key pair it is very unlikely that you step on somebody else's |
70 the current balance in each account, for example |
75 shoes. Compare this with email-addresses you ever wanted to |
|
76 register with, say, Googlemail, but which were always already |
|
77 taken. |
|
78 |
|
79 One main difference between Bitcoins and, say, traditional |
|
80 banking is that you do not have a place that records the |
|
81 balance on your account. Traditional banking involves a |
|
82 central ledger which specifies the current balance in each |
|
83 account, for example |
71 |
84 |
72 \begin{center} |
85 \begin{center} |
73 \begin{tabular}{l|r} |
86 \begin{tabular}{l|r} |
74 account & balance\\\hline |
87 account & balance\\\hline |
75 Alice & \pounds{10.01}\\ |
88 Alice & \pounds{10.01}\\ |
77 Charlie & -\pounds{1.23}\\ |
90 Charlie & -\pounds{1.23}\\ |
78 Eve & \pounds{0.00} |
91 Eve & \pounds{0.00} |
79 \end{tabular} |
92 \end{tabular} |
80 \end{center} |
93 \end{center} |
81 |
94 |
82 \noindent Bitcoins work differently in that there is no |
95 \noindent Bitcoins work differently in that there is no such |
83 central ledger, but a public record of all transactions. This |
96 central ledger, but instead a public record of all |
84 means spending money corresponds to sending messages of |
97 transactions ever made. This means spending money corresponds |
85 the very rough form |
98 to sending messages of the (rough) form |
86 |
99 |
87 \begin{center} |
100 \begin{equation} |
88 $\{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}}$ |
101 \{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}} |
89 \end{center} |
102 \end{equation} |
90 |
103 |
91 \noindent They are encrypted with Alice's private key such |
104 \noindent These are the transactions that are the only data |
92 that everybody, including Bob, can use Alice's public key |
105 that is ever stored (we will come to the precise details later |
93 $K^{pub}_{ALice}$ in order to verify the message came really |
106 on). The transactions are encrypted with Alice's private key |
|
107 such that everybody, including Bob, can use Alice's public key |
|
108 $K^{pub}_{Alice}$ for verifying that this message came really |
94 from Alice, or more precisely from the person who knows |
109 from Alice, or more precisely from the person who knows |
95 $K^{priv}_{Alice}$. The problem with such messages in a |
110 $K^{priv}_{Alice}$. |
96 distributed system is what happens if Bob receives 10, say, of |
111 |
97 these messages. Did Alice intend to send him 10 Bitcoins, or |
112 The problem with such messages in a distributed system is what |
98 did the message by Alice get duplicated by for example an |
113 happens if Bob receives 10, say, of these transactions. Did |
99 attacker re-playing a sniffed message. What is needed is |
114 Alice intend to send him 10 Bitcoins, or did the message get |
100 a kind of serial number for such messages. Meaning transaction |
115 duplicated by for example an attacker re-playing a sniffed |
101 messages look more like |
116 message? What is needed is a kind of serial number for such |
|
117 transactions. This means transaction messages look more like |
102 |
118 |
103 \begin{center} |
119 \begin{center} |
104 $\{\text{I, Alice, am giving Bob Bitcoin \#1234567.}\}_{K^{priv}_{Alice}}$ |
120 $\{\text{I, Alice, am giving Bob Bitcoin \#1234567.}\}_{K^{priv}_{Alice}}$ |
105 \end{center} |
121 \end{center} |
106 |
122 |
107 \noindent There are two problems that need to be solved. One is |
123 \noindent There are two difficulties, however, that need to be |
108 who is assigning serial numbers to bitcoins and also how can |
124 solved. One is who is assigning serial numbers to Bitcoins and |
109 Bob verify that Alice actually owns this Bitcoin to pay |
125 also how can Bob verify that Alice actually owns this Bitcoin |
110 him? In a system with a bank as trusted third-party, Bob |
126 to pay him? In a system with a bank as trusted third-party, |
111 could do the following: |
127 Bob could do the following: |
112 |
128 |
113 \begin{itemize} |
129 \begin{itemize} |
114 \item Bob asks the bank whether the Bitcoin with that serial |
130 \item Bob asks the bank whether the Bitcoin with that serial |
115 number belongs to Alice and Alice hasn’t already spent |
131 number belongs to Alice and Alice hasn’t already spent |
116 this Bitcoin. |
132 this Bitcoin. |
118 The bank updates the records to show that the Bitcoin |
134 The bank updates the records to show that the Bitcoin |
119 with that serial number is now in Bob’s possession and |
135 with that serial number is now in Bob’s possession and |
120 no longer belongs to Alice. |
136 no longer belongs to Alice. |
121 \end{itemize} |
137 \end{itemize} |
122 |
138 |
123 \noindent But banks would need to be trusted and would also be |
139 \noindent But for this banks would need to be trusted and |
124 an easy target for any government interference, for example. |
140 would also be an easy target for any government interference, |
125 Think of the early days of music sharing where the company |
141 for example. Think of the early days of music sharing where |
126 Napster was the single point of ``failure'' which was taken |
142 the company Napster was the single point of ``failure'' which |
127 offline by law enforcement. |
143 was taken offline by law enforcement. |
128 |
144 |
129 Bitcoin solves the problem of not being able to rely on a bank |
145 Bitcoin solves the problem of not wanting to rely on a bank by |
130 by making everybody the bank. Everybody who cares can have the |
146 making everybody the ``bank''. Everybody who cares can have |
131 entire transaction history starting with the first transaction |
147 the entire transactions history starting with the first |
132 made in January 2009. This history of transactions is called |
148 transaction made in January 2009. This history of transactions |
133 \emph{blockchain}. Bob can use his copy of the blockchain for |
149 is called \emph{blockchain}. Bob, for example, can use his |
134 determining whether Alice owned the Bitcoin and if yes |
150 copy of the blockchain for determining whether Alice owned the |
135 transmits the message to every other participant on the |
151 Bitcoin and if yes transmits the message to every other |
136 Bitcoin network. The blockchain looks roughly like a very long |
152 participant on the Bitcoin network. The blockchain looks |
137 chain of individual blocks |
153 roughly like a very long chain of individual blocks |
138 |
154 |
139 \begin{center} |
155 \begin{center} |
140 \includegraphics[scale=0.4]{../pics/bitcoinblockchain0.png} |
156 \includegraphics[scale=0.4]{../pics/bitcoinblockchain0.png} |
141 \end{center} |
157 \end{center} |
142 |
158 |
143 \noindent Each block contains a list of individual |
159 \noindent Each block contains a list of individual |
144 transactions. They are hashed so that the data in the |
160 transactions, called txn in the picture above, and also a |
145 transactions cannot be tampered with. This hash is the unique |
161 reference to the previous block, called prev. The data in a |
146 serial number of each block. Each block also contains a |
162 block (txn's and prev) is hashed so that the reference and |
147 reference of the previous block. Since this |
163 transactions in them cannot be tampered with. This hash is the |
148 previous-block-reference is also hashed, the whole chain is |
164 unique serial number of each block. Since this |
149 robust against tampering. We can check this by checking the |
165 previous-block-reference is also part of the hash, the whole |
150 entire blockchain whether the references and hashes are |
166 chain is robust against tampering. I let you think why this is |
|
167 the case. \ldots{}But does it eliminate all possibilities of |
|
168 fraud? |
|
169 |
|
170 We can check the consistency of the blockchain by checking the |
|
171 entire block\-chain whether the references and hashes are |
151 correctly recorded. I have not tried it myself, but it is said |
172 correctly recorded. I have not tried it myself, but it is said |
152 that with the current amount of data in the blockchain it |
173 that with the current amount of data (appr.~12GB) it takes |
153 takes roughly a day to check the consistency of the blockchain |
174 roughly a day to check the consistency of the blockchain on a |
154 on a ``normal'' computer. Fortunately this consistency test |
175 ``normal'' computer. Fortunately this ``extended'' consistency |
155 from the beginning usually only needs to be done once. |
176 check usually only needs to be done once. |
156 |
177 |
157 Recall I wrote earlier Bitcoins that do not maintain a ledger |
178 Recall I wrote earlier that Bitcoins do not maintain a ledger |
158 listing all the current balances in each account. |
179 listing all the current balances in each account. Instead they |
159 |
180 record only transactions. Therefore it is possible to extract |
|
181 from the blockchain a transaction graph that looks like the |
|
182 picture shown in Figure~\ref{txngraph}. Take for example the |
|
183 rightmost lower transaction from Charles to Emily. This |
|
184 transaction has as receiver the address of Emily and as the |
|
185 sender the address of Charles. In this way no Bitcoins can |
|
186 appear out of thin air (we will discuss later how Bitcoins are |
|
187 actually generated). If Charles did not have a transaction of |
|
188 at least the amount he wants to give Emily to his name |
|
189 (i.e.~send to an address with his public-private key) then |
|
190 there is no way he can make a payment to Emily. Equally, if |
|
191 now Emily wants to pay for a coffee, say, with the Bitcoin she |
|
192 received from Charles she can only make a transaction to |
|
193 forward the message she received. The only slight complication |
|
194 with is that incoming transactions can be combined in a |
|
195 transaction and ``outgoing'' Bitcoins can be split. For |
|
196 example in the leftmost upper transactions in |
|
197 Figure~\ref{txngraph} Fred makes a payment to Alice. But this |
|
198 payment (or transaction) combines the Bitcoins that were send |
|
199 by Jane to Fred and also by Juan to Fred. This allows you to |
|
200 ``consolidate'' your funds: if there was always only a way to |
|
201 split transactions, then the amounts would get smaller and |
|
202 smaller. But it is also important to be able to split the |
|
203 money from one or more incoming transaction to more than one |
|
204 receiver. Consider again the rightmost transactions in |
|
205 Figure~\ref{txngraph} and suppose Alice is a coffeeshop owner |
|
206 selling coffees for 1 Bitcoin. Charles received a transaction |
|
207 from Zack over 5 Bitcoins. How does he pay for the coffee? |
|
208 There is no real notion of change in the Bitcoin system. What |
|
209 Charles has to do instead is to make one single transaction |
|
210 with 1 Bitcoin to Alice and with 4 Bitcoins going back to |
|
211 himself. Which Charles can then use to give to Emily. |
|
212 |
|
213 \begin{figure}[t] |
160 \begin{center} |
214 \begin{center} |
161 \includegraphics[scale=0.4]{../pics/blockchain.png} |
215 \includegraphics[scale=0.4]{../pics/blockchain.png} |
162 \end{center} |
216 \end{center} |
|
217 \caption{Transaction graph that is implicitly recorded in the |
|
218 public blockchain.\label{txngraph}} |
|
219 \end{figure} |
|
220 |
|
221 Let us make another example. Let us assume Emily received 4 |
|
222 Bitcoins from Charles and independently has another |
|
223 transaction (not shown in the picture) that sends 6 Bitcoins |
|
224 to her. If she now wants to buy a coffee from Alice for 1 |
|
225 Bitcoin she has two possibilities. She could just forward the |
|
226 transaction from Charles over 4 Bitcoins to Alice splitted in |
|
227 such a way that Alice receives 1 Bitcoin and Emily sends the |
|
228 remaining 3 Bitcoins `back' to herself. In this case she would |
|
229 now be in the ``posession'' of two unspend Bitcoin |
|
230 transactions, one over 3 Bitcoins and the independent one over |
|
231 6 Bitcoins. Or, Emily could combine both transactions (one |
|
232 over 4 Bitcoins from Charles and the independent one over 6 |
|
233 Bitcoins) and then split this amount with 1 Bitcoin going to |
|
234 Alice and 9 Bitcoins going back to herself. |
|
235 |
|
236 I let you have time to let this concept of transactions sink |
|
237 in\ldots{}in the words of a famous 60ies Band: ``All you need |
|
238 is transactions''. There is no need for a central ledger and |
|
239 no need for an account balance from traditional banking. The |
|
240 closest what Bitcoin has to offer for a notion of a balance in |
|
241 a bank account are the unspend transaction that a person (that |
|
242 is public-private key address) received. That means |
|
243 transactions that can still be forwarded. |
|
244 |
|
245 Also consider the fact that whatever transaction is recorded |
|
246 in the blockchain is what will set the ``historical record''. |
|
247 If a transaction says 1 Bitcoin from address $A$ to address |
|
248 $B$, then this is what will be recorded. This is also how |
|
249 Bitcoins can actually get lost: if you forget your private key |
|
250 and you had just a message forwarded to you address of the |
|
251 public key, then bad luck: you will never be able to forward |
|
252 this message again, because you will not be able to form a |
|
253 valid message that sends this to somebody else (we will see |
|
254 the details of this later). But this is also a way how you can |
|
255 get robbed of your Bitcoins. An attacker might get hold of |
|
256 your private key and then quickly forward the Bitcoins in your |
|
257 name to an address the attacker controls. You have never again |
|
258 access to these Bitcoins, because for the Bitcoin system they |
|
259 are assumed to be spend. And remember with Bitcoins you cannot |
|
260 appeal to any higher authority. Once it is gone, it is gone. |
|
261 This is different with traditional banking where at least you |
|
262 can try to harass the bank to rollback the transaction. |
|
263 |
|
264 |
|
265 This brings us to back to problem of double spend. Say Bob is |
|
266 a merchant. How can he make sure that Alice does not cheat. |
|
267 She could for example send a transaction to Bob. But also to |
|
268 Charlie, or even herself. If Bob is also in the coffee |
|
269 business, he would potentially be cheated out of his money. |
|
270 The problem is how should people update their blockchain? |
|
271 You might end up with a picture like this |
|
272 |
|
273 \begin{center} |
|
274 \includegraphics[scale=0.3]{../pics/bitcoindisagreement.png} |
|
275 \end{center} |
|
276 |
|
277 \noindent Alice convinced some part of the ``world'' that she |
|
278 is still owner of the bitcoin and some other part of the |
|
279 ``world'' thinks its Bob's. How should such a disagreement be |
|
280 resolved? This is actually the main hurdle where Bitcoin |
|
281 really innovated. The answer is that Bob needs to convince |
|
282 ``enough'' people on the network that the transaction from |
|
283 Alice to him is legit. But what means enough in a distributed |
|
284 system? If Alice sets up network of a billion puppy identidies |
|
285 and whenever Bob tries to ask whether Alice is the rightful |
|
286 owner of the Bitcoin and Alice just send a transaction to him, |
|
287 the puppy network of identities just says yes. Bob would then |
|
288 give the coffee to Alice, but then for everybody else the |
|
289 |
|
290 |
|
291 |
163 |
292 |
164 \end{document} |
293 \end{document} |
165 |
294 |
166 bit coin |
295 bit coin |
167 https://bitcoin.org/bitcoin.pdf |
296 https://bitcoin.org/bitcoin.pdf |