← Back to team overview

mimblewimble team mailing list archive

[Review Request] Merkle Mountain Range and sum tree

 

Hi all,
Our sum tree implementation is one of those core areas of functionality that deserve as much review as possible (like commitments and their summing). I pushed a new version over the weekend that's very persistence friendly (it's strictly append-only in an array-ish backend, except for pruning) and does not need to ever materialize any full or partial tree. The added bonus is that by reviewing it, you'll learn about Merkle Mountain Ranges and even get a free binary tree refresher from you CS class :-)
I'd start with Peter Todd's description of MMRs:
https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md
Then I have a fair amount of code comments (by my standards at least) to get you started:
https://github.com/ignopeverell/grin/blob/d32ab967f0414a5fabd9000660301906e52022de/core/src/core/pmmr.rs#L15
And the main binary tree operation:
https://github.com/ignopeverell/grin/blob/d32ab967f0414a5fabd9000660301906e52022de/core/src/core/pmmr.rs#L324
From there the tests should help in giving you a fuller picture:
https://github.com/ignopeverell/grin/blob/d32ab967f0414a5fabd9000660301906e52022de/core/src/core/pmmr.rs#L481
It shouldn't take more than an hour unless you fall into a rabbit hole on the way.
Thanks!

- Igno
P.S. I'm happy to take reviews/critics both over gitter, the mailing list or github.

Follow ups