If we have two devices (say Alice's phone and Bob's phone) that are sending messages to each other, how do we make sure nobody knows who is talking to whom? The answer seems non-trivial to me.
Could we use Alice's and Bob's public keys to encrypt the message and then send them to the entire network, relying on the security of the encryption (and acknowledging that a third part can read all messages any way)? Is there a way to look at a public key and an encrypted message and say that yes, this message was encrypted with this key? It seems that we'd be paying through the nose in terms of throughput capacity (and processing capacity as everyone would have to take in everyone else's packets) if we wanted to maintain metadata privacy this way. I'm sure this is not what you had in mind. Can you please elaborate on how we can secure metadata?