Pattern

Canonical action pairing

A builder uses a keyed sort to put the actions of a bundle in order. The sort sets the pairs of spends and outputs. Thus, each build of the same transaction gives the same note commitments.

Problem

Each action of an Orchard-protocol bundle holds one spend and one output. The ρ of the output is the nullifier of the spend in the same action. ψ, rcm and the note commitment of the output come from ρ. Thus, the note commitment of an output changes when its pair changes.

A standard builder pairs spends and outputs at random. It also makes new dummy notes on each build. Thus, two builds of the same transaction give each output a different note commitment.

Three cases need the same note commitments on each build:

• Rebuild after a reorg. A chain of bound notes binds the cmx of each predecessor. A reorg can remove a transaction. A rebuild with new commitments breaks each later note that bound an old cmx.
• Several signers. With FROST over a PCZT, each signer must examine the bundle before it signs. To calculate the expected bundle, a signer needs the dummy notes and the pairs of the coordinator.
• Receipts before mining. An app can tell a user the note commitment of a note before the chain mines the transaction. That commitment must stay the same after a rebuild.

Mechanism

pairing key k ─┐
context ctx   ─┼─→ pairing seed d ─→ PRF_d ─→ dummy spends, dummy outputs, output rseeds
real nfs      ─┘           │
                           └─→ keyed sort keys ─→ action a = (spend a, output a)
                                                         │
                                       ρ of output a = nf of spend a ─→ cmx

Inputs

Each party that builds or examines the bundle uses the same inputs:

• the pairing key k, a 32-byte secret;
• an app context ctx, for example an epoch number;
• the real spends, each with its note and its nullifier key;
• the real outputs, in the order of the caller;
• the number of actions n;
• the lead byte of the note plaintext.

Steps

1. Sort the nullifiers of the m real spends. Calculate the pairing seed:

   d = BLAKE2b-256("Zcash_PairingSd_",
         k ‖ len(ctx) ‖ ctx ‖ m ‖ nf_1 ‖ … ‖ nf_m)

2. Use d as the key of a PRF. Each value has a tag byte t and an index i:

   PRF_d(t, i, c) = BLAKE2b-512("Zcash_PairingPRF", d ‖ t ‖ i ‖ c)

   c is a counter. It increases only when a value is invalid, for example a spending key.
3. Make n − m dummy spends of value zero. The PRF gives the spending key, ρ and rseed of each dummy spend.
4. Give each real output an rseed from the PRF. A caller can give its own rseed, for example for a bound note.
5. Make the dummy outputs of value zero. The PRF gives the recipient and the rseed of each dummy output.
6. Calculate a keyed sort key for each spend and each output:

   key_spend = BLAKE2b-256("Zcash_PairingOrd", d ‖ 0x00 ‖ nf)
   key_out   = BLAKE2b-256("Zcash_PairingOrd", d ‖ 0x01 ‖ rseed)

7. Sort the spends and the outputs by their keys. Action a holds spend a and output a.
8. Each output takes ρ from the nullifier of its action. Calculate esk, ψ, rcm and the note commitment as ZIP 212 and ZIP 2005 specify.

A value can fail, for example an esk of zero. The chance is about 2⁻²⁵⁴. Then the builder discards the full build. It adds a retry byte to ctx and builds again. Each party that follows this rule gets the same bundle.

Values that stay random

The value commitment trapdoor, the spend authorization randomizer, the proof and some outgoing ciphertexts stay random. Nullifiers and note commitments are independent of these values. Thus, two canonical builds have different transaction IDs. They spend the same notes, so the chain can mine one of them only.

Scope

The pattern is for bundles with enableCrossAddress = 1, in practice Ironwood-pool bundles. For other bundles, ZIP 2006 sets the pairs by expanded receiver.

Cost

• Chain. Zero. A canonical bundle has the same size and the same fee as a standard bundle.
• Build. A small number of BLAKE2b hashes for each action, and one sort.
• Builders. The builder must accept a pairing key and a context. The orchard crate pairs at random. A fork of the crate implements this pattern, and an upstream PR is pending.
• PCZT. The Constructor role makes the canonical build. A signer with k can build the bundle again and compare nf, cmx and epk of each action before it signs.

Limits

• Privacy. All derived values come from k. Only a holder of k can identify each dummy note. To all other parties, the dummy notes and the order of actions look random. Thus, keep k as secret as a viewing key.
• Reused seeds. A dummy nullifier repeats when d repeats. The seed binds the real nullifiers, so two bundles with the same d spend the same notes. Only one of them can go on the chain. A bundle with zero real spends needs a unique ctx.
• Rebuild scope. A rebuild gives the same commitments only with the same inputs. A different fee input changes d, and then all pairs change.

Spec

The full spec is a draft ZIP. It includes the spending key rule for dummy notes, the dummy output memo, the PCZT fields and the rationale. This site will publish the draft after review.

Demo: rebuild a bundle

The demo uses the orchard crate, compiled to WebAssembly. It makes Ironwood-pool notes of value zero. The real spends use demo nullifiers. The real outputs go to a demo address.

Click a build button two times. A canonical build gives the same cmx values each time. A standard build uses a new random seed each time, so its cmx values change.