summaryrefslogtreecommitdiff
path: root/tools/certtools.py
diff options
context:
space:
mode:
authorMagnus Ahltorp <map@kth.se>2015-02-19 16:23:25 +0100
committerMagnus Ahltorp <map@kth.se>2015-02-19 16:23:25 +0100
commit16d405f4d696c3d01785b644678261acb0e9ad3a (patch)
tree68a427e953c270766b2c4a510d81b7f13abe4222 /tools/certtools.py
parent6e5730c8d7eecec7314c15419aff1112960398bb (diff)
Added verification of consistency proofs
Diffstat (limited to 'tools/certtools.py')
-rw-r--r--tools/certtools.py89
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)