MIME-Version: 1.0
Sender: gmaxwell@gmail.com
In-Reply-To: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
References: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
From: Gregory Maxwell <greg@xiph.org>
Date: Wed, 7 Jun 2017 21:41:36 +0000
Message-ID: <CAAS2fgRVTfsfXAyHBoBaCqAXpK+=QCFy-Lx3zH=d3tPteu7GcA@mail.gmail.com>
To: Olaoluwa Osuntokun <laolu32@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Cc: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP Proposal: Compact Client Side Filtering for
 Light Clients
Precedence: list

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.