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

From: Christopher Patton <[email-masked]>
Date: Thu, 2 Dec 2021 16:04:14 -0800

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: "Martin Thomson" <[email-masked]>
Date: Fri, 03 Dec 2021 16:27:55 +1100

Hi Chris,

When you say

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

Having independent enforcement of anti-replay seems like it is important enough for this state to persist beyond the scope of a task.

Maybe stepping back and looking at how anti-replay is managed would help.  You don't want the same thing to be counted more than once.  The original design requires a total ordering of inputs, with a strict enforcement of that ordering.  That uses what is in effect a high resolution timestamp to ensuring that ordering is sensible.  It also means that tasks cannot be initiated out of order (or with overlapping inputs).  That seems unworkable to me.  Perfect global ordering, particularly when you consider helpers that serve multiple customers, is probably infeasible.

I think that #2 is the only reasonable outcome here.  However, you also need to use the timestamp (or part of it) to bound the time period during which you need to remember nonces.

That is, you use the time of an input to select from three different discard treatments:
1. discard because it is too old
2. discard because it is too new (which might be impossible, but you don't want something as simple as clock skew to be why your anti-replay was defeated)
3. discard if it has the same nonce as something you have previously accepted

In code:

if t < now() - window:
  discard as too old
else if t > now():
  discard as from the future
else if nonce in nonces_in_window:
  discard as duplicate
else:
  add nonce to nonces_in_window
  accept the measurement

(There's an interesting potential attack here in that a client provides different nonces or timestamps to each helper with a goal of spoiling results. Accepting half a share could be disastrous.  The validation process catches those pretty naturally, I think, probably.  This is something we should be careful to check any time that independent processing occurs like this.)

Separately, I've been looking at less simplistic applications of something like anti-replay.  I hope to be able to talk about that in more detail soon, but it might be that the anti-replay design you have is too restrictive for what we have in mind, no matter the outcome of this specific decision.

---

From: Christopher Patton <[email-masked]>
Date: Sat, 4 Dec 2021 15:17:43 -0800

Hi Martin, thanks for your thoughtful reply. I really like your suggestion.
I'd like to hear what others think, and in absence of a reason not to take
it I think we should make this a PR :)

Best,
Chris P.

On Thu, Dec 2, 2021 at 9:28 PM Martin Thomson <[email-masked]> wrote:

> Having independent enforcement of anti-replay seems like it is important
> enough for this state to persist beyond the scope of a task.
>
> Maybe stepping back and looking at how anti-replay is managed would help.
> You don't want the same thing to be counted more than once.  The original
> design requires a total ordering of inputs, with a strict enforcement of
> that ordering.  That uses what is in effect a high resolution timestamp to
> ensuring that ordering is sensible.  It also means that tasks cannot be
> initiated out of order (or with overlapping inputs).  That seems unworkable
> to me.  Perfect global ordering, particularly when you consider helpers
> that serve multiple customers, is probably infeasible.
>
> I think that #2 is the only reasonable outcome here.  However, you also
> need to use the timestamp (or part of it) to bound the time period during
> which you need to remember nonces.
>
> 2. discard because it is too new (which might be impossible, but you don't
> want something as simple as clock skew to be why your anti-replay was
> defeated)
> (There's an interesting potential attack here in that a client provides
> different nonces or timestamps to each helper with a goal of spoiling
> results. Accepting half a share could be disastrous.  The validation
> process catches those pretty naturally, I think, probably.  This is
> something we should be careful to check any time that independent
> processing occurs like this.)
>
> Separately, I've been looking at less simplistic applications of something
> like anti-replay.  I hope to be able to talk about that in more detail
> soon, but it might be that the anti-replay design you have is too
> restrictive for what we have in mind, no matter the outcome of this
> specific decision.
>
> --
> Ppm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ppm
>

---

From: Erik Taubeneck <[email-masked]>
Date: Mon, 6 Dec 2021 10:44:44 -0800

> enough for this state to persist beyond the scope of a task.

I strongly agree here, and it seems worthwhile to include in the spec. This
will be important for other privacy mechanisms, beyond anti-replay. For
example, if I understand correctly, the proposed WICG spec Attribution
Reporting API with Aggregate Reports
<https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md>
aims to follow the PPM spec, and would require persistent state to manage a
privacy budget. In addition, that API may even allow replay in a controlled
manner within the privacy budget. From their proposal draft
<https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md#privacy-budgeting>
:

Note: The design for the aggregation service also requires some amount of
> budgeting to ensure records aren’t processed too many times.

Charlie Harrison can likely provide more context on that specific proposal,
but I agree overall that we likely want to support more than just
anti-replay to enforce the privacy of the PPM results.

Cheers,

Erik

On Sat, Dec 4, 2021 at 3:18 PM Christopher Patton <cpatton=
[email-masked]> wrote:

> Hi Martin, thanks for your thoughtful reply. I really like your
> suggestion. I'd like to hear what others think, and in absence of a reason
> not to take it I think we should make this a PR :)
>
> Best,
> Chris P.
>
>> Maybe stepping back and looking at how anti-replay is managed would
>> help.  You don't want the same thing to be counted more than once.  The
>> original design requires a total ordering of inputs, with a strict
>> enforcement of that ordering.  That uses what is in effect a high
>> resolution timestamp to ensuring that ordering is sensible.  It also means
>> that tasks cannot be initiated out of order (or with overlapping inputs).
>> That seems unworkable to me.  Perfect global ordering, particularly when
>> you consider helpers that serve multiple customers, is probably infeasible.
>>
>> 2. discard because it is too new (which might be impossible, but you
>> don't want something as simple as clock skew to be why your anti-replay was
>> defeated)
>> Separately, I've been looking at less simplistic applications of
>> something like anti-replay.  I hope to be able to talk about that in more
>> detail soon, but it might be that the anti-replay design you have is too

---

From: Christopher Patton <[email-masked]>
Date: Tue, 7 Dec 2021 15:18:15 -0800

Thanks Erik, yeah brought up this consideration early on in the process and
is indeed the reason we have this mechanism.

Here's a PR for implementing Martin's suggestion:
https://github.com/abetterinternet/ppm-specification/pull/169

Reviews appreciated!
Chris P.

On Mon, Dec 6, 2021 at 10:45 AM Erik Taubeneck <[email-masked]>
wrote:

> I strongly agree here, and it seems worthwhile to include in the spec.
> This will be important for other privacy mechanisms, beyond anti-replay.
> For example, if I understand correctly, the proposed WICG spec Attribution
> Charlie Harrison can likely provide more context on that specific
> proposal, but I agree overall that we likely want to support more than just

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 08 Dec 2021 11:03:31 +1100

Thanks for putting this together Chris,

There is an implicit assumption in this design that says that reports are bound to a task that is known when the report is generated.  To that end, this design is probably not the best design that we might come up with.

If you assume this operating model, there are two sort of natural ways to approach the report collection process:

1. You publicize a task ID at some time.  Clients produce reports over some period and when you have enough you close the task and generate an aggregate.  In this model, individual reports could be evenly distributed over the period fairly evenly, so using a timestamp as part of your nonce is a good way to improve collision resistance.

2. Reports are generated on demand.  Perhaps you have a polling process that contacts clients at certain times, gives them a task ID and asks for a report.  In this model, reports might be generated all at once, which makes times less useful for avoiding collision.

In both cases, the task ID is what prevents any individual report from being used for multiple reports.  Replay within the task is assured by the uniqueness of the nonce, not the value of the timestamp.  

Of course, you could reuse a task ID, but we might reasonably assume that the aggregation service will not accept that.  Or, you could design a system in which the task ID is usable for multiple aggregation runs, but that seems like it defeats the purpose of having a high entropy task ID in the first place.  My thought is that it might be even better to have a leader assign task IDs so that uniqueness can be assured more easily.  If I'm right in that the task ID is central to the anti-replay design, then that is a more robust design.

