Blockchain

…a distributed ledger without the need for a trusted, centralized entity.

…consensus is achieved using Proof-of-Work, Proof-of-Stake, Proof-of-Authority, or some other Byzantine agreement protocol.

Full Nodes

  • Contain every single block with all transactions
  • Full capabilities: creating transactions, …
  • Bitcoin: Currently ~185 GB

The problem

  • Smartphones?
  • Cars?
  • Washing Machines?

Simplified Blockchain Header

source: https://blog.ethereum.org/2015/11/15/merkling-in-ethereum

Simplified Blockchain Header

source: https://blog.ethereum.org/2015/11/15/merkling-in-ethereum
source: https://hackernoon.com/merkle-trees-181cb4bc30b4
source: https://hackernoon.com/merkle-trees-181cb4bc30b4
source: https://hackernoon.com/merkle-trees-181cb4bc30b4
source: https://hackernoon.com/merkle-trees-181cb4bc30b4

  • Every change affects root
  • Integrity of entire dataset is encapsulated in root

  • →Only necessary to store root hash
  • →Recalculating root hash is efficient
  • Validating that a hash is part of a tree: Merkle Proofs

Scenario

I made a transaction T and want to know:

"Was T included in the latest block?"
(i.e. it went through)


Option 1:

  • Set up full node, download entire chain
  • In each block search through transactions
  • → Not feasible for Smartphones/IoT devices/…

Option 2

  • Follow chain, but download only headers – not transactions.

  • Bitcoin: Header = 80 bytes, ~43 MB entire chain.

A better Idea

Option 2

→ In Bitcoin the tree typically has hundreds transactions/branches

Option 2

→ In Bitcoin the tree typically has hundreds transactions/branches

Simple Payment Verification (SPV)

  • Ask a full node:
    "Was T in the last block?"
  • Full node checks transactions and responds:
    "Yes, here's the path from transaction up to root hash"
  • Light client computes
    MerkleRoot' = Hash(T) + receivedPath
  • T is in block if:
    Computed MerkleRoot' == MerkleRoot in local Chain

  • →No need to trust anyone!
  • →You "just" have to be on the correct (i.e. longest) chain.

Works very well for…

  • Simple blockchains with key-value pairs
  • Databases
  • Version Control Systems
  • Filesystems

→Authenticate a small amount of data in a very large dataset

Shortcomings

Not possible to proof anything about current state.

  • What is the balance of an account?
    →You can ask full nodes, but no way to verify.

  • Who is the owner of some digital asset?

  • What is the status of a smart contract?

Ethereum

  • Blockchain with turing-complete smart contracts

  • Contract accounts can get into arbitrary states

  • →No longer just key-value state pairs

Ethereum: Three Merkle Trees in Header

  • Transactions

  • Receipts

    The effect of the block
  • State
    Merkle Tree representing entire state of network
    (i.e. each account)

Possibilities

  • Was transaction T included in this block?

  • Fetch me all events of type T emmited by address A in the last two weeks

  • What is the current balance of an account?

  • Does account with address A exist?

How?

  • Full node finds object and returns it with Merkle branch

  • Light client verifies by computing Merkle root

  • Mostly doable in O(log(n))

Example

  • Full node returns "Balance of A: 13 + Branch up to root"

  • Light client computes the Merkle root from this

  • And compares MerkleRoot' == MerkleRoot

There is more…

Merkle State Transition Proofs

Pretend to run this transaction on this contract. What would the output be?

Merkle Patricia Tree

Merkle Trees are not ideal for insert/delete/etc.

Further references

Vitalik Buterin – Merkling in Ethereum

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/

Ethereum Spec – Light client protocol

https://github.com/ethereum/wiki/wiki/Light-client-protocol

"The Paper"

https://bitcoin.org/bitcoin.pdf

SELECT * FROM `questions`;