idnits 2.17.00 (12 Aug 2021) /tmp/idnits19330/draft-ietf-ppm-dap-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 6 instances of too long lines in the document, the longest one being 9 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document date (3 May 2022) is 11 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '32' on line 1284 == Outdated reference: draft-irtf-cfrg-hpke has been published as RFC 9180 ** Downref: Normative reference to an Informational draft: draft-irtf-cfrg-hpke (ref. 'I-D.irtf-cfrg-hpke') ** Downref: Normative reference to an Informational RFC: RFC 2818 ** Downref: Normative reference to an Informational RFC: RFC 5861 Summary: 4 errors (**), 0 flaws (~~), 1 warning (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group T. Geoghegan 3 Internet-Draft ISRG 4 Intended status: Standards Track C. Patton 5 Expires: 4 November 2022 Cloudflare 6 E. Rescorla 7 Mozilla 8 C. A. Wood 9 Cloudflare 10 3 May 2022 12 Distributed Aggregation Protocol for Privacy Preserving Measurement 13 draft-ietf-ppm-dap-00 15 Abstract 17 There are many situations in which it is desirable to take 18 measurements of data which people consider sensitive. In these 19 cases, the entity taking the measurement is usually not interested in 20 people's individual responses but rather in aggregated data. 21 Conventional methods require collecting individual responses and then 22 aggregating them, thus representing a threat to user privacy and 23 rendering many such measurements difficult and impractical. This 24 document describes a multi-party distributed aggregation protocol 25 (DAP) for privacy preserving measurement (PPM) which can be used to 26 collect aggregate data without revealing any individual user's data. 28 Discussion Venues 30 This note is to be removed before publishing as an RFC. 32 Discussion of this document takes place on the mailing list (), which 33 is archived at . 35 Source for this draft and an issue tracker can be found at 36 https://github.com/ietf-wg-ppm/ppm-specification. 38 Status of This Memo 40 This Internet-Draft is submitted in full conformance with the 41 provisions of BCP 78 and BCP 79. 43 Internet-Drafts are working documents of the Internet Engineering 44 Task Force (IETF). Note that other groups may also distribute 45 working documents as Internet-Drafts. The list of current Internet- 46 Drafts is at https://datatracker.ietf.org/drafts/current/. 48 Internet-Drafts are draft documents valid for a maximum of six months 49 and may be updated, replaced, or obsoleted by other documents at any 50 time. It is inappropriate to use Internet-Drafts as reference 51 material or to cite them other than as "work in progress." 53 This Internet-Draft will expire on 4 November 2022. 55 Copyright Notice 57 Copyright (c) 2022 IETF Trust and the persons identified as the 58 document authors. All rights reserved. 60 This document is subject to BCP 78 and the IETF Trust's Legal 61 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 62 license-info) in effect on the date of publication of this document. 63 Please review these documents carefully, as they describe your rights 64 and restrictions with respect to this document. Code Components 65 extracted from this document must include Revised BSD License text as 66 described in Section 4.e of the Trust Legal Provisions and are 67 provided without warranty as described in the Revised BSD License. 69 Table of Contents 71 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 72 1.1. DISCLAIMER . . . . . . . . . . . . . . . . . . . . . . . 4 73 1.2. Conventions and Definitions . . . . . . . . . . . . . . . 4 74 2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 5 75 2.1. System Architecture . . . . . . . . . . . . . . . . . . . 6 76 2.2. Validating Inputs . . . . . . . . . . . . . . . . . . . . 9 77 3. Message Transport . . . . . . . . . . . . . . . . . . . . . . 9 78 3.1. Errors . . . . . . . . . . . . . . . . . . . . . . . . . 10 79 4. Protocol Definition . . . . . . . . . . . . . . . . . . . . . 11 80 4.1. Task Configuration . . . . . . . . . . . . . . . . . . . 12 81 4.2. Uploading Reports . . . . . . . . . . . . . . . . . . . . 13 82 4.2.1. Key Configuration Request . . . . . . . . . . . . . . 14 83 4.2.2. Upload Request . . . . . . . . . . . . . . . . . . . 15 84 4.2.3. Upload Extensions . . . . . . . . . . . . . . . . . . 16 85 4.2.4. Leader State . . . . . . . . . . . . . . . . . . . . 17 86 4.3. Verifying and Aggregating Reports . . . . . . . . . . . . 17 87 4.3.1. Aggregate Initialization . . . . . . . . . . . . . . 19 88 4.3.2. Aggregate Continuation . . . . . . . . . . . . . . . 24 89 4.4. Collecting Results . . . . . . . . . . . . . . . . . . . 26 90 4.4.1. Collection Initialization . . . . . . . . . . . . . . 27 91 4.4.2. Collection Aggregation . . . . . . . . . . . . . . . 28 92 4.4.3. Collection Finalization . . . . . . . . . . . . . . . 30 93 4.4.4. Aggregate Share Encryption . . . . . . . . . . . . . 31 94 4.4.5. Validating Batch Parameters . . . . . . . . . . . . . 31 95 4.4.6. Anti-replay . . . . . . . . . . . . . . . . . . . . . 32 97 5. Operational Considerations . . . . . . . . . . . . . . . . . 32 98 5.1. Protocol participant capabilities . . . . . . . . . . . . 33 99 5.1.1. Client capabilities . . . . . . . . . . . . . . . . . 33 100 5.1.2. Aggregator capabilities . . . . . . . . . . . . . . . 33 101 5.1.3. Collector capabilities . . . . . . . . . . . . . . . 34 102 5.2. Data resolution limitations . . . . . . . . . . . . . . . 34 103 5.3. Aggregation utility and soft batch deadlines . . . . . . 35 104 5.4. Protocol-specific optimizations . . . . . . . . . . . . . 35 105 5.4.1. Reducing storage requirements . . . . . . . . . . . . 35 106 6. Security Considerations . . . . . . . . . . . . . . . . . . . 36 107 6.1. Threat model . . . . . . . . . . . . . . . . . . . . . . 36 108 6.1.1. Client/user . . . . . . . . . . . . . . . . . . . . . 37 109 6.1.2. Aggregator . . . . . . . . . . . . . . . . . . . . . 37 110 6.1.3. Leader . . . . . . . . . . . . . . . . . . . . . . . 39 111 6.1.4. Collector . . . . . . . . . . . . . . . . . . . . . . 40 112 6.1.5. Aggregator collusion . . . . . . . . . . . . . . . . 40 113 6.1.6. Attacker on the network . . . . . . . . . . . . . . . 40 114 6.2. Client authentication or attestation . . . . . . . . . . 42 115 6.3. Anonymizing proxies . . . . . . . . . . . . . . . . . . . 42 116 6.4. Batch parameters . . . . . . . . . . . . . . . . . . . . 42 117 6.5. Differential privacy . . . . . . . . . . . . . . . . . . 42 118 6.6. Robustness in the presence of malicious servers . . . . . 43 119 6.7. Infrastructure diversity . . . . . . . . . . . . . . . . 43 120 6.8. System requirements . . . . . . . . . . . . . . . . . . . 43 121 6.8.1. Data types . . . . . . . . . . . . . . . . . . . . . 43 122 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 43 123 7.1. Protocol Message Media Types . . . . . . . . . . . . . . 43 124 7.1.1. "application/ppm-hpke-config" media type . . . . . . 44 125 7.1.2. "message/ppm-report" media type . . . . . . . . . . . 45 126 7.1.3. "message/ppm-aggregate-continue-req" media type . . . 46 127 7.1.4. "message/ppm-aggregate-init-resp" media type . . . . 47 128 7.1.5. "message/ppm-aggregate-continue-req" media type . . . 48 129 7.1.6. "message/ppm-aggregate-continue-resp" media type . . 48 130 7.1.7. "message/ppm-aggregate-share-req" media type . . . . 49 131 7.1.8. "message/ppm-aggregate-share-resp" media type . . . . 50 132 7.1.9. "message/ppm-collect-req" media type . . . . . . . . 51 133 7.1.10. "message/ppm-collect-req" media type . . . . . . . . 52 134 7.2. Upload Extension Registry . . . . . . . . . . . . . . . . 53 135 7.3. URN Sub-namespace for PPM (urn:ietf:params:ppm) . . . . . 53 136 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 53 137 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 53 138 9.1. Normative References . . . . . . . . . . . . . . . . . . 53 139 9.2. Informative References . . . . . . . . . . . . . . . . . 54 140 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 55 142 1. Introduction 144 This document describes a distributed aggregation protocol for 145 privacy preserving measurement. The protocol is executed by a large 146 set of clients and a small set of servers. The servers' goal is to 147 compute some aggregate statistic over the clients' inputs without 148 learning the inputs themselves. This is made possible by 149 distributing the computation among the servers in such a way that, as 150 long as at least one of them executes the protocol honestly, no input 151 is ever seen in the clear by any server. 153 1.1. DISCLAIMER 155 This document is a work in progress. We have not yet settled on the 156 design of the protocol framework or the set of features we intend to 157 support. 159 1.2. Conventions and Definitions 161 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 162 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 163 "OPTIONAL" in this document are to be interpreted as described in 164 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 165 capitals, as shown here. 167 The following terms are used: 169 Aggregation function: The function computed over the users' inputs. 171 Aggregator: An endpoint that runs the input-validation protocol and 172 accumulates input shares. 174 Batch: A set of reports that are aggregated into an output. 176 Batch duration: The time difference between the oldest and newest 177 report in a batch. 179 Batch interval: A parameter of the collect or aggregate-share 180 request that specifies the time range of the reports in the batch. 182 Client: The endpoint from which a user sends data to be aggregated, 183 e.g., a web browser. 185 Collector: The endpoint that receives the output of the aggregation 186 function. 188 Input: The measurement (or measurements) emitted by a client, before 189 any encryption or secret sharing scheme is applied. 191 Input share: An aggregator's share of the output of the VDAF [VDAF] 192 sharding algorithm. This algorithm is run by each client in order 193 to cryptographically protect its measurement. 195 Measurement: A single value (e.g., a count) being reported by a 196 client. Multiple measurements may be grouped into a single 197 protocol input. 199 Minimum batch duration: The minimum batch duration permitted for a 200 PPM task, i.e., the minimum time difference between the oldest and 201 newest report in a batch. 203 Minimum batch size: The minimum number of reports in a batch. 205 Leader: A distinguished aggregator that coordinates input validation 206 and data collection. 208 Aggregate result: The output of the aggregation function over a 209 given set of reports. 211 Aggregate share: A share of the aggregate result emitted by an 212 aggregator. Aggregate shares are reassembled by the collector 213 into the final output. 215 Output share: An aggregator's share of the output of the VDAF [VDAF] 216 preparation step. Many output shares are combined into an 217 aggregate share via the VDAF aggregation algorithm. 219 Proof: A value generated by the client and used by the aggregators 220 to verify the client's input. 222 Report: Uploaded to the leader from the client. A report contains 223 the secret-shared and encrypted input and proof. 225 Server: An aggregator. 227 This document uses the presentation language of [RFC8446] to define 228 messages in the PPM protocol. Encoding and decoding of these 229 messages as byte strings also follows [RFC8446]. 231 2. Overview 233 The protocol is executed by a large set of clients and a small set of 234 servers. We call the servers the _aggregators_. Each client's input 235 to the protocol is a set of measurements (e.g., counts of some user 236 behavior). Given the input set of measurements x_1, ..., x_n held by 237 n users, the goal of a _privacy preserving measurement (PPM) 238 protocol_ is to compute y = F(p, x_1, ..., x_n) for some function F 239 while revealing nothing else about the measurements. 241 This protocol is extensible and allows for the addition of new 242 cryptographic schemes that implement the VDAF interface specified in 243 [VDAF]. Candidates include: 245 * prio3, which allows for aggregate statistics such as sum, mean, 246 histograms, etc. This class of VDAFs is based on Prio [CGB17] and 247 includes improvements described in [BBCGGI19]. 249 * poplar1, which allows for finding the most popular strings among a 250 collection of clients (e.g., the URL of their home page) as well 251 as counting the number of clients that hold a given string. This 252 VDAF is the basis of the Poplar protocol of [BBCGGI21], which is 253 designed to solve the heavy hitters problem in a privacy 254 preserving manner. 256 This protocol is designed to work with schemes that use secret 257 sharing. Rather than send its input in the clear, each client shards 258 its measurements into a sequence of _input shares_ and sends an input 259 share to each of the aggregators. This provides two important 260 properties: 262 * It's impossible to deduce the measurement without knowing _all_ of 263 the shares. 265 * It allows the aggregators to compute the final output by first 266 aggregating up their measurements shares locally, then combining 267 the results to obtain the final output. 269 2.1. System Architecture 271 The overall system architecture is shown in Figure 1. 273 +------------+ 274 | | 275 +--------+ | Helper | 276 | | | | 277 | Client +----+ +-----^------+ 278 | | | | 279 +--------+ | | 280 | | 281 +--------+ | +-----v------+ +-----------+ 282 | | +-----> | | | 283 | Client +----------> Leader <---------> Collector | 284 | | +-----> | | | 285 +--------+ | +-----^------+ +-----------+ 286 | | 287 +--------+ | | 288 | | | | 289 | Client +----+ +-----V------+ 290 | | | | 291 +--------+ | Helper | 292 | | 293 +------------+ 295 Figure 1: System Architecture 297 [[OPEN ISSUE: This shows two helpers, but the document only allows 298 one for now. https://github.com/ietf-wg-ppm/ppm-specification/ 299 issues/117]] 301 The main participants in the protocol are as follows: 303 Collector: The entity which wants to take the measurement and 304 ultimately receives the results. Any given measurement will have 305 a single collector. 307 Client(s): The endpoints which directly take the measurement(s) and 308 report them to the PPM system. In order to provide reasonable 309 levels of privacy, there must be a large number of clients. 311 Aggregator: An endpoint which receives report shares. Each 312 aggregator works with the other aggregators to compute the final 313 aggregate. This protocol defines two types of aggregators: 314 Leaders and Helpers. For each measurement, there is a single 315 leader and helper. 317 Leader: The leader is responsible for coordinating the protocol. It 318 receives the encrypted shares, distributes them to the helpers, 319 and orchestrates the process of computing the final measurement as 320 requested by the collector. 322 Helper: Helpers are responsible for executing the protocol as 323 instructed by the leader. The protocol is designed so that 324 helpers can be relatively lightweight, with most of the state held 325 at the leader. 327 The basic unit of PPM is the "task" which represents a single 328 measurement (though potentially taken over multiple time windows). 329 The definition of a task includes the following parameters: 331 * The type of each measurement. 333 * The aggregation function to compute (e.g., sum, mean, etc.) and an 334 optional aggregation parameter. 336 * The set of aggregators and necessary cryptographic keying material 337 to use. 339 * The VDAF to execute, which to some extent is dictated by the 340 previous choices. 342 * The minimum "batch size" of reports which can be aggregated. 344 * The rate at which measurements can be taken, i.e., the "minimum 345 batch window". 347 These parameters are distributed out of band to the clients and to 348 the aggregators. Each task is identified by a unique 32-byte ID 349 which is used to refer to it in protocol messages. 351 During the duration of the measurement, each client records its own 352 value(s), packages them up into a report, and sends them to the 353 leader. Each share is separately encrypted for each aggregator so 354 that even though they pass through the leader, the leader is unable 355 to see or modify them. Depending on the measurement, the client may 356 only send one report or may send many reports over time. 358 The leader distributes the shares to the helpers and orchestrates the 359 process of verifying them (see Section 2.2) and assembling them into 360 a final measurement for the collector. Depending on the VDAF, it may 361 be possible to incrementally process each report as it comes in, or 362 may be necessary to wait until the entire batch of reports is 363 received. 365 2.2. Validating Inputs 367 An essential task of any data collection pipeline is ensuring that 368 the data being aggregated is "valid". In PPM, input validation is 369 complicated by the fact that none of the entities other than the 370 client ever sees the values for individual clients. 372 In order to address this problem, the aggregators engage in a secure, 373 multi-party computation specified by the chosen VDAF [VDAF] in order 374 to prepare a report for aggregation. At the beginning of this 375 computation, each aggregator is in possession of an input share 376 uploaded by the client. At the end of the computation, each 377 aggregator is in posession of either an "output share" that is ready 378 to be aggregated or an indication that a valid output share could not 379 be computed. 381 To facilitiate this computation, the input shares generated by the 382 client include information used by the aggregators during aggregation 383 in order to validate their corresponding output shares. For example, 384 prio3 includes a distributed zero-knowledge proof of the input's 385 validity [BBCGGI19] which the aggregators can jointly verify and 386 reject the report if it cannot be verified. However, they do not 387 learn anything about the individual report other than that it is 388 valid. 390 The specific properties attested to in the proof vary depending on 391 the measurement being taken. For instance, if we want to measure the 392 time the user took performing a given task the proof might 393 demonstrate that the value reported was within a certain range (e.g., 394 0-60 seconds). By contrast, if we wanted to report which of a set of 395 N options the user select, the report might contain N integers and 396 the proof would demonstrate that N-1 were 0 and the other was 1. 398 It is important to recognize that "validity" is distinct from 399 "correctness". For instance, the user might have spent 30s on a task 400 but the client might report 60s. This is a problem with any 401 measurement system and PPM does not attempt to address it; it merely 402 ensures that the data is within acceptable limits, so the client 403 could not report 10^6s or -20s. 405 3. Message Transport 407 Communications between PPM entities are carried over HTTPS [RFC2818]. 408 HTTPS provides server authentication and confidentiality. In 409 addition, report shares are encrypted directly to the aggregators 410 using HPKE [I-D.irtf-cfrg-hpke]. 412 3.1. Errors 414 Errors can be reported in PPM both at the HTTP layer and within 415 challenge objects as defined in Section 7. PPM servers can return 416 responses with an HTTP error response code (4XX or 5XX). For 417 example, if the client submits a request using a method not allowed 418 in this document, then the server MAY return status code 405 (Method 419 Not Allowed). 421 When the server responds with an error status, it SHOULD provide 422 additional information using a problem document [RFC7807]. To 423 facilitate automatic response to errors, this document defines the 424 following standard tokens for use in the "type" field (within the PPM 425 URN namespace "urn:ietf:params:ppm:error:"): 427 +=====================+=========================================+ 428 | Type | Description | 429 +=====================+=========================================+ 430 | unrecognizedMessage | The message type for a response was | 431 | | incorrect or the payload was malformed. | 432 +---------------------+-----------------------------------------+ 433 | unrecognizedTask | An endpoint received a message with an | 434 | | unknown task ID. | 435 +---------------------+-----------------------------------------+ 436 | outdatedConfig | The message was generated using an | 437 | | outdated configuration. | 438 +---------------------+-----------------------------------------+ 439 | batchInvalid | A collect or aggregate-share request | 440 | | was made with invalid batch parameters. | 441 +---------------------+-----------------------------------------+ 442 | batchMismatch | Aggregators disagree on the report | 443 | | shares that were aggregated in a batch. | 444 +---------------------+-----------------------------------------+ 446 Table 1 448 This list is not exhaustive. The server MAY return errors set to a 449 URI other than those defined above. Servers MUST NOT use the PPM URN 450 namespace for errors not listed in the appropriate IANA registry (see 451 Section 7.3). Clients SHOULD display the "detail" field of all 452 errors. The "instance" value MUST be the endpoint to which the 453 request was targeted. The problem document MUST also include a 454 "taskid" member which contains the associated PPM task ID, encoded 455 with base64 using the standard alphabet [RFC4648] (this value is 456 always known, see Section 4.1). 458 In the remainder of this document, we use the tokens in the table 459 above to refer to error types, rather than the full URNs. For 460 example, an "error of type 'unrecognizedMessage'" refers to an error 461 document with "type" value 462 "urn:ietf:params:ppm:error:unrecognizedMessage". 464 This document uses the verbs "abort" and "alert with [some error 465 message]" to describe how protocol participants react to various 466 error conditions. 468 4. Protocol Definition 470 PPM has three major interactions which need to be defined: 472 * Uploading reports from the client to the aggregators, specified in 473 Section 4.2 475 * Computing the results of a given measurement, specified in 476 Section 4.3 478 * Collecting aggregated results, specified in Section 4.4 480 We start with some basic type definitions used in other messages. 482 /* ASCII encoded URL. e.g., "https://example.com" */ 483 opaque Url<1..2^16-1>; 485 Duration uint64; /* Number of seconds elapsed between two instants */ 487 Time uint64; /* seconds elapsed since start of UNIX epoch */ 489 /* An interval of time of length duration, where start is included and (start + 490 duration) is excluded. */ 491 struct { 492 Time start; 493 Duration duration; 494 } Interval; 496 /* A nonce used to uniquely identify a report in the context of a PPM task. It 497 includes the time at which the report was generated and a random, 64-bit 498 integer. */ 499 struct { 500 Time time; 501 uint64 rand; 502 } Nonce; 504 /* The various roles in the PPM protocol. */ 505 enum { 506 collector(0), 507 client(1), 508 leader(2), 509 helper(3), 510 } Role; 512 /* Identifier for a server's HPKE configuration */ 513 uint8 HpkeConfigId; 515 /* An HPKE ciphertext. */ 516 struct { 517 HpkeConfigId config_id; // config ID 518 opaque enc<1..2^16-1>; // encapsulated HPKE context 519 opaque payload<1..2^16-1>; // ciphertext 520 } HpkeCiphertext; 522 4.1. Task Configuration 524 Prior to the start of execution of the protocol, each participant 525 must agree on the configuration for each task. A task is uniquely 526 identified by its task ID: 528 opaque TaskId[32]; 529 A TaskId is a globally unique sequence of bytes. It is RECOMMENDED 530 that this be set to a random string output by a cryptographically 531 secure pseudorandom number generator. Each task has the following 532 parameters associated with it: 534 * aggregator_endpoints: A list of URLs relative to which an 535 aggregator's API endpoints can be found. Each endpoint's list 536 MUST be in the same order. The leader's endpoint MUST be the 537 first in the list. The order of the encrypted_input_shares in a 538 Report (see Section 4.2) MUST be the same as the order in which 539 aggregators appear in this list. 541 * max_batch_lifetime: The maximum number of times a batch of reports 542 may be used in collect requests. 544 * min_batch_size: The minimum number of reports that appear in a 545 batch. 547 * min_batch_duration: The minimum time difference between the oldest 548 and newest report in a batch. This defines the boundaries with 549 which the batch interval of each collect request must be aligned. 550 (See Section 4.4.5.) 552 * A unique identifier for the VDAF instance used for the task, 553 including the type of measurement associated with the task. 555 In addition, in order to facilitate the aggregation and collect 556 protocols, each of the aggregators is configured with following 557 parameters: 559 * collector_config: The HPKE configuration of the collector 560 (described in Section 4.2.1). 562 * vdaf_verify_param: The aggregator's VDAF verification parameter 563 output by the setup algorithm computed jointly by the aggregators 564 before the start of the PPM protocol [VDAF]). [OPEN ISSUE: This 565 is yet to be specified. See issue#161.] 567 Finally, the collector is configured with the HPKE secret key 568 corresponding to collector_hpke_config. 570 4.2. Uploading Reports 572 Clients periodically upload reports to the leader, which then 573 distributes the individual shares to each helper. 575 4.2.1. Key Configuration Request 577 Before the client can upload its report to the leader, it must know 578 the public key of each of the aggregators. These are retrieved from 579 each aggregator by sending a request to [aggregator]/key_config, 580 where [aggregator] is the aggregator's endpoint URL, obtained from 581 the task parameters. The aggregator responds to well-formed requests 582 with status 200 and an HpkeConfig value: 584 struct { 585 HpkeConfigId id; 586 HpkeKemId kem_id; 587 HpkeKdfId kdf_id; 588 HpkeAeadKdfId aead_id; 589 HpkePublicKey public_key; 590 } HpkeConfig; 592 opaque HpkePublicKey<1..2^16-1>; 593 uint16 HpkeAeadId; // Defined in I-D.irtf-cfrg-hpke 594 uint16 HpkeKemId; // Defined in I-D.irtf-cfrg-hpke 595 uint16 HpkeKdfId; // Defined in I-D.irtf-cfrg-hpke 597 [OPEN ISSUE: Decide whether to expand the width of the id, or support 598 multiple cipher suites (a la OHTTP/ECH).] 600 The client MUST abort if any of the following happen for any 601 key_config request: 603 * the client and aggregator failed to establish a secure, 604 aggregator-authenticated channel; 606 * the GET request failed or didn't return a valid key config; or 608 * the key config specifies a KEM, KDF, or AEAD algorithm the client 609 doesn't recognize. 611 Aggregators SHOULD use HTTP caching to permit client-side caching of 612 this resource [RFC5861]. Aggregators SHOULD favor long cache 613 lifetimes to avoid frequent cache revalidation, e.g., on the order of 614 days. Aggregators can control this cached lifetime with the Cache- 615 Control header, as follows: 617 Cache-Control: max-age=86400 619 Clients SHOULD follow the usual HTTP caching [RFC7234] semantics for 620 key configurations. 622 Note: Long cache lifetimes may result in clients using stale HPKE 623 keys; aggregators SHOULD continue to accept reports with old keys for 624 at least twice the cache lifetime in order to avoid rejecting 625 reports. 627 4.2.2. Upload Request 629 Clients upload reports by using an HTTP POST to [leader]/upload, 630 where [leader] is the first entry in the task's aggregator endpoints. 631 The payload is structured as follows: 633 struct { 634 TaskID task_id; 635 Nonce nonce; 636 Extension extensions<0..2^16-1>; 637 HpkeCiphertext encrypted_input_shares<1..2^16-1>; 638 } Report; 640 This message is called the client's _report_. It contains the 641 following fields: 643 * task_id is the task ID of the task for which the report is 644 intended. 646 * nonce is the report nonce generated by the client. This field is 647 used by the aggregators to ensure the report appears in at most 648 one batch. (See Section 4.4.6.) 650 * extensions is a list of extensions to be included in the Upload 651 flow; see Section 4.2.3. 653 * encrypted_input_shares contains the encrypted input shares of each 654 of the aggregators. The order in which the encrypted input shares 655 appear MUST match the order of the task's aggregator_endpoints 656 (i.e., the first share should be the leader's, the second share 657 should be for the first helper, and so on). 659 To generate the report, the client begins by sharding its measurement 660 into a sequence of input shares as specified by the VDAF in use. To 661 encrypt an input share, the client first generates an HPKE 662 [I-D.irtf-cfrg-hpke] context for the aggregator by running 664 enc, context = SetupBaseS(pk, Report.task_id || "ppm-00 input share" || 665 0x01 || server_role) 667 where pk is the aggregator's public key and server_role is the Role 668 of the intended recipient (0x02 for the leader and 0x03 for the 669 helper). In general, the info string for computing the HPKE context 670 is suffixed by two bytes, the first of which identifies the role of 671 the sender and the second of which identifies the role of the 672 intended recipient. 674 enc is the HPKE encapsulated key and context is the HPKE context used 675 by the client for encryption. The payload is encrypted as 677 payload = context.Seal(nonce || extensions, input_share) 679 where input_share is the aggregator's input share and nonce and 680 extensions are the corresponding fields of Report. Clients MUST NOT 681 use the same enc for multiple reports. 683 The leader responds to well-formed requests to [leader]/upload with 684 status 200 and an empty body. Malformed requests are handled as 685 described in Section 3.1. Clients SHOULD NOT upload the same 686 measurement value in more than one report if the leader responds with 687 status 200 and an empty body. 689 The leader responds to requests whose leader encrypted input share 690 uses an out-of-date HpkeConfig.id value, indicated by 691 HpkeCiphertext.config_id, with status 400 and an error of type 692 'outdatedConfig'. Clients SHOULD invalidate any cached aggregator 693 HpkeConfig and retry with a freshly generated Report. If this 694 retried report does not succeed, clients MUST abort and discontinue 695 retrying. 697 The leader MUST ignore any report whose nonce contains a timestamp 698 that falls in a batch interval for which it has received at least one 699 collect request from the collector. (See Section 4.4.) Otherwise, 700 comparing the aggregate result to the previous aggregate result may 701 result in a privacy violation. (Note that the helpers enforce this 702 as well; see Section 4.4.) In addition, the leader SHOULD abort the 703 upload protocol and alert the client with error "staleReport". 705 4.2.3. Upload Extensions 707 Each Report carries a list of extensions that clients may use to 708 convey additional, authenticated information in the report. [OPEN 709 ISSUE: The extensions aren't authenticated. It's probably a good 710 idea to be a bit more clear about how we envision extensions being 711 used. Right now this includes client attestation for defeating Sybil 712 attacks. See issue#89.] Each extension is a tag-length encoded 713 value of the following form: 715 struct { 716 ExtensionType extension_type; 717 opaque extension_data<0..2^16-1>; 718 } Extension; 720 enum { 721 TBD(0), 722 (65535) 723 } ExtensionType; 725 "extension_type" indicates the type of extension, and 726 "extension_data" contains information specific to the extension. 728 4.2.4. Leader State 730 The leader MUST buffer reports while waiting to aggregate them. The 731 leader SHOULD NOT accept reports whose timestamps are too far in the 732 future. Implementors MAY provide for some small leeway, usually no 733 more than a few minutes, to account for clock skew. 735 4.3. Verifying and Aggregating Reports 737 Once a set of clients have uploaded their reports to the leader, the 738 leader can send them to the helpers to be verified and aggregated. 739 In order to enable the system to handle very large batches of 740 reports, this process can be performed incrementally. To aggregate a 741 set of reports, the leader sends a message to each helper containing 742 those report shares. The helper then processes them (verifying the 743 proofs and incorporating their values into the ongoing aggregate) and 744 replies to the leader. 746 The exact structure of the aggregation flow depends on the VDAF. 747 Specifically: 749 * Some VDAFs (e.g., prio3) allow the leader to start aggregating 750 reports proactively before all the reports in a batch are 751 received. Others (e.g., poplar1) require all the reports to be 752 present and must be initiated by the collector. 754 * Processing the reports -- especially validating them -- may 755 require multiple round trips. 757 Note that it is possible to aggregate reports from one batch while 758 reports from the next batch are coming in. This is because each 759 report is validated independently. 761 This process is illustrated below in Figure 2. In this example, the 762 batch size is 20, but the leader opts to process the reports in sub- 763 batches of 10. Each sub-batch takes two round-trips to process. 765 In order to allow the helpers to retain minimal state, the helper can 766 attach a state parameter to its response, with the leader returning 767 the state value in the next request, thus offloading the state to the 768 leader. This state value MUST be cryptographically protected as 769 described in Section 4.3.1. 771 Leader Helper 773 Aggregate request (Reports 1-10) ------------------------> \ 774 <----------------------------- Aggregate response (State 1) | Reports 775 Aggregate request (continued, State 1) ------------------> | 1-10 776 <----------------------------- Aggregate response (State 1) / 778 Aggregate request (Reports 11-20, State 1) --------------> \ 779 <----------------------------- Aggregate response (State 1) | Reports 780 Aggregate request (continued, State 2) ------------------> | 11-20 781 <----------------------------- Aggregate response (State 2) / 783 Figure 2: Aggregation Flow (batch size=20). Multiple aggregation 784 flows can be executed at the same time. 786 [OPEN ISSUE: Should there be an indication of whether a given 787 aggregate request is a continuation of a previous sub-batch?] 789 The aggregation flow can be thought of as having three phases for 790 transforming each valid input report share into an output share: 792 * Initialization: Begin the aggregation flow by sharing report 793 shares with each helper. Each aggregator, including the leader, 794 initializates the underlying VDAF instance using these report 795 shares and the VDAF configured for the corresponding measurement 796 task. 798 * Continuation: Continue the aggregation flow by exchanging messages 799 produced by the underlying VDAF instance until aggregation 800 completes or an error occurs. These messages do not replay the 801 shares. 803 * Completion: Finish the aggregate flow, yielding an output share 804 corresponding for each input report share in the batch. 806 4.3.1. Aggregate Initialization 808 The leader begins aggregation by choosing a set of candidate reports 809 that pertain to the same PPM task. The leader can run this process 810 for many candidate reports in parallel as needed. After choosing the 811 set of candidates, the leader begins aggregation by splitting each 812 report into "report shares", one for each aggregator. The leader and 813 helpers then run the aggregate initialization flow to accomplish two 814 tasks: 816 1. Recover and determine which input report shares are invalid. 818 2. For each valid report share, initialize the VDAF preparation 819 process. 821 An invalid report share is marked with one of the following errors: 823 enum { 824 batch-collected(0), 825 report-replayed(1), 826 report-dropped(2), 827 hpke-unknown-config-id(3), 828 hpke-decrypt-error(4), 829 vdaf-prep-error(5), 830 } ReportShareError; 832 The leader and helper initialization behavior is detailed below. 834 4.3.1.1. Leader Initialization 836 The leader begins the aggregate initialization phase with the set of 837 candidate report shares as follows: 839 1. Decrypt the input share for each report share as described in 840 Section 4.3.1.3. 842 2. Check that the resulting input share is valid as described in 843 Section 4.3.1.4. 845 3. Initialize VDAF preparation as described in Section 4.3.1.5. 847 If any step yields an invalid report share, the leader removes the 848 report share from the set of candidate reports. Once the leader has 849 initialized this state for all valid candidate report shares, it then 850 creates an AggregateInitReq message for each helper to initialize the 851 preparation of this candidate set. The AggregateInitReq message is 852 structured as follows: 854 struct { 855 Nonce nonce; 856 Extension extensions<0..2^16-1>; 857 HpkeCiphertext encrypted_input_share; 858 } ReportShare; 860 struct { 861 TaskID task_id; 862 opaque agg_param<0..2^16-1>; 863 opaque helper_state<0..2^16>; 864 ReportShare report_shares<1..2^16-1>; 865 } AggregateInitReq; 867 [[OPEN ISSUE: consider sending report shares separately (in parallel) 868 to the aggregate instructions. RIght now, aggregation parameters and 869 the corresponding report shares are sent at the same time, but this 870 may not be strictly necessary. ]] 872 The nonce and extensions fields of each ReportShare match that in the 873 Report uploaded by the client. The encrypted_input_share field is 874 the HpkeCiphertext whose index in Report.encrypted_input_shares is 875 equal to the index of the aggregator in the task's 876 aggregator_endpoints to which the AggregateInitReq is being sent. 877 The agg_param field is an opaque, VDAF-specific aggregation 878 parameter. The helper_state parameter contains the helper's state. 879 This is an optional parameter of an aggregate request that the helper 880 can use to carry state across requests and across aggregate flows. 882 Let [aggregator] denote the helper's API endpoint. The leader sends 883 a POST request to [aggregator]/aggregate with its AggregateInitReq 884 message as the payload. The media type is "message/ppm-aggregate- 885 init-req". 887 4.3.1.2. Helper Initialization 889 Each helper begins their portion of the aggregate initialization 890 phase with the set of candidate report shares obtained in an 891 AggregateInitReq message from the leader. It attempts to recover and 892 validate the corresponding input shares similar to the leader, and 893 eventually returns a response to the leader carrying a VDAF-specific 894 message for each report share. 896 To begin this process, the helper first checks that the nonces in 897 AggregateInitReq.report_shares are all distinct. If two ReportShare 898 values have the same nonce, then the helper MUST abort with error 899 "unrecognizedMessage". If this check succeeds, the helper then 900 attempts to recover each input share in 901 AggregateInitReq.report_shares as follows: 903 1. Decrypt the input share for each report share as described in 904 Section 4.3.1.3. 906 2. Check that the resulting input share is valid as described in 907 Section 4.3.1.4. 909 3. Initialize VDAF preparation and initial outputs as described in 910 Section 4.3.1.5. 912 [[OPEN ISSUE: consider moving the helper nonce check into #input- 913 share-batch-validation]] 915 Once the helper has processed each valid report share in 916 AggregateInitReq.report_shares, the helper then creates an 917 AggregateInitResp message to complete its initialization. This 918 message is structured as follows: 920 enum { 921 continued(0), 922 finished(1) 923 failed(2), 924 } PrepareStepResult; 926 struct { 927 Nonce nonce; 928 PrepareStepResult prepare_step_result; 929 select (PrepareStep.prepare_step_result) { 930 case continued: opaque prep_msg<0..2^16-1>; // VDAF preparation message 931 case finished: Empty; 932 case failed: ReportShareError; 933 } 934 } PrepareStep; 936 struct { 937 opaque helper_state<0..2^16>; 938 PrepareStep prepare_steps<1..2^16-1>; 939 } AggregateInitResp; 941 The helper_state parameter contains the helper's initial state. This 942 is an optional parameter of an aggregate request that the helper can 943 use to carry state across requests. At least part of the state will 944 usually need to be encrypted in order to protect user privacy. 945 However, the details of precisely how the state is encrypted and the 946 information that it carries is up to the helper implementation. 948 [[OPEN ISSUE: we may end up removing helper_state. See #185]] 949 The rest of the message is a sequence of PrepareStep values, the 950 order of which matches that of the ReportShare values in 951 AggregateInitReq.report_shares. Each report that was marked as 952 invalid is assigned the PrepareStepResult failed. Otherwise, the 953 PrepareStep is either marked as continued with the output prep_msg, 954 or is marked as finished if the VDAF preparation process is finished 955 for the report share. 957 The helper's response to the leader is an HTTP 200 OK whose body is 958 the AggregateInitResp and media type is "message/ppm-aggregate-init- 959 resp". 961 Upon receipt of a helper's AggregateInitResp message, the leader 962 checks that the sequence of PrepareStep messages corresponds to the 963 ReportShare sequence of the AggregateInitReq. If any message appears 964 out of order, is missing, has an unrecognized nonce, or if two 965 messages have the same nonce, then the leader MUST abort with error 966 "unrecognizedMessage". 968 [[OPEN ISSUE: the leader behavior here is sort of bizarre -- to whom 969 does it abort?]] 971 4.3.1.3. Input Share Decryption 973 Each report share has a corresponding task ID, nonce, list of 974 extensions, and encrypted input share. Let task_id, nonce, 975 extensions, and encrypted_input_share denote these values, 976 respectively. Given these values, an aggregator decrypts the input 977 share as follows. First, the aggregator looks up the HPKE config and 978 corresponding secret key indicated by 979 encrypted_input_share.config_id. If not found, then it marks the 980 report share as invalid with the error hpke-unknown-config-id. 981 Otherwise, it decrypts the payload with the following procedure: 983 context = SetupBaseR(encrypted_input_share.enc, sk, task_id || 984 "ppm-00 input share" || 0x01 || server_role) 986 input_share = context.Open(nonce || extensions, 987 encrypted_input_share.payload) 989 where sk is the HPKE secret key, task_id is the task ID, nonce and 990 extensions are the nonce and extensions of the report share 991 respectively, and server_role is 0x02 if the aggregator is the leader 992 and 0x03 otherwise. If decryption fails, the aggregator marks the 993 report share as invalid with the error hpke-decrypt-error. 994 Otherwise, it outputs the resulting input_share. 996 4.3.1.4. Input Share Validation 998 Validating an input share will either succeed or fail. In the case 999 of failure, the input share is marked as invalid with a corresponding 1000 ReportShareError error. 1002 The validation checks are as follows. 1004 1. Check if the report has never been aggregated but is contained by 1005 a batch that has been collected. If this check fails, the input 1006 share is marked as invalid with the error batch-collected. This 1007 prevents additional reports from being aggregated after its batch 1008 has already been collected. 1010 2. Check if the report has already been aggregated. If this check 1011 fails, the input share is marked as invalid with the error 1012 report-replayed. This is the case if the report was used in a 1013 previous aggregate request and is therefore a replay. An 1014 aggregator may also choose to mark an input share as invalid with 1015 the error report-dropped under the conditions prescribed in 1016 Section 4.4.6. 1018 If both checks succeed, the input share is not marked as invalid. 1020 4.3.1.5. Input Share Preparation 1022 Input share preparation consists of running the preparation-state 1023 initialization algorithm for the VDAF associated with the task and 1024 computes the first state transition. This produces three possible 1025 values: 1027 1. An error, in which case the input report share is marked as 1028 invalid. 1030 2. An output share, in which case the aggregator stores the output 1031 share for future collection as described in Section 4.4. 1033 3. An initial VDAF state and preparation message, denoted 1034 (prep_state, prep_msg). 1036 Each aggregator runs this procedure for a given input share with 1037 corresponding nonce as follows: 1039 prep_state = VDAF.prep_init(vdaf_verify_param, agg_param, nonce, input_share) 1040 out = VDAF.prep_next(prep_state, None) 1041 vdaf_verify_param is the public VDAF parameter, and agg_param is the 1042 opaque aggregation parameter. If either step fails, the aggregator 1043 marks the report as invalid with error vdaf-prep-error. 1045 Otherwise, the value out is interpreted as follows. If this is the 1046 last round of the VDAF, then out is the aggregator's output share. 1047 Otherwise, out is the pair (prep_state, prep_msg). 1049 4.3.2. Aggregate Continuation 1051 In the continuation phase, the leader drives the VDAF preparation of 1052 each share in the candidate report set until the underlying VDAF 1053 moves into a terminal state, yielding an output share for all 1054 aggregators or an error. This phase may involve multiple rounds of 1055 interaction depending on the underlying VDAF parameters. Each round 1056 trip is initiated by the leader. 1058 4.3.2.1. Leader Continuation 1060 The leader begins each round of continuation for a report share based 1061 on its locally computed prepare message and the previous PrepareStep 1062 from the helper. If PrepareStep is of type "failed", then the leader 1063 marks the report as failed and removes it from the candidate report 1064 set and does not process it further. If the type is "finished", then 1065 the leader aborts with "unrecognizedMessage". [[OPEN ISSUE: This 1066 behavior is not specified.]] If the type is "continued", then the 1067 leader proceeds as follows. 1069 Let leader_outbound denote the leader's prepare message and 1070 helper_outbound denote the helper's. The leader computes the next 1071 state transition as follows: 1073 inbound = VDAF.prep_shares_to_prep(agg_param, [leader_outbound, helper_outbound]) 1074 out = VDAF.prep_next(prep_state, inbound) 1076 where [leader_outbound, helper_outbound] is a vector of two elements. 1077 If either of these operations fails, then the leader marks the report 1078 as invalid. Otherwise it interprets out as follows. If this is the 1079 last round of the VDAF, then out is the aggregator's output share, in 1080 which case the aggregator finishes and stores its output share for 1081 further processing as described in Section 4.4. Otherwise, out is 1082 the pair (new_state, prep_msg), where new_state is its updated state 1083 and prep_msg is its next VDAF message (which will be leader_outbound 1084 in the next round of continuation). For the latter case, the helper 1085 sets prep_state to new_state. 1087 The leader then sends each PrepareStep to the helper in an 1088 AggregateContinueReq message, structured as follows: 1090 struct { 1091 opaque helper_state<0..2^16>; 1092 PrepareStep prepare_shares<1..2^16-1>; 1093 } AggregateContinueReq; 1095 For each aggregator endpoint [aggregator] in 1096 AggregateContinueReq.task_id's parameters except its own, the leader 1097 sends a POST request to [aggregator]/aggregate with 1098 AggregateContinueReq as the payload and the media type set to 1099 "message/ppm-aggregate-continue-req". 1101 4.3.2.2. Helper Continuation 1103 The helper continues with preparation for a report share by combining 1104 the leader's input message in AggregateContinueReq and its current 1105 preparation state (prep_state). This step yields one of three 1106 outputs: 1108 1. An error, in which case the input report share is marked as 1109 invalid. 1111 2. An output share, in which case the helper stores the output share 1112 for future collection as described in Section 4.4. 1114 3. An updated VDAF state and preparation message, denoted 1115 (prep_state, prep_msg). 1117 To carry out this step, for each PrepareStep in 1118 AggregateContinueReq.prepare_shares received from the leader, the 1119 helper performs the following check to determine if the report share 1120 should continue being prepared. 1122 * If failed, then mark the report as failed and reply with a failed 1123 PrepareStep to the leader. 1125 * If finished, then mark the report as finished and reply with a 1126 finished PrepareStep to the leader. The helper then stores the 1127 output share and awaits for collection; see Section 4.4. 1129 Otherwise, preparation continues. In this case, the helper computes 1130 its updated state and output message as follows: 1132 out = VDAF.prep_next(prep_state, inbound) 1134 where inbound is the previous VDAF preapre message sent by the leader 1135 and prep_state is the helper's current preparation state. If this 1136 operation fails, then the helper fails with error vdaf-prep-error. 1137 Otherwise, it interprets out as follows. If this is the last round 1138 of VDAF preparation phase, then out is the helper's output share, in 1139 which case the helper stores the output share for future collection. 1140 Otherwise, the helper interpets out as the tuple (new_state, 1141 prep_msg), where new_state is its updated preparation state and 1142 prep_msg is its next VDAF message. 1144 This output message for each report in 1145 AggregateContinueReq.prepare_shares is then sent to the leader in an 1146 AggregateContinueResp message, structured as follows: 1148 struct { 1149 opaque helper_state<0..2^16>; 1150 PrepareStep prepare_shares<1..2^16-1>; 1151 } AggregateContinueResp; 1153 The order of AggregateContinueResp.prepare_shares MUST match that of 1154 the PrepareStep values in AggregateContinueReq.prepare_shares. The 1155 helper's response to the leader is an HTTP 200 OK whose body is the 1156 AggregateContinueResp and media type is "message/ppm-aggregate- 1157 continue-resp". The helper then awaits the next message from the 1158 leader. 1160 [[OPEN ISSUE: consider relaxing this ordering constraint. See 1161 issue#217.]] 1163 4.4. Collecting Results 1165 In this phase, the collector requests aggregate shares from each 1166 aggregator and then locally combines them to yield a single, 1167 aggregate output. In particular, the collector asks the leader to 1168 collect and return the results for a given PPM task over a given time 1169 period. The aggregate shares are encrypted to the collector so that 1170 it can decrypt and combine them to yield the aggregate output. This 1171 entire process is composed of two interactions: 1173 1. Collect request and response between the collector and leader, 1174 specified in Section 4.4.1 1176 2. Aggregate share request and response between the leader and each 1177 aggregator, specified in Section 4.4.2 1179 Once complete, the collector computes the final aggregate result as 1180 specified in Section 4.4.3. 1182 4.4.1. Collection Initialization 1184 To initiate collection, the collector issues a POST request to 1185 [leader]/collect, where [leader] is the leader's endpoint URL. The 1186 body of the request is structured as follows: 1188 [OPEN ISSUE: Decide if and how the collector's request is 1189 authenticated. If not, then we need to ensure that collect job URIs 1190 are resistant to enumeration attacks.] 1192 struct { 1193 TaskID task_id; 1194 Interval batch_interval; 1195 opaque agg_param<0..2^16-1>; // VDAF aggregation parameter 1196 } CollectReq; 1198 The named parameters are: 1200 * task_id, the PPM task ID. 1202 * batch_interval, the request's batch interval. 1204 * agg_param, an aggregation parameter for the VDAF being executed. 1206 Depending on the VDAF scheme and how the leader is configured, the 1207 leader and helper may already have prepared all the reports falling 1208 within batch_interval and be ready to return the aggregate shares 1209 right away, but this cannot be guaranteed. In fact, for some VDAFs, 1210 it is not be possible to begin preparing inputs until the collector 1211 provides the aggregation parameter in the CollectReq. For these 1212 reasons, collect requests are handled asynchronously. 1214 Upon receipt of a CollectReq, the leader begins by checking that the 1215 request meets the requirements of the batch parameters using the 1216 procedure in Section 4.4.5. If so, it immediately sends the 1217 collector a response with HTTP status 303 See Other and a Location 1218 header containing a URI identifying the collect job that can be 1219 polled by the collector, called the "collect job URI". 1221 The leader then begins working with the helper to prepare the shares 1222 falling into CollectReq.batch_interval (or continues this process, 1223 depending on the VDAF) as described in Section 4.3. 1225 After receiving the response to its CollectReq, the collector makes 1226 an HTTP GET request to the collect job URI to check on the status of 1227 the collect job and eventually obtain the result. If the collect job 1228 is not finished yet, the leader responds with HTTP status 202 1229 Accepted. The response MAY include a Retry-After header field to 1230 suggest a pulling interval to the collector. 1232 If the leader has not yet obtained an aggregator share from each 1233 aggregator, the leader invokes the aggregate share request flow 1234 described in Section 4.4.2. Otherwise, when all aggregator shares 1235 are successfully obtained, the leader responds to subsequent HTTP GET 1236 requests to the collect job's URI with HTTP status 200 OK and a body 1237 consisting of a CollectResp: 1239 struct { 1240 HpkeCiphertext encrypted_agg_shares<1..2^16-1>; 1241 } CollectResp; 1243 The encrypted_agg_shares field is the vector of encrypted aggregate 1244 shares. They MUST appear in the same order as the aggregator 1245 endpoints list of the task parameters. 1247 If obtaining aggregate shares fails, then the leader responds to 1248 subsequent HTTP GET requests to the collect job URI with an HTTP 1249 error status and a problem document as described in Section 3.1. 1251 The leader MUST retain a collect job's results until the collector 1252 sends an HTTP DELETE request to the collect job URI, in which case 1253 the leader responds with HTTP status 204 No Content. 1255 [OPEN ISSUE: Allow the leader to drop aggregate shares after some 1256 reasonable amount of time has passed, but it's not clear how to 1257 specify that. ACME doesn't bother to say anything at all about this 1258 when describing how subscribers should fetch certificates: 1259 https://datatracker.ietf.org/doc/html/rfc8555#section-7.4.2] 1261 [OPEN ISSUE: Describe how intra-protocol errors yield collect errors 1262 (see issue#57). For example, how does a leader respond to a collect 1263 request if the helper drops out?] 1265 4.4.2. Collection Aggregation 1267 The leader obtains each helper's encrypted aggregate share in order 1268 to respond to the collector's collect response. To do this, the 1269 leader first computes a checksum over the set of output shares 1270 included in the batch window identified by the collect request. The 1271 checksum is computed by taking the SHA256 hash of each nonce from the 1272 client reports included in the aggregation, then combining the hash 1273 values with a bitwise-XOR operation. 1275 Then, for each aggregator endpoint [aggregator] in the parameters 1276 associated with CollectReq.task_id (see Section 4.4) except its own, 1277 the leader sends a POST request to [aggregator]/aggregate_share with 1278 the following message: 1280 struct { 1281 TaskID task_id; 1282 Interval batch_interval; 1283 uint64 report_count; 1284 opaque checksum[32]; 1285 opaque helper_state<0..2^16>; 1286 } AggregateShareReq; 1288 * task_id is the task ID associated with the PPM parameters. 1290 * batch_interval is the batch interval of the request. 1292 * report_count is the number of reports included in the aggregation. 1294 * checksum is the checksum computed over the set of client reports. 1296 * helper_state is the helper's state, which is carried across 1297 requests from the leader. 1299 To handle the leader's request, the helper first ensures that the 1300 request meets the requirements for batch parameters following the 1301 procedure in Section 4.4.5. If the batch parameters are invalid, 1302 then it MUST abort with error "batchInvalid". 1304 Next, it computes a checksum based on its view of the output shares 1305 included in the batch window, and checks that the report_count and 1306 checksum included in the request match its computed values. If not, 1307 then it MUST abort with error "batchMismatch". 1309 Next, it computes the aggregate share agg_share corresponding to the 1310 set of output shares, denoted out_shares, for the batch interval, as 1311 follows: 1313 agg_share = VDAF.out_shares_to_agg_share(agg_param, out_shares) 1315 Note that for most VDAFs, it is possible to aggregate output shares 1316 as they arrive rather than wait until the batch is collected. To do 1317 so however, it is necessary to enforce the batch parameters as 1318 described in Section 4.4.5 so that the aggregator knows which 1319 aggregate share to update. 1321 The helper then encrypts agg_share under the collector's HPKE public 1322 key as described in Section 4.4.4, yielding encrypted_agg_share. 1323 Encryption prevents the leader from learning the actual result, as it 1324 only has its own aggregate share and cannot compute the helper's. 1326 The helper responds to the leader with HTTP status 200 OK and a body 1327 consisting of an AggregateShareResp: 1329 struct { 1330 HpkeCiphertext encrypted_aggregate_share; 1331 } AggregateShareResp; 1333 encrypted_aggregate_share.config_id is set to the collector's HPKE 1334 config ID. encrypted_aggregate_share.enc is set to the encapsulated 1335 HPKE context enc computed above and 1336 encrypted_aggregate_share.ciphertext is the ciphertext 1337 encrypted_agg_share computed above. 1339 After receiving the helper's response, the leader uses the 1340 HpkeCiphertext to respond to a collect request (see Section 4.4). 1342 After issuing an aggregate-share request for a given batch interval, 1343 it is an error for the leader to issue any more aggregate or 1344 aggregate-init requests for additional reports in the batch interval. 1345 These reports will be rejected by helpers as described Section 4.3.1. 1347 Before completing the collect request, the leader also computes its 1348 own aggregate share agg_share by aggregating all of the prepared 1349 output shares that fall within the batch interval. Finally, it 1350 encrypts it under the collector's HPKE public key as described in 1351 Section 4.4.4. 1353 4.4.3. Collection Finalization 1355 Once the collector has received a successful collect response from 1356 the leader, it can decrypt the aggregate shares and produce an 1357 aggregate result. The collector decrypts each aggregate share as 1358 described in Section 4.4.4. If the collector successfully decrypts 1359 all aggregate shares, the collector then unshards the aggregate 1360 shares into an aggregate result using the VDAF's agg_shares_to_result 1361 algorithm. In particular, let agg_shares denote the ordered sequence 1362 of aggregator shares, ordered by aggregator index, and let agg_param 1363 be the opaque aggregation parameter. The final aggregate result is 1364 computed as follows: 1366 agg_result = VDAF.agg_shares_to_result(agg_param, agg_shares) 1368 4.4.4. Aggregate Share Encryption 1370 Encrypting an aggregate share agg_share for a given AggregateShareReq 1371 is done as follows: 1373 enc, context = SetupBaseS(pk, AggregateShareReq.task_id || 1374 "ppm-00 aggregate share" || server_role || 0x00) 1376 encrypted_agg_share = context.Seal(AggregateShareReq.batch_interval, 1377 agg_share) 1379 where pk is the HPKE public key encoded by the collector's HPKE key, 1380 and server_role is is 0x02 for the leader and 0x03 for a helper. 1382 The collector decrypts these aggregate shares using the opposite 1383 process. Specifically, given an encrypted input share, denoted 1384 enc_share, for a given batch interval, denoted batch_interval, 1385 decryption works as follows: 1387 context = SetupBaseR(enc_share.enc, sk, 1388 "ppm-00 aggregate share" || 1389 task_id || server_role || 0x00) 1390 agg_share = context.Open(batch_interval, enc_share.payload) 1392 where sk is the HPKE secret key, task_id is the task ID for a given 1393 collect request, and server_role is the role of the server that sent 1394 the aggregate share (0x02 for the leader and 0x03 for the helper). 1396 4.4.5. Validating Batch Parameters 1398 Before an aggregator responds to a collect request or aggregate-share 1399 request, it must first check that the request does not violate the 1400 parameters associated with the PPM task. It does so as described 1401 here. 1403 First the aggregator checks that the request's batch interval 1404 respects the boundaries defined by the PPM task's parameters. 1405 Namely, it checks that both batch_interval.start and 1406 batch_interval.duration are divisible by min_batch_duration and that 1407 batch_interval.duration >= min_batch_duration. Unless both these 1408 conditions are true, it aborts and alerts the peer with "invalid 1409 batch interval". 1411 Next, the aggregator checks that the request respects the generic 1412 privacy parameters of the PPM task. Let X denote the set of reports 1413 for which the aggregator has recovered a valid output share and which 1414 fall in the batch interval of the request. 1416 * If len(X) < min_batch_size, then the aggregator aborts and alerts 1417 the peer with "insufficient batch size". 1419 * The aggregator keeps track of the number of times each report was 1420 added to the batch of an AggregateShareReq. If any report in X 1421 was added to at least max_batch_lifetime previous batches, then 1422 the helper aborts and alerts the peer with "request exceeds the 1423 batch's privacy budget". 1425 4.4.6. Anti-replay 1427 Using a client-provided report multiple times within a single batch, 1428 or using the same report in multiple batches, may allow a server to 1429 learn information about the client's measurement, violating the 1430 privacy goal of PPM. To prevent such replay attacks, this 1431 specification requires the aggregators to detect and filter out 1432 replayed reports. 1434 To detect replay attacks, each aggregator keeps track of the set of 1435 nonces pertaining to reports that were previously aggregated for a 1436 given task. If the leader receives a report from a client whose 1437 nonce is in this set, it simply ignores it. A helper who receives an 1438 encrypted input share whose nonce is in this set replies to the 1439 leader with an error as described in Section 4.4. 1441 [OPEN ISSUE: This has the potential to require aggreagtors to store 1442 nonce sests indefinitely. See issue#180.] 1444 A malicious aggregator may attempt to force a replay by replacing the 1445 nonce generated by the client with a nonce its peer has not yet seen. 1446 To prevent this, clients incorporate the nonce into the AAD for HPKE 1447 encryption, ensuring that the output share is only recovered if the 1448 aggregator is given the correct nonce. (See Section 4.2.2.) 1450 Aggregators prevent the same report from being used in multiple 1451 batches (except as required by the protocol) by only responding to 1452 valid collect requests, as described in Section 4.4.5. 1454 5. Operational Considerations 1456 PPM protocols have inherent constraints derived from the tradeoff 1457 between privacy guarantees and computational complexity. These 1458 tradeoffs influence how applications may choose to utilize services 1459 implementing the specification. 1461 5.1. Protocol participant capabilities 1463 The design in this document has different assumptions and 1464 requirements for different protocol participants, including clients, 1465 aggregators, and collectors. This section describes these 1466 capabilities in more detail. 1468 5.1.1. Client capabilities 1470 Clients have limited capabilities and requirements. Their only 1471 inputs to the protocol are (1) the parameters configured out of band 1472 and (2) a measurement. Clients are not expected to store any state 1473 across any upload flows, nor are they required to implement any sort 1474 of report upload retry mechanism. By design, the protocol in this 1475 document is robust against individual client upload failures since 1476 the protocol output is an aggregate over all inputs. 1478 5.1.2. Aggregator capabilities 1480 Helpers and leaders have different operational requirements. The 1481 design in this document assumes an operationally competent leader, 1482 i.e., one that has no storage or computation limitations or 1483 constraints, but only a modestly provisioned helper, i.e., one that 1484 has computation, bandwidth, and storage constraints. By design, 1485 leaders must be at least as capable as helpers, where helpers are 1486 generally required to: 1488 * Support the collect protocol, which includes validating and 1489 aggregating reports; and 1491 * Publish and manage an HPKE configuration that can be used for the 1492 upload protocol. 1494 In addition, for each PPM task, helpers are required to: 1496 * Implement some form of batch-to-report index, as well as inter- 1497 and intra-batch replay mitigation storage, which includes some way 1498 of tracking batch report size with optional support for state 1499 offloading. Some of this state may be used for replay attack 1500 mitigation. The replay mitigation strategy is described in 1501 Section 4.4.6. 1503 Beyond the minimal capabilities required of helpers, leaders are 1504 generally required to: 1506 * Support the upload protocol and store reports; and 1507 * Track batch report size during each collect flow and request 1508 encrypted output shares from helpers. 1510 In addition, for each PPM task, leaders are required to: 1512 * Implement and store state for the form of inter- and intra-batch 1513 replay mitigation in Section 4.4.6; and 1515 * Store helper state. 1517 5.1.3. Collector capabilities 1519 Collectors statefully interact with aggregators to produce an 1520 aggregate output. Their input to the protocol is the task 1521 parameters, configured out of band, which include the corresponding 1522 batch window and size. For each collect invocation, collectors are 1523 required to keep state from the start of the protocol to the end as 1524 needed to produce the final aggregate output. 1526 Collectors must also maintain state for the lifetime of each task, 1527 which includes key material associated with the HPKE key 1528 configuration. 1530 5.2. Data resolution limitations 1532 Privacy comes at the cost of computational complexity. While affine- 1533 aggregatable encodings (AFEs) can compute many useful statistics, 1534 they require more bandwidth and CPU cycles to account for finite- 1535 field arithmetic during input-validation. The increased work from 1536 verifying inputs decreases the throughput of the system or the inputs 1537 processed per unit time. Throughput is related to the verification 1538 circuit's complexity and the available compute-time to each 1539 aggregator. 1541 Applications that utilize proofs with a large number of 1542 multiplication gates or a high frequency of inputs may need to limit 1543 inputs into the system to meet bandwidth or compute constraints. 1544 Some methods of overcoming these limitations include choosing a 1545 better representation for the data or introducing sampling into the 1546 data collection methodology. 1548 [[TODO: Discuss explicit key performance indicators, here or 1549 elsewhere.]] 1551 5.3. Aggregation utility and soft batch deadlines 1553 A soft real-time system should produce a response within a deadline 1554 to be useful. This constraint may be relevant when the value of an 1555 aggregate decreases over time. A missed deadline can reduce an 1556 aggregate's utility but not necessarily cause failure in the system. 1558 An example of a soft real-time constraint is the expectation that 1559 input data can be verified and aggregated in a period equal to data 1560 collection, given some computational budget. Meeting these deadlines 1561 will require efficient implementations of the input-validation 1562 protocol. Applications might batch requests or utilize more 1563 efficient serialization to improve throughput. 1565 Some applications may be constrained by the time that it takes to 1566 reach a privacy threshold defined by a minimum number of reports. 1567 One possible solution is to increase the reporting period so more 1568 samples can be collected, balanced against the urgency of responding 1569 to a soft deadline. 1571 5.4. Protocol-specific optimizations 1573 Not all PPM tasks have the same operational requirements, so the 1574 protocol is designed to allow implementations to reduce operational 1575 costs in certain cases. 1577 5.4.1. Reducing storage requirements 1579 In general, the aggregators are required to keep state for all valid 1580 reports for as long as collect requests can be made for them. In 1581 particular, the aggregators must store a batch as long as the batch 1582 has not been queried more than max_batch_lifetime times. However, it 1583 is not always necessary to store the reports themselves. For schemes 1584 like Prio in which the input-validation protocol is only run once per 1585 report, each aggregator only needs to store its aggregate share for 1586 each possible batch interval, along with the number of times the 1587 aggregate share was used in a batch. (The helper may store its 1588 aggregate shares in its encrypted state, thereby offloading this 1589 state to the leader.) This is due to the requirement that the batch 1590 interval respect the boundaries defined by the PPM parameters. (See 1591 Section 4.4.5.) 1593 6. Security Considerations 1595 Prio assumes a powerful adversary with the ability to compromise an 1596 unbounded number of clients. In doing so, the adversary can provide 1597 malicious (yet truthful) inputs to the aggregation function. Prio 1598 also assumes that all but one server operates honestly, where a 1599 dishonest server does not execute the protocol faithfully as 1600 specified. The system also assumes that servers communicate over 1601 secure and mutually authenticated channels. In practice, this can be 1602 done by TLS or some other form of application-layer authentication. 1604 In the presence of this adversary, Prio provides two important 1605 properties for computing an aggregation function F: 1607 1. Privacy. The aggregators and collector learn only the output of 1608 F computed over all client inputs, and nothing else. 1610 2. Robustness. As long as the aggregators execute the input- 1611 validation protocol correctly, a malicious client can skew the 1612 output of F only by reporting false (untruthful) input. The 1613 output cannot be influenced in any other way. 1615 There are several additional constraints that a Prio deployment must 1616 satisfy in order to achieve these goals: 1618 1. Minimum batch size. The aggregation batch size has an obvious 1619 impact on privacy. (A batch size of one hides nothing of the 1620 input.) 1622 2. Aggregation function choice. Some aggregation functions leak 1623 slightly more than the function output itself. 1625 [TODO: discuss these in more detail.] 1627 6.1. Threat model 1629 In this section, we enumerate the actors participating in the Prio 1630 system and enumerate their assets (secrets that are either inherently 1631 valuable or which confer some capability that enables further attack 1632 on the system), the capabilities that a malicious or compromised 1633 actor has, and potential mitigations for attacks enabled by those 1634 capabilities. 1636 This model assumes that all participants have previously agreed upon 1637 and exchanged all shared parameters over some unspecified secure 1638 channel. 1640 6.1.1. Client/user 1642 6.1.1.1. Assets 1644 1. Unshared inputs. Clients are the only actor that can ever see 1645 the original inputs. 1647 2. Unencrypted input shares. 1649 6.1.1.2. Capabilities 1651 1. Individual users can reveal their own input and compromise their 1652 own privacy. 1654 2. Clients (that is, software which might be used by many users of 1655 the system) can defeat privacy by leaking input outside of the 1656 Prio system. 1658 3. Clients may affect the quality of aggregations by reporting false 1659 input. 1661 * Prio can only prove that submitted input is valid, not that it 1662 is true. False input can be mitigated orthogonally to the 1663 Prio protocol (e.g., by requiring that aggregations include a 1664 minimum number of contributions) and so these attacks are 1665 considered to be outside of the threat model. 1667 4. Clients can send invalid encodings of input. 1669 6.1.1.3. Mitigations 1671 1. The input validation protocol executed by the aggregators 1672 prevents either individual clients or coalitions of clients from 1673 compromising the robustness property. 1675 2. If aggregator output satisifes differential privacy Section 6.5, 1676 then all records not leaked by malicious clients are still 1677 protected. 1679 6.1.2. Aggregator 1681 6.1.2.1. Assets 1683 1. Unencrypted input shares. 1685 2. Input share decryption keys. 1687 3. Client identifying information. 1689 4. Aggregate shares. 1691 5. Aggregator identity. 1693 6.1.2.2. Capabilities 1695 1. Aggregators may defeat the robustness of the system by emitting 1696 bogus output shares. 1698 2. If clients reveal identifying information to aggregators (such as 1699 a trusted identity during client authentication), aggregators can 1700 learn which clients are contributing input. 1702 1. Aggregators may reveal that a particular client contributed 1703 input. 1705 2. Aggregators may attack robustness by selectively omitting 1706 inputs from certain clients. 1708 * For example, omitting submissions from a particular 1709 geographic region to falsely suggest that a particular 1710 localization is not being used. 1712 3. Individual aggregators may compromise availability of the system 1713 by refusing to emit aggregate shares. 1715 4. Input validity proof forging. Any aggregator can collude with a 1716 malicious client to craft a proof that will fool honest 1717 aggregators into accepting invalid input. 1719 5. Aggregators can count the total number of input shares, which 1720 could compromise user privacy (and differential privacy 1721 Section 6.5) if the presence or absence of a share for a given 1722 user is sensitive. 1724 6.1.2.3. Mitigations 1726 1. The linear secret sharing scheme employed by the client ensures 1727 that privacy is preserved as long as at least one aggregator does 1728 not reveal its input shares. 1730 2. If computed over a sufficient number of reports, aggregate shares 1731 reveal nothing about either the inputs or the participating 1732 clients. 1734 3. Clients can ensure that aggregate counts are non-sensitive by 1735 generating input independently of user behavior. For example, a 1736 client should periodically upload a report even if the event that 1737 the task is tracking has not occurred, so that the absence of 1738 reports cannot be distinguished from their presence. 1740 4. Bogus inputs can be generated that encode "null" shares that do 1741 not affect the aggregate output, but mask the total number of 1742 true inputs. 1744 * Either leaders or clients can generate these inputs to mask 1745 the total number from non-leader aggregators or all the 1746 aggregators, respectively. 1748 * In either case, care must be taken to ensure that bogus inputs 1749 are indistinguishable from true inputs (metadata, etc), 1750 especially when constructing timestamps on reports. 1752 [OPEN ISSUE: Define what "null" shares are. They should be defined 1753 such that inserting null shares into an aggregation is effectively a 1754 no-op. See issue#98.] 1756 6.1.3. Leader 1758 The leader is also an aggregator, and so all the assets, capabilities 1759 and mitigations available to aggregators also apply to the leader. 1761 6.1.3.1. Capabilities 1763 1. Input validity proof verification. The leader can forge proofs 1764 and collude with a malicious client to trick aggregators into 1765 aggregating invalid inputs. 1767 * This capability is no stronger than any aggregator's ability 1768 to forge validity proof in collusion with a malicious client. 1770 2. Relaying messages between aggregators. The leader can compromise 1771 availability by dropping messages. 1773 * This capability is no stronger than any aggregator's ability 1774 to refuse to emit aggregate shares. 1776 3. Shrinking the anonymity set. The leader instructs aggregators to 1777 construct output parts and so could request aggregations over few 1778 inputs. 1780 6.1.3.2. Mitigations 1781 1. Aggregators enforce agreed upon minimum aggregation thresholds to 1782 prevent deanonymizing. 1784 2. If aggregator output satisfies differential privacy Section 6.5, 1785 then genuine records are protected regardless of the size of the 1786 anonymity set. 1788 6.1.4. Collector 1790 6.1.4.1. Capabilities 1792 1. Advertising shared configuration parameters (e.g., minimum 1793 thresholds for aggregations, joint randomness, arithmetic 1794 circuits). 1796 2. Collectors may trivially defeat availability by discarding 1797 aggregate shares submitted by aggregators. 1799 3. Known input injection. Collectors may collude with clients to 1800 send known input to the aggregators, allowing collectors to 1801 shrink the effective anonymity set by subtracting the known 1802 inputs from the final output. Sybil attacks [Dou02] could be 1803 used to amplify this capability. 1805 6.1.4.2. Mitigations 1807 1. Aggregators should refuse shared parameters that are trivially 1808 insecure (i.e., aggregation threshold of 1 contribution). 1810 2. If aggregator output satisfies differential privacy Section 6.5, 1811 then genuine records are protected regardless of the size of the 1812 anonymity set. 1814 6.1.5. Aggregator collusion 1816 If all aggregators collude (e.g. by promiscuously sharing unencrypted 1817 input shares), then none of the properties of the system hold. 1818 Accordingly, such scenarios are outside of the threat model. 1820 6.1.6. Attacker on the network 1822 We assume the existence of attackers on the network links between 1823 participants. 1825 6.1.6.1. Capabilities 1827 1. Observation of network traffic. Attackers may observe messages 1828 exchanged between participants at the IP layer. 1830 1. The time of transmission of input shares by clients could 1831 reveal information about user activity. 1833 * For example, if a user opts into a new feature, and the 1834 client immediately reports this to aggregators, then just 1835 by observing network traffic, the attacker can infer what 1836 the user did. 1838 2. Observation of message size could allow the attacker to learn 1839 how much input is being submitted by a client. 1841 * For example, if the attacker observes an encrypted message 1842 of some size, they can infer the size of the plaintext, 1843 plus or minus the cipher block size. From this they may 1844 be able to infer which aggregations the user has opted 1845 into or out of. 1847 2. Tampering with network traffic. Attackers may drop messages or 1848 inject new messages into communications between participants. 1850 6.1.6.2. Mitigations 1852 1. All messages exchanged between participants in the system should 1853 be encrypted. 1855 2. All messages exchanged between aggregators, the collector and the 1856 leader should be mutually authenticated so that network attackers 1857 cannot impersonate participants. 1859 3. Clients should be required to submit inputs at regular intervals 1860 so that the timing of individual messages does not reveal 1861 anything. 1863 4. Clients should submit dummy inputs even for aggregations the user 1864 has not opted into. 1866 [[OPEN ISSUE: The threat model for Prio --- as it's described in the 1867 original paper and [BBCGGI19] --- considers *either* a malicious 1868 client (attacking soundness) *or* a malicious subset of aggregators 1869 (attacking privacy). In particular, soundness isn't guaranteed if 1870 any one of the aggregators is malicious; in theory it may be possible 1871 for a malicious client and aggregator to collude and break soundness. 1872 Is this a contingency we need to address? There are techniques in 1873 [BBCGGI19] that account for this; we need to figure out if they're 1874 practical.]] 1876 6.2. Client authentication or attestation 1878 [TODO: Solve issue#89] 1880 6.3. Anonymizing proxies 1882 Client reports can contain auxiliary information such as source IP, 1883 HTTP user agent or in deployments which use it, client authentication 1884 information, which could be used by aggregators to identify 1885 participating clients or permit some attacks on robustness. This 1886 auxiliary information could be removed by having clients submit 1887 reports to an anonymizing proxy server which would then use Oblivous 1888 HTTP [I-D.thomson-http-oblivious] to forward inputs to the PPM 1889 leader, without requiring any server participating in PPM to be aware 1890 of whatever client authentication or attestation scheme is in use. 1892 6.4. Batch parameters 1894 An important parameter of a PPM deployment is the minimum batch size. 1895 If an aggregation includes too few inputs, then the outputs can 1896 reveal information about individual participants. Aggregators use 1897 the batch size field of the shared task parameters to enforce minimum 1898 batch size during the collect protocol, but server implementations 1899 may also opt out of participating in a PPM task if the minimum batch 1900 size is too small. This document does not specify how to choose 1901 minimum batch sizes. 1903 The PPM parameters also specify the maximum number of times a report 1904 can be used. Some protocols, such as Poplar [BBCGGI21], require 1905 reports to be used in multiple batches spanning multiple collect 1906 requests. 1908 6.5. Differential privacy 1910 Optionally, PPM deployments can choose to ensure their output F 1911 achieves differential privacy [Vad16]. A simple approach would 1912 require the aggregators to add two-sided noise (e.g. sampled from a 1913 two-sided geometric distribution) to outputs. Since each aggregator 1914 is adding noise independently, privacy can be guaranteed even if all 1915 but one of the aggregators is malicious. Differential privacy is a 1916 strong privacy definition, and protects users in extreme 1917 circumstances: Even if an adversary has prior knowledge of every 1918 input in a batch except for one, that one record is still formally 1919 protected. 1921 [OPEN ISSUE: While parameters configuring the differential privacy 1922 noise (like specific distributions / variance) can be agreed upon out 1923 of band by the aggregators and collector, there may be benefits to 1924 adding explicit protocol support by encoding them into task 1925 parameters.] 1927 6.6. Robustness in the presence of malicious servers 1929 Most PPM protocols, including Prio and Poplar, are robust against 1930 malicious clients, but are not robust against malicious servers. Any 1931 aggregator can simply emit bogus aggregate shares and undetectably 1932 spoil aggregates. If enough aggregators were available, this could 1933 be mitigated by running the protocol multiple times with distinct 1934 subsets of aggregators chosen so that no aggregator appears in all 1935 subsets and checking all the outputs against each other. If all the 1936 protocol runs do not agree, then participants know that at least one 1937 aggregator is defective, and it may be possible to identify the 1938 defector (i.e., if a majority of runs agree, and a single aggregator 1939 appears in every run that disagrees). See #22 (https://github.com/ 1940 ietf-wg-ppm/ppm-specification/issues/22) for discussion. 1942 6.7. Infrastructure diversity 1944 Prio deployments should ensure that aggregators do not have common 1945 dependencies that would enable a single vendor to reassemble inputs. 1946 For example, if all participating aggregators stored unencrypted 1947 input shares on the same cloud object storage service, then that 1948 cloud vendor would be able to reassemble all the input shares and 1949 defeat privacy. 1951 6.8. System requirements 1953 6.8.1. Data types 1955 7. IANA Considerations 1957 7.1. Protocol Message Media Types 1959 This specification defines the following protocol messages, along 1960 with their corresponding media types types: 1962 * HpkeConfig Section 4.1: "application/ppm-hpke-config" 1964 * Report Section 4.2.2: "message/ppm-report" 1966 * AggregateInitReq Section 4.4: "message/ppm-aggregate-init-req" 1968 * AggregateInitResp Section 4.4: "message/ppm-aggregate-init-resp" 1969 * AggregateContinueReq Section 4.4: "message/ppm-aggregate-continue- 1970 req" 1972 * AggregateContinueResp Section 4.4: "message/ppm-aggregate- 1973 continue-resp" 1975 * AggregateShareReq Section 4.4: "message/ppm-aggregate-share-req" 1977 * AggregateShareResp Section 4.4: "message/ppm-aggregate-share-resp" 1979 * CollectReq Section 4.4: "message/ppm-collect-req" 1981 * CollectResp Section 4.4: "message/ppm-collect-resp" 1983 The definition for each media type is in the following subsections. 1985 Protocol message format evolution is supported through the definition 1986 of new formats that are identified by new media types. 1988 IANA [shall update / has updated] the "Media Types" registry at 1989 https://www.iana.org/assignments/media-types with the registration 1990 information in this section for all media types listed above. 1992 [OPEN ISSUE: Solicit review of these allocations from domain 1993 experts.] 1995 7.1.1. "application/ppm-hpke-config" media type 1997 Type name: application 1999 Subtype name: ppm-hpke-config 2001 Required parameters: N/A 2003 Optional parameters: None 2005 Encoding considerations: only "8bit" or "binary" is permitted 2007 Security considerations: see Section 4.1 2009 Interoperability considerations: N/A 2011 Published specification: this specification 2013 Applications that use this media type: N/A 2015 Fragment identifier considerations: N/A 2016 Additional information: Magic number(s): N/A 2018 Deprecated alias names for this type: N/A 2020 File extension(s): N/A 2022 Macintosh file type code(s): N/A 2024 Person and email address to contact for further information: see Aut 2025 hors' Addresses section 2027 Intended usage: COMMON 2029 Restrictions on usage: N/A 2031 Author: see Authors' Addresses section 2033 Change controller: IESG 2035 7.1.2. "message/ppm-report" media type 2037 Type name: message 2039 Subtype name: ppm-report 2041 Required parameters: N/A 2043 Optional parameters: None 2045 Encoding considerations: only "8bit" or "binary" is permitted 2047 Security considerations: see Section 4.2.2 2049 Interoperability considerations: N/A 2051 Published specification: this specification 2053 Applications that use this media type: N/A 2055 Fragment identifier considerations: N/A 2057 Additional information: Magic number(s): N/A 2059 Deprecated alias names for this type: N/A 2061 File extension(s): N/A 2063 Macintosh file type code(s): N/A 2065 Person and email address to contact for further information: see Aut 2066 hors' Addresses section 2068 Intended usage: COMMON 2070 Restrictions on usage: N/A 2072 Author: see Authors' Addresses section 2074 Change controller: IESG 2076 7.1.3. "message/ppm-aggregate-continue-req" media type 2078 Type name: message 2080 Subtype name: ppm-aggregate-init-req 2082 Required parameters: N/A 2084 Optional parameters: None 2086 Encoding considerations: only "8bit" or "binary" is permitted 2088 Security considerations: see Section 4.4 2090 Interoperability considerations: N/A 2092 Published specification: this specification 2094 Applications that use this media type: N/A 2096 Fragment identifier considerations: N/A 2098 Additional information: Magic number(s): N/A 2100 Deprecated alias names for this type: N/A 2102 File extension(s): N/A 2104 Macintosh file type code(s): N/A 2106 Person and email address to contact for further information: see Aut 2107 hors' Addresses section 2109 Intended usage: COMMON 2111 Restrictions on usage: N/A 2112 Author: see Authors' Addresses section 2114 Change controller: IESG 2116 7.1.4. "message/ppm-aggregate-init-resp" media type 2118 Type name: message 2120 Subtype name: ppm-aggregate-init-resp 2122 Required parameters: N/A 2124 Optional parameters: None 2126 Encoding considerations: only "8bit" or "binary" is permitted 2128 Security considerations: see Section 4.4 2130 Interoperability considerations: N/A 2132 Published specification: this specification 2134 Applications that use this media type: N/A 2136 Fragment identifier considerations: N/A 2138 Additional information: Magic number(s): N/A 2140 Deprecated alias names for this type: N/A 2142 File extension(s): N/A 2144 Macintosh file type code(s): N/A 2146 Person and email address to contact for further information: see Aut 2147 hors' Addresses section 2149 Intended usage: COMMON 2151 Restrictions on usage: N/A 2153 Author: see Authors' Addresses section 2155 Change controller: IESG 2157 7.1.5. "message/ppm-aggregate-continue-req" media type 2159 Type name: message 2161 Subtype name: ppm-aggregate-continue-req 2163 Required parameters: N/A 2165 Optional parameters: None 2167 Encoding considerations: only "8bit" or "binary" is permitted 2169 Security considerations: see Section 4.4 2171 Interoperability considerations: N/A 2173 Published specification: this specification 2175 Applications that use this media type: N/A 2177 Fragment identifier considerations: N/A 2179 Additional information: Magic number(s): N/A 2181 Deprecated alias names for this type: N/A 2183 File extension(s): N/A 2185 Macintosh file type code(s): N/A 2187 Person and email address to contact for further information: see Aut 2188 hors' Addresses section 2190 Intended usage: COMMON 2192 Restrictions on usage: N/A 2194 Author: see Authors' Addresses section 2196 Change controller: IESG 2198 7.1.6. "message/ppm-aggregate-continue-resp" media type 2200 Type name: init 2202 Subtype name: ppm-aggregate-continue-resp 2204 Required parameters: N/A 2205 Optional parameters: None 2207 Encoding considerations: only "8bit" or "binary" is permitted 2209 Security considerations: see Section 4.4 2211 Interoperability considerations: N/A 2213 Published specification: this specification 2215 Applications that use this media type: N/A 2217 Fragment identifier considerations: N/A 2219 Additional information: Magic number(s): N/A 2221 Deprecated alias names for this type: N/A 2223 File extension(s): N/A 2225 Macintosh file type code(s): N/A 2227 Person and email address to contact for further information: see Aut 2228 hors' Addresses section 2230 Intended usage: COMMON 2232 Restrictions on usage: N/A 2234 Author: see Authors' Addresses section 2236 Change controller: IESG 2238 7.1.7. "message/ppm-aggregate-share-req" media type 2240 Type name: message 2242 Subtype name: ppm-aggregate-share-req 2244 Required parameters: N/A 2246 Optional parameters: None 2248 Encoding considerations: only "8bit" or "binary" is permitted 2250 Security considerations: see Section 4.4 2252 Interoperability considerations: N/A 2253 Published specification: this specification 2255 Applications that use this media type: N/A 2257 Fragment identifier considerations: N/A 2259 Additional information: Magic number(s): N/A 2261 Deprecated alias names for this type: N/A 2263 File extension(s): N/A 2265 Macintosh file type code(s): N/A 2267 Person and email address to contact for further information: see Aut 2268 hors' Addresses section 2270 Intended usage: COMMON 2272 Restrictions on usage: N/A 2274 Author: see Authors' Addresses section 2276 Change controller: IESG 2278 7.1.8. "message/ppm-aggregate-share-resp" media type 2280 Type name: message 2282 Subtype name: ppm-aggregate-share-resp 2284 Required parameters: N/A 2286 Optional parameters: None 2288 Encoding considerations: only "8bit" or "binary" is permitted 2290 Security considerations: see Section 4.4 2292 Interoperability considerations: N/A 2294 Published specification: this specification 2296 Applications that use this media type: N/A 2298 Fragment identifier considerations: N/A 2300 Additional information: Magic number(s): N/A 2301 Deprecated alias names for this type: N/A 2303 File extension(s): N/A 2305 Macintosh file type code(s): N/A 2307 Person and email address to contact for further information: see Aut 2308 hors' Addresses section 2310 Intended usage: COMMON 2312 Restrictions on usage: N/A 2314 Author: see Authors' Addresses section 2316 Change controller: IESG 2318 7.1.9. "message/ppm-collect-req" media type 2320 Type name: message 2322 Subtype name: ppm-collect-req 2324 Required parameters: N/A 2326 Optional parameters: None 2328 Encoding considerations: only "8bit" or "binary" is permitted 2330 Security considerations: see Section 4.4 2332 Interoperability considerations: N/A 2334 Published specification: this specification 2336 Applications that use this media type: N/A 2338 Fragment identifier considerations: N/A 2340 Additional information: Magic number(s): N/A 2342 Deprecated alias names for this type: N/A 2344 File extension(s): N/A 2346 Macintosh file type code(s): N/A 2348 Person and email address to contact for further information: see Aut 2349 hors' Addresses section 2351 Intended usage: COMMON 2353 Restrictions on usage: N/A 2355 Author: see Authors' Addresses section 2357 Change controller: IESG 2359 7.1.10. "message/ppm-collect-req" media type 2361 Type name: message 2363 Subtype name: ppm-collect-req 2365 Required parameters: N/A 2367 Optional parameters: None 2369 Encoding considerations: only "8bit" or "binary" is permitted 2371 Security considerations: see Section 4.4 2373 Interoperability considerations: N/A 2375 Published specification: this specification 2377 Applications that use this media type: N/A 2379 Fragment identifier considerations: N/A 2381 Additional information: Magic number(s): N/A 2383 Deprecated alias names for this type: N/A 2385 File extension(s): N/A 2387 Macintosh file type code(s): N/A 2389 Person and email address to contact for further information: see Aut 2390 hors' Addresses section 2392 Intended usage: COMMON 2394 Restrictions on usage: N/A 2396 Author: see Authors' Addresses section 2397 Change controller: IESG 2399 7.2. Upload Extension Registry 2401 This document requests creation of a new registry for extensions to 2402 the Upload protocol. This registry should contain the following 2403 columns: 2405 [TODO: define how we want to structure this registry when the time 2406 comes] 2408 7.3. URN Sub-namespace for PPM (urn:ietf:params:ppm) 2410 The following value [will be/has been] registered in the "IETF URN 2411 Sub-namespace for Registered Protocol Parameter Identifiers" 2412 registry, following the template in [RFC3553]: 2414 Registry name: ppm 2416 Specification: [[THIS DOCUMENT]] 2418 Repository: http://www.iana.org/assignments/ppm 2420 Index value: No transformation needed. 2422 Initial contents: The types and descriptions in the table in 2423 Section 3.1 above, with the Reference field set to point to this 2424 specification. 2426 8. Acknowledgements 2428 The text in Section 3 is based extensively on [RFC8555] 2430 9. References 2432 9.1. Normative References 2434 [I-D.irtf-cfrg-hpke] 2435 Barnes, R. L., Bhargavan, K., Lipp, B., and C. A. Wood, 2436 "Hybrid Public Key Encryption", Work in Progress, 2437 Internet-Draft, draft-irtf-cfrg-hpke-12, 2 September 2021, 2438 . 2441 [I-D.thomson-http-oblivious] 2442 Thomson, M. and C. A. Wood, "Oblivious HTTP", Work in 2443 Progress, Internet-Draft, draft-thomson-http-oblivious-02, 2444 24 August 2021, . 2447 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2448 Requirement Levels", BCP 14, RFC 2119, 2449 DOI 10.17487/RFC2119, March 1997, 2450 . 2452 [RFC2818] Rescorla, E., "HTTP Over TLS", RFC 2818, 2453 DOI 10.17487/RFC2818, May 2000, 2454 . 2456 [RFC3553] Mealling, M., Masinter, L., Hardie, T., and G. Klyne, "An 2457 IETF URN Sub-namespace for Registered Protocol 2458 Parameters", BCP 73, RFC 3553, DOI 10.17487/RFC3553, June 2459 2003, . 2461 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data 2462 Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, 2463 . 2465 [RFC5861] Nottingham, M., "HTTP Cache-Control Extensions for Stale 2466 Content", RFC 5861, DOI 10.17487/RFC5861, May 2010, 2467 . 2469 [RFC7234] Fielding, R., Ed., Nottingham, M., Ed., and J. Reschke, 2470 Ed., "Hypertext Transfer Protocol (HTTP/1.1): Caching", 2471 RFC 7234, DOI 10.17487/RFC7234, June 2014, 2472 . 2474 [RFC7807] Nottingham, M. and E. Wilde, "Problem Details for HTTP 2475 APIs", RFC 7807, DOI 10.17487/RFC7807, March 2016, 2476 . 2478 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2479 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2480 May 2017, . 2482 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 2483 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 2484 . 2486 9.2. Informative References 2488 [BBCGGI19] Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., and 2489 Y. Ishai, "Zero-Knowledge Proofs on Secret-Shared Data via 2490 Fully Linear PCPs", 5 January 2021, 2491 . 2493 [BBCGGI21] Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., and 2494 Y. Ishai, "Lightweight Techniques for Private Heavy 2495 Hitters", 5 January 2021, 2496 . 2498 [CGB17] Corrigan-Gibbs, H. and D. Boneh, "Prio: Private, Robust, 2499 and Scalable Computation of Aggregate Statistics", 14 2500 March 2017, . 2502 [Dou02] Douceur, J., "The Sybil Attack", 10 October 2022, 2503 . 2506 [RFC8555] Barnes, R., Hoffman-Andrews, J., McCarney, D., and J. 2507 Kasten, "Automatic Certificate Management Environment 2508 (ACME)", RFC 8555, DOI 10.17487/RFC8555, March 2019, 2509 . 2511 [Vad16] Vadhan, S., "The Complexity of Differential Privacy", 9 2512 August 2016, 2513 . 2516 [VDAF] Barnes, R. L., Patton, C., and P. Schoppmann, "Verifiable 2517 Distributed Aggregation Functions", Work in Progress, 2518 Internet-Draft, draft-irtf-cfrg-vdaf-00, 27 April 2022, 2519 . 2522 Authors' Addresses 2524 Tim Geoghegan 2525 ISRG 2526 Email: timgeog+ietf@gmail.com 2528 Christopher Patton 2529 Cloudflare 2530 Email: chrispatton+ietf@gmail.com 2532 Eric Rescorla 2533 Mozilla 2534 Email: ekr@rtfm.com 2536 Christopher A. Wood 2537 Cloudflare 2538 Email: caw@heapingbits.net