Subject: [Ppm] Uploading report shares directly to aggregators

From: Christopher Patton <[email-masked]>
Date: Tue, 18 Jan 2022 19:19:36 -0800

Hi list,

The current spec has the client upload to the leader a "report" that
contains the encrypted input share of each aggregator. Later, during the
aggregation flow, the leader relays to each helper its share of the report
(i.e., the encrypted input share, the nonce, and extensions). An
alternative upload flow would have the client upload a report share to each
aggregator directly. Both of these approaches have pros and cons, so in
this thread I'd like us to consider which approach makes the most sens or
whether there is a better alternative.

For clarity, the current options are:
Option #1 (status quo): Have the client upload a report to the leader that
contains all of the report shares.
Option #2 (split upload): Have the client upload a report share to each
aggregator directly. For concreteness, this option is spelled out in [1].

There are at least two considerations that lead to the current spec (i.e.,
option #1). One is that option #2 has more failure modes compared to option
#1. For example, if the leader begins aggregating a report before the
helper has received its share from the client, then the report will be
rejected and the leader will be forced to retry later on. The second
consideration is that option #2 has more stringent storage requirements for
the helper, since it has to store its report shares for as long as they can
be aggregated. (Recall that a report may be aggregated multiple times, with
a different aggregation parameter each time [2]. This is necessary to
implement protocols, like Poplar [3], that require the collector to compute
the aggregate result before computing the next aggregation parameter.

The major downside of option #1 (as observed in [4]) is that it increases
the leader-to-helper communication cost. For prio3 the overhead is modest
-- a couple hundred bytes per report share, regardless of the data type --
but for poplar1 the overhead might be significant, since the size of each
input share is linear in the length of the input measurement.

Another downside of option #1 is that, because the leader picks the set of
reports that are aggregated, it can mount a (fairly weak) Sybil attack in
which it stuffs a batch with n-1 bogus reports, thereby leaking the
measurement of a target report entirely. (This requires colluding with the
collector.) Taking option #2 would force the leader to upload the bogus
report shares to the aggregators directly in order to mount the same
attack. In theory, there's not much difference between these two attacks,
since we consider an attacker that controls the network. But as a practical
matter, it would be possible for the helper to mitigate the attack by
rate-limiting requests from the leader's IP address. This isn't perfect,
but it's something. (Note that devising an optional defense against Sybil
attacks is tracked by [5].)

There are, of course, alternatives to these two options. For example:
Option #3 (deployment specific): We could spell the protocol in a way that
leaves this behavior up to the deployment. In particular, for a given task,
the servers would decide whether or not split the uploads.
Option #4 (no re-transmission): The current spec requires the leader to
re-transmit the helper's report share each time the aggregation flow is
executed. Instead, we could have the leader transmit it once and require
the helper to store it thereafter.

Your feedback is greatly appreciated. If anyone has a strong preference for
one of these options, sees a reason why one of them won't work, or has an
idea for an alternative, please chime in :)

Also, it would be great if someone who has implemented IDPFs could tell us
how large the input shares are for, say, inputs of length 64, 128, and 256
bits.

Best,
Chris P.

[1] PR: Draft for split upload:
https://github.com/abetterinternet/ppm-specification/pull/174
[2] Section of VDAF spec defining the aggregation parameter:
https://cjpatton.github.io/vdaf/draft-patton-cfrg-vdaf.html#name-preparation
[3] Section of VDAF spec describing Poplar:
https://cjpatton.github.io/vdaf/draft-patton-cfrg-vdaf.html#name-poplar1
[4] Issue: Cost implications of the leader being the only upload endpoint:
https://github.com/abetterinternet/ppm-specification/issues/130
[5] Issue: Client attestation:
https://github.com/abetterinternet/ppm-specification/issues/89

---

From: Charlie Harrison <[email-masked]>
Date: Wed, 19 Jan 2022 09:13:13 -0600

Thanks for prompting this discussion, Christopher. I would appreciate your
thoughts on Option 3, since it seems like there are very good reasons to
prefer either Option 1 or 2.

Another idle concern I had, which I cannot substantiate immediately, is
whether Option #1 meaningfully limits the space of possible MPC protocols
we could support, by revealing the # of reports being sent to the helper to
the leader.

cc schoppman who I think can give numbers for input shares in the current
C++ implementation, as well as rkubis who likely has opinions here.

> input share is linear in the length of the input measurement.

