Про топологические аспекты цифровой демократии.

-------------------------------------------------

1.1. Есть консенсус и топология.

-------------------------------------------------

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

Лемма (или теорема, чего уж) Кнастера-Куратовского-Мазуркевича (ККМ). Пусть симплекс ? на n вершинах покрыт n замкнутыми множествами A1,...,An, так что i-ая гипергрань симплекса не пересекается с Ai, при всех i. Тогда у множеств Ai непустое пересечение.

Предпосылку можно ослабить, можете в вики посмотреть общую формулировку https://en.wikipedia.org/wiki/Knaster–Kuratowski–Mazurkiewicz_lemma и понять, почему теорема выше оттуда следует. Верна также версия теоремы, в которой все Ai одновременно открытые, см. L.Zhou, A Theorem on Open Coverings of a Simplex and Scarf's Core Existence Theorem through Brouwer's Fixed Point Theorem, Economic Theory 4:3. Можете оценить название журнала, где опубликована топологическая статья. В ней, на самом деле, доказана более общая теорема К-К-М-Шепли, которая особо нужна экономистам, но нам в текущем контексте - не особо.

Пример, как это можно использовать на практике, - задача о справедливом делении арендной платы между студентам, - был описан в The New York Times в 2014 году https://www.nytimes.com/2014/04/29/science/to-divide-the-rent-start-with-a-triangle.html Возможно, это единственная статья в Таймс, как-то связанная с топологией. То есть история, безусловно, довольно знаменательная. С меня, честно говоря, журнал просит подписку, если с вас тоже, - то вам придется поверить моему приблизительному пересказу, который является, в свою очередь, пересказом части лекции Олега Мусина на нашей прошлогодней школе.

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

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

Формализуем нашу задачу. Рассмотрим все возможные способы разделить оплату. Если i-й студент вносит xi, то имеем xi>=0 и ?xi=1. Это стандартное уравнение симплекса ?. Давайте обозначим за Bi множество всех способов оплаты, которые устраивают i-го студента. Введем три ограничения

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

2) Bi покрывают симплекс. То есть любой способ оплаты хотя бы одному студенту нравится. С чисто человеческой точки зрения это довольно сильное условие: мало ли какие там тараканы у людей в голове бывают. Но математически мы его все же потребуем, без него, понятно, науки не построишь.

3) i-ая грань симплекса лежит в множестве Bi. Это как раз с человеческой точки самое естественное условие. Заметим, что i-ая грань симплекса - это как раз те способы оплаты, при которых i-й студент платит xi=0 (ноль рублей ноль копеек). Еще бы бедного студиозуса такое не устраивало!

И вот этих предпосылок достаточно для существования точки xi, которая принадлежит всем Bi. То есть существует способ оплаты, который удовлетворяет всех студентов.

Доказательство. Допустим противное, пусть ?Bi=?. Перейдем от множеств Bi к их дополнениям Ai=?Bi, они замкнуты. Противное допущение по правилам де Моргана влечет, что Ai покрывают симплекс. Раз уж Bi содержит i-ую грань, то Ai ее не пересекает. Мы находимся в условиях Теоремы К-К-М: значит пересечение Ai непусто. Но это противоречит тому, что Bi покрывают симплекс, - опять же по правилам де Моргана.

Для того, чтобы алгоритмически построить точку консенсуса, нужно достаточно мелко триангулировать наш симплекс состояний и жахнуть лемму Шпернера. Это такая дискретная версия ККМ-теоремы, которая используется и в доказательстве ККМ, и, если надо, напрямую в де Морган-двойственном утверждении про студентов. Таймс дает возможность поиграться с этим делом https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html Вдруг вам с соседями и впрямь надо прийти к консенсусу, теперь вы знаете, куда обращаться.

Вообще надо отметить, что лемма ККМ, помимо того что решает проблемы студентов с арендной платой, используется и во всяких фундаментальных вещах. В книге П.С.Александрова "Комбинаторная топология", например, она используется для доказательства того факта, что n-мерный симплекс имеет размерность n. Топологов старой закалки подобные вещи довольно сильно волновали.

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

-------------------------------------------------

1.2. Нет консенсуса и топология.

-------------------------------------------------

