Permalink
Branch: master
Find file Copy path
433 lines (305 sloc) 36.3 KB

Введение в МимблВимбл и Grin

На других языках: English, 简体中文, Español, Nederlands, Русский, 日本語, Deutsch, Portuguese.

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

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

Основными целями и характеристиками Grin являются:

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

Косноязычие Для Всех

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

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

Немного Эллиптических Кривых

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

Эллиптическая Кривая это просто большое множество точек, которые мы назовём C. Эти точки можно складывать, вычитать или умножать на целые числа (так же называемые скалярами). Пусть k является целым числом, тогда, используя скалярное умножение, мы можем вычислить k*H, что так же является точкой на кривой C. Пусть дано другое целое число j, тогда мы также можем вычислить (k+j)*H, что равняется k*H + j*H. Сложение и скалярное умножение на Эллиптической Кривой удовлетворяет свойствам коммутативности и ассоциативности сложения и умножения:

(k+j)*H = k*H + j*H

В Эллиптической Криптографии, если мы выберем большое значение k как закрытый ключ, тогда произведение k*H станет соответствующим открытым ключом. Даже если кто-то знает значение открытого ключа k*H, вычисление k близко к невозможному (другими словами, несмотря на тривиальность умножения, деление точек Эллиптической Кривой является крайне сложным).

Предыдущая формула (k+j)*H = k*H + j*H, где k и j хранятся в тайне, показывает, что открытый ключ может быть получен путём сложения двух закрытых ключей и является идентичным сложению двух соответствующих открытых ключей. Например, в Биткоин работа Детерминистических Иерархичных (HD wallets) кошельков всецело основана на этом принципе. МимблВимбл и Grin тоже используют это свойство.

Создание Транзакций в МимблВимбл

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

Проверка транзакций МимблВимбла опирается на два основных свойства:

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

Далее будет рассказано, как вычисляется баланс кошелька, проверяется владение, образуется "сдача" и будет показано, как перечисленные выше свойства достигаются.

Баланс

Основываясь на свойствах Эллиптических Кривых (ЭК), некто может сокрыть количество отправляемых монет в транзакции.

Пусть v это значение входа или выхода транзакции и H это Эллиптическая Кривая, тогда мы можем просто подставить значение v*H вместо v в транзакцию. Это работает благодаря тому, что используя операции на Эллиптической Кривой, мы сможем удостовериться, что сумма выходов транзакции равняется сумме её входов:

v1 + v2 = v3  =>  v1*H + v2*H = v3*H

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

Однако, количество пригодных для использования количеств монет конечно и злоумышленник может попытаться угадать передаваемое количество монет путём перебора. Кроме того, знание v1 (например из предыдущей транзакции) и конечного значения v1*H, раскрывает значения всех выходов всех транзакций, которые используют v1. Из-за этого мы введём вторую Эллиптическую Кривую G (на самом деле G это просто ещё один генератор группы, образованной той же самой кривой H) и некий закрытый ключ r используемый как фактор сокрытия.

Таким образом, значения входов и выходов транзакции могут быть выражены как:

r*G + v*H

Где:

  • r закрытый ключ, используемый как фактор сокрытия, G это Эллиптическая Кривая и произведение r*G это открытый ключ для r на кривой G.
  • v это значение входа или выхода транзакции, а H это другая ЭК.

Опираясь на ключевые свойства ЭК, ни v ни r не могут быть вычислены. Произведение r*G + v*H называется Обязательство Педерсена.

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

  • vi1 и vi2 это входы.
  • vo3 это выход.

Такие, что:

vi1 + vi2 = vo3

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

(ri1*G + vi1*H) + (ri2*G + vi2*H) = (ro3*G + vo3*H)

Которое, как следствие, требует, чтобы:

ri1 + ri2 = ro3

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

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

Владение

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

Алиса отправляет вам 3 монеты и, чтобы сокрыть количество, вы выбрали 28 как ваш фактор сокрытия (заметим, что на практике фактор сокрытия, будучи закрытым ключом, является очень большим числом). Тогда где-то в блокчейне должен быть следующий выход (UTXO), доступный для траты только вами:

X = 28*G + 3*H

Сумма X является видимой для всех, а значение 3 известно только вам и Алисе. Ну а число 28 известно только вам.

Чтобы передать эти 3 монеты снова, протокол требует, чтобы число 28 было каким-то образом раскрыто. Чтобы показать принцип работы, допустим, что вы хотите передать те же 3 монеты Кэрол. Тогда вам нужно создать простую транзакцию, такую, что:

Xi => Y

Где Xi это выход, который тратит ваш вход X, а Y это выход для Кэрол. Не существует способа создать такую транзакцию без знания вашего закрытого ключа 28. Разумеется, если Кэрол решит принять монеты из этой транзакции, ей нужно будет узнать как значение вашего закрытого ключа, так и значение, которое этой транзакцией переводится. Таким образом:

Y - Xi = (28*G + 3*H) - (28*G + 3*H) = 0*G + 0*H

Проверяя, что всё свелось к нулю, мы в очередной раз убедимся, что новых монет создано не было.

Но постойте-ка! Теперь вы знаете значение закрытого ключа из выхода Кэрол (которое, в этом случае, должно быть такое же, как и у вас, чтобы свести сумму в ноль) и тогда вы можете украсть деньги у Кэрол назад!

Для решения этой проблемы, Кэрол использует закрытый ключ, который выбрала сама. Например, она выбрала 133, тогда в блокчейн будет записано:

Y - Xi = (113*G + 3*H) - (28*G + 3*H) = 85*G + 0*H

Эта сумма (транзакция) больше не сводится к нулю и мы имеем избыточное значение на G (85), которое является результатом сложения всех факторов сокрытия. Но из-за того, что произведение 85*G будет являться корректным открытым ключом на ЭК G с приватным ключом 85, для любого x и y, только если y = 0, сумма x*G + y*H будет являться открытым ключом на G.

Всё что нужно, это проверить, что (Y - Xi) - валидный открытый ключ на кривой G и участники транзакции совместно обладают приватным ключом (85 в случае транзакции с Кэрол). Простейший способ достичь этого, это если потребовать создавать некую подпись избыточного значения (85), которая будет удостоверять, что:

  • Участники транзакции совместно знают закрытый ключ, и
  • Сумма выходов транзакции минус сумма входов, равняется нулю (потому что только валидный открытый ключ будет удовлетворять этой подписи)

Эта подпись, прикрепляемая к каждой транзакции, совместно с некоей дополнительной информацией (например комиссиями майнеров) называется ядром транзакции и должна проверяться всеми валидаторами.

Некоторые Уточнения

Этот раздел уточняет процесс создания транзакций, обсудив то, как образуется "сдача" и требования для доказательств неотрицательности значений. Ничего из этого не требуется для понимания МимблВимбла и Grin, так что если вы спешите, можете спокойной переходить к разделу Всё Вместе.

Сдача

Допустим вы хотите отправить 2 монеты Кэрол из трёх монет, которые вы получили от Алисы. Чтобы это сделать, вы отправите остаток из 1 монеты назад к себе в качестве сдачи. Для этого создайте другой закрытый ключ (например 12) в качестве фактора сокрытия, чтобы защитить ваш выход сдачи. Кэрол использует свой закрытый ключ как и ранее.

Выход для сдачи:     12*G + 1*H
Выход для Кэрол:    113*G + 2*H

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

(12*G + 1*H) + (113*G + 2*H) - (28*G + 3*H) = 97*G + 0*H
Доказательства Интервала

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

Например, можно создать транзакцию со входом в 2 монеты и выходами 5 и -3 монет и всё равно получить хорошо сбалансированную транзакцию, согласно формулам выше. Такие случаи будет трудно обнаруживать, поскольку даже если x отрицательно, соответствующая точка x*H на ЭК является неотличимой от любых других.

Для решения этой проблемы МимблВимбл применяет другую криптографическую идею, называемую range proofs: доказательство того, что число находится в заданном интервале, не раскрывая самого числа. Не вдаваясь в детали, скажем, что достаточно знать, что для любой суммы r.G + v.H мы можем создать такое доказательство, которое покажет, что v больше нуля и не переполняется.

Так же важно то, что для создания корректного доказательства для примера выше, оба значения 113 и 28, использующиеся для создания и подписывания избыточного значения должны быть известны. Причину этого, совместно с более детальным описанием range proof-ов можно найти в публикации о range proof-ах.

Всё Вместе

Транзакция МимблВимбла включает следующее:

  • Набор входов, которые указывают и тратят набор выходов других транзакций.
  • Набор новых выходов, который включает:
    • Количество монет и фактор сокрытия (который является просто новым приватным ключом), умноженный на эллиптическую кривую, что даёт в сумме r.G + v.H.
    • Доказательство того, что v не является отрицательным (range proof).
  • Комиссия транзакции в открытом виде.
  • Подпись, вычисленная путём использования избыточного значения (суммы всех выходов и комиссии за вычетом суммы входов) и использования этого значения в качестве приватного ключа.

Блоки и Состояние Цепочки

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

Формат блоков МимблВимбла привносит дополнительную идею, называемую прорезанием, благодаря которой блокчейн МимблВимбла получает:

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

Агрегирование Транзакций

Напомним, что транзакция состоит из:

  • Набора входов, которые тратят набор предыдущих выходов.
  • Набора новых выходов (Обязательств Педерсена).
  • Ядра транзакции, состоящего из:
    • Избыточного значения (Обязательство Педерсена для нуля).
    • Подпись транзакции, использующая избыточное значение как ключ.

Транзакция подписывается и подпись включается в ядро транзакции. Подпись генерируется с использованием избытка ядра в качестве открытого ключа, доказывая, что транзакция сводится к нулю.

(42*G + 1*H) + (99*G + 2*H) - (113*G + 3*H) = 28*G + 0*H

