spec.bs

<pre class='metadata'>
Title: Private State Token API
H1: Private State Token API
Shortname: private-state-token-api
Level: 1
Status: CG-DRAFT
Group: WICG
Repository: WICG/trust-token-api
URL: https://wicg.github.io/trust-token-api/
Editor: Aykut Bulut, Google https://www.google.com/, aykutb@google.com
Editor: Steven Valdez, Google https://www.google.com/, svaldez@google.com
Abstract: Private State Token API is a web platform API that allows propagating a limited amount of anti-fraud signals across sites, using the Privacy Pass protocol as an underlying primitive.
!Participate: <a href="https://github.com/WICG/trust-token-api">GitHub WICG/trust-token-api</a> (<a href="https://github.com/WICG/trust-token-api/issues/new">new issue</a>, <a href="https://github.com/WICG/trust-token-api/issues?state=open">open issues</a>)
!Commits: <a href="https://github.com/WICG/trust-token-api/commits/main/spec.bs">GitHub spec.bs commits</a>
Markup Shorthands: css no, markdown yes
Ignored Terms: h1, h2, h3, h4, h5, h6, xmp
</pre>

<pre class="link-defaults">
spec:fetch; type:dfn; for:/; text:response
spec:fetch; type:dfn; for:/; text:request
spec:infra; type:dfn; text:list
</pre>

<pre class="anchors">
urlPrefix: https://fetch.spec.whatwg.org/; spec: Fetch
    text: http-network-or-cache fetch; url: #concept-http-network-or-cache-fetch; type: dfn
</pre>

<pre class='biblio'>
{
    "PRIVACY-PASS-ARCHITECTURE": {
        "authors": ["A. Davidson", "J. Iyengar", "C. A. Wood"],
        "href": "https://www.ietf.org/archive/id/draft-ietf-privacypass-architecture-06.html",
        "publisher": "IETF",
        "title": "Privacy Pass Architectural Framework"
    },
    "PRIVACY-PASS-AUTH-SCHEME": {
        "authors": ["T. Pauly", "S. Valdez", "C. A. Wood"],
        "href" : "https://www.ietf.org/archive/id/draft-ietf-privacypass-auth-scheme-05.html",
        "publisher": "IETF",
        "title": "The Privacy Pass HTTP Authentication Scheme"
    },
    "PRIVACY-PASS-ISSUANCE-PROTOCOL": {
        "authors": ["S. Celi", "A. Davidson", "A. Faz-Hernandez", "S. Valdez", "C. A. Wood"],
        "href": "https://www.ietf.org/archive/id/draft-ietf-privacypass-protocol-06.html",
        "publisher": "IETF",
        "title": "Privacy Pass Issuance Protocol"
    },
    "PRIVACY-PASS-WG": {
        "href": "https://datatracker.ietf.org/wg/privacypass/about/"
    },
    "PMB": {
        "authors": ["Ben Kreuter", "Tancrede Lepoint", "Michele Orru", "Mariana Raykova"],
        "href": "https://eprint.iacr.org/2020/072",
        "publisher": "Cryptology ePrint Archive",
        "title": "Anonymous Tokens with Private Metadata Bit"
    },
    "VOPRF": {
        "authors": ["A. Davidson", "A. Faz-Hernandez",  "N. Sullivan", "C. A. Wood"],
        "href": "https://www.ietf.org/archive/id/draft-irtf-cfrg-voprf-13.html",
        "publisher": "IETF",
        "title": "Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups"
    },
    "ISSUER-PROTOCOL": {
        "authors": ["S. Valdez", "A. Bulut", "S. Schlesinger"],
        "href": "https://github.com/WICG/trust-token-api/blob/main/ISSUER_PROTOCOL.md",
        "publisher": "Google",
        "title": "ISSUER_PROTOCOL"
    }
}
</pre>
<pre class="anchors">
urlPrefix: https://tools.ietf.org/html/rfc8941; spec: rfc8941
    type: dfn
        text: structured header; url: #
    for: structured header
        type: dfn
            text: integer; url: #section-3.3.1
            text: string; url: #section-3.3.3
</pre>

Goals {#goals}
==============

The goal of the Private State Token API is to transfer a limited amount of signals across
sites through time in a privacy preserving manner. It achieves this using
privacy pass protocol [[!PRIVACY-PASS-ISSUANCE-PROTOCOL]] specified in working
documents of privacy pass working group of IETF [[PRIVACY-PASS-WG]]. Private
State Tokens can be considered as a web platform implementation of Privacy
Pass.

<!--

In a real-world
system relying on anonymous tokens without private metadata bit, if the issuer stops providing
malicious users with tokens, the attacker will know that they have been detected as malicious.
In fact, this information could serve as an incentive to corrupt more users, or to train machine
learning models that detect which malicious behavior goes un-noticed.

https://eprint.iacr.org/2020/072.pdf

-->


Background {#background}
========================

The Private State Token API provides a mechanism for anonymous authentication. The
API provided by the user agent does not authenticate clients, instead it facilitates
transfer of authentication information.

Authentication of the clients and token signing are both carried by the same
entity referred to as the **issuer**. This is the joint attester and issuer
architecture described in [[!PRIVACY-PASS-ARCHITECTURE]],
[[!PRIVACY-PASS-AUTH-SCHEME]].

User agents store tokens in persistent storage. Navigated origins might fetch/spend
tokens in first party contexts or include third party code that fetch/spend
tokens. Spending tokens is called **redeeming**.

Origins may ask the user agent to fetch tokens from the issuers of their
choice. Tokens can be redeemed from a different origin than the fetching one.

Private State Tokens API performs cross site anonymous authentication without
using linkable state carrying cookies [[RFC6265]]. Cookies do provide cross
site authentication, however, they fail to provide anonymity.

Cookies store large amounts of information. [[RFC6265]] requires at least 4096
bytes per cookie and 50 cookies per domain. This means an origin has
50 x 4096 x 2^8 unique identifiers at its disposal. When backed with back end
databases, a server can store arbitrary data for that many unique
users/sessions.

Compared to a cookie, the amount of data stored in a Private State Token is very
limited. A token stores a value from a set of six values (think of a value of
an enum type of six possible values). Hence a token stores data between 2 and 3
bits (4 < 6 < 8). This is very small compared to 4096 bytes a cookie can store.

Moreover, Private State Tokens API use cryptographic protocols that prevents
origins from tracking which tokens they issue to which user. When presented with
their tokens, issuers can verify they issued them but cannot link the
tokens to the context of their issuance. Cookies do not have this property.

Unlike cookies, storing multiple tokens from an issuer does not deteriorate
privacy of the user due to the unlinkability of the tokens. The Private
State Token API allows at most 2 different issuers in a top level origin. This
is to limit the information stored for a user when the issuers are
collaborating.

Private State Token operations rely on [[!FETCH]]. A fetch request corresponding to a
specific Private State Token operation can be created and used as a parameter to the
fetch function.

Note: This specification uses the terms "masked" and "unmasked" where [[!PMB]]
uses "blinded" and "unblinded", respectively.

<!--
* how this is not as powerful like cookies, privacy guarantees?
* Between first and second para there is some gap. We should fill in.
* Level of details in privacy is good and important. A high level approach of this before API details.
* Start with use case and scenarios. This would help with people confused with API.
* how do we refer to unsigned/signed bind/clear tokens?
-->


Issuer Public Keys {#issuer-public-keys}
========================================

This section describes the public interfaces that an issuer is required to
support to provide public keys to be used by Private State Token protocols.

An issuer needs to maintain a set of keys and implement the **Issue** and
**Redeem** cryptographic functions to sign and validate tokens. Issuers are
required to serve a **key commitment** endpoint. Key commitments are
collections of cryptographic keys and associated metadata necessary for
executing the issuance and redemption operations. Issuers make these available
through secure HTTP [[!RFC8446]] endpoints. User agents should fetch the key
commitments periodically.

Requests to key commitment endpoints should result in a JSON response
[[!RFC8259]] of the following format.

```javascript
{
  <cryptographic protocol_version>: {
    "protocol_version": <cryptographic protocol version>,
    "id": <key commitment identifier>
    "batchsize": <batch size>,
    "keys": {
      <keyID>: { "Y": <base64-encoded public key>,
                 "expiry": <key expirion data>},
      <keyID>: { "Y": <base64-encoded public key>,
                 "expiry": <key expirion data}, ...
    }
  },
  ...
}
```

* `<cryptographic protocol version>` is a string identifier for the Private State Token
    protocol version used. The same string is used as a value of the inner
    `"protocol_version"` field. Protocol version string identifier is either
    `"PrivateStateTokenV3PMB"` or `"PrivateStateTokenV3VOPRF"`. Both protocols have similar
    properties in terms of privacy implications.

    * Protocol version `“PrivateStateTokenV3PMB”` implements [[!PMB]] cryptographic
               protocol. In this protocol, each token contains a private
               metadata bit.

    * Protocol version `“PrivateStateTokenV2VOPRF”` implements [[!VOPRF]] cryptographic
               protocol. Contrary to [[!PMB]], tokens do not contain private
               metadata bits. However, issuers can use twice as many
               concurrently valid token signing keys (six compared to three of
               [[!PMB]]).

* `"id"` field provides the identifier of the key commitment. It is a string
         representation of a non-negative integer that is within the range of
         an unsigned 32 bit integer type. Values should be montonically
         increasing.

* `"batchsize"` specifies the maximum number of masked tokens that the issuer
                supports for each token issuance operation. Its value is a
                string representation of a positive integer. The user agent might send
                fewer tokens in a single operation, but will generally default to
                sending `batchsize` many tokens per operation.

* `"keys"` field is a dictionary of public keys listed by their identifiers.

         * `<keyID>` is a string representation of a non-negative integer that
               is within the range of an unsigned 32 bit integer type.

         * Each key has a `"Y"` field which is a string representation of a
                big-endian base64 encoding [[!RFC4648]] of the byte string of
                the key.

         * `"expiry"` field specifies how long the underlying key is valid. It
                      is a string representation of a nonnegative integer that
                      is within the range of an unsigned 64 bit integer type.
                      Underlying key expires if this amount many or more
                      microseconds are elapsed since the POSIX epoch
                      [[!RFC8536]].

All field names and their values are strings. When new key commitments are
fetched for an issuer, previous commitments are discarded.

Algorithms {#algorithms}
====================================

A user agent has <dfn>issuerAssociations</dfn>, which is a [=map=] where the keys are [=/origin=] |topLevel|, and the values are a [=list=] of [=/origins=].

To <dfn>determine whether associating an issuer would exceed the top-level limit</dfn> given an [=/origin=] |issuer| and an [=/origin=] |topLevel|, run the following steps:

1. If [=issuerAssociations=][|topLevel|] does not [=map/exist=], return false.
1. If [=issuerAssociations=][|topLevel|] [=list/contains=] |issuer|, return false.
1. If the [=issuerAssociations=][|topLevel|] [=list/size=] is less than 2, return false.
1. Return true.

To <dfn>associate the issuer</dfn> |issuer| (an [=/origin=]) with the [=/origin=] |topLevel|, run the following steps:

1. If [=issuerAssociations=][|topLevel|] does not [=map/exist=], [=map/set=] [=issuerAssociations=][|topLevel|] to an empty [=list=].
1. [=list/Append=] |issuer| to [=issuerAssociations=][|topLevel|].

To determine whether an [=/origin=] |issuer| <dfn>is associated with</dfn> a given [=/origin=] |topLevel|, run the following steps:

1. If [=issuerAssociations=][|topLevel|] does not [=map/exist=], return false.
1. If [=issuerAssociations=][|topLevel|] [=list/contains=] |issuer|, return true.
1. Return false.

A user agent has <dfn>redemptionTimes</dfn>, a [=map=] where the keys are a [=tuple=] (|issuer|, |topLevel|), and the values are a [=tuple=] (|lastRedemption|, |penultimateRedemption|).

To <dfn>record redemption timestamp</dfn> given an [=/origin=] |issuer| and an [=/origin=] |topLevel|, run the following steps:

1. Let |currentTime| be the current date and time.
1. Let |previousRedemption| be the earliest representable date and time.
1. If [=redemptionTimes=][(|issuer|,|topLevel|)] [=map/exists=], let |previousRedemption| be the |lastRedemption| field of the tuple [=redemptionTimes=][(|issuer|,|topLevel|)].
1. [=map/set=] [=redemptionTimes=][(|issuer|,|topLevel|)] to the tuple (|currentTime|, |previousRedemption|).

To <dfn>look up penultimate redemption</dfn> given an [=/origin=] |issuer| and an [=/origin=] |topLevel|, run the following steps:

1. Let |penultimateRedemption| be the earliest representable date and time.
1. If [=redemptionTimes=][(|issuer|,|topLevel|)] [=map/exists=], let |penultimateRedemption| be the |penultimateRedemption| field of the tuple [=redemptionTimes=][(|issuer|,|topLevel|)].
1. Return |penultimateRedemption|.

A user agent has <dfn>pstKeyCommitments</dfn>, a [=map=] where the keys are an [=/origin=], and the values are a [=map=] formatted in the same way as the key commitments described in [[#issuer-public-keys]]. Populating [=pstKeyCommitments=] is [=implementation-defined=].

Note: It is recommended that each user agent fetches the key commitments from issuers at a regular cadence and through trusted infrastructure, and then sends the concatenated map of issuers and key commitments to the client to ensure consistency between the keys different user agent instances use.

To <dfn>look up the key commitments</dfn> for a given [=/origin=] |issuer|, run the following steps:

1. If [=pstKeyCommitments=][|issuer|] does not [=map/exist=], return null.
1. Let |issuerKeys| be [=pstKeyCommitments=][|issuer|].
1. For each |pstVersion| that the user agent supports for this API in an [=implementation-defined=] order, run the following steps:
    1. Return |issuerKeys|[|version|], if it [=map/exists=].
1. Return null.

Note: |pstVersion| is a string identifier representing different cryptographic versions of tokens that can be used with this API. User agents should only select keys for versions they support, ordered by which versions they prefer based on performance and any user defined preferences.

To <dfn>retrieve a token</dfn> for an [=/origin=] |issuer|, run the following steps:

1. TODO

To <dfn>discard tokens</dfn> from an [=/origin=] |issuer|, run the following steps:

1. TODO

To get the <dfn>number of tokens</dfn> from an [=/origin=] |issuer|, run the following steps:

1. TODO

To get the <dfn>max batch size</dfn> for an [=/origin=] |issuer|, run the following steps:

1. TODO

To <dfn>generate masked tokens</dfn> given a number |numTokens|, run the following steps:

1. TODO

Integration with Fetch {#fetch-integration}
====================================

Definitions {#definitions}
---------------------------------------------------------------

The {{RefreshPolicy}} is attached to a redemption request, determining whether or not the
redemption should result in a previously returned, unexpired [=redemption record=] or a
new one.

<pre class=idl>
enum RefreshPolicy { "none", "refresh" };
</pre>

The {{TokenType}} is currently set to `"private-state-token"`, as this is the only token
type that the specification supports at this time.

<pre class=idl>
enum TokenType { "private-state-token" };
</pre>

The {{OperationType}} refers to which operation the user agent is attempting to complete.

<pre class=idl>
enum OperationType { "token-request", "send-redemption-record", "token-redemption" };
</pre>

The {{PrivateStateToken}} contains the information required to make a fetch request.

<pre class=idl>
dictionary PrivateStateToken {
  required OperationType operation;
  RefreshPolicy refreshPolicy = "none";
  sequence&lt;USVString> issuers;
};
</pre>

Issue(151): Need to specify how `operation` and `issuers` are used.

This specification adds a new property to the {{RequestInit}} dictionary:

<pre class=idl>
partial dictionary RequestInit {
  PrivateStateToken privateStateToken;
};
</pre>

Modifications to request {#fetch-request}
---------------------------------------------------------------

A [=/request=] has an associated <dfn for=request>token refresh policy</dfn>, which is <code>"none"</code> or <code>"refresh"</code>. Unless stated otherwise it is <code>"none"</code>.

Add the following steps to the <code><a constructor lt="Request()">new Request (<var ignore>input</var>, |init|])</a></code> constructor, before step 28 ("<code>Set [=this=]'s [=Request/request=] to |request|</code>"):

 1. If |init|["{{RequestInit/privateStateToken}}"] [=map/exists=], then set <var ignore>request</var>'s [=request/token refresh policy=]</a> to |init|["{{RequestInit/privateStateToken}}"]["{{PrivateStateToken/refreshPolicy}}"].

Modifications to http-network-or-cache fetch {#http-network-or-cache-fetch}
---------------------------------------------------------------

This specification adds the following steps to the [=http-network-or-cache fetch=] algorithm, before modifying the header list:

    1. [=Append private state token issue request headers=] on |httpRequest|.
    1. [=Append private state token redemption request headers=] on |httpRequest|.

Issuing Protocol {#issuing-protocol}
====================================

This section explains the issuing protocol. It has two sections that explains
the issuing protocol steps for user agents and issuers.

Creating An Issue Request {#issue-request}
---------------------------------------------------------------

<div class=example>
An issue request is created and fetched as demonstrated in the following snippet.

```javascript
let issueRequest = new Request("https://example.issuer:1234/issuer_path?public=0&private=0", {
  privateStateToken: {
    type: "token-request",
    issuer: "https://example.issuer"
  }
});
fetch(issueRequest);
```
</div>

To <dfn>append private state token issue request headers</dfn> given a [=/request=] |request|, run the following steps:

 1. If |request|'s [=request/client=] is not a [=secure context=], return.
 1. Let |issuer| be |request|'s [=request/URL=]'s [=url/origin=].
 1. Let |topLevel| be |request|'s [=request/client=]'s [=environment/top-level origin=].
 1. If associating |issuer| with |topLevel| [=determine whether associating an issuer would exceed the top-level limit|would exceed the top level’s number-of-issuers limit=], return.
 1. [=Associate the issuer=] |issuer| with |topLevel|.
 1. If the [=number of tokens=] for |issuer| is at least 500, return.
 1. Let |commitments| be the result of [=look up the key commitments|looking up the key commitments=] for |issuer|.
 1. If |commitments| is null,  return.
 1. Pass issuer public keys to cryptographic procedures. Reject if keys are
         malformed.

    Issue(187): How do we get the issuer public keys here?

 1. [=Discard tokens=] from |issuer| that are signed with keys other than those from
            the issuer's most recent commitments.

    Issue(189): This probably needs to be its own algorithm, how is "most recent" defined here?

 1. Let |numTokens| be |issuer|'s [=max batch size=] or an [=implementation-defined=] limit on the number of tokens (which is recommended to be 100), whichever is smaller.

 1. Let |tokens| be the result of [=generate masked tokens|generating masked tokens=] with |numTokens|.
 1. Set |request|'s [=cache mode=] to `"no-store"`.
 1. Let |base64-encoded-tokens| be the base64-encoded version of |tokens|.
 1. Let |version| be the version of the cryptographic protocol used.
 1. [=header list/Set a structured field value=] given (<a http-header>`Sec-Private-State-Token`</a>, |base64-encoded-tokens|)
                in |request|'s header list.
 1. [=header list/Set a structured field value=] given (<a http-header>`Sec-Private-State-Token-Version`</a>, |version|)
                in |request|'s header list.

<div class=example>
Private State Token HTTP request headers created for a typical fetch is as follows.

```
Sec-Private-State-Token: <masked tokens encoded as base64 string>
Sec-Private-State-Token-Version: <cryptographic protocol version, VOPRF or PMB>
```
</div>

Issuer Signing Tokens {#issuer-signing-tokens}
----------------------------------------------

This section explains the signing of tokens that happens in the issuer
servers. Information to be encoded in the tokens are passed in the URL `public`
and `private` parameters. VOPRF can only encode a value from set {0,1,2,3,4,5}
passed in the URL `public` parameter. [[!PMB]] can encode a value from set {0,1,2}
in `public` and a value from set {0,1} in `private` parameter.

Using its private keys, issuer signs the masked tokens obtained in the
<a http-header>Sec-Private-State-Token</a> request header value. Issuer uses the cryptographic protocol
specified in the request <a http-header>Sec-Private-State-Token-Version</a> header. Encoding the values
passed in URL `private` and `public` parameters happens in this signing
step. Issuer returns the signed tokens in the <a http-header>Sec-Private-State-Token</a> response header
value encoded as a base64 byte string.

<div class=example>
The following snippet displays a typical response demonstrating the Private State Token
header.

```
Sec-Private-State-Token: <token encoded as base64 string>
```
</div>

The details for servers implementing this protocol can be found in [[!ISSUER-PROTOCOL]].

Handling Issue Responses {#issue-response}
----------------------------------------------------------

To <dfn>handle an issue response</dfn>, given [=request=] |request| and [=response=] |response|, run the following steps:

1. If |request|'s [=request/header list=] [=header list/contains|does not contain=] <a http-header>Sec-Private-State-Token</a>, return null.
1. If |response|'s [=response/header list=] [=header list/contains|does not contain=] <a http-header>Sec-Private-State-Token</a>, return a [=network error=].
1. Let |header| be the result of [=header list/get|getting=] <a http-header>Sec-Private-State-Token</a> from |response|'s [=response/header list=].
1. If |header| is empty, return null.
1. [=header list/delete|Delete=] <a http-header>Sec-Private-State-Token</a> from |response|'s [=response/header list=].
1. Let |unmasked tokens| be the result of carrying out the cryptographic procedures to obtain a list of unmasked tokens given |header|.
1. If |unmasked tokens| is an error, return a [=network error=].
1. Associate |unmasked tokens| with the issuing key's label and store |unmasked tokens|.
1. Return null.

Issue(190): Define "cryptographic procedures to obtain a list of unmasked tokens"

The details for servers implementing this protocol can be found in [[!ISSUER-PROTOCOL]].

<h3 id="modification-to-http-fetch-steps-header">Modification to HTTP fetch steps</h3>
The following steps will be added to the [=HTTP fetch=] steps, before checking the redirect status (i.e. "7. If |actualResponse|'s status is a redirect status, ..."):

1. Let |issue response result| be the result of [=handle an issue response|handling an issue response=], given [=request=] |request| and [=response=] |actualResponse| as input.
1. If |issue response result| is a [=network error=], return |issue response result|.

Redeeming Tokens {#redeeming-tokens}
====================================

When the user agent navigates to a top-level origin, this top-level origin or a third party site
embedded on the top level origin may redeem tokens stored in the user agent from a
specific issuer to learn `public` and/or `private` data encoded in the
tokens.

<div class=example>
Redemption is carried through fetch as demonstrated in the following
snippet. The default value for refreshPolicy is `'none'`.

```javascript
let redemptionRequest = new Request('https://example.issuer:1234/redemption_path', {
  privateStateToken: {
    type: 'token-redemption',
    issuer: 'https://example.issuer',
    refreshPolicy: {'none', 'refresh'}
  }
});
```
</div>

To <dfn>set redemption headers</dfn> with [=/request=] |request| and a [=Redemption Record=] |record|:
 1. Let |redemption-result| be the redemption procedure result.
 1. Let |version| be the version of the cryptographic protocol used.
 1. Let |token-lifetime| be the expiration time of the [=redemption record=] in seconds.
 1. [=header list/Set a structured field value=] given (<a http-header>`Sec-Private-State-Token`</a>, |redemption-result|)
                in |request|'s header list.
 1. [=header list/Set a structured field value=] given (<a http-header>`Sec-Private-State-Token-Version`</a>, |version|)
                in |request|'s header list.
 1. Optionally, [=header list/set a structured field value=] given (<a http-header>`Sec-Private-State-Token-Lifetime`</a>, |token-lifetime|)
                in |request|'s header list.
 1. Set |request|'s [=cache mode=] to `"no-store"`.

To <dfn>append private state token redemption request headers</dfn> given a [=/request=] |request|, run the following steps:

 1. Let |issuer| be |request|'s [=request/URL=]'s [=url/origin=].
 1. Let |topLevel| be |request|'s [=request/client=]'s [=environment/top-level origin=].
 1. If |request|'s [=request/client=] is not a [=secure context=], return.
 1. If associating |issuer| with |topLevel| [=determine whether associating an issuer would exceed the top-level limit|would exceed the top level’s number-of-issuers limit=], return.
 1. [=Associate the issuer=] |issuer| with |topLevel|.
 1. If |request|'s [=request/token refresh policy=] is `"none"`:
     1. Let |record| be the result of [=get an unexpired redemption record|getting an unexpired redemption record=].
     1. If |record| is not null, [=set redemption headers=] with |request| and |record| and return.
 1. Let |penultimateRedemption| be the result of [=look up penultimate redemption =] with |issuer| and |topLevel|
 1. If |penultimateRedemption| is less than an [=implementation-defined=] time period (which is recommended to be 48 hours), return error.

 1. Let |commitments| be the result of [=look up the key commitments|looking up the key commitments=] for |issuer|.
 1. If |commitments| is null, return.
 1. [=Discard tokens=] from |issuer| that are signed with keys other than those from
            the issuer's most recent commitments.

    Issue(189): This probably needs to be its own algorithm, how is "most recent" defined here?

 1. Let |token| be the result of [=retrieve a token|retrieving a token=] for |issuer|.
 1. If |token| is null, return.
 1. Let |record| be the result of running a cryptographic redemption procedure with |token|. If the procedure fails, return.

    Issue(190): This needs to be specified more clearly

 1. [=Set redemption headers=] with |request| and |record|.

ISSUE(165): Add redemption response handling, including calling [=record redemption timestamp=].

<a http-header>Sec-Private-State-Token-Lifetime</a> response header indicates how long (in seconds) the
    [=redemption record=] should be cached for. When <a http-header>Sec-Private-State-Token-Lifetime</a> response header value
is invalid (too large, a negative number or non-numeric), UA should ignore the
<a http-header>Sec-Private-State-Token-Lifetime</a> header. When <a http-header>Sec-Private-State-Token-Lifetime</a> header value
is zero, UA should treat the record as expired. In case of multiple
<a http-header>Sec-Private-State-Token-Lifetime</a> headers, UA uses the last one. If
<a http-header>Sec-Private-State-Token-Lifetime</a> header is omitted, the lifetime of the [=redemption record=] will be
tied to the lifetime of the Private State Token verification key that confirmed the
redeemed token's issuance. The [=redemption record=] is HTTP-only and JavaScript is only able to
access/send the [=redemption record=] via Private State Token Fetch APIs. The [=redemption record=] is treated as an
arbitrary blob of bytes from the issuer, that may have semantic meaning to
downstream consumers.

Redemption Records {#redemption-records}
----------------------------------------

To reduce communication overhead, the user agent might cache blobs returned in
<a http-header>Sec-Private-State-Token</a> header value in redemption responses. These blobs are
referred as [=Redemption Records=]. User agents might choose to store these records
to include them in subsequent requests to the origins that can verify its
validity. An issuer might choose to include an optional <a http-header>Sec-Private-State-Token-Lifetime</a>
header in the redemption response. The value of this header indicates the
expiration time for the [=redemption record=] provided. This expiration is
specified as number of seconds in the <a http-header>Sec-Private-State-Token-Lifetime</a> HTTP response
header value.

A <dfn>Redemption Record</dfn> is a [=byte sequence=].

To <dfn>get an unexpired [=Redemption Record=]</dfn> with an [=/origin=] |issuer| and an [=/origin=] |topLevel|:

1. TODO

<h3 id="the-document-object">Changes to {{Document}}</h3>

<pre class="idl">
partial interface Document {
  Promise&lt;boolean> hasPrivateTokens(USVString issuer, USVString type);
  Promise&lt;boolean> hasRedemptionRecord(USVString issuer, USVString type);
};
</pre>

Query APIs {#query-apis}
========================

Token Query {#token-query}
--------------------------

When invoked on {{Document}} |doc| with {{USVString}} |issuer| and {{USVString}} |type|, the <dfn export method for=Document><code>hasPrivateTokens(issuer, type)</code></dfn> method must run these steps:
1. Let |p| be [=a new promise=].
1. If |doc| is not [=Document/fully active=], then [=reject=] |p| with an "{{InvalidStateError}}" {{DOMException}} and return |p|.
1. Let |global| be |doc|'s [=relevant global object=].
1. If |global| is not a [=secure context=], then [=reject=] |p| with a "{{NotAllowedError}}" {{DOMException}} and return |p|.
1. If |type| is not `"private-state-token"`, [=reject=] |p| with a "{{TypeError}}" {{DOMException}} and return |p|.
1. Let |parsedURL| be the the result of running the [=URL parser=] on |issuer|.
1. If |parsedURL| is failure, [=reject=] |p| with a "{{TypeError}}" {{DOMException}} and return |p|.
1. Let |origin| be |parsedURL|'s [=/origin=].
1. Let |topLevel| be the [=top-level origin=] of |doc|'s [=relevant settings object=].
1. Run the following steps [=in parallel=]:
    1. If associating |issuer| with |topLevel| [=determine whether associating an issuer would exceed the top-level limit|would exceed the top level’s number-of-issuers limit=], [=queue a global task=] on the [=networking task source=] given |global| to [=reject=] |p| with a "{{NotAllowedError}}" {{DOMException}} and return.
    1. [=Associate the issuer=] |origin| with |topLevel|.
    1. [=Look up the key commitments=] for |origin|. If there are key commitments,
             [=discard tokens=] from |origin| that are signed with keys other than those
             from the issuer's most recent commitments.
    1. [=Queue a global task=] on the [=networking task source=] given |global| to [=resolve=] |p| with true if there are tokens stored for the given issuer, with false otherwise.
1. Return |p|.

Note: This query modifies the user agent state. It associates the issuer
argument with the current origin. The specification allows at most 2 issuers associated
with an origin. This is to prevent leaking information through the issuers a
user has tokens from. Note that querying tokens triggers removal of stale tokens.

Redemption Record Query {#redemption-record-query}
--------------------------------------------------

When invoked on {{Document}} |doc| with {{USVString}} |issuer| and {{USVString}} |type|, the <dfn export method for=Document><code>hasRedemptionRecord(issuer, type)</code></dfn> method must run these steps:

1. Let |p| be [=a new promise=].
1. If |doc| is not [=Document/fully active=], then [=reject=] |p| with an "{{InvalidStateError}}" {{DOMException}} and return |p|.
1. Let |global| be |doc|'s [=relevant global object=].
1. If |global| is not a [=secure context=], then [=reject=] |p| with a "{{NotAllowedError}}" {{DOMException}} and return |p|.
1. If |type| is not `"private-state-token"`, [=reject=] |p| with a "{{TypeError}}" {{DOMException}} and return |p|.
1. Let |parsedURL| be the the result of running the [=URL parser=] on |issuer|.
1. If |parsedURL| is failure, [=reject=] |p| with a "{{TypeError}}" {{DOMException}} and return |p|.
1. Let |origin| be |parsedURL|'s [=/origin=].
1. Let |topLevel| be the [=top-level origin=] of |doc|'s [=relevant settings object=].
1. Run the following steps [=in parallel=]:
    1. If |origin| [=is associated with|is not associated with=] |topLevel|, [=queue a global task=] on the [=networking task source=] given |global| to [=resolve=] |p| with false and return.
    1. [=Look up the key commitments=] for |origin|. If there are key commitments,
             [=discard tokens=] from |origin| that are signed with keys other than those
             from the issuer's most recent commitments.
    1. [=Queue a global task=] on the [=networking task source=] given |global| to [=resolve=] |p| with true if there is a [=redemption record=] for the issuer and top level pair, with false otherwise.
1. Return |p|.

Note: Similar to token query, redemption query might modify the user agent state. Unlike
token query, redemption query does not associate issuer with the top level
origin. There is no need to associate the issuer queried with the top level
origin, because the answer to the redemption query does not leak information about
the issuers of the currently stored tokens. Similar to token query, redemption
query clears stale tokens.

Private State Token HTTP Header Fields {#pst-http-header-fields}
=================================

The 'Sec-Private-State-Token' Header Field {#sec-private-state-token}
----------------------------

The <dfn http-header>Sec-Private-State-Token</dfn> *request* header field sends
a collection of unsigned, masked tokens during issuance. During redemption, it
sends a singled signed, unmasked token along with associated redemption
metadata.

The <a http-header>Sec-Private-State-Token</a> *response* header field sends
a collection of signed, masked tokens. During redemption it sends the
just-created signed [=redemption record=].

It is a [=Structured Header=] whose value MUST be an [=structured header/string=]
[[!RFC8941]].

The header’s ABNF is:

``` abnf
Sec-Private-State-Token = sf-string
```


The 'Sec-Private-State-Token-Lifetime' Header Field {#sec-private-state-token-lifetime}
----------------------------

The <dfn http-header>`Sec-Private-State-Token-Lifetime`</dfn> response header
field gives the expiration for the [=redemption record=] 
given in the associated <a http-header>`Sec-Private-State-Token`</a>
response header. The expiration is given in seconds.

It is a [=Structured Header=] whose value MUST be an [=structured header/integer=]
[[!RFC8941]].

The header’s ABNF is:

``` abnf
Sec-Private-State-Token-Lifetime = sf-integer
```


The 'Sec-Private-State-Token-Version' Header Field {#sec-private-state-token-version}
----------------------------

The <dfn http-header>`Sec-Private-State-Token-Version`</dfn> header field gives
the "major version" of Private State Token protocol.

ISSUE(188): Define what "major version" actually means.

It is a [=Structured Header=] whose value MUST be an [=structured header/string=]
[[!RFC8941]].

The header’s ABNF is:

``` abnf
Sec-Private-State-Token-Version = sf-string
```


Privacy Considerations {#privacy}
=================================

Unlinkability {#unlinkability}
------------------------------

Cryptographic protocols [[!VOPRF]] and [[!PMB]] provide masked signatures. At
redemption time, issuers can recognize their signature on the provided token,
however they can not determine at what time or in which context they signed the token.
This prevents issuers from correlating their issuances on an origin with
redemptions on another origin. Issuers learn only the aggregate information
about the origins users visit.


Limiting Encoded Information {#limit-encoded-info}
--------------------------------------------------

User agents should enforce limits on the number of unique keys an issuer can have 
at any point in time, to preserve client privacy.  Without limits, an issuer could 
de-anonymize clients by simply using a unique key for each client. For [[!VOPRF]], the
number of keys is limited to six, and for [[!PMB]], the number is limited to
three keys.

Issuers can utilize different keys to represent different "labels", which correspond
to an arbritrary client state, such as client trust level or some other useful 
anti-fraud signal. Issuers are responsible for understanding this designation and 
sharing the key "labels" with token redeemers so they know how to interpret the 
significance of each token. This helps reduce reverse engineering from malicious 
actors and preserves client privacy over human-readable labels. When using [[!VOPRF]], 
the issuer's 6 keys can effectively represent six labels. Similarly, when using [[!PMB]], 
even though there are only up to three keys, the issuer can still utilize six labels 
by having each key correspond to the the private bit value (3 keys x 2 values = 6 labels). 
Both [[!VOPRF]] and [[!PMB]] encode the same amount of information in a token, however the
difference is [[!PMB]] utilizing a private bit.

### Potential Attack: Side Channel Fingerprinting {#side-channel-fingerprinting}

Unlinkability is lost if the issuer is able to use network-level fingerprinting
or any other side-channel and can associate the user agent at redemption time with
the user agent at token issuance time, even though the Private State Token API
itself has only stored and revealed limited amount of information about the
user agent.

Cross-site Information Transfer {#cross-site-info}
--------------------------------------------------

Private State Tokens transfer limited information between first-party contexts.
Underlying cryptographic protocols guarantee that each token only contains a
small amount of information. Still, if we allow many token redemptions on a
single page, the first-party cookie for user U on domain A can be encoded in
the Private State Token information channel and decoded on domain B, allowing
domain B to learn the user's domain A cookie until either 1p cookie is cleared.
Separate from the concern of channels allowing arbitrary communication between
domains, some identification attacks---for instance, a malicious redeemer
attempting to learn the exact set of issuers that have granted tokens to a
particular user, which could be identifying---have similar mitigations.

### Mitigation: Dynamic Issuance/Redemption Limits {#api-usage-limits}

To mitigate this attack, the specification places limits on both issuance and redemption.
User activation with the issuing site is required in the issuing operation. The
specification does not allow a third redemption in an [=implementation-defined=] time window,
usually 48 hours.

### Mitigation: Per-Site Issuer Limits {#per-issuer-limits}

The rate of identity leakage from one origin to another increases with the
number of issuers allowed in an origin. To avoid abuse, the user agent allows
association of at most two issers per top level origin. Issuers are associated
with top level origins for token query API as well, see [[#token-query]].

Security Considerations {#security}
===================================

Preventing Token Exhaustion {#token-exhaustion}
-----------------------------------------------

Malicious origins might attempt to exhaust all tokens stored in the user agent by
redeeming them all. To prevent this, the specification limits the number of redemption
operations. In the context of a given origin, two redemptions are allowed initially. However,
the third redemption is only allowed once more than an [=implementation-defined=] amount of time,
usually 48 hours, have elapsed since the first redemption.

Preventing Double Spending {#preventing-double-spend}
-----------------------------------------------------

Issuers can verify that each token is seen only once, because every redemption
is sent to the same token issuer. This means that even if a malicious piece of
malware exfiltrates all of a user's tokens, the tokens will run out over time.
Issuers can sign fewer tokens at a time to mitigate the risk.

IANA Considerations {#iana-considerations}
==========================================

This document intends to define the <a http-header>Sec-Private-State-Token</a>,
<a http-header>Sec-Private-State-Token-Lifetime</a>, <a http-header>Sec-Private-State-Token-Version</a>,
HTTP request header fields, and register them in the permanent message
header field registry ([[!RFC9110]]).

'Sec-Private-State-Token' Header Field {#iana-sec-private-state-token}
------------------------

Header field name: Sec-Private-State-Token

Applicable protocol: http

Status: standard

Author/Change controller: IETF

Specification document: this specification ([[#sec-private-state-token]])


'Sec-Private-State-Token-Lifetime' Header Field {#iana-sec-private-state-token-lifetime}
------------------------

Header field name: Sec-Private-State-Token-Lifetime

Applicable protocol: http

Status: standard

Author/Change controller: IETF

Specification document: this specification ([[#sec-private-state-token-lifetime]])


'Sec-Private-State-Token-Version' Header Field {#iana-sec-private-state-token-version}
------------------------

Header field name: Sec-Private-State-Token-Version

Applicable protocol: http

Status: standard

Author/Change controller: IETF

Specification document: this specification ([[#sec-private-state-token-version]])

<h2 id=acknowledgments class=no-num>Acknowledgments</h2>

Thanks to Alex Kallam, Charlie Harrison, Chris Fredrickson, David Van Cleve, Dylan Cutler,
Eric Trouton, Johann Hofmann, Kaustubha Govind, Mike Taylor, Ryan Kalla, and Sam
Schlesinger for their contributions. Thanks to Chris Wilson for reviewing and mentoring this spec.