nebulouslabs / merkletree Goto Github PK

There are a few sanity checks that could be inserted to verify consistency. There are also a few other manual tests I would like to write to make sure that the complexity of the testing exceeds the complexity of the code.

We should be runinng errcheck. This might cause some grief.
I'm not sure what the best approach to errcheck is, but we definitely have missed a few bugs that would have been caught had we been using errcheck.

But there are also lots of examples of harmless failures in errcheck, it's not clear whether we should be rigorous or find some way to explicitly ignore certain errcheck warnings.

An incomplete proof is any time that the index is greater than the numLeaves. Not testing this case resulted in a bug, caught by fuzzing. The bug has now been fixed but there's not an explicit test exploring incomplete proofs.

It can be used in Metadata Request (to provide a proof for a slice of sector ids) and in Data Request (to provide a proof that a slice of bytes inside a sector belongs to the sector).

The algorithm to make proofs can be adjusted to work with slices instead of single index: just replace "subtree containing the proofIndex" with "subtree overlapping with the proofSlice" in the original algorithm. The new algorithm produces exactly the same proofs for a slice of size 1 as the old one provides for the corresponding proofIndex. That means that the new algorithm is backward compatible.

Here is a demonstration script in Python, which prints proof as a list of slices of leaves.

proofSlice = (3, 5)
numLeaves = 7

def size(st):
    return st[1] - st[0]

def inside(point, st):
    return st[0] <= point < st[1]

def overlaps(st):
    return inside(st[0], proofSlice) or inside(proofSlice[0], st)

stack = []

def combine():
    right = stack.pop()
    left = stack.pop()
    if overlaps(right) and not overlaps(left):
        print(left)
    if overlaps(left) and not overlaps(right):
        print(right)
    st2 = (left[0], right[1])
    stack.append(st2)

for i in range(numLeaves):
    st = (i, i+1)
    stack.append(st)
    while len(stack) > 1 and size(stack[-2]) == size(stack[-1]):
        combine()
while len(stack) > 1:
    combine()