Чтобы не тянуть, начнем с ссылок. Я хочу рассказать о работе

M.Saks, F.Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J Comput 29:5 (2000).

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

M.Herlihy, D.Kozlov, S.Rajsbaum, Distributed Computing Through Combinatorial Topology, 2013.

Хотя я не то, чтобы все прочитал и осмыслил. Обсуждать мы будем такие утверждения.

Теорема 1 (слабая, Херлихи). В асинхронной мультипроцессорной системе с общей памятью невозможен сильный консенсус.

Теорема 2 (сильная, Сакс-Захароглу). В асинхронной мультипроцессорной системе с общей памятью невозможен слабый консенсус.

Поймем смысл всех слов из формулировки.

Мультипроцессорная система с общей памятью.

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

Асинхронная...

Это означает, что в компьютерах нет синхронизированных часов. Поэтому при написании программ нельзя использовать условия в духе "в 00:13:47 записать в регистр максимум из уже записанных чисел" или "написать в регистр '1', ждать 10 секунд, проверить, что другие написали". Это выглядит довольно надуманным ограничением: ну у кого в компьютере нет часов? Но на практике это не так уж тупо. Имеется в виду следующее. Считайте, что у вас компы находятся по всему земному шару, но обращаются к одной памяти. Даже если комп думает, что сделал запись в 00:13:47, - далеко не факт, что до памяти эта информация дойдет именно в такое время. Конечность скорости света и задержки при пересылке пакетов никто не отменял. Ну и бывают в сети непредсказуемые обстоятельства непреодолимой силы, вроде Роскомнадзора или "грозой провода оборвало".

Консенсус.

Поставим нашей асинхронной системе такую задачу. Сообщим втайне каждому процессору какое-нибудь натуральное число, пусть p-й процессор получил на вход число xp. Скажем, что система пришла к сильному консенсусу за t шагов, если на t-м шаге в регистре каждого компьютера записано одно и то же число x - и это одно из чисел x1,...,xn. Короче говоря, компам надо проголосовать за одно из входных чисел, прийти к консенсусу. Можно пользоваться общей памятью, нельзя - часами.

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

Теперь что такое слабый консенсус. Это когда на t-м шаге в каждом регистре k записано какое-то число yk с условиями: (1) каждое yk - это какое-то из входных значений xp (не обязательно с тем же номером), (2) среди yk есть хотя бы два повторяющихся. То есть это когда хотя бы два компьютера смогли договориться, грубо говоря.

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

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

Слабая теорема про невозможность сильного консенсуса - вроде бы без топологии доказывается. А сильная про невозможность слабого консенсуса - это про топологию.

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

Первый игрок, Система - это наша мультипроцессорная система, она пытается решить задачу консенсуса. Второй игрок, назовем его Хроносом, - это оппонент. Он пытается сделать так, чтобы у Системы не получилось. Какая свобода действий дана Хроносу? Он может на свое усмотрение в каждый момент времени допускать или не допускать каждый компьютер до работы с регистром. Обозначим через ?j?[n] множество компьютеров, допущенных в j-й момент к работе с регистром, будем считать, что это множество всегда непусто. Таким образом Хронос властен над последовательностью подмножеств ?={?1,?2,?3,...}, которая называется расписанием. А во власти Системы - загрузить заранее на каждый компьютер детерминированный алгоритм. Совокупность этих алгоритмов называется протоколом, назовем его П. Имея протокол П и расписание ?, независимый наблюдатель может написать состояние всех регистров до бесконечности. Это называется публичной записью, обозначим ее R(П,?).

Надо подчеркнуть, что каждый раз, когда компьютер допущен до работы с регистром, он пишет в следующую свободную ячейку своего регистра. То есть у компьютера нет информации о том, на каком временном шаге он сейчас находится - в этом смысл асинхронности. И наконец мы хотим избавиться от привязки к конкретному номеру шага, на котором компьютеры Системы должны выдать ответ. Если система хочет указать, что значение ans и есть ответ (а не просто очередная запись в регистре), то пусть она запишет "My answer is: "+ans. В статье предлагают более короткую запись "@."+ans. Таких ответов можно писать сколь угодно много, но учитываться будет только самый первый, появившийся в регистре.

