Автоматический перевод

MIMBLEWIMBLE

Том Элвис Джедусор

19 июля 2016 г.

----- Вступление -----

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

На момент написания этой статьи в блокчейне было совершено около 150 миллионов транзакций, которые необходимо воспроизвести, чтобы получить набор из 4 миллионов неизрасходованных выходных данных.

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

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

Некоторые решения этого были предложены. Грег Максвелл обнаружил, что шифрует суммы, так что график транзакции безликий, но все же позволяет проверить правильность сумм [1]. Доктор Максвелл также создал CoinJoin, систему для пользователей Биткойн, которая позволяет интерактивно объединять транзакции, запутывая график транзакций. Николас ван Саберхаген разработал систему, которая скрывает записи транзакций, идет гораздо дальше, чтобы скрыть граф транзакций (а также не требует взаимодействия с пользователем) [3]. Позже Шен Нётер объединил два подхода для получения «конфиденциальных транзакций» Максвелла И затемнения Ван Саберхагена [4].

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

CoinJoin доктора Максвелла имеет проблему необходимости интерактивности. Доктор Юань Хорас Мутон исправил это, сделав транзакции свободно объединяемыми [5], но ему нужно было использовать криптографию на основе пар, которая потенциально медленнее и труднее доверять. Он назвал это «односторонними совокупными сигнатурами» (OWAS).

У OWAS была хорошая идея объединить транзакции в блоки. Представьте, что мы можем объединить блоки (возможно, с некоторыми склеивающими данными), чтобы при создании и уничтожении выходных данных они были такими же, как если бы они никогда не существовали. Затем, чтобы проверить всю цепочку, пользователям нужно только знать, когда деньги вводятся в систему (новые деньги в каждом блоке, как в биткойнах или монеро, или пег-ины для боковых цепей [6]) и окончательные неизрасходованные результаты, остальные могут быть удалены и забыты. Тогда у нас могут быть конфиденциальные транзакции, чтобы скрыть суммы, и OWAS, чтобы размыть график транзакций, и использовать меньше пространства, чем биткойн, чтобы позволить пользователям полностью проверить блокчейн. А также представьте, что мы не должны использовать криптографию на основе сопряжения или новые гипотезы, а просто сигнатуры регулярных дискретных логарифмов, такие как биткойн. Вот что я предлагаю.

Я называю свое творение Mimblewimble, потому что оно используется, чтобы препятствовать тому, чтобы блокчейн говорил обо всей информации пользователя [7].

----- Конфиденциальные сделки и OWAS -----

Первое, что нам нужно сделать, это удалить Bitcoin Script. Это печально, но это слишком мощно, поэтому невозможно объединять транзакции с использованием общих сценариев. Мы покажем, что конфиденциальных транзакций доктора Максвелла достаточно (после небольшой модификации), чтобы разрешить расходование ресурсов, а также позволяет совершать комбинированные транзакции без взаимодействия. Это фактически идентично OWAS и позволяет ретранслирующим узлам брать плату за транзакцию или получатель может изменить комиссию за транзакцию. Эти дополнительные вещи Биткойн не может сделать, мы получаем бесплатно.

Мы начнем с напоминания читателю, как работают конфиденциальные транзакции. Сначала суммы кодируются следующим уравнением:

C = r * G + v * H

где C - обязательство Педерсена, G и H - фиксированные генераторы группы эллиптических кривых «ничего-до-моего-рукава», v - величина, а r - секретный случайный слепой ключ.

К этому выходу прикреплен диапазон, который доказывает, что v находится в [0, 2 ^ 64], так что пользователь не может использовать ослепление для создания атак переполнения и т. Д.

Чтобы проверить транзакцию, верификатор добавит обязательства для всех выходных данных, плюс f * H (f здесь - плата за транзакцию, которая указана явно) и вычтет все входные обязательства. Результат должен быть 0, что доказывает, что никакое количество не было создано или уничтожено в целом.

Отметим, что для создания такой транзакции пользователь должен знать сумму всех значений r для записей обязательств. Следовательно, r-values (и их суммы) действуют как секретные ключи. Если мы можем сделать выходные значения r известными только получателю, то у нас есть система аутентификации! К сожалению, если мы сохраним правило, которое фиксирует добавление всех к 0, это невозможно, поскольку отправитель знает сумму всех значений _его_ r и, следовательно, знает сумму значений r получателя с отрицательным значением этого. Таким образом, вместо этого мы разрешаем транзакции суммироваться с ненулевым значением k * G и запрашиваем подпись пустой строки с этим ключом, чтобы доказать, что ее компонент суммы равен нулю.

Мы разрешаем транзакциям иметь столько значений k * G, сколько им нужно, каждое с подписью, и суммируем их во время проверки.

Для создания транзакции отправитель и получатель выполняют следующий ритуал:

1. Отправитель и получатель согласовывают отправляемую сумму. Назовем это b.

2. Отправитель создает транзакцию со всеми входами и изменяет выходные данные и предоставляет получателю общий коэффициент ослепления (r-значение изменения минус r-значения входов) вместе с этой транзакцией. Таким образом, сумма обязательств равна r * G - b * H.

3. Получатель выбирает случайные r-значения для своих выходных данных и значения, которые суммируются с b за вычетом платы, и добавляет их к транзакции (включая подтверждение диапазона). Теперь сумма обязательств равна k * G - fee * H для некоторого k, о котором знает только получатель.

