Inside Bitcoin

1# ElligatorSwift for secp256k1 explained
2
3In this document we explain how the `ellswift` module implementation is related to the
4construction in the
5["SwiftEC: Shallue–van de Woestijne Indifferentiable Function To Elliptic Curves"](https://eprint.iacr.org/2022/759)
6paper by Jorge Chávez-Saab, Francisco Rodríguez-Henríquez, and Mehdi Tibouchi.
7
8* [1. Introduction](#1-introduction)
9* [2. The decoding function](#2-the-decoding-function)
10  + [2.1 Decoding for `secp256k1`](#21-decoding-for-secp256k1)
11* [3. The encoding function](#3-the-encoding-function)
12  + [3.1 Switching to *v, w* coordinates](#31-switching-to-v-w-coordinates)
13  + [3.2 Avoiding computing all inverses](#32-avoiding-computing-all-inverses)
14  + [3.3 Finding the inverse](#33-finding-the-inverse)
15  + [3.4 Dealing with special cases](#34-dealing-with-special-cases)
16  + [3.5 Encoding for `secp256k1`](#35-encoding-for-secp256k1)
17* [4. Encoding and decoding full *(x, y)* coordinates](#4-encoding-and-decoding-full-x-y-coordinates)
18  + [4.1 Full *(x, y)* coordinates for `secp256k1`](#41-full-x-y-coordinates-for-secp256k1)
19
20## 1. Introduction
21
22The `ellswift` module effectively introduces a new 64-byte public key format, with the property
23that (uniformly random) public keys can be encoded as 64-byte arrays which are computationally
24indistinguishable from uniform byte arrays. The module provides functions to convert public keys
25from and to this format, as well as convenience functions for key generation and ECDH that operate
26directly on ellswift-encoded keys.
27
28The encoding consists of the concatenation of two (32-byte big endian) encoded field elements $u$
29and $t.$ Together they encode an x-coordinate on the curve $x$, or (see further) a full point $(x, y)$ on
30the curve.
31
32**Decoding** consists of decoding the field elements $u$ and $t$ (values above the field size $p$
33are taken modulo $p$), and then evaluating $F_u(t)$, which for every $u$ and $t$ results in a valid
34x-coordinate on the curve. The functions $F_u$ will be defined in [Section 2](#2-the-decoding-function).
35
36**Encoding** a given $x$ coordinate is conceptually done as follows:
37* Loop:
38  * Pick a uniformly random field element $u.$
39  * Compute the set $L = F_u^{-1}(x)$ of $t$ values for which $F_u(t) = x$, which may have up to *8* elements.
40  * With probability $1 - \dfrac{\\#L}{8}$, restart the loop.
41  * Select a uniformly random $t \in L$ and return $(u, t).$
42
43This is the *ElligatorSwift* algorithm, here given for just x-coordinates. An extension to full
44$(x, y)$ points will be given in [Section 4](#4-encoding-and-decoding-full-x-y-coordinates).
45The algorithm finds a uniformly random $(u, t)$ among (almost all) those
46for which $F_u(t) = x.$ Section 3.2 in the paper proves that the number of such encodings for
47almost all x-coordinates on the curve (all but at most 39) is close to two times the field size
48(specifically, it lies in the range $2q \pm (22\sqrt{q} + O(1))$, where $q$ is the size of the field).
49
50## 2. The decoding function
51
52First some definitions:
53* $\mathbb{F}$ is the finite field of size $q$, of characteristic 5 or more, and $q \equiv 1 \mod 3.$
54  * For `secp256k1`, $q = 2^{256} - 2^{32} - 977$, which satisfies that requirement.
55* Let $E$ be the elliptic curve of points $(x, y) \in \mathbb{F}^2$ for which $y^2 = x^3 + ax + b$, with $a$ and $b$
56  public constants, for which $\Delta_E = -16(4a^3 + 27b^2)$ is a square, and at least one of $(-b \pm \sqrt{-3 \Delta_E} / 36)/2$ is a square.
57  This implies that the order of $E$ is either odd, or a multiple of *4*.
58  If $a=0$, this condition is always fulfilled.
59  * For `secp256k1`, $a=0$ and $b=7.$
60* Let the function $g(x) = x^3 + ax + b$, so the $E$ curve equation is also $y^2 = g(x).$
61* Let the function $h(x) = 3x^3 + 4a.$
62* Define $V$ as the set of solutions $(x_1, x_2, x_3, z)$ to $z^2 = g(x_1)g(x_2)g(x_3).$
63* Define $S_u$ as the set of solutions $(X, Y)$ to $X^2 + h(u)Y^2 = -g(u)$ and $Y \neq 0.$
64* $P_u$ is a function from $\mathbb{F}$ to $S_u$ that will be defined below.
65* $\psi_u$ is a function from $S_u$ to $V$ that will be defined below.
66
67**Note**: In the paper:
68* $F_u$ corresponds to $F_{0,u}$ there.
69* $P_u(t)$ is called $P$ there.
70* All $S_u$ sets together correspond to $S$ there.
71* All $\psi_u$ functions together (operating on elements of $S$) correspond to $\psi$ there.
72
73Note that for $V$, the left hand side of the equation $z^2$ is square, and thus the right
74hand must also be square. As multiplying non-squares results in a square in $\mathbb{F}$,
75out of the three right-hand side factors an even number must be non-squares.
76This implies that exactly *1* or exactly *3* out of
77$\\{g(x_1), g(x_2), g(x_3)\\}$ must be square, and thus that for any $(x_1,x_2,x_3,z) \in V$,
78at least one of $\\{x_1, x_2, x_3\\}$ must be a valid x-coordinate on $E.$ There is one exception
79to this, namely when $z=0$, but even then one of the three values is a valid x-coordinate.
80
81**Define** the decoding function $F_u(t)$ as:
82* Let $(x_1, x_2, x_3, z) = \psi_u(P_u(t)).$
83* Return the first element $x$ of $(x_3, x_2, x_1)$ which is a valid x-coordinate on $E$ (i.e., $g(x)$ is square).
84
85$P_u(t) = (X(u, t), Y(u, t))$, where:
86
87$$
88\begin{array}{lcl}
89X(u, t) & = & \left\\{\begin{array}{ll}
90  \dfrac{g(u) - t^2}{2t} & a = 0 \\
91  \dfrac{g(u) + h(u)(Y_0(u) - X_0(u)t)^2}{X_0(u)(1 + h(u)t^2)} & a \neq 0
92\end{array}\right. \\
93Y(u, t) & = & \left\\{\begin{array}{ll}
94  \dfrac{X(u, t) + t}{u \sqrt{-3}} = \dfrac{g(u) + t^2}{2tu\sqrt{-3}} & a = 0 \\
95  Y_0(u) + t(X(u, t) - X_0(u)) & a \neq 0
96\end{array}\right.
97\end{array}
98$$
99
100$P_u(t)$ is defined:
101* For $a=0$, unless:
102  * $u = 0$ or $t = 0$ (division by zero)
103  * $g(u) = -t^2$ (would give $Y=0$).
104* For $a \neq 0$, unless:
105  * $X_0(u) = 0$ or $h(u)t^2 = -1$ (division by zero)
106  * $Y_0(u) (1 - h(u)t^2) = 2X_0(u)t$ (would give $Y=0$).
107
108The functions $X_0(u)$ and $Y_0(u)$ are defined in Appendix A of the paper, and depend on various properties of $E.$
109
110The function $\psi_u$ is the same for all curves: $\psi_u(X, Y) = (x_1, x_2, x_3, z)$, where:
111
112$$
113\begin{array}{lcl}
114  x_1 & = & \dfrac{X}{2Y} - \dfrac{u}{2} && \\
115  x_2 & = & -\dfrac{X}{2Y} - \dfrac{u}{2} && \\
116  x_3 & = & u + 4Y^2 && \\
117  z   & = & \dfrac{g(x_3)}{2Y}(u^2 + ux_1 + x_1^2 + a) = \dfrac{-g(u)g(x_3)}{8Y^3}
118\end{array}
119$$
120
121### 2.1 Decoding for `secp256k1`
122
123Put together and specialized for $a=0$ curves, decoding $(u, t)$ to an x-coordinate is:
124
125**Define** $F_u(t)$ as:
126* Let $X = \dfrac{u^3 + b - t^2}{2t}.$
127* Let $Y = \dfrac{X + t}{u\sqrt{-3}}.$
128* Return the first $x$ in $(u + 4Y^2, \dfrac{-X}{2Y} - \dfrac{u}{2}, \dfrac{X}{2Y} - \dfrac{u}{2})$ for which $g(x)$ is square.
129
130To make sure that every input decodes to a valid x-coordinate, we remap the inputs in case
131$P_u$ is not defined (when $u=0$, $t=0$, or $g(u) = -t^2$):
132
133**Define** $F_u(t)$ as:
134* Let $u'=u$ if $u \neq 0$; $1$ otherwise (guaranteeing $u' \neq 0$).
135* Let $t'=t$ if $t \neq 0$; $1$ otherwise (guaranteeing $t' \neq 0$).
136* Let $t''=t'$ if $g(u') \neq -t'^2$; $2t'$ otherwise (guaranteeing $t'' \neq 0$ and $g(u') \neq -t''^2$).
137* Let $X = \dfrac{u'^3 + b - t''^2}{2t''}.$
138* Let $Y = \dfrac{X + t''}{u'\sqrt{-3}}.$
139* Return the first $x$ in $(u' + 4Y^2, \dfrac{-X}{2Y} - \dfrac{u'}{2}, \dfrac{X}{2Y} - \dfrac{u'}{2})$ for which $x^3 + b$ is square.
140
141The choices here are not strictly necessary. Just returning a fixed constant in any of the undefined cases would suffice,
142but the approach here is simple enough and gives fairly uniform output even in these cases.
143
144**Note**: in the paper these conditions result in $\infty$ as output, due to the use of projective coordinates there.
145We wish to avoid the need for callers to deal with this special case.
146
147This is implemented in `secp256k1_ellswift_xswiftec_frac_var` (which decodes to an x-coordinate represented as a fraction), and
148in `secp256k1_ellswift_xswiftec_var` (which outputs the actual x-coordinate).
149
150## 3. The encoding function
151
152To implement $F_u^{-1}(x)$, the function to find the set of inverses $t$ for which $F_u(t) = x$, we have to reverse the process:
153* Find all the $(X, Y) \in S_u$ that could have given rise to $x$, through the $x_1$, $x_2$, or $x_3$ formulas in $\psi_u.$
154* Map those $(X, Y)$ solutions to $t$ values using $P_u^{-1}(X, Y).$
155* For each of the found $t$ values, verify that $F_u(t) = x.$
156* Return the remaining $t$ values.
157
158The function $P_u^{-1}$, which finds $t$ given $(X, Y) \in S_u$, is significantly simpler than $P_u:$
159
160$$
161P_u^{-1}(X, Y) = \left\\{\begin{array}{ll}
162Yu\sqrt{-3} - X & a = 0 \\
163\dfrac{Y-Y_0(u)}{X-X_0(u)} & a \neq 0 \land X \neq X_0(u) \\
164\dfrac{-X_0(u)}{h(u)Y_0(u)} & a \neq 0 \land X = X_0(u) \land Y = Y_0(u)
165\end{array}\right.
166$$
167
168The third step above, verifying that $F_u(t) = x$, is necessary because for the $(X, Y)$ values found through the $x_1$ and $x_2$ expressions,
169it is possible that decoding through $\psi_u(X, Y)$ yields a valid $x_3$ on the curve, which would take precedence over the
170$x_1$ or $x_2$ decoding. These $(X, Y)$ solutions must be rejected.
171
172Since we know that exactly one or exactly three out of $\\{x_1, x_2, x_3\\}$ are valid x-coordinates for any $t$,
173the case where either $x_1$ or $x_2$ is valid and in addition also $x_3$ is valid must mean that all three are valid.
174This means that instead of checking whether $x_3$ is on the curve, it is also possible to check whether the other one out of
175$x_1$ and $x_2$ is on the curve. This is significantly simpler, as it turns out.
176
177Observe that $\psi_u$ guarantees that $x_1 + x_2 = -u.$ So given either $x = x_1$ or $x = x_2$, the other one of the two can be computed as
178$-u - x.$ Thus, when encoding $x$ through the $x_1$ or $x_2$ expressions, one can simply check whether $g(-u-x)$ is a square,
179and if so, not include the corresponding $t$ values in the returned set. As this does not need $X$, $Y$, or $t$, this condition can be determined
180before those values are computed.
181
182It is not possible that an encoding found through the $x_1$ expression decodes to a different valid x-coordinate using $x_2$ (which would
183take precedence), for the same reason: if both $x_1$ and $x_2$ decodings were valid, $x_3$ would be valid as well, and thus take
184precedence over both. Because of this, the $g(-u-x)$ being square test for $x_1$ and $x_2$ is the only test necessary to guarantee the found $t$
185values round-trip back to the input $x$ correctly. This is the reason for choosing the $(x_3, x_2, x_1)$ precedence order in the decoder;
186any order which does not place $x_3$ first requires more complicated round-trip checks in the encoder.
187
188### 3.1 Switching to *v, w* coordinates
189
190Before working out the formulas for all this, we switch to different variables for $S_u.$ Let $v = (X/Y - u)/2$, and
191$w = 2Y.$ Or in the other direction, $X = w(u/2 + v)$ and $Y = w/2:$
192* $S_u'$ becomes the set of $(v, w)$ for which $w^2 (u^2 + uv + v^2 + a) = -g(u)$ and $w \neq 0.$
193* For $a=0$ curves, $P_u^{-1}$ can be stated for $(v,w)$ as $P_u^{'-1}(v, w) = w\left(\frac{\sqrt{-3}-1}{2}u - v\right).$
194* $\psi_u$ can be stated for $(v, w)$ as $\psi_u'(v, w) = (x_1, x_2, x_3, z)$, where
195
196$$
197\begin{array}{lcl}
198  x_1 & = & v \\
199  x_2 & = & -u - v \\
200  x_3 & = & u + w^2 \\
201  z   & = & \dfrac{g(x_3)}{w}(u^2 + uv + v^2 + a) = \dfrac{-g(u)g(x_3)}{w^3}
202\end{array}
203$$
204
205We can now write the expressions for finding $(v, w)$ given $x$ explicitly, by solving each of the $\\{x_1, x_2, x_3\\}$
206expressions for $v$ or $w$, and using the $S_u'$ equation to find the other variable:
207* Assuming $x = x_1$, we find $v = x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions).
208* Assuming $x = x_2$, we find $v = -u-x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions).
209* Assuming $x = x_3$, we find $w = \pm\sqrt{x-u}$ and $v = -u/2 \pm \sqrt{-w^2(4g(u) + w^2h(u))}/(2w^2)$ (four solutions).
210
211### 3.2 Avoiding computing all inverses
212
213The *ElligatorSwift* algorithm as stated in Section 1 requires the computation of $L = F_u^{-1}(x)$ (the
214set of all $t$ such that $(u, t)$ decode to $x$) in full. This is unnecessary.
215
216Observe that the procedure of restarting with probability $(1 - \frac{\\#L}{8})$ and otherwise returning a
217uniformly random element from $L$ is actually equivalent to always padding $L$ with $\bot$ values up to length 8,
218picking a uniformly random element from that, restarting whenever $\bot$ is picked:
219
220**Define** *ElligatorSwift(x)* as:
221* Loop:
222  * Pick a uniformly random field element $u.$
223  * Compute the set $L = F_u^{-1}(x).$
224  * Let $T$ be the 8-element vector consisting of the elements of $L$, plus $8 - \\#L$ times $\\{\bot\\}.$
225  * Select a uniformly random $t \in T.$
226  * If $t \neq \bot$, return $(u, t)$; restart loop otherwise.
227
228Now notice that the order of elements in $T$ does not matter, as all we do is pick a uniformly
229random element in it, so we do not need to have all $\bot$ values at the end.
230As we have 8 distinct formulas for finding $(v, w)$ (taking the variants due to $\pm$ into account),
231we can associate every index in $T$ with exactly one of those formulas, making sure that:
232* Formulas that yield no solutions (due to division by zero or non-existing square roots) or invalid solutions are made to return $\bot.$
233* For the $x_1$ and $x_2$ cases, if $g(-u-x)$ is a square, $\bot$ is returned instead (the round-trip check).
234* In case multiple formulas would return the same non- $\bot$ result, all but one of those must be turned into $\bot$ to avoid biasing those.
235
236The last condition above only occurs with negligible probability for cryptographically-sized curves, but is interesting
237to take into account as it allows exhaustive testing in small groups. See [Section 3.4](#34-dealing-with-special-cases)
238for an analysis of all the negligible cases.
239
240If we define $T = (G_{0,u}(x), G_{1,u}(x), \ldots, G_{7,u}(x))$, with each $G_{i,u}$ matching one of the formulas,
241the loop can be simplified to only compute one of the inverses instead of all of them:
242
243**Define** *ElligatorSwift(x)* as:
244* Loop:
245  * Pick a uniformly random field element $u.$
246  * Pick a uniformly random integer $c$ in $[0,8).$
247  * Let $t = G_{c,u}(x).$
248  * If $t \neq \bot$, return $(u, t)$; restart loop otherwise.
249
250This is implemented in `secp256k1_ellswift_xelligatorswift_var`.