orchard
Requires Rust 1.56.1+.
Documentation
License
Copyright 20202022 The Electric Coin Company.
You may use this package under the Bootstrap Open Source Licence, version 1.0,
or at your option, any later version. See the file COPYING
for
more details, and LICENSEBOSL
for the terms of the Bootstrap
Open Source Licence, version 1.0.
The purpose of the BOSL is to allow commercial improvements to the package while ensuring that all improvements are open source. See here for why the BOSL exists.
Concepts
Preliminaries
User Documentation
Creating keys and addresses
Creating notes
Spending notes
Integration into an existing chain
Design
General design notes
Requirements
 Keep the design close to Sapling, while eliminating aspects we don't like.
Nonrequirements
 Delegated proving with privacy from the prover.
 We know how to do this, but it would require a discrete log equality proof, and the most efficient way to do this would be to do RedDSA and this at the same time, which means more work for e.g. hardware wallets.
Open issues
 Should we have one memo per output, or one memo per transaction, or 0..n memos?
 Variable, or (1 or n), is a potential privacy leak.
 Need to consider the privacy issue related to light clients requesting individual memos vs being able to fetch all memos.
Note structure
 TODO: UDAs: arbitrary vs whitelisted
Typed variables vs byte encodings
For Sapling, we have encountered multiple places where the specification uses typed variables to define the consensus rules, but the C++ implementation in zcashd relied on byte encodings to implement them. This resulted in subtlydifferent consensus rules being deployed than were intended, for example where a particular type was not roundtrip encodable.
In Orchard, we avoid this by defining the consensus rules in terms of the byte encodings of all variables, and being explicit about any types that are not roundtrip encodable. This makes consensus compatibility between stronglytyped implementations (such as this crate) and byteoriented implementations easier to achieve.
Keys and addresses
Orchard keys and payment addresses are structurally similar to Sapling. The main change is that Orchard keys use the Pallas curve instead of Jubjub, in order to enable the future use of the PallasVesta curve cycle in the Orchard protocol. (We already use Vesta as the curve on which Halo 2 proofs are computed, but this doesn't yet require a cycle.)
Using the Pallas curve and making the most efficient use of the Halo 2 proof system involves corresponding changes to the key derivation process, such as using Sinsemilla for Pallasefficient commitments. We also take the opportunity to remove all uses of expensive generalpurpose hashes (such as BLAKE2s) from the circuit.
We make several structural changes, building on the lessons learned from Sapling:

The nullifier private key $nsk$ is removed. Its purpose in Sapling was as defenseindepth, in case RedDSA was found to have weaknesses; an adversary who could recover $ask$ would not be able to spend funds. In practice it has not been feasible to manage $nsk$ much more securely than a full viewing key, as the computational power required to generate Sapling proofs has made it necessary to perform this step on the same device that is creating the overall transaction (rather than on a more constrained device like a hardware wallet). We are also more confident in RedDSA now.

$nk$ is now a field element instead of a curve point, making it more efficient to generate nullifiers.

$ovk$ is now derived from $fvk$, instead of being derived in parallel. This places it in a similar position within the key structure to $ivk$, and also removes an issue where two full viewing keys could be constructed that have the same $ivk$ but different $ovk$s. Users still have control over whether $ovk$ is used when constructing a transaction.

All diversifiers now result in valid payment addresses, due to group hashing into Pallas being specified to be infallible. This removes significant complexity from the use cases for diversified addresses.

The fact that Pallas is a primeorder curve simplifies the protocol and removes the need for cofactor multiplication in key agreement. Unlike Sapling, we define public (including ephemeral) and private keys used for note encryption to exclude the zero point and the zero scalar. Without this change, the implementation of the Orchard Action circuit would need special cases for the zero point, since Pallas is a short Weierstrass rather than an Edwards curve. This also has the advantage of ensuring that the key agreement has "contributory behaviour" — that is, if either party contributes a random scalar, then the shared secret will be random to an observer who does not know that scalar and cannot break Diffie–Hellman.
Other than the above, Orchard retains the same design rationale for its keys and addresses as Sapling. For example, diversifiers remain at 11 bytes, so that a raw Orchard address is the same length as a raw Sapling address.
Orchard payment addresses do not have a standalone string encoding. Instead, we define "unified addresses" that can bundle together addresses of different types, including Orchard. Unified addresses have a HumanReadable Part of "u" on Mainnet, i.e. they will have the prefix "u1". For specifications of this and other formats (e.g. for Orchard viewing and spending keys), see section 5.6.4 of the NU5 protocol specification [#NU5orchardencodings].
Hierarchical deterministic wallets
When designing Sapling, we defined a BIP 32like mechanism for generating hierarchical deterministic wallets in ZIP 32. We decided at the time to stick closely to the design of BIP 32, on the assumption that there were Bitcoin use cases that used both hardened and nonhardened derivation that we might not be aware of. This decision created significant complexity for Sapling: we needed to handle derivation separately for each component of the expanded spending key and full viewing key (whereas for transparent addresses there is only a single component in the spending key).
Nonhardened derivation enables creating a multilevel path of child addresses below some parent address, without involving the parent spending key. The primary use case for this is HD wallets for transparent addresses, which use the following structure defined in BIP 44:
 (H) BIP 44
 (H) Coin type: Zcash
 (H) Account 0
 (N) Normal addresses
 (N) Address 0
 (N) Address 1...
 (N) Change addresses
 (N) Change address 0
 (N) Change address 1...
 (N) Normal addresses
 (H) Account 1...
 (H) Account 0
 (H) Coin type: Zcash
Shielded accounts do not require separating change addresses from normal addresses, because addresses are not revealed in transactions. Similarly, there is also no need to generate a fresh spending key for every transaction, and in fact this would cause a linear slowdown in wallet scanning. But for users who do want to generate multiple addresses per account, they can generate the following structure, which does not use nonhardened derivation:
 (H) ZIP 32
 (H) Coin type: Zcash
 (H) Account 0
 Diversified address 0
 Diversified address 1...
 (H) Account 1...
 (H) Account 0
 (H) Coin type: Zcash
Nonhardened derivation is therefore only required for usecases that require the ability to derive more than one child layer of addresses. However, in the years since Sapling was deployed, we have not seen any such use cases appear.
Therefore, for Orchard we only define hardened derivation, and do so with a much simpler design than ZIP 32. All derivations produce an opaque binary spending key, from which the keys and addresses are then derived. As a side benefit, this makes key formats shorter. (The formats that will actually be used in practice for Orchard will correspond to the simpler Sapling formats in the protocol specification, rather than the longer and more complicated "extended" ones defined by ZIP 32.)
Actions
In Sprout, we had a single proof that represented two spent notes and two new notes. This was necessary in order to facilitate spending multiple notes in a single transaction (to balance value, an output of one JoinSplit could be spent in the next one), but also provided a minimal level of arityhiding: singleJoinSplit transactions all looked like 2in 2out transactions, and in multiJoinSplit transactions each JoinSplit looked like a 1in 1out.
In Sapling, we switched to using value commitments to balance the transaction, removing the min2 arity requirement. We opted for one proof per spent note and one (much simpler) proof per output note, which greatly improved the performance of generating outputs, but removed any arityhiding from the proofs (instead having the transaction builder pad transactions to 1in, 2out).
For Orchard, we take a combined approach: we define an Orchard transaction as containing a bundle of actions, where each action is both a spend and an output. This provides the same inherent arityhiding as multiJoinSplit Sprout, but using Sapling value commitments to balance the transaction without doubling its size.
Memo fields
Each Orchard action has a memo field for its corresponding output, as with Sprout and Sapling. We did at one point consider having a single Orchard memo field per transaction, and/or having a mechanism for enabling multiple recipients to decrypt the same memo, but these were decided against in order to keep the overall design simpler.
Commitments
As in Sapling, we require two kinds of commitment schemes in Orchard:
 $HomomorphicCommit$ is a linearly homomorphic commitment scheme with perfect hiding, and strong binding reducible to DL.
 $Commit$ and $ShortCommit$ are commitment schemes with perfect hiding, and strong binding reducible to DL.
By "strong binding" we mean that the scheme is collision resistant on the input and randomness.
We instantiate $HomomorphicCommit$ with a Pedersen commitment, and use it for value commitments:
$cv=HomomorphicCommit_{rcv}(v)$
We instantiate $Commit$ and $ShortCommit$ with Sinsemilla, and use them for all other commitments:
$ivk=ShortCommit_{rivk}(ak,nk)$ $cm=Commit_{rcm}(rest of note)$
This is the same split (and rationale) as in Sapling, but using the more PLONKefficient Sinsemilla instead of BoweHopwood Pedersen hashes.
Note that for $ivk$, we also deviate from Sapling in two ways:
 We use $ShortCommit$ to derive $ivk$ instead of a full PRF. This removes an unnecessary (large) PRF primitive from the circuit, at the cost of requiring $rivk$ to be part of the full viewing key.
 We define $ivk$ as an integer in $[1,q_{P})$; that is, we exclude $ivk=0$. For
Sapling, we relied on BLAKE2s to make $ivk=0$ infeasible to produce, but it was still
technically possible. For Orchard, we get this by construction:
 $0$ is not a valid xcoordinate for any Pallas point.
 $SinsemillaShortCommit$ internally maps points to field elements by replacing the identity (which has no affine coordinates) with $0$. But $SinsemillaCommit$ is defined using incomplete addition, and thus will never produce the identity.
Commitment tree
The commitment tree structure for Orchard is identical to Sapling:
 A single global commitment tree of fixed depth 32.
 Note commitments are appended to the tree inorder from the block.
 Valid Orchard anchors correspond to the global tree state at block boundaries (after all commitments from a block have been appended, and before any commitments from the next block have been appended).
The only difference is that we instantiate $MerkleCRH_{Orchard}$ with Sinsemilla (whereas $MerkleCRH_{Sapling}$ used a BoweHopwood Pedersen hash).
Uncommitted leaves
The fixeddepth incremental Merkle trees that we use (in Sprout and Sapling, and again in Orchard) require specifying an "empty" or "uncommitted" leaf  a value that will never be appended to the tree as a regular leaf.
 For Sprout (and trees composed of the outputs of bittwiddling hash functions), we use the allzeroes array; the probability of a real note having a colliding note commitment is cryptographically negligible.
 For Sapling, where leaves are $u$coordinates of Jubjub points, we use the value $1$ which is not the $u$coordinate of any Jubjub point.
Orchard note commitments are the $x$coordinates of Pallas points; thus we take the same approach as Sapling, using a value that is not the $x$coordinate of any Pallas point as the uncommitted leaf value. We use the value $2$ for both Pallas and Vesta, because $2_{3}+5$ is not a square in either $F_{p}$ or $F_{q}$:
sage: p = 0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001
sage: q = 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001
sage: EllipticCurve(GF(p), [0, 5]).count_points() == q
True
sage: EllipticCurve(GF(q), [0, 5]).count_points() == p
True
sage: Mod(13, p).is_square()
False
sage: Mod(13, q).is_square()
False
Note: There are also no Pallas points with $x$coordinate $0$, but we map the identity to $(0,0)$ within the circuit. Although $SinsemillaCommit$ cannot return the identity (the incomplete addition would return $⊥$ instead), it would arguably be confusing to rely on that.
Considered alternatives
We considered splitting the commitment tree into several subtrees:
 Bundle tree, that accumulates the commitments within a single bundle (and thus a single transaction).
 Block tree, that accumulates the bundle tree roots within a single block.
 Global tree, that accumulates the block tree roots.
Each of these trees would have had a fixed depth (necessary for being able to create
proofs). Chains that integrated Orchard could have decoupled the limits on
commitmentspersubtree from higherlayer constraints like block size, by enabling their
blocks and transactions to be structured internally as a series of Orchard blocks or txs
(e.g. a Zcash block would have contained a Vec<BlockTreeRoot>
, that each were appended
inorder).
The motivation for considering this change was to improve the lives of light client wallet developers. When a new note is received, the wallet derives its incremental witness from the state of the global tree at the point when the note's commitment is appended; this incremental state then needs to be updated with every subsequent commitment in the block inorder. Wallets can't get help from the server to create these for new notes without leaking the specific note that was received.
We decided that this was too large a change from Sapling, and that it should be possible to improve the Incremental Merkle Tree implementation to work around the efficiency issues without domainseparating the tree.
Nullifiers
The nullifier design we use for Orchard is
$nf=Extract_{P}([(F_{nk}(ρ)+ψ)modp]G+cm),$
where:
 $F$ is a keyed circuitefficient PRF (such as Rescue or Poseidon).
 $ρ$ is unique to this output. As with $h_{Sig}$ in Sprout, $ρ$ includes the nullifiers of any Orchard notes being spent in the same action. Given that an action consists of a single spend and a single output, we set $ρ$ to be the nullifier of the spent note.
 $ψ$ is sendercontrolled randomness. It is not required to be unique, and in practice is derived from both $ρ$ and a senderselected random value $rseed$: $ψ=KDF_{ψ}(ρ,rseed).$
 $G$ is a fixed independent base.
 $Extract_{P}$ extracts the $x$coordinate of a Pallas curve point.
This gives a note structure of
$(addr,v,ρ,ψ,rcm).$
The note plaintext includes $rseed$ in place of $ψ$ and $rcm$, and omits $ρ$ (which is a public part of the action).
Security properties
We care about several security properties for our nullifiers:

Balance: can I forge money?

Note Privacy: can I gain information about notes only from the public block chain?
 This describes notes sent inband.

Note Privacy (OOB): can I gain information about notes sent outofband, only from the public block chain?
 In this case, we assume privacy of the channel over which the note is sent, and that the adversary does not have access to any notes sent to the same address which are then spent (so that the nullifier is on the block chain somewhere).

Spend Unlinkability: given the incoming viewing key for an address, and not the full viewing key, can I (possibly the sender) detect spends of any notes sent to that address?
 We're giving $ivk$ to the attacker and allowing it to be the sender in order to make this property as strong as possible: they will have all the notes sent to that address.

Faerie Resistance: can I perform a Faerie Gold attack (i.e. cause notes to be accepted that are unspendable)?
 We're giving the full viewing key to the attacker and allowing it to be the sender in order to make this property as strong as possible: they will have all the notes sent to that address, and be able to derive every nullifier.
We assume (and instantiate elsewhere) the following primitives:
 $GH$ is a cryptographic hash into the group (such as BLAKE2s with simplified SWU), used to derive all fixed independent bases.
 $E$ is an elliptic curve (such as Pallas).
 $KDF$ is the note encryption key derivation function.
For our chosen design, our desired security properties rely on the following assumptions:
$BalanceNote PrivacyNote Privacy (OOB)Spend UnlinkabilityFaerie Resistance DL_{E}HashDH_{E}Near perfect‡DDH_{E}∨PRF_{F}DL_{E} $
$HashDH_{E}$ is computational DiffieHellman using $KDF$ for the key derivation, with onetime ephemeral keys. This assumption is heuristically weaker than $DDH_{E}$ but stronger than $DL_{E}$.
We omit $RO_{GH}$ as a security assumption because we only rely on the random oracle applied to fixed inputs defined by the protocol, i.e. to generate the fixed base $G$, not to attackerspecified inputs.
$†$ We additionally assume that for any input $x$, ${F_{nk}(x):nk∈E}$ gives a scalar in an adequate range for $DDH_{E}$. (Otherwise, $F$ could be trivial, e.g. independent of $nk$.)
$‡$ Statistical distance $<2_{−167.8}$ from perfect.
Considered alternatives
$⚠Caution$: be skeptical of the claims in this table about what problem(s) each security property depends on. They may not be accurate and are definitely not fully rigorous.
The entries in this table omit the application of $Extract_{P}$, which is an optimization to halve the nullifier length. That optimization requires its own security analysis, but because it is a deterministic mapping, only Faerie Resistance could be affected by it.
$nf[nk][θ]H[nk]H+[rnf]IHash([nk][θ]H)Hash([nk]H+[rnf]I)[F(ψ)][θ]H[F(ψ)]H+[rnf]I[F(ψ)]G+[θ]H[F(ψ)]H+cm[F(ρ,ψ)]G+cm[F(ρ)]G+cm[F(ρ,ψ)]G+[rnf]I[F(ρ)]G+[rnf]I[(F(ρ)+ψ)modp]G[F(ρ,ψ)]G+Commit(v,ρ)[F(ρ)]G+Commit(v,ρ) Note(addr,v,H,θ,rcm)(addr,v,H,rnf,rcm)(addr,v,H,θ,rcm)(addr,v,H,rnf,rcm)(addr,v,H,θ,ψ,rcm)(addr,v,H,rnf,ψ,rcm)(addr,v,H,θ,ψ,rcm)(addr,v,H,ψ,rcm)(addr,v,ρ,ψ,rcm)(addr,v,ρ,rcm)(addr,v,ρ,rnf,ψ,rcm)(addr,v,ρ,rnf,rcm)(addr,v,ρ,ψ,rcm)(addr,v,ρ,rnf,ψ,rcm)(addr,v,ρ,rnf,rcm) BalanceDLDLDLDLDLDLDLDLDLDLDLDLDLDLDL Note PrivacyHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDHHashDH Note Priv OOBPerfectPerfectPerfectPerfectPerfectPerfectPerfectDDHDDHDDHPerfectPerfectNear perfect‡PerfectPerfect Spend UnlinkabilityDDHDDHDDH∨PreDDH∨PreDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRFDDH∨PRF Faerie ResistanceRO∧DLRO∧DLColl∧RO∧DLColl∧RO∧DLRO∧DLRO∧DLRO∧DLRO∧DLDLDLColl∧DLColl∧DLbrokenDLDL Reason not to useNo SU for DLbreakingNo SU for DLbreakingCollfor FRCollfor FRPerf. (2 varbase)Perf. (1 var+1 fixbase)Perf. (1 var+1 fixbase)NP(OOB) not perfectNP(OOB) not perfectNP(OOB) not perfectCollfor FRCollfor FRbroken for FRPerf. (2 fixbase)Perf. (2 fixbase) $
In the above alternatives:

$Hash$ is a keyed circuitefficient hash (such as Rescue).

$I$ is an fixed independent base, independent of $G$ and any others returned by $GH$.

$G_{v}$ is a pair of fixed independent bases (independent of all others), where the specific choice of base depends on whether the note has zero value.

$H$ is a base unique to this output.
 For nonzerovalued notes, $H=GH(ρ)$. As with $h_{Sig}$ in Sprout, $ρ$ includes the nullifiers of any Orchard notes being spent in the same action.
 For zerovalued notes, $H$ is constrained by the circuit to a fixed base independent of $I$ and any others returned by $GH$.
Rationale
In order to satisfy the Balance security property, we require that the circuit must be able to enforce that only one nullifier is accepted for a given note. As in Sprout and Sapling, we achieve this by ensuring that the nullifier deterministically depends only on values committed to (directly or indirectly) by the note commitment. As in Sapling, this involves arguing that:
 There can be only one $ivk$ for a given $addr$. This is true because the circuit checks that $pk_{d}=[ivk]g_{d}$, and the mapping $ivk↦[ivk]g_{d}$ is an injection for any $g_{d}$. ($ivk$ is in the base field of $E$, which must be smaller than its scalar field, as is the case for Pallas.)
 There can be only one $nk$ for a given $ivk$. This is true because the circuit checks that $ivk=ShortCommit_{rivk}(ak,nk)$ where $ShortCommit$ is binding (see Commitments).
Faerie Resistance requires that nullifiers be unique. This is primarily achieved by taking a unique value (checked for uniqueness by the public consensus rules) as an input to the nullifier. However, it is also necessary to ensure that the transformations applied to this value preserve its uniqueness. Meanwhile, to achieve Spend Unlinkability, we require that the nullifier does not reveal any information about the unique value it is derived from.
The design alternatives fall into two categories in terms of how they balance these requirements:

Publish a unique value $ρ$ at note creation time, and blind that value within the nullifier computation.
 This is similar to the approach taken in Sprout and Sapling, which both implemented nullifiers as PRF outputs; Sprout uses the compression function from SHA256, while Sapling uses BLAKE2s.

Derive a unique base $H$ from some unique value, publish that unique base at note creation time, and then blind the base (either additively or multiplicatively) during nullifier computation.
For Spend Unlinkability, the only value unknown to the adversary is $nk$, and the cryptographic assumptions only involve the first term (other terms like $cm$ or $[rnf]I$ cannot be extracted directly from the observed nullifiers, but can be subtracted from them). We therefore ensure that the first term does not commit directly to the note (to avoid a DLbreaking adversary from immediately breaking SU).
We were considering using a design involving $H$ with the goal of eliminating all usages of a PRF inside the circuit, for two reasons:
 Instantiating $PRF_{F}$ with a traditional hash function is expensive in the circuit.
 We didn't want to solely rely on an algebraic hash function satisfying $PRF_{F}$ to achieve Spend Unlinkability.
However, those designs rely on both $RO_{GH}$ and $DL_{E}$ for Faerie Resistance, while still requiring $DDH_{E}$ for Spend Unlinkability. (There are two designs for which this is not the case, but they rely on $DDH_{E}$ for Note Privacy (OOB) which was not acceptable).
By contrast, several designs involving $ρ$ (including the chosen design) have weaker assumptions for Faerie Resistance (only relying on $DL_{E}$), and Spend Unlinkability does not require $PRF_{F}$ to hold: they can fall back on the same $DDH_{E}$ assumption as the $H$ designs (along with an additional assumption about the output of $F$ which is easily satisfied).
Most of the designs include either a multiplicative blinding term $[θ]H$, or an additive blinding term $[rnf]I$, in order to achieve perfect Note Privacy (OOB) (to an adversary who does not know the note). The chosen design is effectively using $[ψ]G$ for this purpose; a DLbreaking adversary only learns $F_{nk}(ρ)+ψ(modp)$. This reduces Note Privacy (OOB) from perfect to statistical, but given that $ψ$ is from a distribution statistically close to uniform on $[0,q)$, this is statistically close to better than $2_{−128}$. The benefit is that it does not require an additional scalar multiplication, making it more efficient inside the circuit.
$ψ$'s derivation has two motivations:
 Deriving from a random value $rseed$ enables multiple derived values to be conveyed to the recipient within an action (such as the ephemeral secret $esk$, per ZIP 212), while keeping the note plaintext short.
 Mixing $ρ$ into the derivation ensures that the sender can't repeat $ψ$ across two notes, which could have enabled spend linkability attacks in some designs.
The note that is committed to, and which the circuit takes as input, only includes $ψ$ (i.e. the circuit does not check the derivation from $rseed$). However, an adversarial sender is still constrained by this derivation, because the recipient recomputes $ψ$ during note decryption. If an action were created using an arbitrary $ψ$ (for which the adversary did not have a corresponding $rseed$), the recipient would derive a note commitment that did not match the action's commitment field, and reject it (as in Sapling).
The nullifier commits to the note value via $cm$ for two reasons:
 It domainseparates nullifiers for zerovalued notes from other notes. This is necessary because we do not require zerovalued notes to exist in the commitment tree.
 Designs that bind the nullifier to $F_{nk}(ρ)$ require $Coll_{F}$ to achieve Faerie Resistance (and similarly where $Hash$ is applied to a value derived from $H$). Adding $cm$ to the nullifier avoids this assumption: all of the bases used to derive $cm$ are fixed and independent of $G$, and so the nullifier can be viewed as a Pedersen hash where the input includes $ρ$ directly.
The $Commit_{nf}$ variants were considered to avoid directly depending on $cm$ (which in its native type is a base field element, not a group element). We decided instead to follow Sapling by defining an intermediate representation of $cm$ as a group element, that is only used in nullifier computation. The circuit already needs to compute $cm$, so this improves performance by removing
We also considered variants that used a choice of fixed bases $G_{v}$ to provide domain separation for zerovalued notes. The most performant design (similar to the chosen design) does not achieve Faerie Resistance for an adversary that knows the recipient's full viewing key ($ψ$ could be bruteforced to cancel out $F_{nk}(ρ)$, causing a collision), and the other variants require assuming $Coll_{F}$ as mentioned above.
Signatures
Orchard signatures are an instantiation of RedDSA with a cofactor of 1.
TODO:
 Should it be possible to sign partial transactions?
 If we're going to merge down all the signatures into a single one, and also want this, we need to ensure there's a feasible MPC.
Circuit
Gadgets
The Orchard circuit makes use of the following gadgets from the halo2_gadgets
crate:
 Elliptic curve:
FixedPoint
FixedPointBaseField
FixedPointShort
NonIdentityPoint
Point
 Poseidon:
Hash<ConstantLength>
 Sinsemilla:
CommitDomain
Message
MessagePiece
MerklePath
It instantiates the instruction sets required for these gadgets with the following chips:
halo2_gadgets::ecc::chip::EccChip
halo2_gadgets::poseidon::Pow5Chip
halo2_gadgets::sinsemilla::chip::SinsemillaChip
halo2_gadgets::sinsemilla::merkle::chip::MerkleChip
halo2_gadgets::utilities::UtilitiesInstructions
halo2_gadgets::utilities::lookup_range_check::LookupRangeCheckConfig
It also makes use of the following utility functions for standardising constraints:
halo2_gadgets::utilities::{bitrange_subset, bool_check}
Message decomposition
$SinsemillaShortCommit$ is used in the $Commit_{ivk}$ function. The input to $SinsemillaShortCommit$ is:
$I2LEBSP_{ℓ_{base}}(ak)∣∣I2LEBSP_{ℓ_{base}}(nk),$
where $ak$, $nk$ are Pallas base field elements, and $ℓ_{base}=255.$
Sinsemilla operates on multiples of 10 bits, so we start by decomposing the message into chunks:
$I2LEBSP_{ℓ_{base}}(ak)I2LEBSP_{ℓ_{base}}(nk) =a∣∣b_{0}∣∣b_{1}=(bits 0..=249 ofak)∣∣(bits 250..=253 ofak)∣∣(bit 254 ofak)=b_{2}∣∣c∣∣d_{0}∣∣d_{1}=(bits 0..=4 ofnk)∣∣(bits 5..=244 ofnk)∣∣(bits 245..=253 ofnk)∣∣(bit 254 ofnk) $
Then we recompose the chunks into message pieces:
$Length (bits)2501024010 Pieceab=b_{0}∣∣b_{1}∣∣b_{2}cd=d_{0}∣∣d_{1} $
Each message piece is constrained by $SinsemillaHash$ to its stated length. Additionally, $ak$ and $nk$ are witnessed as field elements, so we know they are canonical. However, we need additional constraints to enforce that:
 The chunks are the correct bit lengths (or else they could overlap in the decompositions and allow the prover to witness an arbitrary $SinsemillaShortCommit$ message).
 The chunks contain the canonical decompositions of $ak$ and $nk$ (or else the prover could witness an input to $SinsemillaShortCommit$ that is equivalent to $ak$ and $nk$ but not identical).
Some of these constraints can be implemented with reusable circuit gadgets. We define a custom gate controlled by the selector $q_{Commit_{ivk}}$ to hold the remaining constraints.
Bit length constraints
Chunks $a$ and $c$ are directly constrained by Sinsemilla. For the remaining chunks, we use the following constraints:
$Degree33 Constraintshort_lookup_range_check(b_{0},4)short_lookup_range_check(b_{2},5)short_lookup_range_check(d_{0},9)q_{Commit_{ivk}}⋅bool_check(b_{1})=0q_{Commit_{ivk}}⋅bool_check(d_{1})=0 $
where $bool_check(x)=x⋅(1−x)$ and $short_lookup_range_check()$ is a short lookup range check.
Decomposition constraints
We have now derived or witnessed every subpiece, and rangeconstrained every subpiece:
 $a$ ($250$ bits) is witnessed and constrained outside the gate;
 $b_{0}$ ($4$ bits) is witnessed and constrained outside the gate;
 $b_{1}$ ($1$ bits) is witnessed and booleanconstrained in the gate;
 $b_{2}$ ($5$ bits) is witnessed and constrained outside the gate;
 $c$ ($240$ bits) is witnessed and constrained outside the gate;
 $d_{0}$ ($9$ bits) is witnessed and constrained outside the gate;
 $d_{1}$ ($1$ bits) is witnessed and booleanconstrained in the gate.
We can now use them to reconstruct both the (chunked) message pieces, and the original field element inputs:
$bdaknk =b_{0}+2_{4}⋅b_{1}+2_{5}⋅b_{2}=d_{0}+2_{9}⋅d_{1}=a+2_{250}⋅b_{0}+2_{254}⋅b_{1}=b_{2}+2_{5}⋅c+2_{245}⋅d_{0}+2_{254}⋅d_{1} $
$Degree2222 Constraintq_{Commit_{ivk}}⋅(b−(b_{0}+b_{1}⋅2_{4}+b_{2}⋅2_{5}))=0q_{Commit_{ivk}}⋅(d−(d_{0}+d_{1}⋅2_{9}))=0q_{Commit_{ivk}}⋅(a+b_{0}⋅2_{250}+b_{1}⋅2_{254}−ak)=0q_{Commit_{ivk}}⋅(b_{2}+c⋅2_{5}+d_{0}⋅2_{245}+d_{1}⋅2_{254}−nk)=0 $
Canonicity checks
At this point, we have constrained $I2LEBSP_{ℓ_{base}}(ak)$ and $I2LEBSP_{ℓ_{base}}(nk)$ to be 255bit values, with top bits $b_{1}$ and $d_{1}$ respectively. We have also constrained:
$I2LEBSP_{ℓ_{base}}(ak)I2LEBSP_{ℓ_{base}}(nk) =ak(modq_{P})=nk(modq_{P}) $
where $q_{P}$ is the Pallas base field modulus. The remaining constraints will enforce that these are indeed canonicallyencoded field elements, i.e.
$I2LEBSP_{ℓ_{base}}(ak)I2LEBSP_{ℓ_{base}}(nk) <q_{P}<q_{P} $
The Pallas base field modulus has the form $q_{P}=2_{254}+t_{P}$, where $t_{P}=0x224698fc094cf91b992d30ed00000001$ is 126 bits. We therefore know that if the top bit is not set, then the remaining bits will always comprise a canonical encoding of a field element. Thus the canonicity checks below are enforced if and only if $b_{1}=1$ (for $ak$) or $d_{1}=1$ (for $nk$).
In the constraints below we use a base$2_{10}$ variant of the method used in libsnark (originally from [SVPBABW2012, Appendix C.1]) for range constraints $0≤x<t$:
 Let $t_{′}$ be the smallest power of $2_{10}$ greater than $t$.
 Enforce $0≤x<t_{′}$.
 Let $x_{′}=x+t_{′}−t$.
 Enforce $0≤x_{′}<t_{′}$.
In these cases, we check that $ak_{0..=253}<t_{P}$:

$b_{1}=1⟹b_{0}=0.$
Since $b_{1}=1⟹ak_{0..=253}<t_{P}<2_{126},$ we know that $ak_{126..=253}=0,$ and in particular $b_{0}:=ak_{250..=253}=0.$

$b_{1}=1⟹0≤a<t_{P}.$
To check that $a<t_{P}$, we use two constraints:
a) $0≤a<2_{130}$. This is expressed in the custom gate as $b_{1}⋅z_{a,13}=0,$ where $z_{a,13}$ is the index13 running sum output by $SinsemillaHash(a).$
b) $0≤a+2_{130}−t_{P}<2_{130}$. To check this, we decompose $a_{′}=a+2_{130}−t_{P}$ into thirteen 10bit words (littleendian) using a running sum $z_{a_{′}}$, looking up each word in a $10$bit lookup table. We then enforce in the custom gate that $b_{1}⋅z_{a_{′},13}=0.$
$Degree3323 Constraintq_{Commit_{ivk}}⋅b_{1}⋅b_{0}=0q_{Commit_{ivk}}⋅b_{1}⋅z_{a,13}=0q_{Commit_{ivk}}⋅(a+2_{130}−t_{P}−a_{′})=0q_{Commit_{ivk}}⋅b_{1}⋅z_{a_{′},13}=0 $
In these cases, we check that $nk_{0..=253}<t_{P}$:

