Bitxor utiliza estructuras de árbol para almacenar grandes datos asociados a un bloque que no se pueden recuperar directamente desde el encabezado del bloque. Esto permite que los clientes ligeros verifiquen si un elemento (por ejemplo, una transacción, una declaración de recibo) existe sin requerir el historial completo del libro mayor.
Un árbol de Merkle es una estructura de nodos etiquetados con hashes. En la imagen de arriba se muestra la forma más simple de un árbol de Merkle, el árbol de Merkle binario. En particular, Bitxor genera dos Árboles de Merkle por bloque:
Árbol de Merkle de Transacciones: Almacena todas las transacciones incluidas en el bloque.
Árbol de Merkle de Recibos: Almacena todas las declaraciones de recibos vinculadas a un bloque.
Un nodo hoja del árbol contiene el hash SHA3-256 de un elemento adjunto al bloque. Las hojas se ordenan por índice según aparecen en el bloque. Un árbol de Merkle se construye al unir en hash dos hashes, de izquierda a derecha, repitiendo el proceso hasta que se crea un hash singular.
Note
Si hay una capa con un número impar de hashes (y el número es diferente de 1), se duplica el último hash.
El hash en la parte inferior del árbol se llama raíz de Merkle. Las raíces de Merkle de los recibos y las transacciones se incluyen en los encabezados de bloque para resumir los datos vinculados.
El siguiente ejemplo muestra cómo verificar que un bloque está compuesto por todas sus transacciones:
Obtener HRoot; en Bitxor, esto se almacena en el encabezado del bloque.
Calcular HRoot’ creando un Árbol de Merkle con todas las transacciones dentro del bloque en orden natural.
Comparar HRoot y HRoot’.
import { sha3_256 } from 'js-sha3';
import { MerkleTree } from 'merkletreejs/index';
import { QueryParams, RepositoryFactoryHttp, UInt64 } from 'bitxor-sdk';
const example = async (): Promise<boolean> => {
// replace with node url
const nodeUrl = 'NODE_URL';
const repositoryHttp = new RepositoryFactoryHttp(nodeUrl);
const blockHttp = repositoryHttp.createBlockRepository();
// replace with block height
const height = UInt64.fromUint(1);
// 1. Obtain HRoot; in Bitxor, 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();
};
Una prueba de Merkle (también conocida como ruta de Merkle) es el número mínimo de nodos necesarios para calcular nuevamente la raíz de Merkle.
Se siguen los siguientes pasos para validar si un elemento pertenece a un bloque dado:
Calcular H(B); el hash del elemento que deseas validar si existe dentro de un bloque.
Obtener HRoot; en Bitxor, esto se almacena en el encabezado del bloque.
Solicitar la merkleProof: H1, H7, H10.
Calcular HRoot’. Concatenar H(B) con el primer elemento no procesado de la lista merkleProof de la siguiente manera:
Si item.position == left -> proofHash = sha_256(item.hash + proofHash).
Si item.position == right -> proofHash = sha_256(proofHash+ item.hash).
Repetir el paso 4 para cada elemento en la lista MerkleProof.
Comparar si HRoot’ es igual a HRoot.
import { sha3_256 } from 'js-sha3';
import {
BlockRepository,
MerklePosition,
RepositoryFactoryHttp,
UInt64,
} from 'bitxor-sdk';
const validateTransactionInBlock = async (
leaf: string,
height: UInt64,
blockHttp: BlockRepository,
): Promise<boolean> => {
// 2. Obtain HRoot; in Bitxor, 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 = 'NODE_URL';
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),
);
Last updated by John Doe
on 2023‑06‑07.
