Lite Client Message Retrieval Proposal - Revision history

JonathanCoe: /* Possible refinement: Daily changing prefix values */

2015-01-04T16:13:41Z

Possible refinement: Daily changing prefix values

JonathanCoe: Added description of daily changing prefix values idea

2015-01-04T16:12:11Z

Added description of daily changing prefix values idea

JonathanCoe: Added section for 'Daily changing prefix values' idea

2015-01-04T14:35:15Z

Added section for 'Daily changing prefix values' idea

JonathanCoe: Reverted to using prefix length instead of prefix mask

2015-01-04T14:12:39Z

Reverted to using prefix length instead of prefix mask

JonathanCoe: Minor formatting correction

2014-12-23T11:08:58Z

Minor formatting correction

JonathanCoe at 10:58, 23 December 2014

2014-12-23T10:58:31Z

JonathanCoe: Updated note on streams

2014-12-23T10:58:08Z

Updated note on streams

JonathanCoe: Added note about streams

2014-12-23T10:57:13Z

Added note about streams

JonathanCoe: Updated to use prefix mask instead of prefix length

2014-12-23T10:55:22Z

Updated to use prefix mask instead of prefix length

AyrA: added proposal note

2014-12-20T19:38:05Z

added proposal note

@@ Line 102: / Line 102: @@
 ===Possible refinement: Daily changing prefix values===
-While the system described above gives a reasonable balance between anonymity and efficiency, it has some weaknesses. In particular, users sending messages to addresses which specify a non-zero prefix length value will tend to leak some information about who they are communicating with. By observing the prefix nonces of msgs sent by a particular node, an attacker may be able build up information about how many different addresses a given user is communicating with, who they are communicating with more often, and who they do not communicate with for certain periods of time.
+While the system described above gives a reasonable balance between anonymity and efficiency, it has some weaknesses. In particular, users sending messages to addresses which specify a non-zero prefix length value will tend to leak some information about who they are communicating with. By observing the prefix nonces of msgs sent by a particular client, an attacker may be able build up information about how many different addresses a given user is communicating with, who they are communicating with more often, and who they do not communicate with for certain periods of time.
 One possible way to mitigate this problem would be to modify the prefix filtering system so that the prefix values used to 'tag' msgs vary according to a time value. Instead of tagging msgs with the first n bits of the prefix defined in the destination address's pubkey, msgs could be tagged with the first n bits of a hash value. The hash value would be calculated from the first n bits of the prefix concatenated with a time value. The result of this would be that the identifying bits of the prefix nonce of a msg would change every so often in a predictable way, with the frequency of change defined by the time value used.
@@ Line 117: / Line 117: @@
 Advantages:
-* The information leaked by a user sending msgs to addresses which specify a non-zero prefix length value is greatly diminished, as the identifying bits in the prefix nonces of sent msgs change each day. Some information is still leaked, particularly when an attacker already knows the destination address(es) of sent msgs and can therefore calculate what the identifying prefix bits will be each day, but the overall amount of information leaked is substantially reduced.
+* The information leaked by a client sending msgs to addresses which specify a non-zero prefix length value is greatly diminished, as the identifying bits in the prefix nonces of sent msgs change each day. Some information is still leaked, particularly when an attacker already knows the destination address(es) of sent msgs and can therefore calculate what the identifying prefix bits will be each day, but the overall amount of information leaked is substantially reduced.
 Disadvantages:
 * When catching up with the network, lite clients must make a separate request for messages for each day in the time period that they need to check.

← Older revision		Revision as of 16:12, 4 January 2015
Line 102:		Line 102:

	===Possible refinement: Daily changing prefix values===		===Possible refinement: Daily changing prefix values===
−	~~XXX~~	+	While the system described above gives a reasonable balance between anonymity and efficiency, it has some weaknesses. In particular, users sending messages to addresses which specify a non-zero prefix length value will tend to leak some information about who they are communicating with. By observing the prefix nonces of msgs sent by a particular node, an attacker may be able build up information about how many different addresses a given user is communicating with, who they are communicating with more often, and who they do not communicate with for certain periods of time.
		+
		+	One possible way to mitigate this problem would be to modify the prefix filtering system so that the prefix values used to 'tag' msgs vary according to a time value. Instead of tagging msgs with the first n bits of the prefix defined in the destination address's pubkey, msgs could be tagged with the first n bits of a hash value. The hash value would be calculated from the first n bits of the prefix concatenated with a time value. The result of this would be that the identifying bits of the prefix nonce of a msg would change every so often in a predictable way, with the frequency of change defined by the time value used.
		+
		+	For example, if the time value is defined by the protocol as 00:00 on the current day in Unix time, then the identifying prefix bits used to tag msgs will be different each day, in a way that can be easily and reliably calculated by both the sender and the receiver of msgs. The result of this is that rather than all msgs ever sent to a given address having the same identifying prefix bits, all msgs sent to a given address on a given day have the same identifying prefix bits.
		+
		+	A rough pseudocode description of the procedure to calculate the prefixNonce for a msg follows:
		+	unixTime = getUnixTime()
		+	remainderSeconds = unixTime mod 86,400
		+	timeValue = unixTime - remainderSeconds
		+	hash = sha512(sha512(prefix[0-prefixLength] + timeValue))
		+	identifyingBits = hash[0-prefixLength]
		+	prefixNonce = identifyingBits + randomBits
		+
		+	Advantages:
		+	* The information leaked by a user sending msgs to addresses which specify a non-zero prefix length value is greatly diminished, as the identifying bits in the prefix nonces of sent msgs change each day. Some information is still leaked, particularly when an attacker already knows the destination address(es) of sent msgs and can therefore calculate what the identifying prefix bits will be each day, but the overall amount of information leaked is substantially reduced.
		+
		+	Disadvantages:
		+	* When catching up with the network, lite clients must make a separate request for messages for each day in the time period that they need to check.

← Older revision		Revision as of 14:35, 4 January 2015
Line 100:		Line 100:
	===Streams===		===Streams===
	The system described in this proposal is intended to be complementary to streams (i.e. both should be implemented). It is not intended to replace them.		The system described in this proposal is intended to be complementary to streams (i.e. both should be implemented). It is not intended to replace them.
		+
		+	===Possible refinement: Daily changing prefix values===
		+	XXX

@@ Line 24: / Line 24: @@
 == Proposed changes ==
-The pubkey of every hashed address contains two new fields: a 'prefix mask' field and a 'prefix' field. The value of the prefix mask field is determined by the owner of the pubkey. The prefix field is set randomly. The value of the prefix mask field defines what balance of efficiency and anonymity the owner of that address wants. If the owner of the pubkey wants maximum anonymity, then all the bits in the prefix mask field will be set to 0, allowing the prefix to be ignored entirely. On the other extreme, if the owner of the pubkey wants maximum efficiency in retrieving data at the expense of anonymity then all bits in the prefix mask field will be set to 1. Each additional bit set to one halves the proportion of the total data set that you will have to request in order to receive data destined for you. The positions of the bits set to 1 in the prefix mask field are selected randomly.
+The pubkey of every hashed address contains two new fields: a 'prefix length' field and a 'prefix' field. The value of the prefix length field is defined by the owner of the pubkey. The prefix field is set randomly. The value of the prefix length field defines what balance of efficiency and anonymity the owner of that address wants. If the value of the prefix length field is zero, then the prefix field can be ignored entirely, giving maximum anonymity. On the other extreme, if the value of the prefix length field is 32 (the maximum), then the full 32 bits of the prefix should be used, giving maximum efficiency in retrieving data. Each additional bit used halves the proportion of the total data set that you will have to request in order to receive data destined for you.
-All msgs have a 'prefix nonce' as part of their unencrypted data. This prefix nonce is always of a fixed length (32 bits) to avoid leaking information. When sending a msg to an address, the sending client examines the destination pubkey's prefix mask field and records which bit positions (if any) are set to 1. The sending client will then set the bits in the corresponding positions of the prefix nonce to match those found in the destination pubkey's prefix field. The remaining bits of the prefix nonce are set randomly.
+All msgs have a 'prefix nonce' as part of their unencrypted data. This prefix nonce is always of a fixed length (32 bits) to avoid leaking information. When sending a msg to an address, the sending client examines the destination address's pubkey and sets the first n bits of the prefix nonce to match the prefix found in the pubkey. The remainder of the prefix nonce is set randomly.
-When a lite client wishes to retrieve msgs from the network, it makes a request to a server for all msgs which have a prefix nonce where the bits set to 1 in the prefix mask of the receiving address's pubkey match the prefix field of the receiving pubkey.
+When a lite client wishes to retrieve msgs from the network, it makes a request to a server for all msgs which have a prefix nonce where the first n bits matches the prefix of the lite client's address(s).
 === Pubkey object ===
@@ Line 39: / Line 39: @@
 | 4||[[Protocol_specification#Pubkey_bitfield_features|behavior bitfield]]||uint32_t||A bitfield of optional behaviors and features that can be expected from the node receiving the message.
 |-
-| 4||prefix_mask||uint32_t||A bit mask that defines which bits from the prefix field should be used.
+| 1||prefix_length||uint8_t||The number of bits from the prefix value that should be used. Must be in the range 0-32.
 |-
 | 4||prefix||uint32_t||The prefix value. Contains 32 randomly set bits.
@@ Line 62: / Line 62: @@
 ! Field Size !! Description !! Data type !! Comments
 |-
-| 4||prefix_nonce||uint32_t||The prefix nonce.
+| 4||prefixNonce||uint32_t||The prefix nonce.
 |-
 | ?||encrypted||uchar[]||Encrypted data. See [[Protocol_specification#Encrypted_payload|Encrypted payload]]. See also [[Protocol_specification#Unencrypted_Message_Data|Unencrypted Message Data Format]]
@@ Line 71: / Line 71: @@
 ===Example 1===
-If Alice does not care about anonymity, she can have her address's pubkey specify that the full 32 bits of the prefix field should be used. This is done by setting all bits of the pubkey's prefix mask field to 1.  This means that all msgs sent to her will effectively be uniquely tagged for her address (there are roughly 4 billion possible prefix values). This will allow Alice to only download msgs that are destined for her, giving her maximum usability and convenience at the expense of anonymity.
+If Alice does not care about anonymity, she can have her address's pubkey specify that the full 32 bits of the prefix field should be used. This means that all msgs sent to her will effectively be uniquely tagged for her address (there are roughly 4 billion possible prefix values). This will allow Alice to only download msgs that are destined for her, giving her maximum usability and convenience at the expense of anonymity.
 ===Example 2===
-If Bob wants to achieve a balance between anonymity and convenience, he can have his address's pubkey specify that 4 bits of the prefix field should be used. This is done by setting 4 randomly selected bits of the pubkey's prefix mask field to 1. This means that all msgs sent to his address will have a prefix nonce where the 4 bits in the positions set to 1 in the prefix mask will match the corresponding bits in his pubkey's prefix field. A random distribution of prefixes in a stream should mean that roughly 6.25% of msgs in a stream will have a prefix nonce where the bits in those positions match the values of those bits in his pubkey's prefix field. Therefore Bob will be able to download roughly 6.25% of the msgs in a stream and still be guaranteed to receive all msgs destined for him.
+If Bob wants to achieve a balance between anonymity and convenience, he can have his address's pubkey specify that 4 bits of the prefix field should be used, e.g 0110. This means that all msgs sent to his address will have a prefix nonce beginning with 0110. A random distribution of prefixes in a stream should mean that roughly 6.25% of msgs in a stream will have a prefix nonce beginning with 0110. Therefore Bob will be able to download roughly 6.25% of the msgs in a stream and still be guaranteed to receive all msgs destined for him.
 ===Example 3===
-If Carol wants maximum anonymity then she can have her address's pubkey specify that zero bits of the prefix field should be used. This is done by setting all of the bits of the pubkey's prefix mask field to 0. This means that msgs sent to her will contain no identifying information, only a totally random prefix nonce. Carol will have to download and attempt to decrypt all msgs in a stream in order to be sure of receiving all msgs destined for her.
+If Carol wants maximum anonymity then she can have her address's pubkey specify that zero bits of the prefix field should be used. This means that msgs sent to her will contain no identifying information, only a totally random prefix nonce. Carol will have to download and attempt to decrypt all msgs in a stream in order to be sure of receiving all msgs destined for her.

@@ Line 62: / Line 62: @@
 ! Field Size !! Description !! Data type !! Comments
 |-
-| 4||prefixNonce||uint32_t||The prefix nonce.
+| 4||prefix_nonce||uint32_t||The prefix nonce.
 |-
 | ?||encrypted||uchar[]||Encrypted data. See [[Protocol_specification#Encrypted_payload|Encrypted payload]]. See also [[Protocol_specification#Unencrypted_Message_Data|Unencrypted Message Data Format]]

← Older revision		Revision as of 10:58, 23 December 2014
Line 99:		Line 99:

	===Streams===		===Streams===
−	~~This~~ system described in this proposal is intended to be complementary to streams (i.e. both should be implemented). It is not intended to replace them.	+	The system described in this proposal is intended to be complementary to streams (i.e. both should be implemented). It is not intended to replace them.

← Older revision		Revision as of 10:57, 23 December 2014
Line 97:		Line 97:
	===Non-hashed addresses===		===Non-hashed addresses===
	If non-hashed addresses are introduced in the future, this scheme will not apply to them, as they will not have pubkeys. Users of non-hashed addresses will still need to download and attempt to decrypt all msgs in each stream in which they have an address. This makes sense though, as the whole point of introducing non-hashed addresses is to give people the ability to choose greater anonymity at the expense of convenience.		If non-hashed addresses are introduced in the future, this scheme will not apply to them, as they will not have pubkeys. Users of non-hashed addresses will still need to download and attempt to decrypt all msgs in each stream in which they have an address. This makes sense though, as the whole point of introducing non-hashed addresses is to give people the ability to choose greater anonymity at the expense of convenience.
		+
		+	===Streams===
		+	This proposal is intended as a complementary system to streams (i.e. both should be implemented). It is not intended to replace them.

← Older revision		Revision as of 19:38, 20 December 2014
Line 1:		Line 1:
		+	{{Template:Proposal}}
		+
	== Introduction ==		== Introduction ==
	This is a proposal to introduce a mechanism into the Bitmessage protocol that will allow 'lite' Bitmessage clients to retreive messages that have been sent to them without downloading all the messages in a stream.		This is a proposal to introduce a mechanism into the Bitmessage protocol that will allow 'lite' Bitmessage clients to retreive messages that have been sent to them without downloading all the messages in a stream.