On spamming for optional proofs

# On spamming for optional proofs This document outlines the proof spamming issue that arises solely with optional proofs and a few mitigation strategies. ## Scenario zkEVM proofs allow an attester to check the correctness of the execution payload by verifying a proof. EIP 8025 introduces the concept of optional proofs, where the majority of nodes will still re-execute and only some will optionally download proofs. Optional proofs do not require a hard fork and as such to preserve for compatibility with non-zk attesters, zk attesters cannot modify any beacon state information that would be read by non-zk attesters. In particular, - zk attesters cannot slash or eject validators - zk attesters must follow the same fork-choice rules as non-zk attesters As a result, zk proof verification is **advisory** from the perspective of consensus, and any misbehavior related to proofs must be handled outside of the beacon state, typically at the networking layer. This includes spamming proofs. ## Problem Because zk attesters cannot rely on consensus-layer punishments, malicious or faulty behavior related to proof propagation cannot be penalized via validator identities or slashing. Solutions would therefore need to be: - Forkless (compatible with existing consensus rules) - Network-level (peer scoring, rate limiting, etc) The problem statement is then: how can zk attesters receive proofs safely without being DoS'd when: - Proofs are between 128KB to 300KB - Proof verification can take 70ms to 100ms ## Attackers capabilities We assume an attacker who can: - Create as many network/libp2p identities as possible - Send arbitrary messages over the p2p network - Has control over X% of a privileged set (this could be the validator set for example) - Can generate malformed/invalid proofs cheaply - Can generate valid proofs, but not as fast as everyone else The goal of the attacker is to denial of service honest nodes, by either causing them to do a lot of computation or causing them to waste a lot of bandwidth. ## Attack vectors **Attack 1: Invalid Proof Flooding** This is where an attacker sends proofs that are invalid. Impact: - Honest nodes must download the proof - Honest nodes must attempt verification to detect invalidity - Even if peers are downscored and disconnected afterward, the cost is already paid **Attack2: Duplicate Proof Flooding** This is where an attacker sends the same proof multiple times. Impact: - Nodes repeatedly download large payloads - Verification may be skipped, but bandwidth is still consumed - Gossip-based propagation can reintroduce the same proof via multiple peers This attack is especially problematic if proofs are propagated via push-based gossip with large payloads, and can be even more pronounced due to the fact that there might be a lot of redundancy on the network from honest peers. ## Design space There are two axes to analyze in the design space: **Push vs Pull** - Push-based: proofs are gossiped directly to peers - Pull-based: peers announce that they have the proof, and receivers fetch them if they need to **Permissionless vs Permissioned** - Permissionless: anyone may send proof-related messages - Permissioned: proof messages must be signed by an authorized identity (like a member of the validator set for example) ## Solution 1: Permissionless Proof Propagation In this model: - Proof messages are unsigned - Any node on the network may send proofs **Defenses** - Nodes verify unsigned proofs and downscore/disconnect peers that send invalid proofs - Nodes track seen proofs to avoid re-verification **Limitations** - Sybil attacks are cheap, since node IDs are easy to create - Attackers can repeatedly impose verification and bandwidth costs In this model, the attacker is only limited by the mitigations on the p2p layer, however since p2p layer identities are easy to create, this strategy has minimal defenses against invalid proof flooding. > Note: even in scenarios where a node does not need a proof, both attack vectors would cause the node to at least re-download the proof (assuming gossipsub doesn't have a caching mechanism for duplicate proofs) ## Solution 2: Whitelisted proof propagation In this model: - Proof-related messages must be signed - Nodes only process messages from an authorized signer set Possible signer sets include: - A fixed ad-hoc list - The active validator set Since all attesters must see the same list, updates must be synchronised. *Fork based updates:* This would be similar to BPO(Block Parameter Only) forks. Clients would need to have code that states "After slot X, use this list of public keys" *Contract based updates:* For the validator set, the contracts for updating the list and notifying the attesters are the deposit and withdrawal contracts. If we are not using the validator set, then a new contract will need to be deployed and the logs from that contract will need to be parsed and propagated to the attesters. **Benefits** - Cheap pre-verification via signature checks (~1ms) - Limits the cost of proof verification spam to authorized identities - Enables per-signer rate limits (can ignore the same proof being sent to you by same node) **Limitations** - Spam is still possible by the authorised set. The cost to create an identity here is however higher. But note that we still cannot punish/ban nodes on this list without introducing another layer of consensus amongst only the zk attesters. This solution fixes the who can cause an honest node to waste cycles on proof verification -- if this list of authorised entities are honest or are held accountable by some other mechanism, then they should never spam. ## Solution A: Limiting bandwidth consumption (Announce-then-Fetch) Instead of gossiping full proofs. 1) Nodes will gossip proof signed announcements: - (slot, block_root, proof_id, proof_type) 2) Nodes request proofs on demand via request/response: - If they do not have the proof already - From peers they know have the proof > Note: Raul noted that this is best done via IHAVE/IWANT **Benefits** - Eliminates duplicate-download attacks - Allows a node to locally decided when and from whom to fetch proofs from - Decouples gossip from large proof transfer This mechanism allows one to punish peers who also send them unrequested proofs. However, one still pays a bandwidth cost for peers who announce a proof_id and then send you an invalid proof. # Addendum ## On Proof Binding Graffiti One useful property may be to allow the proof to be binded to arbitrary metadata. One can think of this as graffiti. The graffiti should not be trusted, especially in the context of malicious provers. However, one could use portions of the graffiti to embed an public key and then require that only the validator with that public key can sign for that proof. One could also use this graffiti to embed the software versions. ## Punishing the whitelist Checking the requirements, the zk attesters can have state that only they know about, as long as this state cannot be seen or affect normal zk attesters. It is therefore possible to have an accountability mechanism for the whitelist, however this raises an issue around consensus. Imagine we had a list of members who could sign, and one member signs an invalid proof. We could send that invalid proof to all zk attesters to show that the proof was invalid, but we need them to all see it and agree, which essentially is the consensus problem.