Help us understand the problem. What is going on with this article?

Stampery Merkle Tree Algorithm PROOFS VERIFICATION の丁寧な説明

More than 1 year has passed since last update.

Stampery BTA v6

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 を結合する順番に並べたものということです。

KenjiOtsuka
Kotlin じゃないとやる気の出ないエンジニアです。 Qiita はメモとして使っています。 WEB+DB で特集書きました。
http://improve-future.com
eys-style
人生を豊かにする仲間と文化・芸術を慈しみながら生きるコミュニティをテクノロジーで実現する。
http://eys-style.com
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away