Re: [openpgp] [Cfrg] streamable AEAD construct for stored data?

[Peter Todd <[e-mail]>]

On Fri, Oct 30, 2015 at 11:47:42AM -0700, Andy Lutomirski wrote:
> On Fri, Oct 30, 2015 at 11:32 AM, Taylor R Campbell
> <[e-mail]> wrote:
> > This requires only O(log n) working memory to compute the Merkle tree
> > -- it takes a single pass over the whole input.
> >
> ...which reminds me:
> 
> As far as I know, everyone thinks they know how to do a Merkle tree
> for things like this, but there doesn't seem to be a credible
> standard, and there are at least two modern examples of doing it
> wrong: Amazon's Glacier hash and (unless it changed) Bittorrent's new
> Merkle tree.
> 
> Should CFRG consider standardizing a transport format for hash tree
> verifiers (or proofs or whatever they're called) and for a large blob
> that can be used to efficiently generate the proofs (essentially some
> kind of serialized tree)?  The Sakura construction could be a good
> starting point.  If I were designing such a standard, I would be
> extremely hesitant to start with SHA256 or similar because of the lack
> of personalization, whereas Sakura (and maybe BLAKE2) doesn't have
> this problem.
> 
> Sadly, Sakura doesn't seem to be officially blessed yet.

I wasn't aware of Sakura previously; it does seem very complex which I'm
sure is holding it back.

I had a need for a merkle tree over a list of items with the ability to
efficiency prove the (relative) position of items committed to in the
tree, as well as strict determinism. (for every message there is only
one valid digest) I came up a fairly simple scheme that I'm calling
merkle-mountain-ranges:

https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal/mmr.py

While I didn't write the above with hashing byte strings in mind, by
specifying a block size it could be easily modified to do so. (though be
careful you don't lose the determinism!)

-- 
'peter'[:-1]@petertodd.org
00000000000000000de6dfa01305b9163ad2efd9f72c77c23ebddf62afc18b00