[ANNOUNCE] Bitmessage - P2P Messaging system based partially on Bitcoin

[bytemaster]

Bitmask: A Perfectly Anonymous, Naturally Scalable Peer-to-Peer Messaging System

Tommy Anderson
tommy a@mit.edu
www.bitmask.me

We were already planning on introducing some of your ideas as part of Project Quixote and really like some of your innovations and would like to include more of them.

If you would like to join our team and help develop your ideas as part of Project Quixote, please contact me via PM.

Keep up the innovation!

[1715050644]

1715050644

[1715050644]

1715050644

[greBit]

I really like these ideas, especially the use of ephemeral addresses to achieve anonymity and perfect forward secrecy. If you are looking for volunteer developers to help get a proof of concept off the ground I would likely be pretty keen.

I do however have a few questions ...

Offline use

Im a little concerned about the offline-use-case. I understand that advertisement packets have a limited lifespan (any idea how long?), so if I shutdown my machine for the weekend only to reconnect the following monday, it is possible that I miss advertisements meant for me. This means I would need to interrogate a 'storage node' at the cost of giving up valuable information that may help an attacker link an address with my real identity.

For an email replacement, the offline-use-case would be quite common, peers would come and go rather fleetingly. But perhaps this is not your target market, and one of your assumptions is that people will generally stay regularly connected.

Attacker makes lots of connections, analyses origin of permission packet

Thankfully you have included link-layer-encryption, so assuming that the crypto is good, it makes it harder for a global passive adversary. Am I right in assuming that any attacker trying to make large numbers of connections in order to perform statistical analysis on say the origins of a permission packet, would be very quickly blacklisted? i.e. due to the attacker needing to honour a bandwidth/storage 'contract' with each peer he connects with?

What about well funded attackers?

Global packets and scalability

Because of the minimum spanning tree assumption, a peer must continually relay all ad packets within the network or risk being classified as a malicious peer, because all ads will eventually make their way through the minimum spanning tree to the recipient peer. So if a peer receives an ad for a message that it’s the recipient of but never receives the same ad from peers attempting to drop ad packets, those malicious peers can be detected and blacklisted.

So here I get a little worried. "a peer must continually relay all ad packets within the network".

Say we have a network with 1 Billion peers who are all actively sending messages. For each message that is sent, we require numerous advertisement packets to be broadcast on the network. Depending on the lifetime and regularity at which advertisements are resent, the number of global packets that need to be move across each peer-peer link will be huuuge.

If I have interpreted this correctly, how can the network scale and how can low-bandwidth/low-storage nodes participate?

Getting permission to communicate, both parties need to be online?

Do Alice and Bob need to be simultaneously online for Alice's permission packet to reach Bob and for its response to come back to Alice? Or are permission packets also referenced by advertisements in a similar way to messages?

Enforcing behavioural contracts

I like your idea of making sure that nodes behave correctly and continue to store messages they have agreed to store etc.

I am wondering though, do peers need to be exact mirrors of each other? How can Alice check that Bob still stores messages for which Alice does not store herself?

What happens when Alice becomes disconnected from the network, and reconnects to a different set of peers? How do the new peers enforce her (preexisting storage contract) ? Or will she agree to a new contract when she makes the new connections?


Sorry to overload you with questions, im just trying to understand your proposal a little better

[greBit]

I forgot an obvious question topic ... the blacklists

Is the blacklist individual per node, or is this to become 'network knowledge'?

• For the latter, how do nodes achieve consensus on the contents of the list?
• For the former, could attackers not just find new peers to connect to if they become blacklisted. Since it may be tricky to determine quickly if a peer is malicious or not, the attacker may have a bit of time in which to perform some attack before being banned.

[jashper]

Hey greBit,

First off, really good questions; I left out a few of my thoughts from the paper, and you managed to hit a good portion of them!  Thanks for taking the time to read my paper!

For offline use, one could use a storage peer and query all messages in a large address range to preserve anonymity, but as you mentioned, that wouldn't be possible for low-bandwidth users.  One of the things I sort of glossed over in my paper that is important to offline use is the fact that instead of using special acknowledgement messages like Bitmessage, a peer can simply send another message back with an additional ephemeral key to let a peer know that he received his message.  In other words, acknowledgment messages are sent in the form of regular messages.

With this in mind, I think the easiest way of approaching offline use would be the following scenario:

1) Alice sends a message to Bob, who is currently offline

2) After waiting a certain amount of time, Alice never receives a message from Bob acknowledging that he received the message

3) Alice then sends a permission packet to Bob to restart the conversation with a new ephemeral key, and then resend the previously missed message.  One probably doesn't need to go through the whole permission packet process though, seeing as the one-time/ephemeral address concept I use is really only to mask bias in downloading messages (ie: the origin of broadcast for permission and ad packets is anonymized assuming the min spanning tree assumption)

4) Alice can continually resend permission packets every so often until Bob is back online

And yes, users need to be online to answer permission packets.  No reply means the user if offline.  Permission requests should be re-sent randomly, to preserve anonymity (ie: not have a constant amount of time hardcoded in the client)


Attackers making lots of connections is a subset of an area I'm still thinking about, that area being how to best bootstrap the network and how to handle conencting to new peers.  If a peer could gurantee that he is connected to every peer in the network, or even a large subset, he could theoretically start to aproximate network topologies and reduce anonymity depending on how peers are choosing to broadcast ads and permission packets.

To experiment and to try and find out best practices for maximizing anonymity in proportion to the amount of users in the network,  my next step is to create a visual simulator to aproximate network flow and p2p interactions.  This will be used as a proof of concept to estimate the anonymity of users given different topologies, as well as show how the network can react and defend against attempted attacks.  If this goes well, I'll then start client development.

As far as global packets and scalability, that is going to come down to coming up with clever ways of compressing address data, which is on my list of things to think about.  Another thought I had regarding this was to allow messages to be tagged as belonging to a certain category, such as e-mail, files, or twitter-esque service messgae, and then let peers decide what categories/services they want to participate in and relay (ie: think of this as a multiplexing different bitmask networks into one client)

For your behavioral contract question, the beauty of ads is that by relaying an ad to another peer and making them aware of the message's presence, you are simply letting them know that you are serving as a contact for obtaining this message; you don't necessarily have the message cached when you go to pass on the ad.  That way, you only ever checkup on a peer after they have requested a message from you and have received it, meaning you always know which files they should have from you.

When a peer disconnects, new contracts/agreements must be made.  If a peer disconnects too frequently, the peers he was connected to will blacklist him.

With regards to blacklisting, I had only thought of it as being an individual list per peer when I originally wrote the paper.  I'm not sure yet if network knowledge can be done in a trustless manner, as I'm still exploring that.  One idea I had was that you could allocate weight/trust to a node everytime he successfully transfers a message that belongs to you, but it would need to be done in a way that doesn't create an attack vector for discovering which messages you're interested in.

Thanks again, and keep those questions coming

[jashper]

Also, glad to hear you're interested in helping!  Let's chat about working on the simulator; I'll finish putting together some of my thoughts regarding the design and then shoot them over to you so you can take a look at them

I'm looking to put together some sort of startup to facilitate the development of the protocol as well as future applications (ie: separate e-mail clients, IM, Twitter like interface, all sorts of fun stuff).  The goal is to get this simulator proof of concept going and start moving in the direction of a business plan

Cheers,
Tommy

[greBit]

Hey Tommy, thanks for the replies!

I guess I am still a little concerned about the scalability issue. Despite the advertisements being quite small, I see this quickly becoming a bottleneck in similar way to the problems caused by the receive-it-all approach of BitMessage.  

What I have understood is that these advertisement packets will actually be flooded across the network (?) which is pretty expensive, and as the network size grows, the cost will increase non-linearly.

So I feel that you may need to find some way of partitioning the network in order to keep in manageable.

---
Anyway, allow me digress and detail a few of my motivations so we can see if there is some common ground for a potential collaboration

Basically I have a few projects in mind that depend on a layer one could call 'anonymous-message-passing'. The functional requirements being as follows:

• Alice can send a private message to Bob
• Alice can send a public message to the world (publishing model)
• Bob may be offline and can 'check for messages' by connecting to the network. His 'inbox' is stored by the network.
• Anyone can read any message. Private messages are kept private with cryptography.
• Messages are sent reliably, Alice should not need to receive an ACK, in the same way that I do not expect an ACK from gmail

Some of the key non functionals:

