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