Перевод Совершеннейший НОНСенс — статистическое исследование распределения значения нонса в блокчейне Monero

Тема в разделе "Статьи", создана пользователем Mr. Pickles, 14 янв 2019.

  1. Mr. Pickles

    Команда форума Модератор Редактор

    Регистрация:
    11 сен 2017
    Сообщения:
    343
    Симпатии:
    130
    1.jpeg

    На этой неделе я занимался поиском лёгкого привлекательного исследовательского проекта на выходные, и мне показалось, что было бы забавно поиграть с визуализацией имеющихся в доступе значений нонсов. Neptune Research (соучредитель и разработчик Monero Archival Project) любезно предоставили нам выгруженные из блокчейна Monero данные нонсов.

    Я ожидал, что анализ этих данных станет совершенно бессмысленным предприятием, так как возможные выигрышные значения разбросаны в произвольном порядке в огромном диапазоне входов, которые майнеры выбирают при помощи грубой силы. Я даже пошутил в Monero Research Lab: «Мой Jupyter Notebook в конечном счёте покажет, что я потратил час на решение совершенно бесполезной задачи, что само по себе уже будет доказательством работы»...

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

    Пример блока

    Рассмотрим этот блок Monero, который появился, пока я пишу статью. Мы видим упрощённую версию информации, которую он содержит:
    HTML:
    HEIGHT: 1711798
    PREVIOUS BLOCK: 4343ccb0eccf8beac6f95461fe5f5e3aa61b8b49a8d7e920e1f8103826a73908
    TRANSACTIONS: 6b6abb2a046a694d5edc21eeb5a7ddb5aefa4ed494be870c4f19d3612456ea4d
    ccf04b4fe210c5c123d032de6bff200407d955248fdc155cac0414d6c137fb3d
    a813579edc10878ca5fd9d40a678e49db23ff6c1c863c78293549d13576dd522
    37f76871ccd09e0085a85888e71936b9c2305de306aee0d0194be20052120067
    b6b43cd533fd99a966cf20fd4d825244bc62624b7dce4e697863a722c098e7ed
    8e323de9a6595b889a36d1c92f37e9213b55e955da7ae8210edbec3f355147ec
    6a469086bb7733778c8f5c746ad0684a32f89ae7b4e8284722870ad62f75c7a5
    
    NONCE: 944
    Этот (реальный) пример блока содержит ссылки (указатели) на 7 транзакций, которые были добыты из пула памяти. Майнер отмечает высоту блока и ссылку на предыдущий блок.

    Наконец, майнер должен выбрать для нонса произвольное значение, связать его с остальной информацией и хешировать весь блок (включая нонс). Если в конце хеша выхода будет достаточное количество 0, то майнер успешно завершит блок. В этом случае майнер определил, что нонс 944 дал следующий хеш выхода:
    HTML:
    5f9d2da9bb79d244805918bf198560d7e34600d3d33e1a0cde12e40800000000
    Исходные данные

    Поле нонса может содержать любое 32-битное целое число. Другими словами, майнер может включать любое целое число от 0 до 4 294 967 295, которое даст значение хеша, соответствующее порогу сложности сети.

    После того как майнер подготовит блок (за исключением нонса), необходимо методом подбора найти пространство нонса, чтобы найти действительный нонс. Следует отметить, что обычно есть множество значений, разбросанных в произвольном порядке от 0 до 4,3 миллиарда, среди которых находится приемлемый нонс, и майнеру необходимо найти одно из них!

    Ожидания

    Если майнеры произвольно выбирают значения от 0 до 4,3 миллиарда, а выигрышные нонсы произвольно распределяются в том же самом диапазоне, то среди значений, сохранённых в блокчейне, должен быть паттерн.

    В этом случае мы можем ожидать, что распределение будет «единообразным». Другими словами, мы ожидаем, что примерно такое же количество блоков будет заполнено нонсами от 1 до 2 миллиардов, так как есть блоки, которые были заполнены нонсами от 2 до 3 миллиардов.

    Реальность

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

    01.png

    Давайте приблизим этот гигантский столбец в левой части диапазона нонсов от 0 до 10 000:

    02.png

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

    Масштаб применения этой практики становится более понятным с точки зрения функции распределения (CDF) значений нонсов:

    03.png

    При линейной оси x CDF начинается с y = 0,6 , так как большинство нонсов появляется в диапазоне от 0 до 10 000, а область на вышеприведённом графике имеет ширину всего 1 пиксель.

    Такое распределение в обычном диапазоне нахождения нонсов гораздо проще визуализировать, если мы перестроим график, используя данные по оси x:

    04.png

    Примечателен тот факт, что половина нонсов находится в диапазоне от 0 до 10(5), что охватывает только малую часть возможных значений!
    Фракция блоков, найденных в этом малом диапазоне, может использоваться как показатель количества майнеров, использующих эту стратегию поиска. В этом случае получается, что приблизительно половина хеш-рейта используется программным обеспечением, которое начинает линейный поиск нонсов с нуля.

    Другие обнаруженные алгоритмы поиска нонсов

    05.png

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

    Перед тем как мы рассмотрим и эти отрезки, давайте взглянем на произвольный кусок области поиска, чтобы определить наличие какой-либо структуры. Посмотрим на распределение нонсов в диапазоне от 60 000 000 до 61 000 000. Как и ожидалось, паттерн отсутствует, а значения распределяются грубо однородно.

    06.png
    «Контрольный случай», концентрируясь на произвольной подгруппе нонсов, мы видим единообразное распределение без отклонений.

    Теперь, учитывая контрольный случай, о котором говорится выше, давайте взглянем на верхний конец области поиска. Написал ли кто-нибудь программное обеспечение, которое начинает поиск с максимального значения нонса (2(*32)) и сканирует в обратном направлении? (Следует отметить, что смещение по оси x составляет 4,3*10(*9) ~ 2(*32)).

    07.png
    Рассматривая конец области нонсов со значениями близкими к 2(*32), мы отмечаем, что майнеры начинают с максимального значения и осуществляют поиск в обратном направлении!

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

    В случае с последним примером рассмотрим поближе область примерно посередине (следует отметить, что смещение по оси x составляет 2,1*10(*9) ~ 2(*32)/2).

    08.png
    Приблизив область очень близко, мы увидим, что некоторое программное обеспечение начинает сканирование с центра области поиска нонсов (2(*32) /2 ~ 2 миллиарда) и сканирует вверх.

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

    Выводы

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

    Например, предположим, что программное обеспечение X осуществляет поиск нонсов в области, начиная с середины (~2,1 миллиарда) по направлению вверх. Любые блоки с нонсами в диапазоне менее 2,1 миллиарда едва ли будут найдены программным обеспечением X. Взглянув на CDF, мы можем отметить, что это выделяет в блокчейне примерно 70% блоков, которые НЕ могли быть найдены программным обеспечением X, и примерно 30% блоков, которые могли быть найдены с его помощью.

    Эта явная особенность также проявляется в другом довольно малом окне области поиска (0,002%), начиная с середины. Интегрировав этот малый отрезок в соответствии с гистограммой, мы увидим, что ~50 000 блоков (из 1,6 миллиона) были сгенерированы программным обеспечением, которое сканирует вверх, начиная с серединной точки. Это эвристически делит пул на 3% блоков, которые могли быть добыты программным обеспечением X, и 97% блоков, добытых программным обеспечением, использующим другую стратегию поиска.

    Этот тип эвристического разделения не очень информативен (то есть никак не влияет на анонимность) для программного обеспечения, использующего два «нормальных» паттерна поиска, то есть:
    • сканирует область поиска нонсов линейно, начиная с 0;
    • выбирает нонсы в произвольном порядке.
    Тем не менее необычные паттерны поиска (такие как сканирование, начиная с центра) приводят к тому, что блоки находятся в кластерах значений нонсов, где они могли бы быть найдены тем же программным обеспечением или 2+ другими, использующими идентичную необычную стратегию (см. бритва Оккама).

    Обновление от 01.07.2018: Энтони ле Кальвез (Antoine Le Calvez) только что поделился просто фантастической визуализацией, которая демонстрирует, как эти радикальные паттерны поиска нонсов внезапно испарились после обновления сети 2018 года, что стало темой моей первой статьи в Hackernoon.

    Что это означает для вас?

    Этот анализ и его результаты абсолютно никак не влияют на анонимность и безопасность пользователей Monero.

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

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

    Если вы майнер, применяющий специализированное/тайное программное обеспечение, которое осуществляет майнинг, используя необычный паттерн поиска в области нонсов (например, вниз от максимального предела или же вверх от промежуточной точки), то лучше переключиться на произвольную выборку, чтобы ваши блоки сливались с вашим деревом транзакций и общим блокчейном. Следует отметить, что для каждого нового блока понадобится вызвать random() только раз для первого нонса, а затем можно будет осуществлять последовательный поиск в обоих направлениях. Это полностью устраняет статистические связи между нонсами ваших блоков.

    Рекомендация

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

    Источник: Utter “Noncesense” — a statistical study of nonce value distribution on the Monero blockchain

    Перевод:
    Mr. Pickles (@v1docq47)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)
     
    #1 Mr. Pickles, 14 янв 2019
    Последнее редактирование модератором: 10 фев 2019 в 15:57
    MoneroRus и LeD XIII нравится это.
  • О нас

    Наш сайт является одним из уникальных мест, где русскоязычное сообщество Monero может свободно общаться на темы, связанные с этой криптовалютой. Мы стараемся публиковать полезные мануалы и статьи (как собственные, так и переводы с английского) о криптовалюте Monero. Если вы хорошо владеете английским (или можете писать собственные статьи/мануалы) и хотите помочь в переводах и общем развитии Monero для русскоязычной аудитории - свяжитесь с одним из администраторов.