Erlay: протокол эффективного распространения транзакций Биткоина
Наш соотечественник Глеб Науменко, работающий сейчас в Blockstream, разработал новый, более оптимизированный способ распространения транзакций в сети Биткоина, который называется Erlay. Алгоритм позволяет увеличить количество соединений между нодами (что повышает безопасность сети) и при этом снизить трафик, генерируемый передачей транзакций от ноды к ноде, на 40%.
Сеть Биткоина устроена таким образом, что каждая нода получает каждую транзакцию и каждый блок. Когда вы отправляете транзакцию, нода, которая её получает, отправляет её всем нодам, к которым она подключена. Эти ноды рассылают транзакцию всем нодам, к которым они подключены — так транзакция расходится по всей сети. Сейчас это занимает чуть больше 4 секунд.
У такого способа распространения есть несколько недостатков:
1. Ноды в холостую гоняют одни и те же транзакции. Одна может получать одну и ту же транзакцию несколько раз. Эта проблема была частично решена тем, что вместо самих транзакций сначала рассылаются только айдишники — если у ноды нету транзакции с конкретным айдишником, она запросит всю транзакцию.
2. Невозможно увеличить количество соединений между нодами. Различные исследования показывают, что чем больше соединений между нодами в P2P-сети, тем труднее проводить некоторые виды атак. Если сейчас увеличивать количество соединений в сети Биткоина, то сильно вырастет трафик, как раз по большей части из-за спама транзакций.
Именно эти проблемы и решает Erlay.
Биткоин-ноды можно разделить на два типа:
1. Публичные. Это ноды, которые подключаются к другим нодам в сети (исходящие соединений) и позволяют другим нодам подключаться к ним (входящие соединения). По умолчанию, нода открывает 8 исходящих соединений и принимает до 125 входящих соединений.
2. Приватные. Это ноды, которые подключатся к другим нодам, но входящих соединений не разрешают. Они так же по умолчанию подключаются к 8 другим нодам.
Оба типа имеют 8 исходящих подключений, значит каждая нода отправляет каждую транзакцию на 8 других нод — и в этом как раз и есть главный недостаток текущего способа рассылки транзакций. В идеале, кол-во отправленных транзакции должно быть равно количеству нод N, а в текущей реализации получается 8N.
Именно вот эти 8 исходящих соединений хотелось бы увеличить, чтобы сделать сеть более защищённой, но в текущей реализации сети этого сделать нельзя, потому что это ещё больше увеличит спам транзакциями и трафик, который создаёт нода. Больше трафика — труднее и дороже запускать ноду.
Идея Глеба состоит в том, чтобы сократить спам транзакциями и добавить новый механизм сверки и согласования транзакций между нодами.
Теперь транзакции будут рассылаться только публичными нодами (нодами с большим количеством входящих соединений) и только на 8 исходящих соединений (даже если их отрыто больше). Главная задача тут — снизить трафик и при этом разместить транзакции в сети таким способом, чтобы они располагались близко к нодам. Например, нода может не получить новую транзакцию, но транзакция с высокой вероятность будет у одной из нод, к которым она подключена, или в паре «прыжков» от неё. Это снизит трафик, увеличит безопасность (больше соединений = безопаснее сеть), но ноды будут получать не все транзакции. И это решается с помощью нового алгоритма, который называется Minisketch. Алгоритм построен вокруг структуры данных под названием скетч (sketch). Я не смог найти описание этой структуры данных на русском языке (вероятно они сами её изобрели), поэтому перескажу своими словами.
1. Скетч это структура, оптимизированная для сравнения двух множеств и выявления различий между ними. В данном случае множества состоят из айдишников транзакций.
2. Скетчи хранят множества в запакованном виде. В этом смысле они похожи на хэши, из которых можно восстанавливать исходные данные.
3. Скетчи сравниваются между собой операцией XOR. Результат сравнения — скетч разницы двух множеств.
4. Скетч разницы представляет собой симметрическую разность двух множеств, т. е.
Наш соотечественник Глеб Науменко, работающий сейчас в Blockstream, разработал новый, более оптимизированный способ распространения транзакций в сети Биткоина, который называется Erlay. Алгоритм позволяет увеличить количество соединений между нодами (что повышает безопасность сети) и при этом снизить трафик, генерируемый передачей транзакций от ноды к ноде, на 40%.
Сеть Биткоина устроена таким образом, что каждая нода получает каждую транзакцию и каждый блок. Когда вы отправляете транзакцию, нода, которая её получает, отправляет её всем нодам, к которым она подключена. Эти ноды рассылают транзакцию всем нодам, к которым они подключены — так транзакция расходится по всей сети. Сейчас это занимает чуть больше 4 секунд.
У такого способа распространения есть несколько недостатков:
1. Ноды в холостую гоняют одни и те же транзакции. Одна может получать одну и ту же транзакцию несколько раз. Эта проблема была частично решена тем, что вместо самих транзакций сначала рассылаются только айдишники — если у ноды нету транзакции с конкретным айдишником, она запросит всю транзакцию.
2. Невозможно увеличить количество соединений между нодами. Различные исследования показывают, что чем больше соединений между нодами в P2P-сети, тем труднее проводить некоторые виды атак. Если сейчас увеличивать количество соединений в сети Биткоина, то сильно вырастет трафик, как раз по большей части из-за спама транзакций.
Именно эти проблемы и решает Erlay.
Биткоин-ноды можно разделить на два типа:
1. Публичные. Это ноды, которые подключаются к другим нодам в сети (исходящие соединений) и позволяют другим нодам подключаться к ним (входящие соединения). По умолчанию, нода открывает 8 исходящих соединений и принимает до 125 входящих соединений.
2. Приватные. Это ноды, которые подключатся к другим нодам, но входящих соединений не разрешают. Они так же по умолчанию подключаются к 8 другим нодам.
Оба типа имеют 8 исходящих подключений, значит каждая нода отправляет каждую транзакцию на 8 других нод — и в этом как раз и есть главный недостаток текущего способа рассылки транзакций. В идеале, кол-во отправленных транзакции должно быть равно количеству нод N, а в текущей реализации получается 8N.
Именно вот эти 8 исходящих соединений хотелось бы увеличить, чтобы сделать сеть более защищённой, но в текущей реализации сети этого сделать нельзя, потому что это ещё больше увеличит спам транзакциями и трафик, который создаёт нода. Больше трафика — труднее и дороже запускать ноду.
Идея Глеба состоит в том, чтобы сократить спам транзакциями и добавить новый механизм сверки и согласования транзакций между нодами.
Теперь транзакции будут рассылаться только публичными нодами (нодами с большим количеством входящих соединений) и только на 8 исходящих соединений (даже если их отрыто больше). Главная задача тут — снизить трафик и при этом разместить транзакции в сети таким способом, чтобы они располагались близко к нодам. Например, нода может не получить новую транзакцию, но транзакция с высокой вероятность будет у одной из нод, к которым она подключена, или в паре «прыжков» от неё. Это снизит трафик, увеличит безопасность (больше соединений = безопаснее сеть), но ноды будут получать не все транзакции. И это решается с помощью нового алгоритма, который называется Minisketch. Алгоритм построен вокруг структуры данных под названием скетч (sketch). Я не смог найти описание этой структуры данных на русском языке (вероятно они сами её изобрели), поэтому перескажу своими словами.
1. Скетч это структура, оптимизированная для сравнения двух множеств и выявления различий между ними. В данном случае множества состоят из айдишников транзакций.
2. Скетчи хранят множества в запакованном виде. В этом смысле они похожи на хэши, из которых можно восстанавливать исходные данные.
3. Скетчи сравниваются между собой операцией XOR. Результат сравнения — скетч разницы двух множеств.
4. Скетч разницы представляет собой симметрическую разность двух множеств, т. е.