Re: Теория Bitcoin (византийские полководцы и за ее пределы)
Эта проблема стартовала тридцать лет исследований в распределенных системах. Это увлекательное поле, а также очень тонкий один. Вариации этой проблемы бывают несколько основных вкусов, однако, что это возможно и что не сильно зависит от предположений, которые вы делаете и что вы требуете от протокола. Мои цели в этой почте описать основные компоненты проблемы, указать на некоторые из моих любимых материалов для чтения, и мы надеемся начать обсуждение о том, какие допущения и требования подходят для Bitcoin (или altchains). Результаты могут быть собраны в вики. Я также хочу, чтобы сделать общий аргумент: хотя проблемы такого рода были изучены в течение многих десятилетий, академическое поле еще не решен, и Bitcoin, кажется, показывает несколько белых пятен.
котировка
Представьте себе двух пешеходов, пытающихся пройти друг с другом в коридоре, где они должны прийти к консенсусу о том, чтобы передать слева или справа. Каждый изначально имеет предпочтение какому пути они хотят идти (например, право американцев и оставили для британцев), и от ФЛП результата мы знаем, что если пешеходы являются детерминированными и сроки их под контролем противника, каждый из них будет сдаваться и принять предпочтение другого пешехода в одно и то же время. Результаты и неловко (голодание) и неправдоподобно (не бывает в реальной жизни). Раствор для одного или обоих пешеходов, чтобы объявить, что они выбирают новое предпочтение путем монетку. Это дает 50% вероятность того, что оба будут согласны друг с другом, даже если только один из пешеходов подбрасывает монету. Таким образом, после постоянного числа монетных переворачивается, как пешеходы согласны, и (при условии, что они могут обнаружить это соглашение), они будут решены к консенсусу.
Джеймс Aspnes, Yale, отмечает CS465 курс
Джеймс Aspnes, Yale, отмечает CS465 курс
котировка
Хотя есть 100 различных результатов, нет 100 различных идей ... Основная идея, на которой все 100 невозможность доказательства в распределенных вычислений основаны [это] ограничение, налагаемое местного знания.
Сто Невозможность Доказательств для распределенных вычислений. Нэнси Lynch. Принципы распределенных вычислений, 1989.
Сто Невозможность Доказательств для распределенных вычислений. Нэнси Lynch. Принципы распределенных вычислений, 1989.
--------
Все распределенные системы сталкиваются с двумя существенными проблемами: задержки и неудачи.
- Неудачи: Общее количество процессов (иначе: участники, узлы, общий-hashpower) обозначаются "N", Некоторая часть "е" из них может потерпеть неудачу. Виды отказа стоит описывать: постоянно сбой, останавливая-и-перезапуск и византийского - это значит вести себя злонамеренно в худшем виде. Устойчивость системы, как правило, описывается как "N = 2f + 1", Который так же, как то, что мы имеем в виду на 51%.
В большинстве предыдущих работ предположили, что N известен, что каждый процесс имеет уникальный идентификатор, и что каждый знает все идентификаторы с самого начала. Недавнее исследование посмотрел на анонимных сетей и крупномасштабных динамических сетей, показывая, что эти различия не являются тривиальными. Некоторые работы, что приближается все ближе и ближе к Bitcoin:
- Частично анонимные сети (омонимы) Delporte-Gallet и др, 2011
- Вычислительный вызов византийских самозванцев (Тесно связана с Bitcoin в духе) Aspnes, 2005
- протоколы населения (Крошечные анонимные узлы, молекулы взаимодействия) Angluin, 2006
- Рациональные неудачи (Сочетает в себе теорию игр и распределенные системы) Климент и др, 2008
- Задержка: Есть три популярные модели синхронизации, которые описывают неопределенную скорость распространения сообщений в сетях. Простейший случай называется "синхронная система связи"И это когда приходит каждое сообщение в течение определенного известен ограничение по времени, Δ (дельта). Любые сообщения, которые занимают больше времени, чем это есть «Тайм-аут», и вы можете считать их неудачей. Протоколы для этой модели часто протекают в отдельных раундах. Часть Bitcoin, которая отклоняет блоки на основе недействительных отметок времени, например, является показателем предположений синхронности. Сложная модель «асинхронный», где пакеты могут занять больше и больше и больше времени, чтобы прибыть.
Медиум-трудность (и в основном реалистичный) сценарий называется «частично синхронной», где могут возникать временные перегородки, но в конце концов решена. В этой модели вы не используете какие-либо явные временные параметры. Максимальное время задержки Δ существует, но неизвестно. Синтия Дворк, Нэнси Линч, и Ларри Stockmeyer выиграл Дейкстры приз за это 1988 бумаги, который оказался очень полезным. Если вы когда-нибудь мечтали о горной колонии Bitcoin на Марсе, или спрашивает, что произойдет, если трансатлантические оптоволоконная магистраль вдруг разорваны, вы, вероятно, думать о частично синхронной модели. Наилучшие возможные результаты в этой модели на 67% (3f + 1) выбор, а не 51% (2f + 1) сорта. Если даже 67% честные участники могут выжить раздел, который раскалывает их пополам по неизвестной длительности, то злоумышленник с 33% может притвориться (имитировать) находясь на другой стороне перегородки и сорвать вас в любое время. - Варианты постановки задачи: Оригинальный Византийская проблема Generals (Лэмпорт, 1978) показал асинхронные связи между известным набором детерминированных процессов с защищенными каналами между каждой парой. Это требование заключается в том, что процессы в конечном итоге сделать безотзывное «окончательный ответ» решение, и когда они делают, они все согласны. Если что-то вроде «подтвердил после 6 блоков» правила были построены в протокол Bitcoin, то она будет соответствовать этой проблемы.
Есть несколько аспектов, которые делают Bitcoin проблемы сложнее, в частности сети анонимного / неизвестного размера. Есть также много разумных способов сделать это проще.- Случайность, существенная часть Bitcoin, достаточно из того, чтобы сделать иначе, невозможное возможно. Случайность это способ приработка симметрии (см новеллы в верхней части этого поста). Если сложность головоломки достаточно высока, Bitcoin может нарушить симметрию в любой временной шкале. Тем не менее, использование рандомизации, вы должны расслабить проблему так, что либо а) отказ возможен, но с нулевой вероятностью, или б) отказ может произойти с некоторой незначительной вероятностью.
- Случайные оракулы (необратимая криптографический хэш-функция с равномерными случайными выходами).
Хэш-функции являются чем-то мы принимаем с верой, по крайней мере на некоторое время. Это было доказано что ни один хэш-функция ведет себя отлично. С другой стороны, некоторые простые свойства (например, конфликтное сопротивление) являются доказуемо достижимы. Я сомневаюсь, что кто-то будет утверждать, что Bitcoin зависит от неприемлемых свойств хэш. Тем не менее, это является причиной, почему их использование не было столь широко изучены в распределенных системах (Счетчик пример) - от очень традиционной точки зрения, они слишком сильны предположение. Любой протокол, используя хэш будут нести по крайней мере положительный, но незначительный шанс неудачи. Многие протоколы консенсуса считали совершенные с проверкой подлинности каналов, но любой конкретизации из них с примитивами из современной криптографии, скорее всего, ввести случайный оракул в какой-то момент. Я нахожу интересным, что оригинальное использование хэш на основе головоломок был по Дворку и NaOR, два из ведущих фигур в распределенном консенсусе, но они не рассматривали использование таких головоломок в алгоритмах консенсуса. Даже незнакомец, Наор и Нисим был первым предложить сбалансированные деревья Меркле для использования в системах обработки транзакций (аннулированные сертификаты). - Стабилизирующий консенсуса - это то, что вы получаете, когда вы удаляете «окончательное решение» требование от византийской проблемы генералов. Протокол гарантирует, что Вы в конечном счете сходятся, но вы не можете точно сказать, когда это произошло. Дейкстра определен «Автостабилизация» в 1974 году, и Angluin адаптировать его к проблеме консенсуса в 2006 году. Термин «в конечном счете, соответствует» Здесь уместно. Это, я думаю, наиболее подходящее определение проблемы для Bitcoin. Мы в конечном итоге стабилизируется к одной согласованной стоимости для каждого блока, независимо от того, что. Но в любой конкретный момент времени, нет никакого способа, чтобы исключить возможность большей вилки, показывая вверх. Если это произойдет, то вы берете на себя большую вилку и иметь дело с ним, и протокол продолжается. Любые необратимые решения (например, я жду 6 подтверждений и дать вам слиток золота) производятся в соответствии с анализом личного риска пользователя - если они получают раздвоенные, это не считается как провал протокола.
- Случайность, существенная часть Bitcoin, достаточно из того, чтобы сделать иначе, невозможное возможно. Случайность это способ приработка симметрии (см новеллы в верхней части этого поста). Если сложность головоломки достаточно высока, Bitcoin может нарушить симметрию в любой временной шкале. Тем не менее, использование рандомизации, вы должны расслабить проблему так, что либо а) отказ возможен, но с нулевой вероятностью, или б) отказ может произойти с некоторой незначительной вероятностью.
---- Некоторые заключительные мысли -----
котировка
Да, я знаю, что доказательство правильности работы, как он используется в Bitcoin, предназначен, чтобы дать византийская отказоустойчивость, но моя мысль заключается в том, что это не так. И, кроме того, что он не в невероятно неэффективным способом.
Бен Лори, болтают на Bitcoin.
Бен Лори, болтают на Bitcoin.
Именно этот пост Бен Лори, который привел меня, чтобы прочитать о распределенных системах. Я подозреваю, что он неправ. По крайней мере, это можно изменить постановку задачи таким образом, что Bitcoin решает ее. Любой, кто следил за развитием этой области в течение нескольких десятилетий будет признать, что не существует единственно правильного набора допущений модели для каждого приложения. Тонкие изменения привели к неожиданным результатам, как для возможности и невозможности.
Это меня удивляет, что, как еще, никто из распределенных систем не сказал ничего о лежащем в основе консенсуса механизме Bitcoin. (Несмотря на то что Bitcoin и красные шары сближается, они сосредоточились на красную сельди, связанную с сплетнями слоя, а не ядром). Я надеюсь, что это изменится в ближайшее время, как распределенные системы исследователи и сообществу Bitcoin должно быть много, чтобы учиться друг у друга. Как и во многих областях информатики, теория распределенных систем была разработана задолго до реальных сетей и Интернет были широко распространены. Многие из теоретических вкладов были уволены на практике.
котировка
К сожалению, византийские соглашение требует ряда сообщений квадратичных по числу ofparticipants, так что неосуществимо для использования при синхронизации большого количества копий.
Пруд, реализация Oceanstore
Пруд, реализация Oceanstore
котировка
Накладные расходы связи византийского соглашения по своей природе большие
сервера первоначальное соглашение общей иерархии проводных / беспроводных сетей
сервера первоначальное соглашение общей иерархии проводных / беспроводных сетей
Поэтому я думаю, что распределенные системы люди нашли бы очень интересно, что с открытым исходным кодом сообщество подхватило задачу построения крупномасштабной, с высокими ставками консенсуса сети при высшем состязательных условиях. Из того, что я видел, что средний пользователь Bitcoin имеет понимание распределенных систем, совпадающее аспиранта, и мог бы по крайней мере, пройти через результате невозможности ФЛП с точки зрения конкурирующих blockchain вилки с одинаковой силой.
