A simple experimental encoding of transaction order for Graphene.
Graphene is an efficient protocol for Bitcoin and derivatives for communicating the unordered set of transactions that are included in a block. However, in order to be able to reconstruct the block, the recipient needs to know what order the transactions appear in. This project implements an encoding which utilizes the partially sorted nature of Bitcoin blocks that results from block assembly implementations.
Since transactions in typical blocks are mostly sorted by feerate, with exceptions given for transactions that are children or parents of other transactions in the same block, typical transaction orderings usually contain relatively little entropy. This project provides a simple encoding that efficiently captures all remaining entropy while still having reasonable performance in the worst-case, fully-randomized condition.
The encoding works like this:
First, generate a list of offsets. If the transaction at index 5 in the block is at index 20 in the list sorted by feerate, then store a value of 15 into position 5 in the offsets list.
Second, identify repeating offsets and encode them as (count, offset) pairs. If your offset list is [0, 0, 0, 4, 1, 1, 1, -4], you can summarize that as [(3,0), (1,4), (3,1), (1,-4)] since you have three 0s, followed by one 4, etc.
Third, since most of the counts will have a value of 1 (i.e. a single transaction out of place, followed by one or more transactions from a different place), we can reencode the counts by generating a bitmap of which counts are equal to 1. Any count that is not equal to 1 is encoded separately in a list of residual counts.
Last, encode all of the residuals and the offset values as signed varints and serialize them. This serialization step is not yet implemented in this project, but calculating the size of the varints is. Actual signed varint encoding should be trivial to add.
Here is an example of an encoded ordering of a block, plus a walkthrough of the decoding algorithm:
The data for the encoding and decoding of the block is below the dashed line. I will work through the first few steps in the compressed data to show how it generates the data table beneath it. The data table itself shows the index (idx), followed by the feerates (in satoshi/byte) for the transactions as found in each of the actual block (GBT), the decoded ordering (should equal GBT), and in the list of transactions sorted by feerate. The last column shows the relative position of a transaction in the block, such that GBT pos + offset = sorted pos.
Let's work through the decoding process step by step.
The first offset value is 0 at transaction index 0. To see if this is offset gets repeated, we check to see if our bitmap's first bit is set. Since 104 & 1 == 0, we know that this 0 gets repeated. We then check the repetition count, and see that this offset gets repeated 43 times. This means that the first 43 transactions have an offset of 0 -- that is, the block position equals the sorted position plus 0.
Since 104 & 2 == 0, the second offset is also repeating. It gets repeated 7 times, and the offset value value is 1. Block positions 43 .. 49 are filled with sorted positions 44 .. 50. This suggests that the transaction at sorted position 43 depends on another transaction and was moved to a later position in the block. Eventually, we'll see a negative offset at some position that refers to transaction 43. Next.
Since 104 & 4 == 0, the third offset is also repeating. It gets repeated 2 times, and the offset value is 2.
Since 104 & 8 == 8, the fourth offset is NOT repeating. It only appears once. The value for this offset is -1. This indicates that the transaction at index 52 in the block came from index (52-1) = 51 in the sorted list.
Et ceterea.
----------------------
~/dev/bitcoin/grapheneorder$ python orderencode.py -v samplegbts/1
7 bitmap bytes, 23 residual varints, 51 offset varints
81 bytes total
378 transactions total
0 total errors
Compressed data:
Bitmap of non-repeating offsets: [104, 246, 140, 97, 118, 252, 3]
Repetition count of repeating offsets: [43, 7, 2, 12, 11, 19, 13, 2, 58, 7, 14, 8, 9, 20, 13, 3, 6, 46, 40, 5, 2, 2, 8]
The offsets values: [0, 1, 2, -1, 1, 133, -23, -1, 0, 140, -21, -2, 0, -3, 1, -4, -3, -2, -1, -3, -2, -1, 0, 9, -25, -2, -1, 0, 1, 7, -4, -1, 0, 1, -1, 0, 12, -1, 11, -2, 6, -4, 4, -5, 3, -6, 2, -7, 1, -8, 0]
idx GBT Decoded Sorted Correct Offset
0 462.439 462.439 462.439 * 0
1 446.429 446.429 446.429 * 0
2 347.222 347.222 347.222 * 0
3 321.422 321.422 321.422 * 0
4 272.374 272.374 272.374 * 0
5 248.164 248.164 248.164 * 0
6 221.239 221.239 221.239 * 0
7 221.239 221.239 221.239 * 0
8 196.078 196.078 196.078 * 0
9 150.624 150.624 150.624 * 0
10 150.402 150.402 150.402 * 0
11 134.197 134.197 134.197 * 0
12 116.279 116.279 116.279 * 0
13 116.167 116.167 116.167 * 0
14 114.491 114.491 114.491 * 0
15 100.543 100.543 100.543 * 0
16 100.469 100.469 100.469 * 0
17 100.373 100.373 100.373 * 0
18 100.363 100.363 100.363 * 0
19 100.346 100.346 100.346 * 0
20 100.271 100.271 100.271 * 0
21 100.232 100.232 100.232 * 0
22 100.207 100.207 100.207 * 0
23 100.173 100.173 100.173 * 0
24 100.000 100.000 100.000 * 0
25 100.000 100.000 100.000 * 0
26 100.000 100.000 100.000 * 0
27 97.306 97.306 97.306 * 0
28 96.525 96.525 96.525 * 0
29 89.686 89.686 89.686 * 0
30 89.286 89.286 89.286 * 0
31 89.286 89.286 89.286 * 0
32 81.076 81.076 81.076 * 0
33 78.125 78.125 78.125 * 0
34 78.125 78.125 78.125 * 0
35 57.244 57.244 57.244 * 0
36 55.501 55.501 55.501 * 0
37 53.908 53.908 53.908 * 0
38 53.763 53.763 53.763 * 0
39 51.827 51.827 51.827 * 0
40 50.270 50.270 50.270 * 0
41 50.224 50.224 50.224 * 0
42 50.000 50.000 50.000 * 0
43 45.791 45.791 47.619 * 1
44 45.000 45.000 45.791 * 1
45 44.444 44.444 45.000 * 1
46 42.553 42.553 44.444 * 1
47 41.220 41.220 42.553 * 1
48 41.183 41.183 41.220 * 1
49 40.000 40.000 41.183 * 1
50 39.167 39.167 40.000 * 2
51 38.084 38.084 39.320 * 2
52 39.320 39.320 39.167 * -1
53 36.064 36.064 38.084 * 1
54 31.138 31.138 36.064 * 1
55 31.138 31.138 31.138 * 1
56 30.133 30.133 31.138 * 1
57 29.644 29.644 30.133 * 1
58 27.723 27.723 29.644 * 1
59 26.810 26.810 27.723 * 1
60 26.810 26.810 26.810 * 1
61 26.738 26.738 26.810 * 1
62 26.738 26.738 26.738 * 1
63 26.549 26.549 26.738 * 1
64 26.414 26.414 26.549 * 1
65 6.000 6.000 26.414 * 133
66 47.619 47.619 22.321 * -23
67 22.321 22.321 22.321 * -1
68 22.321 22.321 22.222 * -1
69 22.222 22.222 22.222 * -1
70 22.222 22.222 22.124 * -1
71 22.124 22.124 22.124 * -1
72 22.124 22.124 22.124 * -1
73 22.124 22.124 22.124 * -1
74 22.124 22.124 21.622 * -1
75 21.622 21.622 20.942 * -1
76 20.942 20.942 20.000 * -1
77 20.000 20.000 19.531 * -1
78 19.305 19.305 19.305 * 0
79 17.857 17.857 17.857 * 0
80 17.778 17.778 17.778 * 0
81 16.381 16.381 16.381 * 0
82 16.000 16.000 16.000 * 0
83 15.535 15.535 15.535 * 0
84 15.000 15.000 15.000 * 0
85 14.946 14.946 14.946 * 0
86 14.810 14.810 14.810 * 0
87 14.519 14.519 14.519 * 0
88 14.227 14.227 14.227 * 0
89 13.876 13.876 13.876 * 0
90 13.875 13.875 13.875 * 0
91 13.872 13.872 13.872 * 0
92 13.839 13.839 13.839 * 0
93 13.820 13.820 13.820 * 0
94 13.818 13.818 13.818 * 0
95 13.817 13.817 13.817 * 0
96 13.274 13.274 13.274 * 0
97 5.022 5.022 12.498 * 140
98 19.531 19.531 12.487 * -21
99 12.498 12.498 12.387 * -2
100 12.487 12.487 12.332 * -2
101 12.387 12.387 11.991 * -2
102 12.332 12.332 11.492 * -2
103 11.991 11.991 11.484 * -2
104 11.492 11.492 11.453 * -2
105 11.484 11.484 11.437 * -2
106 11.453 11.453 11.398 * -2
107 11.437 11.437 11.065 * -2
108 11.398 11.398 11.000 * -2
109 11.065 11.065 10.867 * -2
110 11.000 11.000 10.777 * -2
111 10.867 10.867 10.758 * -2
112 10.661 10.661 10.661 * 0
113 10.777 10.777 10.661 * -3
114 10.615 10.615 10.658 * 1
115 10.758 10.758 10.615 * -4
116 10.661 10.661 10.615 * -3
117 10.658 10.658 10.558 * -3
118 10.615 10.615 10.558 * -2
119 10.558 10.558 10.413 * -2
120 10.558 10.558 10.398 * -2
121 10.413 10.413 10.297 * -2
122 10.398 10.398 10.251 * -2
123 10.297 10.297 10.251 * -2
124 10.251 10.251 10.134 * -2
125 10.251 10.251 10.105 * -2
126 10.134 10.134 10.044 * -2
127 10.105 10.105 10.044 * -2
128 10.044 10.044 10.039 * -2
129 10.044 10.044 10.030 * -2
130 10.039 10.039 10.027 * -2
131 10.030 10.030 10.027 * -2
132 10.027 10.027 10.019 * -2
133 10.027 10.027 10.015 * -2
134 10.019 10.019 10.000 * -2
135 10.015 10.015 9.964 * -2
136 10.000 10.000 9.938 * -2
137 9.964 9.964 9.766 * -2
138 9.938 9.938 9.749 * -2
139 9.766 9.766 9.733 * -2
140 9.749 9.749 9.256 * -2
141 9.733 9.733 9.173 * -2
142 9.256 9.256 9.009 * -2
143 9.173 9.173 8.827 * -2
144 9.009 9.009 8.827 * -2
145 8.827 8.827 8.788 * -2
146 8.827 8.827 8.747 * -2
147 8.788 8.788 8.730 * -2
148 8.747 8.747 8.326 * -2
149 8.730 8.730 8.142 * -2
150 8.326 8.326 7.831 * -2
151 8.142 8.142 7.728 * -2
152 7.831 7.831 7.662 * -2
153 7.728 7.728 7.662 * -2
154 7.662 7.662 7.659 * -2
155 7.662 7.662 7.649 * -2
156 7.659 7.659 7.628 * -2
157 7.649 7.649 7.628 * -2
158 7.628 7.628 7.628 * -2
159 7.628 7.628 7.628 * -2
160 7.628 7.628 7.624 * -2
161 7.628 7.628 7.623 * -2
162 7.624 7.624 7.529 * -2
163 7.623 7.623 7.330 * -2
164 7.529 7.529 7.175 * -2
165 7.330 7.330 7.076 * -2
166 7.175 7.175 7.062 * -2
167 7.076 7.076 7.031 * -2
168 7.062 7.062 6.817 * -2
169 7.031 7.031 6.794 * -2
170 6.817 6.817 6.726 * -2
171 6.794 6.794 6.717 * -2
172 6.726 6.726 6.696 * -2
173 6.717 6.717 6.667 * -2
174 6.696 6.696 6.667 * -2
175 6.667 6.667 6.637 * -2
176 6.637 6.637 6.637 * -1
177 6.667 6.667 6.637 * -3
178 6.637 6.637 6.637 * -2
179 6.637 6.637 6.637 * -2
180 6.637 6.637 6.637 * -2
181 6.637 6.637 6.362 * -2
182 6.637 6.637 6.353 * -2
183 6.362 6.362 6.349 * -2
184 6.353 6.353 6.328 * -2
185 6.328 6.328 6.328 * -1
186 6.328 6.328 6.268 * -1
187 6.268 6.268 6.182 * -1
188 6.182 6.182 6.081 * -1
189 6.081 6.081 6.054 * -1
190 6.054 6.054 6.054 * -1
191 6.054 6.054 6.041 * -1
192 6.041 6.041 6.029 * -1
193 6.029 6.029 6.027 * -1
194 6.027 6.027 6.027 * -1
195 6.027 6.027 6.027 * -1
196 6.027 6.027 6.027 * -1
197 6.027 6.027 6.016 * -1
198 6.016 6.016 6.000 * -1
199 6.000 6.000 6.000 * 0
200 6.000 6.000 6.000 * 0
201 6.000 6.000 6.000 * 0
202 6.000 6.000 6.000 * 0
203 5.979 5.979 5.979 * 0
204 5.947 5.947 5.947 * 0
205 5.885 5.885 5.885 * 0
206 5.839 5.839 5.839 * 0
207 5.357 5.357 5.761 * 9
208 6.349 6.349 5.761 * -25
209 5.761 5.761 5.749 * -2
210 5.761 5.761 5.534 * -2
211 5.749 5.749 5.533 * -2
212 5.534 5.534 5.533 * -2
213 5.533 5.533 5.500 * -2
214 5.533 5.533 5.370 * -2
215 5.500 5.500 5.359 * -2
216 5.370 5.370 5.357 * -2
217 5.359 5.359 5.357 * -2
218 5.357 5.357 5.344 * -1
219 5.344 5.344 5.276 * -1
220 5.276 5.276 5.276 * -1
221 5.276 5.276 5.276 * -1
222 5.276 5.276 5.230 * -1
223 5.230 5.230 5.086 * -1
224 5.086 5.086 5.067 * -1
225 5.067 5.067 5.067 * -1
226 5.067 5.067 5.067 * -1
227 5.067 5.067 5.067 * -1
228 5.067 5.067 5.045 * -1
229 5.045 5.045 5.045 * -1
230 5.045 5.045 5.045 * -1
231 5.045 5.045 5.040 * -1
232 5.040 5.040 5.040 * -1
233 5.040 5.040 5.040 * -1
234 5.040 5.040 5.040 * -1
235 5.040 5.040 5.027 * -1
236 5.027 5.027 5.022 * -1
237 5.022 5.022 5.022 * -1
238 5.022 5.022 5.022 * 0
239 5.022 5.022 5.022 * 0
240 5.022 5.022 5.022 * 0
241 5.022 5.022 5.022 * 0
242 5.022 5.022 5.022 * 0
243 5.022 5.022 5.022 * 0
244 5.022 5.022 5.022 * 0
245 5.022 5.022 5.022 * 0
246 5.022 5.022 5.022 * 0
247 5.022 5.022 5.022 * 0
248 5.022 5.022 5.022 * 0
249 5.022 5.022 5.022 * 0
250 5.022 5.022 5.022 * 0
251 5.015 5.015 5.022 * 1
252 5.013 5.013 5.015 * 1
253 5.013 5.013 5.013 * 1
254 5.000 5.000 5.013 * 7
255 5.022 5.022 5.011 * -4
256 5.011 5.011 5.006 * -1
257 5.006 5.006 5.004 * -1
258 5.004 5.004 5.004 * -1
259 5.004 5.004 5.004 * -1
260 5.004 5.004 5.004 * -1
261 5.004 5.004 5.000 * -1
262 5.000 5.000 5.000 * 0
263 5.000 5.000 5.000 * 0
264 5.000 5.000 5.000 * 0
265 5.000 5.000 5.000 * 0
266 5.000 5.000 5.000 * 0
267 5.000 5.000 5.000 * 0
268 5.000 5.000 5.000 * 0
269 5.000 5.000 5.000 * 0
270 5.000 5.000 5.000 * 0
271 5.000 5.000 5.000 * 0
272 5.000 5.000 5.000 * 0
273 5.000 5.000 5.000 * 0
274 5.000 5.000 5.000 * 0
275 5.000 5.000 5.000 * 0
276 5.000 5.000 5.000 * 0
277 4.982 4.982 4.982 * 0
278 4.950 4.950 4.950 * 0
279 4.414 4.414 4.414 * 0
280 4.397 4.397 4.397 * 0
281 4.016 4.016 4.016 * 0
282 4.016 4.016 4.016 * 0
283 4.000 4.000 4.000 * 0
284 4.000 4.000 4.000 * 0
285 3.990 3.990 3.990 * 0
286 3.445 3.445 3.445 * 0
287 3.205 3.205 3.205 * 0
288 3.032 3.032 3.032 * 0
289 3.008 3.008 3.008 * 0
290 2.735 2.735 2.735 * 0
291 2.680 2.680 2.680 * 0
292 2.656 2.656 2.656 * 0
293 2.604 2.604 2.604 * 0
294 2.604 2.604 2.604 * 0
295 2.593 2.593 2.593 * 0
296 2.523 2.523 2.523 * 0
297 2.509 2.509 2.509 * 0
298 2.476 2.476 2.476 * 0
299 2.460 2.460 2.460 * 0
300 2.442 2.442 2.442 * 0
301 2.436 2.436 2.436 * 0
302 2.433 2.433 2.433 * 0
303 2.433 2.433 2.433 * 0
304 2.433 2.433 2.433 * 0
305 2.430 2.430 2.430 * 0
306 2.428 2.428 2.428 * 0
307 2.427 2.427 2.427 * 0
308 2.426 2.426 2.427 * 1
309 2.427 2.427 2.426 * -1
310 2.422 2.422 2.422 * 0
311 2.420 2.420 2.420 * 0
312 2.420 2.420 2.420 * 0
313 2.414 2.414 2.414 * 0
314 2.414 2.414 2.414 * 0
315 2.409 2.409 2.409 * 0
316 2.363 2.363 2.363 * 0
317 2.270 2.270 2.270 * 0
318 2.270 2.270 2.270 * 0
319 2.270 2.270 2.270 * 0
320 2.270 2.270 2.270 * 0
321 2.269 2.269 2.269 * 0
322 2.265 2.265 2.265 * 0
323 2.265 2.265 2.265 * 0
324 2.262 2.262 2.262 * 0
325 2.261 2.261 2.261 * 0
326 2.260 2.260 2.260 * 0
327 2.258 2.258 2.258 * 0
328 2.258 2.258 2.258 * 0
329 2.258 2.258 2.258 * 0
330 2.258 2.258 2.258 * 0
331 2.258 2.258 2.258 * 0
332 2.258 2.258 2.258 * 0
333 2.249 2.249 2.249 * 0
334 2.246 2.246 2.246 * 0
335 2.242 2.242 2.242 * 0
336 2.239 2.239 2.239 * 0
337 2.237 2.237 2.237 * 0
338 2.237 2.237 2.237 * 0
339 2.212 2.212 2.212 * 0
340 2.212 2.212 2.212 * 0
341 2.083 2.083 2.083 * 0
342 2.009 2.009 2.009 * 0
343 2.004 2.004 2.004 * 0
344 2.000 2.000 2.000 * 0
345 1.555 1.555 1.555 * 0
346 1.508 1.508 1.508 * 0
347 1.183 1.183 1.183 * 0
348 1.183 1.183 1.183 * 0
349 1.105 1.105 1.105 * 0
350 1.084 1.084 1.085 * 12
351 1.085 1.085 1.085 * -1
352 1.084 1.084 1.085 * 11
353 1.085 1.085 1.085 * -2
354 1.085 1.085 1.085 * -2
355 1.085 1.085 1.085 * -2
356 1.085 1.085 1.085 * -2
357 1.085 1.085 1.085 * -2
358 1.084 1.084 1.085 * 6
359 1.084 1.084 1.085 * 6
360 1.085 1.085 1.085 * -4
361 1.085 1.085 1.085 * -4
362 1.084 1.084 1.084 * 4
363 1.085 1.085 1.084 * -5
364 1.084 1.084 1.084 * 3
365 1.085 1.085 1.084 * -6
366 1.084 1.084 1.084 * 2
367 1.085 1.085 1.084 * -7
368 1.084 1.084 1.084 * 1
369 1.085 1.085 1.084 * -8
370 1.084 1.084 1.084 * 0
371 1.011 1.011 1.011 * 0
372 1.006 1.006 1.006 * 0
373 1.005 1.005 1.005 * 0
374 1.003 1.003 1.003 * 0
375 1.003 1.003 1.003 * 0
376 1.003 1.003 1.003 * 0
377 1.003 1.003 1.003 * 0