Коль скоро мы все это поняли, то теоремы, написанные выше, можно переформулировать таким образом:

Теорема. Каким бы ни был протокол Системы, Хронос может подобрать такое расписание, при котором Система не придет к слабому консенсусу.

А в доказательстве начинается магия. Рассмотрим множество ? всех возможных расписаний (напомню, что расписание - это последовательность из подмножеств процессоров). Это какое-то дикое континуальное множество, естественно. На нем можно, однако, естественным образом ввести топологию, которая называется канторовской. Базу этой топологии образуют подмножества расписаний, имеющих общий префикс. В общем, это буквально p-адическая топология, если вы знаете, что это такое. При p=2 получилось бы канторово множество, ну а на нашем ? в качестве p по сути берется 2^n-1.

Дальше нам надо провести некоторые отождествления. Скажем, что два расписания ? и ?' неразличимы, если для любого протокола П выполнено R(П,?)=R(П,?'). То есть по публичным записям нельзя понять, какое из двух расписаний предложил Хронос. Получается отношение эквивалентности, легко видеть. Можно покопаться в этом немного и конструктивно описать полный набор операций, который позволяет получить из расписания все эквивалентные ему, их оказывается лишь конечное число. Рассмотрим пространство ?^ = ?/~ с естественной фактортопологией. Точки этого пространства называются сжатыми расписаниями.

Для фиксированного протокола П и ответа d, рассмотрим множество A(П,d) всех сжатых расписаний ?, для которых публичная запись R(П,?) содержит ответ d хотя бы в одном из регистров. Назовем подмножество A??^ познавающим, если оно имеет вид A(П,d) для некоторого протокола П и ответа d. Теперь два мозговыносящих факта:

I. Познавающие множества образуют топологию на ?^.

II. Эта топология совпадает с фактортопологией, введенной раньше.

И идея статьи Сакса-Захароглу в том, что пространство ?^ - это что-то типа симплекса на n вершинах, только он какой-то такой частично p-адический. И для него выполнен аналог теоремы Кнастера-Куратовского-Мазуркевича.

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

Возьмем 2-адическую топологию - это стандартное множество Кантора. Точки этого пространства можно отождествить с вещественными числами из отрезка [0;1], у которых в троичной записи содержатся только '0' и '2'. Теперь каждое число, имеющее постфикс '0(2)' отождествим с числом, полученным заменой постфикса на '2(0)'. В каждом классе эквивалентности оказалось лишь конечное число точек. Если перейти к факторпространству, то получится обычный отрезок: потому что ну реально двойки можно мысленно заменить на единицы, и получится представление чисел в виде бесконечных двоичных дробей со стандартными правилами отождествления. Так мы из канторова множества получили вполне разумный отрезок.

Вернемся к тезису о том, что ?^ - это типа симплекс. Назовем i-й гипергранью множества ?^ совокупность всех (сжатых) расписаний, в которых вообще не участвует i-й процессор.

Теорема ККМ для асинхронных систем. Пусть множество ?^ покрыто познавающими множествами A1,...,An, и пусть Ai не пересекает i-ую гипергрань пространства ?^. Тогда множества Ai имеют непустое пересечение.

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

Нам важно применить эту теорему к доказательству невозможности слабого консенсуса. От противного: допустим, что есть протокол П, который решает задачу слабого консенсуса. В частности, он сможет решить задачу и при условии, что 1-му процессору загадали число 1, 2-му - число 2, и т.д. Рассмотрим множество Di, состоящее из всех сжатых расписаний ?, для которых в публичной записи R(П,?) хотя бы один процессор принял решение i. Имеем:

I. По построению все Di познавающие, то есть открыты.

II. Множества Di покрывают ?^. Какое бы дурацкое расписание не предложил Хронос, хотя бы один компьютер к какому-то решению да приходит, так что это почти тавтология.

III. Di не пересекает i-ую гипергрань пространства ?^. Это тоже почти очевидно. Пусть это не так, для определенности i=1: тогда есть расписание, в котором не задействован первый процессор, и в результате выполнения которого кто-то дал ответ 1. Но мы могли бы устроить подставу: загадать первому процессору в самом начале вместо 1 слово 'Попався!'. Никто бы об этом не узнал, потому что 1-й комп не допускают до регистра. Но ответ 1, который дал кто-то в Системе, уже будет неверным, потому что в списке загаданных значений ['Попався!',2,3,..,n] значения 1 уже нет.

