New strategy generation starting with Giraffe: introducing kite traces

[michielbdejong]

The triangle halts after 45 paths: https://github.com/ledgerloops/strategy-pit/blob/main/__tests__/fixtures/batched-butterfly-triangle.puml But the hourglass of Butterflies keeps minting more and more probes, it seems: https://github.com/ledgerloops/strategy-pit/blob/main/__tests__/fixtures/batched-butterfly-hourglass.puml Are these pinning probes?

[michielbdejong]

Yes: https://github.com/ledgerloops/strategy-pit/blob/c549ad66123b5ce838af4a55d5ef707dfdeafde2/__tests__/fixtures/batched-butterfly-hourglass.json#L7185 I think what happens is for instance:

Bob -> Charlie probe1
Bob -> Alice probe1
Alice -> Charlie probe1
// now Charlie will create a pinning flood probe
Charlie -> Alice probe2
Alice -> Bob probe2
Bob -> Charlie probe2
// but also:
Alice -> Dave probe2
Alice -> Edward probe2
Dave -> Edward probe2
// and now Dave will mint probe3
// which then meets itself at Bob or Charlie
// who will mint probe4
// etcetera, with a new pinning flood probe getting minted in the other half of the hourglass back-and-forth

[michielbdejong]

So the solution, I think, is to link the pinning flood probe to the probe it is supposed to investigate. Just like we do for Traces. Time for a new strategy! :)

[michielbdejong]

Ah wait, that wouldn't work because there is no way for Alice (in the middle of the hourglass) to know if Charlie is pinning a probe that reached him from Bob or from Dave. For P-shaped loops you could in fact go straight to Trace - even if the P-shape doesn't give proof of comms, the Trace ID would. The trouble is that the discoverer can distinguish Origin loops, but it can't distinguish between P loops and Kite loops. So to trace a Kite loop, would it make sense to send a Trace back to both senders maybe?

[michielbdejong]

And then those would meet on the fork of the kite.

[michielbdejong]

• Undirected probe loops back to Origin -> Trace it back -> Done
• Undirected probe comes in twice -> Two traces, one to each sender
• Directed trace loops back to Origin -> Done
• Directed trace comes in twice -> You're the fork of a kite -> Supertrace it (in both directions?)
• Directed supertrace loops back to Origin -> Done

[michielbdejong]

OK I thought this over a bit more carefully and we need to change the message types. Consider the following three loop types. Assume this is the communication graph; we ignore links on which A can talk to B but B cannot talk to A (such as if A is a client and B is a server), not because such links are not interesting, but because the Giraffe algorithm depends on bidirectional communication:

O loop

The simplest case is the O loop, where a flood probe loops back to its root: When this happens, the root obtains instant proof of comunication and can just send a trace in the opposite direction, and then that will be enough for all loop participants who see this trace will have an opportunity to start (bidirectionally) negotiating over that loop.

P loop

Slightly less simple but still simple enough is the P loop: a probe that loops back onto itself: The node where the probe meets itself will have no proof of communication. It has received the probe twice and sent it once. Maybe the neighbours from whom it received the probe twice were colluding without communicating, both using a well-known but random-looking probe ID. So sending some sort of trace in this case will help here both to trace back the path and to establish proper proof of communication. Note that for the detecting node, a P loop is indistinguishable from a kite-to-non-leaf loop (see below).

Kite to Leaf loop

A Kite-shape can form if a probe arrives twice at a node, before that node had forwarded it. So now this node knows it is the leaf in a kite-to-leaf loop. It can send back one kite trace message (this is a new concept) to each leg, with one nonce in common (the traceId) and one nonce differently (the legId). So one will carry: probeId-1, traceId-1, legId-1 and the other will carry probeId-1, traceId-1, legId-2. The two traces will meet at the fork node of the kite. This may be the root of the probe, or not, doesn't matter a lot. The fork node sends each kite trace back up the other leg, and they will both eventually find the leaf again. So this proves bidirectional circular communication to the leaf, and traces the path for each intermediate node (including the fork node).

Kite to Non-Leaf Loop

Slightly different if the top of the kite is not a leaf, because then the top node doesn't know if it's the looping point in a P loop or the top of a kite. For a P loop a simple trace would suffice, but this node will send two kite traces to cover both possibilities. If it turns out to be a Kite to Non-Leaf, the two kite traces will hit the fork and come back through the other kite leg, like in the Kite-to-Leaf. If it turns out to be a P loop, one of the kite traces will travel to the probe root and stop there, and the other will loop back to the discovering node.

[michielbdejong]

To keep the code simple, when the probe root discovers an O loop, it can just use a single kite trace, maybe setting the only a traceId and no legId, or setting some random unused string for the legId

[michielbdejong]

When a trace leg splits, send the trace with the same legId to both sublegs When two traces come in with the same legId, just merge them and continue towards the root. So when tracing the red kite, the blue arrows here are just a diversion of one of the trace legs.

[michielbdejong]

probes handling in Giraffe Triangle now looks correct:

[michielbdejong]

It's working now for triangle; for hourglass it still keeps forwarding traces endlessy.

[michielbdejong]

Will create follow-up issues for specific things I see going wrong in hourglass