public inbox for nncp-devel@lists.cypherpunks.ru
Atom feed
From: Sergey Matveev <stargrave@stargrave•org>
To: nncp-devel@lists.cypherpunks.ru
Subject: Re: MTH implementation
Date: Tue, 31 Oct 2023 23:38:18 +0300 [thread overview]
Message-ID: <ZUFlu788VvgRS3-D@stargrave.org> (raw)
In-Reply-To: <87zfzyhe61.fsf@complete.org>
[-- Attachment #1: Type: text/plain, Size: 2076 bytes --]
Greetings!
*** John Goerzen [2023-10-31 12:41]:
>The major thing I'm still puzzled about is writing a compatible Markle
>tree hash. There are various libraries for doing this, but it looks
>like the one in NNCP is home-grown and I'm scratching my head at the
>source code.
I did not find any Merkle-tree library with the ability to "prepend"
some data to partly existing tree and that will "fold" leaves/nodes
that are "ready". So indeed wrote my own one.
Actually that is pretty simple thing, does not requiring any
cryptography knowledge or anything complex. http://www.nncpgo.org/MTH.html
Instead of just hashing the whole data, you split it on 128KiB pieces
and hash each piece independently. But intead of ordinary pure
BLAKE3-256 hash, you use its keyed variant (I assume any BLAKE3
implementation library provides that option) with key="NNCP MTH LEAF".
Then you just hash each pair of resulting hashes with another BLAKE3-256
with the key="NNCP MTH NODE". And repeat that node hashing procedure
until only the single hash stays.
If there is only single block of data, then it is duplicated (not a
problem in NNCP usage context, where encrypted packets are
pseudorandom), to create two leaves. If there are no blocks, then hash
of the zero string is used as a leaf (and duplicated too). That are just
corner cases.
nncp/src/mth.go has so-called MTHFat implementation, that is just a
trivial implementation that keeps all hashes in memory all the time. Can
be used as an example. Complications with MTH appear only if you want to
start "hashing" data not from the beginning, but from some offset,
generating the tree from somewhere in the middle, folding some of the
nodes to save the memory and then "prepending" missing data from the
beginning to it. This is the case where you resumed download of some
file, automatically hash its part and after download finish you just
read from the disk its missing beginning.
--
Sergey Matveev (http://www.stargrave.org/)
OpenPGP: 12AD 3268 9C66 0D42 6967 FD75 CB82 0563 2107 AD8A
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]
prev parent reply other threads:[~2023-10-31 20:38 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-10-31 17:41 Updates on NNCP stuff John Goerzen
2023-10-31 20:03 ` Yggdrasil v0.5 dependency update Sergey Matveev
2023-11-02 23:23 ` John Goerzen
2023-10-31 20:38 ` Sergey Matveev [this message]