Rate Limiting via peer specified challenges

  BIP: 154
  Layer: Peer Services
  Title: Rate Limiting via peer specified challenges
  Authors: Karl-Johan Alm 
  Status: Closed
  Type: Specification
  Assigned: 2017-04-12
  License: BSD-2-Clause

Abstract

An anti-DoS system which provides additional service for peers which perform proof of work.

Definitions

• POW : a proof of work using some arbitrary algorithm, such as SHA256
• challenge : a problem in the form of a POW specification and other data
• solution : a set of inputs which solve a given challenge
• free connection slot : an inbound connection slot that does not require POW
• POW connection slot : an inbound connection slot that requires POW
• SPH : Special Purpose Hardware, such as an ASIC chip
• GPH : General Purpose Hardware, such as a desktop computer
• Work : A measurement of optimized average resources (clock cycles, memory, ...) required to perform a single attempt at solving a given POW algorithm on GPH

Motivation

The Bitcoin network has a maximum number of inbound and outbound connections (125). It is trivial and relatively cheap to flood the network with connections via dummy nodes. Such an attack would result in (1) nodes evicting some other nodes in order to facilitate the new connection, and (2) nodes' ability to connect to each other being severely hampered. In this state, the network is vulnerable to e.g. a Sybil attack.

While the network is under pressure as in the above case, nodes could allow incoming connections anyway by requiring that the incoming peer performs some form of proof of work, to prove that they are not simply spamming the network. This would severely ramp up the costs of a Sybil attack, as the attacker would now have to perform proof of work for each node, beyond the free slots.

However, using the "standard" double-SHA256 POW algorithm in use by Bitcoin nodes to generate blocks means attackers can use special-purpose hardware to greatly accelerate the POW solving process. To counter this, the proof weight would have to be raised, but this would mean standard nodes would need to solve unacceptably costly challenges for simple operation. Therefore, a different proof of work which is arguably less sensitive to special-purpose hardware implementations is introduced. As this is not consensus sensitive, additional POW algorithms may be added in the future.

Specification

A peer that supports Proof of Work Rate Limiting defines two maximums:

• max connections, from which the maximum inbound connections is calculated as nMaxConnections - (nMaxOutbound + nMaxFeeler)
• POW connection slots, which define how many of the above inbound connections require a POW challenge

The peer must interpret two new network peer message types, challenge and solution.

In addition, the network handshake sequence must be altered slightly to facilitate the exchange of challenges and/or solutions:

• when a node connects, it may send a solution message prior to the version
• if it does, and

** the solution satisfies the local node, it is given a connection, but if ** the solution does not satisfy the local node (unknown, wrong, ...), a new challenge is sent and the connection is closed

• if it does not, and it is marked as needing to do POW, a challenge is sent and the connection is closed

This means nodes will be disconnected after receiving the challenge. It is then up to the individual nodes whether they solve the challenge and reconnect, or discard it and find a different peer (or wait for the peer to have an open free slot).

POW Identifiers

There are two POW identifiers currently. When a new identifier is introduced, it should be added with an increment of 1 to the last identifier in the list. When an identifier is deprecated, its status should be changed to Deprecated but it should retain its place in the list indefinitely.

ID	Algorithm Name	Work	Param size	Solution size	Provably Secure	SPH Resistance	Status
1	sha256	11k cycles	11+ bytes	0, 4 or 8 bytes	Yes	Low	Active
2	cuckoo-cycle	ss 28: 150G cycles / ~48M RAM	6+ bytes	168 bytes	No	High	Active

sha256

Properties:

Property	Value
Solution probability	sum((1/2)^i*(1-targetBE[i]))

Challenge format:

Range	Field Name	Data Type	Description
0	config_length	varint	Length of configuration part; always 9
1..4	target	uint32	Difficulty target, in the form of a compact size (like nBits in blocks).
5	nonce_size	uint8	Size of nonce in bytes; must be 0 (no nonce), 4 (uint32) or 8 (uint64)
6..9	nonce_offset	uint32	Location of nonce value in target
10..	payload_length	varint	Length of the input data
..	payload	byte array	Input data