Итого мы в позиции применить теорему ККМ к множествам D1,...,Dn. Теорема гласит, что они пересекаются. Значит есть расписание ? при котором какой-то из n компьютеров дает ответ 1, какой-то дает ответ 2, ..., какой-то дает ответ n. Среди этих ответов нет повторов, значит на таком расписании слабый консенсус не достигается.

Хронос победил. Ура, с матчастью закончили.

-------------------------------------------------

2.1 Блокчейн

-------------------------------------------------

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

Что такое биткоин, если конкретно?

Биткоин - это огромный текстовый файл (в настоящее время около половины терабайта), копии которого, полные или частичные, хранятся на нескольких тысячах компьютеров, связанных по P2P сети. Вот тут https://bitnodes.io/ можно посмотреть, где находятся узлы сети биткоина, включенные в настоящий момент. Этот дикий текстовый файл называется блокчейном или цепочкой.

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

И наконец биткоин - это виртуальная монетка.

Но самое важное - правила. Конкретно для биткоина они таковы. Примерно раз в 10 минут в файл дописывается кусок текста, который называется блоком. В блоке записано некоторое количество содержательной информации, плюс какая-то абракадабра из символов, и про то и про другое ниже написано подробно. Записью новых блоков в файл занимаются компьютеры, которые называются майнерами. Майнер, которому удалось записать очередной блок в цепочку, автоматически получает награду. Сейчас награда составляет 6.25 биткоина за блок, запись об этой награде и его счастливом обладателе включена в записанный блок. Изначально награда была равна 50 биткоинов, но в правилах написано, что раз в 210000 блоков - примерно раз в 4 года, как легко посчитать, - награда должна уменьшаться вдвое. Просуммировав бесконечную геометрическую прогрессию, нехитро получаем, что всего в мире может быть максимум 21 миллион битков. Сейчас их существует чуть больше 19 миллионов. Также понятно, что лет этак через 30 автоматическая награда за блок станет весьма скромной и майнеров надо будет стимулировать другими способами.

Содержательная информация в блоке. В принципе, это может быть все, что угодно. Например, можно написать в блок слово "хуй". Зачем? Затем же, зачем оно написано в подъезде, - чтобы было. Только в подъезде его рано или поздно закрасят, а в блокчейне оно будет гарантированно храниться на нескольких тысячах компьютеров по всему миру. Пока сеть блокчейна и входящие в нее узлы физически существуют, этой информации ничего не грозит. И это, вроде как, надежнее, чем хранить информацию на сервере (или двух, или десяти серверах) какой-нибудь компании. Довольно бедная статистика показывает, что Александрийская библиотека сгорает чаще, чем глобальная информационная сеть. Поэтому, типа, считается, что блокчейн - это полезная технология даже и вне привязки к виртуальным деньгам. Хотя тут можно поспорить: никто не будет долго хранить всякую фигню, если в этом нет финансовой выгоды.

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

Говоря про биткоин, бОльшая часть содержательной информации в блоке - это лог транзакций монеток. Что-то в духе "Петя послал Маше 0.378478272 биткоина, Катя послала Васе 0.000232329 биткоина,...". Только вместо имен - обновляемые коды кошельков. И на все это навешивается некоторое количество криптографии (в случае битка - криптографии на эллиптических кривых) с приватными и публичными ключами. Тут криптография позволяет подтвердить, что Петя послал именно Маше, так сказать, в здравом уме и твердой памяти. Защита нужна, чтобы какой-нибудь условный Ваня не смог написать в блок "Петя послал Ване мильон битков", и поиметь нечестный гешефт. Но эти методы защиты довольно стандартные для банковских переводов, особого крипто-ноу-хау в этой части истории нет, потому и останавливаться на этом мы не будем.

