? 15 лет назад, 13 ноября 2008, Сатоши Накамото объяснил крупнейший научный прорыв — решение проблемы византийских генералов — в личной переписке с Джеймсом А. Дональдом. Представляем вам перевод сообщения.
? Джеймс А. Дональд пишет:
? Недостаточно, чтобы все знали X. Нам также нужно, чтобы все знали, что все знают X, и чтобы все знали, что все знают, что все знают X – что, как и в проблеме византийских генералов, является классической проблемой распределённой обработки данных.
? Сатоши Накамото отвечает:
? Цепочка доказательства работы (Proof of Work) – это решение проблемы византийских генералов. Попробую привести пример.
Несколько византийских генералов – каждый за своим компьютером – хотят атаковать королевский Wi-Fi путём перебора пароля, количество символов в котором стало им известно. После того, как им удастся заставить сеть создать пакет, им нужно взломать пароль за ограниченное время, чтобы провести атаку, стереть записи и остаться при этом незамеченными. Чтобы взломать пароль в срок, большинство мощностей их процессоров должны быть задействованы одновременно.
Им неважно, когда будет проведена атака, главное, чтобы все были в сговоре. Было решено, что каждый желающий может объявить время, и то время, которое будет озвучено первым, будет считаться официальным временем атаки. Проблема в том, что сеть не мгновенна, и если два генерала почти одновременно объявят разное время, то часть группы первым делом услышит одного, а другая – другого.
Для решения этой проблемы генералы используют цепочку доказательства работы. Как только каждый генерал впервые слышит предложенное время, он настраивает свой компьютер на решение чрезвычайно сложной задачи доказательства работы. Время атаки является частью исходных данных, которые хешируются в процессе решения этой задачи. Поиск доказательства работы настолько сложен, что результат совместной работы над ним ожидается лишь через 10 минут. Как только один из генералов находит доказательство работы, он транслирует его в сеть, и остальные перенастраивают своё оборудование, чтобы учесть обновлённые данные. Если чья-то работа основывалась на другом времени атаки, они переключаются на новую цепочку доказательства работы, потому что она теперь длиннее.
Через два часа один из вариантов времени атаки должен быть утверждён цепочкой из 12 успешно проведённых вычислений. Каждый генерал может легко проверить сложность цепочки доказательства работы, оценить, сколько параллельной вычислительной мощности в час было на неё затрачено, и убедиться, что для производства такого объёма работы в отведённое время потребовалось большинство компьютерных мощностей. Эта информация доступна каждому, ведь Proof of Work доказывает, что работа была проделана. Если вычислительная мощность, продемонстрированная цепочкой доказательства работы, достаточна для взлома пароля, то участники могут атаковать в оговорённое время.
Цепочка доказательства работы – это подход к решению проблем синхронизации, распределённых баз данных и глобальных вопросов, которые вы задавали.