4.6.5 Bitcoin - новая платежная система

Чтобы реализовать распределенный сервер временных меток на базе peer-to-peer, нам будет нужно использовать систему proof-of-work [10] аналогично с Adam Back's Hashcash [6]. Система proof-of-work использует алгоритм CPP (Client Puzzle Protocol). Система proof-of-work включает в себя поиск кода, который после хэширования, например, посредством SHA-256, имеет некоторого числа нулевых бит. Объем необходимой работы экспоненциально зависит от числа нулевых бит. Хэш легко верифицируется посредством одного хэш-преобразования.

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

Рис. 3.

Proof-of-work решает в большинстве случаев также проблему репрезентации принятия решения. Если большинство базировалось на схеме один IP-адрес-один-голос, оно может быть свергнуто любым, кто может разместить много IP-адресов. Система Proof-of-work принципиально предполагает схему один-ЦПУ-один-голос. Решение большинства представляется самой длинной цепочкой, на которую потрачено более всего усилий proof-of-work. Если большинство вычислительной мощности контролируется честными узлами, честная цепочка будет рости быстрее, обходя любые конкурирующие цепочки. Чтобы модифицировать последний блок, атакер должен заново проделать proof-of-work блока и всех последующих блоков и затем обойти честные блоки. Мы покажем далее, что вероятность медленного атакера настигнуть остальных при формировании последующих блоков падает экспоненциально.

Рис. 3A. Основная последовательность блоков (чёрные) является самой длинной от начального (зелёный) до текущего. Побочные ветви (cерые) отсекаются. (взято из статьи wikipedia)

Чтобы компенсировать увеличивающееся быстродействие оборудования и вариации заинтересованности рабочих узлов со временем, трудность proof-of-work определяется числом генерируемых блоков в час. Если они генерируются слишком быстро, сложность увеличивается.

Сеть

Сеть работает следующим образом:

1. Новые транзакции широковещательно рассылаются всем узлам.
2. Каждый узел собирает новые транзакции в блок.
3. Каждый узел работает над нахождением proof-of-work для своего блока.
4. Когда узел находит proof-of-work, он широковещательно рассылает блок всем узлам.
5. Узлы воспринимают блок, только если все транзакции в нем корректны и не были уже потрачены.
6. Узлы отмечают восприятие блока формированием следующего блока в цепочке, используя хэш принятого блока в качестве предыдущего хэша.

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

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

Стимул

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

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

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

Раз позднейшая транзакция в монете похоронена под достаточным числом блоков, транзакции, потраченные до этого, могут быть удалены, чтобы сэкономить место на диске. Чтобы облегчить это без разрушения хэша блока, транзакции хэшируются согласно дереву Merkle [7][2][5], с корнем, содержащим хэш блока. Старые блоки могут быть минимизированы путем удаления ветвей дерева. Внутренние хэши запоминать не нужно.

Рис.4.

Заголовок блока без транзакций будет иметь около 80 байт. Если мы предположим, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4.2MБ в год. С компьютерной системой, обычно продаваемой с 2ГБ оперативной памяти (2008г), и предсказанием закона Мура роста в 1,2 ГБ в год, память не должна стать проблемой даже, если заголовки блоков должны храниться в памяти.

Упрощенная верификация платежа

Имеется возможность верифицировать платежи без создания сети узлов. Пользователю только нужно иметь копию заголовков блоков самой длинной proof-of-work цепочки, которую он может получить, запрашивая узлы сети пока не убедится в том, что его цепочка длиннее, и получил ветвь Merkle, соединяющую транзакцию с блоком. Он не может проверить транзакцию сам, но связав ее с местом в цепочке, он может понять, что узел сети воспринял ее и блоки, добавленные позднее, подтверждают признание ее сетью.

Рис.5.

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

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

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

Конфиденциальность

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

Рис. 6

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

Вычисления

Для уменьшения размера БД используется древовидное хэширование. Мы рассматриваем сценарий, когда атакер пытается генерировать альтернативную цепочку быстрее, чем это делается для истинной цепочки. Такая попытка возможна, если атакер пользуется услугами мощной botnet. Даже если это выполнено, это не открывает систему для произвольных изменений, таких как, например, изъятие денег непринадлежащих атакеру. Узлы не воспринимают некорректные транзакции в качестве платежа, и честные узлы никогда не примут блок, их содержащие. Атакер может только попытаться изменить одну из своих собственных транзакций, чтобы вернуть деньги, которые он потратил.

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

