Unclear purpose of commitment id in key commitment endpoint

[aliaksei-imi]

It is unclear when to increase id field in key commitment endpoint. Is it supposed to be increased after every key rotation or per issuer (re)registration?

Also, key rotation procedure seems poorly documented. Do we rotate all 6 keys at once while increasing their respective ids? If we had 6 keys with ids 0-5, then when the keys are rotated, we

1. create new set of 6 keys with ids (6-11)
2. keep old keys internally for some time to avoid clients losing their tokens, but do not show them in the commitment list
3. increase commitment id

Is that correct?

[colinbendell]

The interpretation I would like to suggest (and how I've implemented in my demo):

• commitment id is epoch seconds of the max(public key creation time)
• key_id is the same as truncated_key_id as defined in PrivacyPass:

• "truncated_token_key_id" is the least significant byte of the token_key_id (Section 5.5) in network byte order (in other words, the last 8 bits of token_key_id).

As for the rotation, looking at chrome's implementation, it appears that once the expiration time (in microseconds!) is reached, the tokens and redemption records (which are keyed based on underlying tokens) are expired. This means keeping the other expired commitment ids around is only needed for the +/- 60s caused by usual time drifts.

This functionally means that we likely:

• never rotate keys and set expiration dates very far into the future
• stagger the use of commitment ids, so you issue tokens using key=1 for the first 30 days, then use key=2 for days 31-60, (while accepting key=1), then key=3 for days 61-90 (while accepting key=1, 2), then when you move to key=4, you drop support for key=1.
• AND ensure that tokens are regularly issued/spent. Even if the client has a token currently, it might soon expire unceremoniously. Therefore, you'll want to keep adding tokens to make sure that they have at least one token that might not have expired. This all feels very fragile.

Underlying this is a general uncertainty of how long tokens actually live in the browser.

[aliaksei-imi]

This functionally means that we likely:

@colinbendell doesn't this approach contradict the idea that we might use different keys for public metadata transfer? if we use one key at a time (like in privacypass), then we don't have public metadata anymore.

What you describe resembles privacypass implementation more than chromium's PST, I believe they are a bit different at this point.

[colinbendell]

What you describe resembles privacypass implementation more than chromium's PST, I believe they are a bit different at this point.

how do you mean? Just to clarify, my list of options is just my editorial based on the constraints that Chrome's PST has implemented. The issue is that token and Redemption tokens are invalidated if the commitment id has expired (see linked code above).

doesn't this approach contradict the idea that we might use different keys for public metadata transfer? if we use one key at a time (like in privacypass), then we don't have public metadata anymore.

Agree. The constraint of having an expiration published forces this situation since we will need to handle key rotation at some point. It's also unclear how far into the future a key commitment would be permitted to use. If we can use an infinite date (say: 2999-01-01) then we sidestep the rotation and have retained the public metadata capabilities.

[aliaksei-imi]

how do you mean?

I am just saying that what you're suggesting is very similar to what we have in privacypass token keys right now (rotate individual keys, keeping current/next/old, and no public metadata). But from what I read about PST, 6 keys are for public metadata, and supposed to be rotated all at once.

The same way https://trusttoken.dev/tt/k has expiry of all keys set to the same date 1767139200000000 (Wednesday, December 31, 2025 12:00:00 AM), although very far in future.

And your demo https://private-state-token.colinbendell.dev/ seems to have a strangely large value of 253402300799000000.

btw I can't spot any code that would expire tokens (not redemption records) if the key is expired. Can you please point me there?

So, to follow up, given these conditions

1. https://github.com/WICG/trust-token-api/blob/main/PRIVACY_FRAMEWORK.md#example-limit mentions 60 days of keys' lifetime
2. https://github.com/WICG/trust-token-api/blob/main/PRIVACY_FRAMEWORK.md#limit-key-rotation-frequency mentions we need regular rotation (as well as to invalidate old tokens issued under previous epochs (to avoid large pools of tokens being gathered by malicious parties and to update issuance logic)
3. we might need public metadata
4. as far as i understand there's no code that expires individual tokens in chromium, but redemption will fail if given key_id is not present anymore in your server's keystore

this is how I came to the approach that I've outlined in the description.

You approach is also good, but it does not allow for public metadata.

[colinbendell]

btw I can't spot any code that would expire tokens (not redemption records) if the key is expired. Can you please point me there?

There are two places that I see the pruning / expiration happen:

• on token-redemption requests. The tokens are pruned and then active tokens are used.
• on send-redemption-record requests. Similarly, redemption records are checked that they aren't expired.

The net-net is that once the key commitment has expired, all tokens and redemption records are dead. This is clearly not a desired behaviour since it means that steady-state is never achieved.

And your demo private-state-token.colinbendell.dev seems to have a strangely large value of 253402300799000000.

This is the same test key that is used in the wpt tests. (where d = ORDER -1n and expiration is Friday, December 31, 9999 11:59:59 PM GMT

...mentions 60 days of keys' lifetime

I'm hoping that this document is only a guidance. The verbiage is also very loose. Terms like "allowed" and "best practices" seem to suggest that this is origin dependent? See:

Key rotations will be allowed at a 60 day cadence, in keeping with best practices while limiting the aggregate information leakage over time.

[aliaksei-imi]

on token-redemption requests. The tokens are pruned and then active tokens are used.

Thanks a lot, got it.

I'm hoping that this document is only a guidance

could be, but know knows :)

(as well as to invalidate old tokens issued under previous epochs (to avoid large pools of tokens being gathered by malicious parties and to update issuance logic)

Well, if this sentence does really mean that we abruptly expire all previous tokens, than this all makes sense, which is aligned with 6 metadata bits.

Otherwise what do you think of the approach of having 3 metadata bits + a legacy key for each bit, e.g.

start with 3 (id: key) pairs (3 public metadata bits)
0: y1
1: y2
2: y3

after 60 days, we retain the old keys, but add a new key per metadata bit
0: y1-1 (new key for bit 1)
1: y1 (old key for bit 1)
2: y2-1 (new key for bit 2)
3: y2 (old key for bit 2)
4: y3-1 (new key for bit 3)
5: y3 (old key for bit 3)

after 1 day (or some period of time to allow tokens to gracefully expire or be redeemed), we remove old keys
0: y1-1
1: y2-1
2: y3-1

after 60 days, we again create new keys, retaining the old ones

@dvorak42 maybe you could point out if we are looking at the right direction?

[dvorak42]

The "key commitment ID" is an integer in the key commitment, it is recommended to change between key rotations, however currently it has no meaning. It is intended for debugging and we may eventually expose the version the client has through DevTools or other UI, though don't currently do so. "key_id" should be unique per key though otherwise doesn't have a particular pattern they need to abide by (other than being a string representing a uint32 number), and may be dependent on your key rotation protocol.

For key rotation, the concrete restrictions are you shouldn't change the key commitment (set of keys) you serve more often than 60 days (this is to avoid rapidly shifting key commitments from being used to target specific sets of users.

You can have more than six keys (this needs to be fixed up as part of #233) in your key commitment, however the client will only use the six keys soonest to expire for issuing tokens (and will discard tokens/redemption records associated with other keys). So you can have multiple key sets in a key commitment at a time (but only one keyset will be active).

This leads to a couple different ways of handling keys:

1) You have keys A1,A2,A3,A4,A5,A6 that expire at T+10 and another set of keys B1,B2,B3,B4,B5,B6 that expire at T+20. Your issuer issues tokens with A from T+0 to T+10 and with B from T+10 to T+20. This does allow you to use all 6 metadata values, however when you rotate your keys you lose tokens/records issued during the previous epoch.

2) You have keys A1,A2,A3 that expire at T+10, B1,B2,B3 that expire at T+20, C1, C2, C3 that expire at T+30. Your issuer issues tokens with B from T+0 to T+10, but can redeem tokens that are either A or B from T+0 to T+10. From T+10 to T+20 you issue tokens with C, but can redeem B or C, etc. (if at redemption time you see tokens from the epoch that is about to expire you can use that to issue new tokens in the new epoch). This reduces your metadata to 3 buckets, but allows more gradual transition between keys.

There are also more complicated schemes where you keep non-overlapping keys for some buckets and overlapping keys for others.

We'll try to add some demos/examples on these key rotation schemes.

[colinbendell]

You can have more than six keys (this needs to be fixed up as part of https://github.com/WICG/trust-token-api/issues/233) in your key commitment, however the client will only use the six keys soonest to expire for issuing tokens (and will discard tokens/redemption records associated with other keys). So you can have multiple key sets in a key commitment at a time (but only one keyset will be active).

Is this correct:

• hasPrivateToken() and redeem-request will filter on for those that match a key commitment for latest to expire tokens and ties are randomly resolved? (SELECT token ... FROM ... WHERE ... ORDER BY expiration desc TOP 6)
• hasRedemptionRecord() and 'send-redemption-record will filter on any key commitment so long as they haven't expired.

It would be nice to see some WPT tests around this behaviour because it is not intuitive based on the spec descriptions.

[dvorak42]

The logic for getting the current key commitments first filters the key commitments received down to the six most recent keys, before it gets applied through the other checks:

https://source.chromium.org/chromium/chromium/src/+/main:services/network/trust_tokens/trust_token_key_filtering.h;l=22

That runs before both the redemption record and redemption code checks.

Yeah, #233 will hopefully clarify the spec description, adding WPT for it is a good idea we'll add to the queue.

[colinbendell]

The logic for getting the current key commitments first filters the key commitments received down to the six most recent keys, before it gets applied through the other checks:

Ok, so because it is based on std::vector I'm assuming that the order that the keys are listed can change which 6 are used in a tie. Correct? How often could I add a new key commitment?

[dvorak42]

It's sorted first on the expiry, then on the byte value of the body so it will always consistently choose the same set of keys given that the keys themselves haven't changed.

Currently the key commitment itself can only change every 60 days.

[aliaksei-imi]

@dvorak42 appreciate your quick response, this is really helpful,. thanks

[colinbendell]

I think the algorithm for selecting the top 6 public keys in the key commitment should be published as part of the spec. It will be easy for origins to get out of sync with the implementation. If other browser vendors implement slightly different selection algorithms origins will have to resort to UA sniffing.

[dvorak42]

Added a comment on #233 to track that.

[brcthdrgn]

Colin you referred to the tokens corresponding with each other for 30 days behind the next fourth coming 30 day token. So that's keeping the client up-to-date with the users browser stays uncorrupted or cleaned correct? Im learning this reading everyday as much as possible. So now I'm trying to understand that the user's browser has a certain amount of time beyond its microsecond disengagement coded into the key creation or the "grace period"? And can I ask how long tokens actually live in the browser? Those are very noob questions I understand completely also. I'm just having a lot of trouble being able to log into my email accounts and my browser isn't being corrupted or affected by anything that I know of so I don't know what I can actually monitor or clean my browser should I say so that the tokens that I'm getting from my email providers isn't being removed destroyed or corrupted. Don't mind me everyone I'm totally green and could probably find those answers I'm a blog I presume. I just keep losing emails and I can't get back into him I can't get the providers to let me back in them so I don't know what it is that I need to do and if there's a certain help me page or a Blog please direct me I'll be more than happy to read it. Also I consider myself as mario amongst a full field is the very best Nascar racers the world has to offer which is you all that's present here. Beep Beep its'a mariooo im coming through. Thanks for any response if any of it made sense. If not I apologize completely to you all.