📅 Original date posted:2017-01-03
📝 Original message:I believe the filter can be more compact than this, but even if not an
order of magnitude saving of disk space is still significant.
On 2016-05-11 13:29, Bob McElrath wrote:
> Eerrrr....let me revise that last paragraph. That's 12 *GB* of filters
> at
> today's block height (at fixed false-positive rate 1e-6. Compared to
> block
> headers only which are about 33 MB today. So this proposal is not
> really
> compatible with such a wallet being "light"...
>
> Damn units...
>
> Bob McElrath via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org]
> wrote:
>> I like this idea, but let's run some numbers...
>>
>> bfd--- via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
>> > A Bloom Filter Digest is deterministically created of every block
>>
>> Bloom filters completely obfuscate the required size of the filter for
>> a desired
>> false-positive rate. But, an optimal filter is linear in the number
>> of elements
>> it contains for fixed false-positive rate, and logarithmic in the
>> false-positive
>> rate. (This comment applies to a RLL encoded Bloom filter Greg
>> mentioned, but
>> that's not the only way) That is for N elements and false positive
>> rate
>> \epsilon:
>>
>> filter size = - N \log_2 \epsilon
>>
>> Given that the data that would be put into this particular filter is
>> *already*
>> hashed, it makes more sense and is faster to use a Cuckoo[1] filter,
>> choosing a
>> fixed false-positive rate, given expected wallet sizes. For Bloom
>> filters,
>> multiply the above formula by 1.44.
>>
>> To prevent light clients from downloading more blocks than necessary,
>> the
>> false-positive rate should be roughly less than 1/(block height). If
>> we take
>> the false positive rate to be 1e-6 for today's block height ~ 410000,
>> this is
>> about 20 bits per element. So for todays block's, this is a 30kb
>> filter, for a
>> 3% increase in block size, if blocks commit to the filter. Thus the
>> required
>> size of the filter commitment is roughly:
>>
>> filter size = N \log_2 H
>>
>> where H is the block height. If bitcoin had these filters from the
>> beginning, a
>> light client today would have to download about 12MB of data in
>> filters. My
>> personal SPV wallet is using 31MB currently. It's not clear this is a
>> bandwidth
>> win, though it's definitely a win for computing load on full nodes.
>>
>>
>> [1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
>>
>> --
>> Cheers, Bob McElrath
>>
>> "For every complex problem, there is a solution that is simple, neat,
>> and wrong."
>> -- H. L. Mencken
>>
>>
>>
>> !DSPAM:5733934b206851108912031!
>
>
>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>> !DSPAM:5733934b206851108912031!
>
> --
> Cheers, Bob McElrath
>
> "For every complex problem, there is a solution that is simple, neat,
> and wrong."
> -- H. L. Mencken
bfd at cock.lu [ARCHIVE] /
npub1md…gy6y7
2023-06-07 17:55:12
in reply to nevent1q…54qy
Author Public Key
npub1mdmqmt0prpddcexkljfzd40uf7nvrc56c7gsg2spn3lgcjghguxqwgy6y7Published at
2023-06-07 17:55:12Event JSON
{
"id": "50e61d48bea9758430a8386832efd0ba69588120841c660d1afdcf5733bc56af",
"pubkey": "db760dade1185adc64d6fc9226d5fc4fa6c1e29ac791042a019c7e8c4917470c",
"created_at": 1686160512,
"kind": 1,
"tags": [
[
"e",
"12de089a3e4ccbe31128a134586c26b5a984bf25231ca8b54e0116dac53ecb14",
"",
"root"
],
[
"e",
"350ee62a9abb327136fc44e96c149d514116ba52f9b89eb15bae63ba75205882",
"",
"reply"
],
[
"p",
"db760dade1185adc64d6fc9226d5fc4fa6c1e29ac791042a019c7e8c4917470c"
]
],
"content": "📅 Original date posted:2017-01-03\n📝 Original message:I believe the filter can be more compact than this, but even if not an\norder of magnitude saving of disk space is still significant.\n\n\nOn 2016-05-11 13:29, Bob McElrath wrote:\n\u003e Eerrrr....let me revise that last paragraph. That's 12 *GB* of filters \n\u003e at\n\u003e today's block height (at fixed false-positive rate 1e-6. Compared to \n\u003e block\n\u003e headers only which are about 33 MB today. So this proposal is not \n\u003e really\n\u003e compatible with such a wallet being \"light\"...\n\u003e \n\u003e Damn units...\n\u003e \n\u003e Bob McElrath via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] \n\u003e wrote:\n\u003e\u003e I like this idea, but let's run some numbers...\n\u003e\u003e \n\u003e\u003e bfd--- via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:\n\u003e\u003e \u003e A Bloom Filter Digest is deterministically created of every block\n\u003e\u003e \n\u003e\u003e Bloom filters completely obfuscate the required size of the filter for \n\u003e\u003e a desired\n\u003e\u003e false-positive rate. But, an optimal filter is linear in the number \n\u003e\u003e of elements\n\u003e\u003e it contains for fixed false-positive rate, and logarithmic in the \n\u003e\u003e false-positive\n\u003e\u003e rate. (This comment applies to a RLL encoded Bloom filter Greg \n\u003e\u003e mentioned, but\n\u003e\u003e that's not the only way) That is for N elements and false positive \n\u003e\u003e rate\n\u003e\u003e \\epsilon:\n\u003e\u003e \n\u003e\u003e filter size = - N \\log_2 \\epsilon\n\u003e\u003e \n\u003e\u003e Given that the data that would be put into this particular filter is \n\u003e\u003e *already*\n\u003e\u003e hashed, it makes more sense and is faster to use a Cuckoo[1] filter, \n\u003e\u003e choosing a\n\u003e\u003e fixed false-positive rate, given expected wallet sizes. For Bloom \n\u003e\u003e filters,\n\u003e\u003e multiply the above formula by 1.44.\n\u003e\u003e \n\u003e\u003e To prevent light clients from downloading more blocks than necessary, \n\u003e\u003e the\n\u003e\u003e false-positive rate should be roughly less than 1/(block height). If \n\u003e\u003e we take\n\u003e\u003e the false positive rate to be 1e-6 for today's block height ~ 410000, \n\u003e\u003e this is\n\u003e\u003e about 20 bits per element. So for todays block's, this is a 30kb \n\u003e\u003e filter, for a\n\u003e\u003e 3% increase in block size, if blocks commit to the filter. Thus the \n\u003e\u003e required\n\u003e\u003e size of the filter commitment is roughly:\n\u003e\u003e \n\u003e\u003e filter size = N \\log_2 H\n\u003e\u003e \n\u003e\u003e where H is the block height. If bitcoin had these filters from the \n\u003e\u003e beginning, a\n\u003e\u003e light client today would have to download about 12MB of data in \n\u003e\u003e filters. My\n\u003e\u003e personal SPV wallet is using 31MB currently. It's not clear this is a \n\u003e\u003e bandwidth\n\u003e\u003e win, though it's definitely a win for computing load on full nodes.\n\u003e\u003e \n\u003e\u003e \n\u003e\u003e [1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf\n\u003e\u003e \n\u003e\u003e --\n\u003e\u003e Cheers, Bob McElrath\n\u003e\u003e \n\u003e\u003e \"For every complex problem, there is a solution that is simple, neat, \n\u003e\u003e and wrong.\"\n\u003e\u003e -- H. L. Mencken\n\u003e\u003e \n\u003e\u003e \n\u003e\u003e \n\u003e\u003e !DSPAM:5733934b206851108912031!\n\u003e \n\u003e \n\u003e \n\u003e\u003e _______________________________________________\n\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e \n\u003e\u003e \n\u003e\u003e !DSPAM:5733934b206851108912031!\n\u003e \n\u003e --\n\u003e Cheers, Bob McElrath\n\u003e \n\u003e \"For every complex problem, there is a solution that is simple, neat,\n\u003e and wrong.\"\n\u003e -- H. L. Mencken",
"sig": "a05515822122145d284c6b988f3b5f628a98a65bc68069ffb0a2032cc92fa4f4ec578255670edd8619a7f5dda8c8ebc342a4bed90b521b33eda35e1d32532f01"
}