search

private-attribution / ipa

A raw implementation of Interoperable Private Attribution
MIT License
42 stars 25 forks source link

Malicious IPA takes 14x longer to finish on large inputs than semi-honest implementation #1354

Open akoshelev opened 1 week ago

akoshelev commented 1 week ago

For small inputs (< 5M) we observed malicious implementation to be within 10% from semi-honest. However, as the input size grows, the difference becomes more and more noticeable. At 25M it becomes extreme

Semi-honest runtime Malicious runtime Difference
1 hr 14,5 hrs 14x
akoshelev commented 1 week ago

@andyleiserson pointed out that we spent the majority of the time in breakdown reveal aggregation

2024-10-14T21:54:41.371120 - 2024-10-14T21:54:41.371054Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 67103744 multiplications
2024-10-14T21:57:36.048696 - 2024-10-14T21:57:36.048629Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 134207488 multiplications
2024-10-14T22:01:49.456526 - 2024-10-14T22:01:49.456460Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 201311232 multiplications
2024-10-14T22:07:21.850994 - 2024-10-14T22:07:21.850909Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 268414976 multiplications
2024-10-14T22:14:12.626203 - 2024-10-14T22:14:12.626120Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 335518720 multiplications
2024-10-14T22:22:22.328127 - 2024-10-14T22:22:22.328057Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 402622464 multiplications
2024-10-14T22:31:50.003549 - 2024-10-14T22:31:50.003479Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 469726208 multiplications
2024-10-14T22:42:36.610152 - 2024-10-14T22:42:36.610074Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 536829952 multiplications
2024-10-14T22:54:41.165647 - 2024-10-14T22:54:41.165569Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 603933696 multiplications
2024-10-14T23:08:04.353133 - 2024-10-14T23:08:04.353058Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 671037440 multiplications
2024-10-14T23:22:46.196891 - 2024-10-14T23:22:46.196817Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 738141184 multiplications
2024-10-14T23:38:46.607207 - 2024-10-14T23:38:46.607140Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 805244928 multiplications
2024-10-14T23:56:05.290890 - 2024-10-14T23:56:05.290815Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 872348672 multiplications
2024-10-15T00:14:43.065684 - 2024-10-15T00:14:43.065612Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 939452416 multiplications
2024-10-15T00:34:39.091368 - 2024-10-15T00:34:39.091286Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1006556160 multiplications
2024-10-15T00:55:53.212394 - 2024-10-15T00:55:53.212324Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1073659904 multiplications
2024-10-15T01:18:26.944136 - 2024-10-15T01:18:26.944075Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1140763648 multiplications
2024-10-15T01:42:20.084730 - 2024-10-15T01:42:20.084670Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1207867392 multiplications
2024-10-15T02:07:30.988207 - 2024-10-15T02:07:30.988146Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1274971136 multiplications
2024-10-15T02:34:00.151183 - 2024-10-15T02:34:00.151113Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1342074880 multiplications
2024-10-15T03:01:48.366203 - 2024-10-15T03:01:48.366131Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1409178624 multiplications
2024-10-15T03:30:54.250196 - 2024-10-15T03:30:54.250115Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1476282368 multiplications
2024-10-15T04:01:18.512687 - 2024-10-15T04:01:18.512613Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1543386112 multiplications
2024-10-15T04:33:02.758926 - 2024-10-15T04:33:02.758847Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1610489856 multiplications
2024-10-15T05:06:04.489836 - 2024-10-15T05:06:04.489764Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1677593600 multiplications
2024-10-15T05:40:24.330067 - 2024-10-15T05:40:24.329986Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1744697344 multiplications
2024-10-15T06:16:03.717829 - 2024-10-15T06:16:03.717763Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1811801088 multiplications
2024-10-15T06:53:00.782534 - 2024-10-15T06:53:00.782464Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1878904832 multiplications
2024-10-15T07:31:16.630685 - 2024-10-15T07:31:16.630611Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 1946008576 multiplications
2024-10-15T08:10:50.850043 - 2024-10-15T08:10:50.849968Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 2013112320 multiplications
2024-10-15T08:51:43.785105 - 2024-10-15T08:51:43.785035Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 2080216064 multiplications
2024-10-15T09:33:54.577989 - 2024-10-15T09:33:54.577915Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 2147319808 multiplications
2024-10-15T10:16:11.487852 - 2024-10-15T10:16:11.487782Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 2162031872 multiplications
2024-10-15T10:20:04.704548 - 2024-10-15T10:20:04.704514Z  INFO oprf_ipa_query{sz=25000000}:attribute_cap_aggregate:breakdown_reveal_aggregation{total=20455893}: ipa_core::protocol::context::dzkp_validator: validating 524288 multiplications

2_147_319_808 multiplications is quite a lot to process

andyleiserson commented 1 week ago

1355 fixes the issue with proof batching in breakdown reveal aggregation and reduces the overhead for malicious IPA to ~3x.