Bitcoin And Cryptocurrency Technologies: Notes

2020-08-13


These are notes on the Princeton Bitcoin book by Narayanan et al. There is a Coursera course that accompanies the book, and all course content is free. I was deciding between this book and Mastering Bitcoin. Though this book was pretty good, I imagine the latter being more comprehensive from a development standpoint. I have merely printed my own notes, meaning that I have skipped certain portions that did not interest me.

Introduction

In today’s financial system, we use a mixture of credit and cash.

In online payments, providing credit card details directly to a seller can be a security risk.

Double spending problem: if you receive a piece of data representing a unit of virtual cash, you can make copies of it and pass it on to different people. David Chaum’s innovation (blind signature):

Digicash and others relied on USD or gold. To make a currency out of thin air, it needs to be scarce. This is the objective of Bitcoin mining. Desired properties of computational puzzles:

The idea of Bitcoin’s blockchain is to collect documents in a tree structure into blocks and link the blocks (Bitcoin does this and also gets rid of signatures).

“Bitcoin is an implementation of Wei Dai’s b-money proposal on Cypherpunks in 1998 and Nick Szabo’s Bitgold proposal” – Satoshi

Ch 1: Introduction to Cryptography & Cryptocurrencies

Cryptocurrencies make heavy use of cryptography for securely encoding the rules of the system in the system itself.

A hash function is a mathematical function with variable size input and fixed size output (assume 256 bits) and is efficiently computable. A cryptographic hash function has some additional properties:

SHA-256, the hash function that Bitcoin uses, takes \(768\)-bit input and produces \(256\)-bit output. It uses the Merkle-Damgard transform and pads the input so that the length is multiple of \(512\) bits.

A hash pointer consists of a pointer to where some info is stored in addition to a cryptographic hash of the info, so that you can both retrieve info and verify that the retrieved info has not changed.

A blockchain is a linked list of blocks containing data as well as a hash pointer to the previous block. So, you have the location of the value of the previous block and a digest of that value. You store the head of the list (ie the hash pointer to the most recent block).

A Merkle tree is a binary tree using hash pointers. Group the leaves, which are the blocks, into pairs and then for each pair make a structure with a hash pointer to each block. Keep building hash pointers up the tree until the root. Tampering with a block can be detected by storing the hash pointer at the root. Proof of membership for a block in the tree required only \(log(n)\) blocks out of \(n\) for verification.

A digital signature scheme has three algos: 1) \((sk,pk)=generateKeys(keysize)\), 2) \(sig=sign(sk,msg)\), and 3) \(isValid=vrfy(pk,msg,sig)\), and requires that \(vrfy(pk,msg,sign(sk,msg)) = 1\) and that signatures are existentially unforgeable. Except verification, the algorithms should be randomized.

Bitcoin uses a signature scheme called ECDSA (elliptic curve digital signature algorithm) over the elliptic curve secp256k1 which provides ~\(128\)-bit security.

We treat a public key from a digital signature scheme as an identity of a person. This means that you can make a new identity whenever you want. The probability of someone else generating the same key as you is negligible (given a good source of randomness). But using the same identity, however random-looking, over time makes a series of statements that can be used to identify the real-world person.

Key challenges faced by a cryptocurrency to solve: double spending, removing central trusted authority, minting new coins.

Ch 2: How Bitcoin Achieves Decentralization

Decentralization is not all or nothing. While SMTP is an open standard and anyone can set up an email server, the market is dominated by a handful of centralized providers. While Bitcoin is decentralized, Bitcoin exchanges and wallets may be centralized. We can measure Bitcoin’s decentralization with 5 questions:

  1. Who maintains the ledger?

  2. Who has authority over transaction validity?

  3. Who creates new bitcoins?

  4. Who determines how the rules of the system change?

  5. How do bitcoins acquire exchange value?

We want to achieve a distributed consensus protocol, ie a protocol of \(n\) nodes (which are either honest or malicious/faulty) with input values that 1) must terminate with all honest nodes in agreement on the value and 2) the agreed-upon value must have been generated by an honest node.

By incorporating incentives and randomness, Bitcoin violates certain assumptions in traditional models of consensus which were built for distributed databases.

A consequence of pseudonymity in Bitcoin is a Sybil attack: a malicious adversary creates copies of nodes to look like there are a lot of different participants.

