[Compact blocks] Decoding of prefilledtxn is wrong #8705

issue dagurval opened this issue on September 12, 2016

dagurval commented at 6:07 PM on September 12, 2016: contributor
It looks to me like decoding of prefilled transactions is incorrect in Bitcoin Core 0.13. The error is in PartiallyDownloadedBlock::InitData where it decodes CBlockHeaderAndShortTxIDs incorrectly.

Given a block with 5 transactions, where transactions 3 and 5 are prefilled (+ coinbase). Prefilled transactions are encoded like this:

TX Prefilled? Encoded ID

0 YES 0

1

2

3 YES 3

4

5 YES 2

However in lines 60 to 75, this is decoded like this:

Prefilled index Decoded index

0 0 (-1 + 0 + 1)

1 4 (0 + 3 + 1)

2 7 (4 + 2 + 1)

If you change line 60 from:
```
int32_t lastprefilledindex = -1;
```
to
```
int32_t lastprefilledindex = 0;
```
and line 65 from
```
    lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so cant overflow here
```
to
```
    lastprefilledindex += cmpctblock.prefilledtxn[i].index; //index is a uint16_t, so cant overflow here
```
The decoding would become:

Prefilled index Decoded index

0 0 (0 + 0)

1 3 (0 + 3)

2 5 (3 + 2)

This would match the original index in the block.

Since shortids depend on prefilledtxn being decoded correctly, these also will also decode incorrectly.
dagurval commented at 7:22 PM on September 12, 2016: contributor

The consequence of this bug is that Bitcoin Core cannot receive more than 1 prefilled transaction (only coinbase).
sdaftuar commented at 9:02 PM on September 12, 2016: member

I think you're misreading the BIP for how indexes are encoded; also I'm pretty sure the compact blocks p2p test exercises the case of Bitcoin core receiving a block with multiple pre filled transactions. From the bip:

Several uses of CompactSize below are "differentially encoded". For these, instead of using raw indexes, the number encoded is the difference between the current index and the previous index, minus one. For example, a first index of 0 implies a real index of 0, a second index of 0 thereafter refers to a real index of 1, etc.

Also see here for the test that exercises this logic: https://github.com/bitcoin/bitcoin/blob/master/qa/rpc-tests/p2p-compactblocks.py#L391
MarcoFalke added the label Brainstorming on Sep 12, 2016
dagurval commented at 9:40 PM on September 12, 2016: contributor

Yes, you're correct, it is my misunderstanding of the encoding. The example above should be

TX Prefilled Encoded ID

0 YES 0

1

2

3 YES 2

4

5 YES 1

In this case the decoding logic is correct.
MarcoFalke commented at 9:55 PM on September 12, 2016: member

In this case the decoding logic is correct.

Closing.
MarcoFalke closed this on Sep 12, 2016
MarcoFalke locked this on Sep 8, 2021

TX	Prefilled?	Encoded ID
0	YES	0
1
2
3	YES	3
4
5	YES	2

Prefilled index	Decoded index
0	0 (-1 + 0 + 1)
1	4 (0 + 3 + 1)
2	7 (4 + 2 + 1)

Prefilled index	Decoded index
0	0 (0 + 0)
1	3 (0 + 3)
2	5 (3 + 2)

TX	Prefilled	Encoded ID
0	YES	0
1
2
3	YES	2
4
5	YES	1

Contributors

Labels