Bitcoin (2008)

Technical Problem #1: Transferring Physical Money

Removing the trusted 3rd-party would seem to require a world where the buyer could transfer physical money to the seller. But this is often impractical. First, for small amounts of money, the fixed shipping costs could be impractical. A current US postage stamp is 0.49 USD, which is about 50% of the cost of a 0.99 USD iTunes song. Second, the time taken for payment to reach the seller is often on the order of the time taken for the seller’s product to reach the buyer. This means that if the seller were to wait until receiving payment, it would effectively double the total transaction time. This problem could be fixed by having both the buyer and the seller ship simultaneously, but that exposes the seller to the risk of buyer fraud. Third, sending actual physical money exposes the buyer to both the risk of theft in transit and the risk of seller fraud. The risk of theft in transit can be reduced by introducing another trusted 3rd-party, in this case USPS, by converting the buyer’s money into a USPS money order. The risk of seller fraud can be reduced by choosing buyer-vetted sellers, which increases prices by reducing competition, and by limiting the maximum purchase to an amount that the buyer can afford to lose, which increases prices by incurring opportunity costs.

From the previous paragraph, most may conclude that it is simply faster and safer to utilize trusted 3rd-parties for eCommerce.

Technical Problem #2: Detecting Double Spending in Digital Money

The first technical problem focused on a buyer transferring physical money directly to a seller. The second technical problem focuses on a buyer transferring digital money directly to a seller. What would this digital money look like and why doesn’t it exist today (in 2008)?

It is possible to create a digital coin (also called a digital token) by using public key cryptography. Here is the definition of a coin, as expressed in Python, using the description from the paper.

 1 class Coin:
 2     """Example of a digital coin, as described in the paper.
 3 
 4     NOTE: This is my own interpretation of the paper and most likely does
 5     not correspond with Bitcoin or any other actual cryptocurrency.
 6     """
 7     def __init__(self, first_owner_pubkey, first_owner_privkey):
 8         """Create a new coin, using the public and private keys of the
 9         original owner."""
10         self.transactions = [{
11             'owner_pubkey': first_owner_pubkey
12             'signature': first_owner_privkey.sign(hash(first_owner_pubkey))
13         }]
14     def transfer(self, new_owner_pubkey, current_owner_privkey):
15         """Transfer this coin to a new owner."""
16         prev_transaction = self.transactions[-1]
17         self.transactions.append({
18             'owner_pubkey': new_owner_pubkey
19             'signature': current_owner_privkey.sign(hash(prev_transaction + prev_transaction.owner_pubkey))
20         })
21     def verify(self):
22         """Verify that this coin has a valid chain of ownership."""
23         prev_transaction = None
24         for transaction in self.transactions:
25             if prev_transaction is None:
26                 prev_transaction = transaction
27                 continue
28             prev_transaction.owner_pubkey.verify(transaction.signature)
29             prev_transaction = transaction

A coin is a list of transactions, where each transaction represents the transfer of ownership of the coin to a new owner. Nakamoto uses the term transaction, but in this context, it may be better to use a term such as transference. Anyone can verify that the coin was transferred properly by walking the list of transactions from beginning to end, and verifying the signature stored in each transaction using the public key stored in the previous transaction.

With this definition of a coin firmly established, Nakamoto explains the technical problem of double spending. Double spending occurs when an owner, Oscar, makes a copy of his coin, and transfers copy “A” to Alice and copy “B” to Bob (without telling Alice about Bob’s coin and without telling Bob about Alice’s coin). In order to prevent chaos, it is imperative that if double spending occurs, that it is at least detected. But the only way to ensure that double spending is detected is to observe all transactions across all coins in the economy. Nakamoto mentions that previous solutions have proposed a trusted 3rd-party to be the one to observe and sanction all transactions. But this proposed solution does not solve the original problem of seeking to avoid the use of trusted 3rd-parties.

Timestamp Server

First, Nakamoto defines a traditional timestamp service that takes a block of data as input and produces a timestamp as output. The timestamp proves that the block of data existed prior to the creation of the timestamp, but does not say when the block of data was actually created (in terms of real human time). In fact, the “timestamp” itself is the output of a hash function and does not correspond to real human time. But the timestamp can be associated with real human time by publishing the timestamp. Here is the definition of a timestamping service, as expressed in Python, using the description from the paper.

 1 class TimestampService:
 2    """Example of a timestamp service, as described in the paper.
 3 
 4    NOTE: This is my own implementation of a timestamp service and most
 5          likely does not correspond with any actual timestamp service.
 6    """
 7    def __init__(self):
 8        """Create a new (empty) timestamp service."""
 9        self.blockchain = []
10        self.hashchain = []
11    def add_block(self, block):
12        """Add a new block to the blockchain."""
13        self.blockchain.append(block)
14        if len(self.hashchain) == 0:
15            self.hashchain.append(hash(block))
16        else:
17            self.hashchain.append(self.hashchain[-1] + hash(block))
18    def get_timestamp(self):
19        """Return the most recent hash from the hashchain."""
20        if len(self.hashchain) == 0:
21            return None
22        return self.hashchain[-1]

So how does this timestamp service solve the double spending problem? In my opinion, Nakamoto is not so clear on this point. I could imagine that blocks could contain coins. By timestamping a block containing a coin, one is proving that Alice is the first recipient of a given coin, and not Bob. And from the previous section, it is enough to prove the first recipient in order to solve the double spending problem.

So far, all is well. But wait! Who runs the timestamp service? This traditional solution does not work for our needs because it requires a trusted 3rd-party.

Proof-of-Work

What is proof-of-work? Sometimes one would like to control access to a shared resource to prevent abuse of that resource. Dwork and Naor (1992) [3] presented a scheme where if Alice wants to access a shared resource, she is required to “pay” for access by performing some busywork. Access to the resource is then contingent on Alice’s ability to prove that she has in fact done this busywork. If Alice wishes to submit some message x to the shared resource, then the busywork takes the form of computing a moderately hard function y = f(x). Alice then submits both the message and the proof-of-work together (x, y). Principals agree not to accept messages without valid proofs-of-work. Bob can validate Alice’s proof-of-work by computing y’ = f(x) and verifying that y = y’. As an optimization, the moderately hard function f(x) can be chosen so that checking y is much faster than computing y.

Nakamoto describes a particular proof-of-work function f(x) that involves searching for an input x where the hash of that input y = f(x) begins with a particular number k ≥ 1 of zero bits, which gets exponentially harder with k. In order to keep up with Moore’s law over time, the parameter k is chosen (increased?) automatically so that a desired number of blocks are created each hour.

Distributed Timestamp Service

In my opinion, Nakamoto does not present this section of the paper very clearly. Nakamoto is describing the design of a distributed timestamp service where proof-of-work is required to timestamp a block, i.e., to add a block to the blockchain. The key is that all of the principals agree on how to verify that a block has been timestamped correctly. All principals possess a complete copy of the blockchain. Here is the definition of a distributed timestamping service, as expressed in Python, using the description from the paper.

 1 class DistributedTimestampService:
 2    """Example of a distributed timestamp service, as described in the paper.
 3 
 4    NOTE: This is my own implementation of a distributed timestamp service
 5          and most likely does not correspond with any actual timestamp service.
 6    """
 7    def __init__(self, k):
 8        """Create a new (empty) distributed timestamp service."""
 9        self.k = k
10        self.blockchain = []
11    def add_block(self, block):
12        """Add a new block to the blockchain."""
13        block.prev_hash = 0
14        if len(self.blockchain) > 0:
15            block.prev_hash = hash(self.blockchain[-1])
16        block.N = 0  # start with random number?
17        while True:
18            block.N += 1
19            if bin(hash(block))[2:2+self.k] == 0:
20                self.blockchain.append(block)
21                break
22    def verify_block(self, block):
23        """Return True if a given block should be added to the blockchain
24        and also add it to the blockchain."""
25        prev_hash = 0
26        if len(self.blockchain) > 0:
27            prev_hash = hash(self.blockchain[-1])
28        if block.prev_hash != prev_hash:
29            return False
30        if bin(hash(block))[2:2+self.k] != 0:
31            return False
32        self.blockchain.append(block)
33        return True

So now we have the distributed timestamp service we mentioned at the beginning of this section. The rest of this section deals with loose ends.

Network

The paper clearly describes the Bitcoin protocol. Essentially, blocks contain broadcasted transactions (coins) and there is a great race to extend the block chain.

Incentive

Why should everyone race to extend the blockchain? For money of course! Each new block created also creates a new bitcoin, owned by the person who created the block. This is inflationary. There is also a non-inflationary incentive: transaction fees. A transaction must specify an input value and an output value. If the output value is less than the input value, then the person who creates the block keeps the difference for himself as a transaction fee.

Reclaiming Disk Space

Not everyone needs to have a full copy of the blockchain in order to use Bitcoin. Nakamoto describes how the use of Merkle Trees allow parts of the blockchain to be discarded without affecting the ability to validate later blocks.

Simplified Payment Verification

Combined with the previous section, anyone can verify a payment using only a subset of the blockchain.

Combining and Splitting Value

Do we need a separate transaction for each minimum unit of currency (later named a satoshi after the author), or can we have a single transaction for a larger amount? A transaction has one or more inputs (coins that Alice owns) and one or two outputs (Alice and Bob, where Bob is the recipient). I felt that this section of the paper was vague.