blockchain.tex

\section{Blockchain (цепочка блоков)}\label{section-blockchain}\index{Blockchain|(}
\selectlanguage{russian}

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

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

В таких системах есть три группы действующих лиц:

\begin{itemize}
	\item генераторы событий (транзакций);
	\item генераторы блоков (фиксаторы транзакций);
	\item получатели (читатели) блоков и зафиксированных транзакций.
\end{itemize}

В зависимости от реализации эти группы могут пересекаться. В системах типа Bitcoin\index{Bitcoin}, например, все участники распределённой системы могут выполнять все три функции. Хотя за создание блоков (фиксацию транзакций) обычно отвечают выделенные вычислительные мощности, а управляющими их участников называют майнерами (\langen{miners}, см. раздел про децентрализованный blockchain далее).

Основное требование к таким журналам таково:

\begin{itemize}
	\item невозможность модификации журнала: после добавления транзакции в журнал должно быть невозможно её оттуда удалить или изменить.
\end{itemize}

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

\begin{itemize}
	\item Каким образом гарантируется, что внутри блока нельзя поменять информацию?
	\item Каким образом система гарантирует, что уже существующую цепочку блоков нельзя перегенерировать, тем самым исправив в них информацию?
\end{itemize}

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

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

\begin{itemize}
	\item централизованный с доверенным центром,
	\item централизованный с недоверенным центром,
	\item децентрализованный вариант с использованием доказательства работы.
\end{itemize}

\subsection{Централизованный blockchain с доверенным центром}

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

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

\subsection{Централизованный blockchain с недоверенным центром}

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

Для этого можно использовать, например, следующие методы.

\begin{itemize}
	\item Первый метод с использованием дополнительного доверенного хранилища. После создания очередного блока центр должен отправить в доверенное и независимое от данного центра хранилище хэш-код от нового блока. Доверенное хранилище не должно принимать никаких изменений к хэш-кодам уже созданных блоков. В качестве такого хранилища можно использовать и децентрализованную базу данных системы, если таковая присутствует. Размер хранимой информации может быть небольшим по сравнению с общим объёмом журнала.
	\item Второй возможный метод состоит в дополнении каждого блока меткой времени, сгенерированной доверенным центром временных меток. Такая метка должна содержать время генерации метки и электронную подпись центра, вычисленную на основании хэш-кода блока и времени метки. В случае, если <<недоверенный>> центр захочет перегенерировать часть цепочки блоков, будет наблюдаться разрыв в метках времени. Стоит отметить, что этот метод не гарантирует, что <<недоверенный>> центр не будет генерировать сразу две цепочки блоков, дополняя их корректными метками времени, а потом не подменит одну другой.
	\item Некоторые системы предлагаю связывать закрытые blockchain-решения и открытые (и неконтролируемые ими) сети вроде Bitcoin'а, публикую в последнем (в виде транзакции) информацию о хэш-суммах новых блоков из закрытой цепочки. В этом случае информация из открытой и неконтролируемой организацией сети позволяет доказать, что определённый блок во внутренней сети был сформирован не позднее времени создания блока в открытой сети. А отсутствие для известных (заданных заранее) адресов отправителя других транзакций позволяет доказать, что центральный узел не формирует какую-нибудь параллельную цепочку для замены в будущем.
\end{itemize}

\subsection{Децентрализованный blockchain}

Наибольший интерес для нас -- и наименьший для компаний, продающих blockchain-решения, -- представляет децентрализованная система blockchain без выделенных центров генерации блоков. Каждый участник может взять набор транзакций, ожидающих включения в журнал, и сформировать новый блок. Более того, в системах типа Bitсoin\index{Bitcoin} такой участник (будем его назвать <<майнером>>, от \langen{to mine} -- копать) ещё и получит премию в виде определённой суммы и/или комиссионных от принятых в блок транзакций.

Но нельзя просто так взять и сформировать блок в децентрализованных системах. Надёжность таких систем основывается именно на том, что новый блок нельзя сформировать быстрее (в среднем) чем за определённое время. Например, за 10 минут (Bitcoin). Это обеспечивается механизмом, который получил название доказательство работы (\langen{proof of work, PoW}).

Механизм основывается на следующей идее. Пусть есть криптографически стойкая хэш-функция $h(x)$, и задан некоторый параметр $t$ (от \langen{target} -- цель). $0 < t < 2^{n}$, где $n$ -- размер выхода хэш-функции в битах. Корректным новым блоком blockchain-сеть будет признавать только такой, значение хэш-суммы которого меньше текущего заданного параметра $t$. В этом случае алгоритм работы майнера выглядит следующий образом:
\begin{itemize}
	\item собрать из пула незафиксированных транзакций те, которые поместятся в 1 блок (1 мегабайт для сети Bitcoin\index{Bitcoin}) и имеют максимальную комиссию (решить задачу о рюкзаке\index{задача!о рюкзаке});
	\item добавить в блок информацию о предыдущем блоке;
	\item добавить в блок информацию о себе (как об авторе блока, кому начислять комиссии и бонусы за блок);
	\item установить $r$ в некоторое значение, например, $0$;
	\item выполнять в цикле:
	\begin{itemize}
		\item обновить значение $r := r + 1$;
		\item посчитать значение $h = h( \text{блок} || r)$;
		\item если $h < t$, добавить в блок $r$ и считать блок сформированным, иначе -- повторить цикл.
	\end{itemize}
\end{itemize}

Для каждой итерации цикла вероятность получить корректный блок равна $t / 2^{n}$. Так как $t$ обычно мало, то майнерам нужно сделать большое количество итераций цикла, чтобы найти нужный $r$. При этом только один (обычно -- первый) из найденных блоков будет считаться корректным. Чем больше вычислительная мощность конкретного майнера, тем больше вероятность, что именно он первым сумеет найти нужный $r$.

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

Кроме задания параметра $t$ можно оперировать другими величинами, так или иначе относящимися к мощности вычислений.
\begin{itemize}
	\item \textit{Hashrate} -- количество хэшей, которые считают за единицы времени конкретный майнер или сеть в целом. Например, в ноябре 2017 года общий hashrate для сети Bitcoin составлял примерно $7,7 \times 10^{18}$ хэшей в секунду.
	\item \textit{Difficulty} -- сложность поиска корректного блока, выражаемая как $d = d_{const} / t$, где $d_{const}$ -- некоторая константа сложности, а $t$ -- текущая цель (\langen{target}). В отличие от параметра $t$, который падает с ростом вычислительной мощности сети, $d$ изменяется вместе с $hashrate$, что делает его более простым для восприятия и анализа человеком.
\end{itemize}

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

В случае нормального поведения системы на включение конкретных транзакций в блоки это влияет мало, так как каждый из добросовестных майнеров следует одному и тому же алгоритму включения транзакций в блок (например, в сети Bitcoin\index{Bitcoin} -- алгоритму максимизации комиссии за блок). Однако можно предположить, что какой-нибудь злоумышленник захочет <<модерировать>> распределённый blockchain, включая или не включая в блоки транзакции по своему выбору. Предположим, что доля вычислительных ресурсов злоумышленника (направленных на генерацию нового блока) равна $p, 0 < p < 1/2$. В этом случае каждый следующий сгенерированный блок с вероятностью $p$ будет сгенерирован мощностями злоумышленника. Это позволит ему включать в блоки те транзакции, которые другие майнеры включать не захотели.

Но позволит ли это злоумышленнику не включать что-то в цепочку транзакций? Нет. Потому что после его блока с вероятностью $1 - p$ будет следовать блок <<обычного>> майнера, который с радостью (пропорциональной комиссии-награде) включит все транзакции в свой блок.

Однако ситуация меняется, если мощности злоумышленника составляют более 50\% от мощности сети. В этом случае, если после блока злоумышленника был с вероятностью $1 - p$ сгенерирован <<обычный>> блок, злоумышленник его может просто проигнорировать и продолжать генерировать новые блоки, как будто он единственный майнер в сети. Тогда если среднее время генерации одного блока всеми мощностями $t$, то за время $T$ злоумышленник сможет сгенерировать $N_E = p \times T / t$, а легальные пользователи $N_L = (1 - p) \times T / t$ блоков, $N_E > N_L$. Даже если с некоторой вероятностью легальные пользователи сгенерируют 2 блока быстрее, чем злоумышленник один, последний всё равно <<догонит и перегонит>> <<легальную>> цепочку примерно за время $t / (2p - 1)$. Так как в blockchain есть договоренность, что за текущее состояние сети принимается наиболее длинная цепочка, именно цепочка злоумышленника всегда будет восприниматься правильной. Получается, что злоумышленник сможет по своему желанию включать или не включать транзакции в цепочки.

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

Кроме концепции <<доказательство работы>> используются и другие. Например, в подходе <<доказательство доли владения>> (\langen{proof of share, PoS}), который планировалось использовать в сетях Etherium и EmerCoin, вероятность генерации блока пропорциональна количеству средств на счетах потенциальных создателей нового блока. Это намного более энергоэффективно по сравнению с PoW, и, кроме того, связывает ответственность за надёжность и корректность генерации новых блоков с размером капитала (чем больше у нас средств, тем меньше мы хотим подвергать опасности систему). С другой стороны, это даёт дополнительную мотивацию концентрировать больше капитала в одних руках, что может привести к централизации системы.

\subsection{Механизм внесения изменений в протокол}
Любая система должна развиваться. Но у децентрализованных систем нельзя просто <<включить один рубильник>> и заставить участников системы работать по-новому -- иначе систему нельзя назвать полностью децентрализованной. Механизмы и способы внесения изменений могут выглядеть на первый взгляд нетривиально. Например:

\begin{enumerate}
	\item апологеты системы предлагают изменения в правилах работы;
	\item авторы ПО вносят изменения в программный код, позволяя сделать две вещи:
	\begin{itemize}
		\item указать участникам системы, что они поддерживают новое изменение,
		\item поддержать новое изменение;
	\end{itemize}
	\item участники системы скачивают новую версию и выставляют в новых блоках транзакций (или в самих транзакциях) сигнальные флаги, показывающие их намерение поддержать изменение;
	\item если к определённой дате определённое число блоков (или число транзакций, или объём транзакций) содержат сигнальный флаг, то изменение считается принятым, и большая (по числу новых блоков) часть участников системы в определённую дату включают эти изменения;
	\item те участники, которые не приняли изменения, или приняли изменения вопреки отсутствию согласия на них большей части участников, в худшем случае начнут генерировать свою цепочку блоков, только её признавая корректной. Основную цепочку блоков они будут считать неверно сгенерированной. По факту это приведёт к дублированию (разветвлению, форку) системы, когда в какую-то дату вместо одного журнала транзакций появляется два, ведущимися разными людьми. Это журналы совпадают до определённой даты, после чего в них начинаются расхождение.
\end{enumerate}

Подводя итоги, Сатоши Накамото (псевдоним, \langen{Satoshi Nakamoto}), автор технологий blockchain и Bitcoin\index{Bitcoin}, сумел предложить работающий децентрализованный механизм, в котором и само поведение системы, и изменения к этой системе проходят через явный или неявный механизм поиска консенсуса участников. Для получения контроля над системой в целом злоумышленнику придётся получить контроль как минимум над 50\% всех мощностей системы (в случае PoW), а без этого можно лишь попытаться ограничить возможность использования системы конкретными участниками.

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

\index{Blockchain|)}