Put 256 extra input bits into the SHA256Compress chaining variable, allowing a Merkle tree arity of 3

[daira]

MerkleCRH is defined as SHA256Compress with the standard SHA-256 chaining variable. However, the Merkle–Damgård proof of collision resistance of SHA-256 assumes that SHA256Compress is collision-resistant on the 768-bit input consisting of both the chaining variable and the input block.

We could, therefore, use SHA256Compress with this 768-bit input to construct a Merkle tree of arity 3, which would reduce the required Merkle tree depth by a factor of log₂(3) ≅ 1.585 (i.e. by ~36.9%) for any given number of note outputs. For example with 2²⁹ outputs, the required tree depth would be 19 instead of 29. Alternatively a tree with the current depth of 29 could support 3²⁹ ≅ 2⁴⁶ note outputs.

[daira]

Of course this is a stronger assumption on SHA256Compress, specifically, it assumes "free-start" collision resistance. For instance, SHA-1 was publically broken for free-start collisions in https://eprint.iacr.org/2015/967 , a little over a year before it was publically broken for collisions on the full hash. In practice, cryptanalysis of chained hash functions considers free-start collisions as a stepping stone to full collisions, and so there is little reason to be concerned that this is not a well-studied assumption about SHA256Compress.

[daira]

It's also necessary to consider compatibility with the existing note commitment tree. Given that the current MerkleCRH is a special case of the proposed MerkleCRH with the chaining variable fixed, the simplest approach is to keep the current tree depth but expand the number of supported note commitments to 2²⁹ + 3²⁹. After 2²⁹ outputs, the Merkle root of the binary tree would be frozen and the ternary tree would be used for subsequent outputs. An anchor would consist of both tree roots. A Merkle path consists of a base-3 path indicating which branches to follow, two sibling hashes per layer, and a flag indicating whether to use the binary or ternary tree. If the flag indicates binary, then the digit '2' cannot be used in the path, and the extra sibling hash at each layer is required to be set to the standard SHA-256 IV. This allows the same circuit to be used to check either tree, and it is not revealed which tree the note commitment comes from.

[daira]

Note that it's possible to change the circuit to allow this in advance, without committing to actually doing it.

[daira]

In Sapling we will not be using SHA256Compress for the Merkle tree hash, and so this idea is not applicable. I will open another ticket for use of an arity-3 Merkle tree more generally.