Distributed Aggregation Protocol for Privacy Preserving Measurement

1.2.1. Glossary of Terms

Aggregate result:

The output of the aggregation function computed over a batch of measurements and an aggregation parameter. As defined in [VDAF].¶

Aggregate share:

A share of the aggregate result emitted by an Aggregator. Aggregate shares are reassembled by the Collector into the aggregate result, which is the final output of the aggregation function. As defined in [VDAF].¶

Aggregation function:

The function computed over the Clients' measurements. As defined in [VDAF].¶

Aggregation parameter:

Parameter used to prepare a set of measurements for aggregation. As defined in [VDAF].¶

Aggregator:

A server that receives input shares from Clients and validates and aggregates them with the help of the other Aggregators.¶

Batch:

A set of reports (i.e., measurements) that are aggregated into an aggregate result.¶

Batch duration:

The time difference between the oldest and newest report in a batch.¶

Batch interval:

A parameter of a query issued by the Collector that specifies the time range of the reports in the batch.¶

Client:

The DAP protocol role identifying a party that uploads a report. Note the distinction between a DAP Client (distinguished in this document by the capital "C") and an HTTP client (distinguished in this document by the phrase HTTP client), as the DAP Client is not the only role that sometimes acts as an HTTP client.¶

Collector:

The party that selects the aggregation parameter and receives the aggregate result.¶

Helper:

The Aggregator that executes the aggregation and collection interactions as instructed by the Leader.¶

Input share:

An Aggregator's share of a measurement. The input shares are output by the VDAF sharding algorithm. As defined in [VDAF].¶

Output share:

An Aggregator's share of the refined measurement resulting from successful execution of the VDAF preparation phase. Many output shares are combined into an aggregate share during the VDAF aggregation phase. As defined in [VDAF].¶

Leader:

The Aggregator that coordinates aggregation and collection with the Helper.¶

Measurement:

A plaintext input emitted by a Client (e.g., a count, summand, or string), before any encryption or secret sharing is applied. Depending on the VDAF in use, multiple values may be grouped into a single measurement. As defined in [VDAF].¶

Minimum batch size:

The minimum number of reports in a batch.¶

Public share:

The output of the VDAF sharding algorithm broadcast to each of the Aggregators. As defined in [VDAF].¶

Report:

A cryptographically protected measurement uploaded to the Leader by a Client. Comprised of a set of report shares.¶

Report Share:

An encrypted input share comprising a piece of a report.¶

4.2.1. Time-interval Batch Mode

The time-interval batch mode is designed to support applications in which reports are collected into batches grouped by an interval of time. The Collector specifies a "batch interval" that determines the time range for reports included in the batch. For each report in the batch, the time at which that report was generated (see Section 4.5) MUST fall within the batch interval specified by the Collector.¶

Typically the Collector issues queries for which the batch intervals are continuous, monotonically increasing, and have the same duration. For example, the sequence of batch intervals (1659544000, 1000), (1659545000, 1000), (1659546000, 1000), (1659547000, 1000) satisfies these conditions. (The first element of the pair denotes the start of the batch interval and the second denotes the duration.) However, this is not a requirement--the Collector may decide to issue queries out-of-order. In addition, the Collector may need to vary the duration to adjust to changing report upload rates.¶

4.2.2. Leader-selected Batch Mode

The leader-selected batch mode is used to support applications in which it is acceptable for reports to be batched in an arbitrary fashion by the Leader. Each batch of reports is identified by an opaque "batch ID". Both the reports included in each batch and the ID for each batch are allocated in an arbitrary fashion by the Leader.¶

The Collector will not know the set of batch IDs available for collection. To get the aggregate of a batch, the Collector issues a query, which does not include any information specifying a particular batch (see Section 4.2). The Leader selects a recent batch to aggregate. The Leader MUST select a batch that has not yet been associated with a collection job.¶

The Aggregators can output batches of any size that is larger than or equal to min_batch_size. The target batch size, if any, is implementation-specific, and may be equal to or greater than the minimum batch size. Deciding how soon batches should be output is also implementation-specific. Exactly sizing batches may be challenging for Leader deployments in which multiple, independent nodes running the aggregate interaction (see Section 4.6) need to be coordinated.¶

4.5.1. HPKE Configuration Request

Before the Client can upload its report to the Leader, it must know the HPKE configuration of each Aggregator. See Section 6 for information on HPKE algorithm choices.¶

Clients retrieve the HPKE configuration from each Aggregator by sending an HTTP GET request to {aggregator}/hpke_config.¶

An Aggregator responds to well-formed requests with HTTP status code 200 OK and an HpkeConfigList value, with media type "application/dap-hpke-config-list". The HpkeConfigList structure contains one or more HpkeConfig structures in decreasing order of preference. This allows an Aggregator to support multiple HPKE configurations simultaneously.¶

HpkeConfig HpkeConfigList<0..2^16-1>;

struct {
  HpkeConfigId id;
  HpkeKemId kem_id;
  HpkeKdfId kdf_id;
  HpkeAeadId aead_id;
  HpkePublicKey public_key;
} HpkeConfig;

opaque HpkePublicKey<0..2^16-1>;
uint16 HpkeAeadId; /* Defined in [HPKE] */
uint16 HpkeKemId;  /* Defined in [HPKE] */
uint16 HpkeKdfId;  /* Defined in [HPKE] */

Aggregators MUST allocate distinct id values for each HpkeConfig in an HpkeConfigList.¶

