Subject: Re: [Ppm] Revisit the operational requirements for the Helper?

From: Christopher Patton <[email-masked]>
Date: Mon, 3 Jan 2022 09:14:36 -0800

Happy new year friends! The PR with the suggested change to anti-replay is
up to date and ready for another round of review:
https://github.com/abetterinternet/ppm-specification/pull/169

It would be great if, by the end of the week, we can get a sense of whether
folks support (some version of) this change or not

Cheers,
Chris P.

On Thu, Dec 2, 2021 at 4:04 PM Christopher Patton <[email-masked]>
wrote:

> Hi everyone,
>
> I've begun an implementation of the PPM spec with `prio3` [1]. One of the
> design goals of the sepc was to make it as easy as possible for a Helper to
> participate in the protocol, even at the expense of higher resource
> requirements for the Leader. Based on my experience so far, I think we may
> have over-indexed on this goal a bit. I propose that we revisit this and
> consider balancing the work between the Aggregators more evenly. While at
> it, we may be able to resolve [2].
>
> The spec requires that reports be processed in strictly ascending order,
> where the order is defined in [3]. The ordering is based on a timestamp and
> random number generated by the client and included in the report. I'll
> refer to thus (time, rand) pair as the nonce. Ordering reports based on the
> nonce allows the Helper to prevent replay attacks* without needing to store
> the nonces. In fact, the only long-term storage it needs for anti-replay is
> the most recently processed nonce. The downside is that the Leader has to
> sort reports as they arrive, which makes horizontally scaling the Leader
> more challenging.
>
> A simpler alternative that we had discussed previously is just having each
> of the Aggregators remember the nonces of the reports they have processed.
> This removes the Leader's coordination problem, at the cost of additional
> storage requirements. In fact, both Aggregators need to store the set of
> processed nonces for the duration of a task. This cost can be mitigated by
> refusing to process reports that arrive, say, a day or two late. (Of
> course, this would need to be a parameter that the Aggregators agree on in
> advance.)
>
> Let's call these schemes option #1 and option #2 respectively. Previously
> I was in favor of option #1, but after getting my hands a little dirty and
> conferring with some of my colleagues, I've come to the conclusion that the
> costs of #1 outweigh the costs of #2. I'm curious if others have thought
> about this and whether they are strongly in favor of either option.
>
> Now, if we take option #2, we might also consider revisiting the question
> raised in [2]. The spec currently requires the Clients to upload their
> encrypted input shares to the Leader, who then piggy-backs the Helper's
> input shares on its aggregate requests. Egress fees from cloud providers is
> typically higher than ingress, which makes the status quo more expensive to
> deploy than if the Clients uploaded their encrypted input shares directly
> to each Aggregator.
>
> What might an alternative look like? The client would generate a nonce as
> usual and upload the nonce and an encrypted input share to each of the
> Aggregators. The aggregation flow would largely be the same: The Leader
> sends an Aggregate Request to the Helper, which contains the nonce of the
> report it wants to aggregate as usual. The difference now is that the
> Helper may not have yet received the report before the Leader's request. In
> this case the Leader would just try again later.
>
> Another advantage of this alternative is that it prevents a fairly weak
> Sybil attack, whereby the Leader makes up `n-1` bogus reports that are
> processed into the batch.**
>
>
> Thanks for your consideration,
> Chris P.
>
>
> * Anti-replay is required to prevent privacy violations. See [3].
> ** The Leader can still mount a slightly stronger attack: Just upload the
> `n-1` encrypted input shares to the Helper, impersonating the Clients.
> Though this can be mitigated slightly by rate-limiting requests from the
> Leader's IP address.
>
> [1]
> https://datatracker.ietf.org/doc/html/draft-patton-cfrg-vdaf-00#section-6
> [2] https://github.com/abetterinternet/ppm-specification/issues/130
> [3]
> https://datatracker.ietf.org/doc/html/draft-gpew-priv-ppm#section-4.4.2
>
>

---

From: Christopher Patton <[email-masked]>
Date: Tue, 18 Jan 2022 13:52:33 -0800

Hi all, at the end of last week we merged the PR:
https://github.com/abetterinternet/ppm-specification/pull/169
An issue that we left open is how to prevent aggregators from having to
store nonce sets indefinitely. That issue is tracked here:
https://github.com/abetterinternet/ppm-specification/issues/180

Thanks to all who chime in on this.

Best,
Chris P.

On Mon, Jan 3, 2022 at 9:14 AM Christopher Patton <[email-masked]>
wrote:

> It would be great if, by the end of the week, we can get a sense of
> whether folks support (some version of) this change or not
>
> Cheers,
> Chris P.
>
>> A simpler alternative that we had discussed previously is just having
>> each of the Aggregators remember the nonces of the reports they have
>> processed. This removes the Leader's coordination problem, at the cost of
>> additional storage requirements. In fact, both Aggregators need to store
>> the set of processed nonces for the duration of a task. This cost can be
>> mitigated by refusing to process reports that arrive, say, a day or two
>> late. (Of course, this would need to be a parameter that the Aggregators
>> agree on in advance.)
>>