With that in mind, I'm not sure that you even need a timestamp at all.  At least for this design.  I think that if we want to consider designs where the use of a single report is not so strictly Boolean, then we could need timestamps.

On Wed, Dec 8, 2021, at 10:18, Christopher Patton wrote:
> Thanks Erik, yeah brought up this consideration early on in the process 
> and is indeed the reason we have this mechanism.
>
> On Mon, Dec 6, 2021 at 10:45 AM Erik Taubeneck <[email-masked]> wrote:
>> Martin said:
>> 
>> I strongly agree here, and it seems worthwhile to include in the spec. This will be important for other privacy mechanisms, beyond anti-replay. For example, if I understand correctly, the proposed WICG spec Attribution Reporting API with Aggregate Reports <https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md> aims to follow the PPM spec, and would require persistent state to manage a privacy budget. In addition, that API may even allow replay in a controlled manner within the privacy budget. From their proposal draft <https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md#privacy-budgeting>:
>> 
>> 
>>> Note: The design for the aggregation service also requires some amount of budgeting to ensure records aren’t processed too many times.
>> 
>> Charlie Harrison can likely provide more context on that specific proposal, but I agree overall that we likely want to support more than just anti-replay to enforce the privacy of the PPM results. 
>> 
>> Cheers,
>> 
>> Erik
>> 
>> 
>> 
>> On Sat, Dec 4, 2021 at 3:18 PM Christopher Patton <cpatton=[email-masked]> wrote:
>>> Hi Martin, thanks for your thoughtful reply. I really like your suggestion. I'd like to hear what others think, and in absence of a reason not to take it I think we should make this a PR :)
>>> 
>>> Best,
>>> Chris P.
>>>

---

From: Tim Geoghegan <[email-masked]>
Date: Tue, 7 Dec 2021 16:37:26 -0800

Hi Martin,

I think you may be misunderstanding the purpose or scope of the task ID (or
perhaps I should say: the draft is not sufficiently clear about how task ID
works). You write:

>You publicize a task ID at some time.  Clients produce reports over some
period and when you have enough you close the task and generate an
aggregate.

...suggesting a 1:1 relationship between a task ID and an aggregate emitted
by a PPM deployment. Rather, a task ID describes a long-running report
collection and aggregation task, for which aggregates are emitted
periodically (the period or _aggregation window_ is one of the parameters
associated with a task ID). Further, many clients may be contributing
reports under a single task ID.

So for example, imagine a web browser measuring whether users press a
certain button. The browser vendor would configure a PPM task and
distribute its parameters to two aggregators (n.b. the mechanism for task
parameter distribution is explicitly out of scope for the PPM protocol).
Then, the browser vendor ships a version of the browser to all its users
that knows about the task ID (the task ID could be compiled into the
browser or maybe the browser vendor has some secure configuration
mechanism). Browser installations then start submitting reports to
aggregators using the task ID.

>Reports are generated on demand.  Perhaps you have a polling process that
contacts clients at certain times, gives them a task ID and asks for a
report.  In this model, reports might be generated all at once, which makes
times less useful for avoiding collision.

In PPM, clients push reports into aggregators rather than having reports
pulled (or scraped, as Prometheus would put it) from clients by
aggregators. This is necessary because clients will frequently be behind
NAT or egress only firewalls or unable to keep a port open for metrics
pulls for some other reason.

Thanks,
Tim

On Tue, Dec 7, 2021 at 4:04 PM Martin Thomson <[email-masked]> wrote:

