Optimize memory allocation in MerkleProof

[frangio]

openzeppelin-contracts/contracts/utils/cryptography/MerkleProof.sol

Lines 42 to 48 in 7d17acf

	if (computedHash <= proofElement) {
	// Hash(current computed hash + current element of the proof)
	computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
	} else {
	// Hash(current element of the proof + current computed hash)
	computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
	}

abi.encodePacked allocates a new memory location on every iteration. This is incredibly wasteful. For this code in particular we don't even need to allocate new memory, since we're hashing exactly two words, we can use the scratch space in memory.

[Amxx]

Since both values are bytes32, I expect the resulting hash would be the same, right ? (otherwise it would be a breaking change)

I that is the case, and if the resulting code is more memory efficient, then we should merge that.

[Amxx]

I tried using both abi.encode and abi.encodePacked. With optimizations, running and deploying codes are identical (I believe the produced bytecode is the same).

Would you like to use assembly?

[frangio]

Yeah I don't think we have an alternative to using assembly, but we should localize it to a helper function that hashes 2 bytes32 words using the scratch space in memory.

[hack3r-0m]

@frangio would something like this work? i can open PR with comparision of performace

function efficientHash(bytes32 a, bytes32 b) internal pure returns (bytes32) {

    assembly {
        mstore(0x00, keccak256(a, b))
        return(0, 0x20)
    }
}

[frangio]

@hack3r-0m No, that function is not correct for a couple of reasons. return in an assembly block means something completely different than Solidity return... It will essentially abort execution at the smart contract level, which is not the same as returning from the current function.

Furthermore keccak256 takes as parameters a memory location and a length so a, b are not appropriate parameters.

[hack3r-0m]

thanks @frangio for helping

function efficientHash(bytes32 a, bytes32 b) public pure returns (bytes32 value) {

    assembly {
        mstore(0x00, a)
        mstore(0x20, b)

        value := keccak256(0x00, 0x40)
    }
}

I tried the above functions with a few random inputs and it seems to work. what would be the best way to return value from a function without aborting execution? I checked yul docs but there does not seem to be way other than pushing on top of stack

[frangio]

@hack3r-0m's proposal is correct. The 64 bytes starting at position 0 are "scratch space for hashing methods". The zero slot is at 0x60.

Please open a PR!