Orchard straw protocol: https://hackmd.io/Yyz4wYntSASHfpvqNN4fYQ?both
\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline x_A & y_A & x_P & y_P & \lambda_1 & \lambda_2 & q_{add} & q_{double} & q_{mul} & q_{mul\_fixed} & q_{point} \\ \hline 0 & 0 & x_p & y_p & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline \end{array}
Constraints:
(Refer to https://zcash.github.io/halo2/background/curves.html#point-doubling for point doubling formula)
Input: \(P = (x_P, y_P)\)
Output: \(A = [2]P = (x_A, y_A)\)
\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline x_A & y_A & x_P & y_P & q_{add} & q_{double} & q_{mul} & q_{mul\_fixed} \\ \hline x_a & y_a & x_p & y_p & 0 & 1 & 0 & 0 \\ \hline \end{array}
Formulae:
\(\lambda_1 = \frac{3 x_p^2}{2 \cdot y_p}\)
\(x_a = \lambda_1^2 - 2 \cdot x_p\)
\(y_a = \lambda_1(x_p - x_a) - y_p\)
Substituting for \(\lambda_1\), we get the constraints:
\(4 \cdot y_p^2(x_a + 2 \cdot x_p) - 9 x_p^4 = 0\)
\(2 \cdot y_p(y_a + y_p) - 3 x_p^2(x_p - x_a) = 0\)
(Refer to https://zcash.github.io/halo2/background/curves.html#todo-point-addition for point addition formula)
Inputs: \(P = (x_P, y_P), Q = (x_Q, y_Q)\)
Output: \(A = P + Q = (x_A, y_A)\)
\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline x_A & y_A & x_P & y_P & q_{add} & q_{double} & q_{mul} & q_{mul\_fixed} \\ \hline x_q & y_q & x_p & y_p & 1 & 0 & 0 & 0 \\ \hline x_a & y_a & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}
Formulae:
\(\lambda_1 \cdot (x_p - x_{q}) = y_p - y_{q}\)
\(x_{a} = \lambda_1^2 - x_{q} - x_p\)
\(y_{a} = \lambda_1(x_{q} - x_{a}) - y_{q}\)
Substituting for \(\lambda_1\), we get the constraints:
\((x_{a} + x_{q} + x_p) \cdot (x_p - x_q)^2 - (y_p - y_{q})^2 = 0\)
\((y_{a} + y_{q})(x_p - x_{q}) - (y_p - y_{q})(x_{q} - x_{a}) = 0\)
See https://hackmd.io/o9EzZBwxSWSi08kQ_fMIOw?view
For each fixed point, we precompute Lagrange interpolation polynomials for its multiples using 3-bit windows. Since we only need these points for scalar multiplication with 255-bit scalars, we can stop at \(\mathsf{ceiling}(255/3) = 85\) windows.
For some fixed base \(B,\) define a matrix: \(M[0..84][0..7]\) such that:
This avoids adding the point at infinity in the case \(k = 0\).
Assert that all the matrix entries have distinct \(x\)-coordinates. We don't have enough table space to use lookups (that would need \(5 \times \mathsf{ceiling}(255/3) \times 2^3\) entries for \(3\)-bit tables), so we should use interpolation instead.
(We checked that using fewer tables and some doublings doesn't help, relative to interpolation.)
For each set of fixed-base multiples \(M[w] = (M[w][0], \cdots, M[w][7]), w \in [0..84]\):
Repeating this for all \(85\) windows, we end up with:
Each \(x\)-coordinate interpolation polynomial will be of the form
\[\mathcal{L}_x[w](k) = c_0 + c_1 \cdot k + c_2 \cdot k^2 + \cdots + c_7 \cdot k^7,\]
where \(w \in [0..84]\) and \(c_k\)'s are the coefficients for each power.
Note that in the Orchard protocol, we have \(5\) fixed bases:
We reuse the same selector columns for each base.
We decompose a 255-bit scalar \(\alpha \in [0, q)\) in 3-bit windows (i.e. base \(2^3 = 8\)), which gives \(\mathsf{ceiling}(255 / 3) = 85\) windows:
\begin{align*} \alpha &= \sum\limits_{w = 0}^{84} k_w \cdot 8^w \\ &= \sum k_0 + k_1 \cdot 8 + k_2 \cdot 8^2 + \cdots + k_{84} 8^{84}. \end{align*}
where each \(k_w \in [0..7].\)
Assignment:
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
k & q_{witness\_scalar\_fixed}\\ \hline
k_0 & 1 \\ \hline
k_{1} & 1 \\ \hline
\vdots & 1 \\ \hline
k_{83} & 1 \\ \hline
k_{84} & 1 \\ \hline
\end{array}
Constraints:
\(q_{witness\_scalar\_fixed} \cdot \mathsf{range\_check\_8}(k_i)\)
We implement fixed-base scalar multiplication with precomputed points encoded in interpolation polynomials.
Given an input scalar \(\alpha\) and a fixed base \(B\), we compute \([\alpha]B\) as such:
Constraints:
\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline k & x_A & y_A & x_P & y_P & u_P & c_0 & c_1 & c_2 & c_3 & c_4 & c_5 & c_6 & c_7 & z & q_{add} & q_{mul\_fixed} & q_{witness\_point} \\ \hline k_0 & x_{a, 0} & y_{a, 0} & M[0][k_0]_x & M[0][k_0]_y & u_{0} &c_{0,0} & c_{1,0} & c_{2,0} & c_{3,0} & c_{4,0} & c_{5,0} & c_{6,0} & c_{7,0} & z_{0} & 1 & 1 & 1 \\ \hline k_{1} & x_{a,1} & y_{a,1} & M[1][k_1]_x & M[1][k_1]_y & u_{1} &c_{0,1} & c_{1,1} & c_{2,1} & c_{3,1} & c_{4,1} & c_{5,1} & c_{6,1} & c_{7,1} & z_{1} & 1 & 1 & 1 \\ \hline k_{2} & x_{a,2} & y_{a,2} & M[2][k_2]_x & M[2][k_2]_y & u_{2} &c_{0,2} & c_{1,2} & c_{2,2} & c_{3,2} & c_{4,2} & c_{5,2} & c_{6,2} & c_{7,2} & z_{2} & 1 & 1 & 1 \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \hline k_{84}& x_{a,84} & y_{a,84} & M[84][k_{84}]_x & M[84][k_{84}]_y & u_{84} & c_{0,84}& c_{1,84} & c_{2,84} & c_{3,84} & c_{4,84} & c_{5,84} & c_{6,84} & c_{7,84} & z_{84} & 1 & 1 & 1 \\ \hline & x_{a} & y_{a} & & & & & & & & & & & & & & & \\ \hline \end{array}
This is used for \(\mathsf{ValueCommit^{Orchard}}\).
We want to compute \(\mathsf{ValueCommit^{Orchard}_{rcv}}(\mathsf{v^{old}} - \mathsf{v^{new}}) = [\mathsf{v^{old}} - \mathsf{v^{new}}] \mathcal{V} + [\mathsf{rcv}] \mathcal{R}\), where
\[
-(2^{64}-1) \leq \mathsf{v^{old}} - \mathsf{v^{new}} \leq 2^{64}-1
\]
\(\mathsf{v^{old}}\) and \(\mathsf{v^{new}}\) are each already constrained to 64 bits (by their use as inputs to \(\mathsf{NoteCommit^{Orchard}}\)).
Witness the sign \(s\) and magnitude \(m\) such that
\[
s \in \{-1, 1\} \\
m \in [0, 2^{64}) \\
\mathsf{v^{old}} - \mathsf{v^{new}} = s \cdot m
\]
Then compute \(P = [m] \mathcal{V}\), and conditionally negate \(P\) using \((x, y) \mapsto (x, s \cdot y)\).
We need to precompute \(M[21][0..7]\): \(M[w][k] = [k \cdot (8)^w - \sum\limits_{j=0}^{20} (8)^j]B\)
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe