Echtle, Klaus:
Avoiding Malicious Byzantine Faults by a New Signature Generation Technique
In: Dependable Computing - EDCC-3: Third European Dependable Computing Conference, Prague, Czech Republic, September 1999. Proceedings : Lecture Notes in Computer Science / Hlavicka, Jan; Maehle, Erik (Hrsg.). - Heidelberg / Berlin: Springer, 1999, S. 106 - 123
1999Buchaufsatz/Kapitel in Sammelwerk
Avoiding Malicious Byzantine Faults by a New Signature Generation Technique
Echtle, KlausLSF


Agreement problems like interactive consistency, reliable broadcast, group membership, etc. require a high protocol overhead when they must be solved under general (and thus hard) fault assumptions. Known signature methods contribute to more efficient solutions by protecting forwarded information from being altered undetectably. This paper presents a new signature generation technique, which prevents the occurrence of malicious Byzantine faults in the sender with very high probability. Hence, it is not necessary to ex-change multicast messages among the receivers for an equality check. This advantage opens an extended design space of agreement protocols with fewer messages, fewer timeouts and thus lower execution times. The new unique signature generation algorithm (called UniSig) is based on alternately step-wise generation of coded sequence numbers and digital signatures. Different messages can-not obtain the same valid signature, because the steps to increment the coded sequence number are included in UniSig. Deviations from the program execution path are very likely to lead to detectably corrupted signatures. Hence, for each sequence number a valid signature can be generated only once.