V2 for Tree32

Tree Proof

Name

Size

Contents

tag

1bytes

0b000000zy where y is tag of kinded_hash for before (0b0 for `Value, 0b1 for `Node), z is also tag of kinded_hash for after(same)

version

2 bytes

int16

before

32 bytes

hash

after

32 bytes

hash

state

variable

Tree

Tree

value of tree

Let p be the byte length of length. If length < (1<<8) then p = 1. Else if length < (1<<16) then p = 2. Otherwise p = 4.

Name

Size

Contents

tag

1 byte

0b110000yy where yy is length tag (0b00 for p = 1, 0b01 for p = 2, 0b11 for p = 4)

length

p bytes

byte length of value

value

(length) bytes

bytes

blinded_value of tree

Name

Size

Contents

tag

1 byte

0b11001000

hash

32 bytes

hash

node of tree

Name

Size

Contents

tag + length

1 byte

0b10yyyyyy where yyyyyy is length of list below (<=32)

(step * tree) list

variable

sequence of (Step * Tree)

blinded_node of tree

Name

Size

Contents

tag

1 byte

0b11010000

hash

32 bytes

hash

inode of tree (sparse case)

When proofs have less than 15 trees, sparse case is selected. Otherwise, dense case is selected.

Name

Size

Contents

tag + length

1 byte

0b00yyyyzz where yyyy is length of proofs(<15), zz is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

proofs

variable

sequence of (uint8 * Inode_tree)

inode of tree (dense case)

Name

Size

Contents

tag

1 byte

0b010000zz where zz is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

proofs

variable

sequence of Inode_tree (the number of inode_tree is 32)

extender of tree

Name

Size

Contents

tag

1 byte

0b110110yy where yy is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

segment

variable

Segment

proof

variable

Inode_tree

Inode_tree

blinded_inode of inode_tree

Name

Size

Contents

tag

1 byte

0b11000000

hash

32 bytes

hash

inode_values of inode_tree

Name

Size

Contents

tag+length

1 byte

0b10yyyyyy where yyyyyy is length of list below (<=32)

(step * tree) list

variable

sequence of (Step * Tree)

inode_trees of inode_tree (sparse case)

Name

Size

Contents

tag + length

1 byte

0b00yyyyzz where yyyy is length of proofs(<15), zz is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

proofs

variable

sequence of (uint8 * Inode_tree)

inode_trees of inode_tree (dense case)

Name

Size

Contents

tag

1 byte

0b010000yy where yy is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

proofs

variable

sequence of Inode_tree (the number of inode_tree is 32)

inode_extender of inode_tree

Name

Size

Contents

tag

1 byte

0b110100yy where yy is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

segment

variable

Segment

proof

variable

Inode_tree

none of inode_tree

Used in proofs in inode of tree (dense case) and inode_trees of inode_tree (dense case)

Name

Size

Contents

tag

1 byte

0b11100000

Stream Proof

Name

Size

Contents

tag

1bytes

0b000000zy for y is tag of kinded_hash for before(0b0 for `Value, 0b1 for `Node), z is also tag of kinded_hash for after(same)

version

2 bytes

int16

before

32 bytes

hash

after

32 bytes

hash

length

4 bytes

byte length of state

state

(length) bytes

sequence of Elt

Elt

value of elt

Let p be the byte length of length. If length < (1<<8) then p = 1. Else if length < (1<<16) then p = 2. Otherwise p = 4.

Name

Size

Contents

tag

1 byte

0b110000yy where yy is length tag (0b00 for p = 1, 0b01 for p = 2, 0b11 for p = 4)

length

p bytes

byte length of value

value

(length) bytes

bytes

node of elt

Name

Size

Contents

tag + length

1 byte

0b10yyyyyy where yyyyyy is length of list below (<=32)

(step * kinded_hash) list

variable

sequence of (Step * Kinded_hash)

inode of elt (sparse case)

When proofs have less than 15 hashes, sparse case is selected. Otherwise, dense case is selected. Hashes that proof contains are encoded as Optional_hash (some_case is always selected).

Name

Size

Contents

tag + length

1 byte

0b00yyyyzz where yyyy is length of proofs(<15), zz is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

proofs

variable

sequence of (uint8 * Optional_hash)

inode of elt (dense case)

Name

Size

Contents

tag

1 byte

0b010000zz where zz is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

proofs

variable

sequence of Optional_hash (the number of hashes is 32)

inode_extender of elt

Name

Size

Contents

tag

1 byte

0b111000yy where yy is tag for length (0b00 for p = 1, 0b01 for p = 2, 0b10 for p = 4, 0b11 for p = 8)

length

p bytes

int

segment

variable

Segment

hash

32 bytes

hash

Kinded_hash

Name

Size

Contents

tag

1 byte

0b00000000 for `Value, 0b00000001 for `Node

hash

32 bytes

hash

Other Components

Step

Name

Size

Contents

length

1 byte

< 256

content

(length) bytes

bytes

Segment

Same as in V1 for Tree32.

  • The segment int is in 5 bits

  • 10* is filled at the end of the bytes

  • n segments need (n*5+8)/8 bytes

ex: Encoding of [aaaaa; bbbbb; ccccc; ddddd; eeeee; ..; zzzzz]

|76543210|76543210|7654.. ..       |76543210|
|aaaaabbb|bbcccccd|ddde.. ..        zzzzz100|

|76543210|76543210|7654.. ..  43210|76543210|
|aaaaabbb|bbcccccd|ddde.. ..  yzzzz|z1000000|

|76543210|76543210|7654.. .. 543210|76543210|
|aaaaabbb|bbcccccd|ddde.. .. yzzzzz|10000000|

Name

Size

Contents

length

1 byte

< 256

content

(length) bytes

5bit integers with terminal

Optional_hash

none case

Name

Size

Contents

tag

1 byte

0b00000000

some case

Name

Size

Contents

tag

1 byte

0b00000001

hash

32 bytes

hash