Merkle tree generation and proofing

merkle.py

#!/usr/bin/env python
from hashlib import sha256

H = lambda *x: sha256(''.join([str(X) for X in x])).hexdigest()

def merkle_tree(items):
	"""Given an array of items, build a merkle tree"""
	tree = [[H(x) for x in items]]
	while len(tree[-1]) != 1:
		it = iter(tree[-1])
		tree.append([H(item, next(it, item)) for item in it])
	return tree

def merkle_path(item, tree):
	"""Given an item and a tree, return its path"""
	lvl = 0
	itemidx = tree[lvl].index(H(item))
	even = itemidx % 2
	baseidx = itemidx - even
	otheridx = itemidx - 1 if even else idx + 1
	path = [tree[lvl][otheridx]]
	lvl += 1
	while len(tree[lvl]) != 1:
		baseidx = baseidx / 2
		path += tree[lvl][baseidx:baseidx+2]
		lvl += 1
	return path

def merkle_proof(item, path, root):
	path.insert(0 if H(item, path[0]) == path[0] else 1, item)
	it = iter(path)
	for x in it:
		x = H(x, next(it))
	return x == root

X = merkle_tree(range(0, 15))
print "Tree:", X
print "Height:", len(X) - 1
P = merkle_path(1, X)
print "Path:", P
print "Valid path:", merkle_proof(H(1), P, X[-1][0])