データバリデーション

Symbol は ブロックヘッダ から直接取り出すことの出来ないブロックに関連する大きなデータを保存するために木構造を用いています。これにより軽量クライアントは要素 (例: トランザクションレシートステートメント) を帳簿全体の履歴を必要とすることなく検証できるようになります。

マークル木

graph TD A --> H1["H1 = H(A)"] B --> H2["H2 = H(B)"] C --> H3["H3 = H(C)"] D --> H4["H4 = H(D)"] E --> H5["H5 = H(E)"] H1 --> H6["H6 = H(H1 +H2)"] H2 --> H6 H3 --> H7["H7 = H(H3 + H4)"] H4 --> H7 H5 --> H8["H8 = H(H5+H5)"] H6 --> H9["H9 = H(H6+H7)"] H7 --> H9 H8 --> H10["H10 = H(H8+H8)"] H9 --> R["HRoot = H(H9+H10)"] H10 --> R

Diagram of a Binary Merkle Tree

マークル木とはハッシュによってラベル付けされたノード構造です。前述の図はマークル木の単純な形状で、マークル二分木です。具体的には Symbol はブロックごとに2つのマークル木を生成します。

  • トランザクションマークル木: ブロックに含まれるすべてのトランザクションを保存します。
  • レシートマークル木: ブロックにリンクしたすべてのレシートステートメントを保存します。

葉ノード

ツリーの葉ノードにはブロックにアタッチされた要素の ** SHA3-256** ハッシュが含まれます。葉はブロックに現れるインデックス順に並べられます。マークルツリーは 2 つのハッシュを左から右にハッシュすることで構築され、特異ハッシュが作成されるまでプロセスを繰り返します。

注釈

ハッシュの数が奇数である (そしてその数が 1 ではない) 場合、最後のハッシュは 2 倍になります。

マークルルート

ツリーの下部にあるハッシュはマークルルートと呼ばれます。レシートおよびトランザクションのマークルルートハッシュはブロックヘッダーに含まれ、リンクされているデータを要約しています。

次の例示では、ブロックがすべてのトランザクションで構成されていることを確認する方法を示しています。

  1. HRoot を取得します。 Symbol では、ブロックヘッダーに格納されます。
  2. HRoot』 を計算して、ブロック内のすべてのトランザクションを自然な順序でマークルツリーを作成します。
  3. HRoot と HRoot』 を比較する。
import { sha3_256 } from 'js-sha3';
import { MerkleTree } from 'merkletreejs/index';
import { QueryParams, RepositoryFactoryHttp, UInt64 } from 'symbol-sdk';

const example = async (): Promise<boolean> => {
  // replace with node url
  const nodeUrl = 'http://api-01.us-east-1.testnet.symboldev.network:3000';
  const repositoryHttp = new RepositoryFactoryHttp(nodeUrl);
  const blockHttp = repositoryHttp.createBlockRepository();
  // replace with block height
  const height = UInt64.fromUint(1);

  // 1. Obtain HRoot; in Symbol, this is stored in the block header.
  const HRoot = (await blockHttp.getBlockByHeight(height).toPromise())
    .blockTransactionsHash;
  // 2. Calculate HRoot' creating a Merkle tree with all the transactions within the block in natural order.
  // Note: This code snippet assumes that the block has less than 100 transactions.
  const queryParams = new QueryParams({ pageSize: 100 });
  const transactions = await blockHttp
    .getBlockTransactions(height, queryParams)
    .toPromise();
  const leaves = transactions
    .sort((n1, n2) => n1.transactionInfo!.index - n2.transactionInfo!.index)
    .map((transaction) => transaction.transactionInfo!.hash);
  const tree = new MerkleTree(leaves, sha3_256, {
    duplicateOdd: true,
    hashLeaves: false,
    sort: false,
    sortLeaves: false,
    sortPairs: false,
    isBitcoinTree: false,
  });
  const HRoot0 = tree.getRoot().toString('hex');
  // 3. Compare HRoot and HRoot'.
  return HRoot.toUpperCase() === HRoot0.toUpperCase();
};

マークル証明

マークルプルーフ ( マークルパス とも呼ばれる) は、マークルルートを再度計算するために必要な最小ノード数です。

graph TD style B stroke:#333,stroke-width:4px style H1 stroke:#333,stroke-width:4px style H7 stroke:#333,stroke-width:4px style H10 stroke:#333,stroke-width:4px A --> H1["H1 = H(A)"] B --> H2["H2 = H(B) (target)"] C --> H3["H3 = H(C)"] D --> H4["H4 = H(D)"] E --> H5["H5 = H(E)"] H1 --> H6["H6 = H(H1 +H2)"] H2 --> H6 H3 --> H7["H7 = H(H3 + H4)"] H4 --> H7 H5 --> H8["H8 = H(H5+H5)"] H6 --> H9["H9 = H(H6+H7)"] H7 --> H9 H8 --> H10["H10 = H(H8+H8)"] H9 --> R["HRoot = H(H9+H10)"] H10 --> R

The nodes highlighted belongs to the Merkle proof of B.

ある要素が特定のブロックに属しているかどうかを検証するには、次の手順を実行します。

  1. H(B) を計算します。ブロック内に存在するかどうかを検証する要素のハッシュ。
  2. HRoot を取得します。 Symbol では、ブロックヘッダーに格納されます。
  3. マークルプルーフを要求: H1, H7, H10.
  4. HRoot』 を計算します。 H(B) を次のように merkleProof リストの最初の未処理のアイテムと連結します:
  1. If item.position == left -> proofHash = sha_256(item.hash + proofHash).
  2. If item.position == right -> proofHash = sha_256(proofHash+ item.hash).

4 を繰り返す。マークル証明リストの各アイテムごとに。

  1. HRoot』 が HRoot と等しいかどうかを比較します。
import { sha3_256 } from 'js-sha3';
import {
  BlockRepository,
  MerklePosition,
  RepositoryFactoryHttp,
  UInt64,
} from 'symbol-sdk';

const validateTransactionInBlock = async (
  leaf: string,
  height: UInt64,
  blockHttp: BlockRepository,
): Promise<boolean> => {
  // 2. Obtain HRoot; in Symbol, this is stored in the block header.
  const HRoot = (await blockHttp.getBlockByHeight(height).toPromise())
    .blockTransactionsHash;
  // 3. Request the merkleProof: H1, H7, H10
  const merkleProof = (
    await blockHttp.getMerkleTransaction(height, leaf).toPromise()
  ).merklePath!;
  // 4. Calculate HRoot'.
  if (merkleProof.length === 0) {
    // There is a single item in the tree, so HRoot' = leaf.
    return leaf.toUpperCase() === HRoot.toUpperCase();
  }
  const HRoot0 = merkleProof.reduce((proofHash, pathItem) => {
    const hasher = sha3_256.create();
    if (pathItem.position === MerklePosition.Left) {
      return hasher.update(Buffer.from(pathItem.hash + proofHash, 'hex')).hex();
    } else {
      return hasher.update(Buffer.from(proofHash + pathItem.hash, 'hex')).hex();
    }
  }, leaf);
  // 5. Compare if the HRoot' equals to HRoot.
  return HRoot.toUpperCase() === HRoot0.toUpperCase();
};

const nodeUrl = 'http://api-01.us-east-1.testnet.symboldev.network:3000';
const repositoryHttp = new RepositoryFactoryHttp(nodeUrl);
const blockHttp = repositoryHttp.createBlockRepository();
// Define block height
const height = UInt64.fromUint(1);
// 1. Calculate H(B); the hash of the element you want to validate if exists within a block.
const leaf = '1F4B55D42C9C91805E73317319DDDA633667D5E44EB0F03678FF7F130555DF4B'.toLowerCase();
validateTransactionInBlock(leaf, height, blockHttp).then((result) =>
  console.log(result),
);

次項: コンセンサスアルゴリズム