The Client MUST abort if any of the following happen for any HPKE config request:¶

• the GET request did not return a valid HPKE config list;¶

• the HPKE config list is empty; or¶

• no HPKE config advertised by the Aggregator specifies a supported a KEM, KDF, or AEAD algorithm triple.¶

Aggregators SHOULD use HTTP caching to permit client-side caching of this resource [RFC5861]. Aggregators SHOULD favor long cache lifetimes to avoid frequent cache revalidation, e.g., on the order of days. Aggregators can control this cached lifetime with the Cache-Control header, as in this example:¶

  Cache-Control: max-age=86400

Servers should choose a max-age value appropriate to the lifetime of their keys. Clients SHOULD follow the usual HTTP caching [RFC9111] semantics for HPKE configurations.¶

Note: Long cache lifetimes may result in Clients using stale HPKE configurations; Aggregators SHOULD continue to accept reports with old keys for at least twice the cache lifetime in order to avoid rejecting reports.¶

4.5.2. Upload Request

Clients upload reports by using an HTTP POST to {leader}/tasks/{task-id}/reports. The payload is a Report, with media type "application/dap-report", structured as follows:¶

struct {
  ReportID report_id;
  Time time;
} ReportMetadata;

struct {
  ReportMetadata report_metadata;
  opaque public_share<0..2^32-1>;
  HpkeCiphertext leader_encrypted_input_share;
  HpkeCiphertext helper_encrypted_input_share;
} Report;

• report_metadata is public metadata describing the report.¶

  • report_id is used by the Aggregators to ensure the report is not replayed (Figure 2). The Client MUST generate this by generating 16 random bytes using a cryptographically secure random number generator.¶

  • time is the time at which the report was generated. The Client SHOULD round this value down to the nearest multiple of the task's time_precision in order to ensure that that the timestamp cannot be used to link a report back to the Client that generated it.¶

• public_share is the public share output by the VDAF sharding algorithm. Note that the public share might be empty, depending on the VDAF.¶

• leader_encrypted_input_share is the Leader's encrypted input share.¶

• helper_encrypted_input_share is the Helper's encrypted input share.¶

Aggregators MAY require Clients to authenticate when uploading reports (see Section 7.3). If it is used, HTTP client authentication MUST use a scheme that meets the requirements in Section 3.1.¶

The handling of the upload request by the Leader MUST be idempotent as discussed in Section 9.2.2 of [RFC9110].¶

To generate a report, the Client begins by sharding its measurement into input shares and the public share using the VDAF's sharding algorithm (Section 5.1 of [VDAF]), using the report ID as the nonce:¶

(public_share, input_shares) = Vdaf.shard(
    "dap-12" || task_id,
    measurement, /* plaintext measurement */
    report_id,   /* nonce */
    rand,        /* randomness for sharding algorithm */
)

where task_id is the task ID. The last input comprises the randomness consumed by the sharding algorithm. The sharding randomness is a random byte string of length specified by the VDAF. The Client MUST generate this using a cryptographically secure random number generator.¶

The sharding algorithm will return two input shares. The first input share returned from the sharding algorithm is considered to be the Leader's input share, and the second input share is considered to be the Helper's input share.¶

The Client then wraps each input share in the following structure:¶

struct {
  Extension extensions<0..2^16-1>;
  opaque payload<0..2^32-1>;
} PlaintextInputShare;

Field extensions is set to the list of extensions intended to be consumed by the given Aggregator. (See Section 4.5.3.) Field payload is set to the Aggregator's input share output by the VDAF sharding algorithm.¶

Next, the Client encrypts each PlaintextInputShare plaintext_input_share as follows:¶

enc, payload = SealBase(pk,
  "dap-12 input share" || 0x01 || server_role,
  input_share_aad, plaintext_input_share)

where pk is the Aggregator's public key; 0x01 represents the Role of the sender (always the Client); server_role is the Role of the intended recipient (0x02 for the Leader and 0x03 for the Helper), plaintext_input_share is the Aggregator's PlaintextInputShare, and input_share_aad is an encoded message of type InputShareAad defined below, constructed from the same values as the corresponding fields in the report. The SealBase() function is as specified in [HPKE], Section 6.1 for the ciphersuite indicated by the HPKE configuration.¶

struct {
  TaskID task_id;
  ReportMetadata report_metadata;
  opaque public_share<0..2^32-1>;
} InputShareAad;

The Leader responds to well-formed requests with HTTP status code 201 Created. Malformed requests are handled as described in Section 3.2. Clients SHOULD NOT upload the same measurement value in more than one report if the Leader responds with HTTP status code 201 Created.¶

If the Leader does not recognize the task ID, then it MUST abort with error unrecognizedTask.¶

The Leader responds to requests whose Leader encrypted input share uses an out-of-date or unknown HpkeConfig.id value, indicated by HpkeCiphertext.config_id, with error of type 'outdatedConfig'. When the Client receives an 'outdatedConfig' error, it SHOULD invalidate any cached HpkeConfigList and retry with a freshly generated Report. If this retried upload does not succeed, the Client SHOULD abort and discontinue retrying.¶

If a report's ID matches that of a previously uploaded report, the Leader MUST ignore it. In addition, it MAY alert the Client with error reportRejected.¶

