Skip to main content

Алгоритмы выборов NPoS

Алгоритмы выборов NPoS​

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

  1. Максимизация общей суммы на кону.
  2. Максимизация ставки за валидатором с минимальной ставкой.
  3. Минимизация дисперсии ставки в наборе.
заметка

Последовательная фрагментация, Phragmms and Балансировка звезд несколько известных алгоритмов, используемых для вычисления решений NPoS в Bitzal и Ogona.

Что такое последовательный метод Фрагмена?​

Последовательный метод Фрагмена - это метод выборов с несколькими победителями, введенный Эдвардом Фрагменом в 1890-х годах. Приведенная ниже цитата взята из ссылки Бумага Phragmén подводит итог цели последовательного метода Фрагмена:

заметка

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

Выборы Валидаторов​

Последовательный фрагмен - это один из методов, используемых в схеме Nominated Proof-of-Stake для избрания валидаторов на основе их собственной доли и доли, которая передается им от номинаторов. Он также пытается выровнять веса между валидаторами после каждого раунда выборов.

Фрагмен вне цепи​

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

Ставки майнеров

Процесс вычисления оптимального решения для выборов NPoS может быть делегирован Ставке Майнеров.

Выборы совета​

Deprecated in Bitzal TrueGov

Phragmen was used for Council elections in Governance v1.

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

Что это значит для операторов узлов?​

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

Вы можете использовать этот оффлайн-фрагмен инструмент для прогнозирования результатов выборов валидатора перед новыми выборами.

Понимание Фрагмена​

В этом разделе подробно рассказывается о последовательном методе Фрагмена и приводятся примеры.

Фрагмен Основы​

Рационализация​

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

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

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

Алгоритм, который мы здесь называем "Basic Phragmén" был впервые описан Брилем и др. в статье et al. их работе "Методы голосования Фрагмена и обоснованное представительство".

Алгоритм​

Метод Phragmén будет выполнять итерации, выбирая по одному месту за раз, в соответствии со следующими правилами:

  1. Избиратели подают свои бюллетени, отмечая, каких кандидатов они одобряют. Бюллетени не могут быть изменены после подачи.
  2. Для каждого бюллетеня устанавливается начальная нагрузка, равная 0..
  3. Кандидат, получивший следующее свободное место, - это тот, за кого проголосуют его сторонники будет иметь наименьшую среднюю (средняя) стоимость если этот кандидат победит.
  4. n бюллетени, утвердившие победившего кандидата, получают 1/n добавленного к своей нагрузке.
  5. Нагрузка всех бюллетеней, поддержавших победителя этого раунда, усредняется так, чтобы они были равны.
  6. Если есть еще места, вернитесь к шагу 3. В противном случае выбор заканчивается.

Пример​

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

Открытые места: 3

Кандидаты:   A B C D  L0
-------------------------
Выборщик V1:       X      0
Выборщик V2:         X X  0
Выборщик V3:       X   X  0
Выборщик V4:     X X      0
Выборщик V5:       X X X  0

В этом примере мы видим, что выборщик V1 одобряет только кандидатуру B, выборщик V2 одобряет кандидаты C и D, и т.д. Vвыборщики могут утвердить любое количество кандидатов от 1 до number_of_candidates - 1. Первоначальная "загрузка" из 0 устанавливается для каждого бюллетеня (L0 = загрузка после раунда 0, т.е. "раунд" b предшествующий первому раунду). Вскоре мы увидим, как этот массив обновляется и используется для отбора кандидатов.

Теперь мы проведем итерационный алгоритм, каждая итерация которого соответствует одному "месту". Поскольку мест три, мы пройдем три раунда.