Solution format:

Range	Field Name	Data Type	Description
0..	nonce	uint32/64, or data	Nonce value that satisfies challenge; for zero-byte nonces, this is variable data that is appended to the challenge payload before hashing

Note: SHA256 works in two "modes". # One is where the task is to insert a nonce into an existing data block so that the hash of the data block matches a given target; this is the conventional block proof of work behavior. # The other is where the whole or parts of the data chunk are given as input (a "big nonce"). In this case, the internal nonce size is zero bytes, and the task is simply to check whether the hash of the data matches the target. If it does not, there is no way to find a solution except by getting different input from the generator (a successor algorithm). This mode is used when SHA256 is a predecessor to another algorithm.

Additional notes:

• The initial nonce value (when present) for finding a suitable digest should be randomized, or a challenger may deliberately pick a challenge with "poor" outcomes to fool a node into spending more than predicted time solving.

cuckoo-cycle

Properties:

Property	Value
Solution probability	~1.0 for sizeshift=28, proofsize-min:-max=12:228

Challenge format:

Range	Field Name	Data Type	Description
0	config_length	varint	Length of configuration part; always 5
1	sizeshift	uint8	Size shift; must be equal to 28, but may be variable in the future
2..3	proofsize-min	uint16	Minimum number of edges in cycle; must be even and greater than or equal to 12 (recommended: 12)
4..5	proofsize-max	uint16	Maximum number of edges in cycle; must be even, greater than or equal to proofsize-min, and smaller than or equal to 254 (recommended: 228)
6	payload_length	varint	Length of the input data; must be 76, but may be variable in the future
7..	payload	byte array	Input data

Solution format:

Range	Field Name	Data Type	Description
0..3	nonce	uint32	Nonce which is appended to challenge payload to form solution graph
4..171	edges	uint32 array	42 values which identify each of the 42 edges in the cycle

Additional notes:

• The initial nonce value used for finding a graph with a suitable solution should be randomized, or a challenger may deliberately pick a challenge with "poor" outcomes to fool a node into spending more than predicted time solving.
• Further information on the recommended challenge parameters can be found here: https://web.archive.org/web/20230207054058/http://bc-2.jp/cuckoo-profile.pdf

Purpose Identifiers

There is only one Purpose Identifier currently. In the future, more Purpose Identifiers could be added for at-DoS-risk operations, such as bloom filters. When a new identifier is introduced, it should be added with an increment of 1 to the last identifier in the list. When an identifier is deprecated, its status should be changed to Deprecated but it should retain its place in the list indefinitely.

ID	Purpose Name	Description	Status
1	connect	Establish peer to peer connection	Active

Challenges

Challenges consist of one or several chained POW identifiers with accompanying parameters, as well as indicators for the purpose of the challenge, and a signature that lets the node verify the challenge authenticity.

After creating a challenge, the node signs it, delivers it to the peer, then discards it. When a node provides a solution to a challenge, the node verifies the signature and adds the challenge hash to a list of solved challenges along with its expiration time. This list is pruned on each insertion, removing any expired challenges.

If nodes needed to keep track of unsolved challenges, an attacker could hypothetically swarm a node, causing a DoS by having it generate so many challenges that it runs out of memory and crashes. By signing and discarding challenges, a node only has to retain challenges that were solved, and which have not yet expired, effectively DoS- protecting the node via the challenges themselves.

The challenge message type

A challenge consists of four parts: the POW specification, a purpose identifier, an expiration date, and a signature. The POW specification contains a list of tuples containing a POW identifier and corresponding POW parameters.

• Each POW identifier specifies a POW algorithm (see POW Identifiers)
• The POW parameters define the inputs and requirements of the POW algorithm
• The purpose identifier specifies the purpose of the challenge (see Purpose Identifiers)
• The expiration date is a UNIX timestamp indicating when the challenge expires
• The signed content should contain a signature of the hash SHA256(SHA256(pow-count || pow-id || pow-params || ... || purpose-id || expiration)), i.e. the hash of the entire challenge except for the signature length and data.

Field Size	Description	Data type	Description
1 byte	pow-count	uint8	Number of POW algorithms in the range [1..255]
4 bytes	pow-id	uint32	The POW algorithm to solve the problem with
?	pow-params	?	The POW parameters and payload
...	...	...	pow-id and pow-params for algorithms 2 and beyond
4 bytes	purpose-id	uint32	The purpose of the challenge
8 bytes	expiration	int64	Expiration UNIX timestamp
?	sign-len	varint	The length of the signature
?	sign	byte array	The signature data

For POW specifications with a pow-count > 1, the output of the succeeding POW algorithm will be appended to the input of the predecessor for all POW algorithms except the last one. Normally mid-layer (all but the last) POW algorithms have a zero-length input. Example implementing sha256(cuckoo-cycle):

Range	Field Name	Value	Comment
0	pow-count	2	Two POW algorithms
1..4	pow-id	1	sha256
5	pow-params (config_length)	9
6..9	pow-params (target)	0x207fffff	Resulting hash must be <= the compact hash 0x207fffff*
10	pow-params (nonce_size)	0	No nonce
11..14	pow-params (nonce_offset)	0	--
15..18	pow-params (payload_length)	0	0 byte input (turns into 32 byte input from successor)
19..22	pow-id	2	cuckoo-cycle
23	pow-params (config_length)	8
24	pow-params (sizeshift)	28
25..26	pow-params (proofsize-min)	12
27..28	pow-params (proofsize-max)	228
29	pow-params (payload_length)	76	76 byte input
30..105	pow-params	(random data)	A randomized challenge of 76 bytes
106..109	purpose-id	1	Purpose is a peer-to-peer connection
110..117	expiration	1491285696	Expiration is April 4 2017, 15:01:36 (JST)
118	sign-len	71	71 byte signature
119..189	sign	(signature)	Signature of above challenge

(* Compact 0x207fffff = 0x7fffff0000000000000000000000000000000000000000000000000000000000.)

The above should be interpreted as SHA256(cuckoo-cycle(random data || nonce)) < 0x7fffff0000000000000000000000000000000000000000000000000000000000.

• Run cuckoo-cycle on random data || nonce; increment nonce until solution is found, then

** Run SHA256 on 32 byte digest from above; if less than 0x7fffff0000000000000000000000000000000000000000000000000000000000, *** Mark solved.

• Otherwise loop back and increase nonce and continue finding solutions

The solution message type

A solution consists of two parts: the entire challenge, and solution parameters:

• The challenge must match the given challenge up to and including the signature bytes
• The solution parameters must form a valid solution to each POW step in the challenge

Field Size	Description	Data type	Description
1 byte	pow-count	uint8	Number of POW algorithms in the range [1..255]
4 bytes	pow-id	uint32	The POW algorithm used to solve the problem
?	pow-params	?	The input to the POW solver for the above algorithm
...	...	...	pow-id and pow-params for algorithms 2 and beyond
4 bytes	purpose-id	uint32	The purpose of the challenge
8 bytes	expiration	int64	Expiration UNIX timestamp
?	sign-len	varint	The length of the signature
?	sign	byte array	The signature data
?	solution	?	The solution to the challenge

Note that the solution contains the parameters for the last algorithm only. For each algorithm except the last one, the input is derived from the output of the successor. Example solution:

Range	Name	Value	Description
0	length	4	The input to the innermost POW is 4 bytes in length
1..4	nonce32	0x12345	The nonce used as input is 0x12345

The above example will provide a single nonce for the inner POW. For the SHA256(SHA256(challenge data || nonce32)) case, the solution would claim that SHA256(SHA256(challenge data || 0x00012345)) solves the challenge.

Signing and Verifying Challenges

Below is a suggestion for how to sign a challenge. The implementation generates a new, random key-pair at launch and uses that to sign all challenges until the node is shutdown.

Signing a Challenge

# (first time) Create a new random key-pair key and pubkey and keep these around until shutdown # (second+ time) Fetch key created above # Create a double-SHA256 sighash of the challenge in se