[Sapling] Use ternary Merkle tree for note commitments

[daira]

In #2173 it was suggested to implement a ternary Merkle tree by making use of the chaining variable of SHA256Compress. Since we will not be using SHA256Compress for Sapling, and since the discussion on #2173 was specific to SHA256Compress, I decided to open this new ticket for a similar idea applied to Pedersen hashes (#2234).

[daira]

The cost of a Pedersen hash that compresses 3-to-1 is slightly less than 1.5 times the cost of one that compresses 2-to-1, because the comparison of the hash from the previous layer with the field order is not needed. Also, a 3-to-1 hash is effectively worth log₂(3) ~= 1.585 of the 2-to-1 hashes, in terms of how much it expands the supported number of leaves (in this case, note commitments).

Specifically, a 3-to-1 hash costs 3*255 + 1 + 176 + (765/5) * 7 + (765/5 - 2) * 7 + 6 = 3076 constraints (about 1.460 times the cost of a 2-to-1 hash). So the overall cost improvement is a factor of around 1.585/1.460 which is 1.0856, i.e. a 7.89% improvement. Alternatively for the same cost, we can support 1.460 times fewer layers, but at the cost of the current binary depth of 29 this works out to around 5.58 times more leaves. In fact this is quantised so you would probably use 20 ternary layers, for a 0.68% cost increase but 6.49 times more leaves.

This has to be set against the complexity of implementing and specifying a ternary Merkle tree. It seems questionable whether the cost improvement is worth the complexity, but let's consider it anyway.

[daira]

If we want a Pareto improvement, 19 ternary layers gives 2.16 times as many leaves for a 4.35% cost improvement over 29 binary layers.

(Of course this is just the cost of the Merkle tree, so the cost improvement for the whole circuit or circuits will be less.)

[daira]

After the Pedersen hash improvements here, a 2-to-1 hash costs 1779 constraints, and a 3-to-1 hash costs 3 * 255 + 1 + 1 * 7 + 190 * 4 + (191 - 1) * 6 + 4 = 2677 constraints.

This puts a 3-to-1 hash at 1.505 times the constraint cost of a 2-to-1 hash. The difference from 1.460 calculated above is explained mainly by the overhead due to the range check having been removed. This change makes it less favourable to use a ternary hash. There is still an overall cost improvement of around 1.585/1.505 which is 1.0533, i.e. a 5.06% improvement. In this case 19 ternary layers would give 2.16 times as many leaves for a 1.41% cost improvement over 29 binary layers.

This seems hardly worth the complexity, so I will close this ticket.