В первом туре победителем будет считаться кандидат, набравший наибольшее количество голосов. Поскольку все загрузки равны, наименьшую среднюю загрузку получит кандидат с наибольшим n, поскольку 1/n будет становится меньше по мере того, как n увеличивается. Например, в первом раунде кандидат A за них проголосовал один избиратель. Таким образом, средняя нагрузка на кандидата А составляет 1/1, или 1. Кандидат С имеет два Одобрительных бюллетеней, поэтому средняя загрузка составляет 1/2. Кандидат B имеет самую низкую среднюю загрузку, при 1/4 и они получают первое место. Нагрузка на бюллетени теперь усредняется, хотя для первой итерации это не окажет никакого влияния.

Заполненные места: 1 (B)
Открытые места: 2

Кандидаты:   A B C D  L0 L1
-----------------------------
Выборщик V1:       X      0  1/4
Выборщик V2:         X X  0  0
Выборщик V3:       X   X  0  1/4
Выборщик V4:     X X      0  1/4
Выборщик V5:       X X X  0  1/4

Теперь у нас осталось всего несколько кандидатов A, C, и D на два свободных места. Есть только один выборщик (V4) для A, с загрузкой 1/4. C имеет 2-х выборщиков, V2 и V5, с большим количеством 0 и 1/4. D имеет трех выборщиков, одобряющих их, V2, V3, и V5, с большим количеством0, 1/4, и 1/4, соответственно.

Если кандидат A выигрывает, средняя загрузка составит (1/4 + 1/1) / 1, или 5/4. Если кандидат C побеждает, средняя загрузка составит ((0 + 1/2) + (1/4 + 1/2)) / 2, или 5/8. Если кандидат D побеждает, средняя загрузка составит ((0 + 1/3) + (1/4 + 1/3) + (1/4 + 1/3)) / 3, или 1/2. Поскольку 1/2 средняя загрузка наименьшая, кандидат D побеждает во втором раунде.

Теперь все, кто голосовал за кандидата D имеет среднюю загрузку, 1/2 всех загрузок.

Заполненные места: 2 (B, D)
Открытые места: 1

Кандидаты:   A B C D  L0 L1  L2
---------------------------------
Выборщик V1:       X      0  1/4 1/4
Выборщик V2:         X X  0  0   1/2
Выборщик V3:       X   X  0  1/4 1/2
Выборщик V4:     X X      0  1/4 1/4
Выборщик V5:       X X X  0  1/4 1/2

В настоящее время открыто одно место и два кандидата, A и C. Выборщик V4 единственный, кто голосует за A, так что если A выигрывает, то средняя загрузка составит (1/4 + 1/1) / 1, или 5/4. Выборщики V2 и V5 (оба с загрузкой 1/2) поддерживают C, так что если C выигрывает, то средняя загрузка составит ((1/2 + 1/2) + (1/2 + 1/2)) / 2, или 1. Поскольку средняя загрузка будет ниже при C, C выигрывает финальное место.

Заполненные места: 3 (B, D, C)
Открытые места: 0

Кандидаты:   A B C D  L0 L1  L2  L3
------------------------------------
Выборщик V1:       X      0  1/4 1/4 1/4
Выборщик V2:         X X  0  0   1/2 1
Выборщик V3:       X   X  0  1/4 1/2 1/2
Выборщик V4:     X X      0  1/4 1/4 1/4
Выборщик V5:       X X X  0  1/4 1/2 1

Интересная особенность этого расчета заключается в том, что общая загрузка всех избирателей всегда будет равна числу мест, заполненных в данном раунде. В нулевом туре загрузка начинается с 0 и нет заполненных мест. После первого тура общая сумма всех загрузок составляет 1, после второго раунда это 2, и т.д.

Взвешенный Фрагмен​

Рационализация​

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

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

Алгоритм​

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

ПРИМЕЧАНИЕ: с точки зрения выбора валидатора, для следующего алгоритма вы можете представить "выборщиков " как "номинаторов" а "кандидатов " "валидаторами".

  1. Кандидаты избираются по одному в каждом раунде и добавляются к числу успешных кандидатов (они получили "место"). Этот аспект алгоритма очень похож на базовый "алгоритм Фрагмена" описанный выше.
  2. Однако по мере избрания кандидатов строится взвешенное отображение, определяющее веса каждого выбора валидатора каждым номинатором.

Если говорить более подробно, то алгоритм работает следующим образом:

  1. Создаем список всех выборщиков, их общую сумму ставки и какие валидаторы они поддерживают.
  2. Генерируем начальный граф с взвешенными границами, отображающий избирателей на кандидатов, где вес каждой границы является общим потенциальным весом (ставкой), присвоенный этим выборщиком. Сумма всех потенциальных весов для данного кандидата называется его ставкой на утверждение.
  3. Теперь мы начинаем выбирать кандидатов. Для списка всех кандидатов, которые не были избраны, получим их рейтинг, который равен 1 / доля_одобрения.
  4. Для каждого выборщика обновляем оценку каждого кандидата, которого он поддерживает, путем сложения его общего бюджета (ставки), умноженного на загрузку выборщика, а затем деля его на ставку одобрения кандидата (voter_budget * voter_load / candidate_approval_stake).
  5. Выбираем кандидата с наименьшим количеством баллов и избираем его. Исключаем избранного кандидата из числа потенциальных кандидатов.
  6. Обновляется загрузка для каждой границы, соединяющей с победившим кандидатом, при этом загрузка границы устанавливается равной оценке кандидата минус загрузка выборщиков, а загрузка выборщиков устанавливается в значение оценки кандидата.
  7. Если нужно избрать больше кандидатов, переходим к шагу 3. В противном случае переходим к шагу 8.
  8. Теперь доля распределяется между всеми номинаторами, которые поддержали хотя бы одного избранного кандидата. Ставка поддержки для каждого кандидата рассчитывается путем взятия бюджета выборщика и умножения на загрузку границы, затем деления на загрузку кандидата. (voter_budget * edge_load / candidate_load).

Пример​

Примечание: Все числа в этом примере округлены до трех знаков после запятой.

В следующем примере есть пять выборщиков и пять кандидатов, претендующих на три потенциальных места. Каждый выборщик V1 - V5 имеет сумму ставки, равную их количеству (например, V1 имеет ставку 1, V2 имеет ставку 2, и т.д.). Каждый выборщик также будет иметь загрузку, которая изначально начинается с 0.

Заполненные места: 0
Открытые места: 3

Кандидаты:    A B C D E  L0
----------------------------
Выборщик V1 (1):  X X        0
Выборщик V2 (2):  X X        0
Выборщик V3 (3):  X          0
Выборщик V4 (4):    X X X    0
Выборщик V5 (5):  X     X    0

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

Кандидат A: 1 + 2 + 3 + 5 = 11
Кандидат B: 1 + 2 + 4 = 7
Кандидат C: 4 = 4
Кандидат D: 4 + 5 = 9
Кандидат E: 0

Первый шаг прост - кандидат E имеет 0 голосов, и с этого момента его можно игнорировать. Он никогда не будет избран.

Теперь мы можем рассчитать начальные баллы кандидатов, а именно 1 / approval_stake:

Кандидат A: 1 / 11 = 0.091
Кандидат B: 1 / 7 = 0.143
Кандидат C: 1 / 4 = 0.25
Кандидат D: 1 / 9 = 0.111
Кандидат E: N/A

Для каждой границы мы вычисляем результат, который равен текущему результату плюс общий бюджет * загрузка выборщика, деленная на долю одобрения кандидата. Однако, поскольку загрузка каждого избирателя начинается с 0, и все, что умножается на 0, равно 0, любое добавление будет 0 / x, или 0. Это означает, что данный шаг можно смело игнорировать для начального раунда.

Таким образом, наилучший (наименьший) результат в раунде 0 имеет кандидат А, набравший 0.091.

Кандидаты:    A B C D E  L0 L1
----------------------------------
Выборщик V1 (1):  X X        0  0.091
Выборщик V2 (2):  X X        0  0.091
Выборщик V3 (3):  X          0  0.091
Выборщик V4 (4):    X X X    0  0
Выборщик V5 (5):  X     X    0  0.091
Заполненные места: 1 (A)
Открытые места: 2

Кандидат:    A B C D E  L0
----------------------------
Выборщик V1 (1):  X X        0
Выборщик V2 (2):  X X        0
Выборщик V3 (3):  X          0
Выборщик V4 (4):    X X X    0
Выборщик V5 (5):  X     X    0

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

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

Любой выборщик, у которого один из кандидатов занял место в этом туре (т.е. выборщики V1, V2, V3, и V5, которые голосовали за A) будет увеличена загрузка. Такая загрузка приглушит влияние их голосов в будущих раундах, а граница (которая будет использоваться при определении распределении ставок в дальнейшем) устанавливается равным баллу избранного кандидата минус текущей загрузки выборщика.

edge_load = elected_candidate_score - voter_load
voter_load = elected_candidate_score

В этом случае баллы избранного кандидата составляют 0.091 а загрузка выборщиков - все 0. Итак, для каждого выборщика, проголосовавшего за A, мы рассчитаем новую загрузку границы Выборщика -> A of:

Загрузка границы: 0.091 - 0 = 0.091

и новая загрузка выборщиков, равная:

Загрузка выборщиков: 0.091

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

Кандидат B : 0.143
Кандидат C : 0.25
Кандидат D : 0.111

Теперь мы проходим по взвешенному графу и обновляем оценку кандидата и загрузку границы, используя алгоритм:

candidate_score = candidate_score + ((voter_budget * voter_load) / candidate_approval_stake)

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

V1 обновляет B до 0.156
V2 обновляет B до 0.182
V4 обновляет B до 0.182
V4 обновляет С до 0.25
V4 обновляет D до 0.111
V5 обновляет D до 0.162

После обновления оценок окончательные баллы кандидатов в этом раунде составляют:

Кандидат B: 0.182
Кандидат C: 0.25
Кандидат D: 0.162

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

Затем мы обновляем загрузку для избирателей и границ, как указано выше, для всех выборщиков, которые проголосовали за кандидата D (визируем., V4 и V5) по той же формуле, что и выше.

Заполненные места: 2 (A, D)
Открытые места: 1

Кандидаты:    A B C D E  L0 L1    L2
-----------------------------------
Выборщик V1 (1):  X X        0  0.091 0.091
Выборщик V2 (2):  X X        0  0.091 0.091
Выборщик V3 (3):  X          0  0.091 0.091
Выборщик V4 (4):    X X X    0  0     0.162
Выборщик V5 (5):  X     X    0  0.091 0.162

Следуя аналогичному процессу для 2 раунда, мы начинаем с начальных оценок кандидатов, равных:

Кандидат B : 0.143
Кандидат C : 0.25

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

V1 обновляет B до 0.156
V2 обновляет B до 0.182
V4 обновляет B до 0.274
V4 обновляет С до 0.412

С самым низким показателем 0.274, Кандидат B претендует на последнее свободное место. Кандидаты A, D, и B были избраны, а кандидаты C и E нет.

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

Заполненные места: 3 (A, D, B)
Открытые места: 0

Кандидаты:    A B C D E  L0 L1    L2    L3
------------------------------------------
Выборщик V1 (1):  X X        0  0.091 0.091 0.274
Выборщик V2 (2):  X X        0  0.091 0.091 0.274
Выборщик V3 (3):  X          0  0.091 0.091 0.091
Выборщик V4 (4):    X X X    0  0     0.162 0.274
Выборщик V5 (5):  X     X    0  0.091 0.162 0.162

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

В этом примере взвешенный график выглядит следующим образом:

Номинатор: V1
	Граница с загрузкой A= 0.091
	Загрузка от границы до границы B= 0.183
Номинатор: V2
	Граница с загрузкой A = 0.091
	Загрузка от границы до B = 0.183
