Zerocoin - анонимная распределенная система электронных денег от Bitcoin

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 18:49, 20 декабря 2015.
Zerocoin - анонимная распределенная система электронных денег от Bitcoin


ZerocoinOakland.png
Авторы Ian Miers [@: 1]
Christina Garman[@: 2]
Matthew Green[@: 3] and
Aviel D. Rubin[@: 4]
Опубликован 2013 г.
Сайт Johns Hopkins University Information Security Institute
Перевели Alexey Vasyunin
Denis Babarykin
Год перевода 2015 г.
Скачать оригинал


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

Введение

Цифровые валюты имеют длинную академическую родословную. Однако ни одна система из научной лекции не имеет широкого применения. Bitcoin, с другой стороны, является жизнеспособной цифровая валюта с рыночной капитализацией на сумму более чем $100 миллионов [1] и от $2 до $5 миллионов долларов в транзациях в день [2]. В отличие от многих предлагаемых цифровых валют, Bitcoin полностью децентрализована и не требует центральный банк или орган. Вместо этого, его безопасность зависит от распределенной архитектуры и двух предположений: большинство его узлов подлинные, основное доказательство правильности работы в том, что он может сдерживать атаки Sybil. Как следствие, Bitcoin не требует ни правовых механизмов для выявления и наказания двойных расходов, ни доверенных участников, чтобы выбрать, контролировать или охранять. Эта распределенная структура, скорее всего, отвечает за успех Bitcoin, но это имеет цену: все транзакции открыты и проводятся между криптографически связанными псевдонимами.

В то время как сравнительно мало научных работ рассмотрели влияние на конфиденциальность структуры Bitcoin [2], [3], предварительные результаты не обнадеживают. В одном примере исследователям удалось проследить расходование 25000 Bitcoin'ов, которые якобы украли в 2011 году [3], [4]. Хотя отслеживание украденных монет могут показаться безобидным, отметим, что подобные методы могут также применяться для отслеживания конфиденциальных транзакций, тем самым нарушая конфиденциальность пользователей. Кроме того, есть основания полагать, что сложные результаты из других областей (например, усилия по деанонимизации данных социальной сети с помощью сетевой топологии[5]) скоро будет применяться для график транзакций Bitcoin.

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

Сообщество Bitcoin в целом признает слабые стороны валюты в отношении конфиденциальности. К сожалению, доступные смягчение весьма ограничены. Самая распространенная рекомендация - использовать прачечную службу, которая обменивает биткоины различных пользователей. Некоторые из них используются сегодня для коммерческих операций[6], [7]. Эти сервисы, однако, имеют серьезные ограничения: операторы могут украсть средства, отслеживать денежные операции, или просто выйти из бизнеса, забрав средства пользователей с собой. Возможно, в знак признания этих рисков, многие сервисы предлагают короткие периоды для обмена, которые приводят к минимальным объемам транзакций и, следовательно, ограниченной анонимности.

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

Мы не первые предложили методы для решения проблем конфиденциальности в Bitcoin. Однако общая проблема многих протоколов электронной наличности является то, что они полагаются принципиально на доверенного источника валюты, "банк", который создает электронные "монеты", используя слепую схему. Одно решение (безуспешно с Bitcoin [8]) - просто создать такого участника. Кроме того, можно распространить ответственность между группой узлов с использованием порога криптографии. К сожалению, оба эти решения вводят точки отказа и кажутся несовместимыми с сетевой моделью Bitcoin, которая состоит из многих ненадежных узлов, которые обычно входят и выходят из. Более того, проблема выбора долгосрочных доверенных участников, особенно в серой нормативно-правовая зоне Bitcoin является, кажется, главным препятствием на пути принятия денег. Zerocoin устраняет необходимость такого источника монет, позволяя индивидуальным клиентам Bitcoin создавать свои собственные монеты, если у них есть достаточно классических биткоинов для этого.

Рисунок 1. Два примера блока цепей. Цепь (a) показывает обычную историю транзакций Bitcoin, каждая транзакция связана с предыдущей транзакцией. Цепь (b) показывает цепь Zerocoin. Связь между источником и тратой (пунктирная линия) не может быть определен из данных цепи блока.

Соображения, лежащие в основе конструкции. Чтобы понять что лежит в основе Zerocoin, рассмотрим следующий пример протокола. Представим, что все пользователи разделяют доступ к физическая доске. Чтобы отчеканить zerocoin фиксированного значения в $ 1, пользователь Алиса сначала создает случайное число монет S, потом фиксирует число S с использованием надежной цифровой схемы обязательств. Результирующее обязательство - это монета, обозначенная C, которая может только быть открытой случайным числом r, чтобы раскрыть последовательное число S. Алиса прикрепляет C на открытую доску объявлений вместе $1 физической валюты. Все пользователи примут C, если она правильно структурирована и несет правильную валютную сумму.

Чтобы воспользоваться своей монетой C, Алиса сначала сканирует доску, чтобы получить набор допустимых обязательств , которые были опубликованы всеми пользователями в системе. Затем она производит неинтерактивное доказательство с нулевым разглашением для следующих двух утверждений: (1) она знает , (2) она знает скрытое значение r такое, что обязательство C открывает S. На глазах у других, Алиса, используя маскировку, чтобы скрыть свою личность, отправляет операцию "потратить", содержащую Остальные пользователи проверяют доказательство и проверяют, что S до этого не появлялась в любой другой операции "потратить". Если эти условия выполнены, пользователи позволяют Алисе забрать $1 из любого положения на доске объявлений; иначе ее операцию отвергают и препятствуют сбору валюты.

Этот простой протокол достигает некоторых важных целей. Во-первых, отчеканенные монеты Алисы не могут быть связаны с ее полученными средствами: чтобы связать монеты C с серийным номером S, используемым в ее выводе, надо либо знать r, или непосредственно знать, о каких монетах Алиса доказала знания, ни один из которых не открывается доказательством. Таким образом, даже если первоначальный долларовый счет был запятнан для распознавания (например, он был использован в спорной сделке), он не может быть привязан к новому долларовому счету Алисы. В то же самое время, если обязательство и доказательство с нулевым разглашением безопасны, тогда Алиса не может два раза потратить любую монету без повторного использования серийного номера S и быть распознанной участниками сети.

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

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

Конечно, даже при интеграции с блоком цепи Bitcoin, протокол выше, имеет еще один практическую задачу. Конкретно, сложно эффективно доказать, что обязательство C в множестве . Решение - доказать дизъюнкцию К сожалению, такое доказательство имеет размер O(N), что делает непрактичным для всех малых значений N.

Наш второй вклад - решение этой проблемы, создавая новую конструкцию с доказательствами, которые не растут линейно с ростом N. Вместо указания дорогого доказательства "Или", мы используем "открытый" односторонний аккумулятор, чтобы уменьшить размер этого доказательства. Односторонние аккумуляторы [9], [10], [11], [12], [13], впервые предложенные Беналохом и де Маре [9], позволяют участникам объединить много элементов в структуру данных постоянного размера, эффективно доказывая, что одно особое значение содержится в множестве. В нашей конструкции сеть Bitcoin вычисляет аккумулятор A по обязательствам , вместе с соответствующие статус свидетелей для каждого элемента множества. Транжире нужно только доказать знание одного такого свидетеля. На практике это может снизить стоимость доказывания транжиры до или до постоянного размера.

Наше приложение требует специфических свойств от аккумулятора. При отсутствии надежных лиц аккумулятор и связанные с ним свидетели должны быть публично вычислимы и верифицируемы (хотя мы желаем смягчить это требование, чтобы включать в себя одну доверенную фазу установки, в которых генерируются параметры). Более того, аккумулятор должен привязывать вычисляющего участника к значениям в множестве. Аккумулятор должен поддерживать эффективных неинтерактивных свидетелей. К счастью, такие аккумуляторы существуют. Мы используем конструкцию, основанную на сильном RSA аккумуляторе Каменищ и Лисянской [11], который сам основан на аккумуляторе Барика и Фитзмана, [10] Беналоха и де Маре[9].

План этой работы. Остаток этой работы посвящен следующему. В разделе 2 мы предоставляем краткие технический обзор протокола Bitcoin. В разделе 3 мы формально определяем понятие электронной валюты и предоставляем корректность и безопасность требований для такой системы. В разделе 4 мы даем реализацию нашей схемы, основанной на стандартных криптографических предположениях, включая проблему дискретного логарифма и сильного RSA. В разделах 5, 6, 7 мы описываем, как мы интегрировали нашу электронную валюту в протокол Bitcoin, обсуждаем безопасность и предоставленную анонимность, детальные экспериментальные результаты, показывающие, что наше решение практически выгодно.

Обзор Bitcoin

В этом разделе мы предоставляем краткий обзор протокола Bitcoin. Для более детального описания мы ссылаемся не оригинальную спецификацию Накамото [14] или в краткости Барбера и других. [2].

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

Bitcoin клиенты соревнуются для определения того, какой узел будет создавать следующий каноничный блок. Это соревнование требует, чтобы каждый узел решил доказательство работы, основанное на определении SHA-256 прообразов, особенно блок B такой, как SHA256(SHA256(B)) = . Значение выбирается голосом периодической сети, чтобы гарантировать, что в среднем блок создается каждые 10 минут. Когда клиент создает верное решение, процесс называется добычей, майнингом, он транслирует новый блок на все узлы в системе. Если блок верный (например, все операции проверяются и верное доказательство работы привязывает блок к цепи до сих пор), тогда к новому блоку получают доступ, когда голова цепи блока. Процессы могут повторяться.

Bitcoin предоставляет 2 отдельных стимула для пиров, чтобы генерировать новые блоки. Во-первых, успешно сгенерировав новый блок (который требует затрат на вычисление) право создателя на вознаграждение, в настоящее время составляет 25 BTC. Во-вторых, узлы, которые генерируют блоки, которым дано право собирать плату операций из каждой операции из каждой операции, которые они включают. Плата определятся автором (через майнеры можно исключить операции с недостаточной платой).

Операции Bitcoin. Операции Bitcoin состоят из набора выводов и вводов. Каждый вывод представлен (a, V), где a - это количество, обозначенное в Сатоши (один биткоин = Сатоши), и V - это спецификация того, кто авторизован, чтобы проводить этот вывод. Эта спецификация, обозначенная scriptPubKey, дана в Bitcoin скрипте, основанный на стеке не тьюринго-полный язык, похожия на Форт.

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

Вводы транзакций - просто ссылки на вывод предыдущей транзакции, так же, как и предыдущий скрипт, scriptSig, с кодом и данными, которые при объединении с scriptPubKey вычисляет верно. Транзакции coinbase, которые начинают каждый блок и платят своему создателю, не включают ввод транзакции.

Чтобы послать d биткоинов Бобу, Алиса встраивает хеш публичного ключа Боба ECDSA , количество d, и некоторые скриптовые инструкции в scriptPubKey как один вывод транзакции, чьи ссылаемые общий ввод по крайней мере d биткоинов (смотрите Рисунок 2). Так как лишний ввод оплачивается как плата транзакции на узел, который включает его в блок, Алиса обычно добавляет второй вывод, оплачивая изменения для себя. Когда транзакция распространяется по сети и включена в блок, биткоины принадлежат Бобу. Однако Бобу следует только рассматривать монеты по крайней мере ссылки на пять последующих блоков этого блока. Боб может потратить эти монеты в транзакции, ссылаясь на нее как ввод, включая в scriptSig сигнатуру на претендующую транзакцию под и открытым ключом .

Анонимность. Анонимность не была одной из целей проектирования Bitcoin [3], [14], [15]. Bitcoin предоставляет только псевдоанонимность через использование Bitcoin идентичностей (открытые ключи или их хеши), которые пользователь Bitcoin может сгенерировать неограниченное число. Много Bitcoin клиентов монотонно генерируют новые идентичности, чтобы сохранить конфиденциальность пользователя.

Несмотря на цели проектирования Bitcoin, пользовательская база Bitcoin кажется желающей пройти через значительные усилия, чтобы сохранять свою анонимность, включая риски своими деньгами и платой транзакционных сборов. Одна иллюстрация этого - это существование прачечных, которые (за плату) будут смешивать различные пользовательские средства в группы, чтобы трудно их отследить [2], [6], [7]. Так как такие системы от пользователей доверять прачечным к обоим (a) не записывать, как смесь сделана и (b) вернуть пользователям деньги, которые они положили, использование этих систем включает некий риск.

Децентрализованная денежная система

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

Обозначение. Пусть λ представляет регулируемый параметр безопасности, пусть poly(·) представляет некоторую полиномиальную функцию, и пусть ν(·) представляет незначительную функцию. Мы используем C, чтобы определить множество допустимых значений монет.

Определение 3.1 (Децентрализованная схема электронной валюты): Децентрализованная схема электронной валюты состоит из кортежа возможных случайных алгоритмов (Setup, Mint, Spend, Verify).

  • . На входе параметр безопасности, выход - множество глобальных открытых параметров params и описание множество C.
  • . На входе параметры params, выход - монета , как и люк skc.
  • . Данные params, монета c, ее люк skc, некоторые транзакционные строки , и произвольное множество монет , вывод монеты тратит транзакцию, состоящую из доказательства и серийного номера S, если . Иначе вывод .
  • . Данные params, доказательство π, серийный номер S, транзакционная информация R, и множество монет , вывод 1, если и верные. Иначе вывод 0.

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

Каждая монета создается, используя алгоритмы случайного майнинга. Серийный номер S - это уникальное значение, выпущенное в течение траты монет и разработанные, чтобы предотвратить любого пользователя от траты тех же самых монет дважды. Мы формализуем корректность и свойства безопасности децентрализованной схемы электронной валюты. Каждый вызов алгоритма Spend может включать произвольную строку R, которая хранит специфичную для транзакции информацию.

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

   

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

Определение 3.2 (Анонимность): Схема децентрализованной электронной валюты удовлетворяет требованию анонимности, если вероятностный противник имеет незначительное преимущество в следующем эксперименте.


   Anonymity
        Setup()
       For : () ← Mint()
       
        Spend()
       Output: 


Мы определяем преимущество приведенной выше игре как |[b = b0] − 1/2|.

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

Наше определение напоминает определение еще одной подделки, широко используемое для слепых подписей. Мы предоставляем атакующему коллекцию действительных монет и оракул , который она может использовать, чтобы потратить любую из них. должно произвести m монет и m+1 действительную транзакцию траты такую, что ни одна транзакция не дублирует серийный номер или изменяет транзакцию, созданную честным оракулом.

Определение 3.3 (Сбалансированность): Схема децентрализованной электронной валюты Π = (Setup, Mint, Spend, Verify) удовлетворяет свойству сбалансированности, если ∀N ≤ poly(λ) для каждого вероятностного неприятеля имеет незначительное преимущество в следующем эксперименте.


   Balance() 
        Setup()
       For  Mint()
       Output: 


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

Мы говорим, что побеждает (например, она производит больше монет, отчеканен), если , где :

  • Verify(.
  • .
  • .
  • появляется только в одном кортеже из .

Мы определяем преимущество как вероятность, что побеждает в привиденной выше игре.

Децентрализованная электронная валюта из сильного RSA

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

Криптографические строительные блоки

Доказательства с нулевым знанием и подписи знаний. Наши протоколы используют доказательства с нулевым уровнем знания, которые могут быть инстанцированы, используя технику Шнора [16], с расширениями, [17], [18], [19], [20]. Мы преобразовываем их в неинтерактивные доказательства, применяя эвристику Фиата-Шамира[21]. Позже мы ссылаемся на результирующие неинтерактивные доказательства как подписи знания, как определено в [22].

Когда ссылаемся на эти доказательства, мы будем использовать систему обозначений Камениш и Стадлер [23]. Например, обозначает неинтерактивное доказательство нулевого знания элементов и , которые удовлетворяют как , так и . Все не заключенные в () значения полагаю известными верификатору. Аналогично расширение показывает подпись знания в сообщении m.

Аккумуляторы. Наша конструкция использует аккумуляторы, основанные на сильном RSA. Аккумулятор, который мы используем, был впервые предложен Беналохом и де Маре [9] и позже улучшен Бариком и Фитзманом [10], Камених и Лисянской [11]. Мы опишем аккумулятор, используя следующие алгоритмы:

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

Описание, привиденное выше, использует полное вычисление A. Камениш и Лисянская [11] заметили, что аккумулятор может быть также постепенно обновлен, к данному существующему аккумулятору возможно добавить элемент и получить новое значение аккумулятора путем вычисления . Мы активно используем эту оптимизацию в нашей практической реализации.

Камениш и Лисянская [11] показывают, что аккумулятор удовлетворяем сильному свойству устойчивости к столкновениям, если предположение о сильном RSA твердо. Это гарантирует, что никакой вероятностный неприятель не может создать пару такую, что и AccVerify удовлетворено. Дополнительно они описывают эффективное доказательство с нулевым знанием, что зафиксированное значение находится в аккумуляторе. Мы преобразовываем его в неинтерактивное доказательство, используя преобразование Фиата-Шамира и ссылаемся на результирующее доказательство, используя следующее:

   

Конструкция

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

Опишем алгоритмы:

  • . На вход подается параметр безопасности,

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

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

  • . Данное доказательство , серийный номер , и множество монет , во-первых, вычисляем . Далее проверяем, что является is the вышеупомянутой подписью знания на , используя известные открытые значения. Если доказательство проверяет удачно, то вывод 1, иначе вывод 0.

Наш протокол предполагает процесс доверенной установки для создания параметров. Мы подчеркиваем, что люк аккумулятора не используется последовательно для процедуры Setup и поэтому может быть уничтожен сразу после генерации параметров. В качестве альтернатива можно использовать техники Сандера для генерации так называемых RSA UFOs для параметров аккумулятора без люка [24].

Анализ безопасности

Сейчас мы рассмотрим безопасность нашей конструкции.

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

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

Теорема 4.2: Если доказательство подписи озвучено в модели случайного оракула, проблема сильного RSA тяжелая, проблема дискретного логарифма тяжелая в , тогда удовлетворяет свойству сбалансированности.

Доказательство теоремы 4.2 включено в приложение А. Это доказательство основано на привязке свойств монетных обязательств так же, как и обоснованность, нековкость ZKSoK and устойчивость к столкновениям аккумулятора. Мы покажем, что недоброжелатель, который побеждает в игре сбалансированности с We show that an adversary who wins the Balance game with большим преимуществом, может быть использован или для нахождения столкновений в схеме обязательств (позволяя нам решить проблему дискретного логарифма) или найти столкновение в аккумуляторе (что приводит к решению сильного RSA).

Интеграция с Bitcoin

Хотя мы и дали в предыдущем разделе обзор нашего подхода, нам еще предстоит описать, как наши техники интегрировать с Bitcoin. В этом разделе мы поднимем вопросы, которые возникают, когда мы объединяем схему децентрализованной электронной валюты с протоколом Bitcoin.

Общий обзор нашего подхода является прямолинейным. Чтобы отчеканить zerocoin номинала , Алиса запускает runs и хранит безопасно. Она затем встраивает c в вывод Bitcoin транзакции, которая тратит классических биткоинов. Когда транзакция чеканки помещается в блочную цепь, включается в глобальный аккумулятор A, и к валюте нельзя получить доступ кроме как по Zerocoin трате, то есть она помещена в депозит.

Чтобы потратить c с Бобом, Алиса сначала создает частичную транзакцию ptx, которая ссылается на необъявленную транзакцию чеканки как на вход и включает открытый ключ Боба как вывод. Она затем обходит все допустимые транзакции чеканки в блочной цепи, собирает набор отчеканенных монет , запускает . В конце она завершает транзакцию встраиванием в scriptSig входа . Выход этой транзакции может также быть дальнейшей транзакцией чеканки Zerocoin — функция, которая может быть полезной, чтобы передавать значение между многими экземплярами Zerocoin (например, различным номиналом), работающими в той же самой блочной цепи.

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

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

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

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

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

Мы расширяем Bitcoin добавлением новых инструкций: ZEROCOIN_MINT. Создание зерокоина строит транзакцию с выходом, чей scriptPubKey содержит эту инструкцию и монету . Узлам, которые получают эту транзакцию, следует проверять, что хорошо сформированная монета. Чтобы потратить зерокоин, Алиса строит новую транзакцию, которая требует в качестве входа некоторую транзакцию для чеканки и имеет поле scriptSig, содержащее и ссылку на блок, содержащий аккумулятор, используемый в . Верификатор извлекает аккумулятор из ссылаемого блока и, используя его, проверяет трату так, как было описано ранее.

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

Сохранение состояния и побочные эффекты. Проверка зерокоина изменяет смысл Bitcoin: постоянное состояние Bitcoin определено только в понятиях транзакций и блоков транзакций. Более того, доступ к этом состоянию совершается через явную ссылка на хеш. Zerocoin, с другой стороны, из-за требования анонимности имеет дело с deals with экзистенциалами: монета является набором до этих пор отчеканенных монет, ее серийный номер еще не находится в наборе потраченных серийных номеров. Чтобы удовлетворить этим требованиям, мы вводим побочные эффекты в управление транзакциями Bitcoin. Обработка транзакции чеканки является причиной того, что монета накапливается как сторонний эффект. Обработка транзакции траты является причиной того, что серийный номер монеты добавляется в список потраченных серийных номером, находящийся у клиента.

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

Оптимизации доказательства. Доказательства создаются , превосходящей ограничение по размеру транзакции в 10 KB в Bitcoin. Хотя мы можем просто увеличить этот предел, это имеет 2 недостатка: (1) это кардинально увеличивает требования к хранилищу для Bitcoin, так как размер текущих транзакций находится между 1 и 2 KB, (2) это может увеличить нагрузку на память у клиентов, которые хранят транзакции в памяти.

В нашей реализации-прототипе мы храним наши доказательства в различных местах (простой сервер). Полная реализация может использовать распределенную хеш-таблицу или хранилище, основанное не на блок-цепочке в Bitcoin. Пока мы рекомендуем хранить доказательства в блочной цепочке, эти альтернативы не увеличивают хранилище, требуемое для блочной цепочки.

Предложения по оптимизации проверки доказательств

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

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

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

Ограниченная анонимность и безопасность

Серьезное беспокойство в сообществе Bitcoin вызывает потеря кошельков из-за плохой безопасности конечных точек. В обычном Bitcoin это приводит к краже монет [4]. Однако в Zerocoin это может позволить атакующему деанонимизировать транзакции Zerocoin, используя хранимые . Очевидное решение - безопасно удалять немедленно после того, как монета потрачена. К несчастью, это не приносит защиты, если хранится в некоторой более ранней точке.

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

Изменения кода

Для нашей реализации мы выбрали изменять bitcoind, оригинальный Bitcoin клиент на C++ с открытым исходным кодом. Это потребовало нескольких изменений. Во-первых, мы добавили инструкции в Bitcoin скрипт для чеканки и траты зерокоинов. Далее мы добавили типы транзакций и код для обработки этих новых инструкций так же, как и сохранение списка потраченных серийных номеров и аккумулятор. Мы использовали криптографический Фреймворк Charm [25], чтобы реализовать криптографические конструкции на Python, мы использовали Python Boost, чтобы вызывать этот код из bitcoind. Это включает некоторые накладные расходы относительно производительности, но это позволяет нам быстро создать прототип для реализации будущих конструкций.

Постепенное развертывание

Как описано выше, Zerocoin требует изменений в протоколе Bitcoin, которые должны быть совершены глобально: пока транзакции, содержащие новые инструкции будут проверяться обновленными серверами, они потерпят неудачу в проверке на старых узлах, потенциально заставляя сеть раскалываться, когда блок создается, что проверяет некоторые, но не все узлы. Хотя это не первый раз, когда Bitcoin столкнулся с этой проблемой, существует стратегия обновления типа флага дня [26], неясно, каково желание сообщества Bitcoin, чтобы повторить его. Таким образом, мы рассматриваем возможность постепенного развертывания.

Один способ - выполнить это, чтобы встроить описанный выше протокол как комментарии в стандартных скриптах Bitcoin. Для не Zerocoin узлов, эти данные фактически инертны, и мы можем использовать of поддержку подписи Bitcoin, чтобы определить, что такие зерокоины со встроенным комментарием достоверны, если подписаны подмножеством обрабатывающих узлов Zerocoin. Такие Zerocoin узлы могут анализировать комментарии и взимать транзакционные платежи для проверки согласно доказательствам, встроенным в комментарии, предоставляя стимул для больших узлов предоставить такие сервисы. Так как это только меняет механизм проверки для Zerocoin, свойство анонимности сохраняется как свойство баланса, если не более чем узлов Zerocoin nodes are вредоносные.

Некоторое внимание должно быть уделено, когда выбираем эти узлы, чтобы предотвратить атаку Sybil. Если мы требуем, что такой узел также создает блоки в блочной цепочке Bitcoin, у нас есть достойный сдерживающий фактор. Более того, так как любое злодеяние над этими узлами является легко обнаруживаемым (потому что они подписаны недостоверной транзакцией Zerocoin), третьи лица могут проверять эти узлы и потенциально хранить средства в депозите для предотвращения мошенничества.

Безопасность в реальном мире и выбор параметра

Анонимность Zerocoin

Определение 3.2 утверждает, что две данных чеканки Zerocoin и одна трата, невозможно сделать лучше, чем угадать, какая отчеканенная монета была потрачена. Иначе говоря, злоумышленник узнает из нашей схемы не больше, чем из наблюдения чеканок и трат некоторой идеальной схемы. Однако даже идеальная схема накладывает ограничения. Например, рассмотрим случай, где монет отчеканены, потом все монет последовательно тратятся. Если другая монета создается после этого, размер анонимного множества для следующей траты равен , не , так как ясно всем наблюдателям, что предыдущие монеты были использованы. Мы также подчеркиваем это, как и во многих системах анонимности, конфиденциальность может быть нарушена злоумышленником, который чеканит большую долю активных монет. Следовательно, нижнее ограничение на предоставленную анонимность - это число монет, отчеканенных честными участниками в промежутке времени между чеканкой монеты и ее тратой. Верхнее ограничение - общее число отчеканенных монет.

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

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

Параметры

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

  1. Размер группы Шнорра, используемой в обязательствах монет.
  2. Размер модуля RSA, используемого в аккумуляторе.
  3. , безопасность доказательств нулевого знания.

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

Одно из решений состоит в минимизации размера группы, объявив свежие параметры схемы обязательств периодически и заставляя старые зерокоины истекать, если не обмениваются на новые зерокоины, отчеканенные при новых значениях параметров. Так как все монеты, потраченные по сети во время , тратятся с текущими параметрами и все предыдущие монеты могут быть преобразованы в новые, это не уменьшает анонимность системы. Это, однако, требует от пользователей преобразовывать все зерокоины в свежие перед тем, как старые параметры истекают. Для нашей реализации мы выбрали использовать 1024-битные параметры в предположении, что параметры обязательств могут быть регенерированы периодически. Мы открываем вероятность расширений Zerocoin, которые могут включить более маленькие группы в разделе "Завершение и будущая работа".

RSA ключ аккумулятора. Так как создание нового аккумулятора требует или новой доверенной фазы установки, или созданием нового RSA UFO [24], мы не можем менять ключ очень часто. В результате аккумулятор является живущим долго, таким образом, нам на самом деле нужна долгосрочная безопасность. Поэтому мы предлагаем RSA ключ длиной в как минимум 3072 битов. Мы замечаем, что это не сильно влияет на размер монет, что, так как доказательство членства аккумулятора является эффективным, это не несет большой негативный эффект на размер доказательства траты траты всех монет. Хотя изменение ключа аккумулятора дорого, не нужно уменьшать анонимность системы, так как новые параметры быть использованы, чтобы накопить существующий набор монет и анонимизировать траты по всей истории.

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

Производительность

Чтобы проверить результаты, мы провели несколько экспериментов, используя измененную реализацию bitcoind, описанную в разделе 5. Мы провели наши эксперименты в тремя различными размерами параметров, где каждый соответствует длине модуля RSA : 1024 бита, 2048 битов, 3072 бита.

Рисунок 3. Производительность Zerocoin как функция размера параметра.

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

Все наши эксперименты были проведены на Intel Xeon E3-1270 V2 (3.50GHz процессоре с четырьмя ядрами с гиперсредингом) с 16 Гб оперативной памяти, 64-разрядную Ubuntu Server 11.04 с ядром Linux версии 2.6.38.

Микросхемы

Чтобы вычислить производительность наших алгоритмов Mint, Spend, и Verify в изоляции, мы провели серию микротестов, используя реализацию Charm (Python). Наша цель в этих экспериментах была предоставить прямую оценку производительность наших криптографических примитивов.

Экспериментальная установка. Одна задача в проведении наших микротестов - накопление монет в для сведетельства в или для глобального аккумулятора в обоих и . Это проблематично по двум причинам. Во-первых, мы не знаем, насколько большое будет на практике. Во-вторых, в нашей реализации аккумуляторы последовательно увеличиваются. Чтобы адресовать эти проблемы, мы выбрали разбить наши микротесты в два различных эксперимента. Первый эксперимент просто вычисляет аккумулятор для числа возможных размеров , изменяющихся от 1 до 50,000 элементов. Второй эксперимент измеряет время работы подпрограмм и с вычисленным до этого аккумулятором и свидетельством .

Мы провели наши эксперименты на одном потоке процессора, используя все три размера параметров. Все эксперименты были выполнены 500 раз, и данные результаты представляют среднее. Рисунок 3a показывает измеренные времена для вычисления монетных операций, рисунок 3b показывает размеры результирующего доказательства для каждого параметра безопасности, а рисунок 3c показывает результирующие времена для вычисления аккумулятора. Мы подчеркиваем, что накопление в нашей системе является последовательным, обычно за 200−500 транзакций в блоке (которые занимают в худшем случае 8 секунд), поэтому стоимость вычисления глобального аккумулятора погашается. Единственный раз, когда пользователь может накопить 50000 монет в одно время будет при генерации свидетельства для очень старого зерокоина.

Проверка блока

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

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

Экспериментальная установка. Чтобы измерить воздействие Zerocoin на проверку блока, мы измеряем, как долго требуется измененному клиенту bitcoind проверить загруженные извне тестовые блоки, содержащие 200, 400, и 800 транзакций, где 0, 10, 25, 75 или 100 процентов транзакций являются транзакциями Zerocoin (половина из которых являются чеканками, а половина - тратами). Мы повторяем этот эксперимент для всех параметров безопасности.

Наши тестовые данные состоят из двух блоков. Первый содержит чеканок Zerocoin, которые должны существовать для любых трат, чтобы встретиться. Второй блок - это наш тестовый вектор. Он содержит в случайном порядке трат монет Zerocoin в предыдущем блоке, чеканок Zerocoin, а - стандартные sendToAddress транзакции Bitcoin. Мы измеряем то, сколько времени требуется вызову processblock клиента bitcoind, чтобы проверить второй блок, содержащий смесь Zerocoin и классических транзакций Bitcoin. Для точности мы повторяем измерения 100 раз и усредняем результаты. Результаты представлены на рисунке 3d.

Обсуждение

Наши результаты показывают, что Zerocoin масштабирует за пределами транзакционных объемов Bitcoin. Хотя нам требуются значительные вычислительные ресурсы, проверка не угрожает работоспособности сети: даже с блоком, содержащим 800 транзакций Zerocoin — приблизительно удваивая средний размер блока Bitcoin — проверка требует менее пяти минут. Это происходит под неразумным предположением, что все транзакции вытеснены транзакциями Bitcoin. Мы можем масштабировать с хорошими результатами за пределами текущего среднего между 200 и 400 транзакциями на каждый блок [27], если транзакции Zerocoin не являются большинством транзакций в сети. Если мы предполагаем, что проверка масштабируется линейно, тогда мы можем поддержать 50% транзакций, смешанных с 350 транзакциями, в минуту (3500 транзакций на блок) и 10% смесь с 800 транзакциями в минуту (8000 на блок).

Один оставшийся вопрос заключается, в какой точке мы начинаем подвергаться риску того, что конфликты серийных номеров монет вызывают ошибочные двойные траты. Даже для наших самых маленьких серийных номеров — 160 битов — вероятность конфликта мала, а для серийного номера в 256 бит, используемого с аккумулятором в 3072 бита, вероятность конфликта в худшем случае равна шансам конфликта обычной транзакции Bitcoin, которая использует SHA-256 хеши.

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

Во-вторых, описанные выше данные не являются точной оценкой финансовой стоимости Zerocoin для сети: (a) это переоценка дополнительных усилий генерирующих узлов, когда происходит проверка предложенных блоков, так как на практике много транзакций в полученном блоке будут уже получены и проверены узлом, когда он попытается создать свой собственный вклад в блочную цепочку; (b) время выполнения - плохая мера в контексте Bitcoin, так как создатели обеспокоены текущей денежной операционной стоимостью; (c) так как добыча обычно проводится, используя GPU, чтобы уменьшить протяженность FPGA и ASIC, которые намного более эффективны в вычислении конфликтов хешей, стоимость обработки на CPU, измеренная здесь, незначительна.

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

Предыдущая работа

Электронная валюта и Bitcoin

Электронная валюта долгое время была темой исследования для криптографов. Многие криптографические системы электронной валюты сосредоточены на конфиденциальности пользователей и обычно предполагают существование банка. Схемы электронных валют разделяют на онлайн схемы, где пользователи имеют контакт с банком или реестром, и оффлайн схемы, где трата может происходить даже без соединения с сетью. Чаум представил первую онлайн криптографическую систему электронной валюты [28], основанную на подписях RSA, позже расширяя эту работу к оффлайн установке [29] деанонимизацией пользователей, которые совершают двойную трату. Много последующих работ улучшили эти методы, сохраняя требование доверенного банка: например, делая монеты делимыми[30], [31] и уменьшая размер кошелька[32]. Одно исключение для правила выше приходит от Сандера и Та-Шма [33], которые точно разработали альтернативную модель, которая напоминает наше предположение: центральный банк заменяется на хеш-цепочку и подписи с аккумуляторами. К несчастью, аккумулятор не был практичным, центральный участник был все еще необходим, а не существовало существующей системы, чтобы вычислить цепочку.

Первоначальная цель Bitcoin, с другой стороны, не анонимность. Она уходит корнями в неакадемическое предложение Вей Дая для распределенной валюты, основанной на решении вычислительных проблем [34]. В оригинальном предложении Дая любой может создать валюту, но все транзакции должны были разосланы всем клиентам. Второй вариант ограничивал создание и рассылку транзакции набору серверов, который использует Bitcoin. Это помеченное отличие от большинства, если не всех, других систем, так как не необходимости выбирать одного или более доверенных участников. Существует общее предположение, что большинство узлов Bitcoin честные, но любой может присоединить узел к сети Bitcoin, любой может получить граф транзакций. Обзор Bitcoin и некоторых его недостатков был представлен Барбером и другими в [2].

Анонимность

Многочисленные работы показали, что “псевдонимные” графы могут быть повторно определены даже под пассивным анализом. Нараянан и Шматиков [5] показали, что реальные социальные сети могут быть пассивно деанонимизированы. Аналогично Бекстром и другие [35] построили направленные атаки против анонимных социальных сетей, чтобы протестировать взаимоотношения между вершинами. Ранее Нараянан и Шматиков деанонимизировали пользователей в Netflix, используя данные из IMDB [36].

Bitcoin появился в 2009 и сейчас начинает получать критики от исследователей конфиденциальности. Методы деанонимизации были применены к Bitcoin даже при относительно малом размере в 2011 Рейдом и Харриганом [3]. Рон и Шамир исследовали общую структуру графа сети Bitcoin [1] после почти трехкратного расширения. В конце концов, мы приложили усилия, чтобы исследовать анонимность Bitcoin.

Завершение и дальнейшая работа

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

Наша работа оставила несколько проблем открытыми. Во-первых, хотя наша схема является рабочей, необходимость для доказательства двойного дискретного логарифма приводит к большим размерам доказательств и временам проверки. Мы предпочли бы схему как с меньшими доказательствами, так и большей скоростью. Это особенно важно, когда это приводит к уменьшению стоимости проверки третьими лицами транзакций Zerocoin. В криптографической литературе существует несколько обещающих конструкций, например, билинейные аккумуляторы, "ртутные обязательства" [12], [37]. Пока мы не смогли найти аналог нашей схемы, используя альтернативные компоненты, возможно, что дальнейшее исследование приведет к другим решениям. В идеале такое улучшение может производить замену для нашей существующей реализации.

Во-вторых, Zerocoin в настоящий момент получает как анонимность, так и безопасность относительно надежных криптографических предположений на стоимости значительно увеличенной вычислительной сложности и размерa. Как описано в разделе, анонимность относительно дешевая, эта стоимость вытекает из требования избегания подделок, проявляя себя по размеру монет и используемых доказательств.

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

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

Наконец, мы считаем, что дальнейшее исследование может привести к различным компромиссам между безопасностью, подотчетностью и анонимностью. Типичным для Bitcoin является то, что он может использоваться для отмывания денег в обход юридически обязательных требований к финансовой отчетности. Мы полагаем, что дополнительное модификации протокола (например, использование анонимных учетных [38]) может позволить пользователям поддерживать свою анонимность в то время как демонстрации соответствия требованиям отчетности.

Благодарности. Мы благодарим Стивена Чековай, Джорджа Данезиса, анонимных рецензентов за их полезные комментарии. Исследования в данной работе была частично поддержаны Управлением военно-морских исследований в соответствии с договором N00014-11- 1-0470, и DARPA и научно-исследовательской лабораторией ВВС (AFRL) в соответствии с контрактом FA8750-11-2-0211.

Авторы

  1. The Johns Hopkins University Department of Computer Science, Baltimore, USA. Email: imiers@cs.jhu.edu
  2. The Johns Hopkins University Department of Computer Science, Baltimore, USA. Email: cgarman@cs.jhu.edu
  3. The Johns Hopkins University Department of Computer Science, Baltimore, USA. Email: mgreen@cs.jhu.edu
  4. The Johns Hopkins University Department of Computer Science, Baltimore, USA. Email: rubin@cs.jhu.edu

Ссылки

  1. 1,0 1,1 D. Ron and A. Shamir, “Quantitative Analysis of the Full Bitcoin Transaction Graph,” Cryptology ePrint Archive, Report 2012/584, 2012, http://eprint.iacr.org/.
  2. 2,0 2,1 2,2 2,3 2,4 S. Barber, X. Boyen, E. Shi, and E. Uzun, “Bitter to better – how to make bitcoin a better currency,” in Financial Cryptography 2012, vol. 7397 of LNCS, 2012, pp. 399–414.
  3. 3,0 3,1 3,2 3,3 F. Reid and M. Harrigan, “An analysis of anonymity in the Bitcoin system,” in Privacy, security, risk and trust (PASSAT), 2011 IEEE Third Internatiojn Conference on Social Computing (SOCIALCOM). IEEE, 2011, pp. 1318–1326.
  4. 4,0 4,1 T. B. Lee, “A risky currency? Alleged $500,000 Bitcoin heist raises questions,” Available at http://arstechnica.com/, June 2011.
  5. 5,0 5,1 A. Narayanan and V. Shmatikov, “De-anonymizing social net- works,” in Security and Privacy, 2009 30th IEEE Symposium on. IEEE, 2009, pp. 173–187.
  6. 6,0 6,1 “Bitcoin fog company,” http://www.bitcoinfog.com/.
  7. 7,0 7,1 “The Bitcoin Laundry,” http://www.bitcoinlaundry.com/.
  8. “Blind Bitcoin,” Information at https://en.bitcoin.it/wiki/Blind Bitcoin Transfers.
  9. 9,0 9,1 9,2 9,3 J. Benaloh and M. de Mare, “One-way accumulators: a decentralized alternative to digital signatures,” in EUROCRYPT ’93, vol. 765 of LNCS, 1994, pp. 274–285.
  10. 10,0 10,1 10,2 N. Bari ́ c and B. Pfitzmann, “Collision-free accumulators and fail-stop signature schemes without trees,” in EUROCRYPT ’97, vol. 1233 of LNCS, 1997, pp. 480–494.
  11. 11,0 11,1 11,2 11,3 11,4 J. Camenisch and A. Lysyanskaya, “Dynamic accumulators and application to efficient revocation of anonymous creden- tials,” in CRYPTO ’02, 2002, pp. 61–76.
  12. 12,0 12,1 L. Nguyen, “Accumulators from bilinear pairings and appli- cations,” in Topics in Cryptology – CT-RSA 2005, 2005, vol. 3376 LNCS, pp. 275–292.
  13. J. Camenisch, M. Kohlweiss, and C. Soriente, “An accumulator based on bilinear maps and efficient revocation for anonymous credentials,” in PKC ’09, vol. 5443 of LNCS, 2009, pp. 481– 500.
  14. 14,0 14,1 S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system, 2009,” 2012. [Online]. Available: http://www.bitcoin.org/ bitcoin.pdf
  15. European Central Bank, “Virtual currency schemes,” Available at http://www.ecb.europa.eu/pub/pdf/other/ virtualcurrencyschemes201210en.pdf, October 2012.
  16. C.-P. Schnorr, “Efficient signature generation for smart cards,” Journal of Cryptology, vol. 4, no. 3, pp. 239–252, 1991.
  17. R. Cramer, I. Damg ̊ ard, and B. Schoenmakers, “Proofs of partial knowledge and simplified design of witness hiding protocols,” in CRYPTO ’94, vol. 839 of LNCS, 1994, pp. 174–187.
  18. J. Camenisch and M. Michels, “Proving in zero-knowledge that a number n is the product of two safe primes,” in EUROCRYPT ’99, vol. 1592 of LNCS, 1999, pp. 107–122.
  19. J. L. Camenisch, “Group signature schemes and payment systems based on the discrete logarithm problem,” Ph.D. dissertation, ETH Z ̈ urich, 1998.
  20. S. Brands, “Rapid demonstration of linear relations connected by boolean operators,” in EUROCRYPT ’97, vol. 1233 of LNCS, 1997, pp. 318–333.
  21. A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” in CRYPTO ’86, vol. 263 of LNCS, 1986, pp. 186–194.
  22. M. Chase and A. Lysyanskaya, “On signatures of knowledge,” in CRYPTO’06, vol. 4117 of LNCS, 2006, pp. 78–96.
  23. J. Camenisch and M. Stadler, “Efficient group signature schemes for large groups,” in CRYPTO ’97, vol. 1296 of LNCS, 1997, pp. 410–424.
  24. 24,0 24,1 T. Sander, “Efficient accumulators without trapdoor extended abstract,” in Information and Communication Security, vol. 1726 of LNCS, 1999, pp. 252–262.
  25. J. A. Akinyele, C. Garman, I. Miers, M. W. Pagano, M. Rushanan, M. Green, and A. D. Rubin, “Charm: A framework for rapidly prototyping cryptosystems,” To appear, Journal of Cryptographic Engineering, 2013. [Online]. Available: http://dx.doi.org/10.1007/s13389-013-0057-3
  26. [Online]. Available: https://en.bitcoin.it/wiki/BIP 0016
  27. [Online]. Available: http://blockchain.info/charts/n- transactions-per-block
  28. D. Chaum, “Blind signatures for untraceable payments,” in CRYPTO ’82. Plenum Press, 1982, pp. 199–203.
  29. D. Chaum, A. Fiat, and M. Naor, “Untraceable electronic cash,” in CRYPTO 88, 1990, vol. 403 of LNCS, pp. 319–327.
  30. T. Okamoto and K. Ohta, “Universal electronic cash,” in CRYPTO 91, 1992, vol. 576 of LNCS, pp. 324–337.
  31. T. Okamoto, “An efficient divisible electronic cash scheme,” in Crypt ’95, 1995, vol. 963 of LNCS, pp. 438–451.
  32. J. Camenisch, S. Hohenberger, and A. Lysyanskaya, “Compact e-cash,” in EUROCRYPT ’05, 2005, vol. 3494 of LNCS, pp. 566–566.
  33. T. Sander and A. Ta-Shma, “Auditable, anonymous electronic cash (extended abstract),” in CRYPTO ’99, vol. 1666 of LNCS, 1999, pp. 555–572.
  34. W. Dai. B-money proposal. [Online]. Available: http: //www.weidai.com/bmoney.txt
  35. L. Backstrom, C. Dwork, and J. Kleinberg, “Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography,” in Proceedings of the 16th international conference on World Wide Web, ser. WWW ’07. New York, NY, USA: ACM, 2007, pp. 181–190.
  36. A. Narayanan and V. Shmatikov, “Robust de-anonymization of large sparse datasets,” in IEEE Symposium on Security and Privacy. IEEE, 2008, pp. 111–125.
  37. M. Chase, A. Healy, A. Lysyanskaya, T. Malkin, and L. Reyzin, “Mercurial commitments with applications to zero-knowledge sets,” in EUROCRYPT ’05, vol. 3494, 2005, pp. 422–439.
  38. J. Camenisch and A. Lysyanskaya, “An efficient system for non-transferable anonymous credentials with optional anonymity revocation,” in EUROCRYPT ’01, vol. 2045 of LCNS, 2001, pp. 93–118.