Skip to content

Archive: Paper notes

Jump to bottom
Albert Armea edited this page Mar 30, 2018 · 1 revision

Old notes copied verbatim from my paper notebook for archival purposes. Ideas here may be inaccurate or incomplete.

Mobile mesh based chat/mail

Why

  • Decentralize to avoid single points of failure
    • Cloud-based messaging servers can go down or otherwise refuse to deliver messages
    • ISPs and governments can block access to any IP-based communication
    • Mobile carriers are not accessible everywhere, can be expensive, or can refuse to deliver certain messages

How

  • Mesh of smartphones connecting directly to each other to bypass cellular networks, Wi-Fi, ISPs, etc.
  • On Android, use Wi-Fi Peer-To-Peer
  • On iOS, use MultipeerConnectivity
  • On both, can use BLE instead, which allows many-to-many communication without pairing
  • But we can't expect to have a fully connected graph at any time
    • Wi-Fi range is limited
    • Full connectivity only possible with repeaters everywhere
    • But people (and phones) move, so we can piggyback off this (so this is basically an automated sneakernet)

Similar

  • Riot & Matrix
    • Riot provides chat
    • Matrix provides decentralized communications
  • P2P libraries
    • Underdark
    • Wave
    • Thali -- everything but message relaying
    • Serval -- probably the closest (almost-) existing app
      • When I last investigated this, they required extra hardware for long-range communication and root for ad-hoc mode
      • But they've added Bluetooth support since then, so maybe that's changed?
      • Looks like they prioritize forming a regular mesh network -- I can't find anything about message relaying either (but this shouldn't be too hard to add)

TODO

  • Re-investigate Serval

Protocol v0

Idea

  • Every phone is always listening for connections to other phones
  • Every phone periodically (every few seconds/minutes?) scans for other phones and connects to them
  • Every phone has a collection of messages
    • Messages are encrypted and can only be read by the sender and recipient
    • Key exchange happens in person (using something like QR code or NFC)
    • Or people should be able to announce an identity (via a special message type)?
  • Upon connection, each phone copies every message it doesn't already have
  • Individual messages expire and are deleted after some amount of time or when the phone runs out of space (maybe based on difficulty of proof-of-work?)

Problems

  • Needs rate limiting to prevent DoS attacks (maybe via a proof-of-work system?)
  • Potentially large storage requirements to ensure long-distance delivery
  • Stress-case: international airports

Possible extensions

  • Message board/forum via publicly readable messages (refer to Usenet)
  • Rate limiting based on size of message -- phones can be more likely to download a message the shorter it is. Other factors could be number of nearby phones, how frequently a sender sent messages
  • Attachments
  • The application should be able to be downloaded directly from another phone (i.e. without an app store)
  • Forward secrecy using ephemeral key exchange
    • See Signal and off-the-record messaging
    • The key attached to the message can also be used as a read receipt of sorts

TODO

  • Simulate this (with moving nodes on a real map) to see how well it works.

Preventing denial-of-service attacks

(i.e. how to handle extremely high load)

Maybe botnet detection methods can help?

Need to establish consensus of who are abusive users

  • Problem: typical consensus algorithms need lots of communication and at least 50% of the network immediately available

Proof of work: use the block (from the blockchain)

  • Attach a publicly visible nonce to each message
  • Consider the message valid if the message concatenated with the nonce has a certain property in its hash
  • Invalid messages can be discarded
  • Nonces are expensive to make but easy to verify

Routing

Naive: every phone is a data mule - it has all data from every other phone it connected to (i.e. epidemic routing)

See delay-tolerant networking for other possible methods

Zach: talk to Colin/Eric about autoroute (for shorter distances or dense mesh areas)

  • Direct communication in these scenarios should also reduce shortage costs?

Fallback protocol v0

Implement both a real-time network and a store-and-forward network

  1. Mobile mesh local real-time network
  2. "Cloud"/internet-based forwarder
  3. Mobile mesh delay-tolerant network

Basically, if we can directly contact the destination and verify it received the message, don't waste resources in the mesh

Mesh simulation

Can probably take some inspiration from disease spread simulations

Message delivery receipts

Can help reduce network load by deleting a successfully delivered message from intermediaries

Receipt sent immediately on delivery

  • Reduces network redundancy ASAP
  • But it's just another message that itself can clog the network

Implicit receipt

  • Use the key attached to the next message for ephemeral key exchange as the receipt
  • Slower, but avoids extra messages for message deduplication

Ad-hoc app distribution

Only possible on Android, which allows installation of apps from unknown sources (i.e. not an app store)

