private-attribution / ipa

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

Use recursion factor of 4 for all proofs #1440

Closed andyleiserson closed 1 week ago

andyleiserson commented 1 week ago

Cleaned up version of #1407.

Performance was similar for recursion factors of 4 and 8. However, a recursion factor of 4 (at least for the first proof) makes it easier to implement the lookup table for Lagrange interpolation output in #1437, so that's what I've used here.

I change the calculation of proof batches to adjust downwards (rather than upwards) from the target to a power of two, so that there doesn't need to be a large margin between TARGET_PROOF_SIZE and the limit defined by MAX_PROOF_RECURSION.

I also change the names LargeProofGenerator and SmallProofGenerator to FirstProofGenerator and CompressedProofGenerator.

codecov[bot] commented 1 week ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 93.53%. Comparing base (4e0608e) to head (fa44ad0). Report is 6 commits behind head on main.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #1440 +/- ## ========================================== + Coverage 93.45% 93.53% +0.07% ========================================== Files 227 228 +1 Lines 39251 39746 +495 ========================================== + Hits 36681 37175 +494 - Misses 2570 2571 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.


🚨 Try these New Features:

andyleiserson commented 1 week ago

Draft run at aca8ca5: https://draft-mpc.vercel.app/query/view/far-image2024-11-15T2016. 2:27. This is a bit slower than the run with recursion factor of 8 (still much faster than baseline which I think is 3:25). However, it appears that this difference goes away when the additional optimization in #1437 is added. It is possible that a fully optimized implementation of λ = 8 with lookup table for Lagrange interpolation outputs would be the fastest of all implementations, but I am not sure it is worth the effort to do that right now. (I made a comparison of all the draft results here: https://docs.google.com/spreadsheets/d/1BG3DNnjb2dRzQ2VOLehKIOTn8QsYk1KkkQrZagYuWks/edit)

So I propose to take this change, and take the change to use a lookup table for Lagrange interpolation outputs of the first level proof.

andyleiserson commented 1 week ago

One more draft run at 7a7bdb1: https://draft-mpc.vercel.app/query/view/alien-fuse2024-11-16T2033, 2:23

We can also try using λ = 4 for the first proof with λ = 8 for the other proofs. I doubt it will make much of a difference, but it's an easy experiment.