I don't quite understand this. I thought in Prio the input shares were
linear in the length of the input measurement even excluding the proofs,
since they are simple vector shares. Are you talking about just the SNIP
proofs?

> Your feedback is greatly appreciated. If anyone has a strong preference
> for one of these options, sees a reason why one of them won't work, or has
> an idea for an alternative, please chime in :)
>
> --
> Ppm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ppm
>

---

From: Erik Taubeneck <[email-masked]>
Date: Wed, 19 Jan 2022 09:00:02 -0800

Thanks for kicking this off Chris, and I appreciate the detailed analysis.

Ultimately, I would argue this should be a choice made in the
implementation, and not in the specification. A bunch more thoughts below:

There is a 4th option being discussed in issue #166
<https://github.com/abetterinternet/ppm-specification/issues/166> [1],
which moves in the opposite direction by proposing sending reports to a new
party called a consumer which is entirely untrusted and specified by the
collector. Note that the consumer would also also be able to mount the
Sybil attack, which I’ll address below.

This is the architecture proposed in Interoperable Private Attribution
<https://docs.google.com/document/d/1KpdSKD8-Rn0bWPTu4UtK54ks0yv2j22pA5SrAD9av4s/edit#heading=h.f4x9f0nqv28x>
[2], which we intend to be an implementation of PPM. I believe that it is
also the Multi-Browser Aggregation Service Explainer
<https://github.com/WICG/conversion-measurement-api/blob/main/SERVICE.md>
[3], with reports being sent to the reporting origin, but I would look to
Charlie Harrison to confirm.

The rationale here is almost entirely operational. Both of the APIs above
are implemented within an user-agent, but are used by arbitrary websites
and apps. Consuming and storing these reports sent from instances of those
user-agents is a non-trivial infrastructure challenge, and we should assume
that aggregators will not have 100% uptime. In fact, improving from 99.9%
uptime to 99.99% uptime can often mean an order of magnitude increase in
operational costs.

I would assume that the set of parties offering their services as
aggregators will be fairly constrained for the near-to-mid term, and as
such, collectors will have minimal choice when it comes to finding the
appropriate trade offs between operational concerns like uptime vs
infrastructure costs. As such, I believe it’s beneficial to move as much of
this cost and operational effort outside of the aggregators.

To the point on Sybil attacks: nearly all the APIs that would implement PPM
will run in user-agents on untrusted and unknown devices. The code used to
generate those reports will be open source, or at least the protocol will
be publicly known, so the bigger threat, in my opinion, is a malicious
entity operating a modified user-agent to generate events which enable a
Sybil attack. The IPA proposal linked above (as well as the Attribution
Reporting API with Aggregate Reports
<https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md>
[4]) propose using differential privacy to address these types of attacks.
This approach should also mitigate Sybil attacks.

I don’t believe that all implementations will end up using differential
privacy, and thus may find the proposal for reports to be sent directly to
all aggregators useful, but for those that do implement this mitigation,
sending the reports directly to all aggregators presents some meaningful
challenges.

Finally, in terms of cost, given that the majority of the bandwidth cost is
in egress cost (i.e. leaving a cloud provider network.) I would agree that
it would be useful to be able to specify multiple locations for reports to
be sent, somewhat similar to the structure proposed in this comment
<https://github.com/abetterinternet/ppm-specification/issues/130#issuecomment-967730879>
[5]. This would enable reports to be sent directly from clients into
different cloud providers–and the server running in those cloud providers
could be a proxy of the consumer (proposed above), a proxy of the leader,
or the aggregators themselves. This structure would allow us to separate
the egress cost concerns from the Sybil attack concerns.

Cheers,

Erik

[1] Issue 166: adding an untrusted consumer that stores reports before
aggregation: https://github.com/abetterinternet/ppm-specification/issues/166

[2] Interoperable Private Attribution proposal:
https://docs.google.com/document/d/1KpdSKD8-Rn0bWPTu4UtK54ks0yv2j22pA5SrAD9av4s/edit#heading=h.f4x9f0nqv28x

[3] Multi-Browser Aggregation Service Explainer, subset of the Attribution
Reporting API proposal:
https://github.com/WICG/conversion-measurement-api/blob/main/SERVICE.md

[4] Attribution Reporting API with Aggregate Reports, subset of the
Attribution Reporting API proposal:
https://github.com/WICG/conversion-measurement-api/blob/main/AGGREGATE.md

[5] Issue 130 comment, proposing proxies to receive reports in separate
cloud providers:
https://github.com/abetterinternet/ppm-specification/issues/130#issuecomment-967730879

On Wed, Jan 19, 2022 at 7:15 AM Charlie Harrison <csharrison=
[email-masked]> wrote:

>> Option #1 (status quo): Have the client upload a report to the leader
>> that contains all of the report shares.
>> There are at least two considerations that lead to the current spec
>> (i.e., option #1). One is that option #2 has more failure modes compared to
>> option #1. For example, if the leader begins aggregating a report before
>> the helper has received its share from the client, then the report will be
>> Another downside of option #1 is that, because the leader picks the set
>> of reports that are aggregated, it can mount a (fairly weak) Sybil attack
>> in which it stuffs a batch with n-1 bogus reports, thereby leaking the
>> Option #3 (deployment specific): We could spell the protocol in a way
>> that leaves this behavior up to the deployment. In particular, for a given
>> task, the servers would decide whether or not split the uploads.
>> Also, it would be great if someone who has implemented IDPFs could tell
>> us how large the input shares are for, say, inputs of length 64, 128, and
>> 256 bits.
>>
>> Best,
>> Chris P.
>>
>>
>> [4] Issue: Cost implications of the leader being the only upload
>> endpoint: https://github.com/abetterinternet/ppm-specification/issues/130

---

From: Christopher Patton <[email-masked]>
Date: Wed, 19 Jan 2022 12:59:15 -0800

> I would appreciate your thoughts on Option 3, since it seems like there
> are very good reasons to prefer either Option 1 or 2.
>

I think the main downside to #3 is that it adds complexity to the protocol
and therefore more ways for things to fail. Ideally we'd identify a single
approach that everyone agrees will work and then figure out how to mitigate
the downsides.  In my opinion, option #3 should only be considered if there
is some use case for which #1 or #2 is untenable.

> we could support, by revealing the # of reports being sent to the helper to

This is an interesting observation. The current PPM spec is centered around
the execution of a VDAF, the shape of which already rules out any MPC in
which the helper and leader get a different number of shares. This could
change, of course, as we're amendable to changes to the VDAF spec to
include MPC protocols that might end up being useful. Or there might be
different PPM variants, in order to support MPC protocols with a different
shape.

> since they are simple vector shares. Are you talking about just the SNIP

Yes, this includes the proof shares. In prio3, the input and proof shares
are just vectors of field elements that add up to the plaintext input and
proof. The helper shares are computed by picking a PRNG seed and expanding
it into a sequence of pseudorandom field elements. That means all a helper
needs to represent its share is the seed itself. This optimization is
fairly standard. Here is how it works in code:
https://github.com/abetterinternet/libprio-rs/blob/main/src/vdaf/prio3.rs#L417-L441

Note that the leader's input share is indeed linear in the length of the
measurement. The length of the proof share depends on the data type, but
can range anywhere from O(n), O(n^{-1/2}), or O(log n) with some
optimization.

Chris P.

---

From: Christopher Patton <[email-masked]>
Date: Wed, 19 Jan 2022 13:25:06 -0800

Hi Erik!

> Sybil attack, which I’ll address below.

Let's call this option #5 for the sake of discussion. Option #4 is defined
at the top of this thread.

> this cost and operational effort outside of the aggregator
>

The ENPA system called this the "ingestor". There the rationale was the
same: To relieve the aggregators of the operational burden of horizontally
scaling to consume client traffic. In the current spec, there is a
distinguished aggregator, called the leader, who bears this responsibility.

I think it makes sense for a leader deployment to have a separate
"leader-ingestor" service and "leader-aggregator" service that have
different uptime requirements (and are perhaps maintained by different
teams within the same organization). My (current) objection to option #5 is
that roles like "leader", "helper", and "collector" have more to do with
the trust model than who is operationally responsible for what. For
instance, a statement "We assume the leader and helper don't collude" is
meaningful because they get different sets of input shares; on the other
hand, it doesn't sense to ask whether the leader-ingestor and
leader-aggregator collude, since they only see one set of input shares.

It's just my opinion, but I think option #5 would only make sense if the
ingestor/consumer did something that is not already implemented by some
server in the protocol.

> To the point on Sybil attacks: nearly all the APIs that would implement
> PPM will run in user-agents on untrusted and unknown devices. The code used
> to generate those reports will be open source, or at least the protocol
> will be publicly known, so the bigger threat, in my opinion, is a malicious

DP has been discussed as a defense for Sybil attacks, as has (some variant
of) Privacy Pass, which would allow the aggregators to avoid ingesting
reports from clients they haven't seen before. All of these things are
still on the table, but so far have been considered as extensions to the
core PPM protocol.

> sending the reports directly to all aggregators presents some meaningful

Interesting, could you be more specific? I'm not aware of a DP mechanism
for which option #2 would be a barrier.

---

From: Erik Taubeneck <[email-masked]>
Date: Wed, 19 Jan 2022 14:31:10 -0800

Thanks for the reply Chris.

> teams within the same organization).

