Новости Алгоритм выбора приманки в Monero игнорирует последние выходные данные (Issue #7807)

Тема в разделе "Новости", создана пользователем Mr. Pickles, 28 июл 2021.

  1. Mr. Pickles

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

    Регистрация:
    11 сен 2017
    Сообщения:
    970
    Симпатии:
    246
    Обзор

    Алгоритм выбора ложных выходов даёт примерно 0 шансов выбрать в качестве ложных самые последние выходы. Сегодня, если пользователь тратит выход непосредственно в том блоке, который он вычисляет, а выход изначально был создан в блоке, в котором имеется менее 100 выходов, реальный выход будет очень просто идентифицировать в составе кольца. Для справки: среднее значение за год составляет около 63 выходов на блок. Следовательно, выходы, которые тратятся сразу после разблокировки, вероятно, сегодня можно идентифицировать в кольцах.

    Для ясности: я согласовал эту информацию с основными разработчиками до её публикации.

    Техническое объяснение

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

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

    В работе Миллера и др. (см. раздел 6.1) при выборе ложных выходов рекомендуется использовать определённый вид распределения, известный как гамма-распределение, который правильно отражает реальные модели траты, наблюдаемые в Monero в то время, когда выходы Monero могут быть связаны в блокчейне. Вот как выглядит рекомендуемое в статье гамма-распределение:

    1.png

    Суть приведённой выше диаграммы состоит в следующем: сегодня значение exp(x) примерно эквивалентно возрасту выходов, когда они тратятся (в секундах). Например, если значение exp(x) равно 120, это означает, что выходу было 120 секунд, когда он был потрачен. Если приблизить определённую точку на этом графике, то значение y будет ожидаемой вероятностью того, что выходу exp(x) секунд ИЛИ он будет моложе, когда будет потрачен. Например, когда exp(x) имеет значение ~133 000, значение y составляет ~0,50. Это означает, что ~ 50% выходов, как ожидается, будет потрачено за ~133 000 секунд или меньше.

    Далее, на приведённой выше диаграмме не учитывается, что в кольце используется 10 ложных выходов. Вероятность того, что среди 10 выходов есть по крайней мере один выход со значением exp(x) равным ~133 000 секунд или меньше, на самом деле намного выше, чем вероятность наличия одного выхода со значением exp(x) ~133 000 или меньше. Если учитывать тот факт, что в кольцах имеется 10 ложных выходов, диаграмма, отображающая ожидаемую вероятность, что в кольце содержится по крайней мере один выход, значение которого составляет exp(x) секунд или меньше, если двигаться вдоль оси x, будет выглядеть следующим образом:

    2.png
    Сопоставляя вышесказанное с реализацией алгоритма выбора ложных выходов, по достижению exp(x) делит exp(x) на average_output_time (средний возраст выхода), а затем использует это значение при вычитании из общего количества выходов, начиная с 10 блоков, предшествующих текущей высоте. Вот английская версия того, что делает этот код:
    Код:
    gamma_picker::gamma_picker(const std::vector<uint64_t> &rct_offsets, double shape, double scale):
    
        rct_offsets(rct_offsets)
    {
      gamma = std::gamma_distribution<double>(shape, scale);
     
    ...
    
      begin = rct_offsets.data();
      end = rct_offsets.data() + rct_offsets.size() - CRYPTONOTE_DEFAULT_TX_SPENDABLE_AGE;
      num_rct_outputs = *(end - 1);
      THROW_WALLET_EXCEPTION_IF(num_rct_outputs == 0, error::wallet_internal_error, "No rct outputs");
      average_output_time = DIFFICULTY_TARGET_V2 * blocks_to_consider / outputs_to_consider; // this assumes constant target over the whole rct range
    };
    
    gamma_picker::gamma_picker(const std::vector<uint64_t> &rct_offsets): gamma_picker(rct_offsets, GAMMA_SHAPE, GAMMA_SCALE) {}
    
    uint64_t gamma_picker::pick()
    {
      double x = gamma(engine);
      x = exp(x);
      uint64_t output_index = x / average_output_time;
      if (output_index >= num_rct_outputs)
        return std::numeric_limits<uint64_t>::max(); // bad pick
      output_index = num_rct_outputs - 1 - output_index;
    
    ...
    Следует отметить, что сегодня, как подчёркивается в PR #7798, значение average_output_time равно 1. Таким образом, значение exp(x) сегодня эквивалентно секундам.

    Теперь отметим, что на втором графике выше среди 10 ложных выходов вероятность наличия по крайней мере одного значения exp(x), равного ~100 или ниже, фактически равна 0. Это означает, что алгоритм выбора ложных выходов практически никогда не выберет значение exp(x), равное 100 или ниже. Это означает, что если output_index, равный 100 или являющийся более поздним, не будет включён в блок, в который входит БОЛЕЕ 100 выходов, шансы на то, что алгоритм выбора ложных выходов выберет его, практически равны 0. Тот факт, что всё ещё остаётся шанс на выбор ложного выхода со значением индекса <100, сохраняется именно благодаря данной части алгоритма, которая берет output_index, определяемый exp(x), находит блок, в котором он находится, а затем случайным образом выбирает выход из этого блока. Таким образом, выходы из блоков, включающих в себя >100 выходов, имеют шанс быть выбранными в качестве ложных. Но блок, содержащий в себе 10 выходов, например, имеет 0 шансов на выбор любого из его выходов в качестве ложного.

    Рассмотрение практических последствий

    На высоте блока 2412231 всего насчитывалось 35746773 выхода. Следовательно, когда пользователи строили транзакции на высоте блока 2412241, любые выходы ниже 35746773 должны были справедливо включаться в кольца. Однако вероятность того, что кольцо будет включать в себя выходы с 35746772 по 35746672, практически равна нулю, что можно увидеть на этой диаграмме:

    3.png

    Я также запустил get_outs 100 тыс. раз (то есть построил 100 тыс. колец) на высоте 2412241, используя этот код, и ни один выход из блоков 2412231 или 2412230 не был выбран в качестве ложного ни в одном из 100 тыс. колец.

    Последствия этой ошибки также можно рассматривать под следующим углом. На этой диаграмме представлено наблюдаемое внутри блокчейна распределение выходов в диапазоне блоков от 2210720 до 2402699 (начиная с версии Monero v14). Обратите внимание, что в левой части диаграммы наблюдается максимальный подъём. Пиковое значение составляет 11 или 12, но наблюдаются и выходы со значением, равным 10. Я считаю, что этот странный взлёт объясняется тенденцией алгоритма к игнорированию самых ранних из последних выходов. Я обнаружил эту ошибку, исследуя этот странный рост. Я просмотрел список правдоподобных объяснений такого странного повышения и остановился на данной ошибке как на наиболее вероятном объяснении.

    Исправление

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

    Моя первая мысль, связанная с возможностью исправления, заключалась в том, что алгоритм выбора ложных выходов, по сути, был отключён на 10 блоков, а это означает, что гамма-распределение, рекомендованное в документе, уже учитывало время разблокировки. Таким образом, я считал, что алгоритм выбора ложных выходов неправильно применяет гамма-распределение к набору расходуемых выходов, начиная с 10 блоков до определённого момента, вместо того чтобы применять его к набору из ВСЕХ выходов, а затем удаляет выходы, которые нельзя расходовать, из кольца. Однако это не верно, поскольку вероятность того, что выход был потрачен в диапазоне между 120 и 1200 секундами назад, не является незначительной в случае гамма-распределения.

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

    Более подробные сведения об истории введения времени разблокировки, равной 10 блокам, возведении в квадрат в совокупности с использованием описанного в статье гамма-распределения, вероятно, объяснят всё вышеизложенное и позволят внести правильное исправление.

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

    ---

    Источник: Decoy selection algorithm ignores very recent outputs #7807

    Перевод:
    Mr. Pickles (@v1docq47)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)
     
  • О нас

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