Next: Service
Properties Up: Contents Previous: Introduction
We use a Byzantine failure model, i.e., faulty nodes may behave arbitrarily, subject only to the restriction mentioned below. We assume independent node failures. For this assumption to be true in the presence of malicious attacks, some steps need to be taken, e.g., each node should run different implementations of the service code and operating system and should have a different root password and a different administrator. It is possible to obtain different implementations from the same code base [28] and for low degrees of replication one can buy operating systems from different vendors. N-version programming, i.e., different teams of programmers produce different implementations, is another option for some services.
We use cryptographic techniques to prevent spoofing and replays and
to detect corrupted messages. Our messages contain public-key signatures
[33], message authentication codes [36],
and message digests produced by collision-resistant hash functions [32].
We denote a message m signed by node i as
m
and the digest of message m by D(m) . We follow the
common practice of signing a digest of a message and appending it to the
plaintext of the message rather than signing the full message
(
m
should be interpreted in this way). All replicas know the others' public
keys to verify signatures.
We allow for a very strong adversary that can coordinate faulty nodes, delay communication, or delay correct nodes in order to cause the most damage to the replicated service. We do assume that the adversary cannot delay correct nodes indefinitely. We also assume that the adversary (and the faulty nodes it controls) are computationally bound so that (with very high probability) it is unable to subvert the cryptographic techniques mentioned above. For example, the adversary cannot produce a valid signature of a non-faulty node, compute the information summarized by a digest from the digest, or find two messages with the same digest. The cryptographic techniques we use are thought to have these properties [32, 36, 33].