Re: [Trans] Verifying inclusion proof

[Adam Eijdenberg <[e-mail]>]

Hi Ondrej,

I had the exact same question last week when I started wanted to verify
get-proof-by-hash.  It turns out that you actually can figure out which is
applied to the left and the right by looking the bits in the index of the
log entry that you are requesting proof for.  I found it easier to describe
in code than words.  Take a look at the following Python that fetches an
arbitrary entry from an arbitrary log, then fetches the current STH, then
requests an inclusion proof and finally verifies that proof.

I hope that helps.

Cheers, Adam


import urllib, urllib2, json, base64, hashlib

# Entry to play with
log_entry = 438942
log = 'ct.googleapis.com/pilot'

# Get the merkle tree leaf and b64 decode it
entries = json.loads(urllib2.urlopen('https://%s/ct/v1/get-entries?%s' %
(log, urllib.urlencode({'start': log_entry, 'end': log_entry}))).read())
mtl = base64.b64decode(entries['entries'][0]['leaf_input'])

# Get current STH
sth = json.loads(urllib2.urlopen('https://%s/ct/v1/get-sth' % log).read())

# Create the leaf hash
leaf_hash = hashlib.sha256(chr(0) + mtl).digest()

# Fetch proof that the leaft hash is included in the current STH
url = 'https://%s/ct/v1/get-proof-by-hash?%s' % (log,
urllib.urlencode({'hash': base64.b64encode(leaf_hash), 'tree_size':
sth['tree_size']}))
proof = json.loads(urllib2.urlopen(url).read())

# Derive the sha256 root hash based on the leaf_hash and the audit_proof
node = leaf_hash
idx = log_entry
for p in proof['audit_path']:
  if idx & 1:
    node = hashlib.sha256(chr(1) + base64.b64decode(p) + node).digest()
  else:
    node = hashlib.sha256(chr(1) + node + base64.b64decode(p)).digest()
  idx >>= 1

if node == base64.b64decode(sth['sha256_root_hash']):
  print 'Log proved inclusion'
else:
  print 'Fail.'



On Fri, Jun 26, 2015 at 7:30 AM Ondrej Mikle <[e-mail]> wrote:

> Pardon me if I am asking something obvious, but I'm missing one piece of
> information for inclusion proof verification - the "placement" of each
> node returned from "get-proof-by-hash" method in audit_path list
> (whether it's left subtree or right subtree).
>
> Since the hashing of concatenation of strings is not commutative, the
> auditor needs to put the two partial tree hashes in correct order to get
> to the correct root hash.
>
> I'd guess the placement of the missing nodes from audit_path could be
> derived from leaf_index and tree_size, but can't see a straightforward
> way to do it. The reference client does not implement this verification
> either.
>
> Ondrej
>
> _______________________________________________
> Trans mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/trans
>