Quantum-resistant blockchain

In this article I will talk about the security problem in blockchain technology in the light of the growth in performance of quantum computers, analyze some methods of protection against attacks using a quantum computer, and a recent project: Quantum-Resistant Ledger. According to the developers, this will be the first platform in the world, built on the principles of post-quantum encryption and designed to provide protection from the "quantum blow" in the event of the rapid development of these technologies. Platforms built using classical encryption principles can be subjected to such a blow. Without fundamental changes, Bitcoin, Ethereum, Ardor, and most similar platforms may be in the near future.

Part 1. Security issue

Vulnerability

The algorithm for protecting Bitcoin and similar systems is based on the principle of asymmetric encryption with public and private keys. The transaction is signed by the private key, and its truth is verified using the public key.

Using the classic attack algorithms, it is almost impossible to find the private key, knowing the public key. Asymmetric encryption systems such as RSA and the like (DSA, DH, etc.) are based on the statement that the complexity of decomposing a number into prime factors grows exponentially with the size of the key. However, using the Shor algorithm on a quantum computer, it becomes possible to decompose a number into prime factors in polynomial time and, thus, find the private key, knowing the public key.

In 2001, IBM demonstrated this capability by decomposing the number 15 into two simple factors 3 and 5. For these purposes, a quantum computer consisting of 7 qubits was used. Since then, the development of quantum computing technology is happening faster.

In 2016, a group of researchers from the Massachusetts Institute of Technology, together with the Innsbruck Institute, performs the same task of decomposing the number 15, using only 5 qubits .

In July 2017, a programmable 51 qubit computer was created by Russian-American physicists.

At the end of October 2017, an international research team from Singapore and Australian universities concluded that most cryptographic protocols used in the blockchain are vulnerable to attacks from a powerful quantum computer. The report of the group contains 2 predictions for the growth of the power of a quantum computer: optimistic and less optimistic. According to the first, the number of qubits of a quantum computer will double every 10 months. A less optimistic forecast indicates a doubling of the number of quits every 20 months. The figure below shows the graphs of both forecasts.

The algorithm for creating a digital signature based on elliptic curves ( ECDSA ) has been recognized as the most vulnerable to attacks by a quantum computer. Thus, according to the report of the group , Bitcoin in its classic form can be cracked by 2027.

Maybe not so bad? Public key is not stored in clear view

At the end of April 2017, an article is published on bitcoin.com to answer the question of whether Bitcoin holders should be wary of its hacking using a quantum computer. It says that in spite of the fact that asymmetric encryption is used in the Bitcoin blockchain, users do not have to fear for the safety of their coins. The public key is not stored in clear text. So, addresses for transferring coins are not public keys, but only the result of using the SHA-256 hash function. The hash function performs one-way conversion and is therefore resistant to attacks from a quantum computer.

The public key becomes known during the transaction.

The statement that the public key is not available in the clear, is not quite true. Without going into small details, let us look at Bitcoin (BTC) as an example of how cryptocurrency is transferred from one person to another.

Let Alice in her wallet on one of the Bitcoin addresses has 100 mBTC (1000 mBTC = 1 BTC). She wants to translate 1 mBTC to Bob. To do this, she indicates Bob’s Bitcoin address, transfer commission and Bitcoin address in her wallet to receive the change. Let Alice specify 1 mBTC as a commission. Thus, out of 100 mBTC Alice has, 1 mBTC is sent to Bob, 1 mBTC goes as a Bitcoin network commission and 98 mBTC is returned to Alice’s wallet.

Now let's look at what happens at the level of the Bitcoin network. Alice and Bob have purses containing addresses for storing coins. One wallet may contain several Bitcoin addresses. Addresses are generated when creating wallets. Each address corresponds to a pair of keys created by the ECDSA algorithm: public and private. During the transfer of coins, a transaction is created in which information on the number of coins transferred by Alice, Bob’s Bitcoin address, a signature made with Alice’s private key, Alice’s public key, and some other data is transmitted. Further, the transaction in an open (unencrypted) form is sent to the network . Network nodes, before accepting a transaction for processing, verify its signature using the public key. If the signature is valid, they add the transaction information to the block. Such an act of inclusion is called confirmation.

The average time of generating a block in the Bitcoin network is 10 minutes. The network aims to keep this time constant. Before using the funds received, it is recommended to wait for 6 confirmations. Thus, Bob, while observing the safety rules, will be able to use the funds received about an hour after their transfer.

