# Understanding Banderwagon: High Level ## Why are we using Banderwagon? Certainly one curve is less complex than two, and Ethereum already uses the bls12-381 curve, so why introduce another curve? Good question, I'm glad you have the mental fortitude to challenge me so early in the article. **TLDR: It allows us to create efficient zero knowledge proofs in a snark.** **Proof of execution** A proof of execution is an protocol that allows you to prove that some function $f$ executed correctly with some input $x$ and produced some output $y$. Upon receiving the proof, one can quickly verify the claim $y=f(x)$ quicker than it takes to execute $f(x)$. If one decides that they want to hide the value of $x$, then one usually calls this a _zero knowledge proof_. **Embedded curves** Although the verification of such proof is usually quick no matter the size of $f$, creating such a proof can be very expensive. The problem becomes worse if $f$ involves elliptic curve arithmetic or bit-string hash functions like sha256. For elliptic curve arithmetic, we can alleviate this problem by choosing curves whose elliptic curve arithmetic is efficient inside of the proof of execution. These are known as _embedded curves_ and bandersnatch is one of those. ## Difference between bandersnatch and banderwagon The astute reader may notice that I used the term bandersnatch in the last sentence, but the title says banderwagon. To explain the difference, lets build an analogy with a simpler example. **`Uint32` vs `NonZeroUint32`** A `uint32` is a data type that is able to store a number between $0$ and $2^{32}-1$, ie $[0, 2^{32})$ Now consider the data type `NonZeroUint32`. It is a `uint32` but it disallows the value zero. The way it does this is not important, it could be that upon creation, the number is checked to not be zero. A `NonZeroUint32` is able to store a number between $1$ and $2^{32}-1$, ie $[1, 2^{32})$. One can say that a `NonZeroUint32` is a safety invariant over a `uint32` as its safe to use it if you need the number to never be zero. **Bandersnatch vs Banderwagon** Similarly, one can view banderwagon as a safety invariant over bandersnatch. There are points in the bandersnatch group that are disallowed in the banderwagon group. The way it does this, is what we will build up to in the following documents. *Why do we want to avoid certain points with banderwagon?* There are two types of points that one generally wants to avoid: - *Special Points*: These are points that would lead one to divide by zero. Sometimes called points at infinity or exceptional points. - *Low order points*: These are points which reduce the security of the group. Using a low order point as your Ethereum public key would allow an attacker to guess your private key in the time it takes to say, *there goes my life savings*. Moreover, replacing an otherwise good public key $P$ with a public key $P+S$ where $S$ lies in a small order subgroup, can allow an attacker to deduce information about your private key. > **Note:** Banderwagon does not _avoid_ points of low order, instead they are _merged_ or quotiented out into points of prime of order. **Credit** The technique used to transform bandersnatch into banderwagon existed in the literature for almost a decade and was adapted to bandersnatch by Gottfried Herold.
Last changed by  
 
kevaundray
577

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

Reference The formulas were derived by reading the following academic article here Problem In the multipoint protocol, we had a polynomial of the form: $$ g(X) = r^0 \frac{f_0(X) - y_0}{X-z_0} + r^1 \frac{f_1(X) - y_1}{X-z_1} + \ldots +r^{m-1} \frac{f_{m-1}(X) - y_{m-1}}{X-z_{m-1}} $$

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

Vector Commitment Scheme vs Polynomial Commitment Scheme 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$. Converting a vector to a polynomial can be done by either interpreting the elements in the vector as the coefficients for the polynomial or interpreting the elements as evaluations of the polynomial. Hence, we can state our schemes in terms of a polynomial commitment scheme and the translation would be done as mentioned above. Similarly, the term multipoint will be used when referring to a polynomial commitment scheme and multi-index when referring to a vector commitment scheme. they mean the same thing, but just in different contexts. Introduction A vector commitment scheme allows you to prove that an element $e$ in a vector $v$ is indeed at some specific index $i$, ie the fact that $v[i]=e$.

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