Консенсус

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

Как ноды выпускают точки для консенсуса

Точка — это одна вершина графа. Чтобы сеть сошлась к единому подграфу:

• каждый валидатор выпускает точку, которая ссылается на свою прошлую точку, если она была;
• прикладывает подписи других валидаторов на свою прошлую точку;
• ссылается не менее чем на 2/3 чужих точек прошлого раунда.

Помимо этого каждый валидатор знает лидеров прошлых раундов и лидера текущей волны и указывает их через anchor_proof и anchor_trigger.

Также протокол разрешает делать слабые ссылки на более ранние раунды.

Важно подчеркнуть, что точка содержит подписи других валидаторов для своей предыдущей точки. То есть публикация точки и сбор подписей — асинхронные процессы.

Лидер и волны

Лидер выбирается на волну, а волна — это последовательность из четырёх раундов. Выбор лидера детерминированный: он вычисляется по номеру волны и упорядоченному списку валидаторов, поэтому все честные ноды приходят к одному и тому же лидеру. Если выбранный лидер не входит в текущий набор валидаторов, волна считается “без лидера”.

Внутри волны лидер выпускает ключевые точки:

• candidate (раунд 0);
• proof (раунд 1);
• trigger (раунд 2).

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

• в anchor_proof — на последнюю известную proof точку;
• в anchor_trigger — на последнюю известную trigger.

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

Ссылки и слабые ссылки

Точка обязана:

• иметь ссылки не менее чем на 2/3 известных точек из прошлого раунда (includes);
• указывать последний известный валидатору anchor_proof и anchor_trigger.

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

Как формально определяется принятая история

В каждой волне раундов выбирается лидер; его candidate → proof → trigger образуют якорь. При появлении валидного trigger все честные узлы независимо друг от друга восстанавливают цепочку якорей через anchor_proof:

• От якоря берётся максимально доступный подграф точек, достижимых по includes/witness.
• Этот подграф детерминированно выпрямляется в линейный порядок точек.

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

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

Что должны проверять валидаторы

• В каждом раунде у валидатора не более одной точки;
• includes содержит не менее 2F+1 зависимостей из прошлого раунда;
• evidence содержит подписи от других валидаторов (>= 2F) на предыдущую точку валидатора;
• anchor_proof и anchor_trigger должны ссылаться на корректные лидерские точки соответствующих раундов;
• time строго больше времён зависимостей.

Свойства: финальность, реорганизации, прогресс

• Тип финальности: детерминированная по якорям — после коммита якоря его история не пересматривается;
• Реорганизации: реорганизаций нет;
• Условия прогресса: требуется наличие активного набора валидаторов (≤ F византийских), достижение порогов 2F+1/2F по точкам и подписям, доступность лидера текущей волны;
• Пропускная способность: в первую очередь определяется тем, сколько external сообщений сеть успевает упорядочить за одну волну. На практике она зависит от размера одной вершины и от числа валидаторов.