Define attack capability / impact matrix (without analysis)

[nathan-at-least]

Suggested Improvement

Issue #39 is titled for a specific attack capability, then in comments we start fleshing out an attack capability table.

This ticket is about defining that table but leaving most of the cells as "tbd", just to provide the structure.

The table could have capability rows and impact columns:

Attack capabilities are the cartesian product of a few categories:

• PoS with $N$ notaries (often called "validator nodes") with attacker compromise of $n$ nodes where:
  • $n ≤ \frac{N}{3}$
  • $\frac{N}{3} < n ≤ \frac{2 N}{3}$
  • $n > \frac{2 N}{3}$
• Malicious PoW hashrate of:
  • $0 + \epsilon$ (a tiny miner, say a home computer)
  • 10% - significant hashrate below selfish mining threshold (see Majority is not Enough: Bitcoin Mining is Vulnerable]
  • $X$%, a selfish mining threshold
  • $>50%$ majority miner

Attack impact categories include:

• safety (finality and transactional / consensus rule coherence)
• dynamic availability
• privacy

Close this ticket by putting that table into the book with tbd columns.

[nathan-at-least]

Consider these distinct PoS Attack Capabilities:

• compromising a critical threshold (≥2/3) of signing keys.
• compromising the signature scheme:
  • forging signatures for any target pubkey
  • Signature aggregation compromise
  • (Are there other signature scheme compromises here?)
• Preventing notarization votes from target victim nodes from being received by other nodes.

These different capabilities have different implications:

• If an attacker compromises 2/3 of signing keys, their misbehavior can be correctly attributed to those keys.
• If an attacker can forge signatures, the identity of the pubkeys cannot safely be used to attributing malice.
• If an attacker can prevent legitimate signers from propagating messages, they can prevent detection of misbehavior.

[nathan-at-least]

More on preventing votes:

An adversary may control a signing key exclusively, e.g. it just runs a malicious notary with its own identity.

vs

An adversary controls a signing key of a victim node, so both nodes are racing to emit messages.

Consider the distinct impacts of these cases, ex: in the first case, if the adversary is the epoch leader, there's no race, whereas in the latter case, there is a race.

In practice, it's likely an attacker will always want exclusive control of a notary, so that in some cases they won't have races (such as when their node is an epoch leader). This does require some minimum cost: enough to control at least one "legitimate" notary roster entry.