📅 Original date posted:2017-06-07
📝 Original message:On Thu, Jun 1, 2017 at 7:01 PM, Olaoluwa Osuntokun via bitcoin-dev
<bitcoin-dev at 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.
Gregory Maxwell [ARCHIVE] /
npub1f2…crwet
2023-06-07 18:02:08
in reply to nevent1q…6hh5
Author Public Key
npub1f2nvlx49er5c7sqa43src6ssyp6snd4qwvtkwm5avc2l84cs84esecrwetPublished at
2023-06-07 18:02:08Event JSON
{
"id": "299ef7dc02c544b5736cd7d413cb88eabf9c2ab597f923b411831e69032ff3c8",
"pubkey": "4aa6cf9aa5c8e98f401dac603c6a10207509b6a07317676e9d6615f3d7103d73",
"created_at": 1686160928,
"kind": 1,
"tags": [
[
"e",
"55a56c7ebba05dd9613a9ae00ae6d5bbfa4f7fd0155fa447a7d09d61ff658a4b",
"",
"root"
],
[
"e",
"15c00af1419ead8ec4cf8c72f79a0c2ef041a3d3974ea06622d96ba9ebe301b1",
"",
"reply"
],
[
"p",
"cf98d015f410ea690e93370543fcb2c3129303ca3921fd6d463206f557722518"
]
],
"content": "📅 Original date posted:2017-06-07\n📝 Original message:On Thu, Jun 1, 2017 at 7:01 PM, Olaoluwa Osuntokun via bitcoin-dev\n\u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e Hi y'all,\n\u003e\n\u003e Alex Akselrod and I would like to propose a new light client BIP for\n\u003e consideration:\n\u003e * https://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki\n\nI see the inner loop of construction and lookup are free of\nnon-constant divmod. This will result in implementations being\nneedlessly slow (especially on arm, but even on modern x86_64 a\ndivision is a 90 cycle-ish affair.)\n\nI believe this can be fixed by using this approach\nhttp://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/\n which has the same non-uniformity as mod but needs only a multiply\nand shift.\n\nOtherwise fast implementations will have to implement the code to\ncompute bit twiddling hack exact division code, which is kind of\ncomplicated. (e.g. via the technique in \"{N}-bit Unsigned Division via\n{N}-bit Multiply-Add\" by Arch D. Robison).\n\nShouldn't all cases in your spec where you have N=transactions be\nn=indexed-outputs? Otherwise, I think your golomb parameter and false\npositive rate are wrong.",
"sig": "28406f70f5d7720798f2617fb68f1223fc6010b65cf5481466b96c2b6531e1b7c0bd4d597423320a94d262a1b56431904017906d29ade163b34881efa0fc2557"
}