Skip to content

Plompiler: Merkle trees path proofs for trees of arbitrary arity - Fixes #61

Miguel Ambrona requested to merge alocascio-miguel@arity-n into master

Support and tests for proving knowledge of membership in a Merkle tree of arity n:

Relation:

  • Public input: root
  • Private input: leaf + leaf position + (n-1) hash-witnesses per level in the tree

TODO: Study whether we can have trees of arity n = 4 with only 1 iteration of Poseidon. That would require redefine Poseidon such that we do not pad the input (padding is usually performed to support arbitrary length inputs and avoid prefix attacks, under the promise that never more than 4 values (or exactly 4) will be hashed, padding may be not necessary.)

Edited by Marco Stronati

Merge request reports