On Thu, May 13, 2021 at 03:02:52PM +0000, Rob Stradling wrote:
> On https://datatracker.ietf.org/doc/draft-ietf-trans-rfc6962-bis/ballot/, Ben
> Kaduk wrote:
> > > If m <= k, the right subtree entries D[k:n] only exist in the current
> > > tree. We prove that the left subtree entries D[0:k] are consistent
> > > and add a commitment to D[k:n]:
> > >
> > > SUBPROOF(m, D_n, b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])
> >
> > This 'b' is always 'false', right?
>
> Despite being one of the document authors, I am yet to fully get my head
> around Section 2 (Cryptographic Components), so yesterday I sought help
> off-list from several folks who I'm sure have a better grasp of the crypto.
> Here's what we came up with (which I believe I now understand and agree with!
> :-) ):
>
> Short answer:
> "PROOF(m, D_n) = SUBPROOF(m, D_n, true)" appears just a few lines above, so
> no.
>
> Long answer:
> No. The first substitution of "PROOF(m, D_n)" gives you an invocation of
> SUBPROOF with b=true. As you recurse down, you may reach a call where all
> further recursive calls have b=false, but the base case should be b=true.
> SUBPROOF is defined in four cases. b could be either true or false depending
> on whether and how it was invoked by the third case, fourth case, or the base
> case from the definition of PROOF.
> The SUBPROOF case that Ben's question refers to is for m != n, m <= k, and
> any b.
Thanks, Rob.
I had tentatively reached a similar conclusion yesterday, but didn't get a
chance to remind myself of what the "D[0:m]" referenced in the definition
of the 'b' parameter was.
For what little it's worth, I think my question originated from a
misreading of the surrounding text:
SUBPROOF(m, D[m], false) = {MTH(D[m])}
For m < n, let k be the largest power of two smaller than n. The
subproof is then defined recursively.
If m <= k, the right subtree entries D[k:n] only exist in the current
tree. We prove that the left subtree entries D[0:k] are consistent
and add a commitment to D[k:n]:
SUBPROOF(m, D_n, b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])
If m > k, the left subtree entries D[0:k] are identical in both
trees. We prove that the right subtree entries D[k:n] are consistent
and add a commitment to D[0:k].
SUBPROOF(m, D_n, b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])
I suspect I noticed that there was a literal 'false' in the first and last
SUBPROOF lines, and missed the boundary between the "m==n" case (first
SUBPROOF) and the "m < n" case (last two SUBPROOFs, that handle the m<=k
and m>k sub-cases respectively). If I was thinking that the last two were
both somehow subcases of the first, then it would be natural (but wrong) to
assume that the literal 'false' should be in all three SUBPROOFs.
Sorry to have caused the extra work,
Ben
_______________________________________________
Trans mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/trans
