Bitcoin

• Bitcoin: A Peer-to-Peer Electronic Cash System

The main contribution of the paper

• A purely peer-to-peer version of electronic cash. It has several benefits (from bitcoin.org):
  • Payment freedom - It is possible to send and receive bitcoins anywhere in the world at any time. No bank holidays. No borders. No bureaucracy. Bitcoin allows its users to be in full control of their money.
  • Fewer risks for merchants - Bitcoin transactions are secure and irreversible. Merchants are protected from losses caused by fraud or fraudulent chargebacks.
  • Security and control - Bitcoin payments can be made without personal information tied to the transaction. This offers strong protection against identity theft. Bitcoin users can also protect their money with backup and encryption.
  • Transparent and neutral - All information concerning the Bitcoin money supply itself is readily available on the block chain for anybody to verify and use in real-time. No individual or organization can control or manipulate the Bitcoin protocol because it is cryptographically secure.
• A solution to the double-spending problem using a peer-to-peer network.
  What is a double spending problem?

  Suppose that Alice wants to pay Bob $1.

  • If Alice and Bob use physical cash, then Alice will not longer have the $1 after the transaction is executed. Everything is fine, assuming forgery of bills is infeasible.
  • However, if Alice and Bob use digital cash, then the problem gets more complicated, since the digital medium is so easy to copy.
    • If Alice sends a digital file worth $1 to Bob by email for example, Bob cannot know for sure if Alice has deleted her copy of the file.
    • If Alice still has the $1 digital file, then she can choose to send the same file to Carol. This problem is called double-spending.

  According to the abstract, the main idea of the solution is timestamping transactions by hashing them into an ongoing chain of hash-based proof-of-work, which is essentially one line of summary of the blockchain technology. We will see that this means the detail.

Bitcoin Address (Pseudonymous Account)

• Create a random key pair (pk, sk) of a digital signature scheme. Roughly speaking, the hashed version of the public key (i.e., H(pk)) is the account.
• In other words, any person can freely create an account. The account is random and not tied to the person. In fact, a single person can create as many accounts as he wants. In summary, the account is pseudonymous.
• In bitcoin terminology, these accounts are called bitcoin addresses. The following is the bitcoin address of bitcoin.org:

   3E8ociqZa9mZUSwGdSmAEMAoAxBK3FNDcd 

  With the hash, all addresses have the same length.

Distributed Global Public Ledger

  1: xad8d minted 2 coins

  2: daufx minted 2 coins

  3: ydand minted 2 coins

  4: zdydd minted 2 coins
  5: ydand spent 2 coins from [line 3] with fee 0.1 coin
  6:   send 1 coin to daufx  
  7:   send 0.9 coin to ydand

  8: uddaq minted 2 coins
  9: xad8d spent 2 coins from [line 1] with fee 0.1 coin
 10:   send 0.5 coin to xad8d
 11:   send 1.4 coin to mdaqx
 12: daufx spent 3 coins from [lines 2, 6] with fee 0.1 coin
 13:   send 1.5 coin to ydand
 14:   send 1.4 coin to daufx

xad8d: 0.5 [lines 1, 9, 10]
daufx: 1.4 [lines 2, 6, 12, 14]
ydand: 2.4 [lines 3, 5, 13]
zdydd: 2.1 [line 4 + fee] 
uddaq: 2.2 [line 8 + fees]
mdaqx: 1.4 [line 11]

---------------------------
total: 10 coins

• In the above so far, the ledger has 5 blocks.
• Each block contains 0 or more transactions. In particular, the first three blocks have 0 transaction. The fourth has one transaction, and the fifth two transactions.
• One can only add blocks in the ledger. No update. No removal.
• The first line of each block starts with a party minting 2 coins.
• The party who mints coins in each block is actually the creator of the block. Jumping ahead, the creator has to "work" (mining coins) for adding a block to the ledger, and the proof of work is involved in this procedure. He will collect the fees for the work that he pushed and stamped the transactions to the ledger.
• When a party spends coins, he needs to indicate where such many coins (i.e., "from [lines ..]") come from.
• For each transaction, the input amount must be the same as the output amount plus fee.

Preventing double-spending

• The ledger is maintained globally, in public, and in a distributed manner. How do to this securely is non-trivial, which is the key contribution of the bitcoin paper. We will discuss it in the later part of the lecture and the next lecture.
• Assuming the ledger is maintained consistently and securely, double-spending is impossible.
  • The ledger is append only. So, if Alice tries to double-spend her money, she must make the ledger contain two transactions with the same money source.
  • However, these two transactions would incur inconsistency of the ledger. In other words, Alice must break consistency of the ledger system to achieve what she wants. Security of the ledger system wouldn't allow Alice to do so.

Transactions

Addressing the problem of authenticity

  5: ydand spent 2 coins from [line 3] with fee 0.1 coin
  6:   send 1 coin to daufx  
  7:   send 0.9 coin to ydand

Use a digital signature!

• Note ydand is a hash of a public key of a digital signature scheme.
• So, the following data (i.e., pk and sig) will serve as a proof to ensure the authenticity:
  • pk: the public key such that ydand = H(pk).
  • sig: a signature on the transaction data (signed using the secret key sk).
• Given (pk, sig), the authenticity of the transaction can now be validated as follows:
  • See if ydand = H(pk).
  • Validate the signature sig with regard to the public key pk and the transaction data.
  The collision resistance of the hash scheme and the unforgeability of the digital signature scheme will ensure that the proof must have been issued by the real owner of ydand.

Append-only Ledger: Block Chaining with Hashes

• The ledger is represented as a chain of blocks.
• For example, PrevHash in Block2 amounts to H(Block1). Likewise, PrevHash in Block3 amounts to H(Block2).
• Tx denotes a transaction.
• Nonce will be used for proof of work (explained later).

Bitcoin Network

Peer-to-peer network

How a transaction is put into the global ledger

1. New transactions (to be stamped) are broadcast to all nodes.
2. Each node collects new transactions into a block. (Note the difference between transactions and blocks).
3. Each node works on finding a difficult proof-of-work for its block.
4. When a node finds a proof-of-work, it broadcasts the block to all nodes.
5. Nodes accept the block only if the proof-of-work is correct, and all transactions in it are valid and not already spent.
6. Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash.

Nonce and Proof of Work

A puzzle or condition A block, in order to be put into the ledger, should satisfy the following condition: The hash of a block should start with a bunch of 0s. How many 0's? It is dynamically set as a system parameter. Proof of Work The above condition implies the following: Note that a block contains PrevHash, Nonce, and Tx's. PrevHash and Tx's are fixed. However, Nonce can be random. So, by trying many random Nonce's, one can eventually obtain a block whose hash has enough leading 0s. The more 0s, the harder to find a good Nonce. For example, with ten leading 0 bits, one probably has to try roughly 210 Nonces, since hashes are roughly random. With 40 leading 0 bits, roughly 240 trials would be necessary.

H(Block) should be 0000...00000???...??? Proof of Work A good Nonce that causes the hash of the block to have enough leading 0's.

How many leading 0s in a block hash?

• How many leading 0s a block hash should have is the system parameter, called the difficulty level.
• The difficulty level is tuned dynamically so that the network (all nodes together) can find a good nonce every 10 minutes.
• So, the more nodes, the higher difficulty level.