Prio benchmarks and communication cost

[csharrison]

It would be good to have a table for various parameter settings of Prio (vector size, domain size, etc.) along with

• Message size overhead
• Some measure of computation cost for that parameterization for aggregating N vectors

This will help us in two major ways:

1. It can help us determine whether e.g. something like domain size should be a parameter we expose to callers (e.g. to reduce their message sizes in an opt-in way)
2. It can help users of the system understand the implication to emitting large histograms

In both cases, having "rules of thumb" for these would be great as a way of efficiently communicating the resource constraints to API callers.

cc @schoppmp @bmcase

[martinthomson]

My position here is that sites can probably make whatever call they like about the size of the domain up to a point.

Browsers should probably set a baseline security margin for each requests, which means setting the number of bits in the field to some function of the L1 bound and number of buckets (from memory, the margin is roughly fieldSizeBits - l1BoundBits - log2(buckets + 1) - 1). But the consequence of having too little margin is that the odds of someone being able to spoil an aggregate increases.

If sites are willing to tolerate some risk, they can ask that the browser use a smaller field, probably up to some lower bound. I would suggest that 20 bits of margin is pretty weak, but don't have a problem with setting a lower margin as the floor.

The only problem with having a lower margin is that you start to get to the point that there is a risk of wrapping the results. Again, sites can manage that risk. Following the above approximation, if your margin is just 10 bits and you have 16 buckets, you only need 30k measurements to put their maximum value in the same bucket and you get close to wrapping, especially with noise added. If we let sites do that, we should mention this risk, but that gets pretty theoretical if the baseline margin is higher (you need many million conversions in the same aggregation once you have a 20 bit security margin).

[bmcase]

+1 to gathering a table of these parameter settings for Prio. I have a doc with some parameters I think would be interesting to include but welcome any input on that.

cc some PPM folks who likely already have an understanding of many of these or would know best how to evaluate them @tgeoghegan @jcjones @divergentdave @cjpatton

[cjpatton]

There are two parameters not listed in the doc that impact performance and I think are worth playing around with:

1. The default field for the Prio3SumVec and Prio3L1BoundSum is Field128, which is 16 bytes per field element. You should consider using Field64, which is 8 bytes per field element. Note that you would need to bump PROOFS to 3 to get the same security level, but this trade-off pays off for large enough vectors. (You could also consider PROOFS == 2, but I would worry somewhat about robustness.)

2. The size of the proof is determined in part by the chunk_length parameter. The asymptotically optimal value is $O(\sqrt{n})$, where $n$ is the input size, but concretely, the best choice depends on $n$. It's worth playing around to find out. @divergentdave once had a script for this.

Also, remember that the length of the input vector is linear in the number of bins of your histogram. From a communication stand point, this will be the highest cost. If the vectors are sparse, then for sufficiently large vectors, it'll be more efficient to use one or more IDPFs (as in Poplar1 or Mastic) to represent the vector. This means more computation on the server side, but it will reduce the size of the input vector to $O(\log n)$. Note that we're no longer talking about Prio: you would essentially have a new VDAF that combines an IDPF with an FLP to prove validity of the expanded input vector.

[bmcase]

@cjpatton Thanks! It sounds like especially for the field size and number of proofs it would be good to do collect a couple different options in this evaluation. If we already know how to find an optimal chunk_length for a given n, then we should should probably just always calculate and use the optimal chunk_length for the set of parameters we are evaluating and don't need to explicitly consider it as a parameter to vary in the analysis.

[wbl]

I think regrettably these vectors are way too short. If we want to track conversions across 100 creatives, broken to 20 cities, with 4 publishers, and 5 distinct kinds of conversion action that comes out to 20,000. And that's a small number of fully broken down things. If we want to avoid complete drill downs to make multiple smaller vectors, that probably has implications.

[martinthomson]

That's a comment we've received a few times already. I continue to assert that measuring multiple times, looking at each dimension independently is a viable alternative. It's not perfect, because you'd lose information about the interaction across different axes, but the cost is much less (as is the noise).

Some amount of discretionary combining of axes could let you learn about any interactions (publisher X is good in city Y, but bad in city Z, for example). I know that this is not great for optimization, which seems to want individual data points.

There's a version of this (perhaps with Mastic) that goes to one histogram bucket per ad placement. Then you have built an expensive version of event-level ARA.

[cjpatton]

I think regrettably these vectors are way too short. If we want to track conversions across 100 creatives, broken to 20 cities, with 4 publishers, and 5 distinct kinds of conversion action that comes out to 20,000. And that's a small number of fully broken down things. If we want to avoid complete drill downs to make multiple smaller vectors, that probably has implications.

DPFs would provide a substantial improvement here.

To use Mastic or Poplar for this, you would pick an encoding of your attributes as a bit vector. Let's take the most straightforward encoding for each, which is the number of bits for each category. That is, $\Sigma_{v\in A} \lceil \log_2 v \rceil = 17$ where $A=\{100, 20, 4, 5\}$.

Here's the size in bytes of the various messages (input shares are sent to individual Aggregators; public share is sent to both):

• Poplar1(17):
  • len(public_share) = 597
  • len(input_share_0) = 368
  • len(input_share_1) = 368
• MasticCount(17):
  • len(public_share) = 1093
  • len(input_share_0) = 56
  • len(input_share_1) = 48

Source: https://github.com/jimouris/draft-mouris-cfrg-mastic/blob/main/poc/examples.py

For comparison, let's take Prio3Histogram with the smallest possible vector size, which would be $\Pi_{v\in A} v = 40000$:

• Prio3Histogram(2, 40000, 200) (2 is the number of shares, and 200 is the chunk length)`
  • len(public_share) = 64
  • len(input_share_0) = 654608
  • len(input_share_1) = 64

Source: https://github.com/divviup/libprio-rs/blob/main/binaries/src/bin/vdaf_message_sizes.rs

Note: this can improved be roughly a factor of 2 by reducing the size of the finite field.