メルケル樹の概念

メルケルツリーの概念はNAVERブログで簡単に説明されている.
初めてこの言葉を聞いた人は、リンクをクリックして簡単に読むことをお勧めします.

メルケルツリーコードを使用して実装

1.開発環境

Ubuntu-20.04

2.使用する言語

Javascript

3.モジュールの使用

merkletreejs:カートリッジツリーの作成と検証方法を提供

crypto-js:SHA 256、AESなど多種の暗号化方法

4.完全なソースコード

githup.
githubリンク

5.実施目標

カートリッジツリーの作成方法と検証方法について説明します.

6.実施過程

1）必要なモジュールのインストール

$ npm i merkletreejs crypto-js

2）SHA 256を使用して暗号化を試みる

// Import modules
const SHA256 = require("crypto-js/sha256");

// Check output of SHA256()
console.log("SHA256('a') : ", SHA256("a"));
console.log("SHA256('a').toString() : ", SHA256("a").toString());

crypto-jsのSHA256関数の出力値は、64ビット16進数を示します.toString()関数は、必要な形状のハッシュ値を出力します.
テストする配列を作成し、すべての内部要素をハッシュします.

// Create an array and convert it into hash using SHA256
const testSet = ['a', 'b', 'c', 'd', 'e']
const testArray = testSet.map((v) => SHA256(v).toString());
console.log(testArray)

3)メルケルツリーの作成

上に作成したテスト配列を使用して、インクカートリッジツリーを作成します.

// Import modules
const SHA256 = require("crypto-js/sha256");
const { MerkleTree } = require("merkletreejs");

...

// Create a merkleTree of testArray
const testMerkleTree = new MerkleTree(testArray, SHA256);
console.log("testMerkleTree : ", testMerkleTree);

// Get merkleRoot
const merkleRoot = testMerkleTree.getRoot();
console.log("merkleRoot : ", merkleRoot);

出力された値から見ると、以下の情報が存在する.

leaves:サブノードのない最下位ノード

layers:各レイヤに存在するノードを表し、最後のレイヤ(元は最上位ノード)にMerkle Rootがある.

4）検証

最後に、上に作成したメルケルツリーに属しているかどうかを確認します.

4-1)メルケルツリーに存在する値の検証

...

// Verify valid hash, 'a'
const testValue_valid = "a";
const leaf_valid = SHA256(testValue_valid).toString();
const proof_valid = testMerkleTree.getProof(leaf_valid)
const result_valid = testMerkleTree.verify(proof_valid, leaf_valid, merkleRoot)
console.log('leaf_valid : ', leaf_valid);
console.log('proof_valid : ', proof_valid);
console.log('result_valid : ', result_valid);

proof_valid値を表示すると、どの値とどの順序で比較されるかがわかります.leavesが奇数の場合は、下図のように操作します.

詳細については、Verifiable data structuresを参照してください.

4-2)メルケルツリーに存在しない値の検証

...

// Verify invalid hash, 'u'
const testValue_invalid = "u";
const leaf_invalid = SHA256(testValue_invalid).toString();
const proof_invalid = testMerkleTree.getProof(leaf_invalid);
const result_invalid = testMerkleTree.verify(proof_invalid, leaf_invalid, merkleRoot);
console.log('leaf_invalid : ', leaf_invalid);
console.log('proof_invalid : ', proof_invalid);
console.log('result_invalid : ', result_invalid);

値が存在しないため、proofは空の配列を返し、resultはfalseを返します.

7.終了

自分で作成したアルゴリズムではないが,モジュールを用いてメルケルツリーがどのように検証されたかを理解できる.
このように,ブロックチェーンにおいて,Peerごとにすべてのトランザクションデータがなくても,有効に検証できるとはどういう意味であるか.
これから使い方をもっと勉強しなければなりません.