One of the features of the transfer of coins in the Bitcoin network is that it is not possible to transfer only part of the coins from a single address. Coins are always transferred to the entire volume located on the Bitcoin address of the wallet, while the sender returns the change. It can be obtained both on the address from which the coins were sent, and on any other. Therefore, Alice must provide an address for delivery. In a number of software operating the wallet, the delivery address is the shipping address.

Strictly speaking, a transaction fee is not mandatory, but its absence may postpone the transaction for a long time. The converse is also true: you can speed up the transaction a little by increasing the amount of commission. At the time of this writing (January 2018), most software wallets offer to specify a commission of 1 mBTC. There are a number of resources, for example, this one , which make it possible to estimate the time when a transaction is included in a block, depending on the amount of commission.

Use public key 1 time

From a security point of view, it is best to receive a change to a new address, the public key of which will be unknown to the network. In this case, the key pair is used only once. However, according to statistics, as of December 2017, about 41.34% of addresses are reused.

10 minutes to attack

However, sooner or later you will need to use the tools on the new address. The public key is transmitted to the network in the clear. Until a confirmation is received, the funds are still at the sender. If an attacker gets a public key during a transaction, he will have about 10 minutes to get the private key using a quantum computer and try to conduct his transaction from the same address, setting a higher commission.

Static addresses are more vulnerable

In systems such as Ethereum, NXT, Ardor, and others, the public key also becomes known after the first transaction. The situation is aggravated by the fact that tokens or smart contracts are tied to static addresses that can be attacked for a long time. If the attack is successful, the attacker will be able to destroy the entire economic system based on these addresses.

Part 2. Solutions

How to ensure resistance to attacks of a quantum computer?

Currently, there are several basic methods that provide protection against attacks from a quantum computer:

hash based cryptography;
code-based cryptography;
matrix based cryptography;
cryptography based on multidimensional quadratic systems;
cryptography based on the secret key.

With sufficiently long keys and security requirements, these protection methods are able to withstand both classic attacks and attacks using a quantum computer.

The most studied is the use of digital signatures based on hash functions.

As mentioned earlier, the hash function performs one-way message conversion. The message is converted to a fixed-length hash value. Using the hash function on the one hand should make it senseless to search for messages to get the same hash value. On the other hand, the algorithm must be resistant to collisions: when 2 different messages correspond to the same hash value.

Grover’s quantum algorithm can be used to try to find a collision or perform a preliminary attack to find the original message. This will require

$O (2 ^ {\ frac {n} {2}})$ operations. Thus, to maintain 128-bit security, the required hash length is at least 256 bits. SHA-256 can be selected as such a function.

Signature Lamport

One of the uses of the hash function in a digital signature is the Lamport signature. It can be built on the basis of any one-way hash function. The cryptostability of the algorithm is based on the cryptostability of the hash functions used.

Signature scheme

For the message

$M$ long

$m$ keys are generated. First, private keys are generated in pairs.

$SK$ long

$n$ then, using the hash function, public key pairs are formed from the private keys

$PK$ . The number of pairs of private and public keys is equal to the number of bits in the original message.

When performing the signature, the message is read bit by bit, and, depending on the value of the current bit, one of the private keys of the corresponding pair is selected. Selected private keys are combined into a signature. Next, the resulting signature and

$m$ public key pairs are sent to the addressee.

Signature verification is similar to the process of creating it. The signature is broken into fragments by length.

$n$ which are then converted using the same hash function. The message is read bit by bit and the value of the bit is chosen as the public key, which is compared with the received hash value.

As a rule, before applying the signature, the original message is hashed to reduce its size. Let SHA-256 be selected as the hash function, then

$m = n = 256$ . At the same time, the total length of the open (as well as the closed) key

$L_ {PK}$ it turns out to be:

$L_ {PK} = n * 2 * m = 256 * 2 * 256 = 128 KB = 16 KB.$

Signature length

$L_S$ is:

$L_S = n * m = 64 KB = 8 KB.$

The signature of Lamport is a one-time (it remains safe only when it is used once), since during its execution and transfer, half of the private key becomes known. Let the message length be 256 bytes and the hash length be 256. Before Alice publishes the message signature, no one knows 2 * 256 random numbers in the secret key. Thus, no one can create the correct set of 256 numbers for the signature.

After Alice publishes the signature, no one will yet know the remaining 256 numbers, and thus cannot create a signature for messages that have a different hash.

The fact that Lamport's signature is one-time, combined with an impressive total signature and public key (24 KB with a message length of 256 bytes and a hash length of 256 bytes), makes its use in a public transaction block impractical.

Signature Vinernytsia

There are other one-time digital signature algorithms. In the Winternitz signature, unlike the Lamport signature, the original message is signed, not bitwise, but blockwise. The one-time Winternitz signature, like that of Lamport, can be built on the basis of any strong cryptographic function.

Signature scheme

Message

$M$ long

$m$ broken into fragments

$M_i$ long

$w$ . A private key is generated for each fragment.

$SK$ lengths

$n$ . A hash operation is sequentially applied to each private key.

$2 ^ w-1$ times (rounds

$R$ ). As a result of the operations performed, the corresponding public keys are obtained.

$PK$ same length

$n$ .

When signing, as in the generation of public keys, an iterative calculation of the hash over the private keys is performed. The number of repetitions in each case depends on the message being signed. As mentioned earlier, the message is divided into blocks of length.

$w$ . The numerical value of this block

$M_i$ and is the number of iterations that must be performed on the private keys to obtain the signature. The connection of the received blocks will be the signature of this message.

When checking the signature on fragments of its length

$n$ an iterative hash calculation is performed. Number of rounds

$R_i$ applying a hash function is defined as the difference between the number of iterations to obtain the public key and the numerical value of the message block, i.e.

$R_i = 2 ^ w-1 - M_i$ time. Then the obtained values are compared with the corresponding public key.

Example

I will illustrate the above with a small example. Let the message be given

$M$ (in bit representation) lengths

$m$ , the parameter Vinternitsa

$w$ and some length hash function

$n$ :

$M = 11000111 \: 01100111, m = 16, \: w = 8, \: n = 256.$

We generate

$m / w = 2$ private keys based on a pseudo-random number generator. We apply to each private key

$2 ^ w-1 = $ 25$ times the hash function, thereby obtaining

$2$ public keys that are combined into one common key length

$2 * n = 512$ bit. Next for each message block

$M$ lengths

$w$ determine the number of hashing operations applied to the private key

$R_i$ . In this case, these will be the values.

$11000111_2 = 199_ {10}$ and

$01100111_2 = 103_ {10}$ respectively. By performing a hash operation on private keys, we get a signature length

$2 * n = 512$ bit.

To verify the signature divide it into parts of length

$n$ . Over each part we produce

$R_i = 2 ^ w-1 - M_i$ hash operations Those.

$255 - 199 = $ 5$ and

$255 - 103 = $ 15$ times accordingly. If, as a result of the operations performed, the value obtained coincides with the public key, then the message is valid.

When using SHA-256 as a hash function for the signature Winterternits,

$m = n = 256$ .

Let be

$w = 8$ bit. Then the full size of the public key

$L_ {PK}$ and signatures

$L_S$ are equal:

$L_ {PK} = L_S = m / w * n = 256/8 * 256 = 8 KB = 1 KB.$

The number of hash calculations in this case is:

$P = (2 ^ w-1) * m / w = (2 ^ 8-1) * 256/8 = 8160.$

For the case of

$w = 16$ this value increases to

$P = $ 104856$ .

The sizes of the public key and the signature, with the same parameters as in the example for the signature of Lamport, are equal to 1 KB. In total, this is less than in the signature of Lamport (24 KB). However, the number of hash calculations is 8160. This is undoubtedly a lot. In addition, when verifying the signature, an average of half of this number of iterations is performed. This makes this option signature inappropriate for use in the blockchain.

There are several variants of the Winterternitz signature, including with the extension of the signature in order to increase reliability and reduce the number of applications of the hash function. Their description is beyond the scope of this article. Those who are interested can see more here . The use of the Winternitz signature based on the national hash function GOST 34.11-12 can be viewed here .

Merkle Tree (MSS)

One-time signatures can provide satisfactory cryptographic security; however, it is their disposability that can be a serious problem. Let it be necessary to transfer savings from one address to another. It turns out that when using one-time signatures, it will be necessary to transfer the entire amount of funds each time, and a new address will be needed for each transaction. With each transaction you will need to publish a new public key. In addition, the preservation in the blockchain of new transactions will gradually require more time to search for them.

To solve the problem, the signature scheme is extended by holding several signatures based on several key pairs for each address. The use of several signatures is performed on the basis of a binary hash tree - the Merkle tree.

Read more

