80 COMMUNICATIONS OF THE ACM | APRIL 2016 | VOL. 59 | NO. 4
the combined computing power of all the other participants
of the protocol. Hence, for example, the sybil attack does not
work, as creating a lot of fake identities in the network does
not help the adversary. In a moment we will explain how this
is implemented, but let us first describe the functionality of
the trusted party that is emulated by the users.
One of the main problems with digital currencies is potential double spending: if coins are just strings of bits, then the
owner of a coin can spend it multiple times. Clearly, this risk
could be avoided if the users had access to a trusted ledger
with the list of all the transactions. In this case, a transaction
would be considered valid only if it is posted on the ledger.
For example, suppose the transactions are of a form: “user A
transfers x Bitcoins to user B.” In this case, each user can verify
if A really has x Bitcoins (i.e., she received it in some previous
transactions) and she did not spend it yet. The functionality
of the trusted party emulated by the Bitcoin network does precisely this: it maintains a full list of the transactions that happened in the system. The format of Bitcoin transactions is in
fact more complex than in the example above. Since it is of a
special interest for us, we describe it in more detail in Section
2. 1. However, for the sake of simplicity, we omit the features
of Bitcoin that are not relevant to our work such as transaction
fees or how the coins are created.
The Bitcoin ledger is in fact a chain of blocks (each block
contains transactions) that all the participants are trying to
extend. The parameters of the system are chosen in such a way
that an extension happens on average once each 10 min. The
idea of the block chain is that the longest chain C is accepted
as the proper one and appending a new block to the chain
takes nontrivial computation. As extending the block chain
or creating a new one is very hard, all users will use the same,
original block chain. Speaking in more detail, this construction prevents double spending of transactions. If a transaction is contained in a block Bi and there are several new blocks
after it, then it is infeasible for an adversary with less than a
half of the total computational power of the Bitcoin network
to revert it—he would have to mine a new chain C′ bifurcating
from C at block Bi− 1 (or earlier), and C′ would have to be longer
than C. The difficulty of that grows exponentially with number of new blocks on top of Bi. In practice, transactions need
10–20 min for reasonably strong confirmation and 60 min ( 6
blocks) for almost absolute certainty that they are irreversible.
To sum up, when a user wants to pay somebody in Bitcoins,
he creates a transaction and broadcasts it to other nodes
in the network. They validate this transaction, send it further, and add it to the block they are mining. When some
node solves the mining problem, it broadcasts its block to
the network. Nodes obtain a new block, validate transactions in it and its hash, and accept it by mining on top of it.
The presence of the transaction in the block is a confirmation of this transaction, but some users may choose to wait
for several blocks to get more assurance. In our protocols,
we assume that there exists a maximum delay Tmax between
broadcasting the transaction and its confirmation and that
every transaction once confirmed is irreversible.
2. 1. Bitcoin transactions
In contrast to the classical banking system, Bitcoin is based
on transactions instead of accounts. A user A has some Bitcoins
if in the system there are unredeemed transactions for which
he is a recipient. Each transaction has some value (number of
Bitcoins which is being transferred) and a recipient address.
An address is simply a public key pk. Normally, every such key
has a corresponding private key sk known only to one user—
that user is the owner of the address pk. The private key is used
for signing (authorizing) the transactions, and the public key
is used for verifying the signatures. Each user of the system
needs to know at least one private key of some address, but
this is simple to achieve since the pairs (sk, pk) can be eas-
ily generated offline. We will frequently denote the key pairs
using capital letters (e.g., A) and refer to the private key and
the public key of A by
A.sk and
A.pk, respectively.
Simplified version. We first describe a simplified version
of Bitcoin and then show how to extend it to obtain the description of the real Bitcoin. Let (
A.sk,
A.pk) and (
B.sk,
B.pk)
be the key pairs belonging to users A and B, respectively.
In our simplified view, a transaction describing the fact that
an amount υ (called the value of a transaction) is transferred
from an address
A.pk to an address
B.pk has the form
Tx = ( y, υ,
B.pk, sig), where y is an index of a previous transaction Ty, and sig is a signature computed using sender’s secret
key
A.sk on the whole transaction excluding the signature
itself (i.e., on ( y, υ,
B.pk)). We say that
B.pk is the recipient
of Tx, and that the transaction Ty is an input of the transaction Tx, or that Ty is redeemed by Tx. More precisely, the meaning of Tx is that the amount υ of money transferred to
A.pk in
transaction Ty is transferred further to
B.pk. The transaction
Tx is valid only if ( 1)
A.pk was a recipient of the transaction
Ty, ( 2) the value of Ty was equal to υ, ( 3) the transaction Ty
has not been redeemed earlier, and ( 4) the signature of A is
correct. All these conditions can be verified publicly.
We will present the transactions as boxes. The redeeming
of transactions will be indicated with arrows with the value of
the transaction. For example, a transaction Tx = ( y, υ,
B.pk, sig),
which transfers υ Bitcoins from A to B, is depicted in Figure 1(a).
The first important generalization of this simplified system is that a transaction can have several “inputs” meaning
that it can accumulate money from several past transactions
Ty1, .. . , Ty. Let A1, . .. , A be the respective key pairs of the
recipients of those transactions. Then a multiple-input transaction has the following form: Tx = ( y1, . . . , y, υ,
B.pk, sig1, . . . ,
sig), where each sigi is a signature computed using key
Ai.sk on the whole message excluding the signatures. The
result of such transaction is that
B.pk gets the amount υ, provided it is equal to the sum of the values of the transactions
Ty1, .. . , Ty. This happens only if none of these transactions
has been redeemed before, and all the signatures are valid.
Each transaction can also have several outputs, which is a
way to divide money between several users or get change,
but we do not use this feature in our protocols.
A more detailed version. The real Bitcoin system is significantly more sophisticated than what is described above. First
of all, there are some syntactic differences, the most important for us being that each transaction Tx is identified not by its
index, but by the hash of the whole transaction, H(Tx). Hence,
from now on, we will assume that x = H(Tx). Moreover, each
transaction can have a time-lock t that tells at what time the