romac
commented
6 years ago Wow, that's great work, thank you so much!
These performance improvements are very welcome, as the previous implementation was pretty much useless for "big" secrets (eg. > 2MB) because of its slowness.
I have merged this manually, and got rid of the old interpolation method, because the absolute performance improvement for k < 5 did not seem big enough to warrant keeping the old code around, but thanks for being so thorough and paying such close attention to detail :)
Previously the tests in the lagrange module were allowed to pass nodes to the interpolation algorithms with x = 0. Genuine shares will not be evaluated at x = 0, since then they would just be the secret, so:
Now nodes in tests start at x = 1 like scheme::secret_share deals them out. I have added assert statements to reinforce this fact and guard against division by 0 panics.
This meant getting rid of the evaluate_at_works test, but interpolate_evaluate_at_0_eq_evaluate_at provides a similar test.
Good point!
A couple more interesting things to note about barycentric weights:
- Barycentric weights can be partially computed if less than threshold shares are present. When additional shares come in, computation can resume with no penalty to the total runtime.
- They can be determined totally independently from the y values of our points, and the x value we want to evaluate for. We only need to know the x values of our interpolation points.
That is very interesting indeed! Let's keep this in mind if we see good use case for it on the Sunder/CLI side.
Implements barycentric Lagrange interpolation. Uses algorithm (3.1) from the paper "Polynomial Interpolation: Langrange vs Newton" by Wilhelm Werner to find the barycentric weights, and then evaluates at
Gf256::zero()using the second or "true" form of the barycentric interpolation formula.I also earlier implemented a variant of this algorithm, Algorithm 2, from "A new efficient algorithm for polynomial interpolation," which uses less total operations than Werner's version, however, because it uses a lot more multiplications or divisions (depending on how you choose to write it), it runs slower given the running time of subtraction/ addition (equal) vs multiplication, and especially division in the Gf256 module.
The new algorithm takes n^2 / 2 divisions and n^2 subtractions to calculate the barycentric weights, and another n divisions, n multiplications, and 2n additions to evaluate the polynomial*. The old algorithm runs in n^2 - n divisions, n^2 multiplications, and n^2 subtractions. Without knowing the exact running time of each of these operations, we can't say for sure, but I think a good guess would be the new algorithm trends toward about 1/3 running time as n -> infinity. It's also easy to see theoretically that for small n the original lagrange algorithm is faster. This is backed up by benchmarks, which showed for n >= 5, the new algorithm is faster. We can see that this is more or less what we should expect given the running times in n of these algorithms.
To ensure we always run the faster algorithm, I've kept both versions and only use the new one when 5 or more points are given.
Previously the tests in the lagrange module were allowed to pass nodes to the interpolation algorithms with x = 0. Genuine shares will not be evaluated at x = 0, since then they would just be the secret, so:
scheme::secret_sharedeals them out.This meant getting rid of the
evaluate_at_workstest, butinterpolate_evaluate_at_0_eq_evaluate_atprovides a similar test.Further work will include the use of barycentric weights in the
interpolatefunction.A couple more interesting things to note about barycentric weights: