Skip to content
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Commit 18a7f4f

Browse files
committedNov 7, 2014
Move example down, where it makes more sense.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
1 parent ecfd749 commit 18a7f4f

1 file changed

+38
-34
lines changed
 

‎_posts/2014-11-05-Playing-with-invertible-bloom-lookup-tables-and-bitcoin-transactions.md

+38-34
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,43 @@ those, you might find more buckets now have 1 thing in them, etc. The
2121
[paper](http://arxiv.org/pdf/1101.2245.pdf) is worth reading, but this
2222
should give you the idea.
2323

24-
Here's a simplified example. Consider the following buckets:
24+
### Subtracting IBLTs ###
25+
26+
The clever bit comes by realizing that if I create an IBLT with
27+
everything in my set, and you create an IBLT with everything in your
28+
set, it's trivial to subtract my IBLT from your IBLT and get an IBLT
29+
of the set differences. Which is great, because all bloom filters
30+
become useless when they clog up, but if our sets are very similar,
31+
the subtraction result gives a nice sparse IBLT. And
32+
[here's the paper](http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf).
33+
34+
<a name="Using-IBLTs"></a>
35+
36+
## Using IBLTs for Bitcoin ##
37+
38+
([Skip if you're familiar with Gavin's IBLT proposal](#Testing-IBLTs))
39+
40+
Gavin suggested some ways to adapt an IBLT to the blockchain problem:
41+
42+
1. Set a size of 1M for the whole thing.
43+
2. Make each IBLT bucket look like this
44+
45+
struct entry {
46+
u32 count;
47+
struct keySum {
48+
u8 id[6];
49+
u16 index;
50+
u8 frag[8];
51+
} key;
52+
}
53+
54+
This gives 52428 buckets for a 1MB table.
55+
56+
3. Generate a 48-bit id for each transaction and fragment it into
57+
64-bits at a time, with index incremented for each fragment. This
58+
means the average transaction (263 bytes) uses about 32 of these.
59+
60+
So here's a simplified example of 4 buckets of an IBLT:
2561

2662
count: 1
2763
id: 0xf00
@@ -71,39 +107,7 @@ turns out that fragment 1 is also in that third bucket, so we subtract
71107

72108
Now we can extract id 0x00f, which is "I love Triffids".
73109

74-
### Subtracting IBLTs ###
75-
76-
The clever bit comes by realizing that if I create an IBLT with
77-
everything in my set, and you create an IBLT with everything in your
78-
set, it's trivial to subtract my IBLT from your IBLT and get an IBLT
79-
of the set differences. Which is great, because all bloom filters
80-
become useless when they clog up, but if our sets are very similar,
81-
the subtraction result gives a nice sparse IBLT. And
82-
[here's the paper](http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf).
83-
84-
<a name="Using-IBLTs"></a>
85-
86-
## Using IBLTs for Bitcoin ##
87-
88-
Gavin suggested some ways to adapt an IBLT to the blockchain problem:
89-
90-
1. Set a size of 1M for the whole thing.
91-
2. Make each IBLT bucket look like this
92-
93-
struct entry {
94-
u32 count;
95-
struct keySum {
96-
u8 id[6];
97-
u16 index;
98-
u8 frag[8];
99-
} key;
100-
}
101-
102-
This gives 52428 buckets for a 1MB table.
103-
104-
3. Generate a 48-bit id for each transaction and fragment it into
105-
64-bits at a time, with index incremented for each fragment. This
106-
means the average transaction (263 bytes) uses about 32 of these.
110+
<a name="Testing-IBLTs"></a>
107111

108112
## Testing It ##
109113

0 commit comments

Comments
 (0)
Please sign in to comment.