zktrie

README

Type for zktrie

Data Format in stateDb

All data node being stored via stateDb are encoded by following syntax:

    node             =  magic string | node data ;

    magic string     =  "THIS IS SOME MAGIC BYTES FOR SMT m1rRXgP2xpDI" ;

    node data        =  parent node | leaf node | empty node ;

    empty node       = '0x2' ;

    parent node      = '0x0', left hash, right hash ;

    field            = 32 * hex char ;

    left hash        = field ;

    right hash       = field ;

    leaf node        = node key , value len , compress flag , <value len> * value field, key preimage ;

    node key         = field ;

    compress flag    = 3 * byte ;

    value len        = byte ;

    value field      = field | compressed field, compressed field ;

    compressed field = 16 * hex char ;

    key preimage     = '0x0' | preimage bytes ;

    preimage bytes   = len, <len> * byte ;

    len              = byte ;

A field is an element in prime field of BN256 represented by big endian integer and contained in fixed length (32) bytes;

A compressed field is a field represented by big endian integer which could be contained in 16 bytes;

For the total value len items of value field (maximum 255), the first 24 value fields can be recorded as field or 2x compressed field (i.e. a byte32). The corresponding bit in compress flag is set to 1 if it was recorded as byte32, or 0 for a field.

Key scheme

The key of data node is obtained from one or more poseidon hash calculation: poseidon := (field, field) => field.

For parent node:

key = poseidon(<left hash>, <right hash>)

For leaf node:

key = poseidon(<pre key>, <value hash>)

pre key = poseidon(field(1), <node key>)

value hash = poseidon(<leaf element>, <leaf element>) | poseidon(<value hash>, <value hash>)

leaf element = <value field as field> | poseidon(<compressed field as field>, <compressed field as field>) | field(0)

That is, to calculate the key of a leaf node:

1. In the sequence of value fields, take which is recorded as 'compressed' and calculate the 2x compressed field for its poseidon hash, replace the corresponding value field ad-hoc in the sequence;

2. Consider the sequence from 1 as the leafs of a binary merkle tree (append a 0 field for odd leafs) and calculate its root by poseidon hash;

For empty node:

key = field(0)

Account data

Each account data is saved in one leaf node of account zktrie as 4 value fields:

1. Nonce as field
2. Balance as field
3. CodeHash as compressed field (byte32)
4. Storage root as field

The key for an account data is calculated from the 20-bit account address as following:

32-byte-zero-end-padding-addr := address, 16 * bytes (0)

key = poseidon(<first 16 byte of 32-byte-zero-end-padding-addr as field>, <last 16 byte of 32-byte-zero-end-padding-addr as field>)

Data examples

A leaf node in account trie:

0x017f9d3bbc51d12566ecc6049ca6bf76e32828c22b197405f63a833b566fe7da0a040400000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000029b74e075daad9f17eb39cd893c2dd32f52ecd99084d63964842defd00ebcbe208a2f471d50e56ac5000ab9e82f871e36b5a636b19bd02f70aa666a3bd03142f00

Can be decompose to:

• 0x01: node type prefix for leaf node
• 7f9d3bbc51d12566ecc6049ca6bf76e32828c22b197405f63a833b566fe7da0a: node key as field
• 04: value len (4 value fields)
• 040000: compress flag, a 24 bit array, indicating the third field is compressed
• 0000000000000000000000000000000000000000000000000000000000000001: value field 0 (nonce)
• 0000000000000000000000000000000000000000000000000000000000000000: value field 1 (balance)
• 29b74e075daad9f17eb39cd893c2dd32f52ecd99084d63964842defd00ebcbe2: value field 2 (codeHash, as byte32)
• 08a2f471d50e56ac5000ab9e82f871e36b5a636b19bd02f70aa666a3bd03142f: value field 3 (storage root)
• 00: key preimage is not available

The key calculation for this node is:

arr = [<value field 0>, <value field 1>, <value field 2>, <value field 3>]

hash_pre = poseidon(<first 16 byte for value field 2>, <last 16 byte for value field 2>)

arr[2] = hash_pre

layer1 = [poseidon(arr[0], arr[1]), poseidon(arr[2], arr[3])]

key = poseidon(layer1[0], layer1[1])

Notice all fields and compressed fields are represented as big endian integer.

A parent node in account trie:

0x00000000000000000000000000000000000000000000000000000000000000000004470b58d80eeb26da85b2c2db5c254900656fb459c07729f556ff02534ab32a

Notice the left child of this node is an empty node (so its key is field(0))

Documentation

Index

• Constants
• Variables
• func BigEndianBitsToBigInt(bits []bool) *big.Int
• func CheckBigIntInField(a *big.Int) bool
• func InitHashScheme(f func([]*big.Int, *big.Int) (*big.Int, error))
• func NewBigIntFromHashBytes(b []byte) (*big.Int, error)
• func ReverseByteOrder(b []byte) []byte
• func SetBitBigEndian(bitmap []byte, n uint)
• func TestBit(bitmap []byte, n uint) bool
• func TestBitBigEndian(bitmap []byte, n uint) bool
• func ToSecureKey(key []byte) (*big.Int, error)
• type Byte32
  • func NewByte32FromBytes(b []byte) *Byte32
  • func NewByte32FromBytesPaddingZero(b []byte) *Byte32
  • func ToSecureKeyBytes(key []byte) (*Byte32, error)
  • func (b *Byte32) Bytes() []byte
  • func (b *Byte32) Hash() (*big.Int, error)
• type Hash
  • func HandlingElemsAndByte32(flagArray uint32, elems []Byte32) (*Hash, error)
  • func HashElems(fst, snd *big.Int, elems ...*big.Int) (*Hash, error)
  • func HashElemsWithDomain(domain, fst, snd *big.Int, elems ...*big.Int) (*Hash, error)
  • func NewHashFromBigInt(b *big.Int) *Hash
  • func NewHashFromBytes(b []byte) *Hash
  • func NewHashFromCheckedBytes(b []byte) (*Hash, error)
  • func NewHashFromString(s string) (*Hash, error)
  • func (h *Hash) BigInt() *big.Int
  • func (h *Hash) Bytes() []byte
  • func (h Hash) Hex() string
  • func (h Hash) MarshalText() ([]byte, error)
  • func (h Hash) String() string
  • func (h *Hash) UnmarshalText(b []byte) error

Constants

const (
	HASH_DOMAIN_ELEMS_BASE = 256
	HASH_DOMAIN_BYTE32     = 2 * HASH_DOMAIN_ELEMS_BASE
)

const HashByteLen = 32

HashByteLen is the length of the Hash byte array

Variables

var BigOne = big.NewInt(1)

var BigZero = big.NewInt(0)

var HashZero = Hash{}

var Q *big.Int

Functions

func BigEndianBitsToBigInt

func BigEndianBitsToBigInt(bits []bool) *big.Int

func CheckBigIntInField

func CheckBigIntInField(a *big.Int) bool

CheckBigIntInField checks if given *big.Int fits in a Field Q element

func InitHashScheme

func InitHashScheme(f func([]*big.Int, *big.Int) (*big.Int, error))

func NewBigIntFromHashBytes

func NewBigIntFromHashBytes(b []byte) (*big.Int, error)

NewBigIntFromHashBytes returns a *big.Int from a byte array, swapping the endianness in the process. This is the intended method to get a *big.Int from a byte array that previously has ben generated by the Hash.Bytes() method.

func ReverseByteOrder

func ReverseByteOrder(b []byte) []byte

ReverseByteOrder swaps the order of the bytes in the slice.

func SetBitBigEndian

func SetBitBigEndian(bitmap []byte, n uint)

SetBitBigEndian sets the bit n in the bitmap to 1, in Big Endian.

func TestBit

func TestBit(bitmap []byte, n uint) bool

TestBit tests whether the bit n in bitmap is 1.

func TestBitBigEndian

func TestBitBigEndian(bitmap []byte, n uint) bool

TestBitBigEndian tests whether the bit n in bitmap is 1, in Big Endian.

func ToSecureKey

func ToSecureKey(key []byte) (*big.Int, error)

ToSecureKey turn the byte key into the integer represent of "secured" key

Types

type Byte32

type Byte32 [32]byte

func NewByte32FromBytes

func NewByte32FromBytes(b []byte) *Byte32

same action as common.Hash (truncate bytes longer than 32 bytes FROM beginning, and padding 0 at the beginning for shorter bytes)

func NewByte32FromBytesPaddingZero

func NewByte32FromBytesPaddingZero(b []byte) *Byte32

create bytes32 with zeropadding to shorter bytes, or truncate it

func ToSecureKeyBytes

func ToSecureKeyBytes(key []byte) (*Byte32, error)

ToSecureKeyBytes turn the byte key into a 32-byte "secured" key, which represented a big-endian integer

func (*Byte32) Bytes

func (b *Byte32) Bytes() []byte

func (*Byte32) Hash

func (b *Byte32) Hash() (*big.Int, error)

type Hash

type Hash [HashByteLen]byte

Hash is the generic type to store the hash in the MerkleTree, encoded in little endian

func HandlingElemsAndByte32

func HandlingElemsAndByte32(flagArray uint32, elems []Byte32) (*Hash, error)

HandlingElemsAndByte32 hash an arry mixed with field and byte32 elements, turn each byte32 into field elements first then calculate the hash with HashElems

func HashElems

func HashElems(fst, snd *big.Int, elems ...*big.Int) (*Hash, error)

HashElems call HashElemsWithDomain with a domain of HASH_DOMAIN_ELEMS_BASE(256)*<element counts>

func HashElemsWithDomain

func HashElemsWithDomain(domain, fst, snd *big.Int, elems ...*big.Int) (*Hash, error)

HashElemsWithDomain performs a recursive poseidon hash over the array of ElemBytes, each hash reduce 2 fieds into one, with a specified domain field which would be used in every recursiving call

func NewHashFromBigInt

func NewHashFromBigInt(b *big.Int) *Hash

NewHashFromBigInt returns a *Hash representation of the given *big.Int

func NewHashFromBytes

func NewHashFromBytes(b []byte) *Hash

NewHashFromBytes returns a *Hash from a byte array considered to be a represent of big-endian integer, it swapping the endianness in the process.

func NewHashFromCheckedBytes

func NewHashFromCheckedBytes(b []byte) (*Hash, error)

NewHashFromCheckedBytes is the intended method to get a *Hash from a byte array that previously has ben generated by the Hash.Bytes() method. so it check the size of bytes to be expected length

func NewHashFromString

func NewHashFromString(s string) (*Hash, error)

NewHashFromString returns a *Hash representation of the given decimal string

func (*Hash) BigInt

func (h *Hash) BigInt() *big.Int

BigInt returns the *big.Int representation of the *Hash

func (*Hash) Bytes

func (h *Hash) Bytes() []byte

Bytes returns the byte representation of the *Hash in big-endian encoding. The function converts the byte order from little endian to big endian.

func (Hash) Hex

func (h Hash) Hex() string

Hex returns the hexadecimal representation of the Hash

func (Hash) MarshalText

func (h Hash) MarshalText() ([]byte, error)

MarshalText implements the marshaler for the Hash type

func (Hash) String

func (h Hash) String() string

String returns decimal representation in string format of the Hash

func (*Hash) UnmarshalText

func (h *Hash) UnmarshalText(b []byte) error

UnmarshalText implements the unmarshaler for the Hash type