> There is an implicit assumption in this design that says that reports are
> bound to a task that is known when the report is generated.  To that end,
> this design is probably not the best design that we might come up with.
>
> 1. You publicize a task ID at some time.  Clients produce reports over
> some period and when you have enough you close the task and generate an
> aggregate.  In this model, individual reports could be evenly distributed
> over the period fairly evenly, so using a timestamp as part of your nonce
> is a good way to improve collision resistance.
>
> 2. Reports are generated on demand.  Perhaps you have a polling process
> that contacts clients at certain times, gives them a task ID and asks for a
> report.  In this model, reports might be generated all at once, which makes
> times less useful for avoiding collision.
>
> In both cases, the task ID is what prevents any individual report from
> being used for multiple reports.  Replay within the task is assured by the
> uniqueness of the nonce, not the value of the timestamp.
>
> Of course, you could reuse a task ID, but we might reasonably assume that
> the aggregation service will not accept that.  Or, you could design a
> system in which the task ID is usable for multiple aggregation runs, but
> that seems like it defeats the purpose of having a high entropy task ID in
> the first place.  My thought is that it might be even better to have a
> leader assign task IDs so that uniqueness can be assured more easily.  If
> I'm right in that the task ID is central to the anti-replay design, then
> that is a more robust design.
>
> With that in mind, I'm not sure that you even need a timestamp at all.  At
> least for this design.  I think that if we want to consider designs where
> the use of a single report is not so strictly Boolean, then we could need
> timestamps.
>
> >>> Having independent enforcement of anti-replay seems like it is
> important enough for this state to persist beyond the scope of a task.
> Reporting API with Aggregate Reports <
> https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md>
> manner within the privacy budget. From their proposal draft <
> https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md#privacy-budgeting
> >:
> >>
> >>
> >>> Note: The design for the aggregation service also requires some amount
> of budgeting to ensure records aren’t processed too many times.
> >>
> >>>> Having independent enforcement of anti-replay seems like it is
> important enough for this state to persist beyond the scope of a task.
> >>>>
> >>>> I think that #2 is the only reasonable outcome here.  However, you
> also need to use the timestamp (or part of it) to bound the time period
> during which you need to remember nonces.
> >>>>
> >>>> (There's an interesting potential attack here in that a client
> provides different nonces or timestamps to each helper with a goal of
> spoiling results. Accepting half a share could be disastrous.  The
> validation process catches those pretty naturally, I think, probably.  This
> is something we should be careful to check any time that independent

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 08 Dec 2021 15:29:57 +1100

Thanks Tim,

I had not internalized the naming scheme, so you are right.  It's clear (ish), but "task" is entirely the wrong concept to pair this to.  Of course, if it were structured in the way I describe, then it would be fine.  It's not, so let's talk about how it is structured.

The PR sets a narrow window about the current time over which the reports can be accepted.  A little into the past, a different amount into the future.  This isn't really helpful as it relates to anti-replay.  All you need here is a rolling window over which you are willing to track nonces for the purposes of anti-replay.  (Multiple discrete slices of time is probably best as that allows you to have entries fall off the back cheaply.)  Under that model, it's OK if the report was generated days or even weeks ago, as long as you are still tracking for that period.  If you want to ensure that your ingress system is able to take in reports and just stash them for processing later, then this design forces you to consider that ingress system to be part of what you trust. This check is done in real time, so it has to be done now.

There's no reason to do real-time checks.  You could build an ingress system that just sucks reports in and stores them without thinking too much.  Then, when you initiate processing you pass them to trusted components that do the anti-replay checks and the other validation tasks.  None of that requires invoking now().

You also don't really need to worry about time tolerance factors.  At least not as described in the PR.  You need some allowance for reports to arrive into the future, because clock skew is a real thing.  But you can get that by including a little overflow into the future.  The only way in which you need the current time is in determining

The design I implemented for TLS looks something like this:

At any given time you have T windows of time, each W seconds wide.  That means you accept reports for a window of about T*W seconds around the current time.  Each window has a collection of nonces.  As all reports have a unique timestamp you use that to find which collection to use (w = floor(t / W)).  New reports are accepted and added to the corresponding collection if they are not present; or they are dropped if the nonce is present.  On a fixed W second interval (i.e., when (now() + skew_adjustment) % W == 0) you empty out the oldest window.  Anything older than now() + skew_adjustment - T*W or newer than now() + skew_adjustment (careful with fenceposts here) is automatically dropped.

Note that this means that while the window is T*W seconds, you are always accepting timestamps between skew_adjustment and W+skew_adjustment into the future.  The integrity of the system doesn't care about time travel, so that's fine, you just want to avoid rejecting reports just because a client has a dodgy clock.  

Another aspects of this is that you don't really care if the time is accurate or not.  Clients could give you time that is rounded to W and things would work fine under this scheme: you just end up leaning on the randomness a little harder.  (I say this because the fine details of the time series of events could, in some circumstances, be information that a customer of the PPM system might not want to entrust to the system.)

I'm not getting any of that from the pull request.

BTW, regarding the pull vs. push model for submissions, I remind you that we're not documenting a system, we're standardizing something that is hopefully useful for other things.

On Wed, Dec 8, 2021, at 11:37, Tim Geoghegan wrote:
> Hi Martin,
>
> I think you may be misunderstanding the purpose or scope of the task ID 
> (or perhaps I should say: the draft is not sufficiently clear about how 
> task ID works). You write:
>
>>You publicize a task ID at some time.  Clients produce reports over some period and when you have enough you close the task and generate an aggregate. 
>
> ...suggesting a 1:1 relationship between a task ID and an aggregate 
> emitted by a PPM deployment. Rather, a task ID describes a long-running 
> report collection and aggregation task, for which aggregates are 
> emitted periodically (the period or _aggregation window_ is one of the 
> parameters associated with a task ID). Further, many clients may be 
> contributing reports under a single task ID.
>
> distribute its parameters to two aggregators (n.b. the mechanism for 
> task parameter distribution is explicitly out of scope for the PPM 
> protocol). Then, the browser vendor ships a version of the browser to 
> all its users that knows about the task ID (the task ID could be 
> compiled into the browser or maybe the browser vendor has some secure 
> configuration mechanism). Browser installations then start submitting 
> reports to aggregators using the task ID.
>
>>Reports are generated on demand.  Perhaps you have a polling process that contacts clients at certain times, gives them a task ID and asks for a report.  In this model, reports might be generated all at once, which makes times less useful for avoiding collision.
>
> In PPM, clients push reports into aggregators rather than having 
> reports pulled (or scraped, as Prometheus would put it) from clients by 
> aggregators. This is necessary because clients will frequently be 
> behind NAT or egress only firewalls or unable to keep a port open for 
> metrics pulls for some other reason.
>
> Thanks,
> Tim
>

---

From: Christopher Patton <[email-masked]>
Date: Wed, 8 Dec 2021 09:14:07 -0800

Hi Martin,

I had basically the same vision for storing reports, so I think it's just a
matter of making the PR more clear and maybe remove the requirement to
enforce the time boundaries. Detailed comments in-line.

> The PR sets a narrow window about the current time over which the reports
> can be accepted.  A little into the past, a different amount into the
> future.

max_report_backward_offset is intended to define the duration for which an
aggregator MUST remember a nonce for the purpose of anti-replay. Reports
with timestamps too far in the past are ignored so that we don't have to
check for replay.

max_report_forward_offset has a different purpose, as it is intended to
prevent the aggregators from having to hang on to reports for a long time.
The PR conflates this with anti-replay.

> This isn't really helpful as it relates to anti-replay.  All you need here
> is a rolling window over which you are willing to track nonces for the
> purposes of anti-replay.  (Multiple discrete slices of time is probably
> best as that allows you to have entries fall off the back cheaply.)  Under
> that model, it's OK if the report was generated days or even weeks ago, as
> long as you are still tracking for that period.  If you want to ensure that
> your ingress system is able to take in reports and just stash them for
> processing later, then this design forces you to consider that ingress
> system to be part of what you trust. This check is done in real time, so it
> has to be done now.
>
> There's no reason to do real-time checks.  You could build an ingress
> system that just sucks reports in and stores them without thinking too
> much.  Then, when you initiate processing you pass them to trusted
> components that do the anti-replay checks and the other validation tasks.
> None of that requires invoking now().

I agree that we want to be able to decouple the ingress system. The
fundamental purpose of the time boundaries is to reduce storage
requirements. The current spec says that the leader SHOULD ignore reports
from too far in the future. We could keep that, and perhaps say that
aggregators MAY ignore reports from too far in the past. The trouble is
that the leader and helper may disagree on how long they're willing to keep
the nonce set around. For instance, if the leader keeps reports around for
7 days and wants to bulk-aggregate the reports all at once, but the helper
ignores reports that are more than a day old, then most of the reports will
get ignored.

At any given time you have T windows of time, each W seconds wide.  That
> means you accept reports for a window of about T*W seconds around the
> current time.  Each window has a collection of nonces.  As all reports have
> a unique timestamp you use that to find which collection to use (w =
> floor(t / W)).  New reports are accepted and added to the corresponding
> collection if they are not present; or they are dropped if the nonce is
> present.  On a fixed W second interval (i.e., when (now() +
> skew_adjustment) % W == 0) you empty out the oldest window.  Anything older
> than now() + skew_adjustment - T*W or newer than now() + skew_adjustment
> (careful with fenceposts here) is automatically dropped.
>
> Note that this means that while the window is T*W seconds, you are always
> accepting timestamps between skew_adjustment and W+skew_adjustment into the
> future.  The integrity of the system doesn't care about time travel, so
> that's fine, you just want to avoid rejecting reports just because a client
> has a dodgy clock.
>

This is basically what I had in mind for report storage at the leader. But
what about storing the nonce set of processed reports at the helper? The
aggregators should be able to prune the oldest windows in a similar way,
but what happens when the leader sends a report to the helper with a
timestamp is in a previously pruned window? The helper will have to to
ignore it since it can't determine if the report was replayed. The problem
that arises is that the aggregators may not agree on how far in the past is
acceptable.

We solve this in the current PR by having both aggregators enforce
max_report_backward_offset. Perhaps there's another way to solve this
problem? (Or maybe there isn't an actual problem here!)

Chris P.

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 09 Dec 2021 05:37:40 +1100

On Thu, Dec 9, 2021, at 04:14, Christopher Patton wrote:
> But what about storing the nonce set of processed reports at the 
> helper? The aggregators should be able to prune the oldest windows in a 
> similar way, but what happens when the leader sends a report to the 
> helper with a  timestamp is in a previously pruned window? 

Two options:

1. The leader and helpers agree about the nonce retention window.
2. Any server can reject a report and all others have to accept that choice.

---

From: Erik Taubeneck <[email-masked]>
Date: Wed, 8 Dec 2021 14:21:05 -0800

Given the two options, it seems like we actually need both.

> 1. The leader and helpers agree about the nonce retention window.

The retention window should be a globally accepted fact, for a specific
"task ID".  (Agreed with Martin that it might be useful to bikeshed the use
of "task" here.) The leader, helpers, clients, and collector should all be
aware of the window.

> 2. Any server can reject a report and all others have to accept that

If the window is a known value, then ideally all servers would reject the
same reports. The same should be true about checking the nonces. Rejecting
the report if any server rejects it is the most conservative case (secure
up to n-1 dishonest parties). Does the standard aim to be secure up to that
threshold, or could we consider other consensus protocols here?

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 09 Dec 2021 10:08:34 +1100

This seems sensible to me.  I think that the problem I had with the PR is that the definition of the window was anchored on the current time.  This is because it was anchored on the notion of a "task", which is long-running.  However, I think that we want a different concept, that of a "query" perhaps (which is a task in my mind), that governs the batch of things that are being aggregated.  At that point, the time range can be made absolute and agreed.

Then they can all agree to be tracking nonces between t_start and t_end, with values outside that range being uniformly rejected.  You can expect them to all consistently reject or accept everything.  The value of now() doesn't need to come into it.

On Thu, Dec 9, 2021, at 09:21, Erik Taubeneck wrote:
> "task ID".  (Agreed with Martin that it might be useful to bikeshed the 
> use of "task" here.) The leader, helpers, clients, and collector should 
> all be aware of the window.
> 
> If the window is a known value, then ideally all servers would reject 
> the same reports. The same should be true about checking the nonces. 
> Rejecting the report if any server rejects it is the most conservative 
> case (secure up to n-1 dishonest parties). Does the standard aim to be 
> secure up to that threshold, or could we consider other consensus 
> protocols here?
> 
>

---

From: "Christopher Wood" <[email-masked]>
Date: Wed, 08 Dec 2021 15:32:24 -0800

On Wed, Dec 8, 2021, at 3:08 PM, Martin Thomson wrote:
> This seems sensible to me.  I think that the problem I had with the PR 
> is that the definition of the window was anchored on the current time.  
> This is because it was anchored on the notion of a "task", which is 
> long-running.  However, I think that we want a different concept, that 
> of a "query" perhaps (which is a task in my mind), that governs the 
> batch of things that are being aggregated.  At that point, the time 
> range can be made absolute and agreed.
>
> Then they can all agree to be tracking nonces between t_start and 
> t_end, with values outside that range being uniformly rejected.  You 
> can expect them to all consistently reject or accept everything.  The 
> value of now() doesn't need to come into it.

This does seem like a reasonable simplification for the aggregation protocol. It moves the boundary question out of the main flow and closer to configuration. I suppose a task (or query) would have well-defined windows marking t_start and t_end, clients would include a timestamp in the report flow, and aggregators would check that against the known window bounds. Is that the idea?

Best,
Chris

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 09 Dec 2021 15:04:27 +1100

On Thu, Dec 9, 2021, at 10:32, Christopher Wood wrote:
> This does seem like a reasonable simplification for the aggregation 
> protocol. It moves the boundary question out of the main flow and 
> closer to configuration. I suppose a task (or query) would have 
> well-defined windows marking t_start and t_end, clients would include a 
> timestamp in the report flow, and aggregators would check that against 
> the known window bounds. Is that the idea?

That's the general idea, yes.  The good part is that it buries all the complexity in the implementations.  The bad part is that it buries complexity in the implementations, which have to deal with it either way.

---

From: Christopher Patton <[email-masked]>
Date: Thu, 9 Dec 2021 07:48:19 -0800

The collect-request already specifies a "batch interval", which defines the
range of timestamps of reports that will be aggregated. The start and end
time needs to align with time boundaries that the aggregators and collector
agree on:
https://abetterinternet.github.io/ppm-specification/draft-gpew-priv-ppm.html#name-validating-batch-parameters

This collect-request is what I've been thinking of as a "query". I guess
the observation here is that we only need to keep track of nonces for batch
intervals that have not been "collected"?

On Wed, Dec 8, 2021 at 8:04 PM Martin Thomson <[email-masked]> wrote:

> That's the general idea, yes.  The good part is that it buries all the
> complexity in the implementations.  The bad part is that it buries
> complexity in the implementations, which have to deal with it either way.
>
> --
> Ppm mailing list
> [email-masked]

---

From: Christopher Patton <[email-masked]>
Date: Fri, 10 Dec 2021 14:59:31 -0800

Hi all, I've updated the PR to remove the requirement for time
synchronization.

On Thu, Dec 9, 2021 at 7:48 AM Christopher Patton <[email-masked]>
wrote:

> The collect-request already specifies a "batch interval", which defines
> the range of timestamps of reports that will be aggregated. The start and
> end time needs to align with time boundaries that the aggregators and
> collector agree on:
>