State Recursive Gossip issue

[morph-dev]

Issue description

The current gossip logic of the state network uses Recursive gossip, which we recently discovered has a flaw.

While not common in practice, it is possible for recursive gossip to stop before all trie nodes are gossiped. To give a simple example, let's image following trie transition between blocks 1 to 4.

block:  1         2         3         4

        AB        CB        CD        AD  
       /  \  ->  /  \  ->  /  \  ->  /  \ 
      A    B    C    B    C    D    A    D

Here is what would happen on each block:

1. bridge will gossip nodes A and B, and node AB will be gossiped via recursive gossip logic
2. bridge will gossip node C, and node CB will be gossiped via recursive gossip logic
3. bridge will gossip node D, and node CD will be gossiped via recursive gossip logic
4. bridge will gossip node A, nobody in the network will accept A (everybody already has it), resulting in node AD never being gossiped

This scenario can happen whenever some sub-trie (not only single trie node) is reverts to the identical version from some older block, and no other changes are made in the trie within the same block.

Agreed solution

Considering that no viable solution that uses the Recursive gossip logic is found for this problem, we agreed to remove the recursive gossip from the spec.

Instead, we will implement the most naive approach in which bridge gossips separately every new/modified trie node (both inner and leaf).

Considered solution

We considering changing the condition for stopping the recursion, which would avoid this issue.

One idea is to keep trying to gossip parent nodes until one is accepted by at least one peer. While this solution should work in theory, it creates a problem similar to the "thundering herd" (#242) for the trie nodes that are close to the root level (there will be at least one offer for the root node for every leaf node).