Summoning the Socket Optimizoors (Yul optimizations in confined snippets / libraries)

[smitrajput]

Is your feature request related to a problem? Please describe.
At the lure of being readable, pure solidity costs a lot of gas sometimes. With a perpetually dire need for cheap transaction costs, coupled with some awesome resources to leverage Yul for gas-optimizations these days (to make Yul readable/understandable), it's about time we standardise using memory-safe Yul in our solidity chores (especially in libraries), joining our chadfrens at Seaport and Solady on this new sensibly-brave frontier.

Describe the solution you'd like
From a quick look, it makes sense to use Yul at the following places in the codebase:

1. HashChainDecapacitor.verifyMessageInclusion()
2. Hasher.packMessage()
3. Using Solady's SafeTransferLib and ECDSA, in place of SafeTransferLib and SignatureVerifierLib
   And in all the other libraries where it makes enough sense.

A simple demo for (1) above:

    function verifyMessageInclusion(
        bytes32 root_,
        bytes32 packedMessage_,
        bytes calldata proof_
    ) external pure override returns (bool) {
        bytes32[] memory chain = abi.decode(proof_, (bytes32[]));
        uint256 len = chain.length;
        bytes32 generatedRoot;
        bool isIncluded;
        for (uint256 i = 0; i < len; i++) {
            generatedRoot = keccak256(abi.encode(generatedRoot, chain[i]));
            if (chain[i] == packedMessage_) isIncluded = true;
        }

        return root_ == generatedRoot && isIncluded;
    }

would be this snippet, referred from Solady's MerkleProofLib:

    function verifyMessageInclusion(
        bytes32 root_,
        bytes32 packedMessage_,
        bytes calldata proof_
    ) external pure override returns (bool) {
        bytes32[] memory chain = abi.decode(proof_, (bytes32[]));
        bytes32 generatedRoot;
        bool isIncluded;
        /// @solidity memory-safe-assembly
        assembly {
            if mload(chain) {
                // Initialize `offset` to the offset of `chain` elements in memory.
                let offset := add(chain, 0x20)
                // Left shift by 5 is equivalent to multiplying by 0x20.
                // finding the position of the end of the array by adding chain's length's size to offset.
                let end := add(offset, shl(5, mload(chain)))
                // Iterate over chain elements to compute root hash.
                for {} 1 {} {
                    // Store elements to hash contiguously in scratch space.
                    // Scratch space is 64 bytes (0x00 - 0x3f) and both elements are 32 bytes.
                    mstore(0x00, generatedRoot)
                    mstore(0x20, mload(offset))
                    // generatedRoot = keccak256(abi.encode(generatedRoot, chain[i]));
                    generatedRoot := keccak256(0x00, 0x40)
                    // if (chain[i] == packedMessage_) isIncluded = true;
                    if eq(mload(offset), packedMessage_) {
                        isIncluded := true
                    }
                    // i++
                    offset := add(offset, 0x20)
                    // i < len
                    if iszero(lt(offset, end)) { break }
                }
            }
        }
        return root_ == generatedRoot && isIncluded;
    }

And unsurprisingly, it saves 2340 gas for 3 calls to verifyMessageInclusion() in testAddMessageMultiple() i.e. 780 gas per call

Before:

After:

Checkout the difference and test for yourself in the optimize/decapacitor branch of my fork here.

Describe alternatives you've considered
Alternatively, you could try to cut costs using solidity itself, but those savings won't be as impactful.