31.01.2018 07:17
masterdak 35 6600 Источник

В этой статье я расскажу о проблеме безопасности в технологии блокчейн в свете роста производительности квантовых компьютеров, разберу некоторые методы защиты от атак с применением квантового компьютера и о недавно появившемся проекте: Quantum-Resistant Ledger. Как заявляют разработчики, это будет первая в мире платформа, построенная на принципах постквантового шифрования и предназначенная для обеспечения защиты от «квантового удара» на случай быстрого развития этих технологий. Такому удару могут быть подвергнуты платформы, построенные с использованием классических принципов шифрования. Без фундаментальных изменений Bitcoin, Ethereum, Ardor и большинство подобных платформ в недалеком будущем могут оказаться в уязвимости.

Часть 1. Проблема безопасности


Уязвимость


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

С использованием классических алгоритмов атаки практически невозможно найти закрытый ключ, зная открытый. Системы асимметричного шифрования, такие как RSA и подобные (DSA, DH и пр.), построены на том утверждении, что сложность разложения числа на простые множители растет экспоненциально от размера ключа. Однако, с использованием алгоритма Шора на квантовом компьютере становится возможным за полиномиальное время разложить число на простые множители и, таким образом, найти закрытый ключ, зная открытый.

В 2001 году компания IBM продемонстрировала эту возможность, разложив число 15 на два простых множителя 3 и 5. Для этих целей был использован квантовый компьютер, состоящий из 7 кубитов. С тех пор развитие технологий квантовых вычислений происходит все быстрее.

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

В июле 2017 российско-американскими физиками был создан программируемый 51 кубитный компьютер.

В конце октября 2017 Международная исследовательская группа из Сингапурского и Австралийского университетов пришла к выводу, что большинство криптографических протоколов, применяемых в блокчейне, уязвимо к атакам мощного квантового компьютера. В отчете группы приводятся 2 прогноза роста мощности квантового компьютера: оптимистичный и менее оптимистичный. Согласно первому, количество кубит квантового компьютера будет удваиваться каждые 10 месяцев. Менее оптимистичный прогноз говорит об удвоении количества кубит каждые 20 месяцев. На рисунке ниже представлены графики обоих прогнозов.


Наиболее уязвимым к атакам квантового компьютера признан алгоритм создания цифровой подписи на основе эллиптических кривых (ECDSA). Таким образом, говорится в отчете группы, Биткойн в его классическом виде может быть взломан уже к 2027 году.

Может, не все так плохо? Публичный ключ не хранится в открытом виде


В конце апреля 2017 года на сайте bitcoin.com выходит статья, призванная ответить на вопрос, стоит ли держателям Биткойна опасаться его взлома с помощью квантового компьютера. В ней говорится, что не смотря на то, что в блокчейне Биткойн применяется асимметричное шифрование, пользователям не стоит опасаться за сохранность своих монет. Открытый ключ не хранится в открытом виде. Так, адреса для передачи монет не являются открытыми ключами, а лишь результатом применения хеш-функции SHA-256. Функция хеширования выполняет одностороннее преобразование и поэтому является устойчивой к атакам квантового компьютера.

Публичный ключ становится известен во время транзакции


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

Пусть Алиса в своем кошельке на одном из Биткойн-адресов имеет 100 mBTC (1000 mBTC = 1 BTC). Она хочет перевести Бобу 1 mBTC. Для этого она указывает Биткойн-адрес Боба, комиссию за перевод и Биткойн-адрес в ее кошельке для получения сдачи. Пусть в качестве комиссии Алиса указала 1 mBTC. Таким образом, из 100 mBTC, имеющихся у Алисы 1 mBTC отправляется Бобу, 1 mBTC уходит в качестве комиссии сети Биткойн и 98 mBTC возвращается в кошелек Алисы.

Теперь разберем, что же происходит на уровне сети Биткойна. У Алисы и Боба есть кошельки, содержащие адреса для хранения монет. Один кошелек может содержать несколько Биткойн-адресов. Адреса генерируются при создании кошельков. Каждому адресу соответствует созданная по алгоритму ECDSA пара ключей: открытый и закрытый. При передаче монет создается транзакция, в которой передается информация о количестве передаваемых Алисой монет, Биткойн-адрес Боба, подпись, выполненная закрытым ключом Алисы, публичный ключ Алисы и некоторые другие данные. Далее транзакция в открытом (нешифрованном) виде отправляется в сеть. Узлы сети, прежде чем принять транзакцию к обработке, проверяют ее подпись используя открытый ключ. В случае достоверности подписи они добавляют информацию о транзакции в блок. Такая операция включения называется подтверждением.

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

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

