The MMR (Merkle Mountain Range) was originally designed with 0-based leaf and node indices.
This is reflected in the consensus model since hashes are computed with a 0-based node index prepended to the leaf data or the two child hashes.
0-based indices also simplify conversion of a leaf to a node index, which becomes
2 * leaf_index - count_ones(leaf_index).
The other C++ Grin code base, grinplusplus, uses 0-bases indices exclusively.
Unfortunately, 1-based indices have crept into the Grin code base resulting in a mix of both.
Use of 1-based indices has the downside that we often need to test that an index argument isn't 0.
This PR tries to convert as many uses of 1-based indices as possible to 0-based indices.
A few instances remain in storage related code where bitmaps and leaf sets are read from and written to disk.
The changes are not consensus breaking.
Each changed method is in its own commit, except for some pairs of related methods.
Tested with a regular sync as well as a sync from scratch.
name: fixmmr_part2 about: Pull Request checklist title: 'Fixmmr part2 labels: '' assignees: ''
The MMR (Merkle Mountain Range) was originally designed with 0-based leaf and node indices. This is reflected in the consensus model since hashes are computed with a 0-based node index prepended to the leaf data or the two child hashes. 0-based indices also simplify conversion of a leaf to a node index, which becomes 2 * leaf_index - count_ones(leaf_index). The other C++ Grin code base, grinplusplus, uses 0-bases indices exclusively. Unfortunately, 1-based indices have crept into the Grin code base resulting in a mix of both. Use of 1-based indices has the downside that we often need to test that an index argument isn't 0. This PR tries to convert as many uses of 1-based indices as possible to 0-based indices. A few instances remain in storage related code where bitmaps and leaf sets are read from and written to disk. The changes are not consensus breaking. Each changed method is in its own commit, except for some pairs of related methods. Tested with a regular sync as well as a sync from scratch.