search

private-attribution / ipa

A raw implementation of Interoperable Private Attribution
MIT License
40 stars 23 forks source link

IPA fails on large inputs with saturating error #1100

Open akoshelev opened 3 months ago

akoshelev commented 3 months ago

here is an example of such run

Coordinator: 2024-05-29T02:09:55.095547Z  INFO ipa_core::cli::playbook::ipa: Running IPA for 5000000 records took 4177.366415084s
Coordinator: 2024-05-29T02:09:55.104605Z  INFO report_collector: IpaQueryConfig { per_user_credit_cap: 64, max_breakdown_key: 64, attribution_window_seconds: None, num_multi_bits: 3, plaintext_match_keys: true }
Coordinator: 2024-05-29T02:09:55.104682Z  INFO ipa_core::cli::playbook: 
Coordinator: +-----+--------------+-------------+-------+
Coordinator: | Row | Expected     | Actual      | Diff? |
Coordinator: +==========================================+
Coordinator: | 0   | Some(106989) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 1   | Some(105657) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 2   | Some(105677) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 3   | Some(105051) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 4   | Some(106799) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 5   | Some(106926) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 6   | Some(104752) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 7   | Some(104977) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 8   | Some(104764) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 9   | Some(104801) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 10  | Some(104571) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 11  | Some(106523) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 12  | Some(105573) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 13  | Some(104639) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 14  | Some(104887) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 15  | Some(106892) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 16  | Some(104394) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 17  | Some(107038) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 18  | Some(103433) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 19  | Some(105431) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 20  | Some(104720) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 21  | Some(106623) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 22  | Some(106353) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 23  | Some(104670) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 24  | Some(104863) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 25  | Some(106054) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 26  | Some(105873) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 27  | Some(104947) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 28  | Some(104581) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 29  | Some(106903) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 30  | Some(105189) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 31  | Some(104976) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 32  | Some(106442) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 33  | Some(105882) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 34  | Some(104468) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 35  | Some(105692) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 36  | Some(105371) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 37  | Some(104191) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 38  | Some(105768) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 39  | Some(104475) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 40  | Some(106157) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 41  | Some(106300) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 42  | Some(104251) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 43  | Some(104853) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 44  | Some(104275) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 45  | Some(105477) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 46  | Some(105043) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 47  | Some(105353) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 48  | Some(105133) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 49  | Some(105448) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 50  | Some(105972) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 51  | Some(103884) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 52  | Some(104220) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 53  | Some(104569) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 54  | Some(103768) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 55  | Some(104172) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 56  | Some(104006) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 57  | Some(104970) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 58  | Some(105050) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 59  | Some(105561) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 60  | Some(104202) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 61  | Some(104338) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 62  | Some(102706) | Some(65535) | X     |
Coordinator: |-----+--------------+-------------+-------|
Coordinator: | 63  | Some(105328) | Some(65535) | X     |
Coordinator: +-----+--------------+-------------+-------+

if number of input rows is large enough, the container type for breakdown key is too small to account for the sum of all values.

andyleiserson commented 3 months ago

The test data generator has a conversion probability parameter that defaults to 2%, but it looks like it's only used when generating all trigger events (ReportFilter::TriggerOnly). Possibly that is a bug?

akoshelev commented 3 months ago

Possibly that is a bug?

yea it looks like a bug to me, possibly not related to this one as we seem to be running out of space for HV not being large enough to account for degenerate use cases. We could say that we don't support more than 16 bits for HV, but then we need to fix our test in the clear

akoshelev commented 2 months ago

Discussed with @danielmasny - the approach of keeping an overflow bit is relatively straightforward to think about. Just keep the carry bit (secret shared) after the addition operation reaches the HV boundary. To properly set the overflow bit to 1, we need to OR all the carry bits obtained from the additions occurred after the overflow. This will require communication as OR gate cannot be represented by using XOR only

$A \lor B = (A \oplus B) \oplus (A \wedge B)$

So that will cost us an extra multiplication which is an extra 6% communication overhead. Not bad, but the aggregation code may need to significantly change to account for it. Using the appropriate channel, separating the overflow bit from value bits, etc.

danielmasny commented 2 months ago

I think it could be done relatively straightforwardly by using 15 of the 16 bits for storing the actual value and the 16th bit for the overflow. We could implement another integer_add which includes the computation and storage of the overflow bit when adding two values.