On Thu, Jun 1, 2017 at 7:01 PM, Olaoluwa Osuntokun via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi y'all, > > Alex Akselrod and I would like to propose a new light client BIP for > consideration: > * https://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki
I see the inner loop of construction and lookup are free of non-constant divmod. This will result in implementations being needlessly slow (especially on arm, but even on modern x86_64 a division is a 90 cycle-ish affair.) I believe this can be fixed by using this approach http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ which has the same non-uniformity as mod but needs only a multiply and shift. Otherwise fast implementations will have to implement the code to compute bit twiddling hack exact division code, which is kind of complicated. (e.g. via the technique in "{N}-bit Unsigned Division via {N}-bit Multiply-Add" by Arch D. Robison). Shouldn't all cases in your spec where you have N=transactions be n=indexed-outputs? Otherwise, I think your golomb parameter and false positive rate are wrong. _______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev