Re: [Cfrg] Merkle trees

[Gilles Van Assche <[e-mail]>]

Hi Taylor,

Sorry for the late answer.

On 11/03/2015 09:57 PM, Taylor R Campbell wrote:
> With apologies for my false claim above, I must have skimmed the
> paper[1] too quickly to come to that conclusion -- it was a bit more
> general and abstract than the Blake2 tree-hashing specification.

No problemo. And yes, Sakura is not tight to a particular hash function.

> Do I understand correctly that Sakura is map from tree shape to
> encoding, not necessarily with a fixed number of bytes per message
> chunk or fixed fanout, depth per message length, &c.?

Yes, or "to encodings" since there could be more than one possible
encodings for a given tree shape, given the degrees of freedom that are
foreseen in Sakura. Alternatively, we speak about "Sakura-compatible
modes", where a mode specifies unambiguously how to shape and format the
tree.

> That is, you
> get is something like the following, with, e.g., H = RawSHAKE256 and
> with the shape of the tree specified by the caller, no matter how long
> a, b, and c are?
>
> Sakura-H(a) = H(a || root=1)
> Sakura-H(a || b) =
>   H(H(a || root=0) || H(b || root=0) || nrCVs=2 || interleave=0 || root=1)
> Sakura-H((a || b) || c) =
>   H(H(H(a || root=0) || H(b || root=0) || nrCVs=2 || interleave=0 ||
> root=0)
>     || H(c || root=0)
>     || nrCVs=2
>     || interleave=0
>     || root=1)
>
> If I understand correctly, that suggests that Sakura-H(a || b) is not
> a function of Sakura-H(a), since it is the root (`final') node that is
> distinguished from other (`inner') nodes, not leaf nodes (`message
> hops'?) that are distingushed from branch nodes (`chaining hops'?).
>
> I expect that property from a random oracle -- but it's not as useful
> for deduplication, since the additional storage for a || b can't be
> derived from just the storage index of a, namely Sakura-H(a).

I see your point.

Alternatively to your example above, one could define MyTreeH(a) = H(H(a
|| root=0) || nrCVs=1 || root=1). This way, H(a || root=0) would be a
"hash over chunk a", where this chunk could be reused in other files,
and H(a || root=1) or H(H(a || root=0) || nrCVs=1 || root=1) a "hash
over a file whose full content is composed of chunk a only". In other
words, the root/final flag behaves like domain separation between the
hash of a (complete) file versus the hash of a chunk (not necessarily a
complete file).

Kind regards,
Gilles