Изучение деревьев Меркла: основа эффективности в биткойнах

Биткойн — лидер и оригинал децентрализованных цифровых денег. Он использует множество новых технологий, чтобы сделать свою сеть быстрой, безопасной и открытой. Одной из таких технологий является дерево Меркла, базовый способ организации данных, который помогает проверять честность транзакций в блокчейне Биткойн. В этом посте мы рассмотрим, что такое деревья Меркла и как они работают в биткойнах.

Что такое деревья Меркла?

Дерево Меркла — это древовидная структура данных, в которой каждый конечный узел представляет собой хеш-значение, а каждый неконечный узел — это хэш своих дочерних элементов. Такой способ организации данных позволяет легко проверить правильность данных. Добавляя корневой хэш дерева Меркла к цифровой подписи, можно показать, что определенная транзакция принадлежит блоку, не сообщая никакой дополнительной информации.

для вычисления корня Меркла:

• вычислить хэш листовых узлов (txs): H(AB): H(A + B)
• вычислить хэш нелистовых узлов: H(AD) : H(H(AB) + H(C-D))
• наконец, мы вычисляем хэш корневого узла: H(A-H) : H(H(A-D) + H(E-H)

Таким образом, мы видим, что легко проверить, существует ли транзакция в дереве. Например, чтобы проверить наличие транзакции C для другого однорангового узла, все, что вам нужно, это D, H(A-B) и H(C-D), который можно использовать для вычисления корня Меркла. Если корень совпадает с другими одноранговыми узлами, вы можете быть уверены, что транзакция C существует для всех одноранговых узлов.

Деревья Меркла и Биткойн?

Биткойн в значительной степени зависит от деревьев Меркла для достижения эффективности, безопасности и масштабируемости в своей цепочке блоков. Вот некоторые ключевые области, в которых используются деревья Меркла:

• Проверка блоков. Merkle Trees помогает быстро и безопасно проверять блоки биткойнов. Каждый заголовок блока в цепочке блоков имеет корень Меркла, который представляет собой хэш всех транзакций в этом блоке. Сопоставив корень Merkle в заголовке блока с корнем Merkle, рассчитанным на основе данных транзакции, участники сети могут быстро проверить, действителен ли блок.
• Доказательство включения. Деревья Меркла позволяют легко показать, что транзакции находятся в блоке. Когда пользователь хочет проверить, находится ли определенная транзакция в блоке, ему нужно только указать ветвь Merkle, которая связывает транзакцию с корнем Merkle. Это доказательство показывает, что транзакция реальна и находится в блоке, но не показывает всю информацию о блоке. Это свойство полезно для облегченных клиентов и помогает сэкономить пропускную способность сети, необходимую для проверки.
• Эффективная синхронизация блоков. Когда новый узел присоединяется к сети Биткойн, ему необходимо обновить свою цепочку блоков в соответствии с текущей сетью. Деревья Меркла помогают в этом процессе, позволяя узлам сравнивать корни Меркла своей локальной цепочки блоков с корнями других узлов. Совместно используя только разные ветки Merkle, узлы могут быстро обновлять свои блокчейны, экономя пропускную способность и время, необходимое для синхронизации.

Реализация деревьев Меркла

Функция конкатенации

// Import the SHA-256 hash function from the crypto-js library
import sha256 from 'crypto-js/sha256';

// Function to concatenate and hash two leaves using SHA-256
function concat(a, b) {
  const concatenatedString = a + b;
  const hash = sha256(concatenatedString);
  return hash;
}
class MerkleTree {
    constructor(leaves, concat) {
        this.leaves = leaves;
        this.concat = concat; 
    }

    handleHash(nodes){
        let temp = [];
        if (nodes.length > 1){
            let toHash = [];
            for (let i = 0 ; i <= nodes.length ; i++){
                if (i % 2 == 0 && i > 0){
                    temp.push(this.concat(toHash[0],toHash[1]));
                    toHash = [];
                }
                if (i < nodes.length ){
                    toHash.push(nodes[i])
                }
                
            }
            temp = [...temp,...toHash];
            return this.handleHash(temp);
        }else{
            return nodes[0];
        }
    }

    handleProof(nodes,lookup,data){
        let temp = [];
        let newlookup = lookup;
        if (nodes.length > 1){
            let toHash = [];
            for (let i = 0 ; i <= nodes.length ; i++){
                if (i % 2 == 0 && i > 0){
                    let h = this.concat(toHash[0],toHash[1]);
                    if (toHash.includes(lookup) ){
                        if (toHash[0] === lookup){
                            data.push({
                                data : toHash[1],
                                left : false
                            })
                        }else{
                            data.push({
                                data : toHash[0],
                                left : true
                            })
                        }
                        newlookup = h;
                    }
                    
                    temp.push(h);
                    toHash = [];
                }
                if (i < nodes.length ){
                    toHash.push(nodes[i])
                }
                
            }
            temp = [...temp,...toHash];
            return this.handleProof(temp,newlookup,data)
        }else{
            return data;
        }
    }
 
    getProof(index){
        let data = [];
        let proof = this.handleProof(this.leaves,this.leaves[index],data);
        return proof;
    }
    // calculate Merkle Root
    getRoot() {
        return this.handleHash(this.leaves);
        
    }
}

handleHash:

• Этот метод рекурсивно вычисляет корень дерева Меркла, хэшируя узлы.
• Метод перебирает узлы, группируя их в пары (массив toHash) и объединяя их хэши с помощью функции concat.
• Полученные хэши сохраняются в массиве temp.
• Если остались непарные узлы, они добавляются к массиву temp на случай, если у нас нечетное количество листьев.
• Метод рекурсивно вызывает себя с массивом temp в качестве нового набора узлов, пока не останется только один хэш (корень), который затем будет возвращен.

хендлпрооф :

• Этот метод генерирует доказательство Меркла для заданного конечного узла.
• lookup — конечный узел, для которого генерируется доказательство.
• data — это массив, который является результирующим доказательством.
• При обработке узлов проверяется, содержит ли текущая хешируемая пара узлов (массив toHash) листовой узел lookup.
• Если узел lookup найден, он сохраняет родственный узел и его положение (слева или справа) в массиве data, а хэш обеих пар устанавливается в качестве нового поиска.
• Полученные хэши сохраняются в массиве temp, а затем мы повторяем ту же операцию, пока не достигнем корня.
• Метод возвращает массив data, содержащий информацию о проверке.

проверить доказательство:

function verifyProof(proof, node, root, concat) {
    let middleNode = node;
    let h = null;
    for (let elem of proof){
        if (h){
            h = elem.left ? concat(elem.data,h) : concat(h,elem.data);
        }else{
            h = elem.left ? concat(elem.data,node) : concat(node,elem.data);
        }
    }
    return h === root;  
}

• этот метод проверяет, включен ли узел в дерево Меркла
• он использует доказательство, сгенерированное handleProof

Заключение

Деревья Меркла — ключевая часть сети Биткойн, обеспечивающая точность, масштабируемость и эффективность данных. Они используются для проверки блоков, подтверждения включения и синхронизации блоков, что позволяет участникам проверять честность транзакций и обеспечивать безопасность блокчейна Биткойн. По мере роста криптоиндустрии изучение базовых технологий, таких как Merkle Trees, становится все более важным для всех, кто хочет глубже понять удивительный мир криптовалют.