Compare Strings in Solidity

In most programming languates, it is fairly easy to compare equality of strings.

# in Ruby
puts "hello" == "world" #=> false
puts "web3" == "web3" #=> true

However, Solidity does not come with native functions to compare the strings.

Solution 1: StringUtils library

A library was developed by the Ethereum org, called StringUtils. Here is the exerpt from the original source code:

// original: https://github.com/ethereum/dapp-bin/blob/master/library/stringUtils.sol

library StringUtils {
    /// @dev Does a byte-by-byte lexicographical comparison of two strings.
    /// @return a negative number if `_a` is smaller, zero if they are equal
    /// and a positive numbe if `_b` is smaller.
    function compare(string _a, string _b) returns (int) {
        bytes memory a = bytes(_a);
        bytes memory b = bytes(_b);
        uint minLength = a.length;
        if (b.length < minLength) minLength = b.length;
        //@todo unroll the loop into increments of 32 and do full 32 byte comparisons
        for (uint i = 0; i < minLength; i ++)
            if (a[i] < b[i])
                return -1;
            else if (a[i] > b[i])
                return 1;
        if (a.length < b.length)
            return -1;
        else if (a.length > b.length)
            return 1;
        else
            return 0;
    }
    /// @dev Compares two strings and returns true iff they are equal.
    function equal(string _a, string _b) returns (bool) {
        return compare(_a, _b) == 0;
    }
}

As you can see, StringUtils.compare() checks the length of two strings and return early if the length of them differ. Only if the length is the same, it iterates both strings from first letters until the last, and return early if different letters get found in the middle.

By this implementation, you can optimise computational costs, meaning less gas fee.

The downside of this algorithm is that, in the worst case, the computational order is still O(n), where n is the length of the strings. The worst case is that when both strings are the same, and the computational cost increases as n grows, meaning it still takes cost to compare two long strings that are the same.

Solution 2: Compare Hashed Values

Another practical solution was invented from the community.

Solidity has some native cryptographic hash function, including sha256, ripemd160, ecrecover, and keccak256(). Among of all, keccak256() is used in this example.

Keccak, which is a superset of SHA-3, is based on an approach called sponge construction. You can read more about this novel model at this article by the Keccak team.

// SPDX-License-Identifier: UNLICENSED
pragma solidity >=0.7.0 <0.9.0;

contract Util {
    function compStr(string memory x, string memory y)
        public
        pure
        returns (bool)
    {
        if (bytes(x).length != bytes(y).length) {
            return false;
        } else {
            return (keccak256(abi.encodePacked(x)) ==
                keccak256(abi.encodePacked(y)));
        }
    }
}

Compared to the solution of StringUtils library, the cost does not increases as n grows because it is hashed values that are compared.

An idea of checking the length at first is introduced as well to avoid unnecessary hashing long strings with different values. This check is not necessary and just an optimization though.

Summary

Solidity requires a new way of programming paradigm due to its design, but still there are a lot of ideas that you can introduce from your learning of other programming languates in the past. Being gas effecient is at last to think about the best computational way of implementing your programs.