Summary

The IOTA protocol uses proof-of-work as a means to rate-limit the network. Currently, the Curl-P-81 trinary hash function is used and is required to provide a hash with the matching number of trailing zero trits to issue a transaction to the Tangle. With Chrysalis, it will be possible to issue binary messages of arbitrary size. This RFC presents a proposal to adapt the existing PoW mechanism to these new requirements. It aims to be less disruptive to the current PoW mechanism as possible.

Motivation

In the current IOTA Protocol, each transaction has a fixed size of 8019 trits and is hashed using Curl-P-81 to compute its 243-trit transaction hash, where the PoW's difficulty equals the number of trailing zero trits in that hash.
Unfortunately, the performance of Curl-P-81 is slow, achieving only about 2 MB/s on a single core. This would make the PoW validation a bottleneck, especially for high usage scenarios with larger messages. Thus, this RFC proposes a two-stage approach to speed up the validation process: First, the BLAKE2b-256 hash function is used to create a short, fixed length digest of the message. Then, this digest, together with the nonce, is hashed using Curl-P-81. Since the digest only needs to be computed once while iterating over different nonce values, this preserves Curl as the PoW-relevant hash. However, the validation is much faster, as BLAKE2b-256 has a performance of about 1 GB/s and Curl then only needs to be executed for one single 243-trit block of input. Since the input of the final Curl computation is always fixed, parallel Curl variants can be used in this stage to further speed up the validation if necessary.
Furthermore, it is important to note that the time required to do the PoW depends on the PoW difficulty and not on the message length. As such, to treat messages with different lengths differently, we need to weight the PoW difficulty by the message length.

It will be easy to adapt existing hardware and software implementations of the current PoW mechanism to work with the proposed design. Only the input and the position of the nonce in the buffer needs to be adapted. This enables existing Curl projects to continue persisting and also the entire PoW landscape should stay almost the same.

Detailed design

The PoW score is defined as the average number of iterations required to find the number of trailing zero trits in the hash divided by the message size.

The PoW validation is performed in the following way:

Compute the BLAKE2b-256 hash of the serialized message (as described in TIP-6) excluding the 8-byte Nonce field and convert the hash into its 192-trit b1t6 encoding. (See TIP-5 for a description of the encoding.)
Take the 8-byte Nonce in little-endian representation, convert it into its 48-trit b1t6 encoding and append it to the hash trits.
Add a padding of three zero trits to create a 243-trit string.
Compute the Curl-P-81 hash.
Count the number of trailing zero trits in the hash.
Then, the PoW score equals 3^#zeros / size(message).

This can also be summarized with the following pseudocode:

pow_digest ← BLAKE2b-256(serialized message excluding nonce field)
pow_hash ← Curl-P-81(b1t6(pow_digest) || b1t6(nonce) || [0, 0, 0])
pow ← 3**trailing_zeros(pow_hash) / size

where size is the number of bytes of the full serialized message.

Example

Message including nonce (21-byte): 48656c6c6f2c20576f726c64215ee6aaaaaaaaaaaa
PoW digest (32-byte): 511bc81dde11180838c562c82bb35f3223f46061ebde4a955c27b3f489cf1e03
Nonce (8-byte): 5ee6aaaaaaaaaaaa (12297829382473049694)
Curl input (81-tryte): 9C9AYYBATZQAXAH9BBVYQDYYPBDXNDWBHAO9ODPDFZTZTCAWKCLADXO9PWEYCAC9MCAZVXVXVXVXVXVX9
PoW hash (81-tryte): DJCAGKILZPLXNXWFTNXFLCHRFVUHHMTPFIOFKQXMGIKITSEVWECMQOKCFXDIIHK9YVHGQICAIVEVDJ999
Trailing zeros: 9
PoW score: 3⁹ / 21 = 937.2857142857143

Drawbacks

Curl is a ternary hash function that is applied on binary data. This makes it necessary to introduce an additional encoding step. However, the proposed b1t6 encoding is reasonably performant. Additionally, hash functions usually contain an encoding step to write the input into their internal state. In that sense, the b1t6 encoding is not much different.
One additional trailing zero in the PoW hash effectively allows the message size to be tripled. This could potentially incentivize users to add otherwise unnecessary data, when the PoW difficulty stays the same. Using a binary hash function instead of Curl would only slightly improve this situation as the allowed message length remains exponential in the difficulty parameter.

Rationale and alternatives

The premise of this proposal is that the PoW should remain Curl-based to cause the least amount of disruption to the protocol and its established projects. Therefore, other hash functions or PoW algorithms have not been considered. However, modifications of the described calculation are possible:

There are several potential encodings for the nonce: E.g. converting its value directly to balanced ternary (the most compact encoding) or using the b1t8 encoding. The chosen b1t6 encoding achieves a nice balance between compactness and performance. Since it is possible to fit the PoW digest and the b1t6 encoded nonce into one Curl block, the simplicity of having only one encoding (for PoW digest and nonce) was preferred over minimal performance improvements other encodings could bring.
Curl can be computed directly on the b1t6 encoded message (after an appropriate padding has been added). However, performance analysis of existing node implementation suggests that the Curl computations during the PoW could become critical, especially since parallel Curl implementations would be much more difficult to deploy because of the dynamic message lengths.
BLAKE2b-256 could be replaced with BLAKE2b-512 or any other binary cryptographic hash function. However, a 256-bit digest fits very nicely into exactly one Curl block and since BLAKE2b-256 is also used for the message ID, it is reasonable to also use it for the PoW digest. This reduces the number of required hashing implementations and even allows reusage of intermediate values between the PoW digest and the message ID computation.

The PoW score formula 3^#zeros / size(message) could be replaced with an alternative function to better match the network usage, e.g. in order to penalize longer message more than linearly.

Reference implementation

Example Go implementation in wollac/iota-crypto-demo:

b1t6 encoding: pkg/encoding/b1t6
PoW computation: pkg/pow