The Leader MUST ignore any report pertaining to a batch that has already been collected (see Section 4.6.1.4 for details). Otherwise, comparing the aggregate result to the previous aggregate result may result in a privacy violation. Note that this is also enforced by the Helper during the aggregation interaction. The Leader MAY also abort the upload interaction and alert the Client with error reportRejected.¶

The Leader MAY ignore any report whose timestamp is past the task's task_expiration. When it does so, it SHOULD also abort the upload interaction and alert the Client with error reportRejected. Client MAY choose to opt out of the task if its own clock has passed task_expiration.¶

The Leader may need to buffer reports while waiting to aggregate them (e.g., while waiting for an aggregation parameter from the Collector; see Section 4.7). The Leader SHOULD NOT accept reports whose timestamps are too far in the future. Implementors MAY provide for some small leeway, usually no more than a few minutes, to account for clock skew. If the Leader rejects a report for this reason, it SHOULD abort the upload interaction and alert the Client with error reportTooEarly. In this situation, the Client MAY re-upload the report later on.¶

If the Leader's input share contains an unrecognized extension, or if two extensions have the same ExtensionType, then the Leader MAY abort the upload request with error "invalidMessage". Note that this behavior is not mandatory because it requires the Leader to decrypt its input share.¶

4.5.3. Upload Extensions

Each PlaintextInputShare carries a list of extensions that Clients use to convey additional information to the Aggregator. Some extensions might be intended for both Aggregators; others may only be intended for a specific Aggregator. (For example, a DAP deployment might use some out-of-band mechanism for an Aggregator to verify that reports come from authenticated Clients. It will likely be useful to bind the extension to the input share via HPKE encryption.)¶

Each extension is a tag-length encoded value of the following form:¶

struct {
  ExtensionType extension_type;
  opaque extension_data<0..2^16-1>;
} Extension;

enum {
  TBD(0),
  (65535)
} ExtensionType;

Field "extension_type" indicates the type of extension, and "extension_data" contains information specific to the extension.¶

Extensions are mandatory-to-implement: If an Aggregator receives a report containing an extension it does not recognize, then it MUST reject the report. (See Section 4.6.1.4 for details.)¶

4.6.1. Aggregate Initialization

The Leader begins an aggregation job by choosing a set of candidate reports that pertain to the same DAP task and a job ID which MUST be unique within the scope of the task. The job ID is a 16-byte value, structured as follows:¶

opaque AggregationJobID[16];

The Leader can run this process for many sets of candidate reports in parallel as needed. After choosing a set of candidates, the Leader begins aggregation by splitting each report into report shares, one for each Aggregator. The Leader and Helper then run the aggregate initialization flow to accomplish two tasks:¶

1. Recover and determine which input report shares are valid.¶

2. For each valid report share, initialize the VDAF preparation process (see Section 5.2 of [VDAF]).¶

The Leader and Helper initialization behavior is detailed below.¶

Implementation note: the Leader will generally want to associate each report with a single aggregation job, as otherwise the duplicated reports will eventually be discarded as a replay. However, it is likely not appropriate to directly use the used-ID storage used for replay protection to determine which reports can be added to an aggregation job: certain errors (e.g. report_too_early) allow the report to be added to another aggregation job in the future; but storage into the used-ID storage is permanent.¶

(state, outbound) = Vdaf.ping_pong_leader_init(
    vdaf_verify_key,
    "dap-12" || task_id,
    agg_param,
    report_id,
    public_share,
    plaintext_input_share.payload)

struct {
  ReportMetadata report_metadata;
  opaque public_share<0..2^32-1>;
  HpkeCiphertext encrypted_input_share;
} ReportShare;

struct {
  ReportShare report_share;
  opaque payload<0..2^32-1>;
} PrepareInit;

opaque BatchID[32];

struct {
  BatchMode batch_mode;
  select (PartialBatchSelector.batch_mode) {
    case time_interval: Empty;
    case leader_selected: BatchID batch_id;
  };
} PartialBatchSelector;

struct {
  opaque agg_param<0..2^32-1>;
  PartialBatchSelector part_batch_selector;
  PrepareInit prepare_inits<0..2^32-1>;
} AggregationJobInitReq;

enum {
  continue(0),
  finished(1)
  reject(2),
  (255)
} PrepareRespState;

enum {
  reserved(0),
  batch_collected(1),
  report_replayed(2),
  report_dropped(3),
  hpke_unknown_config_id(4),
  hpke_decrypt_error(5),
  vdaf_prep_error(6),
  task_expired(7),
  invalid_message(8),
  report_too_early(9),
  (255)
} PrepareError;

struct {
  ReportID report_id;
  PrepareRespState prepare_resp_state;
  select (PrepareResp.prepare_resp_state) {
    case continue: opaque payload<0..2^32-1>;
    case finished: Empty;
    case reject:   PrepareError prepare_error;
  };
} PrepareResp;

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = reject;
  PrepareError report_replayed;
} PrepareResp;

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = reject;
  PrepareError prepare_error;
} PrepareResp;

(state, outbound) = Vdaf.ping_pong_helper_init(
    vdaf_verify_key,
    "dap-12" || task_id,
    agg_param,
    report_id,
    public_share,
    plaintext_input_share.payload)

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = reject;
  PrepareError prepare_error = vdaf_prep_error;
} PrepareResp;

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = continue;
  opaque payload<0..2^32-1> = outbound;
} PrepareResp;

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = reject;
  PrepareError report_replayed;
} PrepareResp;

enum {
  processing(0),
  ready(1),
} AggregationJobStatus;

