ECIP 1055: Flyclient - Succinct PoW Using Merkle Mountain Ranges
| Author | Zac Mitton |
|---|---|
| Discussions-To | https://github.com/ethereumclassic/ECIPs/issues/144 |
| Status | Draft |
| Type | Standards Track |
| Category | Core |
| Created | 2019-03-12 |
Simple Summary
The addition of a Merkle-Mountain-Range (MMR) root to blockheaders
Abstract
A block chain could be interpreted as a linked-list using hashpointers from each block to its previous block. A Merkle-Mountain-Range is a type of tree that, will allow every block to point back to all its previous blocks. This can be accomplished using only a single hashPointer in each block - the current MMR root. Adding this will allow proving the cummulative work of an entire chain in Olog(n) time, instead of the current O(n) time. In the case of ethereum, with small block-times, and over 7 million blocks and counting, this will open a ton of doors in the area light-clients, and data verification.
Motivation
The recent FlyClient paper and presentation at Scaling Bitcoin Represented a major breakthrough the ability to succinctly, and non-interactivly prove the cumulative work of a blockchain.
The current data structures in Ethereum (merkle-patricia-trees) were made with the sole purpose of allowing succinct verification of all the data. I have personally been working for some time on the missing tools to extract, send, and validate these proofs. This work is mostly done, but there is a problem:
Without a succinct way to verify work, there is nothing to verify these merkle proofs against.
A merkle proof can only verify against a hash that I already trust. The validation chain goes something like this for some contract data x:
xis proven to have existed in a particularstorageRoot_xstorageRoot_xis proven to have existed in a particularaccount_xacountis proven to have existed in a particularstateTree_xstateTree_xis proven to have existed in a particularblock_x
And merkle proofs end there: block_x unfortunately cannot be trusted.
There are 2 main strategies for verifying a block:
- Validate every transaction sinse genesis
- This takes a week on desktop and
- Requires the user to have the full dataset anyway, removing the need for merkle proofs in the first place.
- Is infeasible on mobile.
- Validating the work (of the entire chain)
- Relies on majority honest miner assumption
- currently requires all block headers
- currently requires validating every blockHeader’s PoW
The problem is that it ends there. And we still have nothing, if the person (or machine) validating cannot validate the block. The cost to produce such proofs is free; To validate blocks we cant use the same strategy. Blocks validate against a chain, which in turn validates through its proof of work. Currently the only way to do this requires 4gb of chain data. Thats way too much. We need something that can work within a few seconds.
FlyClient is that something, and adding an MMRroot to each blockheader is the protocol change that will allow FlyClient to work.
On a high level, it allows the verifier to sample a subset of blocks in a tree, rather than a full amount thought a linked list, improving the time-complexity from O(n) to O(log(n)). The sample subset can be made large enough such it is cryptographically infeasible to ever produce a false proof.
With this EIP, PoW can be proven in < 3 megabytes. This will hit a sweet spot, where for instance, mobile wallets, can request the latest cummulative work every time they are opened (no need to even “sync”). Users can finally verify data in a practical way (without a full-node). The proofs are even small enough for IoT devices.
This may also open doors for side-chains, state-channels, plasma, trustless bridges, atomic swaps, and the peer-to-peer light-client-protocols being worked on by the Geth and Parity teams.
This also solves EIPs 210, 1094, 641 - it gives the EVM a way to access to historic blockhashes. A transaction sender simply provides a merkle proof relating the historic hash against any of the last 256 blocks, and the block against its blockhash (available as op 0x40), with a size of ~864 bytes.
Specification
There is a consensus-breaking rule change proposed here, and then a bit of software around the change will be needed in order to take advantage of the new features. I think it would be best to keep this EIP as just detailing the rule-change, I will summeraize the other tools and link them
Consensus Rule Change
If block.number >= ISTANBUL_FORK_NUM then when constructing the block, set a 16th value blockHashesRoot in the header to the MMRRoot from the previous block.
This Root is defined by the combining all previous hashes into a Merkle Mountain Range (Peter Todd) using it’s block number as leaf index.
Implementation of this tree is up to the clients but its fairly simple and requires only an additional ~500mb (on disk) to a full/archive node.
The MMR structure uses a proccess of “bagging the peaks” in order to create a single root hash. However, this may be sub-optimal for our use case. I would like to ammend this to instead define each root as the hash of the concatonation of the mountain peaks. This will make building and verifying proofs much simpler without significantly changing the size of the proofs.
The structure can be implimented as an array. Only a log(n) number of read/writes are done for any operation. A put operation needs to be done durring each block validation by the client. About 600 gets need to be performed when one of these proofs is requested (however the client can cache the latest proof). There is exactly 1 valid FlyProof for the current tip (latest mined block).
The FlyCLient paper can be followed almost exactly. Find it herefor specs.
Missing from the paper is a specific way to attain the samples from the blockhash (used as random seed). For this process, I propose we use slice-sampling. This should be a very efficient algorithm as long as our probability density function is invertible. We may require a hash during each iteration (~600). This process is only required for building and verifying proofs, it is not required for instance, of miners.
Rationale
Backwards Compatibility
Test Cases
Implementation
The most obvious need is for a non-full-node to be able to request this Proof from a full-node. This should be done by adding an RPC method. The method will take no arguments and it should return an object with:
- The lastest blockHeader
- A list of the randomly selected ~600 blockheaders for the proof
- we need to create the standard deterministic way to pick the the blocks (using blockhash as seed) over the probability denisty function. I propose that we do something like this
- The 64 byte dataset (each) for verifying an ethHash (~2.4 MB)
- A list of proofNodes from the MMR (+”bag proof” nodes)
Copyright
Copyright and related rights waived via CC0.