4.5 Rate Control Through Adaptive Proof of Work
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:
220.127.116.11 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.
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 . It sets the initial difficulty of PoW.
- Adaptation rate . It provides the rate at which difficulty will be adjusted. Equivalently, indicates how many messages can be sent per time window without increasing the PoW difficulty.
- APoW time window . It describes the width of the time interval considered by the algorithm, i.e., its granularity.
18.104.22.168 Message Generation
Let be the output of the function
CurrentTime(). If node
m wants to issue a new message, it shall perform a PoW with difficulty such that
where represents the number of messages issued by node m with (message) timestamp in the interval . Note that when , the algorithm becomes equivalent to the legacy IOTA implementation.
22.214.171.124 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 issued by node
m. To decide whether this message should be discarded, node
n counts how many messages issued by
m it has received in the last time units. In accordance with the formula above, the node validates the PoW only if the following condition is satisfied:
Discussions on the correctness of this procedure can be found on a related article.
126.96.36.199 Protocol Parameters
In line with the previous section, all nodes know the constants shown by Table 4.5.1.
|integer||The base difficulty|
|float||The adaptation rate (proposed values [0.1 - 1])|
|integer||The APoW time window (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).
188.8.131.52 Local Variables and Metadata
Local variables and metadata are described in Table 4.5.2.
|integer||A value declared by the node representing time at which the message has been issued|
|nodeID||Identity of the node issuing the message defined as the |
|integer||Minimum difficulty needed to pass the APoW verification|
|boolean||Boolean value which indicates whether the APoW verification is successful or not|
|nodeID||Identity of the node running the algorithm|
|list||Cache storing the timestamp of the most recent messages received by |
|list||List of nodeIDs which have issued messages recently (within 2 APoW timestamp windows)|
Table 4.5.2: Local variables and metadata.
184.108.40.206 Built-in Functions
Pseudocodes introduced in the next section will use the built-in functions described in Table 4.5.3.
|Give the greatest integer less than or equal to |
|Sort list |
|Add a new element |
|Remove the oldest element from the ordered data structure |
|Get (without removing) the oldest element from the ordered data structure |
|Current time computed with the local clock|
Table 4.5.3: Built-in functions.
This function accesses the ledger to check the history of messages for
FUNCTION targetPoW = TargetPoW(timestamp, nodeID)
# cache update (this is done as an optimization)
WHILE CurrentTime() - Head(msgCache).timestamp > 2 * APOW_WINDOW
Append(msgCache, <nodeID, timestamp>)
countMsg = 0
FOR msg IN msgCache[nodeID]
IF msg > timestamp - APOW_WINDOW AND msg < timestamp
RETURN BASE_POW + Floor(APOW_RATE * countMsg)
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)
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
#### 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
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 (in number of timestamps) must be larger of the product between the maximum network throughput and the time window . Assume that max throughput is 1000 TPS and the time window is 50 s, cache size must be larger than 50,000. Given the number of nodes issuing recent messages, our caching scheme provides the following performance:
- cache update: ;
- msg counter: ;
- cache size: 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.