Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental information it wants to, like a "witness"). Later, the client will submit the token (and optionally the witness) and the server needs to be able to quickly determine if it is a token value that it (the server) has previously issued. The token does not need to be "secure", so a trivially forgeable token is okay. Ideally, the server can:
- Generate the tokens in O(1) time and space
- Validate that it issued the tokens in O(1) time and space
The most obvious solution to this problem as stated would be to simply use an incrementing counter as the token. The server stores a single integer and increments it when asked for a new value. Determining if the token has been issued by this server means simply ensuring that the token submitted by the client is <= than the server's currently stored value.
The twist: The server might crash and get restored from a backup, meaning that its counter value might regress to a previous value. (We'll call this the regression value). If this happens, any tokens previously issued that are less than or equal to its regression value should be considered valid, but any tokens previously issued with a value higher than its regression value should be considered invalid since they were not generated by "this" instance of the server. In short, we need to detect a "fork" in our token issuing.
For example: Imagine I issued tokens T0 to T20. Then, I restore the server to a backup right after it had issued T10. I want the server to continue to validate/recognize T0-T10, but no longer recognize T10-T20. Furthermore, I want to make sure that it never re-issues tokens that are identical to the previously issued T11-T20.
The restored server doesn't know what the previously highest (MAX) issued token was. (If it did, it could "mark" any token values as invalid if they had a value between its current value and its max value.)
We also need to avoid the restored server issuing the same token its previous incarnation did. The integer counter scheme would not be capable of such a guarantee since it is not sure what the previous maximum token issued was. Thus, it wouldn't know what value to safely increment its counter to. One way to solve this would be to have a separate "restoration counter" to note the number of times the server has been restored. But presumably, if we were capable of saving this separate state somewhere, we could just store the previously maximum issued counter as well.
Another way to solve this problem would be to use timestamps as the token. Assuming an accurate clock, the restored server would be guaranteed to never issue the same value that its predecessor did. However, if we use a timestamp, the server no longer knows which specific timestamp tokens it ever issued in the past, unless it keeps track of a full list of them, bringing the time and space complexity well above O(1). (It could keep a list of the times it was restored from backup and reference this list when validating tokens, but this adds complexity to time and space for validation).
However, if there were a way to compactly store a list of N timestamps and an easy way to test a given timestamp for set membership, the problem would be easy to solve.
Options I have considered:
Option 1: Bloom filter: The server could use a bloom filter and add each number issued to its filter. Unfortunately, the set membership test would be probabilistic, but I could make the filter big enough to reduce my probability of a false positive quite low. However, it seems like the addition of information other than just the token value in the form of witness changes allows us to offload additional information to the clients that later ask for verification, and would allow us to do better somehow.
Option 2: A cryptographic accumulator, like an RSA accumulator. If each of the numbers I was generating were prime, I believe I could use an RSA accumulator to store a single accumulator value of constant size S, where S is significantly fewer bytes than storing a list of N. Each time I add a new prime to my set, I add it to the accumulator, then I generate its witness as well and ship both the number and the witness to my client. Later, the client would submit the integer it is testing, and the witness and I would be able to quickly determine if the number being submitted is in fact a member of my set or not. Possible problems: I need to be able to hash to a prime number deterministically. (Not the end of the world, but adds complexity.) I think I have to update my witness values as I add new values to the accumulator which adds time to the verification step. Lastly: My understanding of accumulators is rudimentary, and I'm not sure how large the accumulator needs to be in relation to the set being accumulated.
Option 3: I'm overthinking this tremendously.
** Related problems: **
This seems a lot like having a lot of hash values in a Merkle tree or hash chain (blockchain), and wanting to be able to determine if a particular hash value were ever seen in the chain, without having to store every value that had been seen in the chain. I'm hopeful that with the additional concept of generating a "witness" value of some sort to be stored along with the number, the server can make a membership determination with much less overhead than having to store all of the numbers. (Coda uses techniques to keep its last chain in its blockchain deterministic in size and offloads the full corresponding Merkle tree to clients. https://eprint.iacr.org/2020/352.pdf)
This feels similar to a vector commitment accumulator, where the numbers being committed to are in a given order, but I think committing to a set is simpler than committing to a vector.
I think that this is the same problem as labeling a tree that looks like the following:
A -> B -> C -> D -> E \ -> F -> G \ -> H
Given any two labels (L1, L2), and only two labels, determine if L1 is an ancestor of L2. There are labeling schemes that allow for this determination in constant time in significantly less than N bits per label, but I am not sure that it perfectly maps to this.
