Bitcoin and Blockchain

Séminaire ECO/Escape

Victor Poupet

2021-12-07

\( \newcommand{\TR}{\operatorname{TR}} \renewcommand{\epsilon}{\varepsilon} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ACA}{\mathcal{A}} \newcommand{\ACQ}{\mathcal{Q}} \)

Introduction

What is Bitcoin?

2008: Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto
2009: Public implementation (open source client)

Digital currency
Not backed by physical ressource
Totally decentralized (no bank, no state, no central authority)
No need for trust

Cryptographic Tools

Hash function

double SHA 256
\(|H(m)|\) = 256 bits
Easy to compute
Deterministic
One-way (only practical way to reverse is brute force search)
Small change in input changes hash value unpredictably

Digital Signature

Uses Elliptic Curve Digital Signature Algorithm
Users generate public/private keys pairs
Message can be signed with private key\[\operatorname{Sign}(m, K_{\operatorname{private}}) = s\]
Signatures can be checked\[\operatorname{Check}(m, s, K_{\operatorname{public}}) \in \{0, 1\}\]
If signature is checked, it had to be signed with private key

\( \newcommand{\sig}{\operatorname{sig}} \)

Transaction Ledger

Alice pays Bob 50 BTC
Bob pays Charlie 20 BTC
Bob pays Alice 40 BTC
...

Alice gets 100 BTC
Alice pays Bob 50 BTC
Bob pays Charlie 20 BTC
Bob pays Alice 40 BTC
...

Alice gets 100 BTC
Alice pays Bob 50 BTC (\(\sig_A\))
Bob pays Charlie 20 BTC (\(\sig_B\))
...

Alice gets 100 BTC
Alice pays Bob 50 BTC (\(\sig_A\))
Bob pays Charlie 20 BTC (\(\sig_B\))
...

Problems

No overspending (no trust)
- mint resources
- reject invalid transactions
No spending others' money
- require emitter signature

Note: no need to store account balance

Distributed Ledger

To avoid central authority, ledger is distributed to all users

→ Problem with conflicting updates (double spending)

Proof of Work

Idea (Proof of Work)

In case of several conflicting series of transactions, keep the one that has the most computational work put into.

To add transactions to the ledger, it is necessary to solve a combinatorial puzzle (spend computation resources)
The history with most solved puzzles has priority
One branch will overtake others and it will be increasingly difficult to bring another branch to the same level
Trust a transaction when enough elements have been added after (confirmations)

The Blockchain

Transactions are gathered in blocks

Blocks contain

A header
- Version number
- Hash of previous block header
- Hash of transactions (merkle root)
- Timestamp
- Difficulty target (bits)
- Nonce
A list of transactions

Proof of Work

The difficulty target is a number set by the protocol
The nonce is a number that is added to the header so that\[H(\operatorname{header}) \leq \operatorname{target}\]

Example: Block 712897

bits = 0x170C9A13
target =
0x0000000000000000000C9A130000000000000000000000000000000000000000
hash =
0x0000000000000000000A150EA94BF7D3A0775FE8F96AA17C8EEB671FBEB06055

Note: The target is adjusted every 2016 blocks so that it takes ~10 minutes to validate a block.

Immutability

The whole blockchain can be downloaded (~700k blocks, ~350GB)
The full chain can be checked for validity
Changing any block (transactions or header) requires redoing all proofs of work for later blocks

Transactions

Transactions are made of

a list of inputs
- reference to a previous unspent transaction output (UTXO)
  - hash of previous transaction
  - index of output in transaction
- script to unlock the UTXO (~signature with private key)
a list of outputs
- value (in Satoshi = \(10^{-8}\) BTC)
- script to unlock the output (~public key of target account)

Example

Total value of inputs ≥ total value of outputs
Inputs are spent entirely
"Change" by adding self to outputs
All unspent input value goes to block validator (transaction fee)

Coinbase Transaction

User who validates a block can add a special coinbase transaction with no input and fixed value (block reward)

Incentive for spending computational power
Block reward halves every 210000 blocks (~4 years)
Initial block reward: 50 BTC, currently 6.25 BTC

Overview

Users broadcast new transactions to all nodes
Nodes gather new transactions into blocks
Nodes work to find suitable hash for block (proof of work)
When proof of work is found, block is broadcast to all nodes
Nodes check validity of block
- Transactions are valid
- Transactions inputs are not spent
- Block structure and hash are correct
If valid, all nodes start working on next block

Note: possible ties are solved by working on block that arrived first (for each node) and switching to first solved

Note 2: The system is fundamentally a distributed consensus protocol but the block reward and transaction fees are required to make it work

Merkle Trees

Transactions are hashed into a Merkle tree
The Merkle root is included in the block header
When transaction is fully spent (all outputs spent) it can be pruned from the tree
All UTXO can still be checked in the block
Blocks with all transactions spent can store only header

Simple verification

Its possible to verify a transaction with only block headers and a query of the Merkle branch for the transaction

Image from Bitcoin white paper

Scripting

Transaction outputs contain a script scriptPubKey
To spend an UTXO, a transaction input contains a second script scriptSig
The transaction is valid if scriptSig + scriptPubKey returns True

see list of opcodes

Example: send to an account (hash of public key)

scriptSig


        <sig>

        <pubKey>

scriptPubKey


        OP_DUP
OP_HASH160

        <pubKeyHash>

        OP_EQUALVERIFY

        OP_CHECKSIG

Example: reverse a given hash

scriptSig

<data>

scriptPubKey


        OP_HASH256

        <hash>

        OP_EQUAL

Example: find a hash collision

scriptSig


        <data1>

        <data2>

scriptPubKey


        OP_2DUP

        OP_EQUAL

        OP_NOT

        OP_VERIFY

        OP_SHA1

        OP_SWAP

        OP_SHA1

        OP_EQUAL

Calculations

Probability of an attacker branch successfully catching up from a deficit of \(z\) blocks:

\[ q_z = \left\{\begin{array}{ll}1 & \textrm{if } p \leq q \\ (q/p)^z & \textrm{if } p > q\\ \end{array}\right. \]

\(p\): prob. honest node finds next block

\(q\): prob. attacker finds next block

Data from Bitcoin white paper

With q = 0.1

z=0	P=1.0000000
z=1	P=0.2045873
z=2	P=0.0509779
z=3	P=0.0131722
z=4	P=0.0034552
z=5	P=0.0009137
z=6	P=0.0002428
z=7	P=0.0000647
z=8	P=0.0000173
z=9	P=0.0000046
z=10	P=0.0000012

With q = 0.3

z=0	P=1.0000000
z=5	P=0.1773523
z=10	P=0.0416605
z=15	P=0.0101008
z=20	P=0.0024804
z=25	P=0.0006132
z=30	P=0.0001522
z=35	P=0.0000379
z=40	P=0.0000095
z=45	P=0.0000024
z=50	P=0.0000006

For P < 0.001

q=0.10	z=5
q=0.15	z=8
q=0.20	z=11
q=0.25	z=15
q=0.30	z=24
q=0.35	z=41
q=0.40	z=89
q=0.45	z=340

Bitcoin and Blockchain

Introduction

What is Bitcoin?

Cryptographic Tools

Hash function

Digital Signature

Transaction Ledger

Distributed Ledger

Proof of Work

The Blockchain

The Blockchain

Proof of Work

Immutability

Transactions

Coinbase Transaction

Overview

Merkle Trees

Simple verification

Scripting

Calculations

References