4.5 Rate Control Through Adaptive Proof of Work

4.5.1 Introduction

In Proof of Work-based blockchains, a built-in rate limit is enforced by the mining difficulty adjustment and the message fees. Without this filter, however, an attacker may be able to easily issue a very large number of messages to potentially harm the network. In order to enable the machine-to-machine economy, IOTA allows neither mining race nor fees, which makes an explicit rate control mechanism necessary. In order to ensure that the network traffic does not exceed the allowed throughput determined by the limited resources, it is fundamental to limit the number of messages issued at node level.

The mechanisms described act as an emergency break during spam attacks, by slowing down the rate of messages a node can issue. For honest nodes, the proof of work difficulty should be small enough not to hamper performance. Finer controls on the access are developed in Section 4.6 - Congestion Control, which regulate network traffic during normal periods of congestion.

The Rate Control specification depends on the following specifications:

• 3.3 - Peer Discovery

• 4.2 - Timestamps

4.5.1.1 Legacy Implementation

In the legacy IOTA implementation, a user is asked to solve a proof of work (PoW) before issuing a new message. The user can either perform that computation locally or outsource it to a third-party service.

In the legacy network, the difficulty of the PoW is set to some value POW_DIFFICULTY. Received messages are stored in a queue and processed in FIFO order. The protocol dictates that the nodes forward messages if and only if the difficulty of the PoW performed is greater or equal to POW_DIFFICULTY. Otherwise, messages shall be dropped.

4.5.1.2 Proposal

Similar to the legacy implementation, we require the solution of a given cryptographic puzzle before a message is issued. Here, however, we impose that the difficulty of the challenge progressively increases as a node issues multiple messages in a short time interval.

The goal of this document is to define this rate control mechanism, called Adaptive PoW (APoW), which permits nodes' theoretical throughput to be independent on their hardware equipment. We believe that this mechanism is fundamental to prevent spam and denial-of-service attacks, disallowing dishonest nodes from inflating their neighbors' buffers through large number of messages in a short time. Unlike APoW, the congestion control mechanism described in Section 4.6 - Congestion Control sets the actual throughput depending on nodes' access Mana, and protects the protocol against Sybil attacks and selfish behavior.

4.5.2 Adaptive Proof of Work

All nodes in the network have knowledge of the following three fixed global parameters:

• Base difficulty $(d_0)$. It sets the initial difficulty of PoW.
• Adaptation rate $(\gamma\in [0, 1])$. It provides the rate at which difficulty will be adjusted. Equivalently, $1/\gamma$ indicates how many messages can be sent per time window without increasing the PoW difficulty.
• APoW time window $(w>0)$. It describes the width of the time interval considered by the algorithm, i.e., its granularity.

4.5.2.1 Message Generation

Let $t$ be the output of the function CurrentTime(). If node m wants to issue a new message, it shall perform a PoW with difficulty $d_m(t)$ such that

$d_m(t) = d_0 + \left \lfloor{\gamma\cdot r_m(t)}\right \rfloor$

where $r_m(t)$ represents the number of messages issued by node m with (message) timestamp in the interval $[t-w, t]$. Note that when $\gamma = 0$, the algorithm becomes equivalent to the legacy IOTA implementation.

4.5.2.2 Message Verification

When a node n receives a message from a neighbor, it shall check that PoW with an appropriate difficulty was performed. The verification of the correctness of the PoW computation is the last step of the parser checks, right after signature verification (see Section 2.4 - Data Flow). Let us assume that node n receives a message with difficulty $d_m$ issued by node m. To decide whether this message should be discarded, node n counts how many messages $r_m(t)$ issued by m it has received in the last $w$ time units. In accordance with the formula above, the node validates the PoW only if the following condition is satisfied:

$d_m \geq d_0 + \left\lfloor{\gamma\cdot r_m(t)}\right\rfloor.$

Discussions on the correctness of this procedure can be found on a related article.

4.5.3 Algorithm

4.5.3.1 Protocol Parameters

In line with the previous section, all nodes know the constants shown by Table 4.5.1.

Parameter	Type	Description
POW_BASE	integer	The base difficulty $d_0$
APOW_RATE	float	The adaptation rate $\gamma$ (proposed values [0.1 - 1])
APOW_WINDOW	integer	The APoW time window $w$ (proposed values [10 - 60s])

Table 4.5.1: Global constants.

The choice of the time window is crucial in the correct functioning of the algorithm. Our claim is that the time window must be kept small for two main reasons:

• Message burst can be captured;
• Implementation is easier as it requires smaller caches.

