Suppose the scalar field of the curve
\[y^2 = x^3 + b\]
is \(F_q\) where \(q\) has 256 bits and the baby Jubjub prime is \(p\) which is slightly less 254-bit. Choose \(n\) and \(k\) so that
where \(\epsilon\) is a small constant.
We represent BigInts with \(k\) registers of \(n\) bits each. For register size \(X = 2^n\), define addition and multiplication without carries by:
Define \(n_{z_i} = \lceil log_2(z_i) \rceil\) for a signal \(x\). This function represents the number of bits needed to represent \(x\).
For an array \(z = \sum_i z_i X^i\), define \(n_z = \max_i (n_{z_i})\). Tracking \(n_z\) allows us to ensure that we are never overflowing the maximum theoretical register size of 253 bits, even when representing numbers in overflow representation.
Additionally, define \(k_z\) to be the number of such \(n_z\)-bit registers used to represent \(k\).
Suppose that \(c = a +' b\). Then \(n_c \leq \max(n_a, n_b) + 1\), and \(k_c = \max(k_a, k_b)\).
Now suppose that \(d = a *' b\). Then \(n_d \leq n_a + n_b + \lceil log_2(\min(k_a, k_b)) \rceil\), and \(k_d = k_a + k_b - 1\).
See Wen-Ding's code here: https://zkrepl.dev/?gist=e168291f275526db7511dc2d049f7219
See Wen-Ding's code here: https://zkrepl.dev/?gist=86d694a9583cc18db77a01a82bcaf884
Consider \(X = 2^{64}\) and
\[S = \sum_{i=0}^9 a_i X^i\]
Where each of the \(a_i\) is up to \(192+\epsilon\) bits (probably fine to say \(\epsilon \leq 6\)).
We wish to find some \(S'\) that is congruent to \(S\) modulo \(p\) (secp256k1 prime) with few registers.
The \(p = 2^{256} - k\) trick is:
\[2^{256} * Z \equiv k * Z \mod p\]
Since the secp256k1 prime has \(p = 2^{256} - 2^{32} - \delta\) for some small \(\delta \approx 2^{10}\), we can write the following congruence:
\[S\]
\[\equiv a_9X^9 + a_8X^8 + a_7X^7 + a_6X^6 + a_5X^5 + a_4X^4 + a_3X^3 + a_2X^2 + a_1X + a_0\]
\[\equiv (2^{64}+2^{33}\delta + \delta^2)a_9X + (2^{64}+2^{33}\delta + \delta^2)a_8 + (2^{32}+\delta)a_7X^3 + (2^{32}+\delta)a_6X^2 + (2^{32}+\delta)a_5X + (2^{32}+\delta)a_4 + a_3X^3 + a_2X^2 + a_1X + a_0\]
Since \((2^{32}+\delta)^2 = 2^{64} + 2^{33}\delta + \delta^2\).
Let \(C_i\) be the coefficient of \(X^i\) after terms are accumulated in this last equation. We have:
\[C_3 = (2^{32}+\delta)a_7 + a_3\]
\[C_2 = (2^{32}+\delta)a_6 + a_2\]
\[C_1 = (2^{64}+2^{33}\delta+\delta^2)a_9 + (2^{32}+\delta)a_5 + a_1\]
\[C_0 = (2^{64}+2^{33}\delta+\delta^2)a_8 + (2^{32}+\delta)a_4 + a_0\]
Let's replace \(2^{64}\) with \(X\) in the expressions for \(C_1\) and \(C_0\) and re-accumulate:
\[C_3' = (2^{32}+\delta)a_7 + a_3\]
\[C_2' = (2^{32}+\delta)a_6 + a_2 + a_9\]
\[C_1' = (2^{33}\delta+\delta^2)a_9 + (2^{32}+\delta)a_5 + a_1 + a_8\]
\[C_0' = (2^{33}\delta+\delta^2)a_8 + (2^{32}+\delta)a_4 + a_0\]
We add an additional 44 bits of overflow at most to the registers (the worst coefficient of an \(a_i\) involved in a sum is \(2^{33}\delta\)). Since our \(a_i\) are at most 200 bits approximately, the \(C_i\) do not overflow the babyjubjub prime (253 bits). So now we have a representation \(S' = C_3'X^3 + C_2'X^2 + C_1'X + C_0'\) of a number that is congruent to \(S\), such that all of the \(C_i'\) are at most 244 bits. After subtracting off some multiple of \(p\) we can check that after carries this is equivalent to \(0\) in \(244 * 4 \approx 1000\) constraints.
For reference, let's see how this plays out for a 7-register number:
\[S\]
\[\equiv a_6X^6 + a_5X^5 + a_4X^4 + a_3X^3 + a_2X^2 + a_1X + a_0\]
\[(2^{32}+\delta)a_6X^2 + (2^{32}+\delta)a_5X + (2^{32}+\delta)a_4 + a_3X^3 + a_2X^2 + a_1X + a_0\]
Here, we get:
\[C_3 = a_3\]
\[C_2 = (2^{32}+\delta)a_6 + a_2\]
\[C_1 = (2^{32}+\delta)a_5 + a_1\]
\[C_0 = (2^{32}+\delta)a_4 + a_0\]
For input points \((x_1, y_1)\) and \((x_2, y_2)\) with sum \((x_3, y_3)\), we verify
To verify each of the first two statements, we do the following:
\[Carry(\sum_i (a_i - b_i) X^i) = Carry(\sum_i r_i X^i *' \sum_i q_i X^i)\]
Note that we'll have to be a little careful on this third substep. We want the quotient \(r\) to be nonnegative, so we probably have to add a fat multiple of \(q\) to LHS to ensure that LHS is positive. i.e. If registers can be overful to 200 bits, then following the prime trick we end up four-register overful numbers which are about \(136\) bits overful. This gives us \(136+256=392\) bit numbers on LHS. So to offset, we probably want to add something like \(2^{137}q\) to LHS, which can be easily done by simply adding the registers of \(q\) left shifted by \(137\) bits to LHS since we're already in overflow representation.
Finally we do a range check.
For input points \((x_1, y_1)\) with double \((x_3, y_3)\), we verify
Note: If \(x_1 = x_2\) and \(y_1 + y_2 = 0\), then \(P + Q = O\) where \(P = (x_1,y_1)\) and \(Q = (x_2, y_2)\).
Aztec CRT trick: https://hackmd.io/@arielg/B13JoihA8
Previous scratchpad: https://hackmd.io/5YUHE_D-TpKRfxvZtJyAqg?both
Onur Kilic's PLONK strategies: https://hackmd.io/ncuKqRXzR-Cw-Au2fGzsMg
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe