# Orchard straw-protocol

Circuit does one spend and one output (can be dummies).

Assume that a note is $(g_d, pk_d, v, \rho, \psi, rcm).$
* $(\rho, \psi, rcm)$ are derived from $rseed$ in a note plaintext.

Assume circuit size $\geq 2^m$ so that we can use $m$-bit tables for Sinsemilla and range checks. Probably $10 \leq m \leq 12$.

The circuit is primarily composed of Sinsemilla hashes and scalar multiplications. We optimise by storing these in adjacent columns, so we can perform them (somewhat) in parallel.

## Circuit

Public inputs:
- $rt$ (part of the bundle, not specific to an action)
- $cv^{balance}$
- Spent note:
- $nf^{old}$
- $rk$
- New output:
- $cm^{new}$
- $epk$?

Auxiliary inputs:
- Spent note:
- $path$ : Merkle path
- $pos$ : Position in tree
- $g_d^{old} : E*$
- $pk_d^{old} : E*$
- $v^{old}$
- $\rho^{old}$, $\psi^{old}$, and $rcm^{old}$
- derived from $rseed$ outside the circuit
- $\alpha$
- $rivk$
- $ak : E*$
- New output:
- $g_d^{new} : E*$
- $pk_d^{new} : \mathbb{B}^{[l_E]}$
- $v^{new}$
- $\rho^{new}$, $\psi^{new}$, and $rcm^{new}$
- derived from $rseed$ outside the circuit
- $esk$ (Optional)
- $rcv^{balance}$

Circuit checks:
- Type checks:
- $g_d^{old}$ is an affine point on the curve
- $g_d^{new}$ is an affine point on the curve
- $ak$ is an affine point on the curve
- $3 \times 1$ rows
- $v^{old}$ is in range $\{0..2^{64}-1\}$
- $v^{new}$ is in range $\{0..2^{64}-1\}$
- These are constrained as Sinsemilla inputs for $NoteCommit$
- Note commitments
- $cm^{old} = NoteCommit^{Orchard}_{rcm^{old}}(g_d^{old}, pk_d^{old}, v^{old}, \rho^{old}, \psi^{old})$
- $cm^{new} = NoteCommit^{Orchard}_{rcm^{new}}(g_d^{new}, pk_d^{new}, v^{new}, \rho^{new}, \psi^{new})$
- Committed data is $2 \times \ell_E + 64 + 2 \times \ell_F$
- TODO: Decide on point representation in commitment, and whether it is necessary to range-constrain coordinates. I think it is sufficient to constrain to $254$ bits.
- $2 \times ceiling\left(\frac{2 \times 2 \times 255 + 64 + 2 \times 255}{m}\right)$ Sinsemilla $+ 2 \times FixedBaseMul_{full}$ other
- $\approx 2 \times 145 = 290$ Sinsemilla ($m = 11$) $+ 2 \times 128 = 256$ other
- $\approx 2 \times 160 = 320$ Sinsemilla ($m = 10$) $+ 2 \times 128 = 256$ other
- Merkle tree
- 32 layers of Sinsemilla (2 elements -> 1 element)
- Either $v^{old} = 0$, or $(path, pos)$ is a valid Merkle path of depth 32 from $cm^{old}$ to $rt$.
- $32 \times \left[1 + ceiling\left(\frac{2 \times \ell_F}{m}\right)\right]$ rows
- $\approx 32 \times (1 + 47) = 1536$ Sinsemilla ($m = 11$)
- $\approx 32 \times (1 + 51) = 1664$ Sinsemilla ($m = 10$)
- Balance commitment (between the spend and output, signed 53/64-bit)
- $cv^{net} = ValueCommit_{rcv^{net}}(v^{old} - v^{new})$
- $2 \times \left(FixedBaseMul_{i65} + FixedBaseMul_{full}\right)$ other
- $\approx 2 \times (33 + 128) = 322$ other
- Nullifier computation / integrity
- $nf^{old} = [(Hash_{nk^{old}}(\rho^{old}) + \psi) \bmod p] \mathcal{K}^\mathsf{Orchard} + cm$
- $PoseidonHash_{1} + FixedBaseMul_{full} + 1$ other
- $\approx 36 + 128 + 1 = 165$ other
- Spend authority
- $rk = SpendAuthSig.RandomizePublic(\alpha, ak) = [\alpha] \mathcal{G} + ak$
- $FixedBaseMul_{full} + 1$ other
- $\approx 128 + 1 = 129$ other
- Diversified address integrity
- $ivk = Comm^{Orchardivk}_{rivk}(ak_x, nk)$
- Derive $ak$ such that its $x$-coordinate, and $nk$, and $ivk$, fit in $254$ bits.
- Need to brute force this during key generation.
- TODO: Decide whether we have a separate $nk$
- $ceiling\left(\frac{\ell_F + \ell_F}{m}\right)$ Sinsemilla $+ FixedBaseMul_{full}$ other
- $\approx 47$ Sinsemilla ($m = 11$) $+ 128$ other
- $\approx 51$ Sinsemilla ($m = 10$) $+ 128$ other
- $pk_d^{old} = [ivk] g_d^{old}$
- $VariableBaseMul_{full}$ rows
- $\approx 256$ rows
- Arbitrary UDA support
- Increase size of note commitment inputs by 255 bits each
- $\approx 47$ Sinsemilla ($m = 11$)
- $\approx 52$ Sinsemilla ($m = 10$)
- Replace fixed-base mul with variable-base in balance commitment
- $\approx 322$ other
- Fudge factor for asset list handling
- $\approx 50$ other

Total, *not* taking into account parallelism; excludes "Ephemeral public key integrity":
- $2035$ Sinsemilla ($m = 10$) $+ 1259$ other
- $1018$ pairs of Sinsemilla + $630$ other
- $1873$ Sinsemilla ($m = 11$) $+ 1259$ other
- $1582$ Sinsemilla ($m = 12$) $+ 1259$ other
- $1920$ Sinsemilla ($m = 11$) $+ 1631$ other with arbitrary UDAs

We can do all of the Sinsemilla lookups ($1896$ rows for $m = 11$) in parallel with the rest of the circuit.
This requires:
- for Sinsemilla:
- $2$ advice columns for the accumulator
- $1$ advice column for the running scalar $z_i$
- $2$ advice columns for $P_i$
- $1$ advice column for the permuted input $A'$ to the lookup
- $1$ advice column for the lookup product
- $1$ advice column for the permuted table $S'$
- $3$ fixed columns for the table $S$
- $2$ advice columns for $\lambda_{1,i}$ and $\lambda_{2,i}$
- for another scalar mul (in parallel):
- $2$ advice columns for the accumulator (copyable)
- $1$ advice column for the running scalar (copyable)
- $2$ advice columns for the base
- $2$ advice columns for $\lambda_{1,i}$ and $\lambda_{2,i}$
- selector columns:
- $1$ fixed column to select ECCLookup
- $1$ fixed column to initialize / copy out the ECCLookup accumulator and scalar
- $1$ fixed column to select scalar mul
- $1$ fixed column for the Rescue round constant (Rescue could reuse other columns)
- $2$ fixed columns for addition and multiplication selectors (possibly more)

for a total of $17$ advice columns and at least $9$ fixed columns.

Notes:
- No small-order checks, since we are using a prime-order curve.
- Validity of $pk_d^{new}$ is *not* checked in this circuit.
- The order of the curve $r_E$ is just over $2^k$, so we represent scalars as $k$ bits, and do not need to check canonicity.
- TODO: Decide whether to do that or use the full scalar range to get perfect (rather than statistical) hiding.

## Fixed bases

* $\mathcal{K}^{\mathsf{Orchard}}$
* base for $\mathsf{NoteCommit^{Orchard}}$
* $\mathcal{V}$ and $\mathcal{R}$ bases for $\mathsf{ValueCommit^\mathsf{Orchard}}$
* $\mathcal{G}$ base for $\mathsf{SpendAuthSig}^\mathsf{Orchard}$

So that's $5$ bases, and we have just under $2^{10}$ table space available. So we can use $\mathsf{floor}(\log_2(1000/5)) = 7$-bit windows for fixed-base multiplication.

### Fixed-base windowing

Suppose that we want to calculate $[x] G$ where $x = \sum\limits_{i=0}^m b_i \cdot 2^{ki}$, where $k$ is window width.

This is equal to $\sum\limits_{i=0}^m \left([b_i] ([2^{ki}] G)\right)$.