The primary question I have received so far when describing how this project is using Bluetooth to create a lightweight, informal mesh, is “how far can it reach?”. The quick answer is “about 10m or 30ft”. That is the typical range of a Bluetooth radio, without interference. Obviously, that is not very far, and the response is usually “Well, can’t I just pass a note or tell the person directly what I want to say?”. This is a fair statement, and so we must do better. In the last 24 hours, I have tested and implemented two new ideas for the Gilgamesh, that address this problem in two very different ways.
First, I have implemented support for Wifi Direct, which is another way that modern Android phones, can create adhoc peer-to-peer networks. It has the same capabilities of discovery and dynamic names that we are build on top of for our broadcast message layer, and so the same hack we using with Bluetooth can be applied here.
Unfortunately, the names seem to be of much shorter length (like a typical Wifi SSID), but it can still be used for short messages, and we can come up with a way to packetize messages, as well. The upside of Wifi Direct is that its range is, in open spaces, up to 100m/300ft! That has amazing potential. You can see the relevant code here.
Second, within the limits of Bluetooth, we can employ some useful app behaviors to extend the range of any message. In the latest code, if you have paired with a trusted person’s device (using the built-in Bluetooth settings panel of your device), and the Gilgamesh app receives a broadcast message from that user, it will be automatically re-shared, aka re-tweeted, aka RT. (Yes, we are building old school Twitter here, just over Bluetooth). What this creates then is a chain reaction – “the wave” phenomenon that I blogged about earlier – that allows a message to propagate up to 30ft in any direction, over and over again, as long as there are trusted/paired devices out in the crowd.
By using the RT method, we can see the chain of users who have sent and replicated the message, and that helps embed trust and reputation into the message as well. Anyone looking to spread misinformation, would have to be on the ground in the area, and would need to convince many people to RT them, either through force or social engineering. This is many times more difficult than just being able to send a message in a global chatroom, like you can on some other apps, ahem.
In addition to the auto-retweet feature, anyone can press and hold on a message, and it will allow for a manually RT, whether you are paired with the sender or not. Finally, let’s not forget that anyone with any bluetooth device, be it a simple feature phone, an iPad or a laptop, can participate in this process, by changing their Bluetooth device name manually themselves, and setting it to a retweet message.
Through both of these new concepts, the simultaneous use of Bluetooth and Wifi Direct to extend the range, and the application and human-powered behavior of retweets, we can effectively extend the range of Gilgamesh to as far as you have people participating in it. It can even survive gaps in coverage, as people move from one mesh group to another, they would bring along their retweets.
Finally, if you haven’t yet, please read my thoughts on the four roles that can and need to be played by people and devices, for the gilgamesh to even be more robust.
hi Nathan,
kudos for a very interesting project. the new WiFi SSID functionality is especially exciting, as the broader range is likely to make the P2P network much more stable. I would like to contribute an idea on to counteract the shorter WiFi SSID length, which is of 32 bytes, each byte being 8 bits. your app could leverage the fact that modern Android phones have a built-in, standard dictionary. a dictionary recognizes, say, about 60k words, which is within 2 bytes. hence, without further compression, one could leverage the standard dictionary to send messages up to 16 words each. (characters in quotes could of course be left uncompressed.)
That is a very interesting idea! The only issue is that it breaks the “plain text” compatibility with non-app users, but if that wasn’t a concern, it definitely is a big breakthrough in usefulness.
Nathan:
indeed, “plain text” compatibility is a limitation. in practice though, whenever that is an issue, the user can always put text in quotes, to leave it in plain form. also — as you already suggest in the blog — a combination of BT and WiFi Direct (one in plain text, the other linked to the Android dictionary) could work best for most user cases. one can even think of situations in which the user wishes to leave part of the text readable to all, and part only accessible by trusted parties. to implement this (with BT, or even WiFi), one can simply associate to each device password used in the pairing a unique permutation of the dictionary (plus, possibly, other static info such as a mesh user id or web link).
Thanks for the great thoughts. I have been thinking about various markers in the first byte of the message that could indicate encoding, or message type. I think using the dictionary method or other compression techniques over Wifi Direct definitely makes a great deal of sense, as it is less necessary for that to be in plaintext.
As for encryption or obfuscation of message content, we’ve got a lot of thinking to do there. Sharing keys ahead of time with trusted parties does make the problem easier.
Nathan:
I think it’s a really worthwhile project. one application that comes to mind is the implementation of forms of digital voting for local communities in a way that is potentially secure against external (non-local) attacks or monitoring. of course, such schemes would also require a method to aggregate individual status messages and broadcast the results in a decentralized way. the “wave” effect you describe in the blog is one example of how individual behavior and mesh rules may jointly determine an aggregate response.
regarding compression — with the dictionary method, let me further note that it would make sense to sacrifice the last 2-byte “word” to associate to each of the remaining 15 words:
* inflection/tense information (6 entries: the 5 regular inflections, plus the empty string)
* a prefix regular expression (the empty string, plus 12 regular expressions, including ‘a’, ‘the’, ‘some’, ‘all’, ‘many’, …),
* a suffix regular expression (the empty string, plus 12 regular expressions including ‘to’, ‘for’, ‘of’, ‘and’, ‘or’, …)
* punctuation (4 regular expressions: question mark, comma, period or space).
with the added information on syntax, a phrase such as “the depth of the oceans” would now count as just 2 words in compressed form.
regarding security: I fully agree that designing procedures to (carefully) inherit trusted status without direct key exchange would be quite desirable in many user cases, and is highly non-trivial. let me just remark that, in practice, even the simplest scenario of direct key exchange and management is far from trivial — one issue being that, in any type of crypto scheme in which users set passwords that they must remember, they’ll inevitably end up using weak keys. one notable advantage of dictionary-based compression/encryption is that, even with weak, multiple-use keys, any brute-force attack would be limited by the difficulty to distinguish true plaintext from pseudo-plaintext generated by a wrong choice of key — instead of, say, “the sun is shining”, one would read, e.g., “the rain is pouring”.
thank you
i have a dream if we could have at same time 3G / 4G for long distances (like BitTorrent Chat) … that would be heaven … a global mesh