However, it is fundamental to keep this time window at least larger than the gratuitous network delay DLARGE (see Section 4.2 - Timestamps).

4.5.3.2 Local Variables and Metadata

Local variables and metadata are described in Table 4.5.2.

Variable/Metadata	Type	Description
timestamp	integer	A value declared by the node representing time at which the message has been issued
nodeID	nodeID	Identity of the node issuing the message defined as the blake2b hash of its public key
targetDifficulty	integer	Minimum difficulty needed to pass the APoW verification
powCheck	boolean	Boolean value which indicates whether the APoW verification is successful or not
ownId	nodeID	Identity of the node running the algorithm
msgCache	list	Cache storing the timestamp of the most recent messages received by ownID
nodeMap	list	List of nodeIDs which have issued messages recently (within 2 APoW timestamp windows)

Table 4.5.2: Local variables and metadata.

4.5.3.3 Built-in Functions

Pseudocodes introduced in the next section will use the built-in functions described in Table 4.5.3.

Function	Description
Floor(x)	Give the greatest integer less than or equal to x
Sort(x, y)	Sort list x by metric y
Append(x, y)	Add a new element y to list x
Remove(x)	Remove the oldest element from the ordered data structure x
Head(x)	Get (without removing) the oldest element from the ordered data structure x
CurrentTime()	Current time computed with the local clock

Table 4.5.3: Built-in functions.

4.5.3.4 Pseudocode

TargetPoW(timestamp, nodeID)

This function accesses the ledger to check the history of messages for nodeId.

FUNCTION targetPoW = TargetPoW(timestamp, nodeID)
    # cache update (this is done as an optimization)
    WHILE CurrentTime() - Head(msgCache).timestamp >  2 * APOW_WINDOW
        Remove(msgCache)
    Append(msgCache, <nodeID, timestamp>)
    Sort(msgCache, `timestamp`)
    countMsg = 0
    FOR msg IN msgCache[nodeID]
        IF msg > timestamp - APOW_WINDOW AND msg < timestamp
            countMsg++
    RETURN BASE_POW + Floor(APOW_RATE * countMsg)

APoWGeneration()

This function sets the difficulty at which the message creator should compute the PoW when generating a new message.

### upon creation of a new message

FUNCTION targetPoW = APoWGeneration()
    RETURN TargetPoW(CurrentTime(), ownID)

APoWVerification(msg)

This function is triggered in the parser by new messages, see Section 2.4 - Data Flow. It returns TRUE if the PoW attached to the message is sufficient, or FALSE otherwise.

#### upon arrival of a message msg

FUNCTION powCheck = APoWVerification(msg)
    targetPoW = TargetPoW(msg.timestamp, msg.nodeID)
    IF msg.pow >= targetPoW
        IF nodeMap[msg.nodeID] == NULL
            Append(nodeMap, msg.nodeID)
        Append(msgCache, msg.timestamp)
        RETURN TRUE
    ELSE
        RETURN FALSE

4.5.3.5 Implementation

The most critical part of the algorithm concerns counting the number of messages recently issued by a node. Since querying the database may be expensive, we propose to cache the most recent messages. To this end, we use two data structures (see Image 4.5.4):

• nodeMap. Each entry in the hashmap corresponds to a different nodeId and points to the doubly linked list of recent messages of the same node.
• msgCache. A queue which removes old messages and adds new ones according to a FIFO policy.

Image 4.5.4: Proposed data structures for the implementation of the rate control mechanism.

Both data structures point to the same locations of memory which store the timestamp of the message. These locations of memory also store the pointers to the other elements of nodeMap and msgCache.

The size of the cache $C$ (in number of timestamps) must be larger of the product between the maximum network throughput and the time window $w$. Assume that max throughput is 1000 TPS and the time window is 50 s, cache size must be larger than 50,000. Given $N$ the number of nodes issuing recent messages, our caching scheme provides the following performance:

• cache update: $\mathcal{O}(1)$;
• msg counter: $\mathcal{O}(C/N)$;
• cache size: $<10$ MB.

Assume that a node receives a message with PoW difficulty equal to targetPoW. However, the node cannot (immediately) know whether older messages have been issued before the timestamp of such message, which would make its PoW not sufficient. In this case, in order not to slow down the network, the node will forward anyway the message for scheduling.

An attacker may exploit the above in order to issue progressively older messages which would be accepted with easier PoW difficulty. Since the timestamp validation window is pretty large, this attack may theoretically be effective.

In case a node receives a new message with a timestamp that would make other messages from the same node would not have the correct PoW difficulty, the node will be blacklisted. However, no transactions which are already scheduled would be dropped.