scratchpad of various design considerations

[gubsheep]

1. are leaves just field elements, or do we provide some convenience functions for people to store arbitrary data that we then hash into the field? currently to keep the protocol simple we are just going to go with field elements, and assume that any sort of hash digest stuff will happen outside (app developer chooses how to do this).
2. multiset (i.e. forced sorting order) vs. array. multiset means that merkle trees are strictly considered to be accumulators of sets, and prevents duplicate multisets from existing (not sure that this is a bad thing). array gives strictly more affordances than multiset, in particular the ability to batch inclusion proofs on contiguous subsequences (i.e. if you're using pairs of adjacent leaves as [address, balance] tuples) and assign semantic meaning to ordering of leaves. seems like there isn't any reason to choose multiset over array, so just go with array
3. when creating a tree on merkleroots.xyz, you must provide n leaf nodes
   option 1: n may be any positive integer (complete left-aligned binary tree)
   option 2: n must be a power of 2 (perfect binary tree but variable depth)
   option 3: n must be a protocol-constant power of 2 (perfect binary tree, constant depth)

@stevenhao: i think i support option 1 since it's most flexible. users who wish to use [perfect] binary trees for circom convenience can do so by manually padding their tree with a value they know to be safe. we can also provide api shorthand for this (e.g. {leaves: [...], size: 1024, padElt: 0 })
also, users who don't want to use perfect binary trees can use the trick where you check if any hash along the path is equal to the desired root: https://github.com/doubleblind-xyz/double-blind/blob/master/circuits/merkle.circom#L40

[abhilashi]

@gubsheep @stevenhao wondering if you had thoughts on

• ways to represent changing Merkle trees of fixed size with updating leaves for e.g BAYC NFT holders list.
• making these trees accessible to DAPPs where ZK proofs are not required but correctness of the tree itself is very important for e.g a grants DAO proposal reviewer would want to accumulate reputation on his address and also receive payouts on the same (doesn't necessarily need pseudonymity)
• on-chain integration will be like the way Oracles work? are you thinking of more native integrations?