Subject: Re: [Trans] Verifying inclusion proof

From: Adam Eijdenberg <[email-masked]>
Date: Thu, 02 Jul 2015 18:37:26 +0000

On Tue, Jun 30, 2015 at 5:30 AM Ben Laurie <[email-masked]> wrote:

> > That document doesn't appear to be referenced in 6962bis, nor would it, I
> > assume, answer the question "how is the inclusion proof represented in
> the
> > response to get-sth-consistency".
>
> Fair enough. Do you have proposed text?
>

While I think the RFC (section 2.1.2) is quite clear enough on how the
inclusion proof is represented in the response to get-sth-consistency, what
I found very difficult is how to actually apply it to verify consistency.

I wrote the following description of an algorithm I adapted from the
open-source code that I believe is correct.  Would that be helpful?

To verify the consistency of a Merkle tree given this output the following
algorithm may be used:

1. If first is a power of 2, then prepend the consistency array with the
Merkle tree hash from the existing STH for the first tree size.

2. Set "fn" to (first - 1) and "sn" to (second - 1).

3. If LSB(fn) is set, then right-shift both fn and sn equal times until
LSB(fn) is not set.

4. Set "first_hash" and "second_hash" to the first value in the consistency
array.

5. For each subsequent value in the consistency array:

   If the LSB(fn) is set, or if fn is equal to sn, then:

   a. Apply the current value of the consistency array to the left of both
the first_hash and second_hash to compute a new first_hash and second_hash
respectively.
   b. If LSB(fn) is not set, then right-shift both fn and fn equal times
until LSB(fn) is set.

   Otherwise:

   c. Apply the current value of the consistency array to the right of just
the second_hash to compute a new second_hash.

   Finally, right-shift both fn and sn one time.

After completing iterating through the consistency array as described above
first_hash and second_hash should be compared against the Merkle tree
hashes for the existing STHs for first and second respectively.

>
> _______________________________________________
> Trans mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/trans
>

---

From: Adam Eijdenberg <[email-masked]>
Date: Mon, 06 Jul 2015 19:22:18 +0000

To close this thread out, there were some errors in my previous code and
algorithms in this thread.  They have been corrected and added under
section 5.5 in the new version of the Internet Draft published earlier
today:
https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-08#section-5.5

I hope the new section is helpful for client implementors.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 7 Jul 2015 14:09:19 +0100

On 6 July 2015 at 20:22, Adam Eijdenberg <[email-masked]> wrote:
> algorithms in this thread.  They have been corrected and added under section
> 5.5 in the new version of the Internet Draft published earlier today:

BTW, Adam also implemented the algorithms to test them, you can find
them here: https://github.com/google/certificate-transparency-rfcs/blob/master/test_rfc_algorithms.py.

---

From: Ondrej Mikle <[email-masked]>
Date: Tue, 07 Jul 2015 17:48:59 +0200

> them here: https://github.com/google/certificate-transparency-rfcs/blob/master/test_rfc_algorithms.py.

Thank you all, the new text and code snippets mentioned in this thread
do make the auditing much clearer.

Ondrej