4. Получатель прикрепляет к транзакции подпись с k и явный сбор fee. И дело сделано.

Теперь создание транзакций таким образом уже поддерживает OWAS. Чтобы показать это, предположим, что у нас есть две транзакции, которые имеют избыток k1 * G и k2 * G, и прикрепленные подписи с ними. Затем вы можете объединить списки входов и выходов двух транзакций, с k1 * G и k2 * G, и voilá! снова действительная транзакция. Из этой комбинации невозможно сказать, какие выходы или входы являются исходной транзакцией.

Из-за этого мы изменяем наш формат блока с биткойна на эту информацию:

1. Явные суммы для новых денег (блочные субсидии или пэгины боковой цепи) с любыми другими данными, в которых они нуждаются. Для встраивания в боковую цепь, возможно, он ссылается на транзакцию Биткойн, которая фиксирует определенное избыточное значение k * G?

2. Входы всех транзакций

3. Выходы всех транзакций

4. Превышение значений k * G для всех транзакций.

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

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

----- Слияние транзакций через блоки -----

Теперь мы использовали Конфиденциальные транзакции доктора Максвелла, чтобы создать неинтерактивную версию CoinJoin доктора Максвелла, но мы не видели последнего из чудесного доктора Максвелла! Нам нужна еще одна идея, сквозная транзакция, он описал в [8]. Опять же, мы создаем неинтерактивную версию этого и показываем, как он используется с несколькими блоками.

Теперь мы можем представить каждый блок как одну большую транзакцию. Чтобы проверить это, мы складываем все выходные обязательства вместе, затем вычитаем все входные обязательства, значения k * G и все явные суммы ввода, умноженные на H. Мы находим, что мы можем объединить транзакции из двух блоков, так как мы объединили транзакции, чтобы сформировать единый блок, и результат снова является действительной транзакцией. За исключением того, что некоторые выходные обязательства имеют входное обязательство, точно равное ему, где вывод первого блока был проведен во втором блоке. Мы могли бы удалить оба обязательства и при этом иметь действующую транзакцию. На самом деле, даже нет необходимости проверять дальность удаленного вывода.

Продолжая эту идею от блока генезиса до последнего блока, мы видим, что КАЖДЫЙ неявный ввод удаляется вместе с ссылочным выводом. Остаются только неизрасходованные выходные данные, явные суммы ввода и каждое значение k * G. И весь этот беспорядок можно проверить, как если бы это была одна транзакция: сложите все выходные данные неизрасходованных обязательств, вычтите значения k * G, проверьте явные входные суммы (если есть что проверить), а затем вычтите их раз H. Если сумма равна 0 вся цепочка хороша.

Что это значит? Когда пользователь запускает и загружает цепочку, ему нужны следующие данные из каждого блока:

1. Явные суммы для новых денег (блочные субсидии или пэгины боковой цепи) с любыми другими данными, в которых они нуждаются.

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

3. Превышение значений k * G для всех транзакций.

Биткойн сегодня насчитывает около 423000 блоков, общим объемом около 80 ГБ данных на жестком диске для проверки всего. Эти данные составляют около 150 миллионов транзакций и 5 миллионов неизрасходованных неконфиденциальных выходных данных. Оцените, сколько места занимает количество транзакций в цепочке Mimblewimble. Каждый неизрасходованный выход составляет около 3Kb для защиты от дальности и от Merkle. Каждая транзакция также добавляет около 100 байтов: значение ak * G и подпись. Заголовки блоков и явные суммы незначительны. Добавьте это вместе и получите 30Gb - с конфиденциальной транзакцией и скрытым графиком транзакций!

----- Вопросы и интуиция -----

Вот несколько вопросов, которые с тех недель мне снились сны, и я проснулся с потом. Но на самом деле это нормально.

В. Если вы удалите выходные данные транзакции, пользователь не сможет проверить диапазон и, возможно, будет создана отрицательная сумма.

О. Это нормально. Для проверки всей транзакции все отрицательные суммы должны быть уничтожены. Пользователь имеет защиту SPV только в том случае, если в прошлом не было незаконной инфляции, но пользователь знает, что _в этот раз_ никакой инфляции не произошло.

В. Если вы удалите входные данные, могут произойти двойные расходы.

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

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

----- Будущие исследования -----

Вот некоторые вопросы, на которые я не могу ответить на момент написания этой статьи.

1. Какая поддержка скриптов возможна? Нам нужно было бы перевести операции скрипта в какую-то дискретную информацию логарифма.

2. Мы требуем, чтобы пользователь проверил все значения k * G, когда на самом деле все, что нужно, это то, что их сумма имеет вид k * G. Вместо использования подписей есть еще одно доказательство дискретного логарифма, который можно объединить?

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

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

[1] https://people.xiph.org/~greg/confidential_values.txt

[2] https://bitcointalk.org/index.php?topic=279249.0

[3] https://cryptonote.org/whitepaper.pdf

[4] https://eprint.iacr.org/2015/1098.pdf

[5] https://download.wpsoftware.net/bitcoin/wizardry/horasyuanmouton-owas.pdf

[6] http://blockstream.com/sidechains.pdf

[7] http://fr.harrypotter.wikia.com/wiki/Sortilège_de_Langue_de_Plomb

[8] https://bitcointalk.org/index.php?topic=281848.0