Комиссия за транзакцию, строго говоря, не является обязательной, но ее отсутствие может надолго отложить выполнение транзакции. Справедливо и обратное утверждение: можно несколько ускорить прохождение транзакции, увеличив размер комиссии. На момент написания статьи (январь 2018) большинство ПО кошельков предлагает указать комиссию в размере 1 mBTC. Есть ряд ресурсов, например, этот, которые позволяют оценить время включения транзакции в блок в зависимости от размера комиссии.

Использование открытого ключа 1 раз


С точки зрения безопасности, лучше всего получать сдачу на новый адрес, открытый ключ которого будет неизвестен сети. В этом случае, пара ключей используется только 1 раз. Однако, согласно статистике по состоянию на декабрь 2017 года около 41,34% адресов используется повторно.

10 минут, чтобы совершить атаку


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

Статические адреса более уязвимы


В таких системах как Ethereum, NXT, Ardor и др. открытый ключ становится также известным после первой транзакции. Ситуация усугубляется тем, что токены или смарт-контракты привязаны к статическим адресам, атака на которые может проводиться продолжительное время. Если атака будет успешной, то злоумышленник сможет разрушить всю основанную на этих адресах экономическую систему.

Часть 2. Пути решения


Чем обеспечить устойчивость к атакам квантового компьютера?


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

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

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

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

Как уже было сказано ранее, хеш-функция выполняет одностороннее преобразование сообщения. Сообщение преобразуется в значение хеша фиксированной длины. Использование хеш-функции с одной стороны должно сделать бессмысленным перебор сообщений для получения аналогичного значения хеша. С другой стороны, алгоритм должен быть устойчив к коллизиям: когда 2-м разным сообщениям соответствует одно и то же значение хеш-функции.

Квантовый алгоритм Гровера может быть использован для попытки найти коллизию или выполнить предварительную атаку, чтобы найти исходное сообщение. Для этого потребуется $O(2^{\frac{n}{2}})$ операций. Таким образом, для поддержания 128-ми битной безопасности, необходима длина результирующего хеша не менее 256 бит. В качестве такой функции может быть выбрана SHA-256.

Подпись Лэмпорта


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

Схема подписи
Для сообщения $M$ длиной $m$ генерируются ключи. Сперва парами генерируются закрытые ключи $SK$ длиной $n$, затем, применяя хеш-функцию, из закрытых ключей формируются пары открытых ключей $PK$. Количество пар закрытых и открытых ключей равно количеству бит в исходном сообщении.


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



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

Как правило, перед применением подписи исходное сообщение хешируется для уменьшения его размера. Пусть в качестве хеш-функции выбрана SHA-256, тогда $m = n = 256$. При этом общая длина открытого (как и закрытого) ключа $L_{PK}$ получается равной:

$L_{PK} = n * 2 * m = 256 * 2 * 256 = 128 Кб = 16 КБ.$


Длина подписи $L_S$ составляет:

$L_S = n * m = 64 Кб = 8 КБ.$



Подпись Лэмпорта является одноразовой (остается безопасной только при однократном ее использовании), поскольку при ее выполнении и передаче становится известной половина закрытого ключа. Пусть длина сообщения равна 256 байт и длина хеша равна 256. До того, как Алиса опубликует подпись к сообщению, никто не знает 2 * 256 случайных чисел в секретном ключе. Таким образом, никто не может создать правильный набор из 256 чисел для подписи.

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

Тот факт, что подпись Лэмпорта является одноразовой, в сочетании с внушительным суммарным объемом подписи и открытого ключа (24 КБ при длине сообщения в 256 байт и длиной хеша в 256 байт), делает ее использование в публичном блоке транзакций нецелесообразным.

Подпись Винтерница


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

Схема подписи
Сообщение $M$ длиной $m$ разбивается на фрагменты $M_i$ длиной $w$. Для каждого фрагмента генерируется закрытый ключ $SK$ длины $n$. К каждому закрытому ключу последовательно применяется операция хеширования $2^w-1$ раз (раундов $R$). В результате проведенных операций получаются соответствующие им открытые ключи $PK$ той же длины $n$.



При подписи, как и при генерации публичных ключей, производится итеративное вычисление хеша над закрытыми ключами. Количество повторений в каждом случае зависит от подписываемого сообщения. Как уже говорилось ранее, сообщение разбито на блоки длины $w$. Численное значение этого блока $M_i$ и является количеством итераций, которые необходимо выполнить над закрытыми ключами для получения подписи. Соединение полученных блоков и будет подписью данного сообщения.