On a rooted phone you can just read the apk from the filesystem and send it via Bluetooth, NFC, Wi-Fi tethering, etc.

On a non-rooted phone, some creativity is needed:

  • apk files are just renamed zip files
  • It's possible to write a recursive zip file/zip bomb
  • Android resources are just files inside the apk/zip
  • So it's theoretically possible to mess with the build system such that the apk contains itself as a resource, recursively. Now we can read it within the app.
  • Probably also want the build system to put an archive of the source code in the apk too

Data model v0

Goals

For messages destined to another device

  • Ensure eventual delivery to that device with high probability
  • Ensure that anything not needed for delivery is unreadable by this device
  • Prevent statistical packet analysis from determining who communicates with who

For messages destined to this device

  • Performant per-conversation message retrieval

Design

Probably want separate tables for retransmission to other devices and for messages intended for this device (a good ORM should be able to take care of this for you)

Retransmission table

  • Hash of data (as ID/index)
  • Data (encrypted blob), fixed size (256b?)
  • Expiry/proof-of-work

Syncing v0

Naive implementation: when you encounter another device, just replicate the databases as completely as possible

Idea's that won't work

Each device sends the hashes of all data blobs

  • If most blobs are small (less than 1KB) this is still a large fraction (at least 1/2^5) of all the data
  • If there are many (billions) blobs, this is still at least hundreds of megabytes of transfer per connection

Git-like syncing

  • Relies on a strict history to known all of the blobs - each blob has the hash of its parent
  • A strict history doesn't make sense for this

Rsync-like syncing

  • Also relies on a strict ordering, this time based on file positions
  • Filenames are sent in full to determine what files to sync

BitTorrent-like syncing

  • Set of hash blobs will does not change - it is defined at the start by the torrent

DNS

  • Hierarchal server architecture
  • Based on timeouts - updates to a given domain do not occur until a preset timeout is hit

Unexplored syncing ideas

  • Bloom filters (we're using this!)
  • Merkel trees
  • Rsync, specifically how it handles filenames (not actual content)
  • Gossip protocol, like epidemic routing (we're using this!)

Wi-Fi Peer to Peer

Gotcha - on Android, this requires user confirmation to connect to a new device

Workarounds

  • Modify the firmware on a rooted device with Xposed framework or by patching Android
    • This will severely limit usage
  • Use a different radio - BLE?
    • Low bandwidth - around 256 kbps peak
    • Not designed for serial communication
    • It's probably good for announcing though

Bluetooth Low Energy

  • Device advertises a service
  • The advertisement itself can include some data
  • We can include some subset of our database's Bloom filter/bit field in the advertisement
  • But because we'll have thousands or millions of messages on each device, putting all of them under a BLE/GATT service isn't really feasible
  • Classic Bluetooth allows pairless sockets communication as long as both devices agree on a UUID (using listenUsingRfCommWithServiceRecord and createInsecureRfcommSocketToServiceRecord)
    • So generate a UUID on service start (separate from the static one that declares that the advertisement is for this app)
    • Put it in the advertisement to coordinate getting a socket

BLE implementation

Advertisement format

  • Turns out only one GUID will fit in an advertisement (advertisements are 31 bytes, GUIDs are 16)
  • So split it in half
    • First half says the advertisement is for this app
    • Second identifies this session for making a connection
  • ScanFilters allow us to filter on partial GUIDs
    • Or do they? This only seems to work when some other app is scanning...

Hashing for Sync

Need a way to efficiently create a Bloom filter summary vector and query for an element

Naive implementation

  • Fully generate the vector on each sync - iterate over all rows, calculate their contribution, and return the union
  • To search, iterate over the rows and calculate the contribution, return matches
  • Doesn't really scale even if we can implement it as a single query

Idea 1: Cache each row's contribution

  • Add a new property to UnknownMessage (probably as a separate table) that stores the row's contribution
  • On each sync, to generate the vector, return the result of a single query or view that is the union of the contributions
  • Search is a where clause on that table

Bundling

RFC 4838 and 5050

Automatically establishing peer-to-peer connections

Things I've tried:

  • Wi-Fi Direct - requires user input to establish a connection
  • Bluetooth LE -> Classic handoff
    • Creating the connection used to work but fails now - I think something changed in Bluetooth recently
    • One of the Android examples suggests that maybe I should immediately be creating a new thread for every connection (separate from the send/receive threads) - there might be a lifetime issue for the BLE scan result threads

Unexplored existing autodiscovery and connection protocols

  • JXME/peerdroid - requires known & always available rendezvous peers to establish connections...
  • AllJoyn - deprecated, merged into IoTivity
  • IoTivity
  • Serval

Serval

Clone this wiki locally