Новости Посмертное вскрытие ошибки с выбором ложных выходов

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

  1. Mr. Pickles

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

    Регистрация:
    11 сен 2017
    Сообщения:
    995
    Симпатии:
    249
    Автор: Джастин Берман (j-berman)
    20 сентября 2021 г.


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

    В период между версиями v0.14.1.0 и v0.17.2.2 Monero основной код кошелька содержал в алгоритме выбора ложных выходов две ошибки, которые влияли на приватность пользователей Monero:
    1. Периодически алгоритм игнорировал самые последние расходуемые выходы и не рассматривал их в качестве ложных. По этой причине было проще понять, когда пользователи тратили выходы сразу же после того, как такой выход уже можно было потратить.

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

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

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

    Технические пояснения

    Ошибка №1: неправильное применение алгоритма

    Алгоритм выбора ложных выходов предназначен для выбора выходов из всего блокчейна на основе наблюдаемых шаблонов расходов, как это рекомендуется в работе Мёзера и др. При анализе, описанном в статье, используются шаблоны траты, принадлежащие более ранним версиям Monero (где в некоторых случаях реальные выходы, используемые в транзакциях, могут быть идентифицированы с высокой степенью определённости), что позволяет прийти к распределению шаблонов траты пользователей Monero. В статье подчёркивается, что пользователи с большей вероятностью потратят выходы, полученные относительно недавно, а не те выходы, которые хранились в течение длительного времени. Кроме того, в данной работе рекомендуется факторизовать наблюдаемые шаблоны траты при выборе выходов из всего блокчейна для использования в качестве ложных, а не применять равную вероятность ко всему набору выходов, имеющемуся в блокчейне. Таким образом, новые выходы с большей вероятностью будут выбраны в качестве ложных, чем старые, что позволит лучше скрыть, какой из выходов является реальным в транзакциях пользователей.

    Когда рекомендации, приведённые в работе, были впервые реализованы в версии v0.13.0.0 Monero, кошелёк при выборе ложных выходов надлежащим образом использовал наблюдаемый шаблон траты, взяв его с конца блокчейна. Однако когда алгоритм был обновлён до версии 0.14.1.0, он стал использовать наблюдаемый шаблон траты, взятый за 10 блоков до конца блокчейна. Такое решение было принято потому, что выходы младше 10 последних блоков блокируются и не могут быть потрачены. Поэтому было логично применить распределение, начиная с 10 блоков до конца блокчейна, чтобы учитывались только те выходы, которые можно потратить. Тем не менее в конечном варианте реализации некоторые самые последние выходы, которые уже можно было потратить, игнорировались при выборе ложных выходов. Помимо этого, в результате алгоритм стал выбирать меньшее количество ложных выходов, возраст которых составлял примерно 10–20 блоков.

    Эта ошибка была исправлена в соответствии с PR №7821.

    Ошибка №2: деление на 0

    При обновлении алгоритма выбора ложных выходов в версии v0.14.1.0 учитывалась изменчивость размера блоков, что обеспечило лучшее соответствие шаблонам траты и уменьшило тенденцию к выбору coinbase-выходов в качестве ложных. При выборе ложного выхода алгоритм сначала определяет его возраст в секундах (это делается путём распределения известных шаблонов траты, о которых говорилось выше). Затем алгоритм делит ожидаемый возраст выходов, выраженный в секундах, на среднее количество секунд между каждым выходом, наблюдаемым за последний год. Так в блокчейне вычисляется выход, который следует использовать в качестве ложного. Если количество выходов в году эквивалентно количеству секунд в году, то среднее количество секунд между каждым выходом в течение года равно 1.

    В вычислении среднего количества секунд на выход присутствовала ошибка, из-за которой результат округлялся. Если среднее количество секунд на выход было ниже 1, результат округлялся до 0. Когда алгоритм делит расчётный возраст выхода, выраженный в секундах, на 0, в большинстве систем это приводит к выбору ложного выхода исключительно из самого последнего блока, в котором выходы уже можно потратить. Таким образом, если объём выходов увеличится в течение длительного периода настолько существенно, что значение интервала между каждым из выходов за последний год упадёт ниже 1 (то есть количество выходов за последний год превысит количество секунд в году), то в подавляющем большинстве случаев алгоритм будет выбирать ложные выходы из самого последнего блока, выходы из которого можно будет потратить. На момент данной публикации среднее количество секунд на выход составляло около 1,7.

    Данная ошибка с делением на 0 была исправлена в соответствии с PR №7845.

    Заключение

    Работа над улучшением алгоритма выбора ложных выходов продолжается. Его можно улучшить так, чтобы обеспечить более надёжную защиту пользователей в целом ряде иных обстоятельств. Внимание! Мы призываем любого, имеющего опыт работы в области статистики и теории вероятностей, принять участие в обсуждении вопросов, связанных с улучшением алгоритма. Такие дискуссии часто ведутся на каналах IRC/Matrix в группах #monero-research-lab и #monero-dev. В то время как параллельно проводятся различные инновационные исследования по улучшению криптографии Monero, имеющие своей целью существенное увеличение количества ложных выходов, смешиваемых с реальными выходами транзакций (то есть увеличение размера кольца), также набирают обороты и исследования по совершенствованию методов статистической обфускации при использовании алгоритма выбора ложных выходов. Если вы считаете, что обладаете необходимыми навыками, имейте в виду, что заинтересованность сообщества Monero в активном привлечении вас к работе над проектом Monero постоянно растёт. Если вас интересна данная проблема, свяжитесь в рабочей группой Monero!

    ---

    Источник:
    Post-Mortem of Decoy Selection Bugs

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

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