*Disclaimer: the code in this package is experimental. It can only be used in research and is not suitable for use in production. The trusted setup must be created in a secure environment. This is a responsibility of the user.*

## General

The repository contains an implementation of the so-called *verkle tree* as a 257-ary trie, a prefix tree. Here’s an article explaining what are verkle trees. In short, these are significantly more efficient replacement for Merkle trees. *Verkle trees* uses *polynomial KZG (aka Kate) commitments* for *vector commitments* instead of usual hash function. The approach offers significant advantages.

The implementation uses *trusted setup* completely in Lagrange basis. Please find here all math and formulas as well as references to the articles it is based upon.

The implementation mostly follows the structure of the Merkle Patricia Tree. Instead of being *hexary*, it commits to 257-long vector in each node: 256 possible values of the byte plus one for an optional commitment to the terminal value in each node. So constant `d = 257`

in the trusted setup, hence the *257-ary trie*.

Keys in the trie are of arbitrary length. They are prefixes of the keys from the state’s key/values storage. So, the structure of the trie follows the hierarchical structure of the state. This allows commit to partitions of the state and results in shorter keys, more predictable and slow-changing structure of the trie. Any key in the trie can point to a terminal value and same time it can be a prefix in other keys. As it is seen from the implementation, the special 257th “character” does not introduce any significant overhead.

## Repository and dependencies

The repository contains:

`kzg`

package with the implementation of the*KZG commitments*and the*trusted setup*.`kzg_setup`

, the CLI program to create a*trusted setup*from a secret and store it into the file.`trie`

package contains implementation of the*trie*as well as corresponding tests and benchmarks.

The implementation of *KZG commitments* uses DEDIS Advanced Crypto Library for Go Kyber v3 and its `bn256`

bilinear pairing suite as cryptographic primitives. The implementation follows formulas presented in this article.

## Implementation

### The state

The state is assumed to be an arbitrary collection of the key/value pairs. Empty key (`nil`

or `""`

) in the implementation is a valid key. The state assumes the empty key always contains serialized binary value of the *trusted setup* upon which the commitments are calculated. So, you can always check if the root commitment contains the commitment to the *trusted setup* itself.

**Determinism of the state**: the state is a **set** of key/value pairs, i.e. no matter the order of how those key/value pairs were added to the storage and trie, the state (and the commitment to it) is the same.

The key/value store is and implementation of `trie.KVStore`

interface.

The state is implemented as `trie.State`

. It contains partitions for key/values pairs of the state and for the trie itself. It also contains the cache for keeping nodes being updated during bulky state update operations to make them atomic.

### The trie

The trie is represented as a collection of key/value pairs in the `trie`

partition of the state. Each key/value pair in the trie represents a *node* of the trie in serialized form.

```
type Node struct {
pathFragment []byte
children [256]kyber.Point
terminalValue kyber.Scalar
}
```

Each node can keep commitments to its up to 256 children and to the terminal value as one vector.

The *ith* child has a commitment to it in `children[i]`

or `nil`

if there’s not commitment to it. Commitment is represented by `kyber.Point`

interface which here is a point on the curve `G1`

.

The commitment to the terminal value, if exists, is not `nil`

and is equal to the `blake2b`

hash of the data itself, adjusted to the underlying field of the curves. It represented by `kyber.Scalar`

interface.

Each *node* represents a *vector* `V = (v0, v1, ...., v256)`

of length 257. Value of `vi`

is 0 if value of the underlying commitment is `nil`

. Otherwise, `v256`

corresponds to the terminal value and other `vi`

are `blake2b`

hashes of commitments adjusted to the field.

Commitment to the node is the commitment to the vector `V`

.

The `pathFragment`

is a slice (can be empty) of bytes taken from the key of the key/value pair in the state.

Let’s say the node `N`

is stored in the trie under the key `K`

. Concatenation `P = K || N.pathFragment`

means the following:

- if
`N`

contains commitment to the terminal value`V`

, the`P`

is the key of that value in the state:`P: V`

. - for any not
`nil`

child with index`0 <= i < 256`

, the`Pi = P || {i} = K || N.pathFragment || {i}`

is the key of the node with the*vector*of commitments of the child. Here`{i}`

is a slice of one byte with value`i`

.

So, whenever we need a proof for the key/value pair `K: V`

in the state, we start from the empty key which corresponds to the root node and then recursively follow the path by concatenating corresponding `pathFragment`

values and picking corresponding byte of the next child in each node. The process is finished when we reach our key and the corresponding node which contains commitment of the terminal value `V`

.

## Example

Let’s say we have the following key/value pairs in the state:

<div class=”snippet-clipboard-content position-relative” data-snippet-clipboard-copy-content=” ” “:

“abra”: “something”

“abrakadabra”: “anything”

“abra+”: “314”

“[email protected]“: “217”

“abra-+” “42”

“>

```
"":
"abra": "something"
"abrakadabra": "anything"
"abra+": "314"
"[email protected]": "217"
"abra-+" "42"
```

On *Intel(R) Core(TM) i7-7600U CPU @ 2.80GHz* laptop.

With 100000 key/value pairs in the state generated uniformly randomly with max key size `70`

:

With 100000 key/value pairs in the state generated with max key size *60* assuming realistic patterns of the state of the IOTA Smart Contract chain: first 4-6 bytes identified partition of the smart contract.

The keys are very short due to the big width of the tree.

GIPHY App Key not set. Please check settings