Bitmessage address mixing

Riffle shuffle

This post introduces the concept of address mixing in Bitmessage - what it is, why it is useful, and how it could be done.

This post does not contain a complete algorithm nor claim to know the best solution to the problem, but is rather intended to start a debate on the best way to achieve the goals described in the following section:

What is address mixing?

Address mixing is when a group of people who knows the Bitmessage addresses of each other, works together to create a list of alternate addresses owned by the same group of people, but without knowing who owns which address.

In other words, everybody creates a new address and shares it with the others in such a way that no member of the group (or anybody outside of the group) can deduce which of the new addresses belong to a specific person of the group.

The idea is that of a trustless mix network - i.e. one that doesn't require anyone to trust anyone else for the process to work.

For this purpose, we assume that any adversary has knowledge of the people in the group, as well as any CMLs or DMLs used by the group.

Why is address mixing useful?

Address mixing potentially has a lot of use cases, but the most obvious is the case where a group of people wants to anonymously send messages to each other without revealing who is the sender, while still convincing everybody that the sender is a member of the group.

One could easily imagine a scenario where this group of people wants to conduct a completely anonymous survey (or maybe an election) while ensuring that only the responses of group members are regarded as valid.

Messages in Bitmessage only provide pseudonymity; if you know the identity of the person behind the sender address, he or she is not anonymous at all. This is undesirable in certain scenarios where the senders of messages wish to be completely anonymous to the group.

Of course, decentralized mailing lists (DMLs or chans) already provides the functionality of sending anonymous messages to a group (and, in fact, the address mixing schemes proposed here will make use of chans), but receiving a message anonymously in a chan only proves that the sender knows of the chan, and not that the sender is an accepted member of the group of people using the chan.

How could address mixing be done?

There are a number of ways to implement address mixing in Bitmessage, and this post will introduce two such ways, each with their own advantages and drawbacks. Both will be using chans as a means of broadcasting information to the other people in the group.

The first approach is rather simple, but allows an attacker armed only with knowledge of the chan to disrupt the mixing.

The second approach (binary mixing) is somewhat more complex, isn't so easily disrupted as the first one, but introduces some other drawbacks.

In the following, each person is assumed to know the following:

  • His/her own address Ai and new anonymous address A'i.
  • A list of addresses of everybody in the group L={A0A1, …, A|L|-1}.

Furthermore, the resulting list of anonymous addresses will be denoted L'={A'0A'1, …, A'|L'|-1}.

Simple mixing

Simple mixing works by having two separate rounds of message exchange, a registration round and a signing round, where each round has a deadline and the end of the registration round signals the start of the signing round:

Registration round Everyone broadcasts1 a registration message from their anonymous address to the chan.