The calculation of the tree is made from leaves to the root. Each leaf node of the tree is computed as a hash of the generated public key. The remaining nodes are calculated by obtaining a hash from the concatenation (gluing) of the child nodes. Thus, the whole tree is calculated to the root. Let there be 4 pairs of keys, the Merkle tree is calculated by calculating 7 hashes (see the figure above).

A feature of the Merkle tree is that the existence of any node or leaf can be cryptographically proven by calculating the root.

The message signature is created using the private key from the selected key pair.

Signature verification involves calculating the root based on the passed parameters and comparing with it as with a reusable public key. These parameters are:

signature;
root;
one-time key, the closed part of which the message was signed;
hashes from the tree, lying on the way from the selected sheet to the root.

When using one-time Merkle or Winternitz signatures, there is no need to transfer a separately selected one-time public key, since it can be obtained from the message signature. It is enough to transfer its number reflecting its position in a tree. For example, in the figure above, the transmitted parameters will be: signature, root, sheet number - 0 (the sheet number with the key

$PK1$ ) and hashes

$H2$ and

$H6$ . When performing a signature verification, the public key will be obtained from it.

$PK1$ respectively hash

$H1$ . Hashes

$H1$ and

$H2$ will calculate

$H5$ . And hashes

$H5$ and

$H6$ will calculate the root

$R$ which can be compared with the value of the transferred root.

The Merkle tree, compiled and calculated from public keys, allows instead of publishing the entire set of them to publish only the root of the tree. This increases the size of the signature by including a part of the tree in the signature, but makes it possible using only 1 hash to verify many signatures. So, at the depth of the tree

$N$ can sign

$2 ^ n$ posts.

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

Гипердеревья

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

Read more

Гипердерево представляет собой структуру, состоящую из деревьев Меркла. В этой структуре по назначению выделяются 2 типа деревьев: дерево сертификации и дерево подписи. Дереву подписи соответствуют ключи, используемые для подписывания сообщений. Дереву сертификации соответствуют ключи для подписывания корней деревьев подписи. Таким образом, деревья подписи являются дочерними к дереву сертификации (см. рисунок ниже).

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

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

Расширенная структура дерева Меркла (XMSS)

Полное описание схемы выходит далеко за рамки данной статьи, подробнее можно прочесть здесь . Коснусь лишь базовых представлений и характеристик. Схема XMSS как и дерево Меркла позволяет расширять одноразовые подписи. Использование битовой маски с применением исключающего ИЛИ (XOR) дочерних узлов до конкатенации хешей в родительский узел позволяет повысить устойчивость к коллизиям применяемых хеш-функций. Так, при использовании SHA-256 в качестве хеш-функции в сочетании с расширенной схемой Винтерница с параметром безопасности (W-OTS+) позволяет увеличить безопасность с 128 до 196 бит. Согласно Ленстра , 196-битной защиты достаточно, чтобы считать ее безопасной против атаки путем простого перебора до 2169 года. При всех достоинствах схемы XMSS ее основным недостатком является длительное время генерации ключа.

В настоящее время существуют и другие схемы расширения дерева Меркла ( GMSS , CMSS ), которые в сочетании с алгоритмами одноразовой подписи также могут быть использованы в блокчейне, устойчивом к атакам с применением квантового компьютера.

Часть 3. Реализация идей

Проект квантово-устойчивого блокчена — QRL

Во второй половине 2016 года доктором наук П. Ватерлендом создается группа по разработке блокчейна устойчивого как классическим атакам, так и к атакам с применением квантового компьютера. По результатам разработки теоретической части в конце того же года в открытый доступ выложен главный документ разрабатываемого блокчейна — «белая книга» (white paper). В настоящий момент документ доступен на нескольких языках, включая русский.

Основные характеристики QRL

1. Схема подписи и безопасность
Применяется схема подписи на основе алгоритма расширенной подписи Винтерница (W-OTS+, w = 16, SHA-256) на базе связных структур XMSS. Такой подход позволяет генерировать адреса с возможностью подписи, избегая длительной вычислительной задержки, наблюдаемой при создании гигантских конструкций XMSS. Обеспечивает 196-битную защиту с прогнозируемой безопасностью против атаки путем простого перебора до 2169 года.

2. Алгоритм консенсуса — доказательство работы (proof-of-work)
В первой итерации основной сети анонсирован алгоритм консенсуса proof-of-work.

