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 batch 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 MUST select a batch that has not yet been associated with a collection job.¶

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

If the configuration does not include max_batch_size, then the Aggregators can output any batch size that is larger than or equal to min_batch_size. This is useful for applications that are not concerned with sample size, i.e., the privacy guarantee is not affected by the sampling rate of the population, therefore a larger than expected batch size does not weaken the designed privacy guarantee.¶

Implementation note: The goal for the Aggregators is to aggregate the same number of reports in each batch. The target batch size is deployment-specific, and may be equal to or greater than the minimum batch size. Deciding how soon batches should be output is also deployment-specific. Exactly sizing batches may be challenging for Leader deployments in which multiple, independent nodes running the aggregate interaction (see Section 4.5) need to be coordinated. The difference between the minimum batch size and maximum batch size is in part intended to allow room for error, and allow a range of target batch sizes.¶

4.1.3. Batch Size Considerations

If each batch will be collected only once (i.e. when using Prio3), then batch sizes MAY be equal to min_batch_size without issue. In the case of fixed size queries, max_batch_size MAY be equal to min_batch_size. Any target batch size between min_batch_size and max_batch_size may be chosen.¶

If each batch may be collected more than once (i.e. when using Poplar1), then batches SHOULD be larger than min_batch_size, to allow for the possibility that some reports may be accepted with the first aggregation parameter, but be rejected with a subsequent aggregation parameter. Once a batch has been collected for the first time, subsequent collections of the same batch must process the same set of reports, and collections can only succeed if the number of successfully aggregated reports is at least min_batch_size (see Section 4.6.5.1 and Section 4.6.5.2). Thus, if enough reports are rejected such that fewer than min_batch_size output shares are available for aggregation, then collection of that batch may not proceed. (Note that this is not an issue for the first collection of a batch, since more reports could be combined with the uncollected reports in a subsequent collection attempt.)¶

The target batch size may be chosen on a deployment-specific basis, based on the expected rate of invalid reports and Sybil attack defenses (Section 7.1). When using fixed size queries, max_batch_size SHOULD be unset or greater than or equal to the target batch size, and the Leader SHOULD construct batches of the target batch size. When using time interval queries, the Collector SHOULD adaptively choose batch intervals based on the report upload rate so that they exceed min_batch_size by enough to allow for subsequent rejections of reports.¶

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 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.4.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 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). 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(
    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 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.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-10 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. 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 interaction. 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-10 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 GET 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. 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 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 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.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.aggregate(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 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.6.4. Aggregate Share Encryption

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

enc, payload = SealBase(pk, "dap-10 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-10 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 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 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 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 interaction, 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.5.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.5.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 the collection protocol, 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.4) parameters in use, if any.¶

If batches will be collected more than once, it is possible that some invalid reports could be accepted and successfully aggregated into the first collection, but be rejected with a subsequent aggregation parameter. This could reduce the number of successfully aggregated reports below the minimum batch size, and make the batch uncollectable with that aggregation parameter, as described in Section 4.1.3. This constitutes an efficient denial of service vector for a Sybil attacker. In deployments that will collect batches more than once, the actual batch sizes, as determined by the Leader or Collector (depending on query type) SHOULD be greater than the minimum batch size to allow for later rejection of some number of invalid reports.¶

7.5.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.4) without knowing the minimum batch size that is enforced by the Aggregators during collection (Section 4.6).¶

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.2 and any additional parameters implied by upload extensions Section 4.4.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. "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¶

8.2.1. Query Types Registry

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

[TODO: define how we want to structure this registry when the time comes]¶

8.2.2. Upload Extension Registry

This document requests creation of a new registry for extensions to the Upload protocol. This registry should contain the following columns:¶

[TODO: define how we want to structure this registry when the time comes]¶

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.5.1.2, with this document as the reference.¶