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



Идея


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


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


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


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


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


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


Большие надежды у меня были на проверяемую случайную функцию (VRF), но изучив матчасть, от данного вариант пришлось отказаться. Хотя VRF и предлагает детерминированный вариант подписи и её доказательства, в алгоритме присутствует странное место, которое открывает чёрную дыру для манипуляций оракулом. А именно, при расчёте значения 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:



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


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

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


  1. worldmind
    25.04.2019 17:27

    Ничего не понял, можно кратко по шагам принцип работы?


    1. deemru Автор
      25.04.2019 23:24

      • пользователь получает от оракула первую половину подписи (из ничего) и держит в запасе;
      • когда пользователю необходимо получить доверенной случайности, он формирует сообщение и получает от оракула вторую половину подписи, используя первую половину подписи как однозначный фиксатор;
      • две половины являются полноценной подписью пользовательского сообщения — это проверяется смарт-контрактом в рамках блокчейна;
      • утверждается, что вторая половина подписи обладает необходимыми свойствами для использования её в качестве доверенного источника энтропии для псевдослучайного числа.


      1. worldmind
        26.04.2019 09:18

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


        1. deemru Автор
          26.04.2019 10:04

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


          Если вам интересна данная тема, в тексте проставлены ссылки для погружения.


          Останутся вопросы — задавайте по существу.


        1. vtools
          26.04.2019 16:44

          Совсем недавно на Хабре было про случайные числа на блокчейне. Без оракула и СМС…


          1. worldmind
            26.04.2019 16:50

            там как раз всё понятно, а вот тут что-то подозрительное


          1. deemru Автор
            26.04.2019 16:55

            Хорошая статья размышление. Готовых решений, а тем более внедрений, ни в одном блокчейне пока нет.


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


        1. datacompboy
          26.04.2019 16:54
          +2

          Задача получить случайное значение заранее, чтоб избежать подтасовки со стороны казино.
          Пример: игра «угадай число».
          Мы отсылаем бабло и предполагаемое число в контракт. Если угадали — получаем обратно вдвое больше.

          Простор для подтасовки огромный:
          — со стороны владельца контракта: генерируем всегда другое число, стрижём бабло
          — со стороны клиента: если мы знаем как генерируется число, мы можем ждать «удобной» транзакции
          — со стороны мощного узла: мы можем собрать удобную транзакцию сами

          Делаем многоэтапно:
          — клиент запрашивает сперва случайное число
          — затем делает своё предположение.

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

          Как обеспечить проверяемость? Простой способ: прикладывать пароль для проверки к ответу результата игры.
          Без прозрачности алгоритма и возможности аудита алгоритма опять же ничем не лучше предыдущего.

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

          Затем запрашиваем шифрованное число (или фиксированную соль для детерминированного алгоритма).
          Делаем предположение, в ответ получаем недостающую половинку для проведения доказательства самостоятельно.

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


          1. worldmind
            26.04.2019 17:10

            Так всё ясно, но такие случайные числа годятся только для очень узкого класса задач, вроде только для угадай число и годится.


            1. datacompboy
              26.04.2019 17:26

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


              1. worldmind
                26.04.2019 17:34

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


                1. datacompboy
                  26.04.2019 23:05

                  А это совершенно другая история, с совершенно нестандартным применением случайности для реально распределённой сети.

                  Всё же оракулы это для уже рабочей сети, а не обспечение жизни самой сети.