При проверке подписи над фрагментами ее длины $n$ производится итеративное вычисление хеша. Количество раундов $R_i$ применения хеш-функции определяется как разность между количеством итераций для получения открытого ключа и численного значения блока сообщения, т.е. $R_i = 2^w-1 - M_i$ раз. Затем полученные значения сравниваются с соответствующим публичным ключом.

Пример
Проиллюстрирую вышесказанное небольшим примером. Пусть дано сообщение $M$ (в битовом представлении) длины $m$, параметр Винтерница $w$ и некоторая хеш-функция длины $n$:

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


Генерируем $m/w = 2$ закрытых ключа на основе генератора псевдослучайных чисел. К каждому закрытому ключу применяем $2^w-1 = 255$ раз хеш-функцию, тем самым получая $2$ открытых ключа, которые объединяются в один общий ключ длины $2 * n = 512$ бит. Далее по каждому блоку сообщения $M$ длины $w$ определяем количество применяемых к закрытому ключу операций хеширования $R_i$. В данном случае это будут значения $11000111_2 = 199_{10}$ и $01100111_2 = 103_{10}$ соответственно. Выполнив операцию хеширования на закрытых ключах получаем подпись длиной $2 * n = 512$ бит.

Для проверки подписи делим ее на части длиной $n$. Над каждой частью производим $R_i=2^w-1 - M_i$ операций хеширования. Т.е. $255 - 199 = 56$ и $255 - 103 = 152$ раза соответственно. Если в результате проведенных операций получается значение совпадающее с открытым ключом, значит, сообщение достоверно.

При использовании SHA-256 в качестве хеш-функции для подписи Винтерница, $m = n = 256$.

Пусть $w = 8$ бит. Тогда полный размер открытого ключа $L_{PK}$ и подписи $L_S$ равны:

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


Количество операций вычисления хеша в данном случае равно:

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


Для случая с $w = 16$, это значение возрастает до $P = 1048560$.

Размеры открытого ключа и подписи, при тех же параметрах, что и в примере для подписи Лэмпорта, равны 1 КБ. В сумме это меньше, чем в подписи Лэмпорта (24 КБ). Однако, количество операций вычисления хеша при этом составляет 8160. Что, несомненно, очень много. К тому же, при проверке подписи выполняется в среднем половина от этого количества итераций. Это делает данный вариант подписи нецелесообразным для использования в блокчейне.

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

Дерево Меркла (MSS)


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

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

Подробнее


Вычисление дерева производится от листьев к корню. Каждый узловой лист дерева вычисляется как хеш от сгенерированного открытого ключа. Остальные узлы вычисляются путем получения хеша от конкатенации (склеивания) дочерних узлов. Таким образом рассчитывается все дерево до корня. Пусть есть 4 пары ключей, дерево Меркла рассчитывается вычислением 7-ми хешей (см. рисунок выше).

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

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

Проверка подписи подразумевает вычисление корня на основе переданных параметров и сравнение с ним как с многоразовым публичным ключом. Этими параметрами являются:

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

При использовании одноразовых подписей Меркла или Винтерница нет необходимости передавать отдельно выбранный одноразовый открытый ключ, поскольку его можно получить из подписи сообщения. Достаточно передать его номер, отражающий его положение в дереве. Например, на рисунке выше передаваемыми параметрами будут: подпись, корень, номер листа — 0 (номер листа с ключом $PK1$) и хеши $H2$ и $H6$. При выполнении проверки подписи из нее будет получен открытый ключ $PK1$, соответственно, и хеш $H1$. Хеши $H1$ и $H2$ позволят вычислить $H5$. А хеши $H5$ и $H6$ позволят вычислить корень $R$, который можно будет сравнить со значением переданного корня.

Дерево Меркла, составленное и рассчитанное из открытых ключей, позволяет вместо публикации всего их множества опубликовать лишь корень дерева. Это увеличивает размер подписи за счет включения части дерева в подпись, но дает возможность используя только 1 хеш проверить множество подписей. Так, при глубине дерева $N$ можно подписать $2^N$ сообщений.

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

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


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

