Added verification of consistency proofs

1 files changed, 89 insertions, 0 deletions

diff --git a/tools/certtools.py b/tools/certtools.py
index 31045b9..5b556cf 100644
--- a/tools/certtools.py
+++ b/tools/certtools.py
@@ -461,3 +461,92 @@ def get_intermediate_hash(store, treesize, level, index):
             zf.close()
         assert len(layer0) == lastleaf - firstleaf + 1
         return calculated_hash
+
+def bits(n):
+    p = 0
+    while n > 0:
+        n >>= 1
+        p += 1
+    return p
+
+def merkle_height(n):
+    if n == 0:
+        return 1
+    return bits(n - 1)
+
+def node_above((pathp, pathl), levels=1):
+    return (pathp >> levels, pathl + levels)
+
+def node_even((pathp, pathl)):
+    return pathp & 1 == 0
+
+def node_odd((pathp, pathl)):
+    return pathp & 1 == 1
+
+def node_lower((path1p, path1l), (path2p, path2l)):
+    return path1l < path2l
+
+def node_higher((path1p, path1l), (path2p, path2l)):
+    return path1l > path2l
+
+def node_level((path1p, path1l)):
+    return path1l
+
+def node_outside((path1p, path1l), (path2p, path2l)):
+    assert path1l == path2l
+    return path1p > path2p
+
+def combine_two_hashes((path1, hash1), (path2, hash2), treesize):
+    assert not node_higher(path1, path2)
+    edge_node = (treesize - 1, 0)
+
+    if node_lower(path1, path2):
+        assert path1 == node_above(edge_node, levels=node_level(path1))
+        while node_even(path1):
+            path1 = node_above(path1)
+
+    assert node_above(path1) == node_above(path2)
+    assert (node_even(path1) and node_odd(path2)) or (node_odd(path1) and node_even(path2))
+
+    if node_outside(path2, node_above(edge_node, levels=node_level(path2))):
+        return (node_above(path1), hash1)
+
+    if node_even(path1):
+        newhash = internal_hash((hash1, hash2))
+    else:
+        newhash = internal_hash((hash2, hash1))
+
+    return (node_above(path1), newhash)
+
+def path_as_string(pos, level, treesize):
+    height = merkle_height(treesize)
+    path = "{0:0{width}b}".format(pos, width=height - level)
+    if height == level:
+        return ""
+    return path
+
+def nodes_for_pos(pos, treesize):
+    height = merkle_height(treesize)
+    nodes = []
+    level = 0
+    while pos > 0 and pos & 1 == 0:
+        pos >>= 1
+        level += 1
+    if pos & 1:
+        nodes.append((pos ^ 1, level))
+    #print pos, level
+    while level < height:
+        pos_level0 = pos * (2 ** level)
+        #print pos, level
+        if pos_level0 < treesize:
+            nodes.append((pos, level))
+        pos >>= 1
+        pos ^= 1
+        level += 1
+    return nodes
+
+def verify_consistency_proof(consistency_proof, first, second):
+    chain = zip(nodes_for_pos(first, second), consistency_proof)
+    (_, hash) = reduce(lambda e1, e2: combine_two_hashes(e1, e2, second), chain)
+    (_, oldhash) = reduce(lambda e1, e2: combine_two_hashes(e1, e2, first), chain)
+    return (oldhash, hash)