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>`__ | +-----------------------+-----------------------+-----------------------+ 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 <#step>`__ \* `Tree <#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-t | | | | ree>`__) | +-----------------------+-----------------------+-----------------------+ 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 <#inode-t | | | | ree>`__ | | | | (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 <#segment>`__| +-----------------------+-----------------------+-----------------------+ | proof | variable | `Inode_tree <#inode-t | | | | ree>`__ | +-----------------------+-----------------------+-----------------------+ .. _v2-tree32-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 <#step>`__ \* `Tree <#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-t | | | | ree>`__) | +-----------------------+-----------------------+-----------------------+ 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 <#inode-t | | | | ree>`__ | | | | (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 <#segment>`__| +-----------------------+-----------------------+-----------------------+ | proof | variable | `Inode_tree <#inode-t | | | | ree>`__ | +-----------------------+-----------------------+-----------------------+ none of inode_tree ^^^^^^^^^^^^^^^^^^ Used in proofs in `inode of tree (dense case) <#inode-of-tree-dense-case>`__ and `inode_trees of inode_tree (dense case) <#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>`__ | +-----------------------+-----------------------+-----------------------+ 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 <#step>`__ \* `Kinded_hash <#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 <#optional-hash>`__ (`some_case <#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 <#opti | | | | onal-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 <#opti | | | | onal-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 <#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 :doc:`v1-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 ==== ======== ==========