# Деревья Меркла (Merkle Trees)

By [w3bgrep](https://paragraph.com/@w3bgrep) · 2025-05-07

---

Short

Деревья Меркла (Merkle Trees) — это структура данных, широко используемая в блокчейнах и Web3 для эффективного и безопасного хранения и проверки больших объемов данных. Вот несколько определений на разных уровнях понимания:

* * *

### lvl0. Humster (easy)

Представь, что у тебя есть огромный список транзакций, например, 1000 штук. Ты хочешь убедиться, что все они правильные, но проверять каждую по отдельности долго. Дерево Меркла — это как "супер-умная папка", которая группирует эти транзакции в маленькие кусочки, а потом объединяет их в одно короткое "резюме" (хэш). Если кто-то меняет хоть одну транзакцию, это "резюме" изменится, и ты сразу поймешь, что что-то не так. В Web3 это помогает блокчейнам, вроде Ethereum, быстро проверять миллионы транзакций и экономить место.

* * *

### lvl1. DGen (normal)

Дерево Меркла — это бинарное дерево, где листья хранят хэши отдельных данных (например, транзакций), а каждый уровень выше объединяет хэши парного уровня ниже, пока не получится один корневой хэш (Merkle Root). Этот корневой хэш — компактное доказательство целостности и наличия всех данных в дереве. В Web3 (например, в блокчейнах) деревья Меркла используются для:

*   **Сжатия данных**: вместо хранения всех транзакций в блоке хранится только Merkle Root.
    
*   **Проверки**: можно быстро доказать, что транзакция входит в блок, предоставив только несколько хэшей (Merkle Proof).
    
*   **Масштабируемости**: решения второго уровня (L2), такие как rollups, используют деревья Меркла для компактной передачи данных в основной блокчейн.
    

Пример: в Ethereum Merkle Root включается в заголовок блока, чтобы узлы могли проверять транзакции, не скачивая весь блок.

* * *

### lvl2. Blockchain-dev (advanced)

Дерево Меркла — это бинарное дерево хэшей, где листовые узлы содержат хэши отдельных элементов данных (например, SHA-256 хэши транзакций), а каждый родительский узел — хэш своих дочерних узлов. Формально, если есть ( n ) элементов данных ( D\_1, D\_2, ..., D\_n ), то:

1.  Создаются листовые хэши: ( H\_i = \\text{Hash}(D\_i) ).
    
2.  Парные хэши объединяются: ( H\_{parent} = \\text{Hash}(H\_{left} || H\_{right}) ).
    
3.  Процесс повторяется, пока не получится корневой хэш (Merkle Root).
    

В контексте Web3 деревья Меркла обеспечивают:

*   **Эффективность**: проверка включения элемента требует ( O(\\log n) ) хэшей (Merkle Proof).
    
*   **Безопасность**: изменение любого элемента данных меняет корневой хэш, что делает подделку невозможной без нарушения консенсуса.
    
*   **Применение**:
    
    *   В Bitcoin и Ethereum — для проверки транзакций в блоках.
        
    *   В L2-роллапах (Optimistic Rollups, ZK-Rollups) — для комп vestigial storage и компактного хранения данных.
        
    *   В IPFS и других децентрализованных хранилищах — для верификации целостности данных.
        

* * *

### lvl3. for Solidity-dev (hard)

Деревья Меркла в Solidity часто используются для реализации эффективных механизмов проверки данных, например, в airdrop-контрактах или whitelist-ах для NFT. Основная идея — использовать Merkle Root как часть смарт-контракта, чтобы проверять, входит ли адрес пользователя в заранее определенный список, без необходимости хранить весь список в блокчейне (что дорого).

Пример использования в Solidity:

    // SPDX-License-Identifier: MIT
    pragma solidity ^0.8.0;
    
    contract MerkleAirdrop {
        bytes32 public merkleRoot;
    
        // Хранит, кто уже получил токены
        mapping(address => bool) public claimed;
    
        constructor(bytes32 _merkleRoot) {
            merkleRoot = _merkleRoot;
        }
    
        // Проверяет, может ли пользователь получить токены
        function claim(address account, uint256 amount, bytes32[] calldata merkleProof) external {
            require(!claimed[account], "Already claimed");
    
            // Проверяем Merkle Proof
            bytes32 leaf = keccak256(abi.encodePacked(account, amount));
            require(verifyMerkleProof(merkleProof, merkleRoot, leaf), "Invalid proof");
    
            // Отмечаем, что токены получены
            claimed[account] = true;
    
            // Логика раздачи токенов (например, mint или transfer)
            // token.transfer(account, amount);
        }
    
        // Функция проверки Merkle Proof
        function verifyMerkleProof(
            bytes32[] memory proof,
            bytes32 root,
            bytes32 leaf
        ) internal pure returns (bool) {
            bytes32 computedHash = leaf;
    
            for (uint256 i = 0; i < proof.length; i++) {
                bytes32 proofElement = proof[i];
    
                if (computedHash <= proofElement) {
                    computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
                } else {
                    computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
                }
            }
    
            return computedHash == root;
        }
    }
    

**Как это работает в Web3**:

*   **Airdrop**: Разработчик создает список адресов и сумм (например, в JSON), генерирует Merkle Tree оффчейн (с помощью библиотек, таких как `merkletreejs` в JavaScript), и записывает Merkle Root в контракт.
    
*   Пользователь предоставляет свой адрес, сумму и Merkle Proof (набор хэшей), чтобы доказать, что он в списке.
    
*   Контракт проверяет proof, сравнивая с Merkle Root, и если все верно, выполняет действие (например, переводит токены).
    

**Преимущества**:

*   Экономия газа: вместо хранения всего списка в контракте (дорого) используется только 32-байтовый Merkle Root.
    
*   Масштабируемость: подходит для тысяч или миллионов участников.
    
*   Безопасность: доказательства Меркла криптографически надежны благодаря хэшированию.
    

**Примеры в Web3**:

*   **Uniswap Airdrop**: использовал Merkle Tree для раздачи токенов UNI.
    
*   **NFT Whitelists**: проверка, входит ли адрес в список допущенных для минта.
    
*   **ZK-Rollups**: Merkle Trees используются для компактного представления состояния транзакций.
    

**Инструменты для работы**:

*   JavaScript: `merkletree.js` для создания деревьев и proof.
    
*   Python: `web3.py` или `eth-utils` для интеграции с Ethereum.
    
*   Hardhat/Foundry: для тестирования и деплоя контрактов.
    

* * *

### In Final

Деревья Меркла — основа для масштабируемости и децентрализации. Они позволяют блокчейнам и dApps обрабатывать большие объемы данных с минимальными затратами газа, сохраняя безопасность и возможность проверки. Без них многие современные решения, такие как L2 или децентрализованные airdrop’ы, были бы неосуществимы из-за высоких затрат на газ.

---

*Originally published on [w3bgrep](https://paragraph.com/@w3bgrep/merkle-trees)*