mmr

package
v0.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 1, 2024 License: MIT Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrNewLogSizeMustBeGreater = errors.New("the new log size must be greater than the previous")
)
View Source 
var (
	ErrNotFound = errors.New("not found")
)

Functions

func AddHashedLeaf 

func AddHashedLeaf(store NodeAppender, hasher hash.Hash, hashedLeaf []byte) (uint64, error)

AddHashedLeaf adds a single leaf to the mmr and back fills any interior nodes 'above and to the left'

Returns the size of the mmr after addition of the leaf. This is also the position of the next leaf.

func AllOnes 

func AllOnes(num uint64) bool

func Ancestors 

func Ancestors(i uint64) []uint64

func BagPeaksRHS 

func BagPeaksRHS(store indexStoreGetter, hasher hash.Hash, pos uint64, peaks []uint64) ([]byte, error)

BagPeaksRHS computes a root for the RHS peaks. This function will only return an err if there is an issue fetching a value from the provided store.

The burden is on the _caller_ to provide valid peaks for the given position pos

If there are no peaks to the right of pos, this function returns nil, nil. This means the sibling hash for pos is to the left and the return value should be ignored.

Working exclusively in positions rather than indices, If the peak pos is 25, then the RHS (and the sibling hash) is just H(26), if pos is 26 then there is not right sibling, and this method would return nil.

The peaks are listed in ascending order (ie from the end of the range back towards pos), So when pos is 15, the RHS sibling hash will be: 

H(H(H(right)|H(left)) | H(22))

Which is: 

H(H(H(26)|H(25)) | H(22))

3            15
           /    \
          /      \
         /        \
2       7          14             22
      /   \       /   \          /   \
1    3     6    10     13      18      21      25
    / \  /  \   / \   /  \    /  \    /  \    /   \
0  1   2 4   5 8   9 11   12 16   17 19   20 23   24 26

func BitLength 

func BitLength(num uint64) int

func BitLength64 

func BitLength64(num uint64) uint64

func GetRoot 

func GetRoot(mmrSize uint64, store indexStoreGetter, hasher hash.Hash) ([]byte, error)

GetRoot returns the root hash for the Merkle Mountain Range. The root is defined as the 'bagging' of all peaks, starting with the highest. So its simply a call to BagPeaksRHS for _all_ peaks in the MMR of the provided size.

func HashPeaksRHS 

func HashPeaksRHS(hasher hash.Hash, peakHashes [][]byte) []byte

HashPeaksRHS merkleizes the peaks to obtain a single tree root This variant copies the peakHashes list in order to be side effect free.

func HeightIndexLeafCount 

func HeightIndexLeafCount(heightIndex uint64) uint64

HeightIndexLeafCount returns the count of leaves that are contained in a single mountain whose height is heightIndex + 1

func HeightIndexSize 

func HeightIndexSize(heightIndex uint64) uint64

HeightIndexSize returns the node count corresponding to the zero based height index

func HeightMaxIndex 

func HeightMaxIndex(heightIndex uint64) uint64

HeightMaxIndex returns the node index corresponding to the zero based height index

func HeightPeakRight 

func HeightPeakRight(mmrSize uint64, height uint64, i uint64) (uint64, uint64, bool)

func HeightSize 

func HeightSize(heightIndex uint64) uint64

HeightSize returns the size of the mmr with the provided heightIndex

func HighestPos 

func HighestPos(mmrSize uint64) (uint64, uint64)

HighestPos returns the height and the peak index for the highest and most left node in the MMR of the given size.

func IndexHeight 

func IndexHeight(i uint64) uint64

IndexHeight obtains the tree height of an MMR index Taking advantage of the binary encoding resulting from the tree construction to do so. This function is the basis for the entire MMR implementation. See the extended remarks in doc.go for exposition on why & how it works.

func IndexHeight2 

func IndexHeight2(pos uint64) uint64

IndexHieght2 obtains the tree height of an MMR index (position - 1) Then, we iteratively reduce the size to the next perfect tree down. Each time we do this if pos sticks out, we shift it back under by shifting it according to the current tree size. This process is (this is the variant that most intuitively follows the typical construction diagrams, and is kept around for testing)

func IndexProof 

func IndexProof(mmrSize uint64, store indexStoreGetter, hasher hash.Hash, i uint64) ([][]byte, error)

IndexProof provides a proof of inclusion for the leaf at index i against the full MMR

It relies on the methods IndexProofLocal, BagPeaksRHS and PeaksLHS for collecting the necessary MMR elements and then combines the results into a final verifiable commitment for the whole MMR.

The proof layout is conceptualy this:

[local-peak-proof-i, right-sibling-of-i, left-of-i-peaks-reversed]

So for leaf 15, given 

3              14
             /    \
            /      \
           /        \
          /          \
2        6            13           21
       /   \        /    \
1     2     5      9     12     17     20     24
     / \   / \    / \   /  \   /  \
0   0   1 3   4  7   8 10  11 15  16 18  19 22  23   25

We get 

               |  BagPeaksRHS   |
               .                .
[H(16), H(20), H(H(H(25)|H(24)) | H(21), H(14)]
 ^ .         ^                   ^           ^
 .___________.                   .___________.
       |                               |
       |                          reversed(PeaksLHS)
   IndexProofLocal

Note that right-sibling is omitted if there is none, and similarly, the left peaks. The individual functions producing those elements contain more detail over the construction of their particular proof component.

func IndexProofLocal 

func IndexProofLocal(mmrSize uint64, store indexStoreGetter, i uint64) ([][]byte, uint64, error)

IndexProofLocal collects the merkle root proof for the local MMR peak containing index i

So for the follwing index tree, and i=15 with mmrSize = 26 we would obtain the path

[H(16), H(20)]

Because the local peak is 21, and given the value for 15, we only need 16 and then 20 to prove the local root. 

3              14
             /    \
            /      \
           /        \
          /          \
2        6            13           21
       /   \        /    \
1     2     5      9     12     17     20     24
     / \   / \    / \   /  \   /  \
0   0   1 3   4  7   8 10  11 15  16 18  19 22  23   25

func IsPow2 

func IsPow2(size uint) bool

IsPow2 determins if the unsigned value size is a perfect power of 2.

func JumpLeftPerfect 

func JumpLeftPerfect(pos uint64) uint64

JumpLeftPerfect is used to iteratively discover the left most node at the same height as the node identified by pos. This is how we discover the height in the tree of an arbitrary pusition so as to avoid ever having to materialise the whole tree. It 'jumps left' by the size of the perfect tree which would contain pos.

So given, 

3            15
           /    \
          /      \
         /        \
2       7          14
      /   \       /   \
1    3     6    10     13      18
    / \  /  \   / \   /  \    /  \
0  1   2 4   5 8   9 11   12 16   17

JumpLeftPerfect(13) returns 6 because the size of the perfect tree containing 13 is 7. The next jump, JumpLeftPerfect(6) returns 3, because the perfect tree containing 6 is size 3. and the 'all ones' node is found. And the count of 1's - 1 is the height.

** Note ** that pos is the *one based* position not the zero based index.

func JumpRightSibling 

func JumpRightSibling(pos uint64) uint64

JumpRightSibling moves from pos to the next sibling at the same height

func LeafCount 

func LeafCount(size uint64) uint64

LeafCount returns the number of leaves in the largest mmr whose size is <= the supplied size. See also triecommon/mmr/PeakBitmap

func LeafMinusSpurSum 

func LeafMinusSpurSum(iLeaf uint64) uint64

LeafMinusSpurSum returns the number of peaks preceding iLeaf that the future tree requires.

This is simply the leaf index *minus* the count of nodes cast 'into shade' by the accumulated interior nodes preceding iLeaf.

This corresponds to the number of preceding nodes that will be required to derive future interior nodes. If those preceding nodes are maintained in a stack, this is the current length of the stack.

considering the following mmr 

3            14                             29
           /    \                                \
          /      \                     /          \
         /        \                   /            \
2      6 .      .  13                21            28
      /   \       /   \             / . \         /   \
1    2     5     9     12         17     20     24     27
    / \  /  \   / \    /  \      /  \   / \     / \ . ./ \
   0   1 3   4  7   8 10   11  15   16 18  19  22  23 25  26 MMR INDICES
   0 . 1 2 . 3  4   5  6    7 . 8 .  9 10  11  12  13 14  15 LEAF INDICES

We start by adding all 11, which as we are zero based is just 11 directly. Then there are (11 - 1) / 2 spurs which are _at least_ 1 long There are a remaining 5 / 2 which are at _at least_ 2 long Then finally there is 2 /2 which is _at least_ 3 long All the 'odd' leafs have 'zero' length spurs

So we are accounting for all the spurs in parallel, and reducing the set of spurs in play on each round. This means the 'count' to subtract is exactly the number of spurs remaining in the set (ie we are always 1 x set length). Due to the binary nature of the tree, the set reduction is just dividing the current number of spurs by 2 and the count to subtract is exactly the result of that.

func LeftAncestors 

func LeftAncestors(i uint64) []uint64

func LeftChild 

func LeftChild(pos uint64) (uint64, bool)

LeftChild returns the position of the top most left child of parent pos. If pos is at height 0 it returns false (and true otherwise)

So, some examples given in the diagram below: 

pos 18 has height 1, and 18 - (1 << 1) =  18 - 2 = 16.
pos 14 has height 2, and 14 - (1 << 2) =  14 - 4 = 10.

3            15
           /    \
          /      \
         /        \
2       7          14
      /   \       /   \
1    3     6    10     13      18
    / \  /  \   / \   /  \    /  \
0  1   2 4   5 8   9 11   12 16   17

func LeftPosForHeight 

func LeftPosForHeight(height uint64) uint64

LeftPosForHeight returns the position that is 'most left' for the given height. Eg for height 0, it returns 0, for height 1 it returns 2, for 2 it returns 6. Note that these are always values where the corresponding 1 based position has 'all ones' set.

func Log2Uint32 

func Log2Uint32(num uint32) uint32

func Log2Uint64 

func Log2Uint64(num uint64) uint64

Log2Uint64 efficiently computes log base 2 of num

func MaxPeakHeight 

func MaxPeakHeight(i uint64) uint64

MaxPeakHeight obtains the hight index of the highest (and left most peak) for the mmr index i

func ParentOffset 

func ParentOffset(height uint64) uint64

func PeakBagRHS 

func PeakBagRHS(
	store indexStoreGetter, hasher hash.Hash, pos uint64, peaks []uint64) ([][]byte, error)

PeakBagRHS collects the peaks for BagPeaksRHS in the right order for hashing

func Peaks 

func Peaks(mmrSize uint64) []uint64

Peaks returns the array of mountain peaks in the MMR. This is completely deterministic given a valid mmr size. If the mmr size is invalid, this function returns nil.

It is guaranteed that the peaks are listed in ascending order of position value. The highest peak has the lowest position and is listed first. This is a consequence of the fact that the 'little' 'down range' peaks can only appear to the 'right' of the first perfect peak, and so on recursively.

Note that as a matter of implementation convenience and efficency the peaks are returned as *one based positions*

So given the example below, which has an mmrSize of 17, the peaks are [15, 18] 

3            15
           /    \
          /      \
         /        \
2       7          14
      /   \       /   \
1    3     6    10     13      18
    / \  /  \   / \   /  \    /  \
0  1   2 4   5 8   9 11   12 16   17

func PeaksBitmap 

func PeaksBitmap(mmrSize uint64) uint64

PeakMap returns a bit mask where a 1 corresponds to a peak and the position of the bit is the height of that peak. The resulting value is also the count of leaves. This is due to the binary nature of the tree.

For example, with an mmr with size 19, there are 11 leaves 

         14
      /       \
    6          13
  /   \       /   \
 2     5     9     12     17
/ \   /  \  / \   /  \   /  \

0 1 3 4 7 8 10 11 15 16 18

PeakMap(19) returns 0b1011 which shows, reading from the right (low bit), there are peaks, that the lowest peak is at height 0, the second lowest at height 1, then the next and last peak is at height 3.

If the provided mmr size is invalid, the returned map will be for the largest valid mmr size < the provided invalid size.

func PeaksLHS 

func PeaksLHS(store indexStoreGetter, pos uint64, peaks []uint64) ([][]byte, error)

PeaksLHS collects the peaks to the left of position pos into a flat sequence

So for the following tree and pos=25 we would get 

[15, 22]

3            15
           /    \
          /      \
         /        \
2       7          14             22
      /   \       /   \          /   \
1    3     6    10     13      18      21      25
    / \  /  \   / \   /  \    /  \    /  \    /   \
0  1   2 4   5 8   9 11   12 16   17 19   20 23   24 26

func PosHeight 

func PosHeight(pos uint64) uint64

PosHeight is used when position is a 1 based count

func SiblingOffset 

func SiblingOffset(height uint64) uint64

SiblingOffset returns the offset to the sibling at the given height.

func SpurHeightLeaf 

func SpurHeightLeaf(iLeaf uint64) uint64

SpurHeightLeaf returns the number of nodes 'above' and to the *left* of the provided leaf index

Notice this is the leaf index as tho the leaves were in their own array rather than the mmr index

considering the following mmr 

3            14                             29
           /    \                                \
          /      \                     /          \
         /        \                   /            \
2      6 .      .  13                21            28
      /   \       /   \             / . \         /   \
1    2     5     9     12         17     20     24     27
    / \  /  \   / \    /  \      /  \   / \     / \ . ./ \
   0   1 3   4  7   8 10   11  15   16 18  19  22  23 25  26 MMR INDICES
   0 . 1 2 . 3  4   5  6    7 . 8 .  9 10  11  12  13 14  15 LEAF INDICES

iLeaf = 3 returns 2, iLeaf 7 returns 3, iLeaf 9 returns 1 Notice that all the even numbered iLeaf, eg 2, 4, 6, 8 all return 0,

func SpurSumHeight 

func SpurSumHeight(height uint64) uint64

SpurSumHeight counts the interior 'spur' nodes required for the given height The height is typically relative to the massif height.

Note that the count *including* the last spur is obtained by adding the argument height to the result See doc.go SpurSumHeight for ascii art and extended explanation

Each round i, starting at 1, calculates the *number* of spurs with height i, and multiplies by the length of that spur. the length of a spur is also its height which is also i.

This technique also forms the basis of a fairly efficient, O log base 2 n ish, method to obtain the tree index from a leaf index.

Mathjax: 

\(sum = {\sum_{i=1}^{h-1}} 2^{h-1}/2^{i} * i\)

=> \(sum = {\sum_{i=1}^{h-1}} 2^{h-1-i} * i\)

And as these are all power 2 operations, we can just shift

func TreeIndex 

func TreeIndex(iLeaf uint64) uint64

TreeIndex returns the mmr index of the i'th leaf It can also be used to calculate the sum of all the 'alpine nodes' in the mmr blobs preceding the blob if the blob index is substituted for iLeaf

func VerifyConsistency 

func VerifyConsistency(
	hasher hash.Hash, peakHashesA [][]byte,
	proof ConsistencyProof, rootA []byte, rootB []byte) bool

VerifyConsistency returns true if the mmr log update from mmr a to mmr b is append only. This means that the new log contains an exact copy of the previous log, with any new nodes appended after. The proof is created by datatrails/forestrie/triecommon/mmr/IndexConsistencyProof

The proof comprises an single path which contains an inclusion proof for each peak node in the old mmr against the new mmr root. As all mmr interior nodes are committed to their mmr position when added, this is sufficient to show the new mmr contains an exact copy of the previous. And so can only be the result of append operations.

There is, of course, some redundancy in the path, but accepting that allows re-use of VerifyInclusion for both consistency and inclusion proofs.

func VerifyFirstInclusionPath 

func VerifyFirstInclusionPath(
	mmrSize uint64, hasher hash.Hash, leafHash []byte, iNode uint64, proof [][]byte, root []byte,
) (bool, int)

VerifyFirstInclusionPath process the proof until it re-produces the root

This method exists for the situation where multiple, possibly related, proofs are catenated together in the same path. As they are in log consistency proofs. See datatrails/forestrie/triecommon/mmr/VerifyInclusion for further details.

Returns 

true and the length of the verified path in proof on success.
false if it reaches the end of proof.

func VerifyInclusion 

func VerifyInclusion(
	mmrSize uint64, hasher hash.Hash, nodeHash []byte, iNode uint64, proof [][]byte, root []byte,
) bool

VerifyInclusion returns true if the provided proof demonstrates inclusion of nodeHash at position iLeaf+1

proof and root should be obtained via IndexProof and GetRoot respectively.

Remembering that the proof layout is this: 

[local-peak-proof-i, right-sibling-of-i, left-of-i-peaks-reversed]

And given the following MMR 

3            15
           /    \
          /      \
         /        \
2       7          14             22
      /   \       /   \          /   \
1    3     6    10     13      18      21      25
    / \  /  \   / \   /  \    /  \    /  \    /   \
0  1   2 4   5 8   9 11   12 16   17 19   20 23   24 26

Note that only the local-peak-proof-i elements will include the commitment to the number of descendent tree nodes. This means we must include H(pos) for each step in local-peak-proof-i, but then exclude it in all the others.

So if we have a proof for leaf position 17 (iLeaf=16) the proof will be composed of the local peak proof for 17, which is 

[ValueAt(16), ValueAt(21), Bagged-Peaks-RHS, Reveresed-LHS-Peaks]

To correctly account for the position in the proof, we need to pre-pend the position for each element in the local peak proof:

H(22 | V(21) | H(18|leaf|V(16)))

Remembering that, confusingly, we always include the value for the 'right' node first despite the fact that reading order makes this seem 'on the left'

Types

type ConsistencyProof 

type ConsistencyProof struct {
	MMRSizeA uint64
	MMRSizeB uint64
	Path     [][]byte
}

ConsistencyProof describes a proof that the merkle log defined by size a is perfectly contained in the log described by size b. This structure aligns us with the consistency proof format described in this ietf draft: https://datatracker.ietf.org/doc/draft-ietf-cose-merkle-tree-proofs/ The proof should be verified against a previously signed root for the mmr size a and the root of the proposed log defined by size b.

A reference introducing the concept of consistency proofs in merkle trees: https://pangea.cloud/docs/audit/merkle-trees#outline-consistency-proof

func IndexConsistencyProof 

func IndexConsistencyProof(
	mmrSizeA, mmrSizeB uint64, store indexStoreGetter, hasher hash.Hash,
) (ConsistencyProof, error)

IndexConsistencyProof creates a proof that mmr B appends to mmr A. Our method works by generating inclusion proofs for each of the peaks of A. This method results in a proof path that has some redundancy in it, but permits re-use of the inclusion proof verification method.

As each peak is an interior node, and as each interior node commits to the number of nodes under it (the count of nodes at that point) there is only one possible location the node can exist in the tree. If node x is in both mmr A and mmr B then it is included in exactly the same position.

Verification will first show that the root of A can be re-produced from MMR B, and then proceed to checking the inclusion proofs for the A peaks in mmr B.

type ConsistencyProofLocal 

type ConsistencyProofLocal struct {
	LogIndex   uint64
	Path       [][]byte
	SizeA      uint64
	PeakIndexA uint64
	// The Path proof is identical in mmr size = A and size = B up to Path[HeightA]
	HeightA    uint64
	SizeB      uint64
	PeakIndexB uint64
}

func IndexProofLocalExtend 

func IndexProofLocalExtend(mmrSizeA, mmrSizeB uint64, store indexStoreGetter, i uint64) (ConsistencyProofLocal, error)

IndexProofLocalExtend produces a proof which can verify for two mmr sizes It shows that the proof for mmrSizeB is an *extention* of the proof for mmrSizeA.

type NodeAppender 

type NodeAppender interface {
	Get(i uint64) ([]byte, error)
	Append(value []byte) (uint64, error)
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.