Merkle Tree の PROOF VERIFICATION の説明ですぐに理解できなかったところがあったので、 メモとして残しておきます。
Page 6 の Merkle Index ( $ \Pi _{[1]} $ ) です。
$$ \omicron = \left( \frac{ \iota }{2^n} \right) \mod{2} $$
より正確に書くと次のようになります。 単なる括弧ではなくガウス記号です。 more precisely:
$$ \omicron = \left[ \frac{ \iota }{2^n} \right] \mod{2} $$
9ページにあるこの式で、 $ \iota $ は 0 から始まる Merkle Tree の何番目のノードかを表すインデックスです。
(iota is the index that represents the node index start with 0.)
$ \omicron $ は $ 0 \lt \frac{\iota}{2^n} \lt 1 $ のときには ゼロ になります。
(omicron is 0 when $ 0 \lt \frac{\iota}{2^n} \lt 1 $ .)
すると、 $n$ , $\iota$ による $ \omicron $ の値は次のようになります。
(The omicron value table corresponding to n and iota is as follows.)
列が $\iota$ を表し、 行が $n$ を表します。
(column means iota value, row means n.)
| $ \omicron $ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
$ \omicron $ が 0 のときは右のハッシュと、 1 のときは左のハッシュと結合します。
(combine hash to the right one when omicron is 0, to the left one when omicron is 1.)
たとえば、 $ \iota = 1 $ のときは、 1, 0 ですから、 左、右 というように結合します。
o
/ \
o o
| | | |
0 1 2 3
つまり、 V. PROOF OF ANCHORAGE の i. Proof formatting for internal use というところで説明されている proof の配列は、 結合するべき HASH を結合する順番に並べたものということです。
