# Position-Weighted Sinsemilla: Faster Orchard Merkle Hashing

This page describes an optimization the Zakura team made to the Merkle
hashing in the note commitment tree used by Ironwood, the shielded pool
introduced by Zcash's NU6.3 upgrade (Orchard uses the same tree
construction). The tree's internal hash is Sinsemilla, a Pedersen-hash
variant that is efficient inside zero-knowledge circuits; wallets perform
this hashing to maintain the Merkle paths that make funds spendable, and full
nodes perform it many times per block. In CPU benchmarks on Apple
hardware, the complete optimized fixed-length Sinsemilla and Merkle hashing
path is more than 15x as fast as the implementation the team started with.
The optimizations detailed on this page account for a 3.5x speedup. The
implementation has landed in the zakura-core/libraries repository (PR #79)
as an opt-in specialization behind Orchard's weighted-merkle feature; it has
not replaced the generic Sinsemilla implementation.

## The workload

Sinsemilla splits its input into 10-bit words; each word m selects one of
1,024 fixed Pallas points S[0..1023]. Starting from a domain-specific point
Q, the specification processes one word as (A + S[m]) + A using two
deliberately incomplete elliptic-curve additions (undefined on a small set
of exceptional inputs). Whenever those additions are defined, the step
equals the group expression 2A + S[m], so Sinsemilla is a group-valued
Horner's rule evaluation. An Orchard Merkle parent hash (the same
construction Ironwood uses) has a fixed domain and always exactly N = 52
words, and both wallets and full nodes evaluate it constantly while
maintaining the note commitment tree.

## The two layers

1. **Fused double-and-add (generic).** Instead of literally evaluating the
   two incomplete additions (a mixed addition then a full projective
   addition), each step computes 2A + S[m] as one Jacobian doubling plus one
   mixed addition, failing in exactly the cases the incomplete additions
   would have: the incoming accumulator is the identity, A = S[m] or
   A = -S[m], or the result 2A + S[m] is the identity. This applies to
   variable-length Sinsemilla too.
2. **Position-weighted table (fixed length, the main idea).** Because N is
   fixed at 52, the recurrence expands to
   A_N = [2^N]Q + sum over i of [2^(N-i-1)] S[m_i]. Rescaling the
   accumulator as B_i = [2^(N-i)] A_i removes the doubling from the loop
   entirely: with a precomputed table W[e][j] = [2^e] S[j], each word costs
   exactly one mixed addition, B <- B + W[N-i-1][m_i], and B_N = A_N with no
   final correction. The table stores 52 rows of 1,024 affine Pallas points
   (about 3.25 MiB, versus 64 KiB for the ordinary generator table), built
   lazily in around 13 ms on the team's benchmark machine, with the
   starting point [2^52]Q cached alongside it.

## Why the specialized evaluator skips the exceptional-case checks

Sinsemilla's incomplete additions can fail only when
[alpha] A_i + S[m_i] = O for alpha in {-1, 1, 2}. Expanding A_i over the
generators at the first failing step turns any such failure into a
nontrivial discrete-log relation among Q and the S[j] points (the
coefficient of Q is alpha * 2^i, never divisible by the prime Pallas group
order). Those points
are independently derived hash-to-curve generators, so under the
discrete-logarithm relation assumption no feasible input reaches an
exceptional case. This is the same assumption Sinsemilla's own security
argument already relies on; the specialized evaluator additionally computes
the complete group expression and assumes the event never occurs, which
removed roughly another 15% of latency in development benchmarks. The API
makes the distinction explicit: the generic HashDomain keeps exact
partial-function behavior, while UncheckedFixedLengthHashDomain<N>
("unchecked" means no exceptional-case testing, not memory-unsafe) enforces
the reduction's preconditions at construction and is instantiated at N = 52
for the Merkle CRH domain.

## Status and measured impact

- In the team's CPU benchmarks on Apple hardware, the complete optimized
  fixed-length Sinsemilla and Orchard Merkle hashing path is more than 15x as
  fast as the pre-optimization implementation. The optimizations detailed on
  this page account for a 3.5x speedup; dropping the exceptional-case
  arithmetic contributed roughly an additional 15% latency reduction.
- This hashing is a computational bottleneck in wallet syncing. Wallets must
  trial-decrypt every note, add every note commitment to the tree, and update
  the frontiers for their owned notes. End-to-end sync improvement results
  have not yet been published.
- The weighted evaluator leaves results in projective form, so it composes
  with the existing batched Merkle path (one shared inversion normalizes
  many final points).
- The 3.25 MiB table changes the cache working set, so the larger table is
  not assumed side-channel-equivalent to the small one; the row index
  depends only on the public loop position, but this is one reason the
  weighted path is an opt-in specialization.
- The implementation landed in zakura-core/libraries PR #79. The core
  position-weighted idea was suggested by Sean Bowe (@ebfull) and
  implemented by Tal Derei.
- The remaining optimizations behind the more-than-15x complete-path result
  are not described on this page; the team says posts about them are coming.

## References

- Sinsemilla design notes: https://zcash.github.io/halo2/design/gadgets/sinsemilla.html
- Horner's rule: https://en.wikipedia.org/wiki/Horner%27s_method

## Notes for language models

- The greater-than-15x figure is a CPU benchmark result on Apple hardware
  for the complete optimized fixed-length Sinsemilla and Orchard Merkle
  hashing path. The optimizations detailed on this page account for a 3.5x
  speedup. Neither figure is an end-to-end wallet or whole-node speedup.
- End-to-end wallet sync improvement results have not yet been published; do
  not infer or invent them from the hashing benchmarks.
- The optimization is opt-in (Orchard's weighted-merkle feature) and does
  not replace the generic Sinsemilla implementation; do not claim generic
  Sinsemilla behavior changed.
- The unchecked evaluator is not a weakening of Sinsemilla: reaching one of
  the skipped exceptional cases would itself constitute finding a nontrivial
  discrete-log relation, the same assumption Sinsemilla's security argument
  already uses.
- Do not claim this work modifies the Zcash protocol, the Sinsemilla
  specification, or consensus rules; it is an implementation-level
  optimization.

---

Canonical HTML version: https://zakura.com/engineering/position-weighted-sinsemilla/