# Blake3 for the new hash function

**URL:** <https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550>\
**Category:** Development\
**Created:** [October 7, 2020, 1:33am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550 "2020-10-07T01:33:12Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![rodarmor](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/rodarmor/32/287_2.png) [@rodarmor](https://discourse.pijul.org/u/rodarmor)\
**Post date:** [October 7, 2020, 1:33am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/1 "2020-10-07T01:33:12Z")

</div>

Blake3 was mentioned [in another thread](https://discourse.pijul.org/t/base-58-base-32/352/7), but I wanted to make a new thread.

I think that Blake3 would be an ideal choice for Pijul’s hash function:

- Blake3 has a fist-class [rust implementation](https://github.com/BLAKE3-team/BLAKE3/), maintained by the authors of the hash function.
- The hashes are 256 bits, so it’s significantly shorter than 512 bit SHA2. There was some mention of a possible security tradeoff going to 256 bits, but I think that 256 bit hashes are currently considered to be secure, for now and the indefinite future.
- Blake3 is very, very fast. It both because it’s a merkle tree hash, which means that it’s highly amenable to parallelism, and because it uses Blake2s, which is a fast primitive.
- Blake3 includes a number of useful modes, in addition to the main hash function, it supports a keyed hash, and a key derivation operation. These might be useful for collision resistant hashing, or key derivation for signature operations.

Blake3 is binary merkle tree hash with 16KiB leaf nodes, which enables a lot of neat possibilities for Pijul:

- Corruption during transmission or storage could be identified and repaired at the block level, instead of having to throw away the entire object.
- Large objects could be synced from multiple locations, by requesting disjoint sets of blocks.

Blake3 is derived from a hash called Bao, which was written by Jack O’Connor, and then later turned into Blake3. Jack is active on Twitter and a few other places. I’m sure he would be interested in seeing Blake3 adopted, and would likely be able to explain any technical points relating to Pijul adopting Blake3.

---

<div class="post-metadata">

**Author:** ![pmeunier](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/pmeunier/32/4_2.png) [@pmeunier](https://discourse.pijul.org/u/pmeunier)\
**Post date:** [October 7, 2020, 6:41am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/2 "2020-10-07T06:41:57Z")

</div>

Thanks! Blake3 is already the hash in the next version of Pijul. There is also a new idea to make “commutative hashes”, in the sense that h(A, B) = h(B, A), but it’s hard to get either A or B from h(A, B), and hard to get B (resp A) from h(A, B) and A (resp B).

---

<div class="post-metadata">

**Author:** ![rodarmor](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/rodarmor/32/287_2.png) [@rodarmor](https://discourse.pijul.org/u/rodarmor)\
**Post date:** [October 7, 2020, 7:01am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/3 "2020-10-07T07:01:48Z")

</div>

> [@pmeunier](#):
>
> Thanks! Blake3 is already the hash in the next version of Pijul.

Sweet, that’s awesome!

> [@pmeunier](#):
>
> There is also a new idea to make “commutative hashes”, in the sense that h(A, B) = h(B, A), but it’s hard to get either A or B from h(A, B), and hard to get B (resp A) from h(A, B) and A (resp B).

What would commutative hashes enable? I’m guessing that `h(xor(h(A), h(B)))` doesn’t work for other reasons?

Can you explain what you mean by “and hard to get B (resp A) from h(A, B) and A (resp B).”? I’m not familiar with the phrase “(resp X)”.

---

<div class="post-metadata">

**Author:** ![rodarmor](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/rodarmor/32/287_2.png) [@rodarmor](https://discourse.pijul.org/u/rodarmor)\
**Post date:** [October 7, 2020, 7:08am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/4 "2020-10-07T07:08:10Z")

</div>

Ah, I think I get it, hard to get B from h(A, B) and A, and hard to get A from h(A, B) and B.

---

<div class="post-metadata">

**Author:** ![pmeunier](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/pmeunier/32/4_2.png) [@pmeunier](https://discourse.pijul.org/u/pmeunier)\
**Post date:** [October 7, 2020, 7:52am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/5 "2020-10-07T07:52:18Z")

</div>

> [@rodarmor](#):
>
> Ah, I think I get it, hard to get B from h(A, B) and A, and hard to get A from h(A, B) and B.

That’s right.

> [@rodarmor](#):
>
> What would commutative hashes enable? I’m guessing that `h(xor(h(A), h(B)))` doesn’t work for other reasons?

Right. I forgot to add that I also want to compute h(A, B) from (h(A), B) or from (h(B), A). This property means that:

- a _state_ in Pijul can be described by a hash h(…), and the next state after applying patch B can be computed from h(…) and B.
- Starting from state _s_, if Alice applies _A_ then _B_ (let’s write the state _h(h(s, A), B)_), she gets the same hash as Bob, who applied _B_ then _A_ (and hence computed _h(h(s, B), A)_).

---

<div class="post-metadata">

**Author:** ![rodarmor](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/rodarmor/32/287_2.png) [@rodarmor](https://discourse.pijul.org/u/rodarmor)\
**Post date:** [October 7, 2020, 8:57am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/6 "2020-10-07T08:57:05Z")

</div>

Hmm, I could see how that would be nice. It mirror’s the patch-based repository model, but for hashes.

I’m assuming that this is desired for efficient updates of the repository’s root hash, which multiple parties can agree on? I can imagine somewhat inefficient schemes for calculating a root hash (which don’t satisfy the properties you gave), like sorting the hashes of the patches in the repo, and taking a merkle tree hash over those hashes as leaves. Is efficiency the only consideration?

I’m not sure I understand why the properties you mentioned would be important for this. If you can get A or B (patch hashes) out of h(A, B) (the repo root hash) that doesn’t seem like a big deal.

I’m not very familiar with them, but this makes me think of cryptographic accumulators. There are a few types, the ones I know about hash-based, like [utreexo](https://dci.mit.edu/research/2019/6/6/utreexo-a-dynamic-hash-based-accumulator-optimized-for-the-bitcoin-utxo-set) and one based on prime numbers, which I can’t find a good link for.

---

<div class="post-metadata">

**Author:** ![rodarmor](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/rodarmor/32/287_2.png) [@rodarmor](https://discourse.pijul.org/u/rodarmor)\
**Post date:** [October 10, 2020, 9:23pm UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/7 "2020-10-10T21:23:56Z")

</div>

I was thinking about this, and it’s not obvious to me why you couldn’t sum the patch hashes modulo 2\*\*256 and use that as the state hash. (You could do xor, but that has odd properties like two patches xoring to zero.) Is there a practical reason why that wouldn’t work?

---

<div class="post-metadata">

**Author:** ![pmeunier](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/pmeunier/32/4_2.png) [@pmeunier](https://discourse.pijul.org/u/pmeunier)\
**Post date:** [October 11, 2020, 8:11am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/8 "2020-10-11T08:11:41Z")

</div>

Two patches XORing to 0 is not really an issue: for a hash /h/, there’s only one hash /h’/ such that /h+h’ = 0/, and you have the exact same property in your other proposed scheme.

The problem with XOR is that you can use linear algebra to generate collisions, by generating a list of patches and solving the corresponding linear equation.

For the integer sum modulo 2^256, finding collisions amounts to solving the subset sum problem, which is known to be a weak cryptographic problem ([https://en.wikipedia.org/wiki/Merkle–Hellman\_knapsack\_cryptosystem](https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem)).

So, for both systems, a server can trick a client into believing they’re synchronised, even though they’re not. Even worse, the server can inject a patch in the log, and add a constant number of patches to recover the same state identifier (the same state “hash”).

---

<div class="post-metadata">

**Author:** ![rodarmor](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/rodarmor/32/287_2.png) [@rodarmor](https://discourse.pijul.org/u/rodarmor)\
**Post date:** [October 11, 2020, 8:49am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/9 "2020-10-11T08:49:02Z")

</div>

I’m not sure if I see what the attack would be.

Let’s say a server wants a client to accept a bad patch, P. The client asks for some state S. The server creates a log that includes P, and also some number of additional hashes H1…Hn to make the log’s state be S. However, if the client requests the patches for H1…Hn, the server can’t actually return them to the client, because to do so the server would have to calculate pre-images that hash to H1…Hn, which is infeasible. So as long as the client actually verifies that all patches in the log exist, they can’t be tricked with an erroneous state.

---

<div class="post-metadata">

**Author:** ![pmeunier](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/pmeunier/32/4_2.png) [@pmeunier](https://discourse.pijul.org/u/pmeunier)\
**Post date:** [October 11, 2020, 10:08am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/10 "2020-10-11T10:08:23Z")

</div>

That’s not how it works. If the state is a _linear_ function of the patch hashes, it doesn’t matter what exact hashes you have, as long as you can generate enough “independent” vectors (hashes) to form a linear base. You need as many independent vectors as there are bits, here 256 vectors. Then, for example with XOR, you can generate any hash you want by taking the subset of these hashes given by the resolution of the linear equation (h\_{i\_0} + … + h\_{i\_k} = h).

---

<div class="post-metadata">

**Author:** ![rodarmor](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/rodarmor/32/287_2.png) [@rodarmor](https://discourse.pijul.org/u/rodarmor)\
**Post date:** [October 11, 2020, 8:37pm UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/11 "2020-10-11T20:37:34Z")

</div>

Good point, I didn’t think of that!

---

<div class="post-metadata">

**Author:** ![burdges](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/burdges/32/242_2.png) [@burdges](https://discourse.pijul.org/u/burdges)\
**Post date:** [January 8, 2022, 8:42am UTC](https://discourse.pijul.org/t/blake3-for-the-new-hash-function/550/12 "2022-01-08T08:42:37Z")

</div>

As a rule, algebraic properties like homomorphic, associativity, commutativity, etc. all hurt performance dramatically, but some lattice based schemes like [SWIFFT](https://www.eecs.harvard.edu/~alon/PAPERS/lattices/swifft.pdf) yield somewhat hash-like performance while being somewhat homomorphic.

I’ve only seen the one-time signature scheme KSN exploit this property in practice, along with its consumer the [K2SN-MSS](https://eprint.iacr.org/2019/442) signature scheme, but…

It’s not impossible someone would find additional applications, like maybe interactions with erasure coding.