Check that all mutable MMRs properly compress deletion bitmaps #5277
Comments
This was referenced Mar 28, 2023
stringhandler
pushed a commit
that referenced
this issue
Mar 28, 2023
Description --- Ensures that mutable MMR root computation first performs deletion bitmap compression. Closes [issue 5277](#5277). Motivation and Context --- Currently, when mutable MMR roots [are computed](https://github.com/tari-project/tari/blob/e334a404e432b0911bae3054a28d8e8ca5876e6c/base_layer/mmr/src/mutable_mmr.rs#L119-L131), it's implicitly assumed that the underlying deletion bitmap has been compressed. If it has not, it's possible for the resulting root to be different than if the bitmap were compressed. This already resulted in an intermittent [test failure](#5268). To reduce the risk that a caller does not perform this compression correctly, this PR adds compression to the Merkle root computation functionality directly. It also removes a few compression calls that become redundant with this change. Note that this may constitute an efficiency regression. If a mutable MMR does not have any deletions since its last bitmap compression, subsequent compression is not necessary. Further, we perform the compression on a clone of the bitmap; this is necessary to avoid mutability and ensure that operations like equality (which rely on root computation) function properly. The efficiency consequences of this change should be examined to ensure they are acceptable. How Has This Been Tested? --- Existing CI passes. What process can a PR reviewer use to test or verify this change? --- Run existing CI. To further check for intermittent test failures, loop affected tests. Breaking Changes --- - [ ] None - [ ] Requires data directory on base node to be deleted - [ ] Requires hard fork - [x] Other - Please specify It may be the case that this change affects the way mutable MMR roots are computed in certain cases, which in turn may be a breaking change.
agubarev
pushed a commit
to agubarev/tari
that referenced
this issue
Mar 31, 2023
Description --- Ensures that mutable MMR root computation first performs deletion bitmap compression. Closes [issue 5277](tari-project#5277). Motivation and Context --- Currently, when mutable MMR roots [are computed](https://github.com/tari-project/tari/blob/e334a404e432b0911bae3054a28d8e8ca5876e6c/base_layer/mmr/src/mutable_mmr.rs#L119-L131), it's implicitly assumed that the underlying deletion bitmap has been compressed. If it has not, it's possible for the resulting root to be different than if the bitmap were compressed. This already resulted in an intermittent [test failure](tari-project#5268). To reduce the risk that a caller does not perform this compression correctly, this PR adds compression to the Merkle root computation functionality directly. It also removes a few compression calls that become redundant with this change. Note that this may constitute an efficiency regression. If a mutable MMR does not have any deletions since its last bitmap compression, subsequent compression is not necessary. Further, we perform the compression on a clone of the bitmap; this is necessary to avoid mutability and ensure that operations like equality (which rely on root computation) function properly. The efficiency consequences of this change should be examined to ensure they are acceptable. How Has This Been Tested? --- Existing CI passes. What process can a PR reviewer use to test or verify this change? --- Run existing CI. To further check for intermittent test failures, loop affected tests. Breaking Changes --- - [ ] None - [ ] Requires data directory on base node to be deleted - [ ] Requires hard fork - [x] Other - Please specify It may be the case that this change affects the way mutable MMR roots are computed in certain cases, which in turn may be a breaking change.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
A recent test failure uncovered that failure to compress the deletion bitmap of a mutable MMR can result in a different root than if compression is done. Further, this failure may not always be detected since compression isn't guaranteed to change the resulting bitmap hash.
There are several critical places in the codebase where mutable MMR roots are computed, and it's not clear if compression is being done properly in all cases. If no deletions are performed, it's not necessary to compress. If deletions are performed, it is necessary.
There seem to be two approaches that could be taken to address this:
The second approach is presumably less efficient, but is much safer.
The text was updated successfully, but these errors were encountered: