Цена анархии в результате применения эгоистичных стратегий маршрутизации в сети Lightning Network (автор: Рене Пикхардт)

В этой статье мы анализируем технические ограничения возможных платежей в биткоине, которые можно провести через Lightning Network. Хотя изучение этого вопроса возможно, только если сделать более-менее обоснованные и спорные предположения, мы предлагаем рассматривать естественную перегруженность сети и истощение ликвидности каналов в результате применения эгоистичных стратегий маршрутизации как важный источник отказов платежей и, как следствие, снижения надежности сети. Хотя концепция цены анархии в процессе эгоистичной маршрутизации хорошо известна, она не совсем соответствует ситуации, сложившейся в Lightning Network. Обычно, когда встает вопрос о перегруженности сети и цене анархии, рассматриваются каналы с определенной ограниченной пропускной способностью. Если провести аналогию с дорогой, то получится, что даже при сильных заторах некоторое (произвольное) количество машин может проехать в одном направлении, если время проезда не ограничено. Но в Lightning Network платежный канал Алисы будет истощен после того, как она передаст все свои сатоши своему партнеру по каналу Бобу, из-за чего не сможет выполнить дополнительные запросы на передачу (маршрутизацию) платежей Бобу, что приведет к сбоям платежей в сети.

В этой статье мы попытаемся определить цену анархии и перегруженности сети в контексте «модели истощения платежных каналов» в сети Lightning Network. Похоже, истощение каналов возникает не только в результате дисбаланса спроса и предложения на сатоши со стороны узлов сети, но может усиливаться в результате применения эгоистичных стратегий маршрутизации, которые узлы используют для удовлетворения спроса и предложения. Поэтому мы предлагаем определить цену анархии как изменение паттерна распределения ожидаемого расходования ресурсов канала, которое возникает в результате применения эгоистичных стратегий маршрутизации (по сравнению с паттерном распределения при оптимальном централизованном планировании платежей). Исходя из этого определения, мы рассмотрим теоретические последствия использования различных эгоистичных стратегий маршрутизации и обсудим проведение более широкого исследования этой проблемы в будущем, которое также будут учитывать последствия вторичного порядка, в том числе очень ограниченные возможности эгоистичного поведения узлов маршрутизации (что может помочь с контролем потока и борьбой с перегруженностью сети) или реакцию на эгоистичное поведение всех участников сети. Наконец, мы предлагаем изучить и найти равновесие Нэша для доминирующих стратегий узлов в Lightning Network.

Истощение платежных каналов и процент отказов объясняются оттоком ресурсов

В недавнем комментарии @bitromortac оспорил предположение о равномерности, которое используется в анализе вероятностного распределения потоков платежей. Хотя эффективность и польза оптимально надежных и низкозатратных платежных потоков в сочетании с вероятностной доставкой платежей была недавно независимо доказана доктором Карстеном Отто, наблюдения bitromortac согласуются с нашими первоначальными выводами. Еще в 2020 году мы не наблюдали единственного равномерного распределения ликвидности в сети — предположение, которое по умолчанию используется для расчета оптимально надежных и низкозатратных платежных потоков — наоборот, около 30% платежных каналов были исчерпаны. Тогда мы подумали, что это новые или плохо  обслуживаемые каналы. Теперь же, используя методы и идеи «случайного блуждания» и располагая информацией об оттоке (расходовании) ресурсов, мы можем спрогнозировать вероятность исчерпания канала. Это эквивалент ожидаемого процента отказов по платежам в сети. В этом контексте отток (drain) определяется как вероятность движения платежа по каналу в определенном направлении. 

Эту вероятность можно определить, например, путем сбора и оценки статистики маршрутизации при эксплуатации узла или, как показано ниже, оценить, основываясь на эгоистичных стратегиях маршрутизации узлов, просто изучив общедоступные данные. Например, слабый отток на уровне 0,5 означает, что одинаковое количество платежей наблюдалось (или ожидается) в обоих направлениях. И наоборот: сильный отток на уровне 1 означает, что все платежи движутся в одном направлении. То же самое можно сказать и об оттоке на уровне 0, когда платежи движутся в противоположном направлении.

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

Даже при сильном оттоке, например 0,1 (что эквивалентно оттоку 0,9 в противоположном направлении), все еще можно ожидать, что 20% всех платежей будут успешными. Это связано с тем, что маловероятные платежи в направлении, противоположном направлению оттока, будут успешными и приведут к наполнению/реверсии исчерпания канала. Это, в свою очередь, вновь позволит нескольким платежам пройти в направлении предполагаемого или рассчитанного оттока.

Отметим, что ситуацию следует рассматривать более детально и точно. До сих пор мы говорили о случайном платеже вне зависимости от направления, но, конечно, мы можем изучить случайные платежи в направлении предполагаемого оттока или противоположном направлении. Например, при сильном оттоке 0,1 или 0,9 случайный платеж пройдет с вероятностью 20%. Но интуитивно мы можем предположить, что почти все платежи, которые движутся против направления оттока, будут успешными. В соответствии с этой грубой оценкой мы можем аналитически вычислить процент успешных платежей в направлении оттока. Итак, изначально мы имеем 0,1 * 1 + 0,9 * x = 0,2, где 0,1 = 10% платежей, которые движутся в направлении, противоположном оттоку. 1 = 100% успеху этих платежей. 0,9 = 90% случайных платежей, которые движутся в направлении оттока, а x — процент успеха этих платежей. Наконец, 0,2 = наблюдаемые 20% в постоянной части диаграммы. Найдя x, мы определим, что только 11,1…% всех платежей в направлении оттока будут успешными.  

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

Как видите, слабый отток (значения около 0,5) приводит к более низким показателям отказов. И наоборот: сильный отток (значения ближе к 0 или 1) приводит к более высоким показателям отказов. Обратите внимание, что на 3-й и 4-й кривых рассматривалась полученная в результате случайного блуждания стационарная частота отказов, и суммы были выбраны случайным образом (следуя равномерному распределению), от 1 сатоши до определенного процента от размера канала. Как видим, на каналах с сильным оттоком крупные платежи по сути снижают процент отказов. При этом на каналах со слабым оттоком крупные платежи ведут к увеличению процента отказов.

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

Эгоистичные стратегии маршрутизации —  предвестник увеличения оттока ресурсов платежных каналов, отказов платежей и снижения надежности сети. 

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

Обратите внимание: чем быстрее кривая растет относительно 1, тем меньший отток (и процент отказов) мы ожидаем увидеть в сети. Как можно заметить, оптимизация надежности (при условии равномерного распределения путем минимизации затрат, связанных с неопределенностью) позволяет ожидать низкого оттока ресурсов в каналах и, таким образом, более низкой цены анархии. Оптимизация комиссии при текущей структуре комиссии в сети — ведет к усилению оттока ресурсов на гораздо большем количестве каналов, то есть цена анархии увеличится. Примечательно, что цена анархии будет самой высокой, когда узлы используют стратегию, которую мы считаем самой эгоистичной. Она возникла в результате инженерии возможностей в процессе исследования оптимально надежного и низкозатратного платежного потока. В этом случае эгоистичная стратегия оптимизирует как комиссию (снижая ее), так и надежность (повышая ее) (за счет снижения затрат, связанных с неопределенностью). Хотя в отдельных случаях эта стратегия кажется очень перспективной для узла-отправителя, ее повсеместное распространение приведет к истощению большего количества каналов. Это впоследствии приведет к повышению частоты отказов и снижению надежности сети и — как уже говорилось — к самой высокой цене анархии (среди рассмотренных четырех стратегий). 

Конечно, эти теоретические наблюдения не учитывают последствия второго порядка, которые могут возникать на практике, например:

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

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

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

Наконец, в рамках программы Summer of Bitcoin я курирую двух студентов (Себастьяна и Кристал, которые любезно и критически прорецензировали первоначальные черновики этого текста). Они помогут нам понять, как правильно смоделировать и вычислить цену анархии в сети Lightning Network и, возможно, даже определить доминирующие стратегии и достичь равновесия Нэша. В результате первых обсуждений и объяснения студентам моего видения этих проблем я и разработал описанный предварительный способ определения цены анархии для передачи сатоши в сети Lightning Network при использовании эгоистичных стратегий, описанных в этой статье. Продолжающуюся работу по этому вопросу и ее результаты можно найти в репозитории lnresearch.