Важный take-home message предыдущего абзаца, однако, в том, что все ваши транзакции биткоинов абсолютно прозрачны - если известны коды, генерируемые вашим кошельком. Любой человек может открыть блокчейн, поискать в нем нужные коды, и найти всю историю ваших переводов, а по истории восстановить сколько битков у вас на балансе. Вот тут https://www.blockchain.com/explorer/blocks/btc можете посмотреть, кто кому сколько деньжищ переводит прямо сейчас (и поплакать). Анонимизация происходит на этапе "личность-коды кошелька". Но очевидно, что эта связка в одном направлении легко ломается методом паяльника в жопе, - видимо, поэтому американское правительство считает биток не самым удобным способом злодеям делать свои темные дела. Как бы в обычных банках метод паяльника работает точно так же, но банк информацию о транзакциях шифрует, - с банком еще по судам тягаться придется. А битки довольно прозрачные по построению. Поэтому, вроде как, их и не запрещают.

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

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

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

Хэш-функция - это детерминированная булева функция f, которая принимает на вход битовую строчку произвольной длины, а выдает битовую строчку фиксированной длины, скажем 256 бит. Результат, значение функции, называется хэш-суммой. Эквивалентно, можно считать, что хэш-сумма - это целое число от 0 до 2^256-1, записанное в двоичной системе. С одной стороны, хэш-функция должна быть достаточно хаотичная в том смысле, что для фиксированного значения y вы ничего не можете сказать об x с условием f(x)=y, т.е. зная хэш-сумму, невозможно ни угадать от чего она была посчитана, ни предсказать какие-либо свойства входа. С другой стороны, хэш-функция должна "сохранять меру" в том смысле, что посылая на вход строчки из равномерного распределения (если длину входа зафиксировать), мы получим равномерное же распределение хэш-сумм, ну примерно. И наконец, однократное вычисление хэш-функции должно быть шустрым.

Короче говоря, хэш - это такой аналог арнольдовской окрошки из кошки, только необратимый и нелинейный. Пример хэша (который сидит в биткоине) - SHA-256, можете почитать, как она определяется, тут https://blog.boot.dev/cryptography/how-sha-2-works-step-by-step-sha-256/ . Весьма медитативное чтиво, скажу я вам.

Итак, что происходит, когда вы отправляете электронное письмо? Ваш почтовый клиент берет из письма какую-то мета-информацию: адрес отправителя, дату и время отправки, пакует это в булеву строчку, - и приписывает к ней абракадабру: некоторое количество случайных битов. И после этого вычисляет от полученной строчки хэш-сумму. Если хэш-сумма начинается с 20 нулей, то это считается победой. В этом случае письмо вместе с абракадаброй отправляется на сервер. Если получить 20 нулей не получилось, то увеличиваем абракадабру на единицу, снова считаем хэш, и смотрим, получилось ли 20 нулей. И так далее - инкрементируем абракадабру, считаем хэш, - делаем, пока не получим в результате 20 нулей. Из-за свойства сохранения меры вероятность получить 20 нулей за один подсчет равна 1/2^20. Поэтому в среднем, чтобы получить результат с 20 нулями, нужно вычислить хэш-функцию 2^20 раз, примерно миллион.

Что происходит на сервере? Сервер получает письмо плюс строчку "метаинформация"+"абракадабра". Сервер проверяет, что метаинформация соответствует письму, и вычисляет хэш от строчки. Если сервер видит в начале хэш-суммы 20 нулей, - то для него это подтверждение того, что клиент проделал вычисление хэша ~2^20 раз. Тогда все ок, письмо летит дальше куда надо. Но если сервер проверяет хэш-сумму, и не видит 20 нулей, то письмо удаляется. Ну там есть еще такая техническая заморочка, что строка "метаинформация"+"абракадабра" должна быть уникальной, все дубли автоматически стираются. Это вынуждает клиента выбирать начальное значение абракадабры каждый раз заново, - даже если метаинформация в наборе писем одна и та же.

Таким образом получается железобетонная гарантия, что каждое успешно доставленное письмо съело у отправителя контролируемо-случайное число процессорных тактов. Описанная концепция называется Proof-of-Work (PoW) и ровно на ней основан майнинг крипты. Такая вот шокирующая новость для людей, которые считают майнеров гнидами, просирающими электричество на бессмысленные операции. Все мы немного майнеры, когда пользуемся электронной почтой, или когда строчим комменты в бложеки. В блогах тоже используется hashcash, только там он нужен для защиты от DDoS-атак, принцип немного модифицирован. Это тот же спам по существу, только с другими целями.

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

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

(*) Далее майнер, допустим его зовут Вова, записывает в блок что-то в духе "Вова<тут стоит код его кошелька> создал этот блок, и получил в награду 6.25 биткоина из великой пустоты небытия". Вот этот вот вброс новой деньги в рынок называется минт, ковка. Через сто лет, когда минт не будет приносить профит, майнеры будут зарабатывать чисто на комиссиях за переводы.

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

(*) Наконец, Вова приписывает к блоку абракадабру. Начальное значение абракадабры по научному называется nonce (это латиницей, если что).

Теперь Вова расчехляет свою RTX-4090, или что там у него, и начинает яростно считать на ней хэш-функцию от всего вышеперечисленного, - пока результат не будет начинаться на чертову уйму нулей. Сейчас, кажется, надо 77 нулей, но вообще это число со временем растет. То есть Вова считает хэш, если не получилось, то инкрементирует абракадабру, снова считает, и так далее. Все эти вычисления очевидным образом параллелятся, а потому хорошо ложатся на GPU. То есть успех настигнет Вову, если он посчитает хэш 2^77 раз, ну в среднем. Это число прямо дохрена больше, чем 2^20. Но так и получить 6.25 биткоина - это вам не котика запостить, за такие деньги можно однушку у МКАДа купить. Если бы в России это было разрешено, хе-хе.

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

Итак, что мешает Вове по описанной выше схеме получать нахаляву 6.25 биткоина раз в 10 минут? Еще примерно стопицот майнеров, которые тоже собирают блоки и подбирают абракадабру, хэш от которой начинается на 77 нулей. Кто первый получил правильный хэш, тот и записывает свой блок в цепочку, остальные работали напрасно. Вероятность того, что выиграет Вова, а не какой-нибудь китаец с фермой из тысячи специально заточенных на это вычислителей, - трындец какая маленькая. Хоть и ненулевая.

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

В итоге, PoW в биткоине гарантирует, что блок записывается раз в 10 минут. И одновременно гарантирует, что майнер не налажает в записи блока. Потому что, если налажал, то это быстро вскроется другими участниками сети - валидаторами, и блок банят, - выходит, что майнер работал напрасно.

Если задуматься, то это все очень похоже на механики ЛМШовых игрушек: если тебе надо занять ребенка на станции на 5-10 минут и дать ему по итогу какую-нибудь ачивку - заставляешь его собирать самолетики, распрямлять фольгу, или факторизовать трехзначные числа. Это немного тупо, конечно, - в продуманных игрушках должны быть более изящные протоколы.

Так и криптовалюты бывают разные. Вот эфир недавно переключился с PoW на PoS: Proof-of-Stake (*на самом деле, форкнулся). В этом протоколе блок записывает не самый везучий майнер, а, грубо говоря, участник сети, поставивший на кон больше всего валюты - и рискующий ее потерять, если налажает или попытается смухлевать. Мы же помним, что информация, у кого сколько валюты, открытая: поэтому условие соответствия легко проверить. Чисто технически переписать блокчейн эфира теперь не сложно, хэши там если и есть, то слабенькие. Фишка в том, что теперь писатели блоков расписываются на них своими сбережениями: если уж ты можешь валидно переписать миллион блоков, то значит на твоих кошельках столько дохрена баблища, что ломать систему тебе вроде бы и невыгодно. Ну как-то так я это понимаю.

-------------------------------------------------

2.2 Форки и прочее

-------------------------------------------------

В п.1.2 мы говорили про отсутствие консенсуса в асинхронных системах, каковой, например, является P2P сеть биткоина. Косвенным образом невозможность консенсуса порождает слабое место любой крипты, основанной на блокчейне: форки. Или, говоря по-русски, вилки.

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

а) Суровые вилки (hard forks). Это когда меняются представления игроков о прекрасном, причем меняются существенно, на уровне основных правил игры. Часть компьютеров в сети сознательно поддерживает эти изменения, а часть - нет. В итоге часть игроков продолжает играть по старым правилам, а часть - переключается на новую игру, и образует новую сеть. Такое бывает не очень часто, и иногда в результате суровой вилки рождается новая криптовалюта.

