Как стать автором
Обновить

Cлучайный оракул на основе цифровой подписи в блокчейне

Децентрализованные сетиКриптографияПрограммированиеКриптовалюты

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



Идея


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


Ломая голову над этим вопросом, окончательно пришёл к выводу: любой блокчейн — это клетка, получить доверенный источник энтропии в замкнутой системе невозможно.


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


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


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


Но, как выяснилось, сделать её детерминированной на самом деле возможно.


Большие надежды у меня были на проверяемую случайную функцию (VRF), но изучив матчасть, от данного вариант пришлось отказаться. Хотя VRF и предлагает детерминированный вариант подписи и её доказательства, в алгоритме присутствует странное место, которое открывает чёрную дыру для манипуляций оракулом (это неверное утверждение, см. Update). А именно, при расчёте значения k (раздел 5.1) используется закрытый ключ, который остаётся неизвестным пользователю, значит пользователь не может проверить корректность вычисления k, значит оракул может использовать любое нужное ему значение k и одновременно вести базу данных соответствий k и подписываемых данных, чтобы всегда уметь повторно вычислить корректный с точки зрения VRF результат. Увидите розыгрыш на основе VRF без раскрытия закрытого ключа, можете поумничать: указать на необходимость или раскрыть ключ, или исключить его из расчёта k, тогда закрытый ключ автоматически сам раскроется при появлении первой же подписи. В общем, как уже было сказано, странная схема для случайного оракула.


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


VECRO — аббревиатура от Verifiable Elliptic Curve Random Oracle, что по-русски означает проверяемый случайный оракул на эллиптических кривых.


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


В такой схеме неважно каким образом фиксируется R, это остаётся в зоне ответственности оракула. Важно, что S однозначно определяется пользователем, но его значение неизвестно пока оракул его не опубликует. Всё как мы хотели!


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


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


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


Полгода идея реализации теплилась в голове, пока наконец не появилась мотивация в виде гранта от Waves Labs. С большим грантом приходит большая ответственность, значит проекту быть!


Реализация


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


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


На текущий момент в основной сети Waves запущен один VECRO (вы можете запустить свой, это не сложно, просто загляните в пример конфигурации). Текущий код работает на PHP (на WavesKit, о котором я рассказывал ранее).


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


  • Зафиксировать R;
    • Отправить минимум 0.005 Waves на алиас оракула init@vecr;
    • Получить R-code в поле attachment в трансфере 1 R-vecr токена от оракула пользователю;
  • Получить подпись;
    • Отправить минимум 0.005 Waves на алиас оракула random@vecr, а также ОБЯЗАТЕЛЬНО указать в поле attachment полученный ранее R-code и дополнительные пользовательские данные;
    • Получить S-code в поле attachment в трансфере 1 S-vecr токена от оракула пользователю;
  • Использовать S-code в качестве источника псевдослучайного числа.

Нюансы текущей реализации:


  • Отправленные оракулу Waves используются в качестве комиссии для обратной транзакции пользователю, вплоть до максимальных 1 Waves;
  • R-code — это конкатенация байта символа ‘R’ и 32-байт значения R в кодировке base58;
  • R-code в attachment должен находиться первым, пользовательские данные идут после R-code;
  • S-code — это конкатенация байта символа ‘S’ и 32-байт значения S в кодировке base58;
  • S является результатом деления по модулю, поэтому нельзя использовать S как полноценное 256-битное псевдослучайное число (данное число может считаться максимум 252-битным псевдослучайным числом);
  • Наиболее простой вариант — использовать в качестве псевдослучайного числа хэш от S-code.

Пример получения S-code:



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


Буду рад ответить на вопросы и принять замечания, спасибо.


Update от 8 мая 2019


Был не прав про VRF. Да, действительно, подпись ECVRF нельзя использовать в качестве источника псевдослучайного числа, но она и не используется по этому назначению. Подпись нужна для построения доказательства однозначности значения Gamma (раздел 5.3, шаг 6). А вот проверенное с помощью подписи значение Gamma уже участвует в качестве источника псевдослучайного числа (раздел 5.2, шаг 5). Спасибо Олегу Тараскину Crittografo за указание на этот момент, признаю свою ошибку. ECVRF имеет полное право на жизнь.


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


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

Теги:waves platformeddsaed25519curve25519randomsignatureblockchain
Хабы: Децентрализованные сети Криптография Программирование Криптовалюты
Всего голосов 14: ↑12 и ↓2+10
Просмотры2.3K
Комментарии Комментарии 12

Похожие публикации

Лучшие публикации за сутки