Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

VIP: Merkle Proof Function #1391

Open
fubuloubu opened this issue Apr 8, 2019 · 6 comments
Open

VIP: Merkle Proof Function #1391

fubuloubu opened this issue Apr 8, 2019 · 6 comments

Comments

@fubuloubu
Copy link
Member

@fubuloubu fubuloubu commented Apr 8, 2019

Simple Summary

Built in function to generate and validate merkle proofs for vanilla Sparse Merkle Tree implementations.

Abstract

Implement a built-in function for computing merkle roots from uncompressed merkle proofs for the sparse merkle tree (SMT) data structure, such as those commonly employed for Plasma and Plasma Cash constructions.

Motivation

Merkle proofs are useful and awesome, and can be difficult to implement due to many considerations and different possible optimizations. Having a built in function similar to ecrecover would greatly simplify in generating these proofs in a gas-efficient way.

Specification

def calc_smt_root(key: uint256,            # key determines order of siblings at each height
                  leaf_hash: bytes32,      # hash_function(abi.encode(leaf))
                  proof: bytes32[N],       # proof array where 'N' is the SMT depth (static)
                  function=hash_function,  # configures the function used
             ) -> bytes32                  # Returns calculated root for above

where

N:

  1. A constant corresponding to the size of the trie.
  2. The maximum number is 256. The minimum is 1 (although this would not make much sense in practice).
  3. The choice of depth determines the number of members that the trie can track.

key:

  1. An integer where each bit corresponds to the decision to traverse the tree left (bitand(key, 2**k) == 0) or right (bitand(key, 2**k) > 0) at the k-th node in the tree.
  2. Must be at least N bits in size (uint256 works by default, but future datatypes may be added, e.g. uint32 for 32-depth trie)
  3. The LSB (least significant bit) corresponds to the leaf node decision (whether it's sibling is left or right in the tree hierarchy recursing up). This is bit 0 of key.
  4. The MSB (most significant bit) corresponds to the root node decision (whether it's sibling is left or right in the final recursion that produces the root node). This is bit N of key (the depth of the trie).

leaf_hash:

  1. A bytes32 hash corresponding to the hash of the leaf node, typically with the same hashing function that the proof generation process uses.
  2. leaf can be any arbitrary data structure. By convention, the data structure would be hashed according to it's ABI encoding, although that is not strictly required.

proof[N]:

  1. A static array (of size N) where each array element corresponds to the sibling of the node at depth k in the trie.
  2. proof is in root to leaf order. Element 0 corresponds to the root level sibling (root_hash := hash(left_node, right_node)), and Element N corresponds to the leaf level sibling.
  3. The algorithm would thus require traversing the provided proof in reverse order.

Additional considerations:

  1. The function only calculates the root hash from the provided key, proof, and leaf hash. Verification is left to the end user (Typically self.root = calc_smt_root(...) or assert self.root == calc_smt_root(...), "Proof does not validate")
  2. The user specifies which hash function to use (e.g. calc_smt_root(..., function=hash_function) where hash_function is one of keccak256, sha256, or any other built-in hash function that produces at 32-byte output)
  3. There is a built-in helper function for generating empty proofs (e.g. EMPTY_BRANCH: bytes32[N] = generate_empty_proof(empty_leaf_hash, N, function=hash_function) where)
  4. This specific implementation structure is already implemented in py-trie (by the author)

An example of using this would be

root_hash: bytes32
N: constant(uint256) = 32

def validate_root(root_hash: bytes32, key: uint256, leaf: int128, proof: bytes32[N]):
    leaf_hash: bytes32 = keccak256(leaf)
    assert self.root_hash == calc_smt_root(key, leaf_hash, proof, function=keccak256)
    # ... do actions!

Backwards Compatibility

New feature

Copyright

Copyright and related rights waived via CC0

@fubuloubu

This comment has been minimized.

Copy link
Member Author

@fubuloubu fubuloubu commented Apr 8, 2019

@jacqueswww @pipermerriam @davesque If you all agree with this proposed Specification, we can move this VIP to Approved and start implementation, since previous (#806) was already approved (but was under-specified)

@jacqueswww

This comment has been minimized.

Copy link
Collaborator

@jacqueswww jacqueswww commented Apr 8, 2019

👍 from me.

@pipermerriam

This comment has been minimized.

Copy link
Contributor

@pipermerriam pipermerriam commented Apr 8, 2019

I abstain, haven't spent time understanding this and am focused elsewhere at the moment.

@davesque

This comment has been minimized.

Copy link
Contributor

@davesque davesque commented Apr 8, 2019

I'll also abstain from this for the same reasons as @pipermerriam .

@fubuloubu fubuloubu added the Approved label Apr 22, 2019
@fubuloubu fubuloubu added this to To do in Release Candidate! via automation Apr 22, 2019
@fubuloubu

This comment has been minimized.

Copy link
Member Author

@fubuloubu fubuloubu commented Apr 22, 2019

Notes:

  • Analyze relevance of 2nd pre-image attack (walkthrough here), and add to documentation around leaf_hash if necessary
  • Add mention that key must be at least 2**N (not strictly uint256)
@fubuloubu

This comment has been minimized.

Copy link
Member Author

@fubuloubu fubuloubu commented Apr 22, 2019

Not necessary to add documentation since this algorithm does not allow one to control N (the depth of the tree), which is a necessary condition to perpetuate this attack (since we control how many iterations are done).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
4 participants
You can’t perform that action at this time.