Can I get a Merkle proof out of blake3?

Matteo Monti

12/23/23, 2:50 PM

The overview of Blake3 states that Blake3 is internally a Merkle tree. Diving a bit deeper into the paper one finds out that Blake3 splits its input in chunks of 1 KiB (1024 B), organizing chunks in a binary tree whose root is used as the Blake3 hash of the input. This makes it fast to compute the Blake3 hash of large inputs taking advantage of an essentially unlimited amount of paralelization, being it from SIMD or actual parallel threads (in fact, the blake3 crate both takes advantage of SIMD and offers rayon-based multi-threaded hashing methods).

Despite Blake3 being internally a Merkle tree, however, I cannot seem to find a way in the blake3 crate to actually produce and verify Merkle proofs.

If I am hashing, say, 1 MiB worth of input with Blake3, it should not impossible to produce a Merkle proof, verifiable against the Blake3 hash of the whole input, for any of the 1024 contiguous chunks of 1024 bytes of which the input is composed. Right?

I am wondering if the lack of this feature comes from it simply being not (yet?) implemented, or because of some security limitation, or?

1 + 0

hash-tree

blake3

Score:2

Crypto

Jack O'Connor

12/24/23, 7:07 AM

These features are implemented in the bao crate, which takes a dependency on blake3. See https://github.com/oconnor663/bao. You might be interested in what Bao calls "slices".

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Can I get a Merkle proof out of blake3?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.