Структуры данных для блокчейна. Спикер: Александр Чепурной

О сложном простыми словами - спикер лекции расскажет об аутентифицированных структурах данных для Блокчейн. Для удобства восприятия и детализации информации тема разбита на несколько частей, данная лекция первая из них.

Прежде чем развернуто анализировать структуры данных в Блокчейн, определим такое основополагающее понятие как хеш функция:

Можно выделить следующие виды хеш функций:

• Стандартная хеш функция - быстро считается, но не является безопасной, поскольку в ней легко найти коллизию
• Криптографическая хеш функция - считается медленно, более устойчива к атакам за счет гораздо большей длины выхода

Для защиты от коллизий необходимо использовать криптографическую хеш функцию, так как найти коллизию в данной функции не представляется возможным по нескольким причинам:

• если атакующий ограничен в вычислительных мощностях, то он не сможет за разумное время совершить результативную атаку
• существует ограниченный класс атак, которые атакующий может использовать

Рассмотрим стандартное определение криптографической хеш функции:

На выход подается хеш ключ который определяет случайность выхода. В теории, если реализация известна, то атакующий может вывести коллизию и метафорически «выиграть игру».

Разберем подробнее:

Есть ключ S с длинной L, есть функция его генерации ⇠ - стрелочка влево показывает, что генерация идет случайным образом
Есть хеш функция, которая получает сгенерированный ключ S и на выход дает битовую строку, той же самой длины L
Игра заключается в том, что нам известен S и мы просим атакующего показать x и x’ и он выигрывает, если хеш от х равен х’ при условии x≠x’
Вероятность атакующего выиграть практически равна нулю.

Предполагается, что в таких функциях вход конечного размера, а функции, которые переводят конечный вход конкретной длины в выход конкретной меньшей длины, называются функцией сжатия. Такие функции используются в алгоритмах симметричного шифрования, а блочные функции из алгоритмов симметричного шифрования используются в хеш функциях.

Чтобы вычислить хеш функцию сообщения, которое больше размера блока, мы сначала дополняем нулями, чтобы делилось на целое количество блоков. Также, существует определенная константа в стандарте, мы ее подаем на вход в блок, который считает хеш. Затем подаем первый блок, считаем значение первого хеша, подаем на второй блок и т.д. пока мы не посчитаем всю хеш функцию.
Как видно, данная хеш функция принимает на вход аргумент любого размера, а на выходе получается значение равное размеру хеш функции одного блока.

Теперь проанализируем хеш функцию, которую можно назвать ранним прототипом Блокчейн:

На данном конкретном примере:
Стартап из Эстонии располагал определенной информацие от клиентов, собирая все файлы с данной информацией, в конце недели высчитывался общий хеш от этих данных и публиковался в газете Financial Times.

Структура называется «Цепочка хешей» (Hashchain) и функционирует она следующим образом:

Вычисляется хеш первого документа (h) и идет в хеш функцию (H), далее выход этой хеш функции вместе с хешем следующего документа идет в хеш функцию второго уровня и т.д. На выходе получается хеш, который удостоверяет все документы.

Недостаток такой структуры заключается в том, что если вам необходимо проверить достоверность одного документа, необходимо проверить все документы в цепочке. Решение - дерево Меркла.

Дерево Меркла - изначально идеально сбалансированное дерево, число элементов (листьев) - это степень двойки, соответственно есть четыре блока внизу.

Рассчитаем как получить единственный хеш, который заносится в архив: считаем хеши от всех четырех документов, затем группируем хеши по два и количество таких пар будет четным, так как внизу степень два. Сгруппировав, считаем хеши от получившихся двух блоков. В результате получаем два узла, которые находятся на втором уровне, от них вычисляем хеш и получаем корневой хеш.

Данная структура позволяет эффективно доказать существование одного узла, если известен архивный хеш:

Чтобы доказать существование документа D, например, необходимо предъявить отмеченные желтым узлы, отмеченный красным узел считается из документа проверяющим, его не надо предъявлять. Можно рассчитать эти узлы и сравнить с корневым, если значения совпадают, то проверяемый документ записан в дерево. Как видно, размер доказательства есть логарифм количеству листьев или высота дерева.

Дерево Меркла в Bitcoin

Дерево Меркла в Bitcoin используется для того, чтобы подтвердить существование транзакций в блоке.

Дерево в Bitcoin строится по такому же принципу, кроме одного существенного отличия - число транзакций в блоке не в степени двойки. По данной причине, последняя транзакция в Bitcoin дублируется, пока не добивается до двойки.
Это означает, что реализовано дерево Меркла в Bitcoin неграмотно, в связи с чем, возникают некоторые проблемы:

• Набор транзакций внизу можно менять

Об этом можно почитать в Bitcoin, в файле Merkle.cpp.

• Нет данных о количестве элементов и высоте дерева, что делает дерево менее устойчивым к коллизиям

Дерево Меркла предназначено для статистического набора данный, концепция довольно проста для понимания и использования, но, в любом случае, требует внимательного подхода.

Это была первая часть из серии лекций по теме «Аутентифицированные структуры данных для Блокчейн», в следующих лекциях по данной теме речь пойдет о более сложных структурах.