$d_{1}=1⟹d_{0}=0.$
Since $d_{1}=1⟹nk_{0..=253}<t_{P}<2_{126},$ we know that $nk_{126..=253}=0,$ and in particular $d_{0}:=nk_{245..=253}=0.$

$d_{1}=1⟹0≤b_{2}+2_{5}⋅c<t_{P}.$
To check that $0≤b_{2}+2_{5}⋅c<t_{P}$, we use two constraints:
a) $0≤b_{2}+2_{5}⋅c<2_{140}$. $b_{2}$ is already constrained individually to be a $5$bit value. $z_{c,13}$ is the index13 running sum output by $SinsemillaHash(c).$ By constraining $d_{1}⋅z_{c,13}=0,$ we constrain $b_{2}+2_{5}⋅c<2_{135}<2_{140}.$
b) $0≤b_{2}+2_{5}⋅c+2_{140}−t_{P}<2_{140}$. To check this, we decompose $b_{2}c_{′}=b_{2}+2_{5}⋅c+2_{140}−t_{P}$ into fourteen 10bit words (littleendian) using a running sum $z_{b_{2}c_{′}}$, looking up each word in a $10$bit lookup table. We then enforce in the custom gate that $d_{1}⋅z_{b_{2}c_{′},14}=0.$
$Degree3323 Constraintq_{Commit_{ivk}}⋅d_{1}⋅d_{0}=0q_{Commit_{ivk}}⋅d_{1}⋅z_{c,13}=0q_{Commit_{ivk}}⋅(b_{2}+c⋅2_{5}+2_{140}−t_{P}−b_{2}c_{′})=0q_{Commit_{ivk}}⋅d_{1}⋅z_{b_{2}c_{′},14}=0 $
Region layout
The constraints controlled by the $q_{Commit_{ivk}}$ selector are arranged across 9 advice columns, requiring two rows.
$aknk ac bd b_{0}d_{0} b_{1}d_{1} b_{2} z_{a,13}z_{c,13} a_{′}b_{2}c_{′} z_{a_{′},13}z_{b_{2}c_{′},14} q_{Commit_{ivk}}10 $
NoteCommit
Message decomposition
$SinsemillaCommit$ is used in the $NoteCommit$ function. The input to $SinsemillaCommit$ is:
$g⋆_{d}∣∣pk⋆_{d}∣∣I2LEBSP_{64}(v)∣∣I2LEBSP_{ℓ_{base}}(ρ)∣∣I2LEBSP_{ℓ_{base}}(ψ),$
where:
 $g⋆_{d},pk⋆_{d}$ are representations of Pallas curve points, with $255$ bits used for the $x$coordinate and $1$ bit used for the $y$coordinate.
 $ρ,ψ$ are Pallas base field elements.
 $v$ is a $64$bit value.
 $ℓ_{base}=255.$
