Consider a DB with a large set of numbers, like hashcash tokens, where new numbers are constantly added(spent). Only numbers that has not been already added can be accepted. Is there a functional way to do this by some sequential operation on the numbers, so that only a single number X is needed to verify that a new number K has not been added before, i.e. a function like: Xn+1 = f(Xn,K) which will return zero if K was previously added? (Or where a small set of numbers can do the same job?)


migrated from crypto.stackexchange.com May 21 '18 at 12:19

This question came from our site for software developers, mathematicians and others interested in cryptography.

  • $\begingroup$ You state DB. Is it a specific DB? Can it be SQL or NOSQL? Are you really taking about collections? $\endgroup$ – paparazzo May 21 '18 at 18:12

There is no lossless way to compress a set of arbitrary numbers where the size of the set is unbounded to a fixed number of bits. Cryptography won't help with that.

If you're okay with the storage requirements growing linearly with the number of elements, then use a hash table. This method has no false positives or false negatives. Queries take $O(1)$ time.

If you want a fixed size and are okay with false positives then use a bloom filter. The more elements you add the greater the probability of false positives become.

If you can force the inputs to use a timestamp then you can reject attempts to add records with a timestamp too far into the past. You can then decide to remove all records from a database that are old enough to be rejected and still prevent double spending. (But if you remove the original record you can no longer test for its membership to the set.)

Hashcash rejects headers with dates more than 2 days in the past, so hashes older than 3 days can be deleted to save storage space while still preventing reuse.

  • $\begingroup$ You can combine the timestamp and Bloom filter too! Start a new Bloom filter every day; reject timestamps >1 day old; check the Bloom filter for timestamps <=1 day old. $\endgroup$ – Squeamish Ossifrage May 20 '18 at 18:27
  • $\begingroup$ Internally hash tables can of course have collisions, it's just that the hash table will adjust the table size or bucket size if it encounters one. $\endgroup$ – Maarten Bodewes May 20 '18 at 18:33
  • $\begingroup$ Ok thx. Was wondering if cryptography had some magic stuff for this but likely not so. $\endgroup$ – Svein May 20 '18 at 18:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.