From: Gregory Maxwell <greg@xiph•org>
To: Olaoluwa Osuntokun <laolu32@gmail•com>
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
Date: Wed, 7 Jun 2017 21:41:36 +0000 [thread overview]
Message-ID: <CAAS2fgRVTfsfXAyHBoBaCqAXpK+=QCFy-Lx3zH=d3tPteu7GcA@mail.gmail.com> (raw)
In-Reply-To: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
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.
next prev parent reply other threads:[~2017-06-07 21:41 UTC|newest]
Thread overview: 39+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-06-01 19:01 Olaoluwa Osuntokun
2017-06-01 21:00 ` Eric Lombrozo
2017-06-01 21:33 ` Matt Corallo
2017-06-01 22:10 ` Olaoluwa Osuntokun
2017-06-02 2:15 ` Chris
2017-06-02 2:28 ` Gregory Maxwell
2017-06-02 3:35 ` Alex Akselrod
2017-06-02 16:07 ` Chris Pacia
2017-06-02 4:49 ` Olaoluwa Osuntokun
2017-06-09 3:59 ` Olaoluwa Osuntokun
2017-11-09 23:44 ` Olaoluwa Osuntokun
2017-06-02 6:00 ` Karl Johan Alm
[not found] ` <CAE0pnx+RRAP269VeWAcxKbrcS9qX4LS8_6nY_js8X5NtQ22t_A@mail.gmail.com>
[not found] ` <CAE0pnxLKYnwHnktTqW949s1AA9uK=6WnVYWmRoau8B1SszzYEg@mail.gmail.com>
[not found] ` <CAE0pnxJxHYQ4+2pt3tt=1WZ0-K0vDxGB4KBXY+R=WfktMmATwA@mail.gmail.com>
2017-06-02 17:55 ` Alex Akselrod
2017-06-05 2:06 ` Karl Johan Alm
2017-06-09 3:03 ` Olaoluwa Osuntokun
2017-06-07 21:41 ` Gregory Maxwell [this message]
2017-06-09 3:42 ` Olaoluwa Osuntokun
2017-06-09 4:47 ` Olaoluwa Osuntokun
2017-06-08 9:50 ` Tomas
2017-06-09 3:50 ` Olaoluwa Osuntokun
2017-06-09 8:26 ` Tomas
2017-06-19 11:58 ` Andreas Schildbach
2017-06-19 12:26 ` bfd
2017-06-19 15:15 ` Tom Zander
2017-06-19 15:49 ` Jonas Schnelli
2017-06-19 15:59 ` Andreas Schildbach
2017-06-19 16:22 ` Jonas Schnelli
2017-06-19 16:36 ` adiabat
2017-06-19 20:49 ` Andreas Schildbach
2017-06-20 7:03 ` Eric Voskuil
2017-06-19 16:07 ` Tom Zander
2017-06-19 16:30 ` Jonas Schnelli
2017-06-19 16:38 ` Tom Zander
2017-06-19 15:43 ` Andreas Schildbach
2017-06-19 16:10 ` Jonas Schnelli
2017-06-19 22:41 ` Gregory Maxwell
2017-06-20 9:52 ` Tom Zander
2017-06-20 13:08 ` bfd
2017-06-20 17:20 ` Adam Back
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAAS2fgRVTfsfXAyHBoBaCqAXpK+=QCFy-Lx3zH=d3tPteu7GcA@mail.gmail.com' \
--to=greg@xiph$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=laolu32@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox