Blockchain: Technical Details

Blockchain Network

P2P network with multiple nodes,
each has a replica of the ledger DB.

Reading from the DB

Query past / current state of the ledger to a node.

Writing to the DB

Sending operation \(O\) to a node:

  • Transactions
  • Account creations, etc

Operations spread into the P2P network.

Block creation

Block proposer (or miner) chooses operations found in his node and form a block of them.

\[B = [O_{v_1},..,O_{v_m}]\]

The validator release \(B\) to the network.

Ledger Update

Each node updates its state \(S\) by applying \(B\).

  • \(S_0 = ∅\)
  • \(S_n = B_n(S_{n-1}) = B_n(B_{n-1}(..(B_1(S_0))..))\)

where

  • \(B(S) = O_{v_m}(O_{v_{m-1}}(..(O_1(S))..))\)
  • \(B = [O_1, .., O_{v_m}]\)

This forms a “blockchain”:

\[S_0 \stackrel{B_1}→ S_1 \stackrel{B_2}→ .. \stackrel{B_{n-1}}→ S_n \stackrel{B_n}→ ..\]

Cryptographic Integrity

More precisely, \(O\) and \(B\) are digitally signed
to avoid forgery:

  • \(O = (o, sign_u(o))\) where \(o\) is a raw operation.
  • \(B_n = (b, sign_v(b))\) where \(b = ([O_{v_1},..,O_{v_m}], H(B_{n-1}))\)

Digital signing \(sign_x\) and the hash function \(H\) are assumed to be secure.

Conflicts

Chain branches when multiple miners propose more than one blocks:

       \(↗︎\stackrel{B_{n+1}}→ S_{n+1} \stackrel{B_{n+2}}→ S_{n+2} \stackrel{B_{n+3}}→ S_{n+3}\)

\(.. \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n}\)

       \(↘︎\underset{B'_{n+1}}→ S'_{n+1} \underset{B'_{n+2}}→ S'_{n+2} \underset{B'_{n+3}}→ S'_{n+3}\)

Attack: Double Spending

You can steal exchanging tokens in the both branches:

               \(💰\)
              \(↗︎\)
       \(↗︎\stackrel{B_{n+1}}→ S_{n+1} \stackrel{B_{n+2}}→ S_{n+2} \stackrel{B_{n+3}}→ S_{n+3}\)

\(.. \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n}\)

       \(↘︎\underset{B'_{n+1}}→ S'_{n+1} \underset{B'_{n+2}}→ S'_{n+2} \underset{B'_{n+3}}→ S'_{n+3}\)
              \(↘︎\)                \(💰\)

Proof of Work (PoW)

Blocks must be with an answer to a hash puzzle \(Q\):

\[B_n = (b_n,sign_v(b_n),A_n) ~\mbox{where}~ H'(A_n) = Q_n\]

  • \(Q_n\) is generated from \(b_{n}\).
  • \(H'(\cdot)\) is a weak hash function.

The nodes choose the longer chain, which used more computation power (or gathered votes):

\(.. \stackrel{B_{n}}→ S_{n}\stackrel{B_{n+1}}→ S_{n+1} \stackrel{B_{n+2}}→ S_{n+2} \stackrel{B_{n+3}}→ S_{n+3} \stackrel{B_{n+4}}→ S_{n+4}\) 😄

    \(\color{gray}{\underset{B'_{n+1}}↘︎ S'_{n+1} \underset{B'_{n+2}}→ S'_{n+2}}\)😢

Incentivize Miners

The cost of solving hash puzzles is covered by rewards.

  • Block reward \(r\), newly minted.
  • Transaction fee: \(f\) in \(o = (\mbox{raw operation},~ f)\),
    set and paid by the issuer of \(o\)

By proposing a block \(B\), the validator can earn

\[r + \Sigma_{o\in B}f_o\]

Nakamoto Consensus

  • Rewards are only available in the branch. No incentive to bet on shorter branches.
  • Longer branches might be overridden by shorter ones, but the probability decreases exponentially as it grows.

\[.. → S_{n-1} \stackrel{💬\\B_{n}}→ S_{n}\stackrel{B_{n+1}}→ S_{n+1} \stackrel{B_{n+2}}→ .. \stackrel{💰\\B_{n+6}}→ S_{n+6} → ..\]

  • User sends tokens to Exchange at \(B_n\) to change them to USD.
  • Exchange pays out the USD after \(B_{n+6}\) to User in return, when it is sure \(B_n\) cannot be taken over.

51% Attack

Someone with more than 50% of computation power can take over the chain to perform double spending.

\(.. → S_{n-1} \stackrel{💬\\B_{n}}→ S_{n}\stackrel{B_{n+1}}→ .. \stackrel{💰\\B_{n+6}}→ S_{n+6}\)

        ⬇︎️

\(.. \color{gray}{ → S_{n-1} \stackrel{💬\\B_{n}}→ S_{n}\stackrel{B_{n+1}}→ .. \stackrel{💰\\B_{n+6}}→ S_{n+6}}\)😮

 \(↘︎S'_{n-1} \underset{B'_{n}}→ S'_{n}\underset{B'_{n+1}}→ .. \underset{B'_{n+6}}→ S'_{n+6}\underset{B'_{n+7}}→ S'_{n+7}\underset{B'_{n+8}}→ S'_{n+8}\)😈

51% Attacks are Real

Minor PoW blockchains, which requires less hash power, are targets of 51% attacks:

  • Verge (XVG), 2M USD (2018-04 and 2018-05)
  • Bitcoin Gold (BTG), 18M USD (2018-05)
  • Monacoin (MONA), 90K USD (2018-05)
  • ZenCash (ZEN) 700K USD (2018-06)

Blockchain: Technical Details

Typical PoW

  • Operation injection
  • Block creation of operations, and upload
  • Ledger update by blocks
  • Branching by conflicts
  • PoW to reduce and choose branches
  • 51% attacks