public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
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.


  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 [bitcoin-dev] BIP Proposal: Compact Client Side Filtering for Light Clients 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.org \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=laolu32@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
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