Skip to content

Instantly share code, notes, and snippets.

@gluk256
Last active October 5, 2017 14:19
Show Gist options
  • Save gluk256/4654922ca45eb9d0846d941d7ca326f4 to your computer and use it in GitHub Desktop.
Save gluk256/4654922ca45eb9d0846d941d7ca326f4 to your computer and use it in GitHub Desktop.

Overview

Whisper is a pure identity-based messaging system. Whisper provides a low-level (non-application-specific) but easily-accessible API without being based upon or influenced by the low-level hardware attributes and characteristics. Peer-to-peer communication between nodes running Whisper clients uses the underlying ÐΞVp2p Wire Protocol. Whisper is not designed to provide a connection oriented system, nor for simply delivering data between a pair of particular network endpoints. Whisper is a new protocol designed expressly for a new paradigm of application development. It is designed from the ground up for easy and efficient multi-casting and broadcasting, and also for low-level partially-asynchronous communications. It is designed to be a building block in next generation ÐApps which require large-scale many-to-many data-discovery, signal negotiation and modest transmissions with an absolute minimum of fuss and the expectation that one has a very reasonable assurance of complete privacy. At its most secure mode of operation, Whisper can theoretically deliver 100% darkness (at a considerable cost of bandwidth and latency). Whisper should also allow the users to configure the level of privacy (how much information it leaks concerning the ÐApp content and ultimately, user activities) as a trade-off for performance.

Methods of probabilistic routing

Fundamentally, all systems present a trade-off between the efficiency of deterministic (and thus supposedly optimal) routing and darkness (or privacy). One of Whisper's differences is in providing a user-configurable trade-off between the privacy and efficiency. At its most dark, Whisper nodes are entirely reactive - they receive and forward messages, trying to maximise the utility of information transmission to the peers. However, Whisper is also designed to be able to route probabilistically using two methods, both giving away minimal routing information and both being exceptionally resilient to statistical attacks from large-scale metadata collection.

Peer steering via rating

The first builds on the functionality of the ÐΞV-p2p backend. This backend provides the ability of Whisper to rate peers and, over time, probabilistically alter (or steer) its set of peers towards those that deliver the most useful information. Ultimately, as the network evolves and the peer set is steered, the number of hops between this peer and any others that tend to be good conduits of useful information is minimised (be they emitters or simply well-positioned hubs). Conversely, peer steering also incentivises nodes to provide useful information to their peers. The risk of being identified as an under-performing peer and thus being dropped in favour of other nodes give nodes an incentive to cooperate and share the most useful information. Usefulness in this case is measured along three dimensions:

  • is provably difficult to author (using a proof-of-work function detailed below)
  • has a low time-to-live (TTL), ie., close expiry date
  • and has a high match to the node's Bloom filter.

Explicit topic advertising

The second mode of probabilistic routing is more dynamic, i.e., it is affected by the actual dapps using the node. Nodes are informed by their ÐApps about the topics they are interested in. The node then can advertise these topics to their peers. Topics may be described using masks or Bloom filters, due to the information loss will reduce the amount of information leaked and make passive statistical attacks arbitrarily difficult to execute. The determination of the amount of information to give to peers can come directly from the user or derived from topic/traffic modelling. The latter can be desribed as: "Given the information coming from this peer and my models of information distribution made from total traffic, am I receiving the amount of useful valuable information that I would expect to receive? If so [VT: if not, no?], narrowing it down with additional description information to the peer may be warranted." These settings can even be configured (i) per-peer, i.e., more trusted/longer-lasting peers may be afforded greater amounts of information, or (ii) per-ÐApp, i.e., ÐApps that may be more sensitive could be afforded less advertising than others. Through combining and reducing the Blooms/masks, weaker Nth-level information can be provided to peers about their peers' interests, forming a probabilistic topic-reception vortex around nodes. This gravity-well in the topic space gets weaker (and thus usefulness less certain) the farther away interested peers are using the number of hops as distance.

Basic Protocol Elements

Key concepts in Whisper are envelopes, topics and messages.

Envelopes

If Whisper is considered a datagram messaging system then envelopes are the packet format which encapsulate the potentially encrypted datagrams together with some metadata. Since envelopes need to be comprehensible by any node, they themselves are unencrypted.

Envelopes are transmitted as RLP-encoded structures of the following format:

[expiry: P, ttl: P, [topic0: B_4, topic1: B_4, ...], data: B, nonce: P]

They contain metadata pertaining to the message/datagram such as (i) time to live (TTL), (ii) expiry time and (iii) topics (see below), (iv) the message itself and finally (v) a nonce.

Expiry is specified in Unix time format (seconds since epoch).
Following this point in time the envelope should no longer be transmitted.

TTL is given in seconds. Implied insertion time is derived as the expiry time minus the TTL. If the implied insertion time is in the past, the envelope is considered invalid and should be dropped immediately. The transmitting peer can be punished for relaying invalid envelopes.

Topics are a list of byte sequences and can be thought of as indexes recorded in order to help an interested party ("recipient") find messages or aid forwarding nodes in routing messages towards their recipients.