Открытый ключ в этом примере это 28*G.

Для любой корректной транзакции мы можем сказать, что (игнорируя комиссию для простоты):

сумма(выходы) - сумма(входы) = избыток_ядра

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

сумма(выходы) - сумма(входы) = сумма(избытки_ядер)

Простыми словами, с блоками МимблВимбла можно работать точно так же, как и с транзакциями МимблВимбла.

Смещения Ядер

Но есть небольшая проблема с блоками МимблВимбла и транзакциями, описанными выше. Является возможным (в некоторых случаях довольно просто) воссоздать накопленные транзакции из блока. Становится очевидным, что это очень плохо сказывается на приватности. Такая проблема является случаем проблемы "подмножества": если дано множество входов, выходов и ядер, подмножество их можно собрать в корректную транзакцию.

Например, даны две транзакции:

(вход1, вход2) -> (выход1), (ядро1)
(вход3) -> (выход2), (ядро2)

Мы можем агрегировать их в одну единую транзакцию:

(вход1, вход2, вход3) -> (выход1, выход2), (ядро1, ядро2)

Довольно просто попробовать все возможные перестановки для восстановления одной из транзакций (чтобы сумма была нулём):

(вход1, вход2) -> (выход1), (ядро1)

Теперь мы знаем, что всё остальное можно использовать для восстановления другой корректной транзакции:

(вход3) -> (выход2), (ядро2)

Для предотвращения этого мы включим смещение ядра в каждое ядро транзакции. Это фактор сокрытия (закрытый ключ), который нужно добавлять к избытку ядра:

сумма(выходы) - сумма(входы) = избыток_ядра + смещение_ядра

Когда мы накапливаем (агрегируем) транзакции в блок, мы храним одно накопленное значение смещения в заголовке блока. Теперь у нас есть единственное смещение, которое невозможно будет разбить по отдельным смещениям ядер и транзакции больше нельзя будет восстановить:

сумма(выходы) - сумма(входы) = сумма(избыток_ядра) + смещение_ядра

Мы "разделим" ключ k в сумму k1+k2 в ходе создания транзакции. Для ядра транзакции (k1+k2)*G мы оставляем открытыми k1*G (избыток) и k2 (смещение) и подписываем транзакцию используя k1*G как раньше. В ходе сборки блока мы можем просто просуммировать смещения ядер для создания одного агрегированого смещения, покрывающего все транзакции в блоке. Смещения каждой отдельно взятой транзакции теперь невозможно восстановить.

Прорезание

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

I1(x1) --- O1
        |- O2

I2(x2) --- O3
I3(O2) -|

I4(O3) --- O4
        |- O5

Можно обнаружить следующие два свойства:

  • Внутри этого блока некоторые выходы напрямую тратятся некоторыми из входов (I3 тратит O2 и I4 тратит O3).
  • Структура каждой транзакции не имеет особого значения. Так как все транзакции суммируются в ноль, сумма всех входов и выходов должна быть нулевой.

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

I1(x1) | O1
I2(x2) | O4
       | O5

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

Блок строится из:

  • Заголовка блока.
  • Списка входов, оставшихся после прорезания.
  • Списка выходов, оставшихся после прорезания.
  • Одно смещение ядра, защищающее блок целиком.
  • Ядра транзакций, содержащие для каждой транзакции:
    • Открытый ключ r*G, полученный из суммирования всех обязательств.
    • Подпись, сгенерированная из избыточного значения.
    • Комиссия.

Организованные таким образом блоки МимблВимбла могут предложить исключительные гарантии приватности:

  • Промежуточные транзакции (прорезанные) представляются только их ядрами.
  • Все выходы выглядят одинаково: просто очень большие числа, которые невозможно отличить друг от друга. Если кто-то захочет убрать или цензурировать один из выходов, ему придётся убрать их все.
  • Структура транзакций уничтожается, скрывая информацию о том, какой выход передаёт монеты какому входу.

И, несмотря на всё это, данная схема всё ещё корректно валидируется!

Прорезание До Конца

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

Обобщая, мы можем заключить, что состояние цепочки (за вычетом заголовков) в любое время может быть сведено к следующей информации:

  1. Общее количество монет, созданное майнингом цепочки.
  2. Полный набор непотраченых выходов транзакций.
  3. Ядра каждой из транзакций.

Информацию для первого пункта мы можем получить просто из высоты (расстояние от генезиса) блока. А, в свою очередь, непотраченые выходы и ядра транзакций довольно компактны.

Это приводит нас к двум важным следствиям:

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

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

Заключение

В этом документе мы осветили основные принципы, лежащие в основе блокчейна МимблВимбла. Используя свойства операции сложения над Эллиптическими Кривыми мы способны создавать транзакции, которые являются абсолютно непрозрачными, но и в то же время могут быть проверены на корректность. Обобщая те же самые свойства с транзакций на блоки, мы можем значительно уменьшить объем хранимых данных, тем самым открывая дорогу для масштабируемости и быстрого подключения новых участников к сети.