3. Плавающая комиссия
Боʼльшие размеры транзакций по сравнению с другими блоками цепочки транзакций требуют оплаты для каждой транзакции. По мнению Ватерленда, рынки с искусственной комиссией (например, Биткойн) не нужны и противоречат идеалу открытого блокчейна. Каждая транзакция, если она сопровождается минимальной оплатой, должна быть такой же действительной, как и любая другая. Размер минимальной оплаты, приемлемой для майнеров, должен быть плавающим и устанавливаться рынком. Those. узлы (майнеры) должны конкурентно устанавливать нижнюю границу оплаты между собой. Абсолютное минимальное значение будет соблюдаться на уровне протокола. Таким образом, майнеры будут заказывать транзакции из мемпула для включения в блок по своему усмотрению.

4. Динамическое вычисление вознаграждения за блок
Каждый новый созданный блок будет включать в себя первую транзакцию «coinbase», содержащую адрес майнинга, для которого вознаграждение будет определено как сумма вознаграждения за монетную ставку с общей суммой комиссий за транзакции внутри блока.

5. Время нахождения блоков — 1 минута
Время между блоками в сети Биткойн составляет примерно 10 минут. При требуемых 6-ти подтверждениях это дополнительно увеличивает время ожидания завершения транзакции. Более новые схемы блока цепочки транзакций, такие как Ethereum, улучшены в этом аспекте и выигрывают за счет более короткого времени нахождения блока без потери в безопасности или централизации майнеров из-за высокой скорости появления осиротевших/устаревших блоков.

Для QRL это время нахождение блока составляет 1 минуту.

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

$x$ средней величины

$y$ последних

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

$x$ and

$z$ будут тогда жесткими консенсусными правилами для сети, которым придется подчиняться. Таким образом, максимальный размер блока

$b$ можно просто вычислить как:

$b = xy$ .

7. Денежная единица — квант
Базовой единицей валюты является квант. Каждый квант делится на наименьшие элементы. Ниже представлены названия всех элементов в порядке возрастания:

Element	Value
Шор	$1$
Накамото	$10^3$
Бутерин	$10^6$
Меркл	$10^{10}$
Лэмпорт	$10^{13}$
Квант	$10^{16}$

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

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

Адрес создается посредством выполнения SHA-256 по корню Меркла самого высокого дерева сертификации XMSS. К этому добавляется четырехбайтная контрольная сумма, образованная из первых четырех байтов двойного хеша SHA-256 корня Меркла, и буквы «Q».

Например, в псевдокоде Python это будет описано следующим образом:

Q + sha256(merkle root) + sha256(sha256(merkle root))[: 4]

Typical account address:
Qcea29b1402248d53469e352de662923986f3a94cf0f51522bedd08fb5e64948af479

Каждый аккаунт имеет баланс, деноминированный в квантах, делимый вплоть до единственной единицы Шора. Адреса с каждой транзакцией используют новую пару ключей одноразовой подписи. Счетчик транзакций, называемый nonce, будет увеличиваться с каждой транзакцией, отправленной с аккаунта. Это позволяет кошелькам, которые не хранят всю цепочку блоков, отслеживать их местоположение в схеме подписи гипердерева с сохранением состояния.

Текущее состояние проекта и планы на будущее

После выпуска «белой книги» группа пополнилась несколькими новыми разработчиками и началась работа над воплощением задуманного в жизнь. На сайте проекта появились регулярные отчеты о проделанной работе. И к апрелю 2017 года уже была запущена тестовая сеть блокчейна QRL. Исходный код проекта выложен на Github. Проект активно обсуждается на Bitcointalk и Reddit.

В мае 2017 было проведено ICO в экосистеме Ethereum. Выпущен токен QRL стандарта ERC20. Всего было выпущено 65 млн. токенов. Из них в обращении находится 52 млн. токенов. Постепенно в течение 200 лет будет выпущено еще 40 млн. монет. Таким образом, общий объем эмиссии составит 105 млн. монет. При запуске основной сети эти токены можно будет обменять на QRL монеты в соотношении 1:1. В настоящий момент токены доступны для покупки на таких биржах как Bittrex, Upbit и Liqui. Котировки QRL, согласно сайту coinmarketcap.com , представлены на рисунках ниже.

Запуск основной сети намечен на февраль-март 2018.

В дальнейшем планируется изменить алгоритм консенсуса с подтверждения работы на подтверждение доли (proof-of-stake). Ожидаемое безопасное время нахождения блоков будет составлять 15-30 секунд.

Conclusion

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

QRL — первая блокчейн-технология, призванная решить эту проблему. В будущем, конечно, появятся и другие. Какая из них будет наиболее успешной — покажет время.

Thanks

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