A simplified Bitcoin consensus algorithm based on implicit consensus: assuming that it is possible to randomly select one node, and if one person has multiple nodes then to only select one of those nodes, in each round a random node is selected and proposes the next block and other nodes implicitly accept (only if all txns are valid) or reject the block by either extending the chain on that block (including the block’s hash in the next block they create) or by ignoring that block.

Protection against invalid transactions is cryptographic, but protection against double-spending is purely by consensus.

Nodes need an incentive for behaving honestly. It’s hard to punish a malicious node, so instead we reward honest nodes. There are two mechanisms to do this:

  1. Block reward: the node that creates a block can include a create coin transactionn to itself in that block (the reward value halves every 210,000 blocks or roughly every 4 years according to a geometric series with sum 21 million). This node can only collect the reward if the block in question ends up on the long-term consensus branch. Need another incentive for when new bitcoins eventually run out.

  2. Transaction fees: creator of transaction can choose to make output value less than the input value and then collect the difference.

Proof of work (PoW): approximate the selection of a random node by instead selecting nodes in proportion to a resource that is hoped nobody can monopolize, e.g. computing power. This is sort of a tax on identity creation and therefore on the Sybil attack

PoW in Bitcoin is done using hash puzzles. The node proposing a new block must find a number ("nonce") such that $$H(nonce||prev\_hash||txn||txn||...||txn)<target$$

Proof of stake (PoS): selecting nodes in proportion to their ownership of the currency.

A miner profits if the the block reward + transaction fees are greater than the hardware cost + operating costs.

Ownership of bitcoins is nothing more than other nodes agreeing that a given party owns those bitcoins.

A cryptocurrency needs bootstrapping to get off the ground so that an adversary cannot take over 50 percent of the new block creation.

51 percent attack: consensus fails and one attacker controls a majority of the mining power. What can he do?

Ch 3: Mechanics of Bitcoin

Bitcoin transactions (abbreviated to txns):

Bitcoin scripts:

Bitcoin network:

Ch 4: How to Store and Use Bitcoins

Storing bitcoins is really all about storing and managing Bitcoin secret keys.

There are three goals in storing keys: being able to spend when you want to; no one else being able to spend your coins; spending being convenient to do.

Keys can be communicated as a text string (key bits converted to base 58) or a QR code.

Cold storage doesn’t have to be online to receive coins; the hot storage just needs to know the cold address.

Hierarchical wallet: the cold side can use an unbounded number of addresses and the hot side can know these addresses, but only with a short, 1-time communication between the two sides (ECDSA)

How to store cold information?

These methods of cold storage all involve a single point of failure. This can be solved using secret sharing:

Ways in which you can use other people’s services to store and manage your bitcoins:

Payment services make it easy for merchants to accept, process, and exchange Bitcoin. They handle receiving the bitcoins and making deposits. They absorb all of the risk. Because of high volume, it needs to actively participate in exchange markets. Example of a Bitcoin purchase:

Ch 5: Bitcoin Mining

Miners validate every txn, build and store all the blocks, and reach a consensus on which blocks to include in the blockchain. Nodes have to perform 6 tasks in order to mine:

  1. Listen for txns and validate them.

  2. Maintain blockchain by listening for new blocks and validating them.

  3. Assemble a candiate block.

  4. Find a nonce that makes your block valid (most difficult part).

  5. Hope your block is accepted.

  6. Profit?

A miner compiles valid txns from his pool into a Merkle tree, up to the block size limit. He then creates a block with a header pointing to the previous block. He keeps trying different nonces looking for the one that causes the block’s hash to be under the target (\(2^{32}\) possibilities).

No two miners work on the same puzzle unless they share a public key, which would only happen if they are in the same mining pool.

The mining difficulty changes every 2016 blocks (~every 2 weeks) and is adjusted based on how efficient the miners were over the period of the previous 2016 blocks.

CPU mining: Miners simply ran a small piece of code on a general purpose CPU to search over nonces linearly. This had the speed of 20 million hashes per second, which meant several hundred thousand years at the \(2^{67}\) difficulty level to find a valid block.

GPU mining: Miners began to mine with their graphics card with a language called OpenCL.

FPGA mining: Field Programmable Gate arrays. At one billion hashes per second, only a marginal improvement over GPUs.

ASIC mining: Bitcoin mining is dominated by application specific integrated circuits, chips designed specifically for Bitcoin. But the cost of electricity and cooling means individual miners are unlikely to profit.

Professional mining: Centers buy ASICs newer and more efficient than the ones available to the public.

Landauer’s principle: says any non-reversible computation (ie those that lose information) uses a minimum amount of energy. Flipping a bit in a non-reversible way requires using a minimum number of joules. SHA-256, being non-reversible, leads to a lot of energy consumption.

A Poisson distribution (\(N\) independent trials each with a \(\lambda/N\) chance of success as \(N\) approaches infinity) approximates the expected number of blocks found by a miner.

Ch 6: Anonymity Basics

Is Bitcoin anonymous? Do we want a cryptocurrency that is truly anonymous?

Bitcoin only achieves pseudonymity. If something has both pseudonymity and unlinkability (different interactions should not be able to be tied to each other) then it has anonymity.

Instead of desiring complete unlinkability, we only try to maximize a txn’s anonymity set, which is the set of txns which an adversary cannot distinguish from the txn.

Deanonymization techniques:

Mixing is a way to counter transaction graph analysis by using an intermediary to swap bitcoins.

Zerocoin and Zerocash incorporate mixing at the protocol level so that you don’t need to trust mixes, peers, intermediaries, or even miners. They are not compatible with Bitcoin. To understand Zerocoin, first consider Basecoin which is a currency that uses Zerocoin as a trading mechanism.

Zerocash builds on Zerocoin and uses zk-SNARK which is a way of making ZKP verification more efficient so that there is no need for basecoin. As a result, txn amounts are no longer inside the commitments or visible on the chain. The ledger only records existence of txns and proofs, not addresses and not values.

Ch 7: Community, Politics, and Regulation

The genius of Bitcoin is consolidating consensus about rules, about history, and that coins are valuable.

Bitcoin Core is the most widely used Bitcoin software. Substaintial changes go through a process called Bitcoin Improvement Proposals. Bitcoin Core developers, (as of 2015, are Gavin Andresen, Jeff Garzik, Greg Maxwell, J van der Laan, Pieter Wuille. If the lead developers behave badly, the community could choose to fork the software.

Stakeholders in Bitcoin:

Roots of Bitcoin:

Ch 8: Alternative Mining Puzzles

Bitcoin’s mining puzzle is a partial hash-preimage puzzle.

Essential puzzle requirements:

ASIC-resistance means a puzzle design for which existing general purpose CPUs are already the cheapest and most efficient devices. This is impossible, so we just want to reduce the gap between ASICs and general purpose CPUs.

Virtual mining: Rather than spending money on power and equipment to prove who has invested the most in mining, simply allocate mining power directly to all currency holders in proportion to how much currency they hold.

Ch 9: Bitcoin as a Platform

Bitcoin as an append-only-log:

Bitcoin as smart property:

Secure multi-party lotteries:

Bitcoin as public randomness source:

Ch 10: Altcoins and the Cryptocurrency Ecosystem

Every altcoin needs a reason to exist. In the simplest case, the altcoin just changes some of the parameters of Bitcoin.

Namecoin: Decentralized version of DNS.

Litecoin: Payment system launched shortly after Namecoin that has been forked more times than even Bitcoin.

Peercoin: First altcoin to use PoS mining.

Dogecoin: A close fork of Litecoin distinguished not by tech but by community values of generosity and humor.

Merge mining: mining on multiple currencies simultaneously, without dividing mining resources. Leads to greater mining centralization in altcoins.

Cross-chain atomic swaps: exchanging between quantities of different coins, despite txns one coin being entirely independent of a txn on another coin. This involves commitments and time-locked deposits, but it’s also complex and doesn’t prevent denial of service.

Side chains: altcoins whose prices are bilaterally pegged to the price of Bitcoin. They use Bitcoin as a sort of reserve currency to remove volatility during the bootstrapping phase. The naive way to do this is encode all the sidechain’s rules into Bitcoin. A better way is SPV proofs:

Bitcoin’s scripting has a small instruction set that isn’t Turing complete, requiring new new altcoins for each new application-specific functionality. Ethereum is a single altcoin that aims to provide a Turing-complete programming language for writing scripts or “contracts”.

Ch 11: Decentralized Institutions: The Future of Bitcoin?

The key difference between Bitcoin and the previous attempts at digital cash is decentralization. The core innovation of Bitcoin that enables decentralization is the blockchain.

Can we decentralize everything? We need to ask four questions:

  1. What is being decentralized?

  2. What is the level of decentralization?

  3. What blockchain is deployed?

  4. What security mechanism does it use?