Take away message в том, что если какая-то сеть объявляет запланированный hard fork, то вы можете вложиться в эту крипту, и тогда после вилки с какой-то вероятностью получите вместо одной коллекции фантиков - две коллекции фантиков. Принесет ли вам это счастье - вопрос уже отдельный.

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

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

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

Может так случиться, что Вова из России и Хелен из Австралии смайнили правильный блок почти одновременно, ну либо валидация произошла почти одновременно. Назовем такую ситуацию паритетом. У P2P сети биткоина нет никакого объективного способа выбрать победителя - об этом нам говорят топологическая теорема из п.1.2 этой заметки. Никакие суперточные timestamps для определения, кто был первым, нас не спасут, потому что timestamps можно подделать.

Чего делать в такой ситуации? А ничего не делать. В whitepaper Сатоси Накамото (это такой Николя Бурбаки в мире крипты) написано, что надо принимать оба блока. Но в дальнейшем, все майнеры и валидаторы пользуются общим правилом: истинной цепочкой считается цепочка наибольшей длины в нашем ветвящемся дереве, и приписывать блоки нужно именно к ней. Как the elder rule в устойчивых гомологиях.

Как я понимаю, на практике это работает так. Допустим, возник паритет Вовы и Хелен. Сейчас обе цепочки - и с концом в блоке Вовы, и с концом в блоке Хелен - имеют одинаковую длину, поэтому обе считаются истинными. В следующие 10 минут каждый майнер выбирает одну из них: как мы помним, майнер использует хэш от предыдущего блока, - поэтому усидеть сразу на двух стульях он не может. Допустим, что майнер Цзинь, выигравший очередной раунд, работал с цепочкой Хелен. Теперь цепочка "предыстория-Хелен-Цзинь" стала длиннее, чем цепочка "предыстория-Вова", а значит именно она является истинной. Блок Вовы объявляют сиротой, с этим блоком теперь никто не будет работать. Система проверяет, все ли транзакции из блока Вовы были учтены в блоке Хелен. Если какие-то транзакции оказались не осуществлены, то их кидают обратно в сеть, - они будут ждать, пока следующий майнер включит их в блок.

Чем это все чревато для игроков? Во-первых, Вове должно быть чертовски обидно: в течение 10 минут он был гордым обладателем однушки у МКАДа, а потом перестал, - потому что какой-то Цзинь выбрал чужой блок. Во-вторых, такая же неопределенность возникает у обычных юзеров: если ваш перевод биткоина был в блоке Вовы, но не Хелен, то ваш получатель как бы и получил деньги и не получил одновременно - вы это не узнаете, пока не напишут следующий блок.

Такое бабло Шрёдингера в реальном мире. Пока случайный Цзинь не проведет наблюдение квантовой системы, мы не узнаем кто прав: Вова или Хелен. Поэтому, конечно, при валидации переводов надо учитывать все возможные альтернативные блоки. Вова/Хелен/ваш получатель не может тратить свое бабло, пока нет подтверждения, что оно записано в единственном истинном префиксе. Из-за этого фактически перевод биткоина может занимать больше 10 минут. Ну либо вы предложили откат достаточно аппетитный, чтобы все возможные майнеры включили вашу транзакцию в свои блоки:)

Самое веселое - риск, что паритет будет повторяться. Если вместе с Цзинем правильный блок сгенерила Ума, и если она выбрала за основу блок Вовы, то у нас получились две цепочки: "предыстория-Хелен-Цзинь" и "предыстория-Вова-Ума". Обе истинные, но не очень полезные. Больше ветвления, больше квантового бабла!

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

Но пофантазировать о математической возможности применять p-адическую теорему Кнастера-Куратовского-Мазуркевича к бесконечно ветвящемуся квантовому блокчейну на протоколе Proof-of-Useful-Work с нейросетками вместо хэшей - довольно приятное занятие для благородных умов.

За сим кончаю, надеюсь, это было познавательно.

Источник: m.vk.com

Комментарии: