Module III: Bitcoin and the Lightning Network

• Bitcoin and the Blockchain

-- A little history: From the origin of public key cryptography to cryptocurrencies

-- The white paper by Satoshi Nakamoto

• Cryptography and Networking

-- Cryptographic Hash Functions

-- Digital signatures

-- P2P networks and the Internet

• Bitcoin scalability and the Lightning Network

-- Payment channels and off-chain transactions

-- Routing payments

• References

1976: Whitfield Diffie and Martin Hellman: Key Exchange Protocol

Whitfield Diffie, Martin E. Hellman
New Directions in Cryptography
IEEE Transactions on Information Theory, 1976.

1983: David Chaum - Blind signatures

David Chaum
Blind signatures for untraceable payments.
Advances in cryptology. Springer, Boston, MA, 1983.

DigiCash Inc. 1989 - 1998

1992: Tim May - The Crypto Anarchist Manifesto

.....

Computer technology is on the verge of providing the ability for individuals and groups to communicate and interact with each other in a totally anonymous manner. Two persons may exchange messages, conduct business, and negotiate electronic contracts without ever knowing the True Name, or legal identity, of the other.

.....

Just as the technology of printing altered and reduced the power of medieval guilds and the social power structure, so too will cryptologic methods fundamentally alter the nature of corporations and of government interference in economic transactions.

.....

May 9, 1993: Eric Hugens - A Cypherpunk's Manifesto

Privacy is necessary for an open society in the electronic age. Privacy is not secrecy. A private matter is something one doesn't want the whole world to know, but a secret matter is something one doesn't want anybody to know. Privacy is the power to selectively reveal oneself to the world.

.....

Therefore, privacy in an open society requires anonymous transaction systems. Until now, cash has been the primary such system. An anonymous transaction system is not a secret transaction system. An anonymous system empowers individuals to reveal their identity when desired and only when desired; this is the essence of privacy.

.....

1993: Cynthia Dwork and Moni Naor - Proof of work

Cynthia Dwork and Moni Naor
Pricing via processing or combatting junk mail
Annual international cryptology conference. Springer, Berlin, Heidelberg, 1992.

1997: Adam Back - Hashcash

1998: Wei Dai - B money

1998: Nick Zabo - Bit gold

2004: Hal Finney - Reusable Proofs of Work

October 31st, 2008: Satoshi Nakamoto - Bitcoin

I've been working on a new electronic cash system that's fully peer-to-peer, with no trusted third party.

The paper is available at: http://www.bitcoin.org/bitcoin.pdf

The main properties: Double-spending is prevented with a peer-to-peer network. No mint or other trusted parties. Participants can be anonymous. New coins are made from Hashcash style proof-of-work. The proof-of-work for new coin generation also powers the network to prevent double-spending.

January 3rd, 2009: Genesis block

The Times 03/Jan/2009 Chancellor on brink of second bailout for banks

Given p = 37861 and q = 47303

Find n such that n = p × q

Given n = 2435614607

Find p e q such that n = p × q

INPUT: Two integer numbers p and q
OUTPUT: An integer number n such that n = p x q
An efficient algorithm exists

INPUT: An integer number n
OUTPUT: Two integer numbers p and q (different from 1 and n) such that n = p × q
No efficient algorithms are known

Idea: It is possible to use problems that are easy to solve in one direction (e.g., multiplication) and hard to solve in the other direction (e.g., factorization) to generate a shared secret key by communicating on an insecure channel.

Easy problem: Modular exponentiation
Given a, b e n find c such that a^b = c mod n

Difficult problem: Discrete logarithm
Given a, c e n find b such that a^b = c mod n

https://www.secg.org/sec1-v2.pdf

Transactions

We define an electronic coin as a chain of digital signatures. Each owner transfers the coin to the next by digitally signing a hash of the previous transaction and the public key of the next owner and adding these to the end of the coin.

The problem of course is the payee can't verify that one of the owners did not double-spend the coin. A common solution is to introduce a trusted central authority ..... The problem with this solution is that the fate of the entire money system depends on the company running the mint

Timestamp server

The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash

The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.

Proof of work

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back's Hashcash

The proof-of-work also solves the problem of determining representation in majority decision making. ... The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains. To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it.

Network

1. New transactions are broadcast to all nodes.
2. Each node collects new transactions into a block.
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 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.

Incentive

The first transaction in a block is a special transaction that starts a new coin owned by the creator of the block. This adds an incentive for nodes to support the network, and provides a way to initially distribute coins into circulation, since there is no central authority to issue them. The steady addition of a constant of amount of new coins is analogous to gold miners expending resources to add gold to circulation.

The incentive can also be funded with transaction fees. If the output value of a transaction is less than its input value, the difference is a transaction fee that is added to the incentive value of the block containing the transaction. Once a predetermined number of coins have entered circulation, the incentive can transition entirely to transaction fees and be completely inflation free.

Disk Space

Transactions are hashed in a Merkle Tree, with only the root included in the block's hash...

A block header with no transactions would be about 80 bytes. If we suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computer systems typically selling with 2GB of RAM as of 2008, and Moore's Law predicting current growth of 1.2GB per year, storage should not be a problem

Simplified Payment Verification

It is possible to verify payments without running a full network node. A user only needs to keep a copy of the block headers of the longest proof-of-work chain, which he can get by querying network nodes until he's convinced he has the longest chain, and obtain the Merkle branch linking the transaction to the block it's timestamped in.

Combining and Splitting Value

To allow value to be split and combined, transactions contain multiple inputs and outputs. Normally there will be either a single input from a larger previous transaction or multiple inputs combining smaller amounts, and at most two outputs: one for the payment, and one returning the change, if any, back to the sender.

It should be noted that fan-out, where a transaction depends on several transactions, and those transactions depend on many more, is not a problem here. There is never the need to extract a complete standalone copy of a transaction's history.

Privacy

The traditional banking model achieves a level of privacy by limiting access to information to the parties involved and the trusted third party. The necessity to announce all transactions publicly precludes this method, but privacy can still be maintained by breaking the flow of information in another place: by keeping public keys anonymous. The public can see that someone is sending an amount to someone else, but without information linking the transaction to anyone.

HD wallets

Seed

Lightweight wallets: Privacy and Bloom filters

Lightweight wallets: Privacy and Bloom filters

Funding transaction

Update balance

Hash Time-Locked Contracts (HTLCs)

Onion routing

Onion routing

https://github.com/bitcoinbook/bitcoinbook

https://github.com/jimmysong/programmingbitcoin

https://bitcoinbook.cs.princeton.edu/

https://github.com/lnbook/lnbook

https://ocw.mit.edu/courses/mas-s62-cryptocurrency-engineering-and-design-spring-2018/