# 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: - $\text{Serialise}$: This algorithm takes in a group element as input and returns a unique encoding of the group element as a byte string. - $\text{MapToFieldBytes}$ : This algorithm takes in a group element as input and maps the group element to the base field $F_p$. The output is a unique encoding of the field element in $F_p$ as a byte string. > MapToFieldBytes returns a byte string so that the verkle trie library does not need to be concerned with $F_p$, only $F_r$ is exposed through the API. ## MultiPoint Scheme API The multipoint scheme exposes three algorithms: - $\text{Prove:}$ This algorithm takes in as input a list of tuples of the form $(C_i, f_i(X), z_i, y_i)$ and produces a proof $\pi$ that each $f_i(z_i) = y_i$. $C_i$ is the commitment to the function $f_i(X)$ and is produced by using the $\text{Commit}$ algorithm. - $\text{Commit:}$ This algorithm takes as input a function $f(X)$ and produces a commitment to that function $C$. - $\text{Verify:}$ This algorithm takes as input a proof $\pi$, and a list of tuples $C_i, z_i, y_i$. The output is true, if the proof can attest to the fact that, for all $i$, $C_i$ commits to a function $f_i(X)$ using $\text{Commit}$ and $f_i(z_i) = y_i$ ## Summary The API surface that the cryptography layer exposes to the verkle trie layer is very small; five methods. We note that in some cases, $\text{Serialise}$ and $\text{MapToFieldBytes}$ can uses the same function. The reason why we have two exposed algorithms is because $\text{MapToFieldBytes}$ is also expected to be zero knowledge friendly for when we provide a proof of execution for verkle trees, while $\text{Serialise}$ does not need to be.
Last changed by  
 
kevaundray
622

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
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
Vector Commitment Scheme - High Level

Familiarity with binary merkle trees is assumed.

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