This is discussed in the last section of the paper.
I did read that section before asking my question.
I got the impression that the only way to know whether or not it was Bob who sent the message is to check the signature on that message.
Is it not so? If it is not, then how?
The signature is checked before peer's relay it to other peers, not every single peer in the network.
A network of trust, this is also strong against sybil as described here -
http://pdos.csail.mit.edu/papers/sybil-dht-socialnets08.pdfPeers can accept trusted from trusted messages as those reasonable to view, and before executing a trade are welcome to take the processing power to verify the message signature themselves.