From 81a35a696d813ac5803afe602e549b56a9dfd9c4 Mon Sep 17 00:00:00 2001
From: Magnus Ahltorp <map@kth.se>
Date: Fri, 20 Feb 2015 01:58:17 +0100
Subject: testcase1: Actually verify inclusion proof

---
 tools/certtools.py | 26 ++++++++++++++++++++++++--
 1 file changed, 24 insertions(+), 2 deletions(-)

(limited to 'tools/certtools.py')

diff --git a/tools/certtools.py b/tools/certtools.py
index 11e09bb..fdff0e1 100644
--- a/tools/certtools.py
+++ b/tools/certtools.py
@@ -512,10 +512,11 @@ def path_as_string(pos, level, treesize):
         return ""
     return path
 
-def nodes_for_pos(pos, treesize):
+def nodes_for_subtree(subtreesize, treesize):
     height = merkle_height(treesize)
     nodes = []
     level = 0
+    pos = subtreesize
     while pos > 0 and pos & 1 == 0:
         pos >>= 1
         level += 1
@@ -532,8 +533,29 @@ def nodes_for_pos(pos, treesize):
         level += 1
     return nodes
 
+def nodes_for_index(pos, treesize):
+    height = merkle_height(treesize)
+    nodes = []
+    level = 0
+    pos ^= 1
+    #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)
+    chain = zip(nodes_for_subtree(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)
+
+def verify_inclusion_proof(inclusion_proof, index, treesize, leafhash):
+    chain = zip([(index, 0)] + nodes_for_index(index, treesize), [leafhash] + inclusion_proof)
+    (_, hash) = reduce(lambda e1, e2: combine_two_hashes(e1, e2, treesize), chain)
+    return hash
-- 
cgit v1.1