struct {
  AggregationJobStatus status;
  select (AggregationJobResp.status) {
    case processing: Empty;
    case ready:      PrepareResp prepare_resps<0..2^32-1>;
  };
} AggregationJobResp;

plaintext_input_share = OpenBase(encrypted_input_share.enc, sk,
  "dap-12 input share" || 0x01 || server_role,
  input_share_aad, encrypted_input_share.payload)

4.6.2. Aggregate Continuation

In the continuation phase, the Leader drives the VDAF preparation of each report in the candidate report set until the underlying VDAF moves into a terminal state, yielding an output share for both Aggregators or a rejection.¶

Whether this phase is reached depends on the VDAF: for 1-round VDAFs, like Prio3, processing has already completed. Continuation is required for VDAFs that require more than one round.¶

struct {
  ReportID report_id;
  opaque payload<0..2^32-1>;
} PrepareContinue;

struct {
  uint16 step;
  PrepareContinue prepare_continues<0..2^32-1>;
} AggregationJobContinueReq;

(state, outbound) = Vdaf.ping_pong_helper_continued(
    "dap-12" || task_id,
    agg_param,
    state,
    inbound,
)

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = reject;
  PrepareError prepare_error = vdaf_prep_error;
} PrepareResp;

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = reject;
  PrepareError report_replayed;
} PrepareResp;

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = continue;
  opaque payload<0..2^32-1> = outbound;
} PrepareResp;

variant {
  ReportID report_id;
  PrepareRespState prepare_resp_state = finished;
} PrepareResp;

4.7.1. Collection Job Initialization

First, the Collector chooses a collection job ID:¶

opaque CollectionJobID[16];

This ID value MUST be unique within the scope of the corresponding DAP task.¶

To initiate the collection job, the collector issues a PUT request to {leader}/tasks/{task-id}/collection_jobs/{collection-job-id}. The body of the request has media type "application/dap-collection-job-req", and it is structured as follows:¶

struct {
  Query query;
  opaque agg_param<0..2^32-1>; /* VDAF aggregation parameter */
} CollectionJobReq;

The named parameters are:¶

• query, the Collector's query. The indicated batch mode MUST match the task's batch mode. Otherwise, the Leader MUST abort with error "invalidMessage".¶

• agg_param, an aggregation parameter for the VDAF being executed. This is the same value as in AggregationJobInitReq (see Section 4.6.1.1).¶

Collectors MUST authenticate their requests to Leaders using a scheme that meets the requirements in Section 3.1.¶

Depending on the VDAF scheme and how the Leader is configured, the Leader and Helper may already have prepared a sufficient number of reports satisfying the query and be ready to return the aggregate shares right away. However, this is not always the case. In fact, for some VDAFs, it is not be possible to begin running aggregation jobs (Section 4.6) until the Collector initiates a collection job. This is because, in general, the aggregation parameter is not known until this point. In certain situations it is possible to predict the aggregation parameter in advance. For example, for Prio3 the only valid aggregation parameter is the empty string. For these reasons, the collection job is handled asynchronously.¶

Upon receipt of a CollectionJobReq, the Leader begins by checking that it recognizes the task ID in the request path. If not, it MUST abort with error unrecognizedTask.¶

The Leader MAY further validate the request according to the requirements in Section 4.7.5 and abort with the indicated error, though some conditions such as the number of valid reports may not be verifiable while handling the CollectionJobReq message, and the batch will have to be re-validated later on regardless.¶

Changing a collection job's parameters is illegal, so further requests to PUT /tasks/{task-id}/collection_jobs/{collection-job-id} for the same collection-job-id but with a different CollectionJobReq in the body MUST fail with an HTTP client error status code.¶

The Leader responds to CollectionJobReqs with a CollectionJobResp, which is structured as follows:¶

enum {
  processing(0),
  ready(1),
} CollectionJobStatus;

struct {
  PartialBatchSelector part_batch_selector;
  uint64 report_count;
  Interval interval;
  HpkeCiphertext leader_encrypted_agg_share;
  HpkeCiphertext helper_encrypted_agg_share;
} Collection;

struct {
  CollectionJobStatus status;
  select (CollectionJob.status) {
    case processing: Empty;
    case ready:      Collection;
  }
} CollectionJobResp;

The body's media type is "application/dap-collection-job-resp". The Collection structure includes the following:¶

• part_batch_selector: Information used to bind the aggregate result to the query. For leader-selected tasks, this includes the batch ID assigned to the batch by the Leader. The indicated batch mode MUST match the task's batch mode.¶

• report_count: The number of reports included in the batch.¶

• interval: The smallest interval of time that contains the timestamps of all reports included in the batch, such that the interval's start and duration are both multiples of the task's time_precision parameter. Note that in the case of a time-interval query (see Section 4.2), this interval can be smaller than the one in the corresponding CollectionJobReq.query.¶

• leader_encrypted_agg_share: The Leader's aggregate share, encrypted to the Collector (see Section 4.7.4).¶

• helper_encrypted_agg_share: The Helper's aggregate share, encrypted to the Collector (see Section 4.7.4).¶

If the Leader finds the CollectionJobReq to be valid, it immediately responds with HTTP status 201 Created with a body containing a CollectionJobResp with the status field set to processing. The Leader SHOULD include a Retry-After header field to suggest a polling interval to the Collector.¶

