…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.
Contain every single block with all transactions Full capabilities: creating transactions, … Bitcoin: Currently ~185 GB
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
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/…
Follow chain, but download only headers – not transactions. Bitcoin: Header = 80 bytes, ~43 MB entire chain.
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 computesMerkleRoot' = 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.
Simple blockchains with key-value pairs Databases Version Control Systems Filesystems … →Authenticate a small amount of data in a very large dataset
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?
Blockchain with turing-complete smart contracts Contract accounts can get into arbitrary states →No longer just key-value state pairs
Transactions Receipts The effect of the block StateMerkle Tree representing entire state of network(i.e. each account)
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?
Full node finds object and returns it with Merkle branch Light client verifies by computing Merkle root Mostly doable in O(log(n))
Full node returns "Balance of A: 13 + Branch up to root" Light client computes the Merkle root from this And compares MerkleRoot' == MerkleRoot
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.
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