Sinsemilla operates on multiples of 10 bits, so we start by decomposing the message into chunks:
$g⋆_{d}pk⋆_{d}I2LEBSP_{64}(v)I2LEBSP_{ℓ_{base}}(ρ)I2LEBSP_{ℓ_{base}}(ψ) =a∣∣b_{0}∣∣b_{1}∣∣b_{2}=(bits 0..=249 ofx(g_{d}))∣∣(bits 250..=253 ofx(g_{d}))∣∣(bit 254 ofx(g_{d}))∣∣(y~ bit ofg_{d})=b_{3}∣∣c∣∣d_{0}∣∣d_{1}=(bits 0..=3 ofx(pk_{d}))∣∣(bits 4..=253 ofx(pk_{d}))∣∣(bit 254 ofx(pk_{d}))∣∣(y~ bit ofpk_{d})=d_{2}∣∣d_{3}∣∣e_{0}=(bits 0..=7 ofv)∣∣(bits 8..=57 ofv)∣∣(bits 58..=63 ofv)=e_{1}∣∣f∣∣g_{0}=(bits 0..=3 ofρ)∣∣(bits 4..=253 ofρ)∣∣(bit 254 ofρ)=g_{1}∣∣g_{2}∣∣h_{0}∣∣h_{1}=(bits 0..=8 ofψ)∣∣(bits 9..=248 ofψ)∣∣(bits 249..=253 ofψ)∣∣(bit 254 ofψ) $
Then we recompose the chunks into message pieces:
$Length (bits)25010250601025025010 Pieceab=b_{0}∣∣b_{1}∣∣b_{2}∣∣b_{3}cd=d_{0}∣∣d_{1}∣∣d_{2}∣∣d_{3}e=e_{0}∣∣e_{1}fg=g_{0}∣∣g_{1}∣∣g_{2}h=h_{0}∣∣h_{1}∣∣h_{2} $
where $h_{2}$ is 4 zero bits (corresponding to the padding applied by the Sinsemilla $pad$ function).
Each message piece is constrained by $SinsemillaHash$ to its stated length. Additionally:
 $g_{d}$ and $pk_{d}$ are witnessed and checked to be valid elliptic curve points.
 $v$ is witnessed as a field element, but its decomposition is sufficient to constrain it to be a 64bit value.
 $ρ$ and $ψ$ are witnessed as field elements, so we know they are canonical.
However, we need additional constraints to enforce that:
 The chunks are the correct bit lengths (or else they could overlap in the decompositions and allow the prover to witness an arbitrary $SinsemillaCommit$ message).
 The chunks contain the canonical decompositions of $g_{d}$, $pk_{d}$, $ρ$, and $ψ$ (or else the prover could witness multiple equivalent inputs to $SinsemillaCommit$).
Some of these constraints are implemented with a reusable circuit gadget, $short_lookup_range_check()$. We define custom gates for the remainder. Since these gates use simple boolean selectors activated on different rows, their selectors are eligible for combining, reducing the overall proof size.
Message piece decomposition
We check the decomposition of each message piece in its own region. There is no need to check the whole pieces:
 $a$ ($250$ bits) is witnessed and constrained outside the gate;
 $c$ ($250$ bits) is witnessed and constrained outside the gate;
 $f$ ($250$ bits) is witnessed and constrained outside the gate;
The following helper gates are defined:
 $bool_check(x)=x⋅(1−x)$.
 $short_lookup_range_check()$ is a short lookup range check.
$b$ has been constrained to be $10$ bits by the Sinsemilla hash.
Region layout
$A_{6}b A_{7}b_{0}b_{2} A_{8}b_{1}b_{3} q_{NoteCommit,b}10 $
Constraints
$Degree332 Constraintq_{NoteCommit,b}⋅bool_check(b_{1})=0q_{NoteCommit,b}⋅bool_check(b_{2})=0q_{NoteCommit,b}⋅(b−(b_{0}+b_{1}⋅2_{4}+b_{2}⋅2_{5}+b_{3}⋅2_{6}))=0 $
Outside this gate, we have constrained:
 $short_lookup_range_check(b_{0},4)$
 $short_lookup_range_check(b_{3},4)$
