After we fix the communication model, synchrony, asynchrony, or partial synchrony, and a threshold adversary we still have 5 important modeling decisions about the adversary power:

  1. The type of corruption (typically: passive, crash, omission, or Byzantine).
  2. The computational power of the adversary (typically: unbounded, computational, or fine-grained).
  3. The adaptivity of the adversary (typically: static, delayed adaptive, adaptive, or strongly adaptive).
  4. The visibility of the adversary (typically: full information or private channel).
  5. The mobility of the adversary (typically: traditional or mobile).

1. Type of corruption

The first fundamental aspect is what type of corruption the adversary can inflict on the $f$ parties it can corrupt. There are four classic types of corruption: Passive, Crash, Omission, and Byzantine.

  1. Passive: a passively corrupted party must follow the protocol just like an honest party, but it allows the adversary to learn information. A passive adversary (sometimes called Honest-But-Curious or Semi-Honest) does not deviate from the protocol but can learn all possible information from its view: i.e., the messages sent and received by parties it controls. A failure in this case is if the passive adversary learns information that the protocol designer wanted the adversary not to learn.

  2. Crash: in addition to passive, once the party is corrupted, the adversary can decide when to cause it to stop sending and receiving all messages.

  3. Omission: in addition to passive, once corrupted, the adversary can decide, for each message sent or each message received, to either drop or allow it to continue. Note that the party is not informed that it is corrupted.
  4. Byzantine: this gives the adversary full power to control the party and take any (arbitrary) action on the corrupted party. Sometimes this model is called active corruption or arbitrary corruption.

Note that each corruption type subsumes the previous one.

There are other types of corruption. Most notable are variants of Covert adversaries. Covert adversaries can be used to model rational behavior where there is fear (utility loss) from punishment through some form of detection.

There are more variants of omission corruption worth mentioning:

  • Oblivious omission: the adversary can decide, for each message sent, or each message received, to either drop or allow it to continue, but the adversary does not have visibility into the party, it just sees the header of each message (source, destination, and message length).
  • Send omission and Receive omission: which are in between crash and omission. See this post.

2. Computational power

The computational power of the adversary:

  1. Unbounded: the adversary has unbounded computational power. This model often leads to notions of perfect security or statistical security. The advantage of this model is that will remain secure forever.

  2. Computationally bounded: the adversary has a polynomial advantage in computational power over the honest parties. Typically, this means that the adversary cannot (except with negligible probability) break the cryptographic primitives being used. For example, typically assume the adversary cannot forge signatures of parties not in its control (see Goldreich’s chapter one for traditional CS formal definitions of polynomially bounded adversaries). All of modern cryptography depends on this type of adversary and typically there is a security parameter that needs to be updated over time (as computation becomes cheaper).
  3. Fine-grained computationally bounded: there is some concrete measure of computational power and the adversary is limited concretely. This model is used in proof-of-work based protocols. For example, see Andrychowicz and Dziembowski for a way to model the hash rate. It is often needed for Verifiable Delay Functions and time lock puzzles.

3. Adaptivity

Adaptivity is the ability of the adversary to corrupt dynamically based on information the adversary learns during the execution.

  1. Static: the adversary has to decide which $f$ parties to corrupt in advance before the execution of the protocol. Note that this is always sufficient when the protocol is deterministic because there are no surprises for the adversary. One natural thing for randomized protocols in this setting it to operate on a random subcommittee.

  2. Delayed Adaptive: once the adversary asks to corrupt a party, the party is corrupted at the end of the round ($\Delta$ time in synchrony, or once the party decides to listen to a port in asynchrony). So while the adversary is adaptive, the actual corruption is delayed to the end of the round. Often in this model, it is also important that honest parties can erase some information in order to get forward security.

  3. Adaptive: once the adversary asks to corrupt a party, the party is immediately corrupted. Messages sent from the party before corruption cannot be erased (so will eventually arrive in asynchrony or in arrive in at most $\Delta$ time in synchrony).

  4. Strong Adaptive: once the adversary asks to corrupt a party, the party is immediately corrupted. Moreover, messages sent from the party before corruption that have not yet arrived can be erased (or claw-backed) by the adversary. Some lower bounds only work in this model.

4. Visibility

The visibility is the power of the adversary to see the messages and the states of the non-corrupted parties. There are two basic variants:

  1. Full information: the adversary sees the internal state of all parties and the content of all message sent. This often severely limits the protocol designer. See for example: Feige’s selection protocols, or Ben-Or et al’s Byzantine agreement. Often, the only thing that the adversary cannot do is predict the value of coins that have not been tossed yet.

  2. Private channels: in this model, we assume the adversary cannot see the internal state of honest parties and cannot see the internal content of messages between honest parties. Each time a message between two honest parties is sent, the adversary learns the source, target, and message size. Depending on the communication model, it can decide to delay it by any value that is allowed by the communication model.

For models that are round-based, another visibility distinction is the adversary’s ability to rush. When does the adversary see the messages sent to parties it controls? In the rushing adversary model, the adversary is allowed to see all the messages sent to parties it controls in round $i$ before it needs to decide what messages to send in its round $i$ messages. In the non-rushing adversary model, the adversary must commit to the round $i$ messages it sends before it receives any round $i$ messages from non-faulty parties.

5. Mobility

In the traditional model the adversary is allowed to corrupt honest parties with some fixed budget of up to $f$ parties, but is not allowed to un-corrupt (or heal) corrupt parties back to being honest. In the mobile model the adversary is allowed to dynamically decide to corrupt and un-corrupt parties. The total number of corrupted parties at any given time is at most $f$, but over time the set of corrupted parties may change. It is often required that there is a gap between the time the adversary un-corrupts one party and the time it is allowed to corrupt another. This model was introduced by Ostrovsky and Yung and exemplified by proactive secret sharing. Another modeling decision is whether the party is aware that it is un-corrupted (in which case it may be able to remove in-memory corrupt data).

More models

There are many more models and variations - here is an incomplete list (let us know in the comments about more).

Mixed corruptions

In some cases, we are interested in a mix of say $f$ Byzantine and $k$ crash corruptions (for example here) or any other mix.

Sleepy model

In the sleepy model of Pass and Shi, in addition to being either honest or corrupt, parties can be either active or inactive each round. The assumption is that the threshold bound on the adversary holds at each round on the actual number of active parties in that round. This is sometimes called the dynamic participation model.

Mobile sluggish

One of the challenges in the mobile model is the fact that the adversary can accumulate the private keys of parties. In the weak synchrony model (also called mobile sluggish), the adversary is allowed to corrupt either via a Byzantine corruption (that is not mobile) or a mobile sluggish corruption. Critically, the sluggish corruption allows the adversary to delay messages to and from the corrupted party but not to learn its private keys. Hence, allowing sluggish corruptions to be mobile does not allow the adversary to accumulate private keys.

Flexible model

The Flexible BFT model introduces two variations. First, a model where different properties are held under different threshold assumptions. Second, a model where the same protocol may serve different clients, where each client may have a different adversary threshold in mind.

Acknowledgments

Special thanks to Alin Tomescu, Kartik Nayak, and Gilad Stern for insightful comments.

Please leave comments on Twitter