• Perfect forward secrecy
• inability for someone other than the person concerned to be able to relate a network identity(pub key) with the real world identity (an IP)

I believe that if this is done well, with a combination of a good technical solution with the appropriate incentive structures for participants, this could become a very useful tool.

I think this could go far beyond just having an alternative to email. When you consider that the endpoints of a communication could be API servers, HTML5 web-apps etc, there is a ton of things this could be useful for.

One example is that this could help remove reliance on Tor/I2p, since the anonymity is taken care of. Silk-road could be re-implemented as an open source browser extension for example!

So your work is a fine start to all of this. Please keep me updated with your progress on your paper and simulations etc and I will surely bother you soon with some more questions.

In the meantime, here is one:

Why not use an anonymous-PUT, anonymous-GET DHT as a basis? I just found a paper on a DHT which aims to do just that http://arxiv.org/pdf/1203.2668v1.pdf and of course we should not forget Freenet which was designed for this very purpose.

Could a messaging system not be implemented as a thin-layer over the top of 'Octopus' / Freenet / I2P ?

[phelix]

Please move detailed discussion about BitMask etc. to another thread.

[virtualmaster]

Interesting ideas with BitMask.
If you are have ideas to integrate with Namecoin identities also you can start a thread on the Namecoin forum also.
http://dot-bit.org/forum/index.php

[Singlebyte]

Securty Now (Twit TV) did a podcast about BitMessage.  I am just now watching it, but it doesn't look favorable.

http://twit.tv/show/security-now/420

[bytemaster]

Securty Now (Twit TV) did a podcast about BitMessage.  I am just now watching it, but it doesn't look favorable.

http://twit.tv/show/security-now/420

Looks like he is quoting outdated critiques of BitMessage's early encryption.

[minimalB]

This looks bad. Does this guy know what he is talking about? ... i think a lot of things have been sorted out already.

[becoin]

Securty Now (Twit TV) did a podcast about BitMessage.  I am just now watching it, but it doesn't look favorable.

http://twit.tv/show/security-now/420

BitMessage has all the potential of becoming the first crypto currency that will really offer intrinsic value and will be backed by something. It is backed by a 100% reserve stored security of your Internet communication. It'll be the first anti-NSA (and the likes) currency. Good job NSA! You're the driving force and engine for developing secure Internet communication systems and protocols. Keep up building big computer centers!

[Rassah]

This looks bad. Does this guy know what he is talking about? ... i think a lot of things have been sorted out already.

