Re: [Trans] Verifying inclusion proof

On Tue, Jun 30, 2015 at 5:30 AM Ben Laurie <benl@google.com> wrote:

> On 30 June 2015 at 00:04, Matt Palmer <mpalmer@hezmatt.org> wrote:
> > On Mon, Jun 29, 2015 at 12:29:47PM +0100, Ben Laurie wrote:
> >> On 28 June 2015 at 23:06, Matt Palmer <mpalmer@hezmatt.org> wrote:
> >> > On Sun, Jun 28, 2015 at 04:26:51PM +0100, Ben Laurie wrote:
> >> >> On 28 June 2015 at 16:05, Stephen Kent <kent@bbn.com> wrote:
> >> >> > IETF standards need to be unambiguous. Code is very helpful, but
> it is not a
> >> >> > substitute
> >> >> > for a rigorous description of how to resolve the issue that Onderj
> raised.
> >> >>
> >> >> Whilst I am not necessarily opposed to that, there has to be a point
> >> >> at which you stop explaining what can be worked out given existing
> >> >> information. The RFC does state how the hash is calculated, from
> which
> >> >> it is clear what the placement of each node is in the hash
> >> >> calculation.
> >> >
> >> > s/it is clear/it is possible to determine/
> >> >
> >> > I would be in favour of more clarity around exactly how the inclusion
> proof
> >> > is represented; I recall having significant trouble comprehending how
> >> > inclusion proofs "worked", and ended up examining existing
> operational logs
> >> > and using trial and error to determine how the inclusion proof was
> >> > presented.
> >>
> >> Feel free to open a ticket. However, the mechanism for verifying
> >> inclusion in a Merkle tree is widely available in standard texts, for
> >> example 3.3 in
> http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf
> .
> >
> > 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?
>

Would the following text be helpful for /get-proof-by-hash? (I realize the
immediate question refers to get-sth-consistency, I'd be happy to tackle
that next)

To verify the Merkle Tree root hash for the tree_size provided as input, a
client can use the hash provided as input combined with applying the
audit_path and leaf_index returned as output in the following manner (note,
all values must be base64 decoded first):

1. Set the intermediate result "r" to hash.

2. For each "i" from 0 up to LENGTH(audit_path) - 1:

   If the least significant bit of (leaf_index >> i) is set, then:

   a. Set r to HASH(0x01 || audit_path[i] || r)

   otherwise:

   b. Set r to HASH(0x01 || r || audit_path[i])

3. Return r

If "r" is equal to the root hash previously returned by /get-sth for the
same tree_size that was passed as input, then the log has successfully
proven the inclusion of the certificate that the Merkle tree leaf hash was
constructed from.

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