search

tari-project / triptych

BSD 3-Clause "New" or "Revised" License
0 stars 3 forks source link

feat: use precomputation on input set keys #69

Closed AaronFeickert closed 2 months ago

AaronFeickert commented 5 months ago

The curve library supports precomputation, which allows us to evaluate multiscalar multiplication operations using both fixed and dynamic values. This means we can generate precomputation tables for input set keys in advance, and use them when generating and verifying proofs.

This PR adds such functionality. However, it surprisingly results in no efficiency benefit (and possibly even an efficiency regression); this is unclear and could use some digging.

Keeping this open as a draft in case a solution is found.

AaronFeickert commented 5 months ago

I also tested using an Rc instead of an Arc to store the precomputed values, in case this made a difference. It did not!

AaronFeickert commented 2 months ago

It looks like the underlying cause is that the curve library functionality for precomputation becomes less efficient than simply doing a variable-time multiscalar multiplication evaluation after about 1000 points.

Since input set sizes shouldn't be relied on to be any particular size, closing this.