Include Max-Key in each node in the CSMT

[meyer9]

Currently, the max key is calculated on the fly in CSMT, but it really should be calculated when inserting.

On recursing back, on the way up all the hashes and max-key values along the minimum distance path are readjusted.

https://eprint.iacr.org/2018/955.pdf

[wqking]

I don't understand. Do you find any bug? Do you mean the max key should be a parameter of CSMT.Insert?
Calculating the max/min key and the distance is the internal mechanism and the external code should not be aware of that.

[meyer9]

MaxKey should be a field of Node.

[wqking]

What problem to solve? Bug or performance?
And getMaxKey is used only once, I can't see why it should be part of the Node.

// NewInnerNode constructs a new InnerNode
func NewInnerNode(hash Hash, left Node, right Node) InnerNode {
    return InnerNode{
        nodeBase: nodeBase{
            key:  *getMaxKey(left.GetKey(), right.GetKey()),
            hash: hash,
        },
        left:  left,
        right: right,
    }
}

[meyer9]

Ah, I see. The key in the inner node is actually the max key of the subtree. Sorry about that.