Symbol は ブロックヘッダ から直接取り出すことの出来ないブロックに関連する大きなデータを保存するために木構造を用いています。これにより軽量クライアントは要素 (例: トランザクション や レシートステートメント) を帳簿全体の履歴を必要とすることなく検証できるようになります。
Diagram of a Binary Merkle Tree¶
マークル木とはハッシュによってラベル付けされたノード構造です。前述の図はマークル木の単純な形状で、マークル二分木です。具体的には Symbol はブロックごとに２つのマークル木を生成します。
ツリーの葉ノードにはブロックにアタッチされた要素の ** SHA3-256** ハッシュが含まれます。葉はブロックに現れるインデックス順に並べられます。マークルツリーは 2 つのハッシュを左から右にハッシュすることで構築され、特異ハッシュが作成されるまでプロセスを繰り返します。
注釈
ハッシュの数が奇数である (そしてその数が 1 ではない) 場合、最後のハッシュは 2 倍になります。
ツリーの下部にあるハッシュはマークルルートと呼ばれます。レシートおよびトランザクションのマークルルートハッシュはブロックヘッダーに含まれ、リンクされているデータを要約しています。
次の例示では、ブロックがすべてのトランザクションで構成されていることを確認する方法を示しています。
import {sha3_256} from 'js-sha3';
import {MerkleTree} from 'merkletreejs/index';
import {QueryParams, RepositoryFactoryHttp, UInt64} from 'symbol-sdk';
const example = async () => {
// replace with node url
const nodeUrl = 'http://api-01.us-east-1.0.10.0.x.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();
};
マークルプルーフ ( マークルパス とも呼ばれる) は、マークルルートを再度計算するために必要な最小ノード数です。
The nodes highlighted belongs to the Merkle proof of B.¶
ある要素が特定のブロックに属しているかどうかを検証するには、次の手順を実行します。
4 を繰り返す。マークル証明リストの各アイテムごとに。
import {sha3_256} from 'js-sha3';
import {BlockRepository, MerklePosition, RepositoryFactoryHttp, UInt64} from 'symbol-sdk';
const validateTransactionInBlock = async (leaf: string, height: UInt64, blockHttp: BlockRepository) => {
// 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.0.10.0.x.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));
次項: コンセンサスアルゴリズム
お探しのものは見つかりましたか？ フィードバックをください。