Blockchain

Introduction

At it's core, Bitcoin represents the replacement of trust through institutions to trust through networks. >> Institutions are failing, because they represent systems of scale for industrial societies ... we are now a global information society —Andreas Antonopolus

Blockchain reduces Uncertainty by simplifying [1]:

  • Identity management
  • Asset tracking
  • Reneging on deals (escrow)

Assurances

  • Digital signatures: Safeguard money
  • Transaction chains: Store history of ownership
  • Blockchain: holds transaction order

Benefits

  • Detachment from gov't manipulation
  • Anonymous transactions (by using Thor networks)
  • Lower costs

Challenges

  • Exchange BT with other currencies
  • Used for illegal activities
  • Mining is still resource-intensive [2]

Cryptography

from Coursera

Decentralization

from Coursera

Questions:

  1. Ledger maintainer?
  2. Authority over transactions validity
  3. Coin creating
  4. rules of the system exchange
  5. how coins acquire exchange value

Bitcoin aspects:

  1. peer-to-peer network: anyone can join, low barrier
  2. mining: open but concentrated
  3. sw updates: trusted core team

Distributed Consensus[3]:

Data consistency across nodes (reliable distrybuted systems) will enable lots of desirable applications (DNS, PK directory, stock trades).

Def:

  • Protocol has end state and correct nodes set same value
  • Value is proposed by a correct node

How it works?

Works in theory.

blocks of transactions + set of outstanding tx + ??

Consensus is hard because nodes may crash or be malicious + network may fail (e.g., lack of global time), see: Byzantine generals problem.

Paxos protocol: Always consistent, but might get stuck

Bitcoin provides an incentive 💰
Bitcoin embrances randomness (no end-point, long wait consensus)

No identity consensus

  • identity provides IDs and security properties.
  • Bitcoin doesn't have identities, hard in P2P. Pseudonymity is a goal

Incentives

Decentralization: partly technical + partly incentive engineering
Use of bitcoin to reward nodes with longest blockchain

  1. block reward: creator of blocks get coin creating transaction (halves every 4 years) Creator get reward if block in long-term consensus branch
  • There is a finite supply of bitcoins
  • how new bitcoins are created (till 2140)
  1. transaction fee: Make output, less than input value. Remainder goes to block creator.
Problems:
  1. How to pick a random node?
  2. How to avoid a free-for-all due to rewards
  3. Prevent Sybil attacks?
Solution: Proof of work
  1. Select nodes in proportion of
  2. their computing power (proof of work) or node competion or hard node creation
  3. bitcoin ownership (proof of stake)

PoW properties (Hash puzzle):

  1. difficult to compute 10^20 hashes/block (miners: very few node bother to compete) -- add nounce a random value to hash, so is harder to find.
  2. parametrizable hash Nodes recalculate target every 2 weeks (avg between blocks = 10min) > Probability (block_found(i)) = fraction (global has power for i)

Security assumption: Attacks are infeasible if majority if miners weighted by hash power follow the protocol

for a miner:


mean_time_to_find_block = 10 min / fraction_of_hash_power

  1. trivial to verify Nonce is part of the block, miner can hash all including nonce and verify is included

Mining economics

Mining_reward             > hardware + 🔌 -> Profit
(block reward + Tx fee )

fixed (💻) vs variable costs(🔌)
reward depends on global hash rate
exchange of rate (USD?) at a given time

Recap

  • Identities: Pseoudonomous key pairs
  • Transactions: Instructions of transfer coin between addresses
  • P2P Network: Best effort (imperfect but OK)
  • Blockchain and consensus: Security, more confirmation more confidence. There is a probability ratio of finding the next block.
  • Hash puzzles and Mining: Difficulty, must find equilibrium between reward and cost

Consensus

  1. value: amount
  2. state: which transactions are valid, ownership part of the consensus
  3. rules: challenged by forks...

Bitcoin is bootstrapped

Now I want to show you another subtle idea, which is very tricky, and
its this very neat idea of bootstrapping that
I really found intriguing the first time I encountered it.
So I want to share this with you.
So what do I mean by bootstrapping.
I mean the tricky interplay between three things in Bitcoin, and
what are these three things?
Let's start from the security of the block chain.
So obviously we want the block chain to be secure for
Bitcoin to be a viable currency.
But, what is necessary for the block chain to be secure?
What this means is that an adversary shouldn't be able to overwhelm
the consensus process.
Shouldn't be able to create a lot of nodes and take over 50% or
more of the new block creation.

