My query: What knowledge construction or algorithm may I exploit to resolve the next set membership drawback effectively?
Think about I’m producing a random 32-bit integer each second, and including it to an inventory of N integers. Think about that every time I generate an integer, I ship it (and another data I may need easy accessibility to) off to a shopper. Later, the shopper will submit an integer (together with another data I’ve given it), and I need to have the ability to shortly decide if a given integer has ever appeared in my set, however I need to do it in fixed time, utilizing a small, fixed quantity of reminiscence. In different phrases, I do not need to simply maintain all of my generated numbers in an inventory or hash desk and test the submitted integer in opposition to this listing. Ideally, including a quantity to this set is a constant-time operation. I don’t ever must delete numbers from the set.
Choice 1: I may use a bloom filter and add every quantity to the bloom filter. Sadly, the set membership check can be probabilistic, however I may make the filter sufficiently big to scale back my chance of a false constructive fairly low. I am open to this strategy, however need to know what different choices I may have.
Choice 2: I’ve been studying about cryptographic accumulators. If every of the numbers I used to be producing had been prime, I imagine I may use an RSA accumulator to retailer a single accumulator worth of fixed dimension. Every time I add a brand new prime to my set, I add it to the accumulator, then I generate its witness as properly and ship each the quantity and the witness to my shopper. Later, the shopper would submit the integer it’s testing and the witness, and I might be capable of shortly decide if the quantity being submitted is in truth a member of my set or not. Doable issues: I would like to have the ability to hash to a primary quantity deterministically. (Not the top of the world, however provides complexity) I feel I’ve to replace my witness values as I add new values to the accumulator. Lastly: My understanding of accumulators is rudimentary.
1: Would this be any simpler if subsequent values in my chain of numbers had been by some means dependent upon earlier values not directly? You might think about some type of non-cryptographic hash chain, whose present hash worth consists of sufficient details about its earlier values that it may shortly decide, “Yep, if my present hash worth is X, and also you submit Y, Y positively was a earlier member of my chain.”
2: If I perceive them accurately, accumulators appear to be a really space-efficient method to retailer units of prime numbers (and maybe different values), however within the literature all of them assume potential adversaries. In my case, I do not want my witness be be unforgeable, so I might suppose that may make the issue a lot simpler to resolve. Maybe it simply implies that I get to make use of smaller constants (so I haven’t got to make use of RSA-2048?). Or maybe this simplifies my drawback even additional?
3: What if the “random” values I used to be producing had been recognized to be growing, or had been merely timestamps? (I nonetheless must know if that exact timestamp had been ever used)
This appears loads like having numerous hash values in a Merkle tree or hash chain (blockchain), and wanting to have the ability to decide if a specific hash worth had been ever seen within the chain, with out having to retailer each worth that had been seen within the chain. I am hopeful that with the extra idea of producing a “witness” worth of some type to be saved together with the quantity, the server could make a membership dedication with a lot much less overhead than having to retailer the entire numbers.
This additionally appears just like a verifiable log or authenticated dictionary.