Recommend against min_batch_size = max_batch_size when aggregation parameters are non-trivial

[divergentdave]

It is possible that a report may pass VDAF preparation with one aggregation parameter, and later fail when prepared with another aggregation parameter. (for example, if a later correction word is corrupted in an otherwise-honestly generated Poplar1 report) We require that the same set of reports in any batch be used as input for aggregation with each aggregation parameter. The batch validation size check enforces that the number of successfully aggregated reports is at least min_batch_size. Therefore, if a deployment were to set min_batch_size equal to max_batch_size, a batch that has already been successfully collected with one aggregation parameter, and contains at least one such report, would be un-collectable with some other aggregation parameters, resulting in a loss of data, and an efficient DoS vector.

I think we should recommend that max_batch_size be strictly greater than min_batch_size for VDAFs that make use of the aggregation parameter. The other solution I can think of would be to somehow allow combining previously-collected batches (while still not allowing subdivision of batches) for subsequent collection with different aggregation parameters, but that would be a lot of complexity.

[cjpatton]

We should try to generalize this into guidance for any query type. Once collected, a batch cannot change: If X% of reports are going to be rejected, then you need to aim for a batch size that is X% larger than the minimum.

[cjpatton]

On the other hand, this is basically a Sybil attack, which DAP does not address on its own. We could consider relaxing the batch size requirement to allow a batch size smaller than the minimum after the initial collection.

[branlwyd]

Naive question: if aggregation with one aggregation parameter succeeds with a different set of reports than aggregation with a second aggregation parameter, are we sure we haven't leaked information about the reports in the delta between the two sets?

I don't think there's any generic VDAF property that guarantees we haven't leaked information, though I might be wrong.

If that's the case, perhaps we should guarantee that the same set of reports is successfully aggregated for every aggregation over the batch. However, I believe that some VDAFs would allow a maliciously-crafted report that passes aggregation with one aggregation parameter but fails aggregation with another -- i.e., an attacker could use this as a DoS vector.

[cjpatton]

@cjpatton On the other hand, this is basically a Sybil attack, which DAP does not address on its own. We could consider relaxing the batch size requirement to allow a batch size smaller than the minimum after the initial collection.

Whoops, meant to update here: Thinking on this more, this is clearly a bad idea. Given our threat model, I think we just have to include more reports in the batch than we think we need and hope that no more than we need end up being invalid. Certainly mechanisms to prevent Sybil attacks would help, but since we've ruled this out for core DAP, @divergentdave's suggestion is the most sound.

@branlwyd Naive question: if aggregation with one aggregation parameter succeeds with a different set of reports than aggregation with a second aggregation parameter, are we sure we haven't leaked information about the reports in the delta between the two sets?

I don't think there's any generic VDAF property that guarantees we haven't leaked information, though I might be wrong.

If that's the case, perhaps we should guarantee that the same set of reports is successfully aggregated for every aggregation over the batch. However, I believe that some VDAFs would allow a maliciously-crafted report that passes aggregation with one aggregation parameter but fails aggregation with another -- i.e., an attacker could use this as a DoS vector.

Great question. To crystalize this a bit: once a report is rejected, it is removed from the batch. That means if it's rejected during the first collection job, then it won't be included in the next collection job. In the case of Poplar1, we do indeed learn some information about the measurement that was rejected, since the prefix counts have changed by 1.

VADF's answer to this question is: honest Clients are perfectly capable of generating measurements that are deemed valid each time they're aggregated; dishonest Clients forfeit privacy. It would indeed be a problem if a valid measurement could be deemed invalid, exactly for the reason you describe.