Hermez 1.5 - Merkle Tree spec

This document describes the Merkle Tree that will use Hermez 1.5. Basic understanding on how Merkle trees and Merkle proofs work is assumed.

Glossary

• Key: position of a leaf in the tree.
• Branch: node of the tree that have children insted of data, e.g: a non-leaf node
• Leaf: node of the tree that stores data

Topology

• Hexary (16 child per branch, could be 8 if deemed necessary to reduce complexity in zk circuits)
• Number of levels doesn't have to be fixed, because STARK allows to compute it dynamically. Max levels is 64 due to key size. At least 32 levels (we may consider using more levels to avoid collisions. Amount of leafs = 16**levels. 32 levels ~= 3.4e38)
• Sparse

Keys and paths

A key is the index of a leaf. They've to be generated in a way that there are no collisions and are deterministic (same leaf always have the same key). Therefore a convinient way to generate keys is by hashing some content of the leaf that uniquely identifies it. Poseidon hash will be used for that purpose (could be changed).

A path is a list of directions that enable navigation from root to a given leaf. Paths are derived from keys by taking the last 4bits * (Levels-1), each 4 bit group will represent a number (values 0 to 15) that indicates which is the child of the branch that follows the path to the leaf.

Since poseidon hashes output 253,59 bits, and 4 bits are needed to encode each direction, the tree can have a maximum of 64 levels: 253.59bits / 4bits = Levels-1.

Keys are Finite Field Elements.
Values are numbers between 0 and 2^256-1 (uint256).

Example

Given a tree with 8 levels (for example purposes, the actual implementation will have at least 32 levels), and the following key, the path will be this:

Key (in Little Endian encoding): 0x21665a9251173584a82d950b0ea5f3c19297fdce2383ef325d3c01cb30191d10

Path:

Graphical representation:

Reference implementation

Jordi has done js implementation here: hermeznetwork/zkproverjs

Example of MT creation

Initially we have an empty MT, that has zero value as a root hash.
For the example purpose it has 5 levels and keys are 2 bytes long (4 bits * 4).

Step 1

Adding first leaf to sparse MT:

• Key: 0x4321
• Value: 0x66

Leafs:

Merkle root hash equals to the hash of the leaf node, which is H[1,1234,66,0,0..0], since there's no other leaves in the tree. keyPrime equals to Path.

Graphical representation:

• Yellow nodes need (re)calculation

Step 2

Adding second leaf:

• Key: 0x4421
• Value: 0x77

Leafs:

Graphical representation:

• Yellow nodes need (re)calculation

Step 3

Adding third leaf:

• Key: 0x6541
• Value: 0x88

Leafs:

Graphical representation:

• Yellow nodes need (re)calculation

Step 4

Adding fourth leaf:

• Key: 0x5541
• Value: 0x99

Leafs:

Graphical representation:

• Yellow nodes need (re)calculation

Nodes

Hermez 1.5 has 2 categories of nodes:

• Leafs: node of the tree that instead of pointing to other nodes, it holds data. There is 4 types of leafs:
  • Nonce: Counter of transactions made by an account
  • Balance: amount of Ether holded by an account
  • SC code: code of a smart contract
  • SC storage: persistent data stored by a smart contract
• Branches: node of the tree that point to other nodes.

Generic schema to generate node hash: poseidon.Hash(1, keyPrime, V0, V1, V2, V3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
where:

• keyPrime - is a remaining part of the key, depends on a position of the Leaf in the Tree
• V0, V1, V2, V3 - parts of Value split in 64 bit chunks

  Value, 256 bits
  MSB			LSB
  64 bits	64 bits	64 bits	64 bits
  V3	V2	V1	V0

• 0 .. 0 - zero padding to get 16 inputs to poseidon hash in total, in this case 10 additional zero values

Branch (middle node)

• Value: array of 16 poseidon hashes
• Key: -
• Hash: poseidon.Hash(hashChild0, hashChild1, ..., hashChild15)

Proofs

Proofs are very similar to the implementation used in Hermez 1.0.

Proof of leaf inclusion in Merkle Tree

This type of proof is needed to prove that a key in Merkle Tree has specific value.

Structure of the proof from a reference implementation:

{
    root: root,
    key: key,
    value: value,
    siblings: siblings,
    isOld0: isOld0, // true if leaf hash is 0
    insKey: insKey,
    insValue: insValue,
}

Proof of leaf update

This type of proof is needed as an input for the ZKP, to prove the transiction from one state state A to the next one state B.

Structure of the proof from a reference implementation:

{
    oldRoot: oldRoot,
    newRoot: newRoot,
    key: key,
    siblings: siblings, // array [level][keys[level]] bytes,
    insKey: insKey,
    insValue: insValue,
    isOld0: isOld0, // true if previous leaf hash was 0
    oldValue: oldValue,
    newValue: value,
}

Hermez specific Leaf Types

Balance

• Value: unsigned integer of 256 bits
• Key: key is generated by hashing the Ethereum address and a constant with value 0 using Poseidon: key = poseidon.Hash(ethAddrBytes[0:8], ethAddrBytes[8:16], ethAddrBytes[16:24], 0, 0..0)
• Hash: poseidon.Hash(1, keyPrime, balanceBytes[0:8], balanceBytes[8:16], balanceBytes[16:24], balanceBytes[24:32], 0..0)

Nonce

• Value: unsigned integer of 256 bits
• Key: key is generated by hashing the Ethereum address and a constant with value 1 using Poseidon: key = poseidon.Hash(ethAddrBytes[0:8], ethAddrBytes[8:16], ethAddrBytes[16:24], 1, 0..0)
• Hash: poseidon.Hash(1, keyPrime, nonceBytes[0:8], nonceBytes[8:16], nonceBytes[16:24], nonceBytes[24:32], 0..0)

SC Code

• Value: byte array that represents the compiled code

• Key: key is generated by hashing the Ethereum address and a constant with value 2 using Poseidon: key = poseidon.Hash(ethAddrBytes[0:8], ethAddrBytes[8:16], ethAddrBytes[16:24], 2, 0..0)

• Hash:

  • Splitting the bytecode into chunks of 15 elements (16 the first one) and hashing the 15 elements and the hash of the previous chunk
  • Pad 0 bytes until fulfill the poseidon inputs
  • poseidon.Hash(1, keyPrime, byteCodeHash[0:8], byteCodeHash[8:16], byteCodeHash[16:24], byteCodeHash[24:32], 0..0)
  • example:

  ​​​​bytecode: "0x1234"
  ​​​​only one poseidon with 16 elements
  ​​​​[
  ​​​​   "123400000000000...000", (31 bytes) (element 0)
  ​​​​   "000...00000000000000 0", (31 bytes) (element 1)
  ​​​​   "000...00000000000000 0", (31 bytes) (element 2)
  ​​​​   ...
  ​​​​   "000...00000000000000 0" (31 bytes) (element 15)
  ​​​​]
  

SC storage

• Value: 256 bits that will be interpreted by the SC
• Key: key is generated by hashing the Ethereum address and a constant with value 3 and the position of the storage that is being accessed: key = poseidon.Hash(ethAddrBytes[0:8], ethAddrBytes[8:16], ethAddrBytes[16:24], 3, storagePositionBytes[0:8], storagePositionBytes[8:16], storagePositionBytes[16:24], storagePositionBytes[24:32], 0..0)
• Hash: poseidon.Hash(1, keyPrime, valueBytes[0:8], valueBytes[8:16], valueBytes[16:24], valueBytes[24:32], 0..0)