Merkle Math: find log and power with merkle tree

• DeFi protocols often have math operations involving logarithm and exponent. Prominent examples are Uniswap and Balancer. They handle millions of dollars' TVL and trading volume.
• 3rd party libraries like ABDK were developed because Solidity lacks native log and exponent function.
• Existing libraries use a combination of iteration, bit shifting and 'magic numbers'. However they're complex gas intensive. Here's Uniswap's log function 🤯

    function getTickAtSqrtRatio(uint160 sqrtPriceX96) internal pure returns (int24 tick) {
        // second inequality must be < because the price can never reach the price at the max tick
        require(sqrtPriceX96 >= MIN_SQRT_RATIO && sqrtPriceX96 < MAX_SQRT_RATIO, 'R');
        uint256 ratio = uint256(sqrtPriceX96) << 32;

        uint256 r = ratio;
        uint256 msb = 0;

        assembly {
            let f := shl(7, gt(r, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF))
            msb := or(msb, f)
            r := shr(f, r)
        }
        assembly {
            let f := shl(6, gt(r, 0xFFFFFFFFFFFFFFFF))
            msb := or(msb, f)
            r := shr(f, r)
        }
        assembly {
            let f := shl(5, gt(r, 0xFFFFFFFF))
            msb := or(msb, f)
            r := shr(f, r)
        }
        assembly {
            let f := shl(4, gt(r, 0xFFFF))
            msb := or(msb, f)
            r := shr(f, r)
        }
// lot more code

• Enter Napier's bones or log tables. Popular in elementary school math, you lookup values in the table instead of calculating.
• Napier's bones meets merkle tree. I built a merkle tree of the log10 table and stored its root on chain.
• Now we can look up log off-chain and pass it to the smart contract with a proof. Merkle tree ensures that the log is cryptographically valid.

The result is around 50% improvement in gas over ABDK, a significant improvement.

1. There's a trade-off between gas and percision. Merkle math gives results accurate upto 4 decimal places, ABDK gives more.
2. Log values must be found client side, before calling the contract. The value provided corresponds to some state variables in the contract. If these state variables change before our transaction is mined, the provided log will become invalid and the transaction revert. For example Uniswap uses logarithm for tick calculations. A frontrunning trade will produce a tick shift, invalidating our computed log.