Re: [Trans] Verifying inclusion proof

On Fri, Jun 26, 2015 at 3:29 PM, Ondrej Mikle <ondrej.mikle@nic.cz> 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.
>

Yes, you're quite right.

>
> 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.
>
>
There are a couple of implementations of this in the o/s code base:
C++ is in cpp/merkletree/merkle_verifier.cc
<https://github.com/google/certificate-transparency/blob/master/cpp/merkletree/merkle_verifier.cc>
(see
VerifyPath())
Python is in python/ct/crypto/merkle.py
<https://github.com/google/certificate-transparency/blob/master/python/ct/crypto/merkle.py>
 (see verify_leaf_inclusion())

HTH.

Cheers,
Al.

> Ondrej
>
> _______________________________________________
> Trans mailing list
> Trans@ietf.org
> https://www.ietf.org/mailman/listinfo/trans
>

-- 
Google UK Ltd | 123 Buckingham Palace Road | London SW1W 9SH | Registered
in England Number: 3977902