The message encapsulates the encrypted payload, some metadata and optionally a signature (see below). The nonce allows the originator node ("sender") to prove that some arbitrary amount of work was done on the message.

Nonce is a 32-byte sequence and is used to prove that some computational work was done on the particular message. Proof of work (PoW) is the SHA3 of the concatenation of the SHA3 hashes of each of the first 4 components of the envelope and the nonce. When this final hash is interpreted as a BE-encoded value, the smaller it is, the higher is the PoW.

Topics

The subject is an arbitrary byte sequence associated with the message interpreted by the application originating it, e.g., twitter-style hash-tags , keywords or encryption keys to the message (in version 4, see below). Topics are defined as the leftmost 4 bytes of the SHA3 hash of this subject. Topics are thus cryptographically secure masks of this application level subject/category to be used in probabilistic partial classification of messages. The size of four bytes was chosen to minimise space should a large number of topics be mentioned while still keeping a sufficiently large topic space to avoid large-scale collision. The topics are serialised as RLP lists, but the order of topics does not matter, they represent sets of indexes that nodes use to find and route envelopes.

Messages

The message data is always encrypted. In version 2 of the protocol (current version), no explicit authentication token is given to indicate that the message is encrypted. Would-be readers of a message must know ahead of time, through the choice of topics they filtered for, that the message is encrypted with a particular key.

A clear text of the message is formed as the concatenation of (i) a single byte for flags, followed by (ii) additional metadata (as stipulated by the flags) and finally (iii) the actual payload.

Currently only one bit is used as a binary flag, if set, it indicates the presence of an optional signature in the following metadata field. The message therefore has the following structure:

flags: 1 byte
optional signature: 65 bytes
payload: variable

All other bits of the flags byte are not yet given a purpose and should be set randomly. A message is invalid if bit 0 is set but the total data is less than 66 bytes (since this wouldn't allow it to contain a signature).

It is left to the application level to determine that the message is indeed from a particular sender. Since the signature is a part of the message and not outside in the envelope, those unable to decrypt the message data are also unable to access the signature.

The signature, if provided, is the ECDSA signature of the SHA3-256 hash of the unencrypted payload using the secret key of the originator identity. The signature is serialised as the concatenation of the r, s and v parameters of the SECP-256k1 ECDSA signature, in that order. r and s are both big-endian encoded, fixed-width 256-bit unsigned. v is an 8-bit big-endian encoded, non-normalised and should be either 27 or 28.

The payload is arbitrary variable-length byte sequence. See later on limiting the length of the payload.

The message will also include a MAC starting from version 5.

In the Javascript API, the distinction between envelopes and messages is blurred. This is because ÐApps should know nothing about envelopes whose messages cannot be inspected. The fact that nodes pass envelopes around regardless of their ability to decode the message (or indeed their interest in it at all) is an important component in Whisper's dark communications strategy.

Encryption of Message Payloads in version 4

Message payloads are encrypted in one of two ways. If the message has a specific recipient, then ECIES is used with the specific recipient's SECP-256k1 public key. If the message has no specific recipient, then it is encrypted with the topics. The payload is encrypted symmetrically using AES-256 with a randomly generated key, then this key is encrypted with each of the topics. As a result anyone who knows at least one topic, can decrypt the message.

When handling an incoming message, a node uses the following procedure. Upon receipt of a message, if the node detects a known topic, it can decrypt the message. If all topics are unknown, then message is not addressed to this node. If there are no topics, it means that the message is encrypted asymmetrically. In this case, the node tries to decrypt the message with its own private key; only the right recepient will succeed.

The use of abridged keys as a topic ensures that nodes that only forward a message and don't know its topics in advance are unable to decrypt the message.

Basic Operation

Nodes are expected to receive and send envelopes continuously, as per the protocol specification. They should maintain a map of envelopes, indexed by expiry time, and prune accordingly. They should also efficiently deliver messages to the front-end API through maintaining mappings between topics and envelopes.

When a node's envelope memory becomes exhausted, a node may drop envelopes it considers unimportant or unlikely to please its peers. Nodes should rate peers higher if they pass them envelopes with lower TTLs and higher proofs-of-work. Nodes should blacklist peers if they pass invalid envelopes, i.e., expired envelopes or envelopes with an implied insertion time in the future. [gluk256: the exact relation between TTL and PoW in assessment of the peer's reputation is yet to be determined]

Nodes should always keep messages that its ÐApps have created. Though not now, later versions of this protocol may allow ÐApps to mark messages as being "archived" and these may be stored and made available for additional time.

Nodes should retain a set of per-ÐApp topics it is interested in (Bloom filters).

Creating and Sending Messages

To insert a message, little more is needed than to place the envelope containing it in the node's envelope set that it maintains; the node should, according to its normal heuristics retransmit the envelope in due course. Composing an envelope from a basic payload, possible identities for authoring and access, a number of topics, a time-to-live and some parameters concerning work-proving targets is done through a few steps:

  • Compose the message data by concatenating the relevant flag byte, a signature of the payload if the user specified a valid author identity, and the user-given payload.
  • Encrypt the data if an access ("recipient") identity's public key is given by the user.
  • Compose topics from the first 4 bytes of the SHA3 of each topic.
  • Set user-given attribute TTL.
  • Set the expiry as the present Unix time plus TTL.
  • Set the nonce as that which provides the most work proved as per the previous definition, after some fixed amount of time of cycling through candidates or after a candidate surpasses some boundary; either should be given by the user.

