go-spacemesh
go-spacemesh copied to clipboard
spacemeshos
PreRound union is unlimited
Receiving multiple PreRound messages from the same sender is currently handled by calculating the union of the pre-round sets. A malicious node can send multiple pre-round messages in which the sets are distinct causing the union to grow indefinitely. Note: This would not be a problem if we hadn't included the pre-round certificate optimization. The certificates make sure the receiver can always verify the message.
The following question needs to be answered: Is there a case in which an honest node should send more than one preround message? i.e. Why should a node track multiple preround messages from a single committee member?
Root cause of this issue arises from the following issue and PR
- https://github.com/spacemeshos/go-spacemesh/issues/564
- https://github.com/spacemeshos/go-spacemesh/pull/600
It is claimed that the pre-round certificate optimization is what forces us to keep/process all preround messages (and build the union of input sets from an equivocating preRound participant).
Context: the preround certificate optimization is what allows us to leave out the very large preRound certificate from the status messages. The assumption is that once all nodes have seen all preRound messages, they'll be able to verify status messages without needing the certificate that should theoretically be paired with said status messages.
It is of my opinion that the discussion in https://github.com/spacemeshos/go-spacemesh/issues/564 missed a solution that would prevent this ever-growing cache vulnerability Because https://github.com/spacemeshos/go-spacemesh/issues/564 is closed, I will continue the discussion here and propose a new implementation path.
In https://github.com/spacemeshos/go-spacemesh/issues/564, they describe a difficult scenario where an honest node is trying to verify a status message or safe value proof which contains values that can only be justified by preround messages from an equivocating node. In other words, an honest node receives multiple preround messages signed by the same preround participant that describe different input sets.
This is a problem when there is no protocol for determining which (if any) of those input sets can be used for justifying a safe value proof or status message.
@gavraz and @zalmen propose keeping all the input sets so that in case an honest leader broadcasts a proposal using one of the equivocating preround messages as justification in the SVP, we'll be able to verify it.
The problem with that is we end up in this situation where a preround participant (presumably malicious) can spam the network and force nodes to store all the spam in memory.
My proposed solution is as follows:
- The first 2 preround messages from any participant are kept, and if more than one unique message from the same preround participant is received, that participant is blacklisted. And we use the equivocating preround messages as proof of being a bad boy.
- When it comes time to generate the status message and safe value proof, we do not use an equivocator's messages to justify the inclusion of values in an accepted set (status round) or proposed set (proposal round).
- When it comes time to validate status messages or safe value proofs, we only use the messages from non-blacklisted signers. Now, an honest leader may include a value in the proposed set that can only be justified using messages from equivocating nodes. This is because it is possible the status round participants and/or leader didn't receive the extra preround messages proving equivocation before generating the status message or safe value proof. We actually don't care about this case because, due to the nature of our p2p network, by the second iteration of hare, all honest nodes will update their "accepted set" to only include values that are justified by non-equivocating preround messages. And from now on the election of any honest leader will result in a successful consensus as described by the inductive proofs in the white paper.
Also, a note about late preround messages and the preround certificate optimization problem: Because of this equivocation problem, I think we end up needing to wait for preround messages until a commit certificate is available whether or not we use my proposed solution. The reason for this is because malicious nodes can time their messages to be sent close to the "cutoff" time so that nodes nearby assume it's just a message that came a long distance, and nodes far away will "miss" the message. No matter how long we wait after the preround, the malicious nodes can always just wait until the "cutoff". So, until we can switch to using the commit certificate instead of the preround certificate, we'll need to keep processing preround messages in case honest leaders use those preround messages to justify a proposed set.