Position-Weighted Sinsemilla

Ironwood reuses Orchard's underlying cryptography but keeps its own note commitment tree. In both pools, every shielded output becomes a leaf in a tree whose internal nodes are hashed with Sinsemilla, a variant of a Pedersen hash that is efficient to evaluate inside zero-knowledge circuits.

The circuit is not the only place the hash runs. It is the computational bottleneck for wallets to maintain the Merkle paths that keep funds spendable, and a full node performs it many times for every block as new commitments enter the trees.

We've sped it up. One optimization changes how the Sinsemilla accumulator is represented: when the input length and domain are fixed, all of the doublings can move into a precomputed table, leaving one addition per word. The observation is that the Sinsemilla recurrence is Horner's rule evaluated in a group, and a fixed-length Horner evaluation can be expanded ahead of time.

In CPU benchmarks on Apple hardware, the complete optimized Sinsemilla Merkle hashing path is more than 15× as fast as what we started with. The optimizations described in this article account for a 3.5× speedup.

The Sinsemilla recurrence

Sinsemilla breaks its input into 10-bit words. Each word selects one of fixed Pallas points,

Starting from a domain-specific point , the hash maintains an accumulator , and the specification processes one word as

where is an incomplete elliptic-curve addition, undefined on a small set of exceptional inputs. Apart from the exceptional cases, Sinsemilla evaluates the recurrence

The implementation we started with followed the specification literally, computing a mixed addition for and then a full projective addition with .

A first improvement is to compute as one Jacobian doubling followed by one mixed addition, arranged to fail in exactly the cases the two incomplete additions would have: when the incoming accumulator is the identity, when , and when .

The larger gain comes from structure specific to the Merkle hash.

The Merkle hash always has 52 words

An Ironwood or Orchard Merkle parent hash has a fixed domain and exactly 10-bit words. The recurrence therefore never needs to run at arbitrary length. On non-exceptional inputs, expanding it gives

which is Horner's rule written out in full. Horner's rule is normally attractive because it avoids storing the powers. Here the coefficients come from a fixed set of 1,024 points, the number of positions is always 52, and the same hash is evaluated over and over, so the opposite trade is the right one: store the powers.

Rescaling the accumulator

The same optimization can be derived as a change of representation for the intermediate state. Define

Then

and the doubling has disappeared from the recurrence. Because and , nothing needs to be undone afterward; the scaling factor decreases to one on its own.

Now define a position-weighted table

At position the evaluator performs

one mixed addition per word and no doubling in the loop. The work has not disappeared; it has moved into a table that is built once and reused by every Merkle hash: 52 rows of 1,024 affine Pallas points, about 3.25 MiB, with the starting point cached alongside it. (The table is initialized lazily, in around 13 ms on our benchmark machine.)

The first exceptional step gives a discrete-log relation

Take a message that reaches an exceptional case, and consider the first step at which the incomplete-addition evaluator would fail. Every earlier addition was defined, so the accumulator entering step can be written as

where the integers are determined by the message words before step . The failure at step means or , and all three cases have the form

Substituting the expansion of gives

a discrete-log relation among and the Sinsemilla generators. The relation is nontrivial, because the coefficient of is , which is never divisible by the Pallas group order, an odd prime. and the are independently derived hash-to-curve generators, so under the discrete-logarithm relation assumption, no feasible computation produces a message that reaches an exceptional case.

This is not a new assumption introduced by the optimization. Sinsemilla's own security argument rests on the same fact: an exceptional output of the incomplete-addition construction yields a nontrivial discrete-log relation, which is why incomplete additions were acceptable there in the first place.

Removing the exceptional-case arithmetic reduced latency by roughly another 15%.

Results and costs

In our fixed-length Sinsemilla and Merkle benchmarks on Apple hardware, the complete optimized function is more than 15× as fast as the original. The optimizations detailed here account for a 3.5× speedup. The primary cost is memory usage: we require a 3.25 MiB table instead of the ordinary 64 KiB one.

This has a significant impact on wallet syncing, which pays three costs:

• Trial-decrypting every note (see our batch affine ladder work).
• Adding every note commitment to the tree
• Updating frontiers for all your owned notes

We'll be discussing the remaining optimizations in our next posts.