Чтобы облегчить представление алгоритма, было сделано предположение, что процессы повторяют в каждом раунде сообщения, которые они посылали в более ранних раундах. Поскольку корректные процессы записывают сообщения, полученные в более ранних раундах, это не нужно, поэтому достаточно послать каждое сообщение только. Таким образом, каждый корректный процесс посылает каждое из N+1 возможных сообщений другому процессу самое большее один раз, что ограничивает сложность по сообщениям величиной . Так как имеется только N+1 различных сообщений, каждое сообщения должно содержать только O (log N) бит.
Если число процессов превышает 3t + 1, для выполнения алгоритма выбирается совокупность 3t активных помощников. (Выбор выполняется статически, например, выбирая 3t процессов, чьи имена следуют за g в порядке имен процессов. Командующий и активные помощники сообщают пассивным помощникам о своем решении, и пассивные помощники останавливаются на значении, которое они получают от более t процессов. Сложность по сообщениям этого послойного подхода - , и разрядная сложность - .
14.2 Протоколы с Установлением Подлинности
Злонамеренное поведение, рассматриваемое до сих пор включало неправильную пересылку информации в дополнение к посылке неправильной информации о собственном состоянии процесса. К счастью, это чрезвычайно злонамеренное поведение Византийских процессов может быть ограничено с помощью криптографических средств, которые сделали бы Теорему 14.1 недействительной. Действительно, в сценариях, используемых в ее доказательстве, сбойные процессы посылали бы сообщения как в сценарии 1, получив только сообщения сценария 0.
В этом разделе предполагается наличие средства для цифровой подписи и установления подлинности сообщений. Процесс p, посылающий сообщение М, добавляет к этому сообщению некоторую дополнительную информацию , которая называется цифровой подписью p для сообщения М. В отличие от рукописных подписей, цифровая подпись зависит от М, что делает бесполезным копирование подписи в другие сообщения. Схема подписи удовлетворяет следующим свойствам.
(1) Если p корректен, только p может правдоподобно вычислить . Это вычисление - подпись сообщения M.
(2) Каждый процесс может эффективно проверять (имея p, М и S) . Эта проверка - установление подлинности сообщения M.
Схемы подписи основаны на частных и общих ключах. Первое предположение не исключает того, что Византийские процессы могут открыть свои секретные ключи друг другу, что позволяет одному Византийскому процессу подделать подпись другого. Предполагается, что только корректные процессы хранят свои частные ключи в секрете.
Мы изучим реализацию схем подписи в Подразделах с 14.2.2 по 14.2.5. В следующем подразделе, сообщение <msg>, подписанное процессом p, то есть, пара, содержащая <msg> и , обозначается <msg> : p.
14.2.1 Протокол Высокой Степени Восстановления
Эффективный Византийский алгоритм вещания, использующий полиномиально много сообщений и t+1 импульсов, был предложен Долевом и Стронгом [DS83]. Установление подлинности, используемое в этом протоколе, разрешает неограниченную способность восстановления. Мы заметим, тем не менее, что могут отказать не более N процессов (из N), и N процессов отказывают, все требования примитивно удовлетворяются; следовательно пусть t < N. Их протокол основан на более раннем, предложенном Лампортом, Шостаком и Пизом [LSP82], который является экспоненциальным по числу сообщений. Мы представляем сначала последний протокол.
В импульсе 1 командующий “выкрикивает” сообщение <value, > : g, содержащее свой (подписанный) вход.
В импульсах со 2 по t + l процессы подписывают и пересылают сообщения, которые они получили в предыдущем импульсе; следовательно, сообщение, которым обмениваются в импульсе i, содержит i подписей. Сообщение <value, v> : g : : ... : называется действительным (имеющим силу) для получающего процесса p, если справедливо следующее.
(1) Все i подписей корректны.
(2) i подписей от i различных процессов.
(3) p не встречается в списке подписей.
В течение алгоритма, процесс p содержит множество значений, содержащихся в действительных сообщениях, полученных p; первоначально это множество пусто, и значение каждого действительного сообщения вставляется в него.
Сообщения, пересылаемые в импульсе i - в точности те действительные сообщения, полученные в предыдущем импульсе. В конце импульса t + 1, процесс p принимает решение основанное на . Если состоит из одиночного элемента {v}, p принимает решение v, иначе p принимает решение значения по умолчанию (например, 0). Чтобы сэкономить на числе сообщений, p пересылает сообщение <value, v> : g : : ... : : p только процессам, не встречающимся в списке g, , ..., . Эта модификация не имеет никакого влияния на поведение алгоритма, так как для процессов в списке сообщение не действительно.
Теорема 14.10 Алгоритм Лампорт, Шостака и Пиза - корректный Византийский алгоритм вещания при t < N, использующий t + 1 импульс.
Доказательство. Все процессы принимают решение в импульсе t + 1, что подразумевает и завершение и одновременность алгоритма.
Если командующий корректен и имеет вход v, все процессы получают его сообщение <value, >: g в импульсе 1, так что все корректные процессы включают v в W. Никакое другое значение не вставляется в W, так как никакое другое значение никогда не подписывается командующим. Следовательно, в импульсе t + 1 все процессы имеют W = {v} и останавливаются на v, что означает зависимость.
Чтобы показать соглашение, мы получим, что для корректных процессов p и q, в конце импульса t + 1. Предположим, в конце импульса t + 1, и пусть i - импульс, в котором p вставил v в Wp, по получении сообщения <value, v> : g : : ... : .
Случай 1: Если q встречается в g, , ..., , то q сам видел значение v и вставил его в .
Случай 2: Если q не встречается в последовательности g, , ..., и , то p пересылает сообщение <value, v>: g : : ... : : p процессу q в импульсе i + i, так что q утверждает (придает силу) v самое позднее в импульсе i + 1.
Случай 3: Если q не встречается в последовательности g, , ..., , и i = t + 1, заметьте, что сообщение, полученное p, было подписано t + l последовательными процессами, включая по крайней мере один корректный процесс. Этот процесс переслал сообщение всем другим процессам, включая q, так что q видит v.
Так как к концу импульса t + 1, p и q принимают одинаковое решение. o
Завершить алгоритм ранее импульса t + 1 невозможно. Во всех импульсах до t, корректный процесс мог бы получать сообщения, созданные и пересланные только сбойными процессами, и не посланные другим корректным процессам, что могло бы вести к противоречивым решениям.
Промежуточный результат предыдущего алгоритма, а именно соглашение о множестве значений среди всех корректных процессов, более сильное, чем необходимо для достижения соглашения об одиночном значении; Это было замечено Долевом и Стронгом [DS83], которые предложили более эффективную модификацию. Фактически достаточно, что в конце импульса t + 1, или (a) для каждого корректного p множество - один и тот же одиночный элемент, или (b) ни для какого корректного p множество не является одиночным элементом. В первом случае все процессы принимают решение v, в последнем случае они все принимают решение 0 (или, если желательно изменить алгоритм таким образом, они принимают решение "командующий сбойный").
Алгоритмом Долева и Стронга достигается более слабое требование на множества W. Вместо того, чтобы передавать каждое действительное сообщение, процесс p пересылает самое большее два сообщения, а именно одно сообщение с первым и одно сообщение со вторым значением, принятым p. Полное описание алгоритма оставлено читателю.
Теорема 14.11 Алгоритм Долева и Стронга, описанный выше - протокол Византийского-вещания, использующий t + 1 импульс и самое большее сообщений.
Доказательство. Завершение и одновременность доказываются, как в предыдущем протоколе, так как каждый корректный процесс принимает решение в конце импульса t + 1. Зависимость выводится так же, как в предыдущем протоколе. Если g правильно “выкрикивает” v в первом импульсе, все корректные процессы принимают v в этом импульсе, и никакое другое значение никогда не принимается; следовательно, все корректные процессы останавливаются на v. Заявленная сложность по сообщениям следует из факта, что каждый (корректный) процесс “выкрикивает” самое большее два сообщения.
Чтобы показать соглашение, мы покажем, что для корректных процессов p и q, и удовлетворяют в конце импульса t + 1 следующему.
(1) Если , то .
(2) Если , то .
Для (1): Предположим, что p принял значение v после получения сообщения <value, v>: g : : ... : в импульсе i, и рассуждаем как в доказательстве Теоремы 14.10:
Случай 1: Если q встречается среди g, , ..., , q точно принял v.
Случай 2: Если q не встречается среди g, , ..., , и , , то p пересылает значение процессу q, который примет его в этом случае.
Случай 3: Если q не встречается и i = t + 1, по крайней мере один из процессов, который подписал сообщение, допустим r, корректен. Процесс r также переслал значение v процессу q, что значит, что v находится в .
Для (2): Предположим, что в конце алгоритма, и пусть w - второе значение, принятое p. Снова подобным рассуждением можно показать, что , что означает, что . (Равенство и не может быть получено, так как процесс p не будет пересылать свое третье принятое значение или более поздние.)
Доказав (1) и (2), предположим, что корректный процесс p останавливается на , то есть . Затем, из (1), v содержится во всех для корректного q, но, следовательно, не шире одиночного элемента {v}; иначе - не одиночный элемент, из (2). Следовательно, каждый корректный процесс q также останавливается на v. Далее, предположим, что корректный процесс p останавливается на значении по умолчанию, так как - не одиночный элемент. Если пуст, каждый корректный q имеет пустой по (1) и если , то по (2); следовательно, q также останавливается на значении по умолчанию.
o
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
