Distributed Aggregation Protocol for Privacy Preserving Measurement

4.1.1. Time-interval Queries

The first query type, time_interval, is designed to support applications in which reports are collected over a long period 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.4) 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.) Of course, there are cases in which Collector may need to issue queries out-of-order. For example, a previous batch might need to be queried again with a different aggregation parameter (e.g, for Poplar1). In addition, the Collector may need to vary the duration to adjust to changing report upload rates.¶

4.1.2. Fixed-size Queries

The fixed_size query type is used to support applications in which the Collector needs the ability to strictly control the sample size. This is particularly important for controlling the amount of noise added to reports by Clients (or added to aggregate shares by Aggregators) in order to achieve differential privacy.¶

For this query type, the Aggregators group reports into arbitrary batches such that each batch has roughly the same number of reports. These batches are identified by opaque "batch IDs", allocated in an arbitrary fashion by the Leader.¶

To get the aggregate of a batch, the Collector issues a query specifying the batch ID of interest (see Section 4.1). The Collector may not know which batch ID it is interested in; in this case, it can also issue a query of type current_batch, which allows the Leader to select a recent batch to aggregate. The Leader SHOULD select a batch which has not yet began collection.¶

In addition to the minimum batch size common to all query types, the configuration includes a parameter max_batch_size that determines maximum number of reports per batch.¶

Implementation note: The goal for the Aggregators is to aggregate precisely min_batch_size reports per batch. Doing so, however, may be challenging for Leader deployments in which multiple, independent nodes running the aggregate sub-protocol (see Section 4.5) need to be coordinated. The maximum batch size is intended to allow room for error. Typically the difference between the minimum and maximum batch size will be a small fraction of the target batch size for each batch.¶

[OPEN ISSUE: It may be feasible to require a fixed batch size, i.e., min_batch_size == max_batch_size. We should know better once we've had some implementation/deployment experience.]¶

4.4.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. Clients MAY specify a query parameter task_id whose value is the task ID whose HPKE configuration they want. If the Aggregator does not recognize the task ID, then it MUST abort with error unrecognizedTask.¶

An Aggregator is free to use different HPKE configurations for each task with which it is configured. If the task ID is missing from the Client's request, the Aggregator MAY abort with an error of type missingTaskID, in which case the Client SHOULD retry the request with a well-formed task ID included.¶

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.¶

[TODO: Allow Aggregators to return HTTP status code 403 Forbidden in deployments that use authentication to avoid leaking information about which tasks exist.]¶

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

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

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

[OPEN ISSUE: Decide whether to expand the width of the id.]¶

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 failed or 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 follows:¶

  Cache-Control: max-age=86400

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.4.2. Upload Request

Clients upload reports by using an HTTP PUT 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 appears in at most one batch (see Section 4.5.1.4). 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.2.1). If it is used, Client authentication MUST use a scheme that meets the requirements in Section 3.1.¶

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.measurement_to_input_shares(
    measurement, /* plaintext measurement */
    report_id,   /* nonce */
    rand,        /* randomness for sharding algorithm */
)

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 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.4.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-07 input share" || 0x01 || server_role,
  input_share_aad, plaintext_input_share)

where pk is the Aggregator's public key; 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. See the implementation note in Section 4.5.1.4.¶

The Leader MUST ignore any report pertaining to a batch that has already been collected (see Section 4.5.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 sub-protocol. The Leader MAY also abort the upload protocol 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 protocol 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.6). 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 protocol 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.4.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.5.1.4 for details.)¶

4.5.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.¶