His main issues were concerns with scalability, some privasy issues regarding tracking ACK (acknowledgement) messages, etc, which Atheros himself claimed he's not even sure about (quote, "There is no clear defined line as I'm not even sure what the bottleneck will be (bandwidth? Disk IO? CPU? Memory?"). But overall he seemed to really like it as the first step to get things going. The TL;DR of his review was "Very neat system, that is very obviously in the very first stages of being developed, and it's great to see so many people giving serious critiques on it, and seriously working on trying to improve it.". Which is true.

[bytemaster]

This looks bad. Does this guy know what he is talking about? ... i think a lot of things have been sorted out already.

His main issues were concerns with scalability, some privasy issues regarding tracking ACK (acknowledgement) messages, etc, which Atheros himself claimed he's not even sure about (quote, "There is no clear defined line as I'm not even sure what the bottleneck will be (bandwidth? Disk IO? CPU? Memory?"). But overall he seemed to really like it as the first step to get things going. The TL;DR of his review was "Very neat system, that is very obviously in the very first stages of being developed, and it's great to see so many people giving serious critiques on it, and seriously working on trying to improve it.". Which is true.

I see no reason why BitMessage insists on addresses being a hash of the public key rather than the actual public key.  It isn't like anyone can remember or will manually type in the address.  This would allow you to get rid of the entire discovery step.

The ACK can be delayed by several hours and thus no one would know who sent the ack...

You need link-level encryption, plus modify the broadcast algorithm to randomly pick only one of your peers to broadcast to first.   Your peer would randomly pick one other peer to broadcast to... if after X amount of time you have not received an inv from all of your other peers you pick another random peer from the subset that haven't acked and broadcast to them... everyone else is doing the same thing.

Then increase the connections-per-node to 32.

The result of this kind of broadcast is that a node that is 'connected to everyone' would only have a 1 in 32 chance of detecting the first broadcast, a 2 in 64 chance of detecting one hop removed, a 4 in 128 chance of first receiving the message after 3 hops.....   At this point it becomes clear that being the 'first to broadcast' something as seen from a peer connected to everyone becomes meaningless... and link-level encryption prevents outside observers from watching the propagation of the message.

The only remaining attack is to man-in-the-middle the ECDH exchange used to establish the link-layer encryption...

 

[greBit]

I see no reason why BitMessage insists on addresses being a hash of the public key rather than the actual public key.  It isn't like anyone can remember or will manually type in the address.  This would allow you to get rid of the entire discovery step.

I agree completely.

The ACK can be delayed by several hours and thus no one would know who sent the ack...

You need link-level encryption, plus modify the broadcast algorithm to randomly pick only one of your peers to broadcast to first.   Your peer would randomly pick one other peer to broadcast to... if after X amount of time you have not received an inv from all of your other peers you pick another random peer from the subset that haven't acked and broadcast to them... everyone else is doing the same thing.

Then increase the connections-per-node to 32.

The result of this kind of broadcast is that a node that is 'connected to everyone' would only have a 1 in 32 chance of detecting the first broadcast, a 2 in 64 chance of detecting one hop removed, a 4 in 128 chance of first receiving the message after 3 hops.....   At this point it becomes clear that being the 'first to broadcast' something as seen from a peer connected to everyone becomes meaningless... and link-level encryption prevents outside observers from watching the propagation of the message.

The only remaining attack is to man-in-the-middle the ECDH exchange used to establish the link-layer encryption...

What frustrates me a little is that the problem of allowing Alice and Bob to communicate, anonymously over the internets, is by no means a novel problem. There is a metric-f*k-ton of material on the topic.

We also have fully implemented open source software such as Freenet / I2P that have been around for years.

Instead of reinventing the wheel completely, could BitMessage2 not build upon and improve existing, well tested, ideas?

For example, is there a reason why BM could not be implemented as a reliable-and-anonymous message channel by just building on top of a DHT such as freenet or similar? This would scale far better and we would not need to care about ACKs.


TLDR:  BitMessage2 should employ a more rigorous, scientific approach to its protocol design. It should relate itself to previous work and motivate each design decision.

[Rassah]

I see no reason why BitMessage insists on addresses being a hash of the public key rather than the actual public key.  It isn't like anyone can remember or will manually type in the address.  This would allow you to get rid of the entire discovery step.

Easier to copy/paste than the huge public key, + possible deterrent to quantum computing?

[justusranvier]

For example, is there a reason why BM could not be implemented as a reliable-and-anonymous message channel by just building on top of a DHT such as freenet or similar? This would scale far better and we would not need to care about ACKs.

Freenet already has a mail system that does everything Bitmessage does, with stronger privacy protections.

[bytemaster]

For example, is there a reason why BM could not be implemented as a reliable-and-anonymous message channel by just building on top of a DHT such as freenet or similar? This would scale far better and we would not need to care about ACKs.

Freenet already has a mail system that does everything Bitmessage does, with stronger privacy protections.

I have attempted to use Freenet's mail... it doesn't work!

[justusranvier]

I have attempted to use Freenet's mail... it doesn't work!

When did you try? There was a 0.1 version series that was basically useless, and a 0.2 series that works.

[jashper]

I see no reason why BitMessage insists on addresses being a hash of the public key rather than the actual public key.  It isn't like anyone can remember or will manually type in the address.  This would allow you to get rid of the entire discovery step.

I believe this sort of hashing is helpful for spam prevention.  In a network of this type, an identifier is needed for determining whether or not a message is intended for a specific peer, so that the peer can then retrieve and decrypt it.  If a public key is used as an identifier, any peer could simply monitor the network, scrape these keys, and send out spam messages for the user to decrypt.  If a hash is used instead, not only can a peer still identify that a message is for him, but he can reject any messages that fail to decrypt properly, as a result of spam bots not knowing his public key.

With this is in mind, users still need a way of securely sharing public keys, while minimizing spam to the simplest of problems, that problem being whether or not you want to speak to someone.  I propose such a way in the Bitmask paper with regards to permission packets and identity profile messages.  Think of it as using skype, and only accepting communication from either those who have added you to their list of contacts, or vice-versa.