Endong Liu

Stay Hungry, Stay Foolish

9 minute read

UCL Course COMP0143 Cryptocurrencies: LEC-03

Byzantine Adversaries

Goal

Prevent network systems from achieving their objects

Capabilities

  • Corrupt a subset of \(f\) out of \(n\) nodes (where \(f \leq n\))

    Adversaries have access to all secrets of nodes in \(f\)

    Adversaries control their actions of nodes in \(f\)

  • Take actions arbitrarily

    e.g., returning any values at all, sending messages in any order, transmitting corrupt values …

  • Observe all messages from honest nodes before taking actions

    Adversaries who take action last called rushing

Relaxtional Variety: Rational Adversaries

Definition

Adversaries will act in a utility-maximizing way

i.e they exploit system weakness to maximize profits without causing the system dysfunctional

Consensus

Goal

Protect Distributed Systems

Properties

  • Safety

    Honest nodes have a consistent view of system’s state

    which agree which transactions took place in what order

  • Liveness

    Honest nodes can make progress and update system’s state eventually

  • Fairness

    Nodes are awarded according to their contributions

    This is specific to incentive-driven systems (relevant against rational adversaries)

Note that

The security requirements are based on

\[|n|=2|f|+1 \quad (<50\% \text{ corrupt nodes})\] \[|n|=3|f|+1 \quad (<33\% \text{ corrupt nodes})\]

which make Byzantine Fault-Tolerant (BFT) consensus meaningful

Requirement: Sybil-Resistant

Sybil Attacks is to create a large number of presudonyms (called sockpuppets)

to subvert the reputation system of a networked service (the root cause for many security issues)

Note that

The cheaper it is to create a pesudonym in a networked system

The easier it usually becomes to mount Sybil Attacks

The secuirty requirements to create Sybil-Resistant Identities

Bitcoin Solution: Proof-of-Work

Proof-of-Work (PoW): Solving computational puzzles

Process

Given the length of blockchain \(l\)

  1. Gather transactions from the network into a block \(B_l\)

  2. Brute-force search a nonce in the block header of \(B_l\) until

    \[H(B_l) < t\]

    where \(H\) is a Collision-Resistant Hash Function (CRHF)
    and \(t\) is a target value which represnets the difficulty of computational puzzles

  3. Once found, broadcast \(B_l\) with the specfic nonce as Proof-of-Work to the rest of network

Note that

A block is accepted only if its Proof-of-Work and all included transactions are valid

Properties

  • Permissionless

  • Independence

  • Optimization-free

  • Progress-free

  • Parameterizability

  • Easy-to-verify

  • Hardness-Accimulation

Requirement: Puzzle-Friendly

Definition

A Collision-Resistant Hash Function \(H\) is puzzle-friendly when

for every possible \(n\)-bit output value \(t\), and
for every random valye \(k\) chosen from a distribution with high min-entropy:
it is infeasible to find \(x\) such that \(t=H(k||x)\) in time significantly less thatn \(2^n\)

In other words,

players cannot find a better way to hit the target value \(t\) than trying random inputs \(x\)

Note that

Bitcoin uses \(H(\cdot) := \text{SHA-256}(\text{SHA-256}(\cdot))\) as a puzzle-friendly CRHF

In Bitcoin, the target \(t\) is the upper bound for which Proof-of-Works are considered valid.

The target \(t\) is based on difficulty \(d\) which meets

\[t = \frac{2^{256}}{2^{32} \cdot d}-1\]

means that the easiest possible target \(t_{max} = 2^{224}-1\) (system parameter) is when \(d = 2^0 = 1\)

Challenge: Blockchain Forks

Since Proof-of-Work is a probabilistic process,

it is possible that different nodes broadcast their found blocks at the same time

Type

  • Unintended Forks (probabilistic process)

  • Intended Forks (essential tool to upgrade blockchain)

Solution: Longest Chain Rule

The solution to unintended forks used in Bitcoin is Longest Chain Rule

Process

  • Miners randomly picks one of the longest branches they are aware of to work on

  • Every time there is a new longest chain,

    all honest miners switch to this branch orphaning shorter ones

  • Probability that a fork survives drops of exponentially with each new mined block

  • Eventual Consistency

    To consider a block finalized, it is recommended to wait until several blocks have been mined on top of it

    In Bitcoin, 6 blocks (about 60 min) is recommended

Note:

Longest Chain Rule means that anyone controls > 50% hashing power will control the Bitcoin

hashing power is as a proxy to security requirements since the size of \(n\) and \(f\) is unknown

In Bitcoin, the required hashing power to mine a block in \(b\) second is

\[p = \frac{2^{32} \cdot d}{b}\]

Putting Everything Together: Nakamoto Consensus

Process

Given the length of blockchain \(l\)

  1. Gather transactions from the network into a block \(B_l\)

    including a hash pointer to a randonly-chosen longest chain

  2. Brute-force search a nonce in the block header of \(B_l\) until

    \[H(B_l) < t\]

    where \(H\) is a Puzzle-Friendly CRyptographic Hash Function (CRHF)
    and \(t\)is a target value which represnets the difficulty of computational puzzles

  3. Once found, broadcast \(B_l\) with the specfic nonce as Proof-of-Work to the rest of network

Attack: 51% of Hashing Power

If someone has 51% of hashing power (centraliztion), he/she can take over this cryptocurrency

  • Undermining Convergence: Fork the chain and double spend

  • Undermining Fairness: Reject blocks of all other miners

  • Undermining Liveness: Demand high transaction fees + Censor Transactions

However, 51% Attacks are not common in practice

  • All attacks are highly visible (broadcast)

  • Risk that currency loses value

  • Mining hardware is illiquid: high entry costs and no salvage value

Attack: Selfish Mining

  • If you get lucky and and find a block then withhold it,

    which means that you do not tell everyone immediately about it to engage in selfish mining

  • If you can mine new blocks fast enough on top of yours,

    then honest miners waste their hash power extending the shorter chain

Proof-of-Work Mining Evolution

Energy Requirements

Cheap Eletricity & Good Network & Cool Climate

  • Embodied Energy

    For manufacturing of chips and other hardware

  • Electricity

    For the actual operation of the mining devices

  • Cooling Energy

    For the protection of the mining equipment

Mining Equipments

  CPU GPU FPGA ASIC
Throughput \(2^{24}\) H/s \(2^{27}\) H/s \(2^{30}\) H/s \(2^{46}\) H/s
Advantages None Easy to buy and set up
Parallel ALUs
Drive many from one CPU
Overclock		 Better performance than GPUs
Good cooling
Extensive customization and optimization		 Fastest in history
Designed to be run constantly for life
Disadvantages Slow
Expansive		 Poor utilisation of hardware
Poor cooling
Large power draw		 Higher power draw than GPUs
High level of expertise required
More expensive
Marginal performance/cost advantage		 Designed only for Bitcoin
Need significant expertise
Need long lead-time

CPU - Central Processing Unit
GPU - Graphical Performance Unit
FPGA - Field Programmable Gate Array
ASIC - Application-Specific Integrated Circuits

Mining Pool

Definition

Pool participants all attempt to mine a block with the same coinbase recipient

which in practice is usually a key owned by the pool manager

Distribute Revenue

which can be based on

  • Per Share

    how much PoW shares they contribute minus a cut for the pool manager

  • Proportional

    since last block (Lower risk for pool manager + More work to verify)

  • Per Last \(n\) Shares

    Minimize “Pool hopping”

  • “Pool-hopping”

    The practice of mining in a pool only during the good times, and leaving during the bad times

    Can get more out of the pool than the value they contribute to it,
    increasing their rewards at the expense of other miners

    which is common in Proportional Distribution Method

Features

  • Advantages: Make mining revenue more predictable and enable smaller miners to still contribute

  • Disadvantages: Lead to centralization.

Proof-of-X: Variants and Alternatives

Ethereum 2.0 Solution: Proof-of-Stake

Idea

Prove your investment in the system to gain voting power and be allowed to participate in consensus

Challenge

  • Nothing-at-Stake: Work on all available forks to ensure/maximize profits (consistency issue)

  • Grinding: Exploit the fact that blocks are cheap to produce to influence consensus (fairness issue)

  • Long-Range Attacks

    Bribe stakers for their old keys to roll back many blocks and create valid forks (consistency and safety issues).

Upgrading Decentralized Systems

Situation

  • Everyone agrees to use a new signature scheme for OP_CHECKSIG

  • Flag Day

    Everyone agrees that at a given block height

    all transactions before are valid using old OP_CHECKSIG

    all transactions after must use the new OP_CHECKSIG

Different Situation 1: Hard Forks

Some miners do not upgrade in time called Hard Forks

because block produced before and after adoption of the decision are incompatible with each other

Think Deeply

Some full nodes do not upgrade in time

  • Full nodes are absolutely essential to the security of the system

    but cannot be trusted to all update in sync

  • Full nodes that do not change over to the main chain can be vulnerable to attacks

    and form a split currency which threatens economic stability

Real World Example

  • Bitcoin Cash

  • Ethereum Classic

  • Monero

Different Situation 2: Soft Forks

Some people agree to change the block size to 0.5 MB

can be one specific case of Soft Forks

Problems in Backwords Compatibility

  • People who have changed into smaller block size will reject blocks with old rules

  • People who have not changed will accept blocks from the changed people

Still form a split currency which threatens economic stability

Governance

Two important layers in cryptocurrency communities

  • Infrastructure

    Decentralized payment system based on global peer-to-peer network

  • Developers

    Small groups of software engineers

    who have been entrusted with key roles for the development of the technology

Not clear who gets to vote and makes decisions

You may also enjoy