After receiving the response to its CollectionJobReq, the Collector periodically makes HTTP GET requests /tasks/{task-id}/collection_jobs/{collection-job-id} to check on the status of the collect job and eventually obtain the result. The Leader responds to GET requests with HTTP status 200 and the status field reflecting the current state of the job. When the collection job is processing, the response SHOULD include a Retry-After header field to suggest a polling interval to the Collector.¶

The Leader then begins working with the Helper to aggregate the reports satisfying the query (or continues this process, depending on the VDAF) as described in Section 4.6.¶

The Leader first checks whether it can construct a batch for the collection job by applying the requirements in Section 4.7.5. If so, then the Leader obtains the Helper's aggregate share following the aggregate-share request flow described in Section 4.7.2. If not, it either aborts the collection job or tries again later, depending on which requirement in Section 4.7.5 was not met. If the Leader has a pending aggregation job that overlaps with the batch and aggregation parameter for the collection job, the Leader MUST first complete the aggregation job before proceeding and requesting an aggregate share from the Helper. This avoids a race condition between aggregation and collection jobs that can yield trivial batch mismatch errors.¶

Once both aggregate shares are successfully obtained, the Leader responds to subsequent HTTP GET requests with the status field set to ready and the Collection field populated with the encrypted aggregate shares. The Collector stops polling once receiving this final request.¶

If obtaining aggregate shares fails, then the Leader responds to subsequent HTTP GET requests to the collection job with an HTTP error status and a problem document as described in Section 3.2.¶

The Leader MAY respond with HTTP status 204 No Content to requests to a collection job if the results have been deleted.¶

The Collector can send an HTTP DELETE request to the collection job, which indicates to the Leader that it can abandon the collection job and discard all state related to it.¶

4.7.2. Obtaining Aggregate Shares

The Leader must obtain the Helper's encrypted aggregate share before it can complete a collection job. To do this, the Leader first computes a checksum over the reports included in the batch. The checksum is computed by taking the SHA256 [SHS] hash of each report ID from the Client reports included in the aggregation, then combining the hash values with a bitwise-XOR operation.¶

Then the Leader sends a POST request to {helper}/tasks/{task-id}/aggregate_shares with the following message:¶

struct {
  BatchMode batch_mode;
  select (BatchSelector.batch_mode) {
    case time_interval: Interval batch_interval;
    case leader_selected: BatchID batch_id;
  };
} BatchSelector;

struct {
  BatchSelector batch_selector;
  opaque agg_param<0..2^32-1>;
  uint64 report_count;
  opaque checksum[32];
} AggregateShareReq;

The media type of the request is "application/dap-aggregate-share-req". The message contains the following parameters:¶

• batch_selector: The "batch selector", which encodes parameters used to determine the batch being aggregated. The value depends on the batch mode for the task:¶

  • For time-interval tasks, the request specifies the batch interval.¶

  • For leader-selected tasks, the request specifies the batch ID.¶

  The indicated batch mode MUST match the task's batch mode. Otherwise, the Helper MUST abort with "invalidMessage".¶

• agg_param: The opaque aggregation parameter for the VDAF being executed. This value MUST match the AggregationJobInitReq message for each aggregation job used to compute the aggregate shares (see Section 4.6.1.1) and the aggregation parameter indicated by the Collector in the CollectionJobReq message (see Section 4.7.1).¶

• report_count: The number number of reports included in the batch.¶

• checksum: The batch checksum.¶

Leaders MUST authenticate their requests to Helpers using a scheme that meets the requirements in Section 3.1.¶

To handle the Leader's request, the Helper first ensures that it recognizes the task ID in the request path. If not, it MUST abort with error unrecognizedTask. The Helper then verifies that the request meets the requirements for batch parameters following the procedure in Section 4.7.5.¶

Next, it computes a checksum based on the reports that satisfy the query, and checks that the report_count and checksum included in the request match its computed values. If not, then it MUST abort with an error of type "batchMismatch".¶

Next, it computes the aggregate share agg_share corresponding to the set of output shares, denoted out_shares, for the batch interval, as follows:¶

agg_share = Vdaf.aggregate(agg_param, out_shares)

Implementation note: For most VDAFs, including Prio3, it is possible to aggregate output shares as they arrive rather than wait until the batch is collected. For the batch modes specified in this document, it is necessary to enforce the batch parameters as described in Section 4.7.5 so that the Aggregator knows which aggregate share to update.¶

The Helper then encrypts agg_share under the Collector's HPKE public key as described in Section 4.7.4, yielding encrypted_agg_share. Encryption prevents the Leader from learning the actual result, as it only has its own aggregate share and cannot compute the Helper's.¶

The Helper responds to the Leader with HTTP status code 200 OK and a body consisting of an AggregateShare, with media type "application/dap-aggregate-share":¶

struct {
  HpkeCiphertext encrypted_aggregate_share;
} AggregateShare;

encrypted_aggregate_share.config_id is set to the Collector's HPKE config ID. encrypted_aggregate_share.enc is set to the encapsulated HPKE context enc computed above and encrypted_aggregate_share.ciphertext is the ciphertext encrypted_agg_share computed above.¶

The Helper's handling of this request MUST be idempotent. That is, if multiple identical, valid AggregateShareReqs are received, they should all yield the same response.¶

After receiving the Helper's response, the Leader uses the HpkeCiphertext to finalize a collection job (see Section 4.7.3).¶

Once an AggregateShareReq has been issued for the batch determined by a given query, it is an error for the Leader to issue any more aggregation jobs for additional reports that satisfy the query. These reports will be rejected by the Helper as described in Section 4.6.1.4.¶