Номинатор: V3
	Загрузка от границы до А = 0.091
Номинатор: V4
	Загрузка от границы до B = 0.113
	Загрузка от границы до B = 0.162
Номинатор: V5
	Загрузка от границы до А = 0.091
	Загрузка от границы до D = 0.071

Например, бюджет V1 составляет 1, загрузка границы до A составляет 0.091, а загрузка выборщиков составляет 0.274. Используя наше уравнение:

backing_stake (A) = voter_budget * edge_load / voter_load

Мы можем заполнить эти переменные с помощью:

backing_stake (A) = 1 * 0.091 / 0.274 = 0.332

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

backing_stake (B) = 1 * 0.183 / 0.274 = 0.668

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

Итоговые результаты:

A избирается с долей 6.807.
D избирается с долей 4.545.
B избирается с долей 3.647.

V1 поддерживает: A с долей: 0.332 и B с долей: 0.668.
V2 поддерживает: A с долей: 0.663 и B с долей: 1.337.
V3 поддерживает: A с долей: 3.0.
V4 поддерживает: B с долей: 1.642 и D с долей: 2.358.
V5 поддерживает: A с долей: 2.813 и D с долей: 2.187.

Вы заметите, что общая сумма ставки для кандидатов A, D, и B равна (за исключением суммарной ставке всех выборщиков). (1 + 2 + 3 + 4 + 5 = 15). Это потому что у каждого выборщика хотя бы один из кандидатов занял место. Любой выборщик, не выбравший ни одного из своих кандидатов, не будет иметь никакой доли в любом из избранных кандидатов.

Оптимизации​

Результаты для номинирования валидаторов далее оптимизируются для нескольких целей:

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

Высокоуровневое описание​

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

Чтобы минимизировать время вычислений блока, процесс стакинга выполняется как внецепочечный работник. Для того чтобы чтобы дать время для работы этого внецепочечного работника, команды стейкинга (bond, nominate и т. д.) не разрешены в последнюю четверть каждой эпохи.

Эти оптимизации не будут подробно рассмотрены на этой странице. Для получения более подробной информации вы можете просмотреть Rust проведение выборов в Matter, the Rust Проведение стейкинга в Matter, or the seqPhragménwithpostprocessing метод в Эталонной реализации на языке Python. Если вы хотите погрузиться еще глубже, вы можете ознакомиться с globalsageblockchain Страница исследования Метода Фрагмена.

Обоснование необходимости минимизации числа проверяющих на одного претендента​

Выплата наград за стейкинг от каждого валидатора всем их номинаторам может потребовать нетривиального объема ресурсов сети (в терминах места в блокчейне и вычислительных ресурсов). Предположим, существует система с 200 валидаторами и 1000 номинаторами, где каждый из номинаторов выбрал 10 различных валидаторов. Выплата в таком случае потребует 1_000 * 10, то есть 10_000 транзакций. В идеальной ситуации если каждый номинатор выбирает одного валидатора, потребуется лишь 1_000 транзакций — на порядок меньше. На практике, замедление сети в начале эры происходило из-за большого числа индивидуальных выплат от валидаторов номинаторам. В экстремальных случаях это может стать вектором атаки на систему, где номинаторы выбирают множество разных валидаторов с небольшими суммами стейкинга, чтобы замедлить систему при смене эры.

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

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

Обоснование для поддержания равномерного распределения долей​

Другая проблема заключается в том, что мы хотим обеспечить как можно более равномерное распределение голосов между избранными валидаторами или членами совета. Это помогает нам повысить безопасность системы за счет того, что гарантируя, что минимальное количество токенов для вступления в активный набор валидаторов или совет будет как можно выше. Например, предположим, что в результате было избрано пять валидаторов, а валидаторы имеют следующую долю: {1_000, 20, 10, 10, 10}, для общей ставки 1_050. В этом случае потенциальный злоумышленник может присоединиться к активному набору валидаторов, имея всего 11 токенов, и может получить большинство валидаторов, имея всего 33 токена (поскольку атакующий должен иметь достаточную ставку, чтобы "выгнать" три самых слабых валидатора).

Для сравнения, представьте себе другой результат при той же сумме общей ставки, но при этом эта ставка распределена совершенно одинаково: {210, 210, 210, 210, 210}. При той же сумме ставки злоумышленнику потребуется поставить 633 токена, чтобы получить большинство валидаторов, что гораздо дороже. Хотя получение равного распределения маловероятно, чем более равное распределение, тем выше порог - и, следовательно, выше затраты - для злоумышленников, чтобы проникнуть в систему.

Обоснование сокращения времени вычисления блоков​

Выполнение алгоритма Фрагмена занимает много времени и часто не может быть завершено в течение производства одного блока. Ожидание завершения вычислений поставило бы под угрозу постоянное время производства блоков в сети. Поэтому как можно больше вычислений переносится на внецепочечного рабочего, валидаторы которого могут работать над проблемой, не влияя на время производства блоков.

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

Фрагмы (также известные как балфрагмы)​

Фрагмы, ранее известные как Балфрагмы, это новое правило выборов, вдохновленное Фрагменом и разработанное собственными силами для Bitzal. В целом, правила выборов на блокчейне - активная тема для исследований. Это связано с противоречивыми требованиями к правилам выборов и блокчейну: выборы требуют больших вычислительных затрат, а блокчейн ограничен в вычислениях. Таким образом, данная работа представляет собой современное состояние в области оптимизации.

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

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

Максиминная цель поддержки и PJR​

Это новое правило выборов направлено на достижение гарантии аппроксимации с постоянным коэффициентом для максиминной цель поддержки и тесно связанное с ним пропорциональное обоснованное представительство (PJR).

Цель максимизации поддержки основана на максимизации поддержки наименее поддерживаемого избранного кандидата или, в случае Bitzal и Ogona, максимизации наименьшей поддержки среди избранных валидаторов. Эта цель, основанная на безопасности, означает гарантию безопасности для NPoS и затрудняет избрание узлов-валидаторов китами недоброжелателей. Фрагммы их правило и гарантии, которые оно предоставляет в плане безопасности и пропорциональности, были формализованы в рецензируемом документе).

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

Сравнение последовательных Фрагменов, ММС и Фрагм​

Последовательный Фрагмен (seqPhragmen) и MMS два эффективных правила выборов, которые достигают PJR.

В настоящее время в Bitzal работают seqPhragmen метод для выборов валидатора и совета. Хотя seqPhramen имеет очень быстрое время выполнения, но не обеспечивает аппроксимацию с постоянным коэффициентом для проблемы максиминной поддержки. Это связано с тем, что seqPhramen только выполняет примерное изменение баланса распределение доли.

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

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

Новое правило выборов: Фрагмы​

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

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

  1. Технико-экономическое обоснование,
  2. Баланс и
  3. Локальная оптимальность - наименьшая поддержка ставки A выше, чем самый высокий балл среди неизбранных кандидатов

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

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

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

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

Фрагмы Правило выборов в настоящее время внедряется на Bitzal. После завершения работы оно станет станет одним из самых сложных правил выборов, реализованных на блокчейне. Впервые, это правило выборов обеспечит как справедливое представительство (PJR), так и безопасность (аппроксимация постоянного коэффициента для возражения максимальной поддержки) в сети блокчейн.

Алгоритм​

Алгоритм Фрагм перебирает доступные места, начиная с пустого комитета размером k:

  1. Инициализирует пустой комитет A и нулевой вектор весов границ w = 0.

  2. Повторяется k раз:

    • Находит неизбранного кандидата с наибольшим количеством баллов и добавьте его в комитет A.
    • Перебалансирует весовой вектор w для нового комитета A.

  3. Возвращает A и w.

Внешние ресурсы​