The Mimblewimble (MW) protocol requires each transaction to specify an explicit fee amount. It is usually stored in the transaction kernel and signed with the kernel public key to prevent tampering. However, the ~100-byte kernel is the only part of a MW transaction that needs to be stored in the blockchain indefinitely. If the transaction fees are stored with full 64-bit precision, the fees may represent up to 8 percent of the whole blockchain download size as the transaction history grows.
This article describes a method to encode transaction priority and fee value in just 2 bytes (16 bits). The main idea is that instead of encoding the fee with the fixed precision of 1 atomic currency unit, we can encode the fee with a relative precision of about 0.1%-0.3%, which should be acceptable to most users.
We will use the 16 bits as follows:
+-------------------+-------------------+-----------------------+
| Priority (2 bits) | Exponent (4 bits) | Significand (10 bits) |
+-------------------+-------------------+-----------------------+
Transaction priority is usually given by the fee rate, which is the fee amount divided by the transaction size. In Bitcoin, the transaction size is known to the sender, so the priority is set implicitly by the specified fee amount.
However, MW allows for non-interactive aggregation of transactions, which means that when Bob is sending a transaction, he cannot know the final size of his transaction when it arrives to a miner. Even if he sets an above-average fee amount, Mallory can join her low-fee transaction with Bob's, resulting in a tranasction that has a total fee rate lower than Bob intended.
It is therefore necessary to specify an explicit priority to prevent fee hijacking. Our protocol supports 4 different priority levels. This should be sufficient in cases when the transaction fee only serves as a spam deterrent and is not meant to replace the block subsidy.
| encoding | priority | multiplier |
|---|---|---|
00 |
Low | 1 |
01 |
Medium | 4 |
10 |
High | 32 |
11 |
Instant | 1024 |
We can then define the following non-consensus rule:
A transaction may only be relayed if its total fee rate is at least
Ltimes the minimum transaction fee rate, whereLis the highest priority multiplier among the transaction's kernels.
Now if Bob wants to expedite his transaction, he can set the High priority level and pay at least 32 times the minimum fee. If Mallory wants to aggregate her transaction with Bob's, she must also pay at least 32 times the minimum fee or the aggregated transaction won't be relayed by the network.
Note: Monero uses similar values of transaction priority multipliers [1]. The exact values are not critical as they can be changed by a simple client update without forking.
The fee amount is calculated from the unsigned exponent e and unsigned significand s as:
fee = s * 2^(a*e+b) + 1024 * Σ(j < e) 2^(a*j+b)
where a, b are constants that can be selected depending on the required minimum and maximum representable fee value and ^ is the exponentiation operator. The second term in the formula sums the ranges of all the exponents lower than e, ensuring that different exponents represent disjunct intervals.
For example, with a=2 and b=6, the values (e=1,s=994) encode the fee amount of 994*2^8 + 1024*2^6 = 320000 atomic units.
Grin has 109 atomic units per coin. Good values for encoding the fee are a=2 and b=0. The range of representable non-zero values then ranges from 1 nanogrin (nG) up to ~1465 Grin, which is more than 20 times the block subsidy and should be enough to submit any reasonably sized transaction with the Instant priority level.
| exponent | approx. range | approx. precision |
|---|---|---|
| 0 | 0-1 μG | 1 nG |
| 1 | 1-5 μG | 4 nG |
| 2 | 5-21 μG | 16 nG |
| 3 | 21-87 μG | 64 nG |
| 4 | 87-349 μG | 256 nG |
| 5 | 0.35-1.4 mG | 1 μG |
| 6 | 1.4-5.6 mG | 4 μG |
| 7 | 5.6-22 mG | 16 μG |
| 8 | 22-89 mG | 65 μG |
| 9 | 89-358 mG | 262 μG |
| 10 | 0.36-1.4 G | 1 mG |
| 11 | 1.4-5.7 G | 4 mG |
| 12 | 5.7-22.9 G | 17 mG |
| 13 | 22.9-91.6 G | 67 mG |
| 14 | 91.6-366 G | 268 mG |
| 15 | 367-1465 G | 1 G |
Bob wants to submit a transaction that requires a minimum fee of 24 mG with the High priority level. The kernel fee should be at least 0.768 G. The closest representable value is (e=10,s=392), which results in a fee value of 0.768693248 G (that's only 0.09% higher than the intended value). The priority+fee will be encoded in binary as 1010100110001000.
I thought about this, but it brings a host of issues:
Thanks, It was a clickable link, but I added an explicit reference at the end.
It seems that the encoding of "nBits" is not unique, for example
0x18001b30and0x171b3000both encode the same value.The 40-bit fixed-precision fee has about the same range as the 14-bit variable-precision fee. Monero gets by just fine with 4 priority levels. Having the user choose their priority from 16 levels may be bad for UX (search for "Hick's law").
Is there a practical benefit to setting the fee to 0.100000001 as opposed to 0.1? I don't see the need to keep the fixed precision across the whole range of possible fee values. In fact, high-precision fees were identified as a possible privacy leak in Monero (but this is less of an issue for Grin).