Вероятность того, что атакер сможет нагнать разрыв, аналогична вероятности в задаче разорения игрока Gambler's Ruin problem. Предположим игрок с неограниченным кредитом начинает, имея долг, и участвует в неограниченном числе попыток, чтобы добиться отыгрыша. Мы можем вычислить вероятность того, что он когда-то отыграется, или того, что атакер сможет сформировать цепочку, длиннее честной, в соответствии с [8]:

p = вероятность нормального узла найти следующий блок
q = вероятность атакеру найти следующий блок
q_z = вероятность того, что атакер сможет догнать, находясь на z блоков позади

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

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

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

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

λ = zq/p

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

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

Преобразуем в C-код...

#include 
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}

Популярность платежной системы Bitcoin растет (см. "3 reasons bitcoins aren't in your wallet yet", Zach Miners, December 9, 2013). Но проблемы безопасности ограничивают ее более широкое использование. Банки пока держатся в стороне.

В 2016 году 4 из пяти крупнейших банков мира решили в экспериментальном порядке осваивать технологию криптовалюты.

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

22 мая 2010 года программист из штата Флорида Ласло Ханич купил две пиццы за 10 000 биткойнов (примерно $5 000 000 по текущему курсу). Это стало первой в истории покупкой, оплаченной в биткойнах. На рис. 7 представлено распространение bitcoin в мире во втором полугодии 2014 года.

Рис. 7. Распространение Bitcoin в мире (вторая половина 2014г)

47% ИТ-технологов полагают, что криптовалюты типа bitcoin (например, XPR и Dogecoin) становятся реальной альтернативой традиционных денег. К концу 2015 года в мире имели хождение более десятка видов криптовалют (общее число их разновидностей достигает 2000): Litecoin, Peercoin, Namecoin, QuarkCoin, Primecoin, NovaCoin, Zetacoin, DigitalCoin и др.

В 2016 году начала распространяться технология blockchain, которая совместима с Bitcoin, Litecoin, Dogecoin и другими криптовалютами (см. "Blockchain: The smart person's guide", Dan Patterson, September 19, 2016). Смотри также журнал Chip N1, 2017, стр. 72-73. права всех участников и банков равны, - blockchain не принадлежит никому (данные никто конкретно не может стиреть), а пользоваться им могут все. Если даже bitcoin выйдет из употребления blockchain сохранится. Blockchain - высоконадежная система, так как данные там хранятся распределеннным образом.

В Абу Даби для безопасного обмена при голосовании используется техника blockchain (см. "Abu Dhabi Securities Exchange uses blockchain for e-voting", Karl Flinders, 18 Oct 2016),

Компания SBI Securities тестирует совместно с IBM Japan технику blockchain для случая bitcoin (см. "IBM and SBI Securities test bond trading on the blockchain", Conner Forrest, October 21, 2016). Целью совместного исследования является возможность безопасного коммерческого использования данной технологии.

На рис. 8 показана поквартальная динамика платежей в bitcoin для разных регионов в 2014-15 гг.

Рис. 8. Динамика платежей в bitcoin

На рис. 9 показан рост числа банкоматов bitcoin в 2015-16 гг. Эти машины позволяют конвертировать доллары в bitcoin. Но росту их числа препятствует высокая стоимость этих операций - 10%.

Рис. 9. Рост числа ATM для bitcoin

В blockchain для bitcoin на конец 2016 года содержится 91,4 ГБ блоков. На рис. 10 представлена динамика для людей, ищущих работу в сфере bockchain и криптовалюты (голубая линия); красная линия - запросы предпринимателей (см. Bitcoin prices plummet, along with interest in blockchain, cryptocurrency jobs.

Рис. 10. Bitcoin в США в 2016-18

Ссылки

[1] Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System" (2009)

[2] W. Dai, "b-money," http://www.weidai.com/bmoney.txt, 1998.

[3] H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.

[4] S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.

[5] D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.

[6] S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.

[7] A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.

[8] R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.

[9] W. Feller, "An introduction to probability theory and its applications," 1957.

[10] http://ru.wikipedia.org/wiki/Bitcoin

[11] http://en.wikipedia.org/wiki/Proof-of-work_system

[12]