Binary Sparse Merkle Tree Update Proof (Proof of new digest) (32 levels -> max ~4mld leafs) (Zokrates Zero-Knowledge Proof)

binary-sparse-merkle-tree-32-levels-update-proof.zok

import "hashes/poseidon/poseidon" as poseidon

const u32[32] powers_of_two = [
  1,
  2,
  4,
  8,
  16,
  32,
  64,
  128,
  256,
  512,
  1024,
  2048,
  4096,
  8192,
  16384,
  32768,
  65536,
  131072,
  262144,
  524288,
  1048576,
  2097152,
  4194304,
  8388608,
  16777216,
  33554432,
  67108864,
  134217728,
  268435456,
  536870912,
  1073741824,
  2147483648
]

def merkleTreeProof( \
  field root_digest, \
  field leaf_digest, \
  u32 leaf_index, \
  field[32] siblings \
) -> bool:
  field current_digest = leaf_digest

  for u32 i in 0..32 do
    field sibling = siblings[i]
    bool sibling_on_the_left = leaf_index & powers_of_two[i] == powers_of_two[i]

    field left = if sibling_on_the_left \
      then sibling \
      else current_digest \
    fi

    field right = if sibling_on_the_left \
      then current_digest \
      else sibling \
    fi

    current_digest = if sibling == 0 \
      then current_digest \
      else poseidon([left, right]) \
    fi
  endfor

  assert(current_digest == root_digest)

  return true

def merkleTreeUpdateProof( \
  field old_root_digest, \
  field old_leaf_digest, \
  field new_root_digest, \
  field new_leaf_digest, \
  u32 leaf_index, \
  field[32] siblings \
) -> bool:
  assert(merkleTreeProof( \
    old_root_digest, \
    old_leaf_digest, \
    leaf_index, \
    siblings \
  ))

  assert(merkleTreeProof( \
    new_root_digest, \
    new_leaf_digest, \
    leaf_index, \
    siblings \
  ))

  return true