When trie start supporting multiproof?

[felicityin]

A Merkle multiproof is a more efficient Merkle proof, for when it is necessary to prove the presence of a multiple elements that are in the same Merkle tree. Details: https://github.com/ledgerwatch/erigon/blob/devel/docs/programmers_guide/guide.md#multiproofs

When trie start supporting multiproof?

[jochem-brouwer]

We support verifying them (verifyRangeProof). Creating proofs is a WIP, see #2243.

[felicityin]

We support verifying them (verifyRangeProof). Creating proofs is a WIP, see #2243.

Thanks! But I want to prove the presence of a multiple elements that do not constitute an interval. Maybe this will meet my needs better: ethereumjs/merkle-patricia-tree#94. But it has not been merged yet.

[jochem-brouwer]

I assumed your erigon page was a page about multiproofs for intervals, but apparently there is also a way to support multiproofs for non-intervals? I will have to read the docs about this to see if this is actually possible. But in that case, this is not being worked on yet.

For the time being, would it also work to just batch createProof and then use this to provide proofs for multiple elements (this of course has duplicate elements)?

[felicityin]

I assumed your erigon page was a page about multiproofs for intervals, but apparently there is also a way to support multiproofs for non-intervals? I will have to read the docs about this to see if this is actually possible. But in that case, this is not being worked on yet.

For the time being, would it also work to just batch createProof and then use this to provide proofs for multiple elements (this of course has duplicate elements)?

There is a way to support multiproofs for non-intervals in Sparse Merkle Tree: https://arxiv.org/pdf/2002.07648.pdf. It is really useful.

[jochem-brouwer]

Very interesting, this sounds fun to implement!

[felicityin]

Very interesting, this sounds fun to implement!

Yes, it is.

[ScottyPoi]

@jochem-brouwer
This is different than the RangeProof work you're doing, right?
If so I will start looking into it.

[jochem-brouwer]

Yes: my current PR (i.e #2243) is about sequential proofs. This paper shows that it is also possible to prove for non-sequential proofs, so this is indeed diffferent.