Shorter Merkle proofs for Snapps

Resembling construction was published by farazhaider for Plasma some days ago. Thank you.

Let’s we represent the way to reduce Merkle proofs for Snapps.

Abstract

Below we will describe a way to reduce a proof size given by a Merkle tree. The way is based on a special - balanced approach to build the tree of hashes. The main idea is that keeping a balanced tree of hashes ensures fewer nodes count between the root and any element even in the worst possible case, so that makes a proof shorter.

Merkle trees

As a good and allied way to store data in zkSnarks is a sparse Merkle tree. The main idea of such tree is keeping the nodes for the whole space of all possible values. There are ways to optimize it on the implementation stage, but the proof part (the proof of including) seems to be too long and may take 160 or more hashes that are complicated to deal with.

This number can be reduced by choosing a different way to build the Merkle tree. As another possible way, we could choose a simple binary tree. Averagely, it has the depth depending on the number of elements, that is better. But the worst case may be even worse than in sparse Merkle tree with respect to the proof size that is still too expensive in use.

In order to resolve the problem of the worst case, we add balancing to the tree building process. As an approach, we chose an AVL tree as one of a possible and quite simple way to implement and use.

AVL tree approach

AVL tree is a binary tree that changes its structure after adding or removing an element, in order to keep the total depth (the maximal distance between the root and a node) as less as possible. On the picture, there are examples of balanced and unbalanced trees.

In AVL tree the balance is reached by two types of rotations in the nodes. For example, if an element is added (or removed), we check each node in the path to the element for the difference in depths of its left and right sub-trees. If the difference is 2 we make a rotation according to the rules invented and discovered by Adelson-Velsky and Landis (this is why such tree is called AVL). There four types of rotations:

After the correct rotation for the node, its depths difference will be 0 or 1, thus the tree will be balanced.

Ordered balanced Merkle tree

Supposing, we use AVL approach to build the Merkle tree.

Let’s demand following properties of our construction:

• the difference between heights of left and right subtrees is equal {-1, 0, 1}
• each leaf has a unique ID and left leaf’s ID is lesser then right.

N(h) is the capacity of the state in the worst case.
It is obvious, that N(1)=1 and N(2)=2.
Also, N(h)=N(h-1)+N(h-2) - it is maximal unbalanced.

We see that N(h) = F_{h+1} - it is Fibbonaci number.

Talking about the sparse Merkle tree, the proof size does not depend on the number of elements, it depends on the size of the values’ space. We can imagine sparse tree as a fully balanced tree that has almost all leaves (places for elements) empty, this is why it is called sparse. In spite of it, ordered a balanced Merkle tree keeps only leaves with inserted elements. Obviously, that’s why the sparse Merkle tree has longer proof size.

For 160bit address space the length for Merkle proof for SMT is 160 and length for OBMT it is 58 (for 2^40 memory cells) and 44 (for 2^30 memory celles).

This result may be useful for snapps, allowing to reduce the number of constraints in 3-4 times.

UX for snapps using OBMT

Snapps based on OBMT memory must have two different kinds of state modification:

1. memory defragmentation
2. properly, snapp execution

At memory defragmentation step we can add or remove cells with zero value and rotate the OBMT.

Snapp can be split into two snarks. Then we can combine several execution blocks of the snapp with one defragmentation block.

We represent circuit for defragmentation gadget in pseudocode (unoptimized at the low level, just a draft).

external constant MAX_HEIGHT

struct Rotation
  uint2 type
  uint160 [4] nodes
end

struct Proof
  uint160 [MAX_HEIGHT] data
  bits[MAX_HEIGHT] way
  bits[MAX_HEIGHT] included
end

struct Item
  uint160 id
  uint160 data
end


gadget insertRightAndRotate(Proof proof, uint160 leaf1, uint160 leaf2, Rotation rotation) returns(uint160):
  let rotationTo := hash(hash(rotation.nodes[1],rotation.nodes[2]), hash(rotation.nodes[3], rotation.nodes[4]))
  let rotationFrom := case4(
    rotation.type, 
    hash(hash(hash(rotation.nodes[1],rotation.nodes[2]), rotation.nodes[3]), rotation.nodes[4]),
    hash(hash(rotation.nodes[1], hash(rotation.nodes[2], rotation.nodes[3])), rotation.nodes[4]),
    hash(rotation.nodes[1], hash(hash(rotation.nodes[2], rotation.nodes[3]), rotation.nodes[4])),
    hash(rotation.nodes[1], hash(rotation.nodes[2], hash(rotation.nodes[3], rotation.nodes[4])))
  )
  let top := hash(leaf1, leaf2)
  for i = MAX_HEIGHT .. 1:
    let _top := orderedHash(proof.way[i], proof.data[i], top)
    let __top := rotationTo if _top == rotationFrom else _top
    let top := case2(proof.included[i], top, __top)
  end
  return top
end


gadget addLeft(uint160 rootFrom, uint160 rootTo, uint160 id, Proof pleft, Item ileft, Proof pright, Item iright, Rotation rotation):
  constraints uint(pleft.way) == uint(pright.way)-1
  constraints merkleProof(pleft, hash(ileft)) == rootFrom
  constraints merkleProof(pright, hash(iright)) == rootFrom
  constraints ileft.id < id
  constraints id < iright.id
  constraints rootTo == insertRightAndRotate(pleft, hash(ileft), hash(id, uint160(0)), rotation)
end

As we can see, there are 3 Merkle proofs for insertion (and two for deletion). Insertion or deletion of cells is more unusual procedure than reading or writing values inside the snapp.

Even if we add the cell before each read operation inside the snapp, we have a number of constraints similar to SMT case. For more used operations (for example, transfer of tokens from cell to cell) we have advantage ~3.5 lesser length of Merkle proof.

Authors

snjax

fomalhaut88