or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
ECC Operations Optimization Plan
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.
Addition and Multiplication (no carries)
We represent BigInts with \(k\) registers of \(n\) bits each. For register size \(X = 2^n\), define addition and multiplication without carries by:
Tracking overflows
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\).
Handling Carries
See Wen-Ding's code here: https://zkrepl.dev/?gist=e168291f275526db7511dc2d049f7219
Canonical representation
See Wen-Ding's code here: https://zkrepl.dev/?gist=86d694a9583cc18db77a01a82bcaf884
Prime trick
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\]
AddUnequal
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.
Double
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)\).
Additional Resources
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