search

mimblewimble / grin

Minimal implementation of the Mimblewimble protocol.
https://grin.mw/
Apache License 2.0
5.04k stars 989 forks source link

refactor pmmr functions, improve efficiency; panic on 0 pos1 #3663

Closed tromp closed 2 years ago

tromp commented 2 years ago

name: fixmmr_part1 about: streamline MMR code title: Fix MMR part 1 labels: assignees: Yeastplume

This PR refactors pmmr.rs, improving efficiency and clarifying use of 0-based vs 1-based positions, introducing panics when passing 0 as a 1-based position, which makes no sense in normal use. The latter did require removal of corresponding test-cases. A followup PR is planned to make all methods use 0-based positions, which are preferable for two reasons: 1) they're baked into the consensus model through hash_with_index 2) they simplify some computations, such as converting leaf to node index: node_index = 2 * leaf_index - count_ones(leaf_index) There appears to be no advantage to 1-based positions. The APIs use them though, so the API implementation is where all the conversion should take place.

yeastplume commented 2 years ago

All looks good from my perspective. The panics should be replaced with proper error types, but moving all of the internals to be 0 based should remove the need from them. The API will remain 1-based, so we'll need to make sure all the error propagation is at that level.