mimblewimble team mailing list archive

[praxeology_guy <praxeology_guy@xxxxxxxxxxxxxx>]

Hey,

I don't really have time to review right now... but can you give me an overview of what aspect of your ledger system is using the MMR tree?

In bitcoin the proposed use was to create a prune-able and comit-able utxo data structure. (by Peter Todd, which, by the way, I am a huge fan of)

A couple of suggestions I had to the bitcoin implementation:
- could put a spentness bit array at about height diff = 8 (to 12) from the leaves... and not modify the leaf utxos when they are spent.  Then wallets would not have to monitor the spentness status of adjacent leaf nodes.  The MMR tree would then be pruned to the nodes w/ the spentness bits by most nodes.
- potentially wallets could guess the spentness status of adjacent utxos instead of monitoring,  in the case where spent leafs were replaced with nulls.

Not sure if either of the two above ideas are useful in your use case.

Cheers,
Praxeology Guy

> -------- Original Message --------
> Subject: [Mimblewimble] [Review Request] Merkle Mountain Range and sum tree
> Local Time: August 7, 2017 12:10 PM
> UTC Time: August 7, 2017 5:10 PM
> From: igno.peverell@xxxxxxxxxxxxxx
> To: mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>
>
> 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.