Gas Optimizations

[code423n4]

Apply updates from upstream Murky library

The upstream Murky library has added a few gas optimization changes you may want to implement yourself. Two are minor optimizations, one is more significant.

Caching _proof.length in MerkleBase#verifyProof:

    function verifyProof(
        bytes32 _root,
        bytes32[] memory _proof,
        bytes32 _valueToProve
    ) public pure returns (bool) {
        // proof length must be less than max array size
        bytes32 rollingHash = _valueToProve;
        unchecked {
            for (uint256 i = 0; i < _proof.length; ++i) {
                rollingHash = hashLeafPairs(rollingHash, _proof[i]);
            }
        }
        return _root == rollingHash;
    }

Suggestion (link to Murky):

    function verifyProof(
        bytes32 _root,
        bytes32[] memory _proof,
        bytes32 _valueToProve
    ) public pure returns (bool) {
        // proof length must be less than max array size
        bytes32 rollingHash = _valueToProve;
        uint256 length = _proof.length;
        unchecked {
            for (uint256 i = 0; i < length; ++i) {
                rollingHash = hashLeafPairs(rollingHash, _proof[i]);
            }
        }
        return _root == rollingHash;
    }

Using a bitwise and in place of the modulo operator in MerkleBase#getProof:

        while (_data.length > 1) {
            unchecked {
                if (_node % 2 == 1) {
                    result[pos] = _data[_node - 1];
                } else if (_node + 1 == _data.length) {
                    result[pos] = bytes32(0);
                    ++counter;
                } else {
                    result[pos] = _data[_node + 1];
                }
                ++pos;
                _node = _node / 2;
            }
            _data = hashLevel(_data);
        }

Suggestion (link to Murky):

        while (_data.length > 1) {
            unchecked {
                if (_node & 0x1 == 1) {
                    result[pos] = _data[_node - 1];
                } else if (_node + 1 == _data.length) {
                    result[pos] = bytes32(0);
                    ++counter;
                } else {
                    result[pos] = _data[_node + 1];
                }
                ++pos;
                _node = _node / 2;
            }
            _data = hashLevel(_data);
        }

Replacing log2ceil_naive with a more efficient log2ceilBitMagic function:

MerkleBase#getProof

        // The size of the proof is equal to the ceiling of log2(numLeaves)
        uint256 size = log2ceil_naive(_data.length);

Suggestion:

        // The size of the proof is equal to the ceiling of log2(numLeaves)
        uint256 size = log2ceilBitMagic(_data.length);

Link to change in upstream Murky.

Consider reviewing these recent changes to Murky and upgrading your forked implementation.