But when will that be true?
What is the prerequisite for that?
A prerequisite for that is having a healthy mining ecosystem

made up of largely honest protocol following nodes.
So that's a prerequisite for security of the block chain.
But what's a prerequisite for that?
When can we be sure that a lot of miners will put a lot of computing power
into participating in this hash puzzle solving competition?
Well, they're only gonna do that if the exchange rate of Bitcoin is pretty high.

Why is that?
Because they receive rewards denominated in Bitcoins,
whereas their expenditure is in dollars, so the more the value of the currency goes
up the more incentivized these miners are going to be.

But what ensures a high and stable value of the currency?
That can only happen if, users in general,
people who want to buy Bitcoins, have trust in the security of the block chain.
Because if they believe that the network could be overwhelmed at any moment by
an attacker then Bitcoin is not going to have a lot of value as a currency.
So you have this interlocking interdependence between these three
things, all right?
So the existence of each of these is predicated on the existence of another.

                             security of             value of
                   +-------> blockchain   +--------> currency
                   |                                    |
                   +                                    |
                 healthy                                |
                 mining   <-----------------------------+
                 ecosystem

51% attacker possibilities

Can't steal coins from address: subvert consensus != subvert cryptography

  • even if chain is the longest, not valid for other nodes ❌

Suppress transactions?

  • from block chain ✅ < easy to spot, not practical for attacker
  • from P2P network ❌

Change block reward? No, copies of honest nodes are not accesible ❌

Destroy confidence. might happen, practical threat ✅✅

Bitcoin consensus

  • append only ledger
  • decentratlize consesns
  • miners to validate Tx

Assume currency exists as motivation!

Transactions

Bitcoin is not account-based model, is transaction-based

Example (one transaction per block)

1. inputs: empty
   outputs: 25.0 -> Alice
   
2. inputs: 1[0] ✍Alice
   outputs: 17.0 -> Bob, 8.0 -> Alice
   
3. inputs: 2[0] ✍Bob
   outputs: 8.0 -> Carol, 7.0 -> Bob
   
4. inputs: 2[1] ✍Alice
   outputs: 6.0 -> David, 2.0 -> Alice

Is Tx4 valid?
Check last transaction by Alice (2), Output 2 has enough to cover Tx4 Ouputs therefore is valid.
Change address: Output must credit back unspent amounts to Alice/Bob
Finite backward scan to verify validity using hash pointers

Merge value becomes possible, by multiple inputs into one output Tx (multiple signatures needed)

Structure of Tx

  1. Meta
  • hash
  • housekeeping (sizes tx, size input, size outputs, lock_time[^100])
  1. Inputs(array)
  • hash previous tx
  • signature
  1. Output(array)
  • value
  • scriptPubKey (recipient address? no, script!)

Bitcoin scripts

  • ScriptSign + ScriptPubKey => paste together run together to validate
  • Specific for Bitcoin (based on Forth language)
  • Simple, cryptography oriented, no-loops, no Turing complete, stack-based, time and memory limited. Finite number of steps to complete.

Signature verification built in the language, no dependencies required, signature only to entire transactions.Only valid or invalid output in this language.

example:

<sig><pubKey> OP_DUP OP_HASH160 <pubKeyHash?> OP_EQUALVERIFY OP_CHECKSIG

256 opcodes, 15 disabled, 75 reserved
arithmetic, if/then, logic/data handling, crypto: hashes, signature verification, multi-signature verification (OP_cHECKMULTISIG) multiple verifications with threshold)

Most known scripts whitelisted by nodes. Proof-of-burn: write arbitrarily data on bitcoin. Multi-sig is complicated for simple Tx, use a hash of redemption script (pay to script hash).

Script applications

Escrow transactions

Alice buys from Bob
Alice > multisig (3 ppl incl. judge=judy, 2 of 3 signs)
Normal case: Alice + Bob sign
Alice doesn't want to pay:  Judge decides

Green addresses

Send money without recipient accessing the blockchain
No bitcoin guarantee, trust shifted to bank or third party. No double spend
Mt. Gox did it. Not very popular anymore.

Efficient micro-payments

many Tx, incur in large fees, do a large Tx at the end instead.
MULTISIG Tx, Send Tx to the Seller not signed by receiver, at the end Seller publishes to the blockchain large transaction.

Generates a huge amount of potential double spends (locally)
locktime: timeout in case Seller doesn't sign, then refund

lock_time[^100]: (hash) block index or real-world timestap must appear to publish this transaction

