<< Part I | This is Part II of a multi-part series on Bitcoin block propagation with IBLT. | Part III >>>
In part I of this IBLT series, Bitcoin block propagation with IBLT, Part I: infographic, I used 3 hash functions and a value size of 64 bytes. Where did I get those numbers from?
Well, I didn't pull them out of my ear. I did some statistical analysis on these parameters. I simulated a block where;
- The block contains 50 transactions that the receiver didn't have (called extra transactions)
- The receiver has 50 transaction that is not present in the block (called absent transactions)
Value size
The first parameter I analyzed was the value size. That is the part of the cell that stores the transaction slice data. I started with value size 8 bytes, and increased it in each iteration up to 512 bytes. For every value size I used interval halving to find the minimum decodable IBLT. For this test I use 4 hash functions, k=4. That number was actually pulled out of my ear. Result of three runs, don't bother about "non-corpus" in the titles:
Here 48-80 bytes seems like a good choice, at least when using k=4.
Hash function count, k
The second parameter I analyzed was the number of hash functions, k. I started with k=2 and iterated the test up to k=10. For each k, I searched for the minimum recoverable IBLT through interval halving. Value size is fixed at 64 bytes. Result of three runs:
There seems to be no reason to use more hash functions than 3 when using 64 byte values. And k=2 is really bad.
Refinement
To refine this I redid the value size test with k=3, to see if that changes the optimal value size:
The optimal value is still in the interval 48-80 bytes, but it's now slightly more distinguished.
Conclusion
I see no reason to use something other that k=3 and value size 48-80 bytes. In my tests from now on I will stick to k=3 and 64 bytes values.
In the next part, Part III, we will explore how the failure probability, the probability that decoding of the block fails, varies with increasing number of cells.