$d$ has been constrained to be $60$ bits by the $SinsemillaHash$.
Region layout
$A_{6}d A_{7}d_{0}d_{2} A_{8}d_{1}d_{3} q_{NoteCommit,d}10 $
Constraints
$Degree332 Constraintq_{NoteCommit,d}⋅bool_check(d_{0})=0q_{NoteCommit,d}⋅bool_check(d_{1})=0q_{NoteCommit,d}⋅(d−(d_{0}+d_{1}⋅2+d_{2}⋅2_{2}+d_{3}⋅2_{10}))=0 $
Outside this gate, we have constrained:
 $short_lookup_range_check(d_{2},8)$
 $d_{3}$ is equalityconstrained to $z_{d,1}$, where the latter is the index1 running sum output of $SinsemillaHash(d),$ constrained by the hash to be $50$ bits.
$e$ has been constrained to be $10$ bits by the $SinsemillaHash$.
Region layout
$A_{6}e A_{7}e_{0} A_{8}e_{1} q_{NoteCommit,e}1 $
Constraints
$Degree2 Constraintq_{NoteCommit,e}⋅(e−(e_{0}+e_{1}⋅2_{6}))=0 $
Outside this gate, we have constrained:
 $short_lookup_range_check(e_{0},6)$
 $short_lookup_range_check(e_{1},4)$