Before completing the collection job, the Leader also computes its own aggregate share agg_share by aggregating all of the prepared output shares that fall within the batch interval. Finally, it encrypts its aggregate share under the Collector's HPKE public key as described in Section 4.7.4.¶

4.7.3. Collection Job Finalization

Once the Collector has received a collection job from the Leader, it can decrypt the aggregate shares and produce an aggregate result. The Collector decrypts each aggregate share as described in Section 4.7.4. Once the Collector successfully decrypts all aggregate shares, it unshards the aggregate shares into an aggregate result using the VDAF's unshard algorithm. In particular, let leader_agg_share denote the Leader's aggregate share, helper_agg_share denote the Helper's aggregate share, let report_count denote the report count sent by the Leader, and let agg_param be the opaque aggregation parameter. The final aggregate result is computed as follows:¶

agg_result = Vdaf.unshard(agg_param,
                          [leader_agg_share, helper_agg_share],
                          report_count)

4.7.4. Aggregate Share Encryption

Encrypting an aggregate share agg_share for a given AggregateShareReq is done as follows:¶

(enc, payload) = SealBase(
    pk,
    "dap-12 aggregate share" || server_role || 0x00,
    agg_share_aad,
    agg_share)

where pk is the HPKE public key encoded by the Collector's HPKE key, server_role is the Role of the encrypting server (0x02 for the Leader and 0x03 for a Helper), 0x00 represents the Role of the recipient (always the Collector), and agg_share_aad is a value of type AggregateShareAad. The SealBase() function is as specified in [HPKE], Section 6.1 for the ciphersuite indicated by the HPKE configuration.¶

struct {
  TaskID task_id;
  opaque agg_param<0..2^32-1>;
  BatchSelector batch_selector;
} AggregateShareAad;

• task_id is the ID of the task the aggregate share was computed in.¶

• agg_param is the aggregation parameter used to compute the aggregate share.¶

• batch_selector is the is the batch selector from the AggregateShareReq (for the Helper) or the batch selector computed from the Collector's query (for the Leader).¶

The Collector decrypts these aggregate shares using the opposite process. Specifically, given an encrypted input share, denoted enc_share, for a given batch selector, decryption works as follows:¶

agg_share = OpenBase(
    enc_share.enc,
    sk,
    "dap-12 aggregate share" || server_role || 0x00,
    agg_share_aad,
    enc_share.payload)

where sk is the HPKE secret key, server_role is the Role of the server that sent the aggregate share (0x02 for the Leader and 0x03 for the Helper), 0x00 represents the Role of the recipient (always the Collector), and agg_share_aad is an AggregateShareAad message constructed from the task ID and the aggregation parameter in the collect request, and a batch selector. The value of the batch selector used in agg_share_aad is computed by the Collector from its query and the response to its query as follows:¶

• For time-interval tasks, the batch selector is the batch interval specified in the query.¶

• For leader-selected tasks, the batch selector is the batch ID sent in the response.¶

The OpenBase() function is as specified in [HPKE], Section 6.1 for the ciphersuite indicated by the HPKE configuration.¶

4.7.5. Batch Validation

Before a Leader runs a collection job or a Helper responds to an AggregateShareReq, it must first check that the job or request does not violate the parameters associated with the DAP task. It does so as described here. Where we say that an Aggregator MUST abort with some error, then:¶

• Leaders should respond to subsequent HTTP GET requests to the collection job with the indicated error.¶

• Helpers should respond to the AggregateShareReq with the indicated error.¶

First the Aggregator checks that the batch respects any "boundaries" determined by the batch mode. These are described in the subsections below. If the boundary check fails, then the Aggregator MUST abort with an error of type "batchInvalid".¶

Next, the Aggregator checks that batch contains a valid number of reports, as determined by the batch mode. If the size check fails, then Helpers MUST abort with an error of type "invalidBatchSize". Leaders SHOULD wait for more reports to be validated and try the collection job again later.¶

Next, the Aggregator checks that the batch has not been queried with multiple distinct aggregation parameters. If the batch has been queried with more than one distinct aggregation parameter, the Aggregator MUST abort with error of type "batchQueriedMultipleTimes".¶

Finally, the Aggregator checks that the batch does not contain a report that was included in any previous batch. If this batch overlap check fails, then the Aggregator MUST abort with error of type "batchOverlap". For time-interval tasks, it is sufficient (but not necessary) to check that the batch interval does not overlap with the batch interval of any previous query. If this batch interval check fails, then the Aggregator MAY abort with error of type "batchOverlap".¶

5.1.1. Client Capabilities

Clients have limited capabilities and requirements. Their only inputs to the protocol are (1) the parameters configured out of band and (2) a measurement. Clients are not expected to store any state across any upload flows, nor are they required to implement any sort of report upload retry mechanism. By design, the protocol in this document is robust against individual Client upload failures since the protocol output is an aggregate over all inputs.¶

5.1.2. Aggregator Capabilities

Leaders and Helpers have different operational requirements. The design in this document assumes an operationally competent Leader, i.e., one that has no storage or computation limitations or constraints, but only a modestly provisioned Helper, i.e., one that has computation, bandwidth, and storage constraints. By design, Leaders must be at least as capable as Helpers, where Helpers are generally required to:¶

• Support the aggregate interaction, which includes validating and aggregating reports; and¶

• Publish and manage an HPKE configuration that can be used for the upload interaction.¶

In addition, for each DAP task, the Helper is required to:¶

• Implement some form of batch-to-report index, as well as inter- and intra-batch replay mitigation storage, which includes some way of tracking batch report size. Some of this state may be used for replay attack mitigation. The replay mitigation strategy is described in Section 4.6.1.4.¶

Beyond the minimal capabilities required of Helpers, Leaders are generally required to:¶

• Support the upload interaction and store reports; and¶

• Track batch report size during each collect flow and request encrypted output shares from Helpers.¶

In addition, for each DAP task, the Leader is required to:¶

• Implement and store state for the form of inter- and intra-batch replay mitigation in Figure 2. This requires storing the report IDs of all reports processed for a given task. Implementations may find it helpful to track additional information, like the timestamp, so that the storage used for anti-replay can be sharded efficiently.¶

5.1.3. Collector Capabilities

Collectors statefully interact with Aggregators to produce an aggregate output. Their input to the protocol is the task parameters, configured out of band, which include the corresponding batch window and size. For each collect invocation, Collectors are required to keep state from the start of the protocol to the end as needed to produce the final aggregate output.¶

Collectors must also maintain state for the lifetime of each task, which includes key material associated with the HPKE key configuration.¶

5.4.1. Reducing Storage Requirements

In general, the Aggregators are required to keep state for tasks and all valid reports for as long as collection requests can be made for them. However, it is not necessary to store the complete reports. Each Aggregator only needs to store an aggregate share for each possible batch interval (for time-interval) or batch ID (for leader-selected), along with a flag indicating whether the aggregate share has been collected. This is due to the requirement that in the time-interval case, the batch interval respect the boundaries defined by the DAP parameters; and that in leader-selected case, a batch is determined entirely by a batch ID. (See Section 4.7.5.)¶

However, Aggregators are also required to implement several per-report checks that require retaining a number of data artifacts. For example, to detect replay attacks, it is necessary for each Aggregator to retain the set of report IDs of reports that have been aggregated for the task so far. Depending on the task lifetime and report upload rate, this can result in high storage costs. To alleviate this burden, DAP allows Aggregators to drop this state as needed, so long as reports are dropped properly as described in Section 4.6.1.4. Aggregators SHOULD take steps to mitigate the risk of dropping reports (e.g., by evicting the oldest data first).¶

Furthermore, the Aggregators must store data related to a task as long as the current time has not passed this task's task_expiration. Aggregator MAY delete the task and all data pertaining to this task after task_expiration. Implementors SHOULD provide for some leeway so the Collector can collect the batch after some delay.¶

5.4.2. Distributed-systems and Synchronization Concerns

Various parts of a DAP implementation will need to synchronize in order to ensure correctness during concurrent operation. This section describes the relevant concerns and makes suggestions as to potential implementation tradeoffs.¶

• The upload interaction requires the Leader to ignore uploaded reports with a duplicated ID, including concurrently-uploaded reports. This might be implemented by synchronization or via an eventually-consistent process. If the Leader wishes to alert the Client with a reportRejected error, synchronization will be necessary to ensure all but one concurrent request receive the error.¶

• The Leader is responsible for generating aggregation jobs, and will generally want to place each report in exactly one aggregation job. (The only event in which a Leader will want to place a report in multiple aggregation jobs is if the Helper rejects the report with report_too_early, in which case the Leader can place the report into a later aggregation job.) This may require synchronization between different components of the system which are generating aggregation jobs. Note that placing a report into more than one aggregation job will result in a loss of throughput, rather than a loss of correctness, privacy, or robustness, so it is acceptable for implementations to use an eventually-consistent scheme which may rarely place a report into multiple aggregation jobs.¶

• Aggregation is implemented as a sequence of aggregation steps by both the Leader and the Helper. The Leader must ensure that each aggregation job is only processed once concurrently, which may require synchronization between the components responsible for performing aggregation. The Helper must ensure that concurrent requests against the same aggregation job are handled appropriately, which requires synchronization between the components handling aggregation requests.¶

• Aggregation requires checking and updating used-report storage as part of implementing replay protection. This must be done while processing the aggregation job, though which steps the checks are performed at is up to the implementation. The checks and storage require synchronization, so that if two aggregation jobs contianing the same report are processed, at most one instance of the report will be aggregated. However, the interaction with the used-report storage does not necessarily have to be synchronized with the processing and storage for the remainder of the aggregation process. For example, used-report storage could be implemented in a separate datastore than is used for the remainder of data storage, without any transactionality between updates to the two datastores.¶

• The aggregation and collection interactions require synchronization to avoid modifying the aggregate of a batch after it has already been collected. Any reports being aggregated which pertain to a batch which has already been collected must fail with a batch_collected error; correctly determining this requires synchronizing aggregation with the completion of collection jobs (for the Leader) or aggregate share requests (for the Helper). Also, the Leader must complete all outstanding aggregation jobs for a batch before requesting aggregate shares from the Helper, again requiring synchronization between the Leader's collection and aggregation interactions. Further, the Helper must determine the aggregated report count and checksum of aggregated report IDs before responding to an aggregate share request, requiring synchronization between the Helper's collection and aggregation interactions.¶

7.6.1. VDAF Verification Key Requirements

Knowledge of the verification key would allow a Client to forge a report with invalid values that will nevertheless pass verification. Therefore, the verification key must be kept secret from Clients.¶

