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.

[wbl]

If we limit to at most 2 dimension crossing, then the biggest vector is 2,000 in the example. If we break down to 3, it's 10,000 long. For bits I agree Poplar makes sense as an alternative approach, unfortunately conversions can have amounts but then various bitslicing/rounding tricks can be used.

[AramZS]

Feedback from @tprieur and @alois-bissuel during TPA2025:

(Please confirm this is accurate and if you can please add some details per this issue)

Limited way of integrating data from the conversion in the histogram. Put as much information in the histogram as possible. Using filters with AA is possible, but it gets quickly becomes interesting on the display-side.
Charlie: You want to break up the histogram by the conversion key, as well? Is it just the function of the conversion context or also impression context?

Alois: Just coming from the conversion context is okay should be sufficient.

Charlie: Unknown whether this is already supported. Depends on how the privacy budget server is supported. Every encrypted report contains a set of keys. Requires that a single report can’t be queried more than once, but it could be okay. Feature request for the privacy budgeting service that is just not specified yet.

Don’t know: impact of the “new” user-level privacy granularity on the utility. ARA is per-click, Attribution API is per-user per-window. Unknown how it will play out in the data.
ML on aggregated data

Need to support at least GLM (incl. Logistic regression - generalized linear models). Use an aggregation service for outsourcing gradient calculation. The gradient can be expressed as a sum.

They considered learning from a noisy label proportions by taking noisy CTRs. They build a production-ready (but not used in production) using the Privacy Sandbox Aggregation service. They found not-ideal, but acceptable performance with epsilon greater than 10 on a weekly window.

They didn’t use user-level DP. Showing the two graphs. Top shows the training-loss function with DP, and the bottom is without DP. In order to perform aggregation, ... . The gradient converged within ~2 week with DP, but without DP it too much longer due to the additional variance.

MT: Histogram size: because it’s aggregated, how many features are you using?

Alois: Many optimisations. Many features including categorical. In order to balance with privacy, must reduce space. What we found, losing 1% per power-of-2.

MT: double the size of the histogram, get 1% back?

Alois: Yes

[martinthomson]

Discussion in Berlin.

Some residual concern about very large upload sizes, especially for mobile devices with limited network bandwidth or battery.

Discussion about whether the incentives of sites are going to be aligned with those of the user in terms of keeping the histogram/upload size down. There's some sense that these are loosely aligned goals, but not perfectly. Particularly when conversion measurement might occur on a different site to where the action took place. If there is value in a larger histogram, that might cause sites to request more bytes, which is in tension with their performance goals.

Some desire to look into a design for Mastic, because of its ability to handle much larger histograms, but deferring that to L2 of the API. One challenge in that API is that the encoding is one-hot, which is not entirely compatible with the current design, where multiple buckets in the histogram can be populated.

Talked about the minimum size we require browsers to support. Considered throwing if saveImpression addressed a bin larger than the limit, but that might not work if the subsequent measureConversion was able to use Mastic. Better then to throw at measureConversion time. An alternative would be to throw at saveImpression based on the maximum allowed size across all aggregation service options.