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

V2 for Tree32

Contents