car-mirror: Edge cases of receiving blocks you already have possible

[matheus23]

Came up in a meeting with @expede: There does exist an edge case where CAR mirror will send blocks that the recipient already has, even outside the cold call.

Specifically, if the receiver has a disjoint graph root that it doesn't know is connected to the DAG they're requesting, then the batch from the sender may contain blocks from that previously disjoint graph root.

E.g. a simple (and admittedly weird) case where the receiver has every second block in a blockchain and is asking for the root.
The sender will respond with a certain depth of the blockchain. Every second of these blocks will be redundant.

So in some cases bitswap will actually be 'more precise'. But the same can be said of CAR mirror in the mode without a bloomfilter.

---

Mostly I filed this for @expede to go through the spec in case there's any mention of never sending a block the receiver already has.

[expede]

I'm trying to load this back into my brain after being on vacation for 2 weeks.

I think graphically, this looks something like this:

flowchart TB
    a -.-> b -.-> c -.-> d -.-> e

    subgraph Want
      a
      b
      d
    end

    subgraph Have

      y --> c
      y --> e
    end

Loading

A cold call can absolutely give you redundant blocks, because it doesn't have enough info yet — and that's covered in the prose.

For the other case, I don't know if you do get redundant blocks, but you're going to have more overhead (blooms etc) than BitSwap in this weird striped edge case. We currently assume that if you have c, then you also have d and e (recursively). It's possible for this to not be the case.

I think that we probably won't include redundant blocks in this case, since they get caight by the bloom. Rather, it will send lots of small results back, and have to do a lot of round trips. I feel like I'm missing something in here — since I was pretty convinved (but also very tired) right before I went on vacation — so I'll think on it more.

[matheus23]

In your example, let's assume the sender only sends "a" in the cold call, and then in the second call, it sends "b" and "c".
The receiver didn't know that they had to put "c" into the bloomfilter between these calls. It tried to walk what it had already, starting from the "a" block, but couldn't find anything, so the bloomfilter was empty.