Gas usage for same contract is constantly growing

Question

Here is the smart contract. The gas usage for this contract is constantly growing. All state variables are initialized at deployment and never changed. Signers array is about 2-3 in size no more. And this contract started from using 150,000 gas to right now 600,000.

Is there any visible issue with code?

Here is few transaction ids:

https://etherscan.io/tx/0x26f13d3b3d0809ffc24f22b5f33966aa0c144e433cbe239649df5f00f3d29740 (used gas: 117,013)

https://etherscan.io/tx/0xfcf395bd21ce4e69857184ee3d7b2164f3d0d8536b666dad46d5be8455aed73c (used gas: 681,795)

Code:

pragma solidity ^0.4.24;

contract MultiSigContract {
    mapping (address => bool) public IsSigner;
    address public Executer;
    address[] public Signers;

    function MultiSigContract(address[] _signers, address _executer) public {
        require(_executer != 0x0);
        Signers = _signers;
        Executer = _executer;
        for (uint i = 0; i < Signers.length; i++) {
            IsSigner[Signers[i]] = true;
        }        
    }

    function execute(address destination, uint amount, uint8[] sigV, bytes32[] sigR, bytes32[] sigS) public {
        require(sigR.length == sigS.length && sigR.length == sigV.length);
        require(sigR.length == Signers.length);
        require(msg.sender == Executer);
        require(address(this).balance >= amount);

        address[] recoveredAddresses;
        bytes32 txHash = keccak256("\x19Ethereum Signed Message:\n72", this, destination, amount);

        for(uint8 i = 0; i < Signers.length; i++) {
            address recovered = ecrecover(txHash, sigV[i], sigR[i], sigS[i]);
            require(IsSigner[recovered] == true);
            recoveredAddresses.push(recovered);
        }

        for(uint8 j = 0; j < Signers.length; j++) {
            require(contains(Signers[j], recoveredAddresses));
        }

        destination.transfer(amount);
    }

    function contains(address _address, address[] _addressArray) private pure returns (bool) {
        for(uint8 i = 0; i < _addressArray.length; i++) {
            if (_addressArray[i] == _address) {
                return true;
            }
        }

        return false;
    }

    function () public payable {}
}

Answer 1

This is because recoveredAddresses isn't marked as memory, so by default, it's in storage. Every time you push to it, you're growing the length, even across transaction calls. That also means that the function contains has to iterate over a larger and larger array of addressArray every time it's executing, growing the gas cost over time. The solution is to make the recoveredAddresses a memory array by writing it as address[] recoveredAddresses;. This also means you have to do some rework around sizing an such since you can't have dynamically sized memory arrays. The size has to be known at compile time. It's pretty simple if you have a small upper-bound of the array size, otherwise it may get complicated.

You can see an example of this by looking at the "State Changes" tab and expanding the address of the contract. You're constantly appending the newly recovered addresses to that array.

Answer 2

Your use of for(i=0; i<n; i++_) implies O(n) complexity, meaning you can optimize the process but it will still increase in cost proportional to n. Optimization only affects slope steepness. The real problem is there is a slope at all.

Unbounded for loops are an anti-pattern because they are not scale-invariant.

Have a look at this: https://blog.b9lab.com/getting-loopy-with-solidity-1d51794622ad

And this: Increase all values of mapping or array without loop

TL;DR;

for(i=0; i<n ... == trouble. Be prepared to reconsider the process that takes great pains to avoid doing it.

Hope it helps.