Подробнее
Гипердерево представляет собой структуру, состоящую из деревьев Меркла. В этой структуре по назначению выделяются 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. Плавающая комиссия
Бо?льшие размеры транзакций по сравнению с другими блоками цепочки транзакций требуют оплаты для каждой транзакции. По мнению Ватерленда, рынки с искусственной комиссией (например, Биткойн) не нужны и противоречат идеалу открытого блокчейна. Каждая транзакция, если она сопровождается минимальной оплатой, должна быть такой же действительной, как и любая другая. Размер минимальной оплаты, приемлемой для майнеров, должен быть плавающим и устанавливаться рынком. Т.е. узлы (майнеры) должны конкурентно устанавливать нижнюю границу оплаты между собой. Абсолютное минимальное значение будет соблюдаться на уровне протокола. Таким образом, майнеры будут заказывать транзакции из мемпула для включения в блок по своему усмотрению.

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

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

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

6. Адаптивный размер блока
Во избежание возможных споров было смоделировано готовое адаптивное решение, базирующееся на предложении Bitpay, которое использует для увеличения размера блока множитель $x$ средней величины $y$ последних $z$ блоков. Использование средней величины не позволяет майнерам манипулировать, включая либо пустые, либо переполненные блоки для изменения среднего размера блока. $x$ и $z$ будут тогда жесткими консенсусными правилами для сети, которым придется подчиняться. Таким образом, максимальный размер блока $b$ можно просто вычислить как: $b = xy$.

7. Денежная единица — квант
Базовой единицей валюты является квант. Каждый квант делится на наименьшие элементы. Ниже представлены названия всех элементов в порядке возрастания:
Элемент Значение
Шор $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]

Типичный адрес аккаунта:
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 секунд.

Заключение


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

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

Благодарности


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

Ссылки


  1. Алгоритм Шора.
  2. Разложение числа 15 на простые множители на квантовом компьютере (IBM).
  3. Разложение числа 15 на простые множители на квантовом компьютере (MIT).
  4. Отчет об экспериментах на 51 кубитном компьютере.
  5. Отчет Международной исследовательской группы об устойчивости Биткойна перед квантовым компьютером.
  6. Использование алгоритма генерации ключей ECDSA в блокчейне Биткойна.
  7. Об устойчивости Биткойна к атакам квантового компьютера.
  8. Подтверждение транзакции в сети Биткойн.
  9. Информация о комиссиях в сети Bitcoin.
  10. Статистика повторного использования Bitcoin-адресов.
  11. Квантовый алгоритм Гровера.
  12. Расширенная подпись Винтерница.
  13. Применение одноразовой подписи Винтерница на базе хеш-функции ГОСТ 34.11-12.
  14. Geektimes об Ethereum.
  15. Схема XMSS.
  16. Ленстра. Выбор размеров криптографических ключей.
  17. GMSS.
  18. CMSS.
  19. Курсы криптовалютных систем.
  20. Ежегодный форум по постквантовой безопасности.


Дополнительный материал


  1. Опасен ли квантовый компьютер для Биткойна.


Проект QRL


  1. Сайт проекта.
  2. Белая книга.
  3. Презентация.
  4. Блог.
  5. Исходный код на GitHub.
  6. Ветка обсуждения на Bitcointalk.

