@@ -21,7 +21,43 @@ those, you might find more buckets now have 1 thing in them, etc. The
21
21
[ paper] ( http://arxiv.org/pdf/1101.2245.pdf ) is worth reading, but this
22
22
should give you the idea.
23
23
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:
25
61
26
62
count: 1
27
63
id: 0xf00
@@ -71,39 +107,7 @@ turns out that fragment 1 is also in that third bucket, so we subtract
71
107
72
108
Now we can extract id 0x00f, which is "I love Triffids".
73
109
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 >
107
111
108
112
## Testing It ##
109
113
0 commit comments