Use keccak to compare arrays #69
Comments
|
The idea for the library was to provide a different alternative to the hashing option. That is dependent on the hash implementation versus having computation done on each of the bytes directly. I don't think I'd ever mask a simple hash comparison behind a lib, too. In addition, have you tested and made sure it is more gas-efficient? |
That's interesting, what for and why? Is hashing insecure? Regarding gas usage, hashing costs 30 gas + 6 per 32-byte word, there's nothing to benchmark really, hashing is probably the cheapest thing you can do with an array of bytes in memory. |
Not really, but we're just giving optionality, I guess. I'm not afraid the keccak opcode is badly implemented in Geth. But that's just the gas usage of the opcode. What about changing the memory pointer, filling the memory in the scratch space, etc.? Because my code does everything in place, we don't even touch the 0x0 - 0x40 scratch space like the Solidity compiler does to hash stuff together. What if you want to hash something that is bigger than 32 bytes? You need to copy multiple times. I'd say that the bigger the array, the more efficient my function is compared to hashing stuff together. This being said, I never benchmarked it, so you may be right. I'd love to see some data to believe the statement, though. |
|
Keccak works in-place, on an arbitrary memory range, check https://www.evm.codes. The scratch space is used mostly for calculating the storage slot indexes, because it involves repeated hashing of pairs of 32-byte words taken from the stack. It's your project, so I can't tell you what to do, you'll do whatever you choose. I don't even use your code as a dependency, so I won't see the benefits of any optimization. All I'm saying is that you should check out hashing because it's a fairly popular strategy for reducing gas usage. Plus you'll drop a lot of complex Yul code. |
|
I just benchmarked it, and you're totally right. Leaving the data here for posterity. This is for a 4-byte-long array comparison with Keccak: This is for the same comparison with my function: Trying longer lengths shows that my function actually scales just a smidge slightly worse than the Keccak comparison. With this being said, if the lengths do not match, my function is O(1) and performs better than the Keccak counterpart in any case. To be honest, I've done this such a long time ago that I don't even know what I was thinking now, about memory manipulation of the Keccak opcode. It probably had something to do with the storage slot calculations, like you mentioned. 🤷♂️ Although this is all true, I still don't think I should change this function. But I sincerely thank you for bringing this up! 🙏 At least now we have some comparisons and options. |
From the very first proposed version in this issue hashing is done only if the lengths are different. Omitting this path doesn't yield meaningful results. I couldn't believe it so I wrote a benchmark too, here are the results. Hashing has a predictable cost which is a useful property on blockchains, and is usually faster, often by a lot. The only edge case are arrays of over 256 bytes where the very first byte is different, for which the loop-based implementation has the O(1) cost, so at some point it gets better than hashing. Sourcepragma solidity ^0.8.24;
import {console, Test} from "forge-std/Test.sol";
contract EqualTest is Test {
function testBenchEqual() public view {
for(uint i = 1; i < 4096; i *= 2) {
_benchForLength(i);
}
}
function _benchForLength(uint256 length) internal view {
bytes memory data = new bytes(length);
for(uint256 i = 0; i < length; i++) {
data[i] = bytes1(uint8(block.prevrandao + i));
}
console.log("Same for length", length);
this.benchEqual(data, data);
bytes memory differentFirst = bytes.concat(data);
differentFirst[0] ^= 0xff;
console.log("Different first for length", length);
this.benchEqual(data, differentFirst);
bytes memory differentLast = bytes.concat(data);
differentLast[differentLast.length -1] ^= 0xff;
console.log("Different last for length", length);
this.benchEqual(data, differentLast);
bytes memory differentLength = bytes.concat(data, bytes1(0));
console.log("Different length for length", length);
this.benchEqual(data, differentLength);
console.log("-----------------------");
console.log("");
}
function benchEqual(bytes memory preBytes, bytes memory postBytes) external view {
uint256 gasEqual = gasleft();
bool equalResult = BytesLib.equal(preBytes, postBytes);
gasEqual -= gasleft();
uint256 gasEqualNonAligned = gasleft();
bool equalNonAlignedResult = BytesLib.equal_nonAligned(preBytes, postBytes);
gasEqualNonAligned -= gasleft();
uint256 gasEqualHash = gasleft();
bool equalHashResult = BytesLib.equalHash(preBytes, postBytes);
gasEqualHash -= gasleft();
if(equalResult != equalNonAlignedResult) console.log("DIFFERENT ALIGNED AND NON ALIGNED!");
assertEq(equalResult, equalHashResult, "Invalid hash result");
console.log("Gas equal: ", gasEqual);
console.log("Gas equal non aligned:", gasEqualNonAligned);
console.log("Gas equal hash :", gasEqualHash);
console.log("");
}
}
library BytesLib {
function equalHash(bytes memory _preBytes, bytes memory _postBytes) internal pure returns (bool) {
return _preBytes.length == _postBytes.length && keccak256(_preBytes) == keccak256(_postBytes);
}
function equal(bytes memory _preBytes, bytes memory _postBytes) internal pure returns (bool) {
bool success = true;
assembly {
let length := mload(_preBytes)
// if lengths don't match the arrays are not equal
switch eq(length, mload(_postBytes))
case 1 {
// cb is a circuit breaker in the for loop since there's
// no said feature for inline assembly loops
// cb = 1 - don't breaker
// cb = 0 - break
let cb := 1
let mc := add(_preBytes, 0x20)
let end := add(mc, length)
for {
let cc := add(_postBytes, 0x20)
// the next line is the loop condition:
// while(uint256(mc < end) + cb == 2)
} eq(add(lt(mc, end), cb), 2) {
mc := add(mc, 0x20)
cc := add(cc, 0x20)
} {
// if any of these checks fails then arrays are not equal
if iszero(eq(mload(mc), mload(cc))) {
// unsuccess:
success := 0
cb := 0
}
}
}
default {
// unsuccess:
success := 0
}
}
return success;
}
function equal_nonAligned(bytes memory _preBytes, bytes memory _postBytes) internal pure returns (bool) {
bool success = true;
assembly {
let length := mload(_preBytes)
// if lengths don't match the arrays are not equal
switch eq(length, mload(_postBytes))
case 1 {
// cb is a circuit breaker in the for loop since there's
// no said feature for inline assembly loops
// cb = 1 - don't breaker
// cb = 0 - break
let cb := 1
let endMinusWord := add(_preBytes, length)
let mc := add(_preBytes, 0x20)
let cc := add(_postBytes, 0x20)
for {
// the next line is the loop condition:
// while(uint256(mc < endWord) + cb == 2)
} eq(add(lt(mc, endMinusWord), cb), 2) {
mc := add(mc, 0x20)
cc := add(cc, 0x20)
} {
// if any of these checks fails then arrays are not equal
if iszero(eq(mload(mc), mload(cc))) {
// unsuccess:
success := 0
cb := 0
}
}
// Only if still successful
// For <1 word tail bytes
if gt(success, 0) {
// Get the remainder of length/32
// length % 32 = AND(length, 32 - 1)
let numTailBytes := and(length, 0x1f)
let mcRem := mload(mc)
let ccRem := mload(cc)
for {
let i := 0
// the next line is the loop condition:
// while(uint256(i < numTailBytes) + cb == 2)
} eq(add(lt(i, numTailBytes), cb), 2) {
i := add(i, 1)
} {
if iszero(eq(byte(i, mcRem), byte(i, ccRem))) {
// unsuccess:
success := 0
cb := 0
}
}
}
}
default {
// unsuccess:
success := 0
}
}
return success;
}
}Results for via-ir=false and 200 optimizer runsResults for via-ir=true and 200 optimizer runsThe runs marked as |
|
I mean, the normal function works as long as you use vanilla Solidity or don't use Yul to mess with the memory pointer manually. That was always its intended use case. In fact its first version was reviewed together with the compiler team. I could consider changing the non-aligned function to become the main one, though, given we don't care about the gas savings. Was I right about the above or should I be worried about a bug in the functions? |
|
Also, please note this library is 7 years old and, again, I am terribly afraid of breaking shit downstream at this point. 🙏 |
It's the code I shared above, just run it with |
|
Sorry! 😅🙈 Completely ignored the “Source” tab. I’ll take a look! 🙏
|
|
I found the bug. In IMO this function is extremely overcomplicated, even forgetting about hashing for a moment. Instead of having a special routine for comparing the partial last word, you could just replace the initial |
|
My current span of attention for this being so thin was the reason why I merged this PR into a different function. I am actually happy I didn't merge or replace the normal equal function for this one like the contributor asked me to. I need some proper time to review the bug and your proposal. But this is great, and I can't thank you enough for taking such a close look! 🙏 |
BytesLib.equalandBytesLib.equal_nonAlignedcan be replaced with a much simpler, more gas efficient and purely Solidity (YUL probably won't bring any benefits here):return _preBytes.length == _postBytes.length && keccak256(_preBytes) == keccak256(_postBytes);.The text was updated successfully, but these errors were encountered: