製品ニュース

マークルツリーとは?

グローバルビットゲッターの皆様へ

マークルツリー はデータ構造の一つで、ハッシュツリーとも呼ばれる。マークルツリーは、木構造の葉のノードにデータを格納し、トップのルートノードまで段階的にデータをハッシュ化することで、葉のノードのデータの変化が上位のノードに伝わり、最終的に木のルートでの変化として表示されるようになっています。

1. マークルツリーの役割

  • ゼロ知識証明
  • データ不変性の確保
  • データ・プライバシーの確保


2. Bitget Limited・ マークルツリーの定義について

2.1 ノード情報

各ツリーノードに保存される情報には、以下のものがあります:
1、ハッシュ値(hash value)  

2、ユーザーの資産スナップショットに含まれるコインの数(例:BTC、ETH、USDT)

hash value,{"BTC":"BTC amount","ETH":"ETH amount","USDT":"USDT amount"}
2070b6a5b12f4ea7,{"BTC":1.763,"ETH":362,"USDT":1077200.2274}


2.2 ハッシュ・ルール

リーフノード(パディングノードは除く)

hash=sha256Function(encryptUid,nonce,balances).substring(0,16)
  • encryptUid:ユーザーの暗号化されたUID
  • nonce:各ユーザーに割り当てられた一意の値
  • balances:ユーザーの資産スナップショット内のコイン数からなるjson文字列(注:末尾の無効な0を取り除き、8ビットの精度を保つこと)
    • 例:{"BTC":1.763,"ETH":362,"USDT":1077200.2274}

親ノード

Parent node's hash = sha256Function(hash1+hash2,{"BTC":(hash1(BTC amount)+hash2(BTC amount)),"ETH":(hash1(ETH amount)+hash2(ETH amount)),"USDT":(hash1(USDT amount)+hash2(USDT amount))},parent node level).substring(0,16)
  • h1:現在のノードの左側の子ノードのハッシュ
  • h2:現在のノードの右側の子ノードのハッシュ
  • レベル(level):親ノード(Parent node)がある場所

ツリー・ノード・レベルの定義:完全なマークルツリー(完全二分木)は、2^n個の葉ノードデータを必要とし、葉ノードレベル=n+1、親ノードレベル=子ノードレベル-1、ルートノードレベル=1、葉ノードレベルは最大値です

パディング・ノードのルール
完全なマークルツリー(完全二分木)には2^n個の葉ノードデータが必要であるが、実際のデータ数は満足せず、奇数個になることもある。そのような場合、「ノードk」に兄弟ノードがなければ、オートパディングにより兄弟「ノードk'」を生成し、hash(k') = hash(k)とし、「ノードk'」のコイン枚数を0枚とします。

例:

Hash
balances
hash1
{"BTC":1,"ETH": 6,"USDT":10}
hash2
{"BTC":2,"ETH":4,"USDT":8}
hash3
{"BTC":2,"ETH":1,"USDT":12}

そして、パディング・ノード・hash4=hash3、格納されたブランスは{"BTC": 0、"ETH": 0, "USDT": 0}となり、図1のハイライトされたノードに示されるようになります。
図1
マークルツリーとは? image 0

Parent node's hash = sha256Function(hash1+hash2,{"BTC":(hash1(BTC amount)+hash2(BTC amount)),"ETH":(hash1(ETH amount)+hash2(ETH amount)),"USDT":(hash1(USDT amount)+hash2(USDT amount))},parent node level).substring(0,16)

したがって、hash6 = SHA256 (hash3 + hash3, {BTC: (2+0), ETH:(1+0), USDT:(12+0)}, level)

検証原則

1. 検証原則:Bitget Limited・ マークルツリーの定義に従って、ユーザー自身のリーフノードからルートノードまでの親ノードのハッシュ値を計算し、「検証ステップ-ステップ1」でルートノードのハッシュ値とマークルツリーのハッシュ値を比較し、両者が等しければ検証は成功、等しくない場合は検証が失敗となります。

2. 例:図1と以下の「jsonテキスト」を組み合わせ、ユーザー自身の葉ノードh3と隣接ノードh4が提供する情報を元に、親ノードh6のハッシュを算出し、さらに隣接ノードh5が提供する情報を元に、親ノードh7のハッシュを算出し、そのハッシュ値とマークルツリーのパスデータで提供されるルートノードh7を比較して、ハッシュ値が等しければ検証完了となります。
マークルツリー・パスデータの「jsonテキスト」:
マークルツリーとは? image 1


検証手順

1. Bitgetアカウントにログインし、「資産概要 - 資産証明」をクリックし、「資産証明」に進むと、最近の監査が直接表示されます。監査時のデータは、デフォルトで展開されて表示されます。

マークルツリーとは? image 2

2. さらに手動でアセットがマークルツリーに含まれていることを確認したい場合は、検証の手順を実行することで可能です。手動検証に必要なデータを取得するために「ダウンロード・データ(Download Data)」ボタンをクリックすると、デフォルト名:merkel_tree_bg.jsonのファイルがダウンロードされます。

マークルツリーとは? image 3


3. 具体的な操作方法:
この例では、ファイル名を 「merkel_tree_bg.json」 とします。マークルツリー・パスデータの「jsonテキスト」は以下の通りです:
マークルツリーとは? image 4

4. Bitget Limitedが提供するオープンソースの検証ツール「ProofOfReserves.zip」をダウンロードします。

5. 「ProofOfReserves.zip」ファイルをカレントディレクトリーに展開して、手順3で保存した「merkel_tree_bg.json」ファイルを同じフォルダに格納する。今回の場合、ダウンロードに保存され、フォルダ名は「proof-of-reserves(プルーフ・オブ・リザーブ)」で、画面は以下のようになります:
マークルツリーとは? image 5

6. ターミナルプログラム(Macシステム:ターミナルアプリケーション、Windowsシステム:cmdアプリケーション)を開きます。
7. ターミナルプログラムでcd ~/Downloads/proof-of-reserves というコマンドを入力し、ダウンロードしたパッケージのディレクトリーを入力します。
8. 次のコマンドを入力して、データを確認します。
Mac/Linux

sh start.sh

Windows
start.bat というファイルをクリックします

注:Macシステムを使用していて、この手順でセキュリティ設定に問題が発生した場合、システム環境設定→セキュリティとプライバシー→一般→ロックボタンをタップして変更→App Storeと承認された開発者からダウンロードしたアプリを許可→ツールに許可を与えます。
以下のように「zsh: permission denied: . /start.sh」と表示されたら、以下のコマンドを実行してください。

chmod a+x ./start.sh

9. 結果を見る

(1) データが正しく、検証に合格した場合は、「Merkle tree root hash consistent, verification succeeded(マークルツリーのルートハッシュが一致、検証成功)」という結果が出ます。

マークルツリーとは? image 6

(2) データが間違っていて検証に失敗した場合、「Merkle tree root hash inconsistency, verification failed(マークルツリーのルートハッシュ不一致、検証失敗)」という結果が出ます。
マークルツリーとは? image 7

10. ビットゲット・リミテッドのオープンソース検証ツールコードとマークルツリー定義(「マークルツリーとは」参照)を参考に、自分でプログラムを書いて、手順2で取得したパスデータを検証したり、今回の監査で生成したマークルツリーに自分の資産が含まれているか確認することも可能です。

Bitget チーム