From 74a4460cba73877830b73742be76cd2bf0d5f47b Mon Sep 17 00:00:00 2001
From: Magnus Ahltorp <map@kth.se>
Date: Thu, 19 Feb 2015 16:23:25 +0100
Subject: Added verification of consistency proofs

---
 tools/certtools.py     | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++
 tools/fetchallcerts.py |  6 ++++
 2 files changed, 95 insertions(+)

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)
diff --git a/tools/fetchallcerts.py b/tools/fetchallcerts.py
index 866bb43..39ffd64 100755
--- a/tools/fetchallcerts.py
+++ b/tools/fetchallcerts.py
@@ -168,6 +168,12 @@ else:
 
 print "calculated root hash", base64.b16encode(calculated_root_hash)
 
+if oldsth and oldsth["tree_size"] > 0 and oldsth["tree_size"] != tree_size:
+    consistency_proof = [base64.decodestring(entry) for entry in get_consistency_proof(args.baseurl, oldsth["tree_size"], tree_size)]
+    (old_treehead, new_treehead) = verify_consistency_proof(consistency_proof, oldsth["tree_size"], tree_size)
+    assert old_treehead == base64.b64decode(oldsth["sha256_root_hash"])
+    assert new_treehead == base64.b64decode(sth["sha256_root_hash"])
+
 if calculated_root_hash != root_hash:
     print "fetched root hash and calculated root hash different"
     sys.exit(1)
-- 
cgit v1.1