Topic Masking and Advertising (Proposal)

Nodes can advertise their topics of interest to each other. For that purpose they use a special type of Whisper message, which will be part of the Whisper protocol. The size of Bloom filter they send to each other is 64 bytes. Subsequently the rating system will be introduced: peers sending useful messages will be rated higher than those sending random messages. A message matches the Bloom filter, if any one of the topics in this message, converted to the Whisper Bloom filter, will match the Bloom filter.

Whisper Bloom function accepts an abridged topic (4 bytes) as a parameter, and produces a 64-byte sequence, where three bits (at the most) are set to one, and the rest are set to zeros, according to the following algorithm:

  1. Set all the bits in the resulting 64-byte filter to zero.
  2. Take 9 bits form the abridged topic, and convert to an integer value (range: 0 - 511).
  3. This value defines the index of the bit in the resulting 512-bit hash, which should be set to one.
  4. Repeat steps 2 & 3 for the second and third bit to be set in the resulting hash.

Thus, in order to produce the Bloom filter, we use 27 bits out of the 32 bits of the abridged topic. For more details, please see the C++ implementation of the function TopicBloomFilterBase::bloom() [https://github.com/gluk256/webthree/blob/develop/libwhisper/BloomFilter.h]

Proof of Work vs. MSCW

The purpose of PoW is spam prevention. But spam could also come in the form of inflated messages. Additionally, the current form of PoW encourages cheating. For instance, nodes could pack many messages together, and then send them in one packet, thus saving on computing PoW.

The cost of computing PoW can be regarded as the price you pay for allocated resources if you want the network to store your message for specific time (TTL). In terms of resources, it does not matter if the network stores X same-sized messages for Y seconds, or Y messages for X seconds. Or N messages of Z bytes versus Z messages of N bytes. So, required PoW should be proportional to both message size and TTL.

I propose to introduce another parameter: Message-Specific Cost of Work (MSCW). It should be calculated as average number of iterations, required to achieve the current PoW. If PoW is number of initial zero bits in the hash, then:

MSCW = (2^PoW) / (size * TTL)

MSCW should be used as aggregated parameter to assess the message priority.

Proposals for Version 5

  • Introduce MAC, along with an additional binary flag. Enforce it unless the message is singed (in which case the signature serves as MAC).
  • Signatures must be encrypted as well, along with the payload. Otherwise too much metainformation is revealed.
  • Topics-based encryption. Topics serving as key to the message (as in version 4), with improved KDF.
  • Message (payload) size must be limited, otherwise somebody will be able to send one huge message and block the entire network with it.
  • MSCW should be used as aggregated parameter to assess the message value, instead of PoW and TTL.
  • Introduce an additional binary flag to distinguish symmetric and asymmetric encryption.
  • For asymmetric encryption topic should contain the hash of salted destination, along with the salt.
  • Message size reveals too much metainformation. Proposed solution: allow only certain message sizes: 64, 128, 256, 512 and so on. On average it will increase the message size by 50%.
  • Message parameters check (TTL, PoW, etc.). Drop peer in case of attempted cheating.
  • Currently, messages created "in the future" are not allowed (dropped and peer is disconnected). But what if two computers are not synchronized? In that case one always produces "future" timestamps (from another's point of view). We should allow for some deviation (several seconds in the future), but in this case MSCW should be adjusted accordingly (decreased).
  • Bloom Filter exchange. Use Bloom Filters for message prioritization.
  • Nonce (4 bytes) is too short. Consider increasing the nonce size.

Suggestions for later versions

  • Rating system for peers, based on Bloom Filters and MSCW.

  • Integration with light client. Incentives for full nodes to accept light client connections, etc.

  • Each node may advertize its own PoW/MSCW requirements (requires another msg size, or changes in Status msg format).

  • Steganography support, providing easy interface.

  • Support for plausible deniability through the use of session keys (ÐApp level).

  • "Nothing up my sleeve" policy. Allow to customize encryption, but provide a default option (e.g., AES-256). Choice of several algorithms and their combination.

  • Currently, it's not practically possible to create high PoW in real-time, because ÐApps need to spend time on PoW. This gives advantage to the ÐApps which can create precalculated messages (including spam, etc.). If I wanted to send a very important message very quickly, I still need a lot of time for PoW. Is there a way to introduce some kind of payment system without compromising privacy?a

  • Private Whisper Servers. There may be another solution: a server which promises to collect and deliver all messages (filtered on unfiltered) if you subscribe for a small fee. Maybe we can ask NSA to do it for free -- they will collect and store all the messages anyway :) In any case, it might be similar to some kind of email-server. A lot of people would be happy to pay a small fee for reliable devlivery of private anonymous email -- there is definitely a market for that.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment