mmr

package module
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Nov 1, 2024 License: MIT Imports: 10 Imported by: 5

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrProofLenTooLarge = errors.New("proof length value is too large")
	ErrPeakListTooShort = errors.New("the list of peak values is too short")
)
View Source 
var (
	ErrAccumulatorProofLen = errors.New("a proof for each accumulator is required")
)
View Source 
var (
	ErrConsistencyCheck = errors.New("consistency check failed")
)
View Source 
var (
	ErrNewLogSizeMustBeGreater = errors.New("the new log size must be greater than the previous")
)
View Source 
var (
	ErrNotFound = errors.New("not found")
)
View Source 
var (
	ErrVerifyInclusionFailed = errors.New("verify inclusion failed")
)

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 CheckConsistency 

func CheckConsistency(
	store indexStoreGetter, hasher hash.Hash,
	mmrSizeA, mmrSizeB uint64, peakHashesA [][]byte) (bool, [][]byte, error)

CheckConsistency verifies that the current state mmrSizeB is consistent with the provided accumulator for the earlier size A The provided accumulator (peakHashesA) should be taken from a trusted source, typically a signed mmr state.

See VerifyConsistency for more.

func CheckConsistencyBagged added in v0.1.0 

func CheckConsistencyBagged(
	store indexStoreGetter, hasher hash.Hash,
	cp ConsistencyProof, rootA []byte) (bool, []byte, error)

CheckConsistencyBagged is used to check that a new log update is consistent With respect to some previously known "bagged" root and the current store.

func ConsistentRoots added in v0.1.0 

func ConsistentRoots(hasher hash.Hash, ifrom uint64, accumulatorfrom [][]byte, proofs [][][]byte) ([][]byte, error)

ConsistentRoots is supplied with the accumulator from which consistency is being shown, and an inclusion proof for each accumulator entry in a future MMR state.

The algorithm recovers the necessary prefix (peaks) of the future accumulator against which the proofs were obtained. It is typical that many nodes in the original accumulator share the same peak in the new accumulator. The returned list will be a descending height ordered list of elements from the accumulator for the consistent future state. It may be exactly the future accumulator or it may be a prefix of it.

The order of the roots returned matches the order of the nodes in the accumulator.

Args:

  • ifrom the last node index of the the complete MMR from which consistency was proven.
  • accumulatorfrom the node values correponding to the peaks of the accumulator at MMR(sizeA)
  • proofs the inclusion proofs for each node in accumulatorfrom in MMR(sizeB)

func FirstMMRSize added in v0.0.2 

func FirstMMRSize(mmrIndex uint64) uint64

FirstMMRSize returns the first complete MMRSize that contains the provided mmrIndex. mmrIndices are used to identify nodes. mmrSizes are the result of *adding* nodes to mmr's, and, because of adding the back fill nodes for the leaves, the range of valid sizes is not continuous. Typically, it is possible to "do the right thing" with just LeafCount, but its use is error prone because of this fact.

The outputs of this function for the following mmrIndices are 

[1, 3, 3, 4, 7, 7, 7, 8, 10, 10, 11]

2        6
       /   \
1     2     5      9
     / \   / \    / \
0   0   1 3   4  7   8 10

func GetLeafProofRoot added in v0.1.0 

func GetLeafProofRoot(peakHashes [][]byte, proof [][]byte, mmrSize uint64) ([]byte, error)

GetLeafProofRoot gets the appropriate peak root from peakHashes for a leaf proof, See GetProofPeakRoot

func GetProofPeakIndex added in v0.1.0 

func GetProofPeakIndex(mmrSize uint64, d int, heightIndex uint8) int

GetLeafProofRoot gets the compressed accumulator peak index for a leaf proof, See GetProofPeakRoot

func GetProofPeakRoot added in v0.1.0 

func GetProofPeakRoot(mmrSize uint64, mmrIndex uint64, peakHashes [][]byte, proofLen int) ([]byte, error)

GetProofPeakRoot returns the peak hash for sub tree committing any node.

This is a convenience for use when the caller does not have the heightIndex naturaly from other operations.

A proof for node 2 would be [5], and the peak list for mmrSize 11 would be 

[6, 9, 10]

To obtain the appropriate root to verify a proof of inclusion for node 2 call this function with: 

peakHashes: [H(6), H(9), H(10)]
proofLen: 1
mmrSize: 11
heightIndex: 1

The returned peak root will be H(6)

For node 7, mmrIndex would be 7, all other parameters would remain the same and the returned value would be H(9) 

2        6
       /   \
1     2     5      9
     / \   / \    / \
0   0   1 3   4  7   8 10

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 HashPosPair64 added in v0.1.0 

func HashPosPair64(hasher hash.Hash, pos uint64, a []byte, b []byte) []byte

HashPosPair64 returns H(pos || a || b) ** the hasher is reset **

func HashWriteUint64 

func HashWriteUint64(hasher hash.Hash, value uint64)

HashWriteUInt64 writes a uint64 to a hasher in bigendian layout - most significant byte at lowest address/storage location

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 HeightSize 

func HeightSize(height uint64) uint64

HeightSize returns the size of the mmr with the provided height

func IncludedRoot added in v0.1.0 

func IncludedRoot(hasher hash.Hash, i uint64, nodeHash []byte, proof [][]byte) []byte

IncludedRoot calculates the accumulator peak for the provided proof and node value. Note that both interior and leaf nodes are handled identically

Arguments:

  • i is the index the nodeHash is to be shown at
  • nodehash the value whose inclusion is to be shown
  • proof is the path of ibling values committing i. They recreate the unique accumulator peak that committed i to the MMR state from which the proof was produced.

func InclusionProof added in v0.1.0 

func InclusionProof(store indexStoreGetter, mmrLastIndex uint64, i uint64) ([][]byte, error)

IndexPath collects the merkle proof mmr index i

For the following index tree, and i=15 with mmrSize = 26 we would obtain the path

[H(16), H(20)]

Because the accumulator peak committing 15 is 21, and given the value for 15, we only need 16 and then 20 to verify the proof. 

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 InclusionProofBagged added in v0.1.0 

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

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

It relies on the methods InclusionProofLocal, 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)
   InclusionProofPath

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 InclusionProofLocal added in v0.1.0 

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

InclusionProofLocal 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 InclusionProofLocalOld added in v0.1.0 

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

InclusionProofLocalOld is depreciated and retained only for testing See InclusionProofLocal instead

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 InclusionProofPath added in v0.1.0 

func InclusionProofPath(mmrLastIndex uint64, i uint64) ([]uint64, error)
returns the mmr indices identifying the witness nodes for mmr index i

This method allows tooling to individually audit the proof path node values for a given index.

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 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 position so as to avoid ever having to materialize the whole tree. It 'jumps left' by the size of the largest perfect tree which would precede 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 largest perfect tree preceding 13 is 7. The next jump, JumpLeftPerfect(6) returns 3, because the perfect tree preceding 6 is size 3. and the 'all ones' node is found. And the count of 1's - 1 is the index 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 merklelog/mmr/PeakBitmap

This can safely be use to obtain the leaf index *only* when size is known to be a valid mmr size. Typically just before or just after calling AddHashedLeaf If in any doubt, instead use LeafIndex() + 1

func LeafIndex added in v0.0.2 

func LeafIndex(mmrIndex uint64) uint64

func LeafMinusSpurSum 

