The first implementation of ArcturusGens::prove() & ArcturusGens::verify() operates on the ring as an iterator of members. This was to allow flexibility to the caller, in-case the ring was not stored in a contiguous array (e.g. an iterator of references to outputs in blocks of a blockchain). Unfortunately, because the ExactSizeIterator is broken, this has led to some ugly hacks (1, 2).
Furthermore, lack of ExactSizeIterator makes parallelization very inefficient. It may be desirable to break up proof generation or verification into K small pieces to be processed in parallel. In the current design, this would require breaking the ring iterator (and any iterators derived from it) into K sub iterators. Unfortunately, since ExactSizeIterator is not functioning, this requires cloning the iterator and evaluating it N/K times to create the next sub iterator. This is very expensive, as some of the iterators involve very expensive mathematics.
Given these issues, I would like to redesign this interface to require the ring argument to be a slice. This will solve both of the above problems, because slices always have exactly known size. This will be a breaking change, and will restrict the caller somewhat, but the IMO the benefits justify the change.
The first implementation of
ArcturusGens::prove()
&ArcturusGens::verify()
operates on the ring as an iterator of members. This was to allow flexibility to the caller, in-case the ring was not stored in a contiguous array (e.g. an iterator of references to outputs in blocks of a blockchain). Unfortunately, because theExactSizeIterator
is broken, this has led to some ugly hacks (1, 2).Furthermore, lack of
ExactSizeIterator
makes parallelization very inefficient. It may be desirable to break up proof generation or verification intoK
small pieces to be processed in parallel. In the current design, this would require breaking the ring iterator (and any iterators derived from it) intoK
sub iterators. Unfortunately, sinceExactSizeIterator
is not functioning, this requires cloning the iterator and evaluating itN/K
times to create the next sub iterator. This is very expensive, as some of the iterators involve very expensive mathematics.Given these issues, I would like to redesign this interface to require the
ring
argument to be a slice. This will solve both of the above problems, because slices always have exactly known size. This will be a breaking change, and will restrict the caller somewhat, but the IMO the benefits justify the change.