l23-bitcoin.html

<h1>6.824 2015 Lecture 23: Bitcoin</h1>

<p><strong>Note:</strong> These lecture notes were slightly modified from the ones posted on the
6.824 <a href="http://nil.csail.mit.edu/6.824/2015/schedule.html">course website</a> from 
Spring 2015.</p>

<h2>Bitcoin</h2>

<ul>
<li>an electronic currency system</li>
<li>has a technical side and a financial, economic, social side</li>
<li>maybe the 1st thing to ask: is it trying to do something better? is there a
problem it solves for us?</li>
<li>online payments use credit cards, why not just use them?
<ul>
<li>Pluses:
<ul>
<li>They work online</li>
<li>Hard for people to steal my credit card (there are laws about how credit
card companies work so that if your number is stolen, you are protected)</li>
</ul></li>
<li>Good/Bad:
<ul>
<li>Customer service # on the back allows you to reverse charges
<ul>
<li>this can prevent or create fraud</li>
</ul></li>
<li>tied to some country's currency</li>
</ul></li>
<li>Minuses
<ul>
<li>No way for me as a customer or a merchant to independently verify anything
about a credit card transaction: do you have money, is the CC # valid?
<ul>
<li>it can be good if you don't want people finding out how much money
you have</li>
</ul></li>
<li>relies on 3rd parties: great way to charge fees on everything</li>
<li>3% fees</li>
<li>settling time is quite long (merchants are not sure they are getting their
money until after one month)</li>
<li>pretty hard to become a credit card merchant
<ul>
<li>credit card companies take a lot of risk by sending money to merchants who
might not send products to customers, resulting in the credit card
company having to refund customers</li>
</ul></li>
</ul></li>
</ul></li>
<li>For Bitcoin:
<ul>
<li>no 3rd parties are needed (well, not really true anymore)</li>
<li>fees are much smaller than 3%</li>
<li>the settling time is maybe 10 minutes</li>
<li>anyone can become a merchant</li>
</ul></li>
<li>Bitcoin makes the sequence of transactions verifiable by everyone and agree
on it <code>=&gt;</code> no need to rely on 3rd parties</li>
</ul>

<h2>OneBit</h2>

<ul>
<li>simple electronic money system</li>
<li>it has one server called OneBank</li>
<li>each user owns some coins</li>
</ul>

<p>Design:</p>

<pre><code>OneBank server
</code></pre>

<ul>
<li>onebit xction:
<ol>
<li>public key of new owner</li>
<li>a hash of the last transfer record of this coin </li>
<li>a signature done over this record by the private key of last owner</li>
</ol></li>
<li>bank keeps the list of transactions for each coin</li>
<li><code>x</code> transfer the coin to <code>y</code></li>
<li><code>[T7: from=x, to=y; hash=h(prev tx); sig_x(this)]</code></li>
<li><code>y</code> transfers the coin to <code>z</code>, gets a hamburger from McDonalds</li>
<li><code>[T8: from y, to=z; hash=h(T7); sig_y(this)]</code></li>
<li>what can go wrong?
<ul>
<li>if someone transfers a coin to <code>z</code> it seems very unlikely that anyone else
other than <code>z</code> can spend that coin: because no one else can sign a new
transaction with that coin since they don't have <code>z</code>'s private key</li>
</ul></li>
<li>we have to trust one bank to not let users double spend money
<ul>
<li><code>y</code> can also buy a milkshake from Burger King with that same coin if the bank
helps him</li>
<li><code>[T8': from y, to=q'; hash=h(T7); sig_y(this)]</code></li>
<li>the bank can show T8 to McDonalds and T8' to Burget King</li>
<li>(I love free food!)</li>
<li>as long as McDonalds and Burger King don't talk to each other and verify
the transaction chain, they won't detect it</li>
</ul></li>
</ul>

<h2>Bitcoin block chain</h2>

<ul>
<li>bitcoin has a single block chain</li>
<li>many server: more or less replicas, have copy of entire block chain</li>
<li>each block in the block chain looks like this:
<ul>
<li>hash of previous block</li>
<li>set of transactions</li>
<li>nonce</li>
<li>current time</li>
</ul></li>
<li>xactions have two stages
<ul>
<li>first it is created and sent out to the network</li>
<li>then the transaction is incorporated into the block chain</li>
</ul></li>
</ul>

<h3>How are blocks created? Mining</h3>

<p>All of the peers in the bitcoin network try to create the next block:</p>

<ul>
<li>each peer takes all transactions that have arrived since the previous block
was created and try to append a new block with them</li>
<li>the rules say that a hash of a block has to be less than a certain number
(i.e. it has a # of leading of zeros, making it hard to find)</li>
<li>each of the bitcoin peers adjust the <code>nonce</code> field in the block until they
get a hash with a certain # of leading zeros</li>
<li>the point of this is to make it expensive to create new blocks
<ul>
<li>for a single computer it might take months to find such a nonce</li>
</ul></li>
<li>the # of leading zeros is adjusted so that on average it takes 10 minutes for
a new block to be added
<ul>
<li>clients monitor the <code>currentTime</code> field in the last 5 transactions or so
and if they took to little time, they add another zero to # of target zeros
<ul>
<li>everyone obeys the protocol because if they don't the others will either
reject their block (say if it has the wrong # of zeros or a wrong timestamp)</li>
</ul></li>
</ul></li>
</ul>

<h3>The empty block chain</h3>

<ul>
<li>"In the beginning there was nothing, and then Satoshi created the first block."</li>
<li>"And then people started mining additional blocks, with no transactions."</li>
<li>"And then they got mining reward for each mined block."</li>
<li>"And that's how users got Bitcoins."</li>
<li>"And then they started doing transactions."</li>
<li>"And then there was light."</li>
</ul>

<h3>What does it take to double spend</h3>

<p>If a tx is in the block chain, can the system double spend its coins?</p>

<ul>
<li>forking the block chain is the only way to do this</li>
<li>can the forks be hidden for long?  </li>
<li>if forks happens, miners will pick either one and continue mining</li>
<li>when a fork gets longer, everyone switches to it
<ul>
<li>if they stay on the shorter fork, they are likely to be outmined by the others
and waste work, so they will have incentive to go on the longer one</li>
<li>the tx's on the shorter fork get incorporated in the longer one</li>
<li>committed tx's can get undone => people usually wait for a few extra blocks
to be created after a tx's block</li>
</ul></li>
<li>this is where the 51% rule comes in: if 51% of the computing power is honest
the protocol works correctly</li>
<li>if more than 51% are dishonest, then they'll likely succeed in mining anything
they want</li>
<li>probably the most clever thing about bitcoin: as long as you believe than more
than half the computing power is not cheating, you can be sure there's no double
spending</li>
</ul>

<h3>Good and bad parts of design</h3>

<ul>
<li>(+) publicly verifiable log</li>
<li>(-) tied to a new currency and it is very volatile
<ul>
<li>lots of people don't use it for this reason</li>
</ul></li>
<li>(+/-) mining-decentralized trust</li>
</ul>

<p>Hard to say what will happen:</p>

<ul>
<li>we could be all using it in 30 years</li>
<li>or, banks could catch up, and come up with their own verifiable log design</li>
</ul>