func LeafMinusSpurSum(leafIndex 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 MMRIndex added in v0.1.0 

func MMRIndex(leafIndex uint64) uint64

MMRIndex returns the node index for the leaf e

Args:

  • leafIndex: the leaf index, where the leaves are numbered consequtively, ignoring interior nodes.

Returns: 

The mmr index for the element leafIndex

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 PeakHashes added in v0.1.0 

func PeakHashes(store indexStoreGetter, mmrIndex uint64) ([][]byte, error)

func PeakIndex added in v0.1.0 

func PeakIndex(leafCount uint64, d int) int

PeakIndex returns the index of the peak accumulator for the peak with the provided proof length.

Given: 

leafCount - the count of elements in the current accumulator, eg LeafCount(mmrIndex).
d - the length of the proof of any element in the mmr identified by leafCount

Return 

The index of the accumulator peak produced by a valid inclusion proof of length d

Note that leafCount identifies the mmr state, not the element.

For interior nodes, you must account for the height by adding IndexHeigh(mmrIndex) to the proof length d.

Example: 

	peaks = PosPeaks(18) = [14, 17]
	peakBits = LeafCount(18) = 101
 	1 = d = proof len for 6
	2 = IndexHeight(6)
	peaks[PeakIndex(peakBits, 1 + 2)] == 14

For this MMR: 

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

func Peaks 

func Peaks(mmrIndex uint64) []uint64

Peaks returns the array of mountain peak indices in the MMR.

This is completely deterministic given a complete mmr index. If the mmr index is not complete, or is otherwise invalid, is invalid, this function returns nil.

The peaks are listed in ascending order of mmr index value. The highest peak has the lowest index 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.

Given the example below, which has an mmrSize of 10, the peaks are [6, 9]: 

2        6
       /   \
1     2     5      9
     / \   / \    / \
0   0   1 3   4  7   8

func PeaksBitmap 

func PeaksBitmap(mmrSize uint64) uint64

PeaksBitmap 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 PeaksOld added in v0.1.0 

func PeaksOld(mmrSize uint64) []uint64

PeaksOld is deprecated and retained only for reference and testing.

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 PosHeight 

func PosHeight(pos uint64) uint64

PosHeight is used when position is a 1 based count

func PosPeaks added in v0.1.0 

func PosPeaks(mmrSize uint64) []uint64

PosPeaks is a depricated version of peaks which returns an array of mmr positions rather than indices.

func SiblingOffset 

func SiblingOffset(height uint64) uint64

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

func SpurHeightLeaf 

func SpurHeightLeaf(leafIndex 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 TopHeight added in v0.1.0 

func TopHeight(i uint64) uint64

TopHeight returns the index height of the largest perfect peak contained in, or exactly, pos This is essentially a ^2 *floor* function for the accumulation of bits: 

TopHeight(0) = TopHeight(1) = 0
TopHeight(1) = TopHeight(2) = TopHeight(3) = TopHeight(4) = TopHeight(5) = 1
TopHeight(6) = 2

2       6
      /   \
1    2     5     9
    / \  /  \   / \
0  0   1 3   4 7   8 10

func TopPeak added in v0.1.0 

func TopPeak(i uint64) uint64

TopPeak returns the smallest, leftmost, peak containing *or equal to* i

This is essentially a ^2 *floor* function for the accumulation of bits: 

TopPeak(0) = TopPeak(1) = 0
TopPeak(1) = TopPeak(2) = TopPeak(3) = TopPeak(4) = TopPeak(5) = 2
TopPeak(6) = 6

2       6
      /   \
1    2     5     9
    / \  /  \   / \
0  0   1 3   4 7   8 10

func TreeIndexOld added in v0.1.0 

func TreeIndexOld(leafIndex 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,
	cp ConsistencyProof, peaksFrom [][]byte, peaksTo [][]byte) (bool, [][]byte, error)

VerifyConsistency verifies the consistency between two MMR states.

The MMR(A) and MMR(B) states are identified by the fields MMRSizeA and MMRSizeB in the proof. peakHashesA and B are the node values corresponding to the MMR peaks of each respective state. The Path in the proof contains the nodes necessary to prove each A-peak reaches a B-peak. The path contains the inclusion proofs for each A-peak in MMR(B). 

    MMR(A):[7, 8]      MMR(B):[7, 10, 11]
 2       7                7
       /   \            /   \
 1    3     6          3     6    10
     / \  /  \        / \  /  \   / \
 0  1   2 4   5 8    1   2 4   5 8   9 11

	Path MMR(A) -> MMR(B)
	7 in MMR(B) -> []
	8 in MMR(B) -> [9]
	Path = [[], [9]]

func VerifyConsistencyBagged added in v0.1.0 

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

VerifyConsistencyBagged 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/go-datatrails-merklelog/merklelog/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 VerifyFirstInclusionPathBagged added in v0.1.0 

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

VerifyFirstInclusionPathBagged process the proof until it re-produces the "bagged" root of the MMR

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, when they are proven against a mono root. See datatrails/go-datatrails-merklelog/merklelog/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(
	store indexStoreGetter, hasher hash.Hash, mmrSize uint64, leafHash []byte, iNode uint64, proof [][]byte,
) (bool, error)

func VerifyInclusionBagged added in v0.1.0 

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

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

proof and root should be obtained via InclusionProof 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'

func VerifyInclusionOld added in v0.1.0 

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

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

proof and root should be obtained via InclusionProof 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'

func VerifyInclusionPath added in v0.1.0 

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

VerifyInclusionPath returns true if the leafHash combined with path, reproduces the provided root

To facilitate the concatenated proof paths used for consistency proofs, it returns the count of path elements used to reach the root.

root: The local "peak" root in which leafHash is recorded. This root is a member of the current mmr accumulator, or is itself a node which can be verified for inclusion in a future accumulator.

Types

type ConsistencyProof 

type ConsistencyProof struct {
	MMRSizeA uint64 `cbor:"1,keyasint"`
	MMRSizeB uint64 `cbor:"2,keyasint"`
	// legacy proof format
	PathBagged [][]byte   `cbor:"3,keyasint"`
	Path       [][][]byte `cbor:"4,keyasint"`
}

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(
	store indexStoreGetter, mmrIndexA, mmrIndexB uint64,
) (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.

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 is then performed in terms of the mmr accumulator states MMR(A) and MMR(B) for each "old" peak in MMR(A) we show there is a path to a "new" or "same" peak in MMR(B)

func IndexConsistencyProofBagged added in v0.1.0 

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

IndexConsistencyProofBagged creates a proof that mmr B appends to mmr A. This 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 InclusionProofLocalExtend added in v0.1.0 

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

InclusionProofLocalExtend 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.