V2 for Tree2

Same as V2 for Tree32 except inode of tree, inode_trees of inode_tree, inode of elt and Segment

Tree Proof

Tree

inode of tree

Name	Size	Contents
tag	1 byte	0b000000yy 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
(optional) inode_tree	variable	0th Inode_tree
(optional) inode_tree	variable	1st Inode_tree

Inode_tree

inode_trees of inode_tree

Name	Size	Contents
tag	1 byte	0b000000yy for 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
(optional) inode_tree	variable	0th Inode_tree
(optional) inode_tree	variable	1st Inode_tree

Stream Proof

Elt

inode of elt

Name	Size	Contents
tag	1 byte	0b0000zwyy 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
(optional) hash	0 or 32 bytes	if w is 0b1, 0th hash (Otherwise, this record does not exist)
(optional) hash	0 or 32 bytes	if z is 0b1, 1st hash (same as above)

Other Components

Segment

Same as in V1 for Tree2

• The segment int is in 1 bits

• 10* is filled at the end of the bytes

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

ex: Encoding of [a; b; c; d; e; ..; z]

|76543210|7654.. ..       |76543210|
|abcdefgh|ijkl.. ..        vwxyz100|

|76543210|7654.. ..  43210|76543210|
|abcdefgh|ijkl.. ..  uvwxy|z1000000|

|76543210|7654.. .. 543210|76543210|
|abcdefgh|ijkl.. .. uvwxyz|10000000|

Name	Size	Contents
length	1 byte	< 256
content	(length) bytes	1 bit integers with termination