Proof of probe possession

[michielbdejong]

Say a node Center has 4 neighbours, and her East and South neighbours are looped together:

       North
        |
West - Alice  - East
        |        |
       South ___/

If she sends one probe abcd to all neighbours in one burst, then it depends on message delivery timing who will detect the loop. If it's batched and alphabetical, then in the first batch, South and East will both receive the probe from center, and in the second batch, East will come before South and South will be the loop detector. If instead of alphabetical, the sending of each batch is simultaneous, then the messages between East and South cross each other - then both will detect the loop but probably reject it because they suspect the other party is just echoing.

So proof of possession depends on timing. If a neighbour is both a from and a to for a "flood probe", a node could respond with a "pin probe" just to them, to see it that returns, before going into loop tracing.

[michielbdejong]

Let's try to pin down ;) the requirements for proof of knowledge loop some more:

• the probeId is hard to guess
• Alice receives it from Bob (this is Bob giving Alice proof of possession)
• Alice did not previously receive it from Bob
• Alice did not send it to Bob
• but Alice has seen this probe before

Note that this can happen if the probeId is public or Bob and some other node are part of the same internet forum, but we count that as a permissable proof of knowledge loop (though not proof of trade loop).

So this means she either generated it herself and sent it to at least one other node (not Bob), or she received it from some other node (but never forwarded it to Bob yet).

[michielbdejong]

More precisely, there are three things you can prove, and we are mostly interested in the third one:

Proof of shared knowledge

If node A sends a message to node B containing some probeId then this proves to B that it shares the knowledge of this probeId with A. A would still not know for sure whether B got the message though. Shared knowledge may exist in any graph structure. Shared knowledge in a cyclic graph called a knowledge loop. Not all nodes in the network need to be taking part in the communication, for instance, an internet forum or a low-entropy preimage may complete the loop.

Proof of knowledge loop

If node A receives a message from both nodes B and C with the same probeId then this proves to A that A, B and C share that knowledge. It does not prove that B and C interacted, because they might have both gotten the probeId from some internet forum. That's why this is proof of knowledge loop and not proof of communication loop.

Proof of communication loop

If node A sends a hard-to-guess probeId to B, and it later comes back through C, then A knows that B and C must have communicated with each other in the meantime.

[michielbdejong]

Proofs from flood probes

A flood probe starts in one or more nodes and spreads throughout a connected graph. While doing so, in some situations, proof of shared knowledge loops and communication loops can be detected: If A sends the same probeId in two directions, and gets it back from both (but A being the source), that is only proof of shared knowledge. If A receives the same probeId from two directions, that is not only proof of a shared knowledge but also proof of a knowledge loop. If A sends a self-minted probeId to only some nodes and then receives it from some other nodes, that is proof of communication loop. If the probeId was not self-minted then it only counts as proof of knowledge loop.

[michielbdejong]

Proofs from pin probes

A pin probe is intended by one node (the 'initiator') to test proof of communication loop with one specific neighbour (the 'whisperer') and some third party (the 'looper'). It is sent only to the whisperer, and never to any other neighbour.

Any neighbour the probeId is then received from, is a looper, and this is proof of a communication loop:

        whisperer
       /         \
initiator         ???
       \          /
        | looper1 |
        | looper2 |
        | looper3 |

Pin Probes are different from Loop tracers because

• the other nodes will not see the difference between a flood probe and a pin probe, but Loop tracers are a different message type
• from the whisperer onwards, pin probes are intended to flood, whereas Loop tracers are intended not to fork

[michielbdejong]

Requirements for an incoming probe message to count as proof of communication

• COMM1: it was home-minted
• COMM2: it was never sent to that neighbour