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