Advanced applications
  • multiplayer lotteries
  • hash pre-image challenges
  • coin-swapping protocols (anonimity)

Bitcoin Blocks

Single unit of works bigger that individual Tx
Limits the length of hash-chain of blocks


     +--------------+        +---------------+       +--------------+
     |              |        |               |       |              |
     |    +------------+     |     +------------+    |   +------------+
  <--+    | prev : H() | <---+     | prev : H() | <--+   | prev : H() |
          | trans: H() |           | trans: H() |        | trans: H() |
          +------------+           +------------+        +------------+
                                              |
                                              |
                                              |
                                              |
                                         +----v-----+
                                   +-----+ H()  H() +----+
                                   |     +----------+    |
                                   |                     |
                                |                        |
                           +----v-----+            +-----v----+
                       +---+ H()  H() +--+      +--+ H()  H() +---+
                       |   +----------+  |      |  +----------+   |
                       |                 |      |                 |
                       |                 |      |                 |
                 +-----v-----+ +---------v-+  +-v---------+ +-----v-----+
                 |transaction| |transaction|  |transaction| |transaction|
                 +-----------+ +-----------+  +-----------+ +-----------+

Merkle tree of all transactions in the block. Easy to traverse/prove the Tx exists in the block.

Block structure:

  1. Block header  >> hashed during ⛏
  • hash ⛏ puzzle
  • ver
  • prev_block
  • time
  • bits ⛏ puzzle
  • nonce ⛏ puzzle
  1. Transaction data
  • mrkl_root hashed during ⛏
  • n_tx
  • size
  • tx: ( ... )
  • mrkl_tree (
  • hash
  • hash
    )

coinbase transaction

in array() {
    prev_out : {
        hash:  "000...000",
        n: 9583
    }
},
coinbase: "arbitrary content"
out: array() {
  value: 25.12121 ⬅ block reward (25) + transaction fee (.12121)
  scriptPubKey: "OPDUP OPHASH160..."
}

Live examples at blochain.info

Bitcoin Network
  • P2P Network:
  • Ad-hoc (TCP 8333),
  • ad-hoc network with random topology
  • nodes are equal
  • new nodes can join any time
  • forget non-responding nodes after 3hr

Node joins: ask 1st peer: Tell me about the nodes you know about? Connect to  random nodes.

Node: Transaction propagation (flooding) happens until same transaction is pushed 2nd time. No forwarding

  • if already Tx valid in current block chain
  • script is whitelisted sanity check, may be ignored
  • not seen before (avoid infinite loops) sanity check, may be ignored
  • no conflict (prevent double-spends) sanity check, may be ignored

Race conditions
For a brief period of time, nodes may disagree on state. Tx or block conflict:

  • Accept what you hear first
  • Network position matter
  • Miners may implement other logic! Always check again

Block propagation is similar (flooding) relay when

  • Block meets the hash target
  • Block has all valid transaction (run all scripts, even if not relaying)
  • Block builds on current longest chain (no forks) sanity check, maybe ignored

Block propagation is bad: Optimized for decentralization, not efficiency.

Full-node
  1. permanent connection
  2. store entire blockchain
  3. Hear and forward very node/Tx

Maintains Unspent Transaction Ouput UTXO, fits in RAM (44M Tx ~12 M)

Thin node SPV client (not fully-validating)
  • Store block headers only
  • Request Tx as needed
  • Trust fully-validating nodes
    20GB
    Just keep info that you need, e.g., wallet

Limitations

Hardcoded: 10 min avg creation time, 1 M bytes in a block, 20K signature ops per block, 100 M satoshis per bitcoin, 12M total bitcoins ever, 50, 25, 12.5 BTC mining reward

Throughput:
  • 1 M bytes/block (10 min)
  • 250 bytes/transaction
  • 7 Tx/sec
visa: 2K - 10K Tx/sec, paypal 50-100 Tx/sec
Cryptography:

Only 1 signature algo (ECDSA/P256)
Hard-coded hash functions

Hard-forking changes are difficult, nodes will be split. Never join together again. Needed: New op codes, changes to size, mining rates, bug fixes.

Soft-forking add new features which only limit the set of valid Tx, needs majority. e.g., pay to script hash. New signature, new per block metadata



How the blockchain will radically transform the economy | Bettina Warburg ↩︎

Bitcoins Energy Consumption An Unsustainable Protocol That Must Evolve? ↩︎

https://www.coursera.org/learn/cryptocurrency/lecture/At1IC/ ↩︎