Furthermore, for a given report, it may be possible to craft a verification key which leaks information about that report's measurement during VDAF preparation. Therefore, the verification key for a task SHOULD be chosen before any reports are generated. Moreover, it SHOULD be fixed for the lifetime of the task and not be rotated. One way to ensure that the verification key is generated independently from any given report is to derive the key based on the task ID and some previously agreed upon secret (verify_key_seed) between Aggregators, as follows:¶

verify_key = HKDF-Expand(
    HKDF-Extract(
        "verify_key",    # salt
        verify_key_seed, # IKM
    ),
    task_id,             # info
    VERIFY_KEY_SIZE,     # L
)

Here, VERIFY_KEY_SIZE is the length of the verification key, and HKDF-Extract and HKDF-Expand are as defined in [RFC5869].¶

This requirement comes from current security analysis for existing VDAFs. In particular, the security proofs for Prio3 require that the verification key is chosen independently of the generated reports.¶

7.6.2. Batch Parameters

An important parameter of a DAP deployment is the minimum batch size. If a batch includes too few reports, then the aggregate result can reveal information about individual measurements. Aggregators enforce the agreed-upon minimum batch size during collection, but implementations SHOULD also opt out of participating in a DAP task if the minimum batch size is too small. This document does not specify how to choose an appropriate minimum batch size, but an appropriate value may be determined from the differential privacy (Section 7.5) parameters in use, if any.¶

7.6.3. Task Configuration Agreement and Consistency

In order to execute a DAP task, it is necessary for all parties to ensure they agree on the configuration of the task. However, it is possible for a party to participate in the execution of DAP without knowing all of the task's parameters. For example, a Client can upload a report (Section 4.5) without knowing the minimum batch size that is enforced by the Aggregators during collection (Section 4.7).¶

Depending on the deployment model, agreement can require that task parameters are visible to all parties such that each party can choose whether to participate based on the value of any parameter. This includes the parameters enumerated in Section 4.3 and any additional parameters implied by upload extensions Section 4.5.3 used by the task. Since meaningful privacy requires that multiple Clients contribute to a task, they should also share a consistent view of the task configuration.¶

8.1.1. Message versioning

Media types for the HTTP requests are specific to this version of DAP. When a new major enhancement is proposed that results in newer IETF specification for DAP, a new set of media types need to be defined. In other words, newer versions of DAP will not be backward compatible with this version of DAP.¶

(NOTE TO RFC EDITOR: Remove this paragraph.) HTTP requests with DAP media types MAY express an optional parameter 'version', following Section 8.3 of [RFC9110]. Value of this parameter indicates current draft version of the protocol the component is using. This MAY be used as a hint by the receiver of the request to do compatibility checks between client and server. For example, A report submission to leader from a client that supports draft-ietf-ppm-dap-09 could have the header Media-Type: application/dap-report;version=09.¶

8.1.2. "application/dap-hpke-config-list" media type

Type name:

application¶

Subtype name:

dap-hpke-config-list¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.3¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.3. "application/dap-report" media type

Type name:

application¶

Subtype name:

dap-report¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.5.2¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.4. "application/dap-aggregation-job-init-req" media type

Type name:

application¶

Subtype name:

dap-aggregation-job-init-req¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.7¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.5. "application/dap-aggregation-job-resp" media type

Type name:

application¶

Subtype name:

dap-aggregation-job-resp¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.7¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.6. "application/dap-aggregation-job-continue-req" media type

Type name:

application¶

Subtype name:

dap-aggregation-job-continue-req¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.7¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.7. "application/dap-aggregate-share-req" media type

Type name:

application¶

Subtype name:

dap-aggregate-share-req¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.7¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.8. "application/dap-aggregate-share" media type

Type name:

application¶

Subtype name:

dap-aggregate-share¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.7¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.9. "application/dap-collection-job-req" media type

Type name:

application¶

Subtype name:

dap-collection-job-req¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.7¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.1.10. "application/dap-collection-job-resp" media type

Type name:

application¶

Subtype name:

dap-collection-job-resp¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

only "8bit" or "binary" is permitted¶

Security considerations:

see Section 4.7¶

Interoperability considerations:

N/A¶

Published specification:

this specification¶

Applications that use this media type:

N/A¶

Fragment identifier considerations:

N/A¶

Additional information:

Magic number(s):

N/A¶

Deprecated alias names for this type:

N/A¶

File extension(s):

N/A¶

Macintosh file type code(s):

N/A¶

Person and email address to contact for further information:

see Authors' Addresses section¶

Intended usage:

COMMON¶

Restrictions on usage:

N/A¶

Author:

see Authors' Addresses section¶

Change controller:

IESG¶

8.2.1. Batch Modes Registry

This document requests creation of a new registry for Batch Modes. This registry should contain the following columns:¶

• TODO Define how we want to structure this registry.¶

8.2.2. Upload Extension Registry

This document requests creation of a new registry for extensions to the upload interaction (Section 4.5). This registry should contain the following columns:¶

• TODO Define how we want to structure this registry.¶

8.2.3. Prepare Error Registry

This document requests creation of a new registry for PrepareError values. This registry should contain the following columns:¶

Name:

The name of the PrepareError value¶

Value:

The 1-byte value of the PrepareError value¶

Reference:

A reference to where the PrepareError type is defined.¶

The initial contents of this registry are as defined in Section 4.6.1.2, with this document as the reference.¶