search

cargodog / arcturus

A pure rust implementation of Arcturus proofs for confidential transactions.
MIT License
12 stars 2 forks source link

tell_size() hack causes suboptimal multiscalar multiplication #24

Closed cargodog closed 3 years ago

cargodog commented 3 years ago

Since multiscalar multiplication requires ExactSized iterators, but that trait does not work well, I added a hack tell_size(0) trait to override the size hint checks within the multiscalar_mult() implementation. Unfortunately, this hack causes multiscalar_mult() to always choose the Straus algorithm and never the Pippenger algorithm for multiscalar multiplication see here.

This can have a serious performance penalty for proofs over large rings. Pippenger claims >40% improvement for certain proofs with >190 point multiplications to perform. I suspect even greater improvement for Arcuturus proofs, as a proof may easily exceed 190 multiplications by several orders of magnitude.

cargodog commented 3 years ago

Since https://github.com/cargodog/arcturus/commit/33c12709b8538a76809b93ceca97dd64144a3335, tell_size() should no longer be needed, as all iterators are derived from slices, and thus have known size. For some reason, the size calculations are still broken, so I dug in to find exactly why.

The issue appears to be that flatten() breaks size_hint(). I've logged an issue upstream. Hopefully it is a simple mistake on my end, and not a bug with flatten(). https://github.com/rust-lang/rust/issues/81001

cargodog commented 3 years ago

As mentioned in the above issue, the issue is not that flatten() "breaks" size_hint(), but that map() depends on a closure, which cannot have known size until the closure is executed.

I think the only way to work around this is to collect the iterators into a container, which would force the closures to execute. The result would be a container with known size. Unfortunately, these containers could be quite large, so I need to think about the trade-offs here.

An alternative would be to use tell_size() with an accurate size. Again... trade-offs to consider.