Cryptography used in Verkle Tries

Disclaimer: The graphics presented in this document may not be pleasing to the eye

Overview

Conceptually we can split verkle tries into two layers, the cryptography layer and the trie logic which depends on the cryptographic layer. The cryptography layer exposes a small set of methods that the trie layer relies on, hiding all of the inherent complexity of the cryptography and allowing both layers to be implemented in parallel.

In this document we focus on the cryptographic layer. We will omit notes on the bottom two layers as they are quite common in cryptography and we do not diverge from the convention in any meaningful way with respects to these two layers. In closing, we note that for the big integer arithmetic layer, one needs a 256 bit integer and the base field needed will be the scalar field of the curve bls12-381.

Elliptic curve arithmetic

• We define a twisted edwards curve \(E\), known as bandersnatch whose basefield \(\mathbb{F}_p\) is equal to the scalar field \(\mathbb{F}_r\) of bls12-381.
• We define a prime group abstraction over bandersnatch known as banderwagon by using the fact that bandersnatch's small subgroup is isomorphic to \(\mathbb{Z}_2 \times \mathbb{Z}_2\). This prime group abstraction also permits an injective map from its group to \(\mathbb{F}_p\).

Single Point Polynomial commitment scheme

• First we note that one is able to use a vector commitment scheme or a polynomial commitment scheme. We use the terminology of polynomial commitment schemes but it is a trivial translation.
• We choose any homomorphic polynomial commitment scheme to work with our multipoint commitment scheme. We have chosen the inner product argument that was first presented in the bulletproofs protocol, however we use the variant from BCMS20. Given that bandersnatch is not pairing friendly, we are able to choose any polynomial commitment scheme which does not use pairings. Kate commitments are therefore not usable.

Multipoint Polynomial commitment scheme

We define a multipoint commitment scheme which is configured to use a homomorphic single point polynomial commitment scheme that is able to create a proving procedure which is more efficient than calling the single point polynomial commitment scheme algorithm repeatedly.

• We also show how to use the first form of the barycentric formula to efficiently divide by a linear polynomial which vanishes on the domain in lagrange basis. Since we are not able to efficiently interpolate many polynomials, this is a crucial component to having an efficient prover in practice.

Table of Contents

API

Exposed API to Verkle Layer

Elliptic curve arithmetic

• Understanding Banderwagon : Introduction
• Understanding Banderwagon: Twisted Edwards Curves
• Understanding Banderwagon : Halving a Point

Commitment scheme

• Vector commitment scheme: Introduction
• Vector commitment scheme : Multipoint argument
• Dividing in Lagrange basis on the domain