Why Encrypted Messages Still Leak Metadata (and How to Protect it on Polkadot)

Encryption can keep a conversation's contents secret, but it doesn't necessarily hide who is talking to whom. For developers building privacy-sensitive applications, that distinction matters.

Even when messages are encrypted, publicly visible information such as sender identities, topics and timing can reveal communication patterns. An observer may not be able to read a single message but can still discover which users are exchanging it.

Polkadot's Statement Store provides a transport layer for applications, leaving developers to decide which guarantees to implement on top. Privacy is one of those guarantees, and getting it right requires more than encrypting message contents.

In this article, we'll use a simple text chat to explore how communication metadata leaks, why some seemingly sensible protections fail, and how session keys, recipient buckets and keyed hashes can help protect it.

The goal is to demonstrate engineering principles and trade-offs, not to present a production-ready private messaging protocol.

Why encrypting messages isn't enough

Let's start with the naive approach. Alice and Bob want to chat. With the Statement Store, they can use a single shared topic and put messages in the data field. But all statements are open. Everyone can subscribe to that topic and receive statements that were not addressed to them.

So Alice and Bob encrypt the data. Now they need a shared secret to read the messages. Both of them already have asymmetric keys: a public key (pk) and a secret key (sk). So they can use Elliptic-Curve Diffie--Hellman (ECDH), a key agreement protocol.

With this protocol, they construct a shared symmetric secret using only their keys: ECDH(sk_Alice, pk_Bob) = ECDH(sk_Bob, pk_Alice). To keep it short, from here on we use the first letters: sk_A, pk_B.

Now they need to set up the chat. Alice invites Bob with a statement with topics ["invite", pk_B] and data encrypted with the shared secret S = ECDH(sk_A, pk_B). The topic is deterministic: Bob knows it in advance and subscribes to it. Bob accepts the invite with a statement with topics ["ack", pk_A] and data encrypted with the same S = ECDH(sk_B, pk_A). Then they start exchanging messages that an observer can't decrypt.

Elliptic-Curve Diffie--Hellman (ECDH): public keys are exchanged openly, secret keys stay at home, and both sides compute the same secret S

Now let's move to the observer's side. Without the keys of Alice and Bob, it can't decrypt the messages. But the messages are not the only data the observer can use.

Let's look at what the other fields reveal and what we can do about it.

• Signer --- who sent the statement. It stays public: a node needs a real account to check the allowance.
• Topics --- the public key of the other party. Topics are fully in our hands, but they must still make sense to the other party.
• Channel --- groups repeated statements of one user. The other party doesn't need it, but it is still public.
• Expiry --- hints at how long a message should matter, that is, how important it is.

Naive encryption covers the data, but the rest of the statement is public

Why hashing public keys doesn't protect metadata

A first guess to protect the conversation is to hash the topics. Instead of clear names, Alice could send an invite with the topic hash("invite" || pk_B), and Bob accepts with hash("ack" || pk_A). After that they chat on hash("chat" || pk_A || pk_B).

This hides the public keys, but it is still not safe. Without even trying to reverse the hashes, the observer sees that two accounts submit statements to one topic at similar times, which already looks like a chat.

Then the observer looks at how the hash is computed, which is easy if the code of the application is open source. The last piece is the list of accounts, which can be taken from the chain state. One hash per account, a few seconds on a laptop, and the observer has the topics for every account and knows who chats with whom in that application.

The lesson: a shared topic leaks the conversation, and a topic computed from a public key is easy to brute-force.

Topics computed from public keys label every conversation for an observer

Building more private messaging with Statement Store

Step 1: Use session keys to protect conversations

The first step in the right direction is to stop using long-term keys as the secret. A chat between Alice and Bob can go on for years, and with the account keys, its secret stays the same all that time. Instead, each side makes a key pair that lives only for one session: a session key.

The application generates such keys on the device and never registers them anywhere, so no account on chain points to them, and to the observer they are just random keys.

Alice makes a session key A1 and sends its public part inside the invite. Bob makes a session key B1 and sends its public part back in the ack. We now have two secrets:

• S1 = ECDH(sk_A1, pk_B) for the invite, which Alice can compute before Bob answers, because she already knows pk_B.
• S2 = ECDH(sk_A1, pk_B1) = ECDH(sk_B1, pk_A1) for the conversation, once both session keys are known.

What session keys don't do is hide the signer: the statement is still signed by the account.

Step 2: Hide recipients using buckets

If we keep Bob's identity in the invite, we'll never hide the conversation. Instead of putting Bob into the topic, Alice can use one topic hash("invite") for everyone and encrypt the data so that only Bob can read it. But now Bob has to try every invite in the network. Invites are rare compared to messages, but for a big network it is still a lot of work.

To save Bob's compute, Alice can invite only a part of the network, for example by splitting the users into buckets by the first byte of their public keys: hash("invite" || pk_B[0]). This cuts Bob's work, but it is also a trade-off in his privacy. One byte gives 256 buckets. For a million users it hides Bob among about four thousand other people.

Step 3: Protect topics and channels with keyed hashes

Hashed topics leaked because the observer could compute the same hashes. With a shared secret we can close that. Instead of a plain hash("topic"), Alice and Bob hash with the shared secret as a key: hash("topic", key: S2). The observer can't brute-force it, and the topic looks like a random value.

Channels are not part of the conversation, but they are public too, so they get a key the same way.

How private messaging works in practice

Alice sends an invite with the topic hash("invite" || pk_B[0]) and data pk_A1 || encrypt(invite, key: S1). Bob scans the statements in his bucket: he takes pk_A1 from the clear part, computes S1 = ECDH(sk_B, pk_A1) and tries to decrypt the rest. If it works, the invite is for him.

For the ack Bob uses the topic hash("ack", key: S1), which only Alice can compute, and shares the public part of his session key in the data: pk_B1 || encrypt(ack, key: S2). Alice takes pk_B1 from the clear part, computes S2 and reads the ack.

After the key exchange, they can start the conversation, but they shouldn't share one topic. They write on different topics:

• Alice: hash("chat" || pk_A || pk_B, key: S2)
• Bob: hash("chat" || pk_B || pk_A, key: S2)

What metadata remains visible?

The observer sees a statement from Alice in a bucket shared by four thousand other users. A minute later, a statement from Bob on a topic that looks like noise. Then more statements from both on two more such topics. Without S2 the observer can't compute these topics, and they look like any other hash in the store.

The mechanism is not perfect. The observer still sees who submits statements, when, and how large they are, and can try to match the invite with the ack by time. We hid the contacts, but not the activity.

With a bucket for the invite and keyed hashes after it, the observer sees unrelated topics

Privacy is an application design decision

Protecting communication metadata requires developers to consider more than message encryption. Session keys, recipient buckets and keyed hashes can reduce what observers learn about a conversation, but each technique introduces trade-offs in complexity, efficiency and privacy.

The effectiveness of these techniques also depends on the size of the network. Bucketing, for example, can provide meaningful privacy in a large network, where a recipient may be hidden among thousands of users. In a smaller network of 10,000 users, a bucket containing just 40 people offers considerably less protection. An observer may be able to identify the recipient by correlating the timing of an invitation with the subsequent acknowledgement.

The example presented here is not a production-ready protocol. Timing correlations, statement sizes and publicly visible senders remain potential sources of information leakage. Additional techniques, including key rotation, padding and dummy traffic, can strengthen privacy depending on an application's requirements.

Polkadot's Statement Store provides the underlying transport, while developers decide how to protect the information their applications exchange. The People Chain's anonymous allowances and TrUAPI offer further capabilities relevant to this work.

The broader opportunity extends beyond chat applications. Any application handling sensitive communications needs to consider what its metadata reveals, even when its contents are encrypted.

For developers building on Polkadot, understanding those risks and the conditions under which privacy techniques are effective is an important part of designing applications that protect their users.