changed 4 years ago  
Linked with GitHub

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)\).

Select a repo