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