fix: ensures mutable MMR bitmaps are compressed #5278
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
ghpbot-tari-project
added
P-acks_required
AaronFeickert
force-pushed
the
mmr-compression
branch
from
9b35e17
to
ed8ce29
Compare
AaronFeickert
force-pushed
the
mmr-compression
branch
from
ed8ce29
to
671fedb
Compare
ghpbot-tari-project
removed
the
P-reviews_required
This was referenced Mar 28, 2023
agubarev
pushed a commit
to agubarev/tari
that referenced
this pull request
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
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Description
Ensures that mutable MMR root computation first performs deletion bitmap compression.
Closes issue 5277.
Motivation and Context
Currently, when mutable MMR roots are computed, 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.
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
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.