$g$ has been constrained to be $250$ bits by the $SinsemillaHash$.
Region layout
$A_{6}gg_{1} A_{7}g_{0}g_{2} q_{NoteCommit,g}10 $
Constraints
$Degree32 Constraintq_{NoteCommit,g}⋅bool_check(g_{0})=0q_{NoteCommit,g}⋅(g−(g_{0}+g_{1}⋅2+g_{2}⋅2_{10}))=0 $
Outside this gate, we have constrained:
 $short_lookup_range_check(g_{1},9)$
 $g_{2}$ is equalityconstrained to $z_{g,1}$, where the latter is the index1 running sum output of $SinsemillaHash(g),$ constrained by the hash to be 240 bits.
$h$ has been constrained to be $10$ bits by the $SinsemillaHash$.
Region layout
$A_{6}h A_{7}h_{0} A_{8}h_{1} q_{NoteCommit,h}1 $
Constraints
$Degree32 Constraintq_{NoteCommit,h}⋅bool_check(h_{1})=0q_{NoteCommit,h}⋅(h−(h_{0}+h_{1}⋅2_{5}))=0 $
Outside this gate, we have constrained:
 $short_lookup_range_check(h_{0},5)$
Field element checks
All message pieces and subpieces have been rangeconstrained by the earlier decomposition gates. They are now used to:
 constrain each field element $I2LEBSP_{ℓ_{base}}(x(g_{d}))$, $I2LEBSP_{ℓ_{base}}(x(pk_{d}))$, $I2LEBSP_{ℓ_{base}}(ρ)$, and $I2LEBSP_{ℓ_{base}}(ψ)$ to be 255bit values, with top bits $b_{1}$, $d_{0}$, $g_{0}$, and $h_{1}$ respectively.
 constrain $I2LEBSP_{ℓ_{base}}(x(g_{d}))I2LEBSP_{ℓ_{base}}(x(pk_{d}))I2LEBSP_{ℓ_{base}}(ρ)I2LEBSP_{ℓ_{base}}(ψ) =x(g_{d})(modq_{P})=x(pk_{d})(modq_{P})=ρ(modq_{P})=ψ(modq_{P}) $ where $q_{P}$ is the Pallas base field modulus.
 check that these are indeed canonicallyencoded field elements, i.e. $I2LEBSP_{ℓ_{base}}(x(g_{d}))I2LEBSP_{ℓ_{base}}(x(pk_{d}))I2LEBSP_{ℓ_{base}}(ρ)I2LEBSP_{ℓ_{base}}(ψ) <q_{P}<q_{P}<q_{P}<q_{P} $
The Pallas base field modulus has the form $q_{P}=2_{254}+t_{P}$, where $t_{P}=0x224698fc094cf91b992d30ed00000001$ is 126 bits. We therefore know that if the top bit is not set, then the remaining bits will always comprise a canonical encoding of a field element. Thus the canonicity checks below are enforced if and only if the corresponding top bit is set to 1.
In the constraints below we use a base$2_{10}$ variant of the method used in libsnark (originally from [SVPBABW2012, Appendix C.1]) for range constraints $0≤x<t$:
 Let $t_{′}$ be the smallest power of $2_{10}$ greater than $t$.
 Enforce $0≤x<t_{′}$.
 Let $x_{′}=x+t_{′}−t$.
 Enforce $0≤x_{′}<t_{′}$.
Recall that $x(g_{d})=a+2_{250}⋅b_{0}+2_{254}⋅b_{1}$. When the top bit $b_{1}$ is set, we check that $x(g_{d})_{0..=253}<t_{P}$:

$b_{1}=1⟹b_{0}=0.$
Since $b_{1}=1⟹x(g_{d})_{0..=253}<t_{P}<2_{126},$ we know that $x(g_{d})_{126..=253}=0,$ and in particular $b_{0}:=x(g_{d})_{250..=253}=0.$

$b_{1}=1⟹0≤a<t_{P}.$
To check that $a<t_{P}$, we use two constraints:
a) $0≤a<2_{130}$. This is expressed in the custom gate as $b_{1}⋅z_{a,13}=0,$ where $z_{a,13}$ is the index13 running sum output by $SinsemillaHash(a).$
b) $0≤a+2_{130}−t_{P}<2_{130}$. To check this, we decompose $a_{′}=a+2_{130}−t_{P}$ into thirteen 10bit words (littleendian) using a running sum $z_{a_{′}}$, looking up each word in a $10$bit lookup table. We then enforce in the custom gate that $b_{1}⋅z_{a_{′},13}=0.$
Region layout
$A_{6}x(g_{d}) A_{7}b_{0}b_{1} A_{8}aa_{′} A_{9}z_{a,13}z_{a_{′},13} q_{NoteCommit,x(g_{d})}10 $
Constraints
$Degree23323 Constraintq_{NoteCommit,x(g_{d})}⋅(a+b_{0}⋅2_{250}+b_{1}⋅2_{254}−x(g_{d}))=0q_{NoteCommit,x(g_{d})}⋅b_{1}⋅b_{0}=0q_{NoteCommit,x(g_{d})}⋅b_{1}⋅z_{a,13}=0q_{NoteCommit,x(g_{d})}⋅(a+2_{130}−t_{P}−a_{′})=0q_{NoteCommit,x(g_{d})}⋅b_{1}⋅z_{a_{′},13}=0 $
Recall that $x(pk_{d})=b_{3}+2_{4}⋅c+2_{254}⋅d_{0}$. When the top bit $d_{0}$ is set, we check that $x(pk_{d})_{0..=253}<t_{P}$:

$d_{0}=1⟹0≤b_{3}+2_{4}⋅c<t_{P}.$
To check that $0≤b_{3}+2_{4}⋅c<t_{P},$ we use two constraints:
a) $0≤b_{3}+2_{4}⋅c<2_{140}.$ $b_{3}$ is already constrained individually to be a $4$bit value. $z_{c,13}$ is the index13 running sum output by $SinsemillaHash(c).$ By constraining $d_{0}⋅z_{c,13}=0,$ we constrain $b_{3}+2_{4}⋅c<2_{134}<2_{140}.$
b) $0≤b_{3}+2_{4}⋅c+2_{140}−t_{P}<2_{140}$. To check this, we decompose $b_{3}c_{′}=b_{3}+2_{4}⋅c+2_{140}−t_{P}$ into fourteen 10bit words (littleendian) using a running sum $z_{b_{3}c_{′}}$, looking up each word in a $10$bit lookup table. We then enforce in the custom gate that $d_{0}⋅z_{b_{3}c_{′},14}=0.$
Region layout
$A_{6}x(pk_{d}) A_{7}b_{3}d_{0} A_{8}cb_{3}c_{′} A_{9}z_{c,13}z_{b_{3}c_{′},14} q_{NoteCommit,x(pk_{d})}10 $
Constraints
$Degree2323 Constraintq_{NoteCommit,x(pk_{d})}⋅(b_{3}+c⋅2_{4}+d_{0}⋅2_{254}−x(pk_{d})=0q_{NoteCommit,x(pk_{d})}⋅d_{0}⋅z_{c,13}=0q_{NoteCommit,x(pk_{d})}⋅(b_{3}+c⋅2_{4}+2_{140}−t_{P}−b_{3}c_{′})=0q_{NoteCommit,x(pk_{d})}⋅d_{0}⋅z_{b_{3}c_{′},14}=0 $
Region layout
$A_{6}value A_{7}d_{2} A_{8}d_{3} A_{9}e_{0} q_{NoteCommit,value}1 $
Constraints
$Degree2 Constraintq_{NoteCommit,value}⋅(d_{2}+d_{3}⋅2_{8}+e_{0}⋅2_{58}−value)=0 $
Recall that $ρ=e_{1}+2_{4}⋅f+2_{254}⋅g_{0}$. When the top bit $g_{0}$ is set, we check that $ρ_{0..=253}<t_{P}$:

$g_{0}=1⟹0≤e_{1}+2_{4}⋅f<t_{P}.$
To check that $0≤e_{1}+2_{4}⋅f<t_{P},$ we use two constraints:
a) $0≤e_{1}+2_{4}⋅f<$