math-mode
Math mode
SDR Spec
Merkle Proofs
Implementation:
Additional Notation: $\index_l: [\lfloor N_\nodes / 2^l \rfloor] \equiv [\len(\BinTree\dot\layer_l)]$
The index of a node in a $\BinTree$
layer $l$
. The leftmost node in a tree has $\index_l = 0$
. For each tree layer $l$
(excluding the root layer) a Merkle proof verifier calculates the label of the node at $\index_l$
from a single Merkle proof path element $\BinTreeProof_c\dot\path[l - 1] \thin$
.
BinTreeProofs
The method $\BinTreeProof\dot\createproof$
is used to create a Merkle proof for a challenge node $c$
.
Code Comments:
Line 5: Calculates the node index in layer
$l$
of the node that the verifier calculated using the previous lath element (or the$\BinTreeProof_c\dot\leaf$ if $l = 0$
). Note that$c \gg l \equiv \lfloor c / 2^l \rfloor \thin$
.
OctTreeProofs
The method $\OctTreeProof\dot\createproof$ is used to create a Merkle proof for a challenge node $c$.
Additional Notation: $\index_l: [\lfloor N_\nodes / 8^l \rfloor] \equiv [\len(\OctTree\dot\layer_l)]$
The index of a node in an $\OctTree$
layer $l$
. The leftmost node in a tree has $\index_l = 0$
. For each tree layer $l$
(excluding the root layer) a Merkle proof verifier calculates the label of the node at $\index_l$
from a single Merkle proof path element $\OctTreeProof_c\dot\path[l - 1] \thin$
.
$\textsf{first\_sibling}_l \thin, \textsf{last\_sibling}: [\lfloor N_\nodes / 8^l \rfloor]$
The node indexes in tree layer $l$
of the first and last nodes in this layer's Merkle path element's siblings array $\OctTreeProof_c\dot\path[l]\dot\siblings \thin$
.
Last updated