that there will only ever be 21 Million Bitcoins with the

already 11 Million Bitcoins in `existence'. Contrast this with

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

cryptographic hashing functions (SHA-256) and public-private

keys using the elliptic-curve encryption scheme for digital

signatures. Hashes are used to generate `fingerprints' of data

that ensure integrity (absence of tampering). Public-private

keys are used for signatures. For example sending a message,

say $msg$, together with the encrypted version

is that you do not have a place, or places, that record the

balance on your account. Traditional banking involves a

central ledger which specifies the current balance in each

account, for example 

account owner & balance\\\hline

encrypted with Alice's private key so that everybody,

The problem with such messages in a distributed system is that

what happens if Bob receives 10, say, of these transactions.

Did Alice intend to send him 10 Bitcoins, or did the message

get duplicated by for example an attacker re-playing a sniffed

solved with serial numbers. One is who is assigning serial

numbers to Bitcoins and also how can Bob verify that Alice

actually owns this Bitcoin to pay him? In a system with a bank

as trusted third-party, Bob could do the following:

Bitcoin he received, and if she did, he transmits the message

that he owns it now to every other participant on the Bitcoin

network. An illustration of a three-block segment of the

blockchain is (simplified) as follows

\begin{equation}

\label{segment}

\end{equation}

\noindent The chain grows with time. Each block contains a

list of individual transactions, written txn in the picture

above, and also a reference to the previous block, written

prev. The data in a block (txn's and prev) is hashed so that

the reference and transactions in them cannot be tampered

with. This hash is the unique serial number of each block.

Since this previous-block-reference is also part of the hash,

the whole chain is robust against tampering. I let you think

why this is the case?\ldots{}But does it actually eliminate

all possibilities of fraud?

check the consistency of the blockchain on a normal computer.

Fortunately this ``extended'' consistency check usually only

needs to be done once. Afterwards the blockchain only needs to

be updated consistently.

Recall I wrote earlier that Bitcoins do not maintain a ledger,

which lists all the current balances in each account. Instead

only transactions are recorded. While a current balance of an

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

rectangle represents a single transaction. 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

Figure~\ref{txngraph}, Fred makes a payment to Alice. But this

``consolidate'' your funds: if it were only possible to split

transactions, then the amounts would get smaller and smaller. 

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

\emph{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.

Let us consider another example. Suppose Emily received 4

Bitcoins from Charles and independently received another

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

transaction from Charles over 4 Bitcoins to Alice split in

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

would now be in the ``posession'' of two unspend Bitcoin

concept of transactions really sink in\ldots{}You should see

that 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 transactions that a

person (more precisely a public-private key address) received.

That means transactions that can still be forwarded. 

nobody has generated a private key, for example because of a

typo in the address field---bad luck for fat

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

in the Bitcoin system. 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 the

corresponding public key. Also in this case 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 again have access to these

Bitcoins, because for the Bitcoin system they are assumed to

be spent. And remember with Bitcoins you cannot appeal to any

higher authority. Once the Bitcoins are gone, they are gone.

This is much different in traditional banking where at least

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

This brings us to back to problem of double spend. Suppose Bob

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

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

\noindent where Alice convinced some part of the ``world''

that she is still the owner of the Bitcoin and some other part

of the ``world'' thinks it's 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. 

What does, however, ``enough'' mean in a distributed system?

If Alice sets up a network of a billion, say, puppy identities

and whenever Bob tries to convince, or validate, that he is

the rightful owner of the Bitcoin, then the puppy identities

agree. Bob would then have no reason to not give Alice her

coffee. But behind his back, however, she has convinced

The reflex reaction to such a situation would be to make the

process of validating a transaction as cheap as possible. The

intention 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 Alice setting up an even bigger network of

puppy identities. The really cool idea of Bitcoin is to go

into the other direction of making the process of transaction

and counterintuitive idea that makes the whole system of

Bitcoins work so beautifully.

\subsubsection*{Proof-of-Work Puzzles}

is called \emph{Bitcoin mining}, where whoever solves a puzzle

will be awarded some Bitcoins. At the beginning this was 50

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

event no new Bitcoins will ever be created again and the

amount of Bitcoins stays fixed. There will be still an

incentive to help with validating transactions, because there

is the possibility in Bitcoins to offer 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 25 Bitcoins that

are currently awarded for solving puzzles. 

What do the puzzles that miners have to solve look like? The

puzzles can be illustrated roughly as follows: Given a string,

say \code{"Hello, world!"}, what is the salt so that the hash

starts with a long run of zeros? Let us look at a concrete

example. Recall that Bitcoins use the hash-function SHA-256.

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

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

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

\end{quote}

\noindent Again this hash value does not contain any leading 

zeros. We could now try out every salt until we reach

\begin{quote}

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

\mbox{}\quad\footnotesize\pcode{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}

\noindent where we have four leading zeros. If four zeros are

enough, then the puzzle would be solved with this salt. The

point is that we can very quickly check whether a salt solves

a puzzle, but it is hard to find one. Latest research suggest

it is an NP-problem. If we want the output hash value to begin

with 10 zeroes, say, then we will, on average, need to try

$16^{10} \approx 10^{12}$ different salts before we find a

suitable one. In Bitcoins the puzzles are not solved according

to how many leading zeros a has-value has, but rather whether

it is below a \emph{target}. The hardness of the puzzle can

actually be controlled by changing the target according to the

available computational power available. I think the

adjustment of the hardness of the problems is done every two

weeks. I am not sure whether this is an automatic process. The

aim of the adjustment is that on average the Bitcoin network

will most likely solve a puzzle within 10 Minutes. 

\begin{center}

\includegraphics[scale=0.37]{../pics/blockchainsolving.png}

\end{center}

\noindent It could be solved quicker, but equally it could 

take longer, but on average after 10 Minutes somebody on the 

network will have found a solution. 

Remember that the puzzles are a kind of proof-of-work that

make the validation of transactions artificially expensive.

The validation and the derivation of the puzzle is done as 

follows:

\begin{equation}

\includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png}

\label{unconfirmed}

\end{equation}

\noindent There are some unconfirmed transactions. Choosing

some of them, the miner (i.e.~the person/computer that tries

to solve a puzzle) will form a putative block to be added to

the blockchain. This putative block will contain the

transactions and the reference to the previous block. The

serial number of such a block is simply the hash of all the

data. The puzzle can then be stated as the ``string''

corresponding to the block and which salt is needed in order

to have the hashed value being below the target. Other miners

will choose different transactions and therefore work on a 

slightly different putative block and puzzle.

The intention of the proof-of-work puzzle is that the

blockchain is at every given moment nicely linearly ordered,

see the picture shown in \eqref{unconfirmed}. If we don’t have

such a linear ordering at any given moment then it may not be

clear who owns which Bitcoins. Assume a miner David is lucky

and finds a suitable salt to confirm the transactions. Should

he celebrate? Not yet. Typically the blockchain will look as

follows

\begin{center}

\includegraphics[scale=0.65]{../pics/block_chain1.png}

\end{center}

\noindent But every so often there will be a fork

\begin{center}

\includegraphics[scale=0.65]{../pics/block_chain_fork.png}

\end{center}

\noindent What should be done in this case? The tie is broken

if another block is solved, like so:

\begin{center}

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

\end{center}

\noindent The rule in Bitcoins is: If a fork occurs, people on

the network keep track of all forks. But at any given time,

miners only work to extend whichever fork is longest in their

copy of the block chain. Why should miners work on the longest

fork? Well their incentive is to mine Bitcoins. If somebody

else already solved a puzzle, then it makes more sense to work

on a new puzzle and obtain the Bitcoins for solving that

puzzle. Note that whoever solved a puzzle on the ``loosing''

fork will actually not get any Bitcoins as reward. Tough luck.

\subsubsection*{Alice against the Rest of the World}

Let is see how the blockchain and the proof-of-work puzzles

avoid the problem of double spend. If Alice wants to cheat

Bob she would need to pull off the following ploy:

\begin{center}

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

\end{center}

\noindent Alice makes a transaction to Bob for paying, for

example, for an online order. This transaction is confirmed,

or validated, in block 2. Bob ships the goods around block 4.

In this moment, Alice needs to get into action and try to

validate the fraudulent transaction to herself instead. 

\begin{center}

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

\end{center}

\noindent At this moment she is in a race against all the

computing power of the ``rest of the world''. She has to solve

the puzzles one by one, because the hash of a block is

determined by all the data in the previous has. She might be

very lucky to solve one puzzle for a block before the rest of

the world, but to be lucky many times is very unlikely. In

order to raise the bar for Alice, merchants accepting Bitcoin

use the following rule of thumb: A transaction is

``confirmed'' if (1) it is part of a block in the longest

fork, and (2) at least 5 blocks follow it in the longest fork.

In this case we say that the transaction has ``6