# Understanding The Wagon - From Bandersnatch to Banderwagon ## Introduction This document explains the transformation from bandersnatch to banderwagon. The particular technique for doing this was independently found by Gottfried Herold. In short, he found that one can create a prime order subgroup by quotienting out the group of rational points in the bandersnatch group. The main purpose is to give one an intuition of why and how banderwagon works. For a concise handling of the topic, check out Gottfried's [Implementation notes](https://hackmd.io/wliPP_RMT4emsucVuCqfHA?view). ## Acknowledgments Thanks to Gottfried for reading, commenting and correcting both mathematical and grammar mistakes. In particular, Gottfried noted that the use of affine co-ordinates to speak about the points at infinity was imprecise. The section on special points has thus been reduced to only note that these four points exist and not on how to derive them using Bessalov's technique. ## Twisted Edwards Curve We define a Twisted Edwards curve over $F_p$ as: $$ E_{a,d} : ax^2 + y^2 = 1 + dx^2y^2$$ - $x, y, a, d \in F_p^*$ - $d \neq 1$ - $char(p) \neq 2$ **Remark**: When $a=1$ we call this called an Edwards curve. Twisted Edwards curves can therefore be seen as a generalisation of Edwards curves. ## Group Law After choosing the identity point to be $(0,1)$. We define the addition of two points $(x_1,y_1)$, $(x_2, y_2)$ to be: $$ (x_1, y_1) + (x_2, y_2) = (\frac{x_1y_2 + y_1x_2}{1+dx_1y_2y_1y_2},\frac{y_1y_2 - ax_1x_2}{1-dx_1x_2y_1y_2}) = (x_3,y_3)$$ The doubling of a point is : $$2(x_1,y_1) = (\frac{2x_1y_1}{1+dx_1^2y_1^2},\frac{y_1^2-ax_1^2}{1-dx_1^2y_1^2}) = (x_2, y_2)$$ >It is possible to replace the denominator in the doubling formula using the curve equation, note that this _will_ speed up the doubling of a point relative to using the point addition formula. Consequently leading to side-channel attacks during scalar multiplication since a doubling can now be differentiated from a addition. The fact that we can use one formula for both point addition and point doubling is known as *unification*. ## Base Points Twisted Edwards curves have four base points which can be found when $x=0$ and $y=0$. $x=0$: We find the following points: $(0,1)$, $(0,-1)$ $(0,1)$ is the identity element and $(0,-1)$ is a rational point of order two. The order can be verified using the group law or by checking that the points and its negation are equal. - We now refer to $(0,-1)$ as $D_0$ $y=0$: We find the following points: $(\sqrt\frac{1}{a}, 0)$, $(-\sqrt\frac{1}{a}, 0)$ - We refer to $(\sqrt\frac{1}{a}, 0)$ and $(-\sqrt\frac{1}{a}, 0)$ as $F_0$ and $F_1$ respectively These points are rational and have order 4 if $a$ is a square. > **Remark:** All edwards curves have at least 2 rational points of order 4, since $a=1$ is always a square. > **Remark:** All twisted edwards curves have an order 2 point $(0,-1)$ ### Bandersnatch base points For the field that bandersnatch is defined over, $a$ is not a square. This means that $F_0$ and $F_1$ are not points in the group. ## Special points These points are referred to as points at infinity or exceptional points. Generally one wants to avoid these points during elliptic curve cryptography. It is analogous to avoiding $\frac{1}{0}$. Twisted Edwards Elliptic curves have four points at infinity $D_1, D_2, F_2, F_3$. - $D_1, D_2$ have order 2 - $F_2, F_3$ have order 4 ### Bandersnatch special points For the field that bandersnatch is defined over, $d$ is not a square, so $F_2$ and $F_3$ are not rational points. However, since $a$ is also non-square $D_1$ and $D_2$ are in the group. > Bandersnatch has two special points in its group. These two points both have order 2. ### Bandersnatch Subgroup The group structure of bandersnatch is $\mathbb{Z_2} \times \mathbb{Z_2} \times p$, where $p$ is a prime. The non-cyclic subgroup which we may refer to as the 2 torsion subgroup is : $$ E[2] = \{(0,1), D_0, D_1, D_2\}$$ > **Remark:** All of these points have order 2 or 1, so it is sufficient to double any point in the bandersnatch group to clear the cofactor. ie one does not need to multiply by the cofactor; 4. >**Remark:** We may also refer to the 2 torsion subgroup as the small order subgroup. ## Bandersnatch group structure For a point $P$ in the subgroup, we have the following coset: $$ P + E[2] = \{ P + (0,1), P+ D_0, P+D_1, P+D_2\}$$ When $P$ is the neutral element, the coset is $E[2]$, otherwise when $P$ is in the prime order subgroup we can explicitly write the coset as: $$ P + E[2] = \{(x,y), (-x,-y), (\frac{1}{\sqrt{ad}}x^{-1}, \sqrt\frac{a}{d}y^{-1}),(-\frac{1}{\sqrt{ad}}x^{-1}, -\sqrt\frac{a}{d}y^{-1}) $$ Notice that each pair of points differ by $D_0$, we can see this better if we explicitly write: $$ P + E[2] = \{ P , P+ D_0, P+D_1, P+D_1 + D_0\}$$ ## Halving a point Halving a point is the opposite of doubling a point. Given a point $Q$ in the prime order subgroup of size $p$. We can halve it by multiplying $Q$ by $\frac{p+1}{2}$. This will result in a point $P$ in the prime order subgroup such that $2P = Q$. Observe however that there are 3 more points which when doubled will result in $Q$ these points are exactly the points in the coset $P + E[2]$. Moreover, note that since there are no rational points of order 4, the only points which are halvable are the points in the prime order subgroup with 4 solutions; 3 of them have order $2p$ and one has order $p$. If $Q$ is the neutral element then the four solutions are instead $E[2]$ . See [here](https://hackmd.io/2yWlVSf_SA-CKba5ZdQ60g#What-points-are-halvable) for an extended explanation. ## Necessary condition for halving a point is $(\frac{1-aX^2}{p})=1$ [Here](https://hackmd.io/gK13DW-6SYqqPTr7-aFkaw) it is shown that a necessary condition for halving a bandersnatch point is that $1-aX^2$ must be a square. It is not a sufficient condition and the easiest way to see this, is to notice that it is true for both a prime order point $(x,y)$ and also $(-x,-y)$ due to the $X^2$ term. It is also shown that: - $(\frac{1-aX^2}{p})=1$ can be used to recognise $( \pm x,\pm y)$ when $(x,y)$ has prime order - This checks rejects any point of the form $P+D_1$ and $P+D_2$ - The number of points that pass this check is $2p$ > Gottfried (**emphasis**): In particular, points that pass the check are not at infinity. So we can ignore them, greatly simplifying things. ## Quotient group The $1-aX^2$ checks allows us to reduce the effective group size to $2p$. It is still not a prime order group and consequently, it is still vulnerable to small subgroup attacks. The usual trick is to check if the point is in the prime order subgroup, however this is expensive and moreover does not need $1-aX^2$. We want to halve the size of the group from $2p$ to $p$ and we will use quotient groups to achieve this. A quotient group can be seen as a method for making two elements equal. The strategy will be to make $(x,y)$ and $(-x,-y)$ be seen as a single element; they will be in the same equivalence class. **Example** Lets look at the integers modulo 5 for an intuition of how we will do this. 4 and 9 are different integers in $\mathbb{Z}$, but in $\mathbb{Z/5Z}$ they are seen as equivalent. If we were to directly check $4 \stackrel{?}{=} 9$ this would fail, but if we check $4 \text{ mod 5} \stackrel{?}{=} \text{9 mod 5}$ this passes. In a way, we have _merged_ $4$ and $9$ to be identified as the same element. *When we look at them modulo $5$ they are in the same equivalence class.* Following this, the first place to modify will be the equality check between points. ### Equality check To _merge_ $(x_1,y_1)$ and $(-x_1,-y_1)$, we no longer check $x \stackrel{?}{=} -x$ and $y \stackrel{?}{=} -y$. We now check: $\frac{x_1}{y_1} \stackrel{?}{=} \frac{-x_2}{-y_2}$. In general, for two points $(x_1, y_1), (x_2,y_2)$, we check they are equal with the equation $\frac{x_1}{y_1} \stackrel{?}{=} \frac{x_2}{y_2}$. This is equivalent to checking $x_1 \times y_2 \stackrel{?}{=} x_2 \times y_1$ **Zero case** Lets analyse the cases when $x$ or $y$ are zero. $x=0$: When $x=0$ we have two points which are on the curve and pass the $1-aX^2$ check; $(0,1)$ and $(0,-1)$. These two points should be merged and seen as equal since they differ by $D_0$. They are the identity element of the quotient group. > **Note**: To check for the identity element, one only needs to check if $x=0$. $y=0$: There is no point on the bandersnatch curve with $y=0$ due to the fact that $a$ is non-square. > **Note**: If the point is not on the curve or does not pass the $1-aX^2$ check, then the equality check is not sound. There should be no API build a banderwagon point without performing these checks. Furthermore, the internal representation should be seen as a blackbox. This is also the suggestion that the Ristretto/Decaf RFC states. ## Serialisation When serialising a point, remember we want $(x,y)$ and $(-x,-y)$ to serialise to the same bitstring. This can be done by taking the sign of the $y$ co-ordinate, multiplying it by the $x$ co-ordinate and sending the result as a bit string. This works because $$\text{serialise(x,y) = sign(y)} \times \text{x}$$ $$\text{serialise(-x,-y) = sign(-y)} \times \text{-x = sign(y)} \times \text{x} $$ **Deserialisation (Informal)** Upon receiving $\text{sign(y)} \times \text{x}$, one must check that $1-aX^2$ is a square. The $\text{sign(y)}$ does not matter as we are squaring $X$. If this check passes, we then find the corresponding $y$ using the curve equation. > **Note:** The curve equation will return $y$ and $-y$ for some choice of positiveness. We want to choose _positive_ $y$. Choosing $(x,-y)$ will give you an element that is valid, but equivalent to the negation of $(x,y)$. > **Remark:** Negating a point in the quotient group can be done by negating either the $x$ or the $y$ co-ordinate > **Note:** If $p \equiv \text{3 mod 4}$ then the $\text{sign}$ function can be implemented with a quadratic residue check **Deserialisation (Formal)** This is also described [here](https://hackmd.io/wliPP_RMT4emsucVuCqfHA?view#Serialization-format-and-MapToFieldElement) - Receive $t = \text{sign(y)} \times \text{x}$. This will be a bit string. - Interpret the bit string $\text{t}$ as a field element $F_p$ in the interval $[0,p-1]$. The interpreted field element is now denoted $x_k$. $x_k$ will be the $x$ co-ordinate of our deserialised point. - Check whether $1-ax_k^2$ is a square. If it is not, Abort. - Using the curve equation, we can find $y_k^2 = \frac{1-ax_k^2}{1-dx_k^2}$ - Take the square root of $y_k^2$. If it does not exist, Abort. - Pick the value of $y_k$ such that $\text{sign}(y_k) = 1$ ## Group law The group law does not change because what we quotiented by was a subgroup. These are still points on the bandersnatch curve and form a group under point addition. ## Map To Field Since we are only dealing with the points $(x,y)$ and $(-x,-y)$ which are considered equal, we can create the following injective maps from the quotient group to the field $F_p$: - $\frac{x}{y}$ - $x \times y$ Since $y\neq 0$ ,$\frac{x}{y}$ is never undefined. For banderwagon, the choice made was to use $\frac{x}{y}$, because in projective co-ordinates $\frac{x}{y} = \frac{X}{Y}$ while $xy = \frac{XY}{Z^2}$ > **Remark:** This map is not injective if you are mapping from the bandersnatch group to $F_p$ because for one, $(x,y)$ and $(-x,-y)$ are not considered to be equal. ## Banderwagon Abstraction The combination of checking if $1-aX^2$ is a square, and the serialisation strategy over bandersnatch is what is known as banderwagon. ## Conclusion Using banderwagon, one is able to view the group as prime order subgroup with an injective map to the field $F_p$. Moreover, the points at infinity are not in this prime order group abstraction, so the group law is *complete*. ## Appendix ### Theorem 1: $(\frac{1-dX^2}{p}) = (\frac{1-aX^2}{p})$ when $X$ is on the curve *Proof.* The curve equation is given as: $ax^2 + y^2 = 1+dx^2y^2$ $$ \rightarrow 1-ax^2 = y^2 - dx^2y^2$$ $$ \rightarrow 1-ax^2 = y^2(1-dx^2)$$ Hence for a point on the curve, $1-dx^2$ and $1-ax^2$ are either both squares or both non-squares. *Proof done.* This means that we could check if $1-dX^2$ is a square, but this is not done because its more expensive than $1-aX^2$ since $a$ is smaller than $d$ ### Theorem 2: $(\frac{1-ax^2}{p})(\frac{1-y^2}{p}) = (\frac{a-d}{p})$ read: the legendre symbol of the lhs is equal to the legendre symbol of the rhs **Proof** $(1-ax^2)(1-y^2)$ $(1 - y^2) - ax^2 + ax^2y^2 \text{ (expanding the brackets)}$ $(ax^2 - dx^2y^2) - ax^2 + ax^2y^2 \text{ (using the curve equation)}$ $(a-d)(xy)^2 \text{ (cancel and group terms)}$ Since $(xy)^2$ is always a quadratic residue, the legendre symbol of $(a-d)(xy)^2$ is determined by $(a-d)$ #### Corrolary: $(\frac{1-ax^2}{p}) = 1 \text{ implies } (\frac{1-y^2}{p}) = -1$ Given that $$ (\frac{1-ax^2}{p})(\frac{1-y^2}{p}) = (\frac{a-d}{p})$$ Plugging in our condition: $$ (\frac{1-ax^2}{p}) = 1$$ We arrive at: $$ (\frac{1-y^2}{p}) = (\frac{a-d}{p})$$ For bandersnatch, $a-d$ is a quadratic non-residue, hence it is sufficient to check that: $$ (\frac{1-y^2}{p}) = -1$$ It seems that we could check if $1-y^2$ is a non-residue, instead of checking if $1-aX^2$ is a residue. The problem is that the identity element is an edge case, it would return a legendre symbol of $0$. We would need to check that case separately, which trades developer complexity for CPU time. ### What points are halvable? Moved to [here](https://hackmd.io/gK13DW-6SYqqPTr7-aFkaw?both#What-points-are-halvable)
Last changed by  
 
kevaundray
677

Read more

Fully non-deterministic Noir

Afterthought After writing up this spec, I would also like to question/justify the idea as to whether we need this. My concerns are around file access for things like state management and if there are any cases where a user may, due to ignorance allow one to execute arbitrary code in a non-sandboxed way Problem statement Introduction Noir is a domain specific language for writing circuits. Non-deterministic behaviour is useful as they allow you to prove statements in a more efficient way. For example, when doing an inverse, one can either deterministically use a inversion algorithm, or non-deterministically supply the inverse and verify that it is the inverse, since we know that the inverse of a number multiplied by that number equals 1, except 0. The same applies for other operations like square root. Another form of non-determinism is state fetching.

12/16/2022
Verkle Cryptography API

Introduction In this document, we describe the API that the cryptography layer needs to expose to the verkle trie layer. If you are creating a verkle trie implementation without the cryptography fully being implemented, you can mock the following APIs. Elliptic Curve API We define a Elliptic curve $E$ over a base field $F_p$ with a scalar field $F_r$. The group exposed by $E(F_p)$ must have prime order. This is so that the verkle trie logic does not need to worry about subgroup attack vectors. The group exposes two algorithm:

6/20/2022
Dividing In Lagrange basis when one of the points is zero - Generalised

The formulas were derived by reading the following academic article here

6/20/2022
Vector Commitment Scheme - Multipoint/Index

We may use these two terms interchangeably however they are not the same, a vector commitment scheme is strictly more powerful than a polynomial commitment scheme. One can take the dot product between two vectors and if one vector is of the form <1, t, t^2, t^3,..., t^n> then one can realise the dot product as the evaluation of a polynomial in monomial basis at the point t.

6/20/2022
Read more from kevaundray
Published on HackMD