What I am proposing, and is discussed in issue #166 and #64, is allowing an
entirely untrusted entity to play the role of "ingestor", so that a
"collector" can either run this system themselves, or be able to hire any
service (beyond the set of approved organizations that run aggregators.)
This is particularly important in the setting where a web platform vendor
may have a very small set of approved organizations; shifting as much of
the operational cost out of that small set.

>From the "collector" point of view, I see these options as
Option #1: I have a limited set of leaders to choose from which can receive
my reports, without much optionality between uptime and cost.
Option #2: I have an even more limited set of aggregators which must
receive my reports, and uptime is dependent on all of them.
Option #5: I can choose to ingest reports myself, or outsource it to any
service provider. I still have a limited set of aggregators, but I only
rely on them for aggregation and not real-time ingestion.

If we can design solutions in which option #5 still provides the intended
security and privacy properties, it seems greatly preferable to the
"collector". That said, I am advocating for option #3, with the choice that
is inclusive of option #5.

> My (current) objection to option #5 is that roles like "leader", "helper",
> and "collector" have more to do with the trust model than who is
> operationally responsible for what. ... it doesn't sense to ask whether the
> leader-ingestor and leader-aggregator collude, since they only see one set
> of input shares.

There is a meaningful set of attacks where the "ingestor" is or colludes
with the "collector", given that the collector may have added context. For
example, in this case the "collector" and "ingestor" could work together to
mount the Sybil attack you describe.

> for which option #2 would be a barrier.

I'm not suggesting that option #2 would prevent DP, but rather that a
solution which employs a DP mechanism to prevent the Sybil attack incurs
the added operational costs of option #2, without the added benefit.

Cheers,
Erik

On Wed, Jan 19, 2022 at 1:25 PM Christopher Patton <[email-masked]>
wrote:

>> that aggregators will not have 100% uptime. In fact, improving from
>> 99.9% uptime to 99.99% uptime can often mean an order of magnitude increase
>> in operational costs.
>>

---

From: Christopher Patton <[email-masked]>
Date: Wed, 19 Jan 2022 15:36:44 -0800

Erik,

> What I am proposing, and is discussed in issue #166 and #64, is allowing
> an entirely untrusted entity to play the role of "ingestor", so that a
> Option #1: I have a limited set of leaders to choose from which can
> receive my reports, without much optionality between uptime and cost.

> is inclusive of option #5.

This use case makes perfect sense to me, and I think we should make sure
the protocol is written in a way that enables it. I'm just not sure doing
so necessitates option #5, i.e., defining an explicit ingestor role. In
particular, if we take option #1, there is nothing that stops the
collector/ingestor from uploading the reports to the leader directly. The
only difference is that the leader may wish to authenticate the upload
request (as is done in ENPA for instance), but this is a matter for the
deployment and needn't be addressed in the core PPM protocol. (Of course,
if we need to define an extension to support this use case, then we can and
should do so.)

The same seems true if we take option #2. Here I would just say that
standing up an ingestion server between the clients and the aggregators is
even more desirable, since the helper wouldn't have to absorb client
traffic. But here again I view this as a matter for the deployment and not
something that impacts the core protocol logic.

Perhaps one way to resolve this question is to have the document enumerate
the various deployment scenarios we envision and make sure that the core
protocol logic supports all of them.

> mount the Sybil attack you describe.

Ah, true enough! Though we've been considering an even stronger attacker
for privacy: One that controls the collector completely and controls a
subset of the aggregators (but not all of them). This is somewhere in
Security Considerations, but I don't think this is spelled out that well.

> the added operational costs of option #2, without the added benefit.

Can you provide more detail? What benefit is lost, exactly? Do you have an
attack? I want to drill down on this because it sounds like a potential
deal breaker for #2. (More broadly, any option that requires us to
significantly compromise security should be off the table.)

Chris P.

---

From: Erik Taubeneck <[email-masked]>
Date: Wed, 19 Jan 2022 16:51:52 -0800

Chris,
 Thanks for your patient feedback, I might be catching up a bit here, but
it's been very helpful for me to wrap my head around this.

> the protocol is written in a way that enables it.

Great! My initial read was that it wouldn't currently enable it, and I'm
happy to work on an issue/PR that can make that more clear and enumerate
various deployment scenarios, as you suggest. One point of confusion was
the suggestion about limiting reports from a single IP address, as I'd
expect an intermediary server between the client and leader/aggregators to
likely have a fixed IP address.

> traffic.

Agreed. My misunderstanding was that this would require all aggregators to
handle real-time client traffic. If this can happen as a batch from an
ingestion service, having it go directly to each aggregator seems
preferable.

> significantly compromise security should be off the table.)

I was not envisioning an attack, but rather that all aggregators would need
to handle real-time client traffic, which could create quite a bit of
operational risk. But given that was my misunderstanding, I don't think
this is a detractor for option #2.

Cheers,
Erik

---

From: Christopher Patton <[email-masked]>
Date: Wed, 19 Jan 2022 17:28:31 -0800

> likely have a fixed IP address.

Awesome! Let's start with opening an issue and folks to start putting their
deployment setups there.

Yes, rate-limiting clients based on IP alone is impossible for aggregators
if they're behind a proxy. It should be noted that this is a heuristic only
that an attacker may be able to defeat in many ways. To deal with with
Sybil attacks in general, we'll definitely have to do a bit more anyway.

Chris P.

---

From: Charlie Harrison <[email-masked]>
Date: Thu, 20 Jan 2022 10:03:48 -0600

Thanks Chris,
I think I am in agreement with Erik that we could mitigate the issues with
Option #2 if there is an ingestor client. I think framing the protocol this
way actually allows close imitation of option #1 and #2

- An "option 1" deployment could just specify one of the aggregators to
work as the ingestor even if it isn't required by the protocol. They just
happen to be the same party.
- An "option 2" deployment could have the ingestor fan out reports to
multiple aggregators (or ignore the ingestor completely)

Your other points make perfect sense to me!

On Wed, Jan 19, 2022 at 7:28 PM Christopher Patton <[email-masked]>
wrote:

> Awesome! Let's start with opening an issue and folks to start putting
> their deployment setups there.
>

---

From: Phillipp Schoppmann <[email-masked]>
Date: Thu, 20 Jan 2022 18:19:26 +0100

Hi everyone,

I'm just reading through the discussion and catching up.
@Christopher Patton <[email-masked]> @Charlie Harrison
<[email-masked]> regarding the sizes of IDPF shares, I did some
benchmarks:

   - 32 bit inputs -> 2127 byte shares
   - 64 bit inputs -> 4283 byte shares
   - 128 bit inputs -> 8539 byte shares

These are for a DPF that allows evaluation at every bit of the input (like
Poplar), but currently without the VDAF part. I am in the process of
implementing verification for our IDPF implementation, and can tell you
more once that's done.

Best,
Phillipp

On Thu, Jan 20, 2022 at 5:04 PM Charlie Harrison <[email-masked]>
wrote:

>> Yes, rate-limiting clients based on IP alone is impossible for
>> aggregators if they're behind a proxy. It should be noted that this is a
>> heuristic only that an attacker may be able to defeat in many ways. To deal
>> with with Sybil attacks in general, we'll definitely have to do a bit more
>> anyway.
>>
>>
>> Chris P.
>>
>

---

From: Phillipp Schoppmann <[email-masked]>
Date: Thu, 20 Jan 2022 18:25:07 +0100

One more note on the share sizes: A lot of overhead (~50%) in our
implementation comes from the way I used protocol buffers for serialization.
I think there is some optimization potential here, so the cost could be
about half that if we use a format that just sends the raw bytes needed.
For example, with 128 bit inputs, the theoretical lower bound of the cost
is just 4128 bytes (again, excluding the verification part).

On Thu, Jan 20, 2022 at 6:19 PM Phillipp Schoppmann <[email-masked]>
wrote:

>> I think I am in agreement with Erik that we could mitigate the issues
>> with Option #2 if there is an ingestor client. I think framing the protocol
>> this way actually allows close imitation of option #1 and #2
>>
>> On Wed, Jan 19, 2022 at 7:28 PM Christopher Patton <
>> [email-masked]> wrote:
>>
>>>
>>>
>>>
>>>> Great! My initial read was that it wouldn't currently enable it, and
>>>> I'm happy to work on an issue/PR that can make that more clear and
>>>> enumerate various deployment scenarios, as you suggest. One point of
>>>> confusion was the suggestion about limiting reports from a single IP
>>>> address, as I'd expect an intermediary server between the client and
>>>> leader/aggregators to likely have a fixed IP address.
>>>>
>>>

---

From: Christopher Patton <[email-masked]>
Date: Thu, 20 Jan 2022 11:18:44 -0800

Thanks for the numbers, Philllipp! The VDAF spec will specify a binary
encoding for the input shares (including the IDPF key shares), which we can
reasonably expect to be much closer to the lower bound. Still, 4KB is a lot
of data to re-transmit per share. If we go with Option #1, we'll definitely
have to figure out a way to mitigate this. (Option #4 is one possibility.)

I also agree with Erik and Charlie that Option #2's downsides can be
mitigated by putting an ingestor in front of the helper. Though it's
important to note that this probably cancels out the egress savings, since
the ingestor (itself a service provider) is proxying report shares to the
helper. To get the egress savings, the helper would have to be able to
absorb traffic from clients directly.

Either way, Option #2 will require extra protocol logic to deal with
synchronization of the report shares. The current spec has each aggregate
sub-request from the leader specify the nonce of the report being
aggregated. To respond, the helper will first check if it has a report
share with that nonce. If not (perhaps the report share hasn't arrived),
it'll have to treat this as an error. Where things get tricky is what the
leader does next:
1. It might retry later, but there's no guarantee that the helper's report
share will ever arrive. Eventually it'll have to give up and the report
will get dropped.
2. It might just ignore the report. If the helper's report share ever shows
up, it might end up storing it indefinitely, waiting for the leader to send
a request that never arrives.

This suggests that some data loss may be inevitable in some deployments of
Option #2. In my own opinion, this data loss is acceptable.

Chris P.

On Thu, Jan 20, 2022 at 9:25 AM Phillipp Schoppmann <[email-masked]>
wrote:

>> These are for a DPF that allows evaluation at every bit of the input
>> (like Poplar), but currently without the VDAF part. I am in the process of

---

From: Erik Taubeneck <[email-masked]>
Date: Thu, 20 Jan 2022 13:16:15 -0800

>
> To get the egress savings, the helper would have to be able to absorb
> traffic from clients directly.
>

I don't think this is always the case (though it depends on specific cloud
providers), but it would require the client to at least send the
various shares to different locations. Here is roughly what I envision:
helper1 (in cloudA)
helper2 (in cloudB)

ingestor.proxyA (in cloudA)
ingestor.proxyB (in cloudB)

If the client is able to send reports to ingestor.proxyA and
ingestor.proxyB, then ingestor.proxyA can forward reports to helper1, and
ingestor.proxyB can forward reports to helper2.  There should be ways in
many cloud providers for that forwarding to not incur egress fees (for
example, AWS allows that to happen with S3 so long as both accounts are
within the same region.)

I'm not sure if this is compatible with what you envision for Option #2,
but it does seem desirable for an ingestor to at least have this option for
cost reduction.

Erik

On Thu, Jan 20, 2022 at 11:18 AM Christopher Patton <[email-masked]>
wrote:

> 2. It might just ignore the report. If the helper's report share ever
> shows up, it might end up storing it indefinitely, waiting for the leader
> to send a request that never arrives.
>
>> On Thu, Jan 20, 2022 at 6:19 PM Phillipp Schoppmann <
>> [email-masked]> wrote:
>>
>>> Hi everyone,
>>>

---

From: Christopher Patton <[email-masked]>
Date: Thu, 20 Jan 2022 13:24:45 -0800

Ohhh yeah that makes sense! Erik's setup seems compatible with Option #2.
The ingestor proxies would still have to speak to each other to coordinate,
but I buy that you could handle the synchronization while still reducing
egress cost. But again, not every deployment will look like this, so there
will still need to be a way in the core protocol to deal with
synchronization.

It sounds like most who have chimed in on this thread are in favor of
Option #2. I'd like to hear from those who object or have reservations.

Chris P.

On Thu, Jan 20, 2022 at 1:16 PM Erik Taubeneck <[email-masked]>
wrote:

> On Thu, Jan 20, 2022 at 11:18 AM Christopher Patton <
>> 1. It might retry later, but there's no guarantee that the helper's
>> report share will ever arrive. Eventually it'll have to give up and the
>> report will get dropped.
>> This suggests that some data loss may be inevitable in some deployments
>> of Option #2. In my own opinion, this data loss is acceptable.
>>
>> Chris P.
>>
>>
>>
>>
>>
>>
>> On Thu, Jan 20, 2022 at 9:25 AM Phillipp Schoppmann <
>>> For example, with 128 bit inputs, the theoretical lower bound of the
>>> cost is just 4128 bytes (again, excluding the verification part).
>>>
>>>>> - An "option 1" deployment could just specify one of the aggregators
>>>>> to work as the ingestor even if it isn't required by the protocol. They
>>>>> just happen to be the same party.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 20 Jan 2022 16:36:48 -0500

> example, AWS allows that to happen with S3 so long as both accounts are

Clients to ingestor replication creates many of the same challenges that
we're trying to solve with the ingestor, in particular partial availability
and replay if I'm understanding the proposal properly. At this point it's
not clear why the ingestor and aggregator need to be separate.

---

From: Erik Taubeneck <[email-masked]>
Date: Thu, 20 Jan 2022 13:46:03 -0800

> not clear why the ingestor and aggregator need to be separate.

I disagree. To me, the point of the ingestor is one of choice and
competition, and not directly one of availability. Consider the example
where a browser vendor implements an API (which is an instance of PPM.)
That browser vendor would need to select some set of aggregators, with
subsets that are trusted to not collude. At that point, if a collector
(independent of the browser vendor) is using that API, it can only select
from those approved subsets to operate as aggregators, giving those
aggregators a fair amount of power. The purpose (that I'm proposing) of the
ingestor (either run by the collector or a 3rd party of their choice) is to
limit the cost borne by the aggregators, so that collectors have as much
choice (and competition exists) in as much of such a protocol as possible.

On Thu, Jan 20, 2022 at 1:36 PM Watson Ladd <[email-masked]> wrote:

>> I don't think this is always the case (though it depends on specific
>> cloud providers), but it would require the client to at least send the
>>>>> <[email-masked]> regarding the sizes of IDPF shares, I did
>>>>> some benchmarks:
>>>>>
>>>>> On Thu, Jan 20, 2022 at 5:04 PM Charlie Harrison <
>>>>> [email-masked]> wrote:
>>>>>
>>>>>> Thanks Chris,
>>>>>>>> Great! My initial read was that it wouldn't currently enable it,
>>>>>>>> and I'm happy to work on an issue/PR that can make that more clear and
>>>>>>> Awesome! Let's start with opening an issue and folks to start
>>>>>>> putting their deployment setups there.
>>>>>>>

---

From: Tim Geoghegan <[email-masked]>
Date: Fri, 21 Jan 2022 17:40:17 -0800

I want to chime in on the question of single upload (what we spell out in
the spec today) vs. split upload (i.e., client is responsible for
separately uploading report shares to each aggregator, or a proxy for the
aggregator). In my view, there are two competing concerns to weigh:
simplicity of the client vs. the egress cost problem.

Having clients upload both report shares to the leader in one request makes
things nice and transactional: clients perform one upload and if they get
HTTP 200 OK, they are assured that the report has been stored by the leader
and so the client can discard it and move on. Also the leader can guarantee
that both report shares are available to be aggregated, because it holds
both of them. The downside is that the leader incurs egress costs when it
retransmits shares to the helper.

If the client has to upload each share to a different aggregator, though,
the transaction is messier: what happens if the upload to the leader
succeeds, but the one to the helper fails (or vice versa)? That's more
state for the client to juggle (and I think simplicity in the client is a
virtue we should aim for), but it also means the aggregators have to deal
with the possibility of the helper and leader not having the same set of
shares.

A few of us were batting this around earlier and concluded that the problem
of aggregators having disjoint views of what shares exist occurs no matter
what: even in the single upload model, we would expect that aggregators
will implement some kind of retention policy for submitted reports to stop
their storage costs from growing indefinitely. So maybe a helper discards
unaggregated shares after 14 days but its leader does so after 21. Even if
they use the same retention policy, we can't guarantee that they will
discard shares at the same moment. If a collector takes long enough to
issue a `CollectReq` (in some VDAFs like `poplar1`, the aggregate phase
cannot begin until the collector supplies the aggregation parameter, i.e.,
the candidate prefixes), then we are in the same error case that is
introduced by partial success of a split upload. That means that the PPM
protocol has to handle this error case no matter what (and we believe it
already does).

Split uploads provides a natural solution to the egress cost problem, as
explained upthread. But Erik T. raises some good points about asymmetries
in availability between aggregators, so we also want a solution that
enables one aggregator, run by an organization that doesn't flinch at
providing ninety nine nines of availability and is willing to accept egress
costs, to field all upload requests from clients. I'm against option #3
(allowing deployments to use either single or split uploads), because I
would prefer that the protocol be as simple as possible. In a split upload
model, the task parameters would have to include two different `upload`
endpoints to which clients send shares. Deployments could simply have both
upload endpoints be hosted by the same incredibly available server to spare
the other aggregator the need to scale up or attain the required uptime.

Split uploads do incur some client complexity I'd rather avoid and they do
increase the chance of upload failures (because there are two requests than
can fail instead of just one), but I think that model supports the greatest
diversity of deployments with the least complexity in the protocol

Tim Geoghegan
ISRG

On Thu, Jan 20, 2022 at 1:46 PM Erik Taubeneck <[email-masked]>
wrote:

>>>>> I think there is some optimization potential here, so the cost could
>>>>> be about half that if we use a format that just sends the raw bytes needed.
>>>>>>> I think I am in agreement with Erik that we could mitigate the
>>>>>>> issues with Option #2 if there is an ingestor client. I think framing the
>>>>>>> protocol this way actually allows close imitation of option #1 and #2
>>>>>>>
>>>>>>> - An "option 2" deployment could have the ingestor fan out reports
>>>>>>> to multiple aggregators (or ignore the ingestor completely)
>>>>>>>

---

From: Christopher Patton <[email-masked]>
Date: Fri, 21 Jan 2022 18:31:26 -0800

Thanks, Tim!

> A few of us were batting this around earlier and concluded that the
> problem of aggregators having disjoint views of what shares exist occurs no
> matter what: even in the single upload model, we would expect that
> aggregators will implement some kind of retention policy for submitted
> reports to stop their storage costs from growing indefinitely. So maybe a
> helper discards unaggregated shares after 14 days but its leader does so
> after 21. Even if they use the same retention policy, we can't guarantee
> that they will discard shares at the same moment. If a collector takes long
> enough to issue a `CollectReq` (in some VDAFs like `poplar1`, the aggregate
> phase cannot begin until the collector supplies the aggregation parameter,
> i.e., the candidate prefixes), then we are in the same error case that is

If I may try to summarize: the main downside of Option #2 is new failure
modes, but similar failure modes already exist, and we'll have to deal with
them in much the same way. I'm inclined to agree, although there is still a
possibility of solving the existing problem in a different way. I'll note
that this question is currently tracked by
https://github.com/abetterinternet/ppm-specification/issues/180. That said,
I'm inclined to agree with your analysis here.

My preference would be to take Option #2.

Hope y'all have a good weekend,
Chris P.

---

From: Christopher Wood <[email-masked]>
Date: Tue, 25 Jan 2022 11:49:08 -0800

Sorry for chiming in late here. I agree that something like Option #2 is perhaps best, assuming we spell it in such a way that an ingestion service can be accommodated without protocol changes. 

Best,
Chris

> On Jan 21, 2022, at 6:31 PM, Christopher Patton <cpatton=[email-masked]> wrote:
> 
> Thanks, Tim!
> 
>  
> A few of us were batting this around earlier and concluded that the problem of aggregators having disjoint views of what shares exist occurs no matter what: even in the single upload model, we would expect that aggregators will implement some kind of retention policy for submitted reports to stop their storage costs from growing indefinitely. So maybe a helper discards unaggregated shares after 14 days but its leader does so after 21. Even if they use the same retention policy, we can't guarantee that they will discard shares at the same moment. If a collector takes long enough to issue a `CollectReq` (in some VDAFs like `poplar1`, the aggregate phase cannot begin until the collector supplies the aggregation parameter, i.e., the candidate prefixes), then we are in the same error case that is introduced by partial success of a split upload. That means that the PPM protocol has to handle this error case no matter what (and we believe it already does).
> 
> If I may try to summarize: the main downside of Option #2 is new failure modes, but similar failure modes already exist, and we'll have to deal with them in much the same way. I'm inclined to agree, although there is still a possibility of solving the existing problem in a different way. I'll note that this question is currently tracked by https://github.com/abetterinternet/ppm-specification/issues/180. That said, I'm inclined to agree with your analysis here.
>