如何更好的节省Gas费用呢?本文提到了5种方法
本题目是Paradigm的CTF系列中挺有意思的一道题,它模仿了leetcode中125. 验证回文串这道题目,通过给定输入,让你判断输入的字符串是不是回文子串,实现用solidity来刷Leetcode,伟大的Samczsun!
目前作者正在找智能合约相关的工作,希望能跟行业内人士多聊聊 🐟 。如果你觉得我写的还不错,可以加我的微信:woodward1993
我们先简单看下什么是回文:
回文就是从左到右读和从右到左读都是一样的字符串成文回文。最经典的解决回文子串的方法是双指针法,如下图所示:
只要left指针和right指针所指的内容不一致,则返回false。直到两个指针相遇,即left < right(这里可以不用取等号,因为奇数时,留下唯一一个肯定是回文)
分别定义左指针left,指向字符串左边第一个元素;右指针right指向字符串右边第一个元素
这时指针left指向的字符”c“与指针right指向的字符”c“是一样的。left需要向右移动一位。同理,指针right也应向左移动一位。
指针left指向的字符”t“与right指向的字符”n“是不同的,也就是说字符串"@CaTnAc#"不是回文串。至此,即使有剩余的字符也就不需要考虑了
我们再来看看他的测试用例有哪些:
testcases = {
"": True,
"a": True,
"ab": False,
"aba": True,
"paradigm": False,
"tattarrattat": True,
}
其实该题的难点在于输入参数的判断。:muscle: 真正的判断是否为回文的逻辑是很清晰的。
当通过函数test(string)
来输入参数如:"aba"时,其aba会被编码为:
0xf9fbd554 => 函数选择器
0000000000000000000000000000000000000000000000000000000000000020 => 动态类型string的编码head
0000000000000000000000000000000000000000000000000000000000000003 => tail[0] 字节长度
6162610000000000000000000000000000000000000000000000000000000000 => tail[1] "aba"的字节数组
因为string是一个动态类型,其在编码时,先编码head,在编码tail。head中的内容是tail部分距离该head所占位点的偏移量,是一个相对值。
$$ \mathtt{head}(X_i) = \mathtt{enc}(||head(X1) ... head(X{k-1}) tail(X1) ... tail(X{i-1})||) $$
$$ tail(X_i) = enc(X_i) $$
对于字符串string,其在编码tail时,
故在结合上head部分,对应的偏移量是0x20, 故test(string)输入参数为aba时的编码如上。
当通过staticcall调用时,其栈情况和内存情况如下:
$\mathtt{gas}=2d5cc5$, $\mathtt{to}=5c9eb5d6a6c2c1b3efc52255c0b356f116f6f66d$, $\mathtt{In offset}=C0$, $\mathtt{Insize}=04$,$\mathtt{Outoffset}=C0$,$\mathtt{OutSize}=20$
那么我理解的calldata应该为:0x3ca7255b
而0x3ca7255b正好是keccak("fwd()")的函数选择器, 故实际上这里的staticcall函数调用的是Challenge合约的fwd()方法。应该返回的是fwd合约的地址:6f16a4f343b671b610476c5dcb740e4c5afcbac1,
calldata=> 我们发现calldata前面差4位,其是从[04:C4]
xxxxxxxx00000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000c0
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000003
6162610000000000000000000000000000000000000000000000000000000000
3ca7255b
第二次staticcall,此时已经拿到了fwd的合约地址
$\mathtt{gas}=2d50ef$, $\mathtt{to}=6f16a4f343b671b610476c5dcb740e4c5afcbac1$, $\mathtt{In offset}=a0$, $\mathtt{Insize}=03$,$\mathtt{Outoffset}=00$,$\mathtt{OutSize}=00$ 此时的calldata是0x616261, 然后就进入了我们自定义的回文逻辑中。
{
//要比较的字符串在calldata中,其是一个只读的数据结构,需要首先拷贝到内存A中
calldatacopy(0x00, 0x00, calldatasize())
//初始化两个指针,left指向首位A,right指向末位(A+calldatasize()-1)
let left := 0x00
let right := sub(calldatasize(),1)
//比较指针left,right指向的值,如果不等就return false。如果相等,就left++, right--, 直到不满足left < right的条件
//注意mload(left)时,会从left处连续读出32个字节作为left_r的值,但实际上我们只需要头部的一个字节,故需要将其向右侧移动248位。故left_r := shr(248, mload(left))
for {} lt(left, right) {} {
let left_r := shr(248,mload(left))
let right_r := shr(248,mload(right))
if iszero(eq(left_r, right_r)) {
mstore(0x00, 0)
return(0x00, 0x20)
}
left := add(left,0x01)
right := sub(right, 0x01)
}
//最后return true回去
mstore(0x00, 1)
return(0x00, 0x20)
}
我们对比下标准答案:
{
let i := returndatasize()
let m := shr(selfbalance(), calldatasize())
let e := sub(calldatasize(), selfbalance())
for {} and(
eq(shr(248, calldataload(i)), shr(248, calldataload(sub(e, i)))),
lt(i, m)
) {i := add(i, selfbalance())} {}
mstore(callvalue(), eq(i, m))
return(callvalue(), 0x20)
}
可以发现标准答案有如下特点,其帮助节约大量Gas费用:
我们根据上述特点,改进一下我们的代码:
{
//要比较的字符串在calldata中,其是一个只读的数据结构,需要首先拷贝到内存A中
//初始化两个指针,left指向首位A,right指向末位(A+calldatasize()-1)
let left := returndatasize()
let right := sub(calldatasize(),selfbalance())
//比较指针left,right指向的值,如果不等就return false。如果相等,就left++, right--, 直到不满足left < right的条件
//注意mload(left)时,会从left处连续读出32个字节作为left_r的值,但实际上我们只需要头部的一个字节,故需要将其向右侧移动248位。故left_r := shr(248, mload(left))
for {} lt(left, right) {} {
let left_r := shr(248,calldataload(left))
let right_r := shr(248,calldataload(right))
// 不匹配,return false 回去
if iszero(eq(left_r, right_r)) {
mstore(0x00, 0)
return(0x00, 0x20)
}
left := add(left,0x01)
right := sub(right, 0x01)
}
//最后return true回去
mstore(0x00, 1)
return(0x00, 0x20)
}
利用EVM 的OPCODE来节省Gas消耗的几点建议:
这个技巧的应用是为了优化官方解决方案中常量0和1的使用。如上所示,returndatasize()和callvalue()
替换了常量0,而selfbalance()
替换了常量1。通过这种方法,0和1的使用达到了每次使用1字节的最佳效果。选择returndatasize()和selfbalance()
来替换常数的原因是,前者总是0(在任何函数调用之前),而后者通常是我们可以控制的。请记住,平衡表是以wei计算的。其他变量如chainid()或number()
也可能被利用,但一般来说用处不大。
对于其他经常使用的常量,不能由环境或区块变量来呈现,把它们推到堆栈中(例如,PUSH2 0x9453
),然后每当使用它们时,就重复它们(例如,DUP1),以节省(至少)每个额外使用的1个字节。
使用强大的操作码,如ADDMOD、MULMOD、BYTE
来简化算术操作。例如,为了得到x的第一个字节,使用byte(0, x)
而不是shr(248, x)
来节省1个字节。如果不需要改变输入的数据,可以考虑用calldataload
将其推入堆栈,而不是用calldatacopy
推入内存,然后再用mload
推入堆栈。
我们选择在对输入数据进行索引(第三部分)之前将i增加1(第二部分),以避免浪费旧的拷贝。在正常情况下,编译器倾向于在更新一个变量后弹出它的旧拷贝。
0010 DUP1 [i i size]
0011 CALLDATALOAD [data[i] i size]
...
0020 DUP1 [i i size]
0021 SELFBALANCE [1 i i size]
0022 ADD [i+1 i size]
0023 SWAP1 [i i+1 size]
0024 POP [i+1 size]
然而,利用旧的dup会让我们节省一个POP和一个DUP。
0010 DUP1 [i i size]
0011 SELFBALANCE [1 i i size]
0012 ADD [i+1 i size]
0013 SWAP1 [i i+1 size]
0014 CALLDATALOAD [data[i] i+1 size]
...
与明确使用REVERT
操作码相比,EVM中的执行错误具有同样的效果,即在不返回任何数据的情况下进行还原。最常见的方式是通过0xfe,也叫INVALID
指令,它只有1个字节长。如果你想根据一个特定的条件进行还原,可以使用JUMPI
跳到一个不是JUMPDEST
的偏移量进行还原。
pc instruction stack
---- -------------- ----------------------------------
0000 CALLDATASIZE size
0001 RETURNDATASIZE size 0
0002 JUMPDEST
0003 DUP1 size i i
0004 SELFBALANCE size i i 1
0005 ADD size i i+1
0006 SWAP1 size i+1 i
0007 CALLDATALOAD size i+1 data[i]
0008 DUP2 size i+1 data[i] i+1
0009 DUP4 size i+1 data[i] i+1 size
000A SUB size i+1 data[i] size-i-1
000B CALLDATALOAD size i+1 data[i] data[size-i-1]
000C XOR size i+1 xor
000D RETURNDATASIZE size i+1 xor 0
000E BYTE size i+1 byte
000F RETURNDATASIZE size i+1 byte 0
0010 JUMPI size i+1 // revert 如果byte != 0,则revert
0011 DUP2 size i+1 size
0012 DUP2 size i+1 size i+1
0013 LT size i+1 cont
0014 PUSH1 0x02 size i+1 cont 0x02
0016 JUMPI size i+1 //
0017 STOP size i+1
pragma solidity 0.8.0;
import "./Setup.sol";
contract Exploit {
constructor(Setup setup) payable {
setup.challenge().deploy(hex"3660006000376000600136035b80821015604357815160f81c815160f81c8082141515603057600060005260206000f35b60018401935060018303925050505b600c565b600160005260206000f35050");
payable(setup.challenge().fwd()).transfer(1);
payable(setup.challenge().rev()).transfer(1);
}
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!