tari-project / bulletproofs-plus / 5961033173

98%

push

github

feat: compute verifier challenge sum more efficiently (#59)

As part of proof verification, the verifier must compute the sum of
consecutive nonzero powers of one of the Fiat-Shamir challenges.
Currently, this is done naively by iteratively computing powers and
adding them into an accumulator. Because the number of powers is equal
to the product of the bit length and aggregation factor, this is
nontrivial.

The computation can be made far more efficient. Because the sum of
powers is a partial sum of a geometric series, it can be computed using
[a well-known
formula](https://mathworld.wolfram.com/GeometricSeries.html) (which is
already used elsewhere in the verifier).

The change requires computation of an additional scalar inverse. As part
of the optimization, all scalar inversions performed by the verifier are
now included in a single batch operation per proof, which is more
efficient.

Documentation is also updated to reflect the efficiency gain.

Overall, the result is an impressive improvement in verification. A
single 64-bit range proof now verifies 7% faster.

12 of 12 new or added lines in 1 file covered. (100.0%)

2121 of 2174 relevant lines covered (97.56%)

429.88 hits per line