2
$\begingroup$

I am looking for a solution for a very specific problem, I have one, but I am not statisfied with it and it feels there must be a much more efficient way to do this.

I have a hashed value of 256 bits. I want to proof if it is NOT part of a given set. IE a ban list. The solution must be unforgable given some commited value.

The solution I have now is pretty straight forward. I use balanced merkle tree with a depth of 256 with a poseidon hash function (128 bit, I want to use it in ZK). I intialized the tree with 0 values, which makes it easy to pre-compute the initial merkle root. When I want 'ban' a value. I use the 256bit value as the leaf index and flip the value from 0 to 1 and then recalculate the root. A proof that a certain value is 0 is easily computed but the merkle proof is rather large (256 * 128 ~= 4kb) and takes quite some hashing to compute, especially in ZK. However, the main issue I have is that the values being 'banned' are random 256 bit numbers. So as I ban them I need to store roughly the same amount (4kb) per banned 256bit value. This method needs to work for billions of values so it adds up.

Since I only need to 'bitflip' a value being true or false it feels like there must be some more efficient solution. I explored some but they seem to increase the proof size significantly.

Note that I am the party that generates the possible values to be banned!

With that knowledge I looked into bloomfilters, since I can add nonces to prevent bloomfilter collisions, however, to gain a reasonable amount I would need a sizable bloomfilter. For the storage requirements this is a very very good option, and might be included as part merkle tree for speedier processing. But the significantly increases the size requirement of the proof as I would need to include the entire bloomfilter as part of the proof (note this is in ZK, so size really matters).

I have also looked at Ethereums Patricia Merkle Trie but that is not efficient either. Their new Verkle tree approach based on pedersen commitmets seems promising but it seems to be focused on some value being part of a larger state tree, ie address lookups and is mainly to proof something IS part of a set, however, I want to proof something is NOT part of a set (maybe I can compute it differently?).

The solution I have now works, but I was wondering if there are some other methods known that can do this more efficiently with smaller more efficient proofs AND lower overhead requirements on the prover (ie knowning the state of merkle tree)

$\endgroup$

1 Answer 1

0
$\begingroup$

How big can the ban list be? You say it has to work for billions of values, but it's not obvious if the ban list is also expected to have the same order of magnitude.

Universal accumulators could work as some can provide both membership and non-membership proofs, but the size of the ban list could be an issue (esp. with pairing-based accumulators, most of which assume an upper bound of accumulated values) depending on the use case.

Verkle trees can be adapted to support non-membership proofs and the proof size remains small even with densely populated trees - see this question and this article.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.