(state, outbound) = Vdaf.ping_pong_leader_init(
    vdaf_verify_key,
    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;

struct {
  QueryType query_type;
  select (PartialBatchSelector.query_type) {
    case time_interval: Empty;
    case fixed_size: BatchID batch_id;
  };
} PartialBatchSelector;

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

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

enum {
  batch_collected(0),
  report_replayed(1),
  report_dropped(2),
  hpke_unknown_config_id(3),
  hpke_decrypt_error(4),
  vdaf_prep_error(5),
  batch_saturated(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;

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

(state, outbound) = Vdaf.ping_pong_helper_init(vdaf_verify_key,
                                               agg_param,
                                               report_id,
                                               public_share,
                                               plaintext_input_share.payload)

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

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

struct {
  PrepareResp prepare_resps<1..2^32-1>;
} AggregationJobResp;

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

4.5.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<1..2^32-1>;
} AggregationJobContinueReq;

(state, outbound) = Vdaf.ping_pong_helper_continued(agg_param,
                                                    state,
                                                    inbound)

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

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

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

4.6.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-collect-req", and it is structured as follows:¶

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

The named parameters are:¶

• query, the Collector's query. The indicated query type MUST match the task's query type. 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.5.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.5) 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 CollectionReq, 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.6.5 and abort with the indicated error, though some conditions such as the number of valid reports may not be verifiable while handling the CollectionReq message, and the batch will have to be re-validated later on regardless.¶

If the Leader finds the CollectionReq to be valid, it immediately responds with HTTP status 201.¶

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.5.¶

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

After receiving the response to its CollectionReq, the Collector makes an HTTP POST request to the collection job URI to check on the status of the collect job and eventually obtain the result. If the collection job is not finished yet, the Leader responds with HTTP status 202 Accepted. The response MAY include a Retry-After header field to suggest a polling interval to the Collector.¶

Asynchronously from any request from the Collector, the Leader attempts to run the collection job. It first checks whether it can construct a batch for the collection job by applying the requirements in Section 4.6.5. If so, then the Leader obtains the Helper's aggregate share following the aggregate-share request flow described in Section 4.6.2. If not, it either aborts the collection job or tries again later, depending on which requirement in Section 4.6.5 was not met.¶

Once both aggregate shares are successfully obtained, the Leader responds to subsequent HTTP POST requests to the collection job with HTTP status code 200 OK and a body consisting of a Collection:¶

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

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

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

  [OPEN ISSUE: What should the Collector do if the query type doesn't match?]¶

• 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 type query (see Section 4.1), this interval can be smaller than the one in the corresponding CollectionReq.query.¶
• leader_encrypted_agg_share: The Leader's aggregate share, encrypted to the Collector.¶
• helper_encrypted_agg_share: The Helper's aggregate share, encrypted to the Collector.¶

If obtaining aggregate shares fails, then the Leader responds to subsequent HTTP POST 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.6.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 {
  QueryType query_type;
  select (BatchSelector.query_type) {
    case time_interval: Interval batch_interval;
    case fixed_size: 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 query type for the task:¶

  • For time_interval tasks, the request specifies the batch interval.¶
  • For fixed_size tasks, the request specifies the batch ID.¶

  The indicated query type MUST match the task's query type. 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.5.1.1) and the aggregation parameter indicated by the Collector in the CollectionReq message (see Section 4.6.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.6.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.out_shares_to_agg_share(agg_param, out_shares)

Implementation note: For most VDAFs, it is possible to aggregate output shares as they arrive rather than wait until the batch is collected. To do so however, it is necessary to enforce the batch parameters as described in Section 4.6.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.6.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 while only consuming one unit of the task's max_batch_query_count (see Section 4.6.5).¶

After receiving the Helper's response, the Leader uses the HpkeCiphertext to finalize a collection job (see Section 4.6.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.5.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.6.4.¶

4.6.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.6.4. Once the Collector successfully decrypts all aggregate shares, it unshards the aggregate shares into an aggregate result using the VDAF's agg_shares_to_result 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.agg_shares_to_result(agg_param,
                                       [leader_agg_share, helper_agg_share],
                                       report_count)

4.6.4. Aggregate Share Encryption

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

enc, payload = SealBase(pk, "dap-07 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), 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-07 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), 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 fixed_size tasks, the batch selector is the batch ID assigned sent in the response.¶

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

4.6.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 POST 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 query type. 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 query type. 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 too many times. This is determined by the maximum number of times a batch can be queried, max_batch_query_count. If the batch has been queried with more than max_batch_query_count distinct aggregation parameters, the Aggregator MUST abort with error of type "batchQueriedTooManyTimes".¶

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".¶

[[OPEN ISSUE: #195 tracks how we might relax this constraint to allow for more collect query flexibility. As of now, this is quite rigid and doesn't give the Collector much room for mistakes.]]¶

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 sub-protocol, which includes validating and aggregating reports; and¶
• Publish and manage an HPKE configuration that can be used for the upload protocol.¶

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.5.1.4.¶

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

• Support the upload protocol 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 Section 4.5.1.4.¶

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 collect requests can be made for them. In particular, Aggregators must store a batch as long as the batch has not been queried more than max_batch_query_count times. However, it is not always necessary to store the reports themselves. For schemes like Prio3 [VDAF] in which reports are verified only once, each Aggregator only needs to store its aggregate share for each possible batch interval, along with the number of times the aggregate share was used in a batch. This is due to the requirement that the batch interval respect the boundaries defined by the DAP parameters. (See Section 4.6.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.5.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.¶

7.1.1. Client/user

7.1.2. Aggregator

7.1.3. Leader

The Leader is also an Aggregator, and so all the assets, capabilities and mitigations available to Aggregators also apply to the Leader.¶

7.1.4. Aggregator collusion

If all Aggregators collude (e.g. by promiscuously sharing unencrypted input shares), then none of the properties of the system hold. Accordingly, such scenarios are outside of the threat model.¶

7.1.5. Attacker on the network

We assume the existence of attackers on the network links between participants. Most passive network attacks are mitigated by DAP's requirement of HTTPS for all traffic and mutual authentication for key protocol interactions (see Section 3). Nonetheless, there remain information leaks that deployments should be aware of.¶

7.2.1. Client authentication

In settings where it is practical for each Client to have an identity provisioned (e.g., a user logged into a backend service or a hardware device programmed with an identity), Client authentication is a highly effective way for the Aggregators (or an authenticating proxy deployed between clients and the Aggregators; see Section 7.3) to ensure that all reports come from authentic Clients and to enforce policy on things like upload rates. Note that because the Helper never handles messages directly from the Clients, reports would have to use an extension (Section 4.4.3) to convey authentication information to the Helper.¶

However, in some deployments, it will not be practical to require Clients to authenticate, so Client authentication is not mandatory in DAP. For example, a widely distributed application that does not require its users to log in to any service has no obvious way to authenticate its report uploads.¶

7.4.1. Verification key requirements

The verification key for a task SHOULD be chosen before any reports are generated. It SHOULD be fixed for the lifetime of the task and not be rotated. One way to ensure this is to include the verification key in a derivation of the task ID.¶

This consideration comes from current security analysis for existing VDAFs. For example, to ensure that the security proofs for Prio3 hold, the verification key MUST be chosen independently of the generated reports. This can be achieved as recommended above.¶

7.4.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 participants. Aggregators must enforce the agreed-upon minimum batch size during the collect protocol, but implementations may 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 minimum batch sizes.¶

7.4.3. VDAFs and compute requirements

The choice of VDAF can impact the computation required for a DAP Task. For instance, the Poplar1 VDAF [VDAF] when configured to compute a set of heavy hitters requires each measurement to be of the same bit-length which all parties need to agree on prior to VDAF execution. The computation required for such tasks can increase superlinearly as multiple rounds of evaluation are needed for each bit of the measurement value.¶

When dealing with variable length measurements (e.g domain names), it is necessary to pad them to convert into fixed-size measurements. When computing the heavy hitters from a batch of such measurements, we can early-abort the Poplar1 execution once we have reached the padding region for a candidate measurement. For smaller length measurements, this significantly reduces the cost of communication between Aggregators and the steps required for the computation. However, malicious Clients can still generate maximum length measurements forcing the system to always operate at worst-case performance.¶

[[TODO: Revisit this paragraph once https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/273 is resolved.]]¶

Therefore, care must be taken that a DAP deployment can comfortably handle computation of measurements for arbitrarily large sizes, otherwise, it may result in a DoS possibility for the entire system.¶

7.8.1. Data types

8.1.1. "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.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.2. "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.4.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.3. "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.6¶

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-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.6¶

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-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.6¶

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-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.6¶

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" 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.6¶

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-collect-req" media type

Type name:

application¶

Subtype name:

dap-collect-req¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

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

Security considerations:

see Section 4.6¶

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" media type

Type name:

application¶

Subtype name:

dap-collection¶

Required parameters:

N/A¶

Optional parameters:

None¶

Encoding considerations:

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

Security considerations:

see Section 4.6¶

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¶