Введение в технологию Блокчейн

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

Мы вычисляем хэш этих данных и поднимается вверх до корня дерева, так как мы помним только корень дерева, проверяя соответствие хэш-указателям.

И это занимает около log n элементов.

Поэтому при очень большом числе блоков данных в дереве Merkle мы можем проверить членство данных за относительно короткое время.

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

И мы можем проверить принадлежность к дереву за логарифмическое время.

Также есть вариант Merkle дерева – это сортированное дерево Merkle.

В этом дереве мы берем блоки данных внизу и сортируем их в некотором порядке.

Алфавитном, лексикографическом, числовом порядок или каком-либо другом порядке.

И как только мы отсортировали дерево Merkle, мы можем доказать, что конкретный блок не находится в дереве Merkle.

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

И тогда мы можем доказать, что оба эти элемента находятся в дереве Merkle последовательно.

И поэтому между ними нет места для элемента, который мы ищем.

Цифровые подписи

Далее мы поговорим о цифровых подписях.

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

Итак, цифровая подпись – это как подпись на бумаге только в цифровой форме.

И что это значит, что мы хотим от подписи? Это две вещи.

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

И тогда вторая вещь, которую вы хотите, заключается в том, что подпись привязана к определенному документу.

Чтобы кто-то не мог взять вашу подпись с одного документа и приклеить ее на другой документ, потому что подпись – это не просто подпись.

Это означает ваше согласие или одобрение конкретного документа.

Теперь, как мы можем построить это в цифровой форме с использованием криптографии?

Вот API интерфейс для цифровых подписей.

Здесь есть три операции, которые мы должны делать.

Первое, нам нужно иметь возможность генерировать ключи, и поэтому у нас есть операции generateKeys, которая принимает размер ключа и создает два ключа, sk и pk.

Ключ sk будет секретным ключом подписи, это информация, которую вы держите в секрете и которую вы используете для создания своей подписи.

И ключ pk является общедоступным ключом проверки, который вы даете всем и который любой может использовать для проверки вашей подписи, когда они ее видят.

Вторая операция, это операция подписи.

Операция подписи берет секретный ключ подписи и сообщение, на котором вы хотите поставить свою подпись.

И она возвращает значение, которое является подписью и которое представляет собой лишь несколько бит, представляя вашу подпись.

И затем, третья операция – это проверка, которая берет то, что утверждается как правильная подпись, и подтверждает, что это действительно так или нет.

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

И операция просто возвращает «да», если подпись действительна, или «нет», если она не действительна.

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

Причем, первые два алгоритма могут быть рандомизированными алгоритмами.

Проверка всегда будет детерминированным алгоритмом.

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

И подписи также должны отличаться для разных сообщений.

Подписи должны удовлетворять следующим двум требованиям.

Прежде всего, действительные подписи должны пройти проверку.

Если подпись действительна, т. е. если я подпишу сообщение с моим секретным ключом, и, если кто-то затем позже попытается проверить ее, используя мой открытый ключ и то же самое сообщение, подпись будет корректно проверяться.

Второе требование, это то, что невозможно подделать подписи.

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

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

Поэтому используется хэш сообщения, а не сам текст сообщения.

Таким образом, сообщение может быть действительно большим, но хэш будет только 256 бит.

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

И, кстати, забавный трюк, который мы будем использовать позже, заключается в том, что вы можете подписать хэш-указатель.

И если вы подписываете хэш-указатель, то подпись покрывает или защищает всю структуру, а не только сам указатель хеширования, но и все, на что он указывает.