diff options
| -rw-r--r-- | tools/certtools.py | 26 | ||||
| -rwxr-xr-x | tools/testcase1.py | 11 |
2 files changed, 33 insertions, 4 deletions
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 diff --git a/tools/testcase1.py b/tools/testcase1.py index 415d475..ce322f1 100755 --- a/tools/testcase1.py +++ b/tools/testcase1.py @@ -84,8 +84,15 @@ def get_and_validate_proof(timestamp, chain, leaf_index, nentries): leaf_hash = get_leaf_hash(merkle_tree_leaf) sth = get_sth(baseurl) proof = get_proof_by_hash(baseurl, leaf_hash, sth["tree_size"]) - assert_equal(proof["leaf_index"], leaf_index, "leaf_index") - assert_equal(len(proof["audit_path"]), nentries, "audit_path length") + leaf_index = proof["leaf_index"] + inclusion_proof = [base64.b64decode(e) for e in proof["audit_path"]] + assert_equal(leaf_index, leaf_index, "leaf_index") + assert_equal(len(inclusion_proof), nentries, "audit_path length") + + calc_root_hash = verify_inclusion_proof(inclusion_proof, leaf_index, sth["tree_size"], leaf_hash) + root_hash = base64.b64decode(sth["sha256_root_hash"]) + + assert_equal(root_hash, calc_root_hash, "verified root hash", nodata=True) get_and_check_entry(timestamp, chain, leaf_index) def get_and_check_entry(timestamp, chain, leaf_index): |