Signing round All members of the group now hold a list of anonymous addresses received from the registering round. Each member then verifi es that their own anonymous address (A'i) is on the list, signs the normalized list with his or her public address (Ai), and broadcasts this signature to the chan.

1 Alternatively, the person could anonymously broadcast a message containing the new address in the message content, but this method ensures that someone actually has the private keys for the address.

Considerations

A few checks must be made in order for this mixing scheme to function properly:

Firstly, when the registration round ends, the members must check if there are more anonymous addresses than original addresses, i.e. if |L'|>|L|. If this is the case, the mixing must be canceled since at least one of the anonymous addresses are not eligible.

On the other hand, if there are fewer anonymous addresses than original addresses, i.e. |L|>|L'|, we assume that one or more members have not participated in the mixing, and we can choose to abort or continue depending on what we want to use the anonymous addresses for.

Secondly, when the signing round ends, everybody must then check that there is exactly as many unique2 signatures as there is anonymous addresses. If there are fewer signatures, it implies that one or more anonymous addresses are not to be included in L', and if there are more signatures, it means that one or more members have signed the list of addresses without owning one of these addresses3.

Also, the members must be sure that they are signing the same list of addresses. All signatures must then have signed the same list in order to be considered valid. If a members receives a different list signature than its own, it means either (a) that one or more anonymous broadcast messages from the registration step has been dropped for some participants or (b) that the other member is acting maliciously. Either way, this signature cannot be considered valid for this mixing.

2 A unique signature means that if multiple signatures arrive from the same address, only one signature is counted.

3 This isn't really a problem for the integrity of the list L', but is disallowed for simplicity.

Advantages

  • This scheme provides anonymity in contrast to "ordinary" Bitmessage messages which only provide pseudomity.
  • Only 2×|L| messages are required to be broadcast in order for the mixing to work.
  • The scheme is pretty simple and easy to understand.

Drawbacks

  • It is very easy for an attacker to cancel a mixing by anonymously broadcasting an address which cannot be signed in the signing round.
  • A dishonest member could sign the list of addresses without having provided one of his own, thus either canceling the mixing or allowing an non-eligible person to include their anonymous address.
  • Everyone has to be connected to the network and perform an action during each of two rounds in order to participate4.

4Although the actions can be automated, the member's client still has to be connected to receive and send broadcasts.

Evaluation of simple mixing

The simple mixing scheme is, as the name hints at, very simple. But that simplicity comes at a cost: Any attacker with knowledge of the chan can completely disrupt a mixing just by broadcasting (almost) any address. In the next mixing scheme, we introduce a protocol that makes it considerably harder for anyone not in the group to do that.

Binary mixing

The binary mixing scheme is broken up in log|L| rounds as opposed to only two rounds before; every member is placed as a leaf in a binary tree, and each pair of siblings in the tree exchange addresses and recursively builds up the complete list of anonymous addresses L'.

In the first round, each of the |V|/2 pairs of members Vi and Vi+1 (we'll call them Alice and Bob) join up and do the following identical steps:

  1. Alice sends her anonymous address V'Alice to Bob and waits for Bob to do the same with:

    Alice\rightarrow{}Bob\qquad:\qquad{}V'_{Alice}\\Bob\rightarrow{}Alice\qquad:\qquad{}V'_{Bob}

  2. Having received Bob's anonymous address, Alice compiles this address and her own in a list, sorts the list, signs it with her private key and sends the list L'AB and signature SigAlice(L) to Bob. Bob does the same:

    Alice\rightarrow{}Bob\qquad:\qquad(L_{AB},\qquad\textrm{Sig}_{Alice}(L_{AB}))\\Bob\rightarrow{}Alice\qquad:\qquad(L_{AB},\qquad\textrm{Sig}_{Bob}(L_{AB}))

  3. When Alice receives the message with the address list and signature from Bob, she compares the list to her own and (if they are equal) decides deterministically5 whether she or Bob should represent the pair in the new round. When she and Bob have both done that, they broadcast the decision:

    Alice\rightarrow{}broadcast\qquad:\qquad{}R_{Alice}\\Bob\qquad\rightarrow{}broadcast\qquad:\qquad{}R_{Alice}

Alice and Bob have now mixed their addresses in a list, and the next round begins when every pair has confirmed that the current round is complete. In the next round, each representative from the first round is paired up to form |V|/4 pairs.

In the same way as the first round, Alice and the representative from the other pair mix their lists of anonymous addresses, and end up with a list of four anonymous addresses.

This process repeats itself until there is only one pair and one list of all the anonymous addresses.

Each round involves broadcasting 3×|V| messages, and with log|V| rounds, this mixing phase requires 3×|V|log|V| messages in total.

5 For example, by taking the first bit in a hash of the addresses

Advantages

  • An outside attacker cannot easily disrupt the mixing phase. We can simply choose to disregard any messages from anyone who is not in the list L
  • Not everyone needs to be online during the entire process; half of the members only need to be there for the first round, a fourth of them for the second round, etc…

Drawbacks

  • Higher complexity than the previous mixing protocol. Instead of O(|V|), this requires O(|V|log|V|) messages.
  • Any adversarial member who wants to disrupt the mixing can either (1) not participate or (2) broadcast fake representatives in the third step.
  • If a member is paired up with an adversary in the first round, he is not anonymous. In fact, his degree of anonymity depends on how many mixing rounds he takes part of before (if ever) mixing with an attacker. The attacker, however, must be in control of one or more of the legitimate member addresses.

Evaluation of binary mixing

The binary mixing scheme eliminates the risk of outsiders disrupting the mixing as was easily done in the simple scheme - now only members can do that. However, this improvement also came at a cost; the protocol is more complex message-wise (and thus time-wise).

Conclusion

In this post, I have introduced the concept of Bitmessage address mixing and a few examples where it will be useful. I do realize, however, that the two proposed protocols are far from perfect, and I must say that this is still a work in progress.

I am hoping to get some comments on the ideas and designs from the community in order to improve upon the work and get closer to something really useful.

About the author

Jesper Borgstrup Jesper is a Masters student of computer science at the University of Copenhagen.

Leave a Reply

Your email address will not be published. Required fields are marked *

* Copy This Password *

* Type Or Paste Password Here *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>