17/01/2019
В этом эпизоде Саранг и Джастин более подробно рассказывают о том, как происходит выбор ложных выходов для кольцевых подписей Monero, что это происходит далеко не «случайным образом». Рассказывается, как со временем эволюционировал алгоритм выбора Monero и как важен алгоритм выбора для создания безопасных кольцевых подписей.
Мальти Мёзер (Malte Möser), Кайл Соска (Kyle Soska), Этан Хейлмен (Ethan Heilman), Кевин Ли (Kevin Lee), Генри Хеффан (Henry Heffan), Шашват Шривастава (Shashvat Srivastava), Кайл Хоган (Kyle Hogan), Джейсон Хеннеси (Jason Hennessey), Эндрю Миллер (Andrew Miller), Эрвинд Нарайанан (Arvind Narayanan), Николас Кристин (Nicolas Christin).
«Эмпирический анализ отслеживаемости в блокчейне Monero»
Стенограмма эпизода:
Джастин: Мы снова рады приветствовать вас в Breaking Monero. Сегодня мы поговорим о выборе входов при составлении кольца Monero. Ранее, в прошлых эпизодах, мы уже обсуждали кольцевые подписи и ложные выходы, и Саранг, в частности, говорил о том, как выбираются ложные выходы, при этом он использовал довольно расплывчатое выражение, которое, по крайней мере, сводилось к тому, что «выбор происходит случайно». И в этом эпизоде мы собираемся обсудить нюансы или более конкретно обсудить, что кроется за этим. Эта «мистическая» фраза сама по себе недостаточно точна, поэтому необходимо и даже важно некоторым образом прояснить ситуацию и объяснить, как всё происходит на самом деле. За кулисами действительно довольно много «случайного», поэтому я начну с рисунка, на котором приводятся примеры некоторых алгоритмов выбора входов Monero, которые использовались ранее. Итак, вот здесь, вверху, показан пример алгоритма полностью случайного распределения. Слева можно увидеть старые выходы, которые были сгенерированы в самом начале истории Monero, а справа — новые выходы, сгенерированные совсем недавно, в течение последних нескольких дней или около того. Допустим, что зелёный круг — это фактически потраченный выход. Это реальные деньги, которые отправляются, а синие — это ложные выходы, которые были выбраны. Метод полностью случайного распределения является хорошим примером, с которого нам следует начать, поскольку вход выбирается по какой угодно причине, и это может стать причиной ряда случайных последствий. Таким образом, в результате довольно сложного эвристического анализа можно будет сказать, что люди чаще тратят новые деньги, чем старые. Поэтому последние входы (здесь они выделены зелёным) наиболее вероятно будут реальными. И вам не потребуется никакого эмпирического свидетельства, чтобы доказать, что это истина. Со временем это само докажет свою надёжность. Потенциально вы можете провести тщательнейший эвристический анализ и убедиться в том, что пример, который вы видите в первой строке на экране, служит тому подтверждением, поскольку именно так часто и происходит. Так ведь? Поэтому Monero начинает улучшаться и производить итерацию этого с этим, и уже во второй строке показан пример алгоритма выбора в «недавней зоне». Таким образом, у вас снова есть полная история выходов Monero, но вы ограничены временным периодом такой «недавней зоны», в пределах которой вы, наиболее вероятно, и будете выбирать ложные выходы. Так в коде Monero может быть указано, например, что недавняя зона должна составлять восемь дней, и вам необходимо выбрать примерно половину ложных выходов из этой недавней зоны. Вот тут вы можете увидеть пример, где примерно половина ложных выходов выбрана из этой недавней зоны, а остальная часть относится к прошлому, как в самом начале истории Monero. У вас по-прежнему есть возможность выбирать эти выходы, но они будут встречаться реже новых выходов. И это позволяет решить некоторые эвристические вопросы, о которых мы говорим, когда самый последний выход в кольце наиболее вероятно оказывается истинным, так как теперь кольцо состоит по большей части из последних ложных выходов. Поэтому в данном случае мы имеем большее количество вероятных выбранных выходов. А «недавняя зона» была простым и удобным способом реализации этой возможности, и, определённо, это было улучшением, если сравнивать с системой полностью случайного выбора Monero, с которой всё начиналось, но и этот вариант не был идеален. И поэтому Monero перешли к тому, что примерно показано в нижней строчке, к своего рода «согласуемому распределению», основанному на эмпирически наблюдаемом распределении, которое мы можем сузить и которое находится вне предела подходов, найденных исследователями Bitcoin и Monero. Это математическая модель, и в этом случае можно увидеть, что самые новые выходы выбираются с наибольшей вероятностью, например. Надеюсь, эта диаграмма поможет продемонстрировать не только, как много входов есть в транзакции, но и как они выбираются, и довольно важно именно как они выбираются, и это больше, чем просто вопрос временных рамок, как я могу показать вам — время является только частью всего этого, и на этом месте я передаю слово Сарангу, который более подробно остановится на факторах, связанных с алгоритмом выбора.
Саранг: Да, ты всё правильно сказал. То есть стоить отметить, что технически в том, как мы делаем это, да и как всегда делали, есть элементы случайности. Я хочу сказать, что слово «случайно» зачастую не вполне подходит. Например, несмотря на то, что обычно выбор выходов происходит по какой-то определённой модели, всё равно остаётся некий элемент случайности. То есть два человека определённо могут выбрать совершенно разные кольца, но в среднем они будут использовать паттерн, подобный тому, который был продемонстрирован тобой. Таким образом, здесь всегда будет некоторый элемент случайности. Однако, как ты сказал, эвристический анализ по времени или просто догадки со стороны злоумышленника могут быть просто основаны на возрасте выхода, и, как ты сказал, это будет всего одним эвристическим принципом. И тут очень много от эвристики, поскольку в случае с большим количеством старых транзакций ты сможешь догадаться, какая из них была последней, и ты можешь оказаться прав, а можешь и доказать это косвенно, но время здесь играет лишь частичную роль. И поэтому мы решили использовать итерацию, чтобы избежать меньших эвристических процедур, не основанных на времени. Примером могут служить так называемые coinbase-выходы. Если вы не знакомы с этим термином, то, скажем, каждый блок генерируемых транзакций Monero имеет специальный выход, генерирующий новые деньги согласно протоколу. Частично этот механизм помогает награждать майнеров за их работу. И вы можете рассматривать такие coinbase-выходы, как и я вижу их, в качестве новых создаваемых денег. И в целом люди тратят именно эти создаваемые деньги или coinbase-выходы. Возможно, но совсем не обязательно не так часто, как старые деньги или выходы, не являющиеся coinbase-выходами. Таким образом, например, если мною будет выбрано кольцо, содержащее, ну я не знаю, 10 coinbase-выходов плюс мой реальный выход, который не будет coinbase-выходом, злоумышленник может взглянуть на это и подумать: «Пожалуй, наиболее вероятно, он не стал тратить coinbase-выход, поскольку всё это совершенно новые деньги». То есть это будет эвристика, когда злоумышленник предположит, что coinbase-выходы являются ложными выходами. Ну, в таком случае это будет подразумевать, что нам следует выбирать поменьше coinbase-выходов в качестве части наших колец. А сколько это слишком много или слишком мало? Я хочу сказать, что эта проблема недостаточно сформулирована и не имеет хорошо продуманного решения. Но так как мы итерировали наш алгоритм выбора, чтобы он позволял избежать эвристической процедуры под названием «угадай новенького», учитывающей возраст выхода, мы ввели в дело больше coinbase-выходов, чем могло бы понравиться некоторым. Поэтому мы немного изменили алгоритм, и теперь вместо того, чтобы взять блок, а затем выдернуть из него ложный выход, в результате чего мы получаем больше coinbase-выходов, теперь вместо этого мы рассматриваем небольшое окно вокруг определённого блока. Таким образом, мы эффективно повышаем размер корзины, из которой выбираем наши выходы. И это статистически означает, что мы выбираем меньше coinbase-выходов, что защищает нас от менее масштабного эвристического анализа, хотя и это, конечно же, не единственный вид эвристики, с которой вы можете столкнуться. Таким образом, coinbase-выходы являются единственной вещью, на которую злоумышленник может посмотреть и попытаться угадать временные рамки, в которых мы работали, и мы уже говорили об этом, злоумышленник может использовать один из них. Например, у меня есть транзакция с двумя различными входами, и у каждого из них будет своё кольцо. Возможно, злоумышленник сможет посмотреть на различные ложные выходы и выходы, находящиеся в этих кольцах, и, возможно, злоумышленник увидит транзакцию. Раньше блокчейн генерировал два разных выхода, один из которых мог оказаться входом моей новой транзакции, а другой — входом другой транзакции. И опять же, это будет догадкой, поскольку это могло произойти случайно, а могло и не случайно. Злоумышленник может попытаться прийти к заключению, что выходы, сгенерированные при проведении предыдущей транзакции, теперь тратятся мною, и на этом основании он придёт к определённому выводу. Опять же, при отсутствии внешней информации эвристика не может служить доказательством, но она даёт злоумышленнику почву для построения своих предположений. Так что в целом это очень и очень сложный вопрос. На данном этапе я бы сказал, что невозможно избежать всех возможных эвристических подходов, поэтому нам постоянно надо улучшать наши алгоритмы выбора. И как отметил Джастин, и на что я некоторым образом намекал, мы делаем это время от времени — мы проводим итерацию, что делает алгоритм всё лучше и лучше. Я не хотел бы рассматривать это, как ты, Джастин, фактически назвал это некоего рода аналогией с затыканием дыры, ну, это уже как тебе будет угодно.
Джастин: Ну, одним из примеров известной нам определённой эвристической процедуры, например, является попытка угадать «самый новый». Итак, мы можем итерировать алгоритм выбора Monero, чтобы избежать такой процедуры. Вторым вопросом является его фактическая эффективность, но в этом плане… Мы по-прежнему… Подбирая какой-то другой метод выбора выходов, люди могут выработать и эвристическую процедуру для него. Таким образом, нет предела числу эвристических подходов, которые могут найти люди. Они могут выработать сложные эвристические процедуры, независимо от того, что мы сделаем. Так что мы постоянно занимаемся затыканием дыр, о которых нам становится известно, к тому же самых больших дыр, но мы тем самым косвенно можем создать небольшие дыры, о которых, возможно, и знать не будем, поскольку принципы эвристики ещё не были поняты до конца, в частности, членами сообщества Monero. Так что в этой области нам придётся непрерывно совершенствоваться. Придётся непрерывно проводить итерации, чтобы сделать алгоритм лучше и залатать эти дыры. Вы не можете проложить дорогу и ожидать, что на ней со временем не появятся выбоины. Это просто необходимо пережить, как зиму в штате Миннесота. И надо идти и латать эти рытвины, которые появляются вновь и вновь. И когда ты уже решишь, что всё закончил и можно ехать, ты выедешь на своём грузовике и сделаешь очередную выбоину. Вот как-то так и происходит. (Приношу извинения за такую ужасную аналогию), но сначала я пытаюсь решить большой вопрос. Нами был приведён пример с «угадыванием нового», но ведь могут возникнуть и другие последствия, например, изменение алгоритма выбора может усилить математическое распределение. На деле мы стали выбирать больше coinbase-выходов, а потом нам пришлось возвращаться, чтобы узнать, как же мы сделали это, нам приходится проверять, стало ли улучшение при очередной итерации действительно улучшением в целом? Сейчас мы можем сказать, что, да, так как мы решили существующую эвристическую проблему, и польза превзошла возможный вред. Но всегда сохраняется некоторый компромисс, с которым нам приходится иметь дело. Я бы так сказал.
Саранг: Да, так оно и есть. Я хочу сказать, что мы постоянно получаем отчёты, и люди нам сообщают небольшие паттерны, которые они находят среди определённых транзакций или выходов на основе метода, который мы используем при выборе, и то, что некоторые из них очень и очень малы, это вовсе не означает, что их наличие является допустимым. Однако в некоторой мере нам не всегда очевидно, как сделать однозначно хорошее изменение, чтобы решить небольшие эвристические проблемы и не разрушить того, что было сделано нами при решении некоторых гораздо больших эвристических проблем. Таким образом, если нам указывают на небольшую проблему, но мы не меняем алгоритма, это вовсе не означает, что нас не беспокоит эта указанная вами эвристическая проблема. Это просто означает, что нам всегда приходится взвешивать пользу, которую принесёт такое изменение, относительно неизбежного вреда, который оно может вызвать. Это всегда перерастает в некую гонку вооружений. Финансовая анонимность в целом, как уже говорилось в этой серии эпизодов, представляет сбой гонку вооружений — анализ со временем становится только лучше, и это здорово. Получение нами время от времени отчётов о возникновении различных эвристических проблем не означает, что мы игнорируем их. Мне нравится читать эти отчёты. Мне приятно узнавать, что люди могут делать с этим анализом, но это лишь напоминает мне о том, что данный анализ осуществляется в стиле гонки вооружений: он становится лучше — мы предлагаем лучшее решение, и это ещё больше совершенствует метод анализа, и всё это развивается по спирали, и мы совершенствуемся.
Джастин: Ты говоришь о развитии по спирали в сторону улучшения. Одним из положительных свойств кольцевых подписей является то, что алгоритм выбора и размер кольца идут рука об руку в цикле положительного или отрицательного развития. Предположим, вы намеренно работаете в направлении ухудшения. Но по мере того, как увеличивается размер кольца Monero, нейтрализуются негативные стороны, скажем, плохого алгоритма выбора, или же снимаются ограничения, связанные с алгоритмом выбора. Если вы просто выбираете больше и больше входов, например, больше и больше ложных выходов, недостатки определённого алгоритма могут уменьшиться или, в идеале, совсем сойти на нет. В то же самое время, если вы улучшаете ваш алгоритм выбора, вы улучшаете процесс использования имеющихся ложных выходов. Таким образом, эти два компонента реально критически важны и обеспечивают высокий уровень анонимности Monero, и во многом всё зависит от кольцевых подписей. Но если у вас будет большой размер кольца, но ужасный алгоритм выбора, то вам не удастся добиться желаемого уровня анонимности, поскольку сохранится вероятность создания действительно сильной формы эвристического анализа. Подобным образом, если вы даже создадите некий совершенный алгоритм, который будет работать при любых обстоятельствах, но размер кольца будет небольшим, например, то вы не преуспеете. Поэтому эти вещи и работают в тесной связи и обеспечивают реальную анонимность, которую и должны обеспечивать кольцевые подписи, это гораздо больше, чем заявляется в случае с готовым вариантом, а сейчас в случае с Monero возможным реальным выходом траты является один из одиннадцати. Всё дело во временном анализе дополнительных метаданных, метаданных coinbase, связанных с этим. И в связи с эти алгоритм выбора должен корректироваться время от времени. В противном случае, мы просто будем брать первые 10 выходов, сгенерированных в блокчейне Monero, и можно будет смело утверждать: «так это любой из последних десяти». И это, очевидно, выглядит совсем не убедительно. Так что алгоритм выбора входов очень важен, как и кольцевые подписи Monero. У тебя есть какие-нибудь заключительные мысли или мы попрощаемся на этом с нашими зрителями?
Саранг: Нашей целью по-прежнему является обеспечение максимально правдоподобного отрицания, которое дают кольцевые подписи, и со временем мы будем находить всё лучшие и лучшие способы, позволяющие добиться этого. И мы будем продолжать и продолжать итерации, так как на данном этапе мы далеки от совершенства, но мы продолжим становиться всё лучше и лучше.
Джастин: Хорошо. Спасибо тебе, Саранг. Спасибо всем, кто смотрел этот эпизод «Breaking Monero». Увидимся в следующей передаче.
Саранг: Увидимся
Перевод: Mr. Pickles
Редактирование: Agent LvM
Коррекция: Kukima