Hashcash for proving set membership
Algorithms like merkle trees and bloom filters allow you to take a group of data items and construct a unique fingerprint of the set. The fingerprint can then be used as a way to prove that some or all members in the group are part of that “fingerprint.”
These constructs are useful and you seem them used a lot in blockchains. The issue for me with these data structures is really the size of the meta data relative to the set size: Bloom filters suck because they only compress the original data like 30%; Merkle trees suck because you still need to retain a shit-load of meta-data to be able to construct proofs.
I think in some situations you might already have a large list of candidates and you want to compactly see if a candidate is in a set. I’ve been thinking about this problem today and I actually think that hashcash might be the solution here. The idea would be to generate an IV that...
Continue reading →