\usepackage{../langs}

Bitcoins float around in the mainstream and not-so-mainstream

media, it will be instructive to re-examine such claims from a

more technically informed vantage point. For example, it is

often claimed that Bitcoins are anonymous and free from any

potential government meddling. It turns out that the first

claim ignores a lot of research in de-anonymising social

networks, and the second underestimates the persuasive means a

government has at its disposal. 

There are a lot of articles, blogposts, research papers

etc.~available about Bitcoins. Below I will follow closely the

very readable explanations from

\noindent The latter also contains a link to a nice youtube

video about the technical details behind Bitcoins.

know. This part of Bitcoins is definitely anonymous. The paper

above is from the end of 2008; the first Bitcoin transaction

was made in January 2009. The rules in Bitcoin are set up so

that there will ever only be 21 Million Bitcoins with the

maximum reached around the year 2140. Currently there are

already 11 Million Bitcoins mined. Contrast this with

traditional fiat currencies where money can be printed almost

at will. The smallest unit of a Bitcoin is called a Satoshi

which is the $10^{-8}$th part of a Bitcoin. Remember a Penny

is the $10^{-2}$th part of a Pound.

integrity (absence of tampering). Public-private keys are used

for signatures. For example sending a message, say $msg$,

together with the encrypted version

\noindent allows everybody with access to the corresponding

public key $K^{pub}$ to verify the message came from the

person who knew the private key. Signatures are used in

Bitcoins for verifying the addresses where the Bitcoins are

sent from. Addresses in Bitcoins are essentially the public

keys. There are $2^{160}$ possible addresses, which is such a

vast amount that there is not even a check for duplicates, or

already used addresses. If you start with a random number to

generate a public-private key pair it is very unlikely that

you step on somebody else's shoes. Compare this with the

email-addresses you always wanted to register with, say

Googlemail, but which are already taken.

One main difference between Bitcoins and traditional banking

is that you do not have a place that records the balance on

your account. Traditional banking involves a central ledger

which specifies the current balance in each account, for

example 

to sending messages of the (oversimplified) form 

\noindent These messages, called transactions, are the only

data that is ever stored in the Bitcoin system (we will come

to the precise details later on). The transactions are

encrypted with Alice's private key such that everybody,

including Bob, can use Alice's public key $K^{pub}_{Alice}$

for verifying that this message came really from Alice, or

more precisely from the person who knows $K^{priv}_{Alice}$. 

was taken offline by law enforcement. Bitcoins is more a

system like BitTorrent without a single central entity that

can be taken offline.

Bitcoin solves the problem of not being able to rely on a bank

by making everybody the ``bank''. Everybody who cares can have

Bitcoin he received, and if yes transmits the message to every

other participant on the Bitcoin network. The blockchain looks

the case?\ldots{}But does it actually eliminate all

possibilities of fraud?

We can check the consistency of the blockchain by checking

whether all the references and hashes are correctly recorded.

I have not tried it myself, but it is said that with the

current amount of data (appr.~12GB) it takes roughly a day to

check the consistency of the blockchain on a ``normal''

computer. Fortunately this ``extended'' consistency check

usually only needs to be done once. After that it only needs 

to be updated consistently.

record only transactions. While a current balance of an

account is not immediately available, it is possible to

extract from the blockchain a transaction graph that looks

like the picture shown in Figure~\ref{txngraph}. Take for

example the rightmost lower transaction from Charles to Emily.

This transaction has as receiver the address of Emily and as

the sender the address of Charles. In this way no Bitcoins can

received from Charles she can essentially only forward the

message she received. The only slight complication with this

setup in Bitcoins is that ``incoming'' Bitcoins can be

combined in a transaction and ``outgoing'' Bitcoins can be

split. For example in the leftmost upper transactions in

smaller. 

But in Bitcoins it is also important to have the ability to

split the money from one or more incoming transaction to

potentially more than one receiver. Consider again the

rightmost transactions in Figure~\ref{txngraph} and suppose

Alice is a coffeeshop owner selling coffees for 1 Bitcoin.

Charles received a transaction from Zack over 5 Bitcoins, say.

How does he pay for the coffee? There is no real notion of

change in the Bitcoin system. What Charles has to do instead

is to make one single transaction with 1 Bitcoin to Alice and

with 4 Bitcoins going back to himself, which then Charles can

use to give to Emily, for example.

Bitcoin, she has two possibilities. She could just forward the

remaining 3 Bitcoins ``back'' to herself. In this case she would

I think this is a good time for you to pause to let this

concept of transactions really sink in\ldots{}abusing the

words of a famous 60ies Band: With Bitcoins ``all you need is

transactions''. There is really no need for a central ledger

and no need for an account balance as familiar from

traditional banking. The closest what Bitcoin has to offer for

the notion of a balance in a bank account are the unspend

transaction that a person (more precisely a public-private key

address) received. That means transactions that can still be

forwarded. 

After the pause also consider the fact that whatever

transaction is recorded in the blockchain will be in the

``historical record'' for the Bitcoin system. If a transaction

says 1 Bitcoin goes from address $A$ to address $B$, then this

is what will be---$B$ has then the possibility to spend the

corresponding Bitcoins, whether the transaction was done

fraudulently or not. There is no exception to this rule.

Interestingly this is also how Bitcoins can get lost: One

possibility is that you send Bitcoins to an address for which

nobody has generated a private key. For example by a typo in

the address field---bad luck for fat

fingers.\footnote{\url{http://en.wikipedia.org/wiki/Typographical_error}}

The reason is that nobody has a private key for this erroneous

address and consequently cannot forward the transaction

anymore. Another possibility is that you forget your private

key and you had messages forwarded to your address

corresponding to your the public key. In this case also bad

luck: you will never be able to forward this message again,

because you will not be able to form a valid message that

sends this to somebody else (we will see the details of this

later). But this is also a way how you can get robbed of your

Bitcoins. By old-fashioned hacking-into-a-computer crime, for

example, an attacker might get hold of your private key and

then quickly forward the Bitcoins that are in your name to an

address the attacker controls. You will never have again

are assumed to be spent. And remember with Bitcoins you cannot

can try to harass the bank to roll back the transaction. 

a merchant. How can he make sure that Alice does not cheat?

She could for example send a transaction to Bob. But also

forward the ``same'' transaction to Charlie, or even herself.

If Alice manages to get the second transaction into the

blockchain, Bob will be cheated out of his money. The problem

in such conflicting situations is how should the network

update their blockchain? You might end up with a picture like

this

\includegraphics[scale=0.4]{../pics/bitcoindisagreement.png}

\noindent Alice convinced some part of the ``world'' that she

is still owner of the bitcoin and some other part of the

``world'' thinks its Bob's. How should such a disagreement be

resolved? This is actually the main hurdle where Bitcoin

really innovated. The answer is that Bob needs to convince

``enough'' people on the network that the transaction from

Alice to him is legit. However what does ``enough'' mean in a

distributed system? If Alice sets up network of a billion

puppy identities and whenever Bob tries to convince, or

validate, that he is the rightful owner of the Bitcoin, the

puppy identities agree. Bob would then have no reason to not

give Alice her coffee. But behind his back she has convinced

everybody else on the network that she is still the rightful

owner of the Bitcoin. After being outvoted, Bob would be a tad

peeved. 

The reflex action of a security engineer would be to make the

process of validating as cheap as possible. The idea is that

Bob will get enough peers to agree with him that he is the

rightful owner. But such a solution has always the limitation

of that Alice could set up an even bigger network of puppy

identities. So the really cool idea of Bitcoin is to go into

the other direction of making the process of transaction

validation (artificially) as expensive as possible, but reward

people for helping with the validation. This is really a novel

and counterintuitive idea that makes the whole system work so

beautifully.

\subsubsection*{Proof-of-Work}

In order to make the process of transaction validation

difficult, Bitcoin uses a kind of puzzles. Solving the puzzles

is called mining where whoever solves a puzzle will be awarded

some bitcoins. At the beginning of Bitcoins this was 50

Bitcoins, but the rules of Bitcoin are set up such that this

amount halves every 210,000 transactions or so. Currently you

will be awarded 25 Bitcoins for solving a puzzle. Because the

amount will halve again and then later again and again, around

2140 it will go below the level of 1 Satoshi. In that event no

new Bitcoins will ever be created again and the amount stays

fixed. There will be still an incentive to help with

validating transactions, because there is the possibility in

Bitcoins to award a transaction fee to whoever solves a

puzzle. At the moment this fee is usually set to 0, since the

incentive for miners is the currently 25 Bitcoins that are

awarded for solving puzzles. 

What are the puzzles that miners have to solve? Recall that

Bitcoins uses the hash-function SHA-256. The puzzle is roughly

as follows: Given a string, say \code{"Hello, world!"}, what

is the salt so the hash starts with a long run of zeros?

Suppose we call the hash function \code{h}, then we could try 

the salt \code{0} as follows:

\begin{quote}

\code{h("Hello, world!0") =}\\

\mbox{}\quad\footnotesize\pcode{1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64}\\

\end{quote}

\noindent OK this does not have any zeros at all. We could 

next try the salt \code{1}: 

\begin{quote}

\code{h("Hello, world!1") =}\\

\mbox{}\quad\footnotesize\pcode{e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8}\\

\end{quote}

%\begin{center}

%\begin{tabular}{@{}l@{}}

%\footnotesize\code{h("Hllo, world!1")}\\ 

%\;\;\scriptsize\code{%\ldots\\

%\footnotesize\code{h("Hello, world!4250")}\\ 

%\;\;\scriptsize\code{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}

%\end{tabular}

%\end{center}