Double spend protection can potentially take a lot of space and storage has to be persistent for a long time

[aliaksei-imi]

The issuer has to keep track of all spent tokens signed with keys currently in rotation.

Given a minimal key rotation period of 60 days and the fact that the issue can have gradual key eviction (keys might live longer than one epoch), spent tokens can potentially take a lot of space.

Privacypass has a notion of redemption context (https://www.ietf.org/archive/id/draft-ietf-privacypass-auth-scheme-01.html#name-token-challenge) which might be stored at the challenge time, and then evicted after small amount of time. And at redemption time the redeemer checks for existing contexts, without storing each spent token. This allows weaker storage requirements and saves space.

Is my way of thinking is correct? If yes, have you considered adding something like redemption context?

[aliaksei-imi]

@dvorak42 one potential way to solve this is to have not just 6 keys per epoch in the commitment endpoint, but say, 3 keys per day (for 3 public metadata bits and 1-day gradual key eviction), and stop redeeming tokens signed with a key 1 day after we stop signing with them, while keeping them in the response of key commitment, e.g.

{
    "PrivateStateTokenV3VOPRF": {
      "protocol_version": "PrivateStateTokenV3VOPRF",
      "id": 1,
      "batchsize": 1,
      "keys": {
        "0": {
          "Y": "AAAAAATZzgIvX/aJXAnd1AZ6cZlpxhiycFENSu4DG+nc9O4yfbKkk4inGnwk/DbZimmUezMQDvAC2nB0nT8t7yKvBJlMmW153UDg+hTflv3G+yz7yaQ0HkTh/nrYsgkoNYdTdmw=",
          "expiry": "day 2"
        },
        "1": {
          "Y": "AAAAAQS0ULAEikB+2aBDqSMf++8zni2mHe05iXSYyFtHbNAErp6N/iL22H1GKtUSHA758gNUKhtozP3NilFxSj8X0K0sDkC9Dk0YSHyw5QLCF2ZA09bAbpWr0aSxh626CKo2gQo=",
          "expiry": "day 2"
        },
        "2": {
          "Y": "AAAAAgQ8+RPlIhm0CIWfffmqocNCdCx5IH7znq8fpTT3HjJ/+hpS1q0I9e5BgQWipNHlUCXvyn+J8fj+fzcXICuuziy6r22mxG3T4TAJF7Iz2B6tVJvVbutQdZ5jXEbkEJ6HINg=",
          "expiry": "day 2"
        },
        "3": {
            "Y": "AAAAAgQ8+RPlIhm0CIWfffmqocNCdCx5IH7znq8fpTT3HjJ/+hpS1q0I9e5BgQWipNHlUCXvyn+J8fj+fzcXICuuziy6r22mxG3T4TAJF7Iz2B6tVJvVbutQdZ5jXEbkEJ6HINg=",
            "expiry": "day 4"
          },
        "4": {
            "Y": "AAAAAgQ8+RPlIhm0CIWfffmqocNCdCx5IH7znq8fpTT3HjJ/+hpS1q0I9e5BgQWipNHlUCXvyn+J8fj+fzcXICuuziy6r22mxG3T4TAJF7Iz2B6tVJvVbutQdZ5jXEbkEJ6HINg=",
            "expiry": "day 4"
        },
        "5": {
            "Y": "AAAAAgQ8+RPlIhm0CIWfffmqocNCdCx5IH7znq8fpTT3HjJ/+hpS1q0I9e5BgQWipNHlUCXvyn+J8fj+fzcXICuuziy6r22mxG3T4TAJF7Iz2B6tVJvVbutQdZ5jXEbkEJ6HINg=",
            "expiry": "day 4"
        },
        ...
        "59": {
          "Y": "AAAABQTPtXHESyjQzIIfBzg/I41xeeH5m8NvFn8933mAVMOHuve24koPCOJJFLqceSYmSyHq4lJOMIHPto0nOEtx4Nxv4/yFFbS5QQ+Cxb/KDZNtynKUDr2z3phrqBfMH5UwHQo=",
          "expiry": "day 61"
        },

        keys for the next epoch for forward-compatibility

        "60": {
          "Y": "AAAABQTPtXHESyjQzIIfBzg/I41xeeH5m8NvFn8933mAVMOHuve24koPCOJJFLqceSYmSyHq4lJOMIHPto0nOEtx4Nxv4/yFFbS5QQ+Cxb/KDZNtynKUDr2z3phrqBfMH5UwHQo=",
          "expiry": "day 62"
        },
        ...
        "119": {
          "Y": "AAAABQTPtXHESyjQzIIfBzg/I41xeeH5m8NvFn8933mAVMOHuve24koPCOJJFLqceSYmSyHq4lJOMIHPto0nOEtx4Nxv4/yFFbS5QQ+Cxb/KDZNtynKUDr2z3phrqBfMH5UwHQo=",
          "expiry": "day 121"
        }
      }
    }
  }

At day 1 we stop signing with keys 0-2, but redeem them for one more day, while signing with keys 3-5 and so on.

keys 0-2: issue day0-day1, redeem day0-day2
keys 3-5: issue day1-day2, redeem day1-day4
keys 6-9: issue day2-day3, redeem day2-day5

This will allow to store tokens for 2 days to avoid double spending. I wonder if such a scheme with 120 keys won't cause any problems with issuer registration and chromium policies on the number of keys?

[dvorak42]

Unfortunately with redemption_context, each different redemption_context is effectively a separate issuer (for the privacy requirements of PST), so sites will only be able to attempt to redeem with a couple redemption_contexts before being unable to redeem more tokens.

The multiple keys approach is one way of reducing how many tokens you have to keep double-spend protection for, though something more like 2 weeks may work better, since as soon as the keys expire you lose all the tokens issued under the previous epoch meaning unless the client is being issued new tokens daily, your chance of having them available at redemption will be low. We don't currently have a technical restriction on the number of keys in a commitment, though may revisit this if the number of issuers with lots of keys ends up causing our list to balloon in size or require extra processing.

The other approach that does allow most of the utility is to have long lived (1-2 month) keys but use a bloom filter style approach and have fallback logic for the false positive case to treat it as a lack of a token.

[aliaksei-imi]

@dvorak42 thank you for your feedback,

revisit this if the number of issuers with lots of keys ends up causing our list to balloon in size or require extra processing.

Is it possible to confirm that 2-week keys will not be blocked in the near future?

bloom filter style approach and have fallback logic for the false positive case to treat it as a lack of a token.

I wonder if you mean that we just deny redeeming tokens that are false positives. I am concerned that if we define the bloom filter parameters wrongly or at traffic peaks, we will be losing legitimate redeem requests.

[dvorak42]

2 week keys (~ 24 keys per commitment) should be fine for the near future and generally you'll have until the next key commitment re-registration before any new policy might apply.

Re Bloom filter, you'll need some logic for legitimate redemption requests when the client doesn't have any tokens available (because they haven't yet been issued tokens or their previous tokens expired), with a low enough false positive rate you should hopefully be able to rely on that logic.

[aliaksei-imi]

@dvorak42 I see, well guess combining these two approaches would be the way to go, rotate keys more often to avoid bloom filter getting too big. Thank you for the advice