Комментарии (35)


  1. ceresian
    31.01.2018 11:06
    #10579707
    -1

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


    1. masterdak Автор
      31.01.2018 11:16
      #10579753

      При хард-форке Биткойна будут потеряны средства, которые хранятся на старых кошельках. Чтобы сделать подобный переход, потребуется участие всех держателей Биткойна (что не реально), иначе кто-то останется в стороне.


      1. norlin
        31.01.2018 14:00
        #10580407

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


        1. masterdak Автор
          31.01.2018 14:12
          #10580481

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


          1. norlin
            31.01.2018 15:19
            #10580705

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


    1. kamnik
      31.01.2018 11:20
      #10579775

      Все верно, можно провести хард-форк в сети Биткойн. Главный вопрос, что делать обладателям кошельков, адреса которых, а следовательно и ключи, были сгенерированы на основе алгоритма ECDSA. Ведь именно закрытый ключ является доказательством обладания данным адресом. Кроме того, любые хард-форки в основной сети Биткойн проходят только после длительных обсуждений или не проходят вовсе (SegWit2x).


      1. ceresian
        31.01.2018 12:29
        #10580097

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


        1. kamnik
          31.01.2018 13:09
          #10580241

          Открытый ключ в блокчейне сохраняется только для тех адресов, с которых были произведены переводы средств на другие адреса. Таким образом, привязать вашим способом можно только адреса, использованные повторно.
          Второй момент. Каким образом можно связать открытый ключ на ECDSA и ключ, сгенерированный по алгоритму, который будет квантово-устойчивым? Для этого в блокчейне должна быть информация о новом публичном ключе, но ее нет, т.к. транзакций с нового адреса еще произведено не было. Провести транзакцию с нового адреса также нельзя, т.к. баланс нулевой, пока нет связи адресов. Адреса и ключи генерируются не блокчейном, а ПО кошелька.
          Связать можно только закрытые ключи, но блокчейн о них ничего не знает и знать не должен.
          Соглашусь с вами на счет того, что часть пользователей сети Биткойна отсеется в случае атаки на сеть при помощи квантового компьютера со всеми вытекающими отсюда экономическими последствиями.


          1. ceresian
            31.01.2018 15:32
            #10580733

            Привязать можно любые адреса, даже те которые не использовались и не существовали. Открытая часть ключа дает связь с закрытой, а та в свою очередь совсеми связанными адресами. Но до часа Х и хадр-форка полная цепочка связей остается тайной. А после через эту цепочку подтвеждаются права на старые скомпромитированые адреса и ключи и происходит переход на новый блокчейн.


            1. masterdak Автор
              31.01.2018 16:11
              #10580819

              1. Вы уверены, что этот форк будет проведен вовремя?
              2. Что делать тем, кто не успеет или забудет на него перейти?


              1. ceresian
                31.01.2018 16:48
                #10580937
                +1

                1. Конечно нет. Я же не главный по биткоину. Но я уверен, что вероятность подобного события очень низка. Будь у меня квантовый компьютер, последнее, что-бы я с ним делал, это воровал копейки из сети биткоина. Если будет украдена большая сумма, то она мгновенно обесценит цену всех битконов. В тех условиях миллион биткоинов — это проклятье.
                  Есть более разумное применение квантового компьютера. А пока подобная технология дойдёт до криминала, то сообщество биткоино-владельцев соизволит поднять зад и сделать форк.
                2. Я уже писал — вороны останутся ни с чем. И на этом заработают те, кто вовремя подсуетится.


        1. masterdak Автор
          31.01.2018 18:05
          #10581177

          Как пишет команда П. Ватерленда:

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

          Вдобавок, далеко не каждый может предсказать где и когда технологические инновации получат существенное развитие. Особенно это верно для технологий, находящихся на стадии становления: блокчейн и квантовые технологии как раз являются такими. Есть потенциал для непредвиденного (скачкообразного) прогресса в области квантовых вычислений, которые могли бы привести к внезапной уязвимости криптовалют, ключи которых сгенерированы с использованием метода ECDSA.


  1. lpwaterhouse
    31.01.2018 11:23
    #10579791

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


    1. kamnik
      31.01.2018 11:44
      #10579841
      +1

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


      1. worldmind
        31.01.2018 22:31
        #10581825
        +1

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


        1. kamnik
          02.02.2018 14:02
          #10585185
          +1

          Это смотря с чем сравнивать. Если сравнить скорость перевода средств между картами VISA, и, скажем, Биткойн, то здесь соглашусь, преимущество не на стороне Биткойн. Если сравнить перевод средств системой SWIFT и перевод средствами Ethereum (или Ripple), то здесь соотношение будет несколько дней против нескольких секунд, как у VISA. К слову, у меня SWIFT-перевод шел почти 2 недели.


          1. worldmind
            02.02.2018 14:15
            #10585215

            Зачем искать какие-то кривые реализации?
            Нормально реализованная централизованная система перевода средств (PayPal?) быстрее чем нормально реализованная децентрализованная т.к. требуется время на консенсус большого числа узлов.


      1. TimsTims
        01.02.2018 20:05
        #10583671

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

        Биткоин никак не решает эту проблему. Биткоин решает только проблему "2 стороны, которые не доверяют банку", только и всего. Переводите биткоины — и второй участник точно так же может вас обмануть (не передать товар/услугу), как и в реальной жизни.


        1. kamnik
          02.02.2018 14:19
          #10585235

          Биткойн — лишь частный случай использования блокчейна. Например, в Ethereum можно создавать смарт-контракты. Одна сторона создает контракт, другая, выполнив ее, получает оговоренное контрактом вознаграждение.


          1. TimsTims
            02.02.2018 22:17
            #10586441

            Смарт-контракты — это распиареное ПО, которое тоже никак не защищают стороны от обмана. Например, пока Etherium не будет интегрирован с базой данных ГИБДД, я не смогу заключить с вами контракт о продаже автомобиля. Либо нужен третье лицо, которое будет заниматься арбитражом сделок за %%, но если мы говорим о полном отсутствии доверия кому-либо, то и третье лицо нужно исключать(да и если вы доверяете третьему лицу(как человеку, который поможет), то лучше уж доверять официальной банковской системе в таком случае, и договорам на бумаге).
            Тоже самое со всем остальным — я заказываю у вас услугу(очистить крышу от снега), то кто должен будет подтвердить контракт? Вы? Или я? Если нет доверия, то и каждый из нас попытается обмануть второго. Но если есть хоть капля доверия, то можно и обычным переводом воспользоваться.
            Хоть ты тресни, но виртуальный мир Etherium никак не связан с реальным миром, это всё сказки.
            Хотя, более-менее сейчас на свет пробивается проект Cardano (ADA), у него одна из главных целей — «правильная» интеграция с банками и законами. В ней многое сделано для подтверждения источника происхождения денег, и привычной анонимности там практически не будет, но поддержка законами вполне ожидается.


      1. worldmind
        02.02.2018 14:17
        #10585221

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


      1. worldmind
        02.02.2018 14:18
        #10585229

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


        1. kamnik
          02.02.2018 14:41
          #10585295

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


          1. worldmind
            02.02.2018 14:46
            #10585321

            тут тогда вопрос упирается в то что называть блокчейном


    1. vasiliysenin
      04.02.2018 20:21
      #10589003

      Хайп больше не вокруг блокчейна, а вокруг биткойна. Смысл в том, что биткойн сам по себе не имеет потребительской стоимости, чтобы он приобрёл стоимость надо создавать ему рекламу, привлекая инвесторов прогнозами повышения стоимости.
      Во время майнинга биткойна расходуются природные ресурсы (на электроэнергию), а ни каких полезных товаров не создаётся.


  1. cicatrix
    31.01.2018 11:48
    #10579855

    А может кто-нибудь объяснить попонятнее, поможет ли квантовый компьютер в майнинге?
    Как я понимаю, для квантового компьютера сложность нахождения очередного хэша должна быть существенно ниже.
    И ещё вопрос — а почему SHA-256 считается устойчивым для атаки на квантовом компьютере?


    1. masterdak Автор
      31.01.2018 12:00
      #10579889

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


    1. masterdak Автор
      31.01.2018 12:27
      #10580077

      SHA-256 устойчив к атакам квантового компьютера. К такому выводу пришла группа канадских исследователей. Подробнее можно посмотреть здесь.


    1. fivehouse
      31.01.2018 13:41
      #10580347
      +1

      И ещё вопрос — а почему SHA-256 считается устойчивым для атаки на квантовом компьютере?
      Потому, что в ходе его вычислений фактически вычисляется 256 бинарных выражений состоящих из 2^256 сложных слагаемых (часть из них вычисляется из ~2^128 переменных). Чтобы это зареверсить нужно как минимум 2^256 объектов, что значительно превосходит количество элементарных частиц в наблюдаемой Вселенной. О времени вычисления речь даже не идет.


  1. write-n-go
    31.01.2018 12:19
    #10580013

    Квантовые вычислительные мощности уже среди нас, бедолаг? Если да, то я бы пересмотрел сложившуюся систему кибербезопасности на корню вдоль и поперек. Но это не так. Громкий заголовок, но к будущему надо готовиться уже прямо щас (сейчас, для перфекционистов)


    1. kamnik
      31.01.2018 12:31
      #10580103

      Почему нет? IBM анонсировала доступ к квантовому компьютеру (5 кубит) для всех заинтересованных в качестве облачных услуг. Microsoft выпустила бета-версию пакета разработки программ для квантовых компьютеров.


      1. molnij
        01.02.2018 10:57
        #10582483

        5 кубит можно эмулировать хоть на бумаге. Это пространство состояний в 32 значения.


  1. mr_tron
    31.01.2018 12:22
    #10580033
    +4

    Квант (от лат. quantum — «сколько») — неделимая порция какой-либо величины в физике.

    Базовой единицей валюты является квант. Каждый квант делится на наименьшие элементы.


  1. Nidere
    01.02.2018 01:45
    #10582043

    Я, конечно, понимаю, как работает технический прогресс, но эта фраза:

    В 2001 году компания IBM продемонстрировала эту возможность, разложив число 15 на два простых множителя 3 и 5.

    меня очень улыбнула :)


    1. molnij
      01.02.2018 10:59
      #10582487

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