Does Your Blockchain Need Multidimensional Transaction Fees?

Blockchains have block-size limits to ensure the entire cluster can keep up with the tip of the chain. These block-size limits are usually single-dimensional, but richer multidimensional constraints allow for greater throughput. The potential for performance improvements from multidimensional resource pricing has been discussed in the literature, but exactly how big those performance improvements are remains unclear. In order to identify the magnitude of additional throughput that multi-dimensional transaction fees can unlock, we introduce the concept of an $\alpha$-approximation. A constraint set $C_1$ is $\alpha$-approximated by $C_2$ if every block feasible under $C_1$ is also feasible under $C_2$ once all resource capacities are scaled by a factor of $\alpha$ (e.g., $\alpha =2$ corresponds to doubling all available resources). We show that the $\alpha$-approximation of the optimal single-dimensional gas measure corresponds to the value of a specific zero-sum game. However, the more general problem of finding the optimal $k$-dimensional approximation is NP-complete. Quantifying the additional throughput that multi-dimensional fees can provide allows blockchain designers to make informed decisions about whether the additional capacity unlocked by multidimensional constraints is worth the additional complexity they add to the protocol.