Paradigm CTF-回文子串

bixia1994
更新于 2021-07-23 19:34
阅读 2665

如何更好的节省Gas费用呢？本文提到了5种方法

本题目是Paradigm的CTF系列中挺有意思的一道题，它模仿了leetcode中[125. 验证回文串](https://leetcode-cn.com/problems/valid-palindrome/)这道题目，通过给定输入，让你判断输入的字符串是不是回文子串，实现用solidity来刷Leetcode，伟大的Samczsun!

> 目前作者正在找智能合约相关的工作，希望能跟行业内人士多聊聊 🐟 。如果你觉得我写的还不错，可以加我的微信：woodward1993

## 题目分析

![imgblog.png](https://img.learnblockchain.cn/attachments/2021/07/sM3iFQSw60faa781b52c8.png)

我们先简单看下什么是回文：

回文就是从左到右读和从右到左读都是一样的字符串成文回文。最经典的解决回文子串的方法是双指针法，如下图所示：

只要left指针和right指针所指的内容不一致，则返回false。直到两个指针相遇，即left < right(这里可以不用取等号，因为奇数时，留下唯一一个肯定是回文)

### :one: 定义左右指针

分别定义左指针left，指向字符串左边第一个元素；右指针right指向字符串右边第一个元素
![1609644495CFJcQTLeetCode125002.jpeg](https://img.learnblockchain.cn/attachments/2021/07/Uvt4eJ5w60faa78a6a530.jpeg)

### :two:移动指针

这时指针left指向的字符”c“与指针right指向的字符”c“是一样的。left需要向右移动一位。同理，指针right也应向左移动一位。
![1609644649KKuYEuLeetCode125004.jpeg](https://img.learnblockchain.cn/attachments/2021/07/x3E69Jnw60faa793017fa.jpeg)

### :three:判定退出

指针left指向的字符”t“与right指向的字符”n“是不同的，也就是说字符串"@CaTnAc#"不是回文串。至此，即使有剩余的字符也就不需要考虑了
![1609644696OXyBbKLeetCode125006.jpeg](https://img.learnblockchain.cn/attachments/2021/07/Wt2Cjxml60faa799ac846.jpeg)

## 测试用例：

我们再来看看他的测试用例有哪些：

```python
testcases = {
    "": True,
    "a": True,
    "ab": False,
    "aba": True,
    "paradigm": False,
    "tattarrattat": True,
}
```

## 思路：

其实该题的**难点在于输入参数的判断**。:muscle: 真正的判断是否为回文的逻辑是很清晰的。

### 参数判断 :muscle:

当通过函数`test(string)`来输入参数如："aba"时，其aba会被编码为：

```js
0xf9fbd554 => 函数选择器
0000000000000000000000000000000000000000000000000000000000000020 => 动态类型string的编码head
0000000000000000000000000000000000000000000000000000000000000003 => tail[0] 字节长度
6162610000000000000000000000000000000000000000000000000000000000 => tail[1] "aba"的字节数组
```

因为string是一个动态类型，其在编码时，先编码head，在编码tail。head中的内容是tail部分距离该head所占位点的偏移量，是一个相对值。

$$
\mathtt{head}(X_i) = \mathtt{enc}(||head(X_1) ... head(X_{k-1}) tail(X_1) ... tail(X_{i-1})||)
$$

$$
tail(X_i) = enc(X_i)
$$

对于字符串string，其在编码tail时，

1. 先转换成字节数组 “aba” => 0x616261
2. 得到字节数组的长度 len(0x616261) = 0x03
3. 将字节数组左对齐 0x616261 =>0x6162610000000000000000000000000000000000000000000000000000000000

故在结合上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**，
![image20210711110836406.png](https://img.learnblockchain.cn/attachments/2021/07/TvhSxSAl60faa7f20e1a5.png)
![image20210711110846467.png](https://img.learnblockchain.cn/attachments/2021/07/zCm1lVGX60faa7f244372.png)

```js
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, 然后就进入了我们自定义的回文逻辑中。
![image20210711113228744.png](https://img.learnblockchain.cn/attachments/2021/07/AzPpZLhT60faa7ff7d46f.png)
![image20210711113247810.png](https://img.learnblockchain.cn/attachments/2021/07/7eAA5Nfp60faa7ffa5aeb.png)

### 回文逻辑

```js
{
//要比较的字符串在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)
}
```

我们对比下标准答案:

```js
{           
    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费用：

1. 使用returndatasize()来代替 push1 0x00
2. 使用selfbalance()来代替 Push1 0x01
3. 使用calldataload(ptr)来代替 mstore(), mload(), 减少一次内存拷贝，直接使用calldataload
4. 使用 i == len(calldata)/2 来判定是否成功，如果相等则返回True，如果不等，则返回False。而不是上面写的分别return True和return False

我们根据上述特点，改进一下我们的代码：

```js
{
//要比较的字符串在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)
}
```

## 节省GAS

利用EVM 的OPCODE来节省Gas消耗的几点建议：

### 技巧1：用环境变量和区块变量替换常数

这个技巧的应用是为了优化官方解决方案中常量0和1的使用。如上所示，`returndatasize()和callvalue()`替换了常量0，而`selfbalance()`替换了常量1。通过这种方法，0和1的使用达到了每次使用1字节的最佳效果。选择`returndatasize()和selfbalance()`来替换常数的原因是，前者总是0（在任何函数调用之前），而后者通常是我们可以控制的。请记住，平衡表是以wei计算的。其他变量如`chainid()或number()`也可能被利用，但一般来说用处不大。

### 技巧2：push一次，dup多次

对于其他经常使用的常量，不能由环境或区块变量来呈现，把它们推到堆栈中（例如，`PUSH2 0x9453`），然后每当使用它们时，就重复它们（例如，DUP1），以节省（至少）每个额外使用的1个字节。

### 技巧3：利用特殊操作码的优势

使用强大的操作码，如`ADDMOD、MULMOD、BYTE`来简化算术操作。例如，为了得到x的第一个字节，使用`byte(0, x)`而不是`shr(248, x)`来节省1个字节。如果不需要改变输入的数据，可以考虑用`calldataload`将其推入堆栈，而不是用`calldatacopy`推入内存，然后再用`mload`推入堆栈。

### 提示4：通过重复使用变量的旧拷贝来避免POP

我们选择在对输入数据进行索引（第三部分）之前将i增加1（第二部分），以避免浪费旧的拷贝。在正常情况下，编译器倾向于在更新一个变量后弹出它的旧拷贝。

```js
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。

```js
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]
...
```

### 提示5：利用执行错误来恢复交易

与明确使用`REVERT`操作码相比，EVM中的执行错误具有同样的效果，即在不返回任何数据的情况下进行还原。最常见的方式是通过0xfe，也叫`INVALID`指令，它只有1个字节长。如果你想根据一个特定的条件进行还原，可以使用`JUMPI`跳到一个不是`JUMPDEST`的偏移量进行还原。

```js
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
```

## 最后：

```js
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);
    }
}
```

![image20210723193312815.png](https://img.learnblockchain.cn/attachments/2021/07/t19AUtp160faa9146c92c.png)

本题目是Paradigm的CTF系列中挺有意思的一道题，它模仿了leetcode中125. 验证回文串这道题目，通过给定输入，让你判断输入的字符串是不是回文子串，实现用solidity来刷Leetcode，伟大的Samczsun!

目前作者正在找智能合约相关的工作，希望能跟行业内人士多聊聊 🐟 。如果你觉得我写的还不错，可以加我的微信：woodward1993

题目分析

我们先简单看下什么是回文：

回文就是从左到右读和从右到左读都是一样的字符串成文回文。最经典的解决回文子串的方法是双指针法，如下图所示：

只要left指针和right指针所指的内容不一致，则返回false。直到两个指针相遇，即left < right(这里可以不用取等号，因为奇数时，留下唯一一个肯定是回文)

:one: 定义左右指针

分别定义左指针left，指向字符串左边第一个元素；右指针right指向字符串右边第一个元素

:two:移动指针

这时指针left指向的字符”c“与指针right指向的字符”c“是一样的。left需要向右移动一位。同理，指针right也应向左移动一位。

:three:判定退出

指针left指向的字符”t“与right指向的字符”n“是不同的，也就是说字符串"@CaTnAc#"不是回文串。至此，即使有剩余的字符也就不需要考虑了

测试用例：

我们再来看看他的测试用例有哪些：

testcases = {
    "": True,
    "a": True,
    "ab": False,
    "aba": True,
    "paradigm": False,
    "tattarrattat": True,
}

思路：

其实该题的难点在于输入参数的判断。:muscle: 真正的判断是否为回文的逻辑是很清晰的。

参数判断 :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时，

先转换成字节数组 “aba” => 0x616261
得到字节数组的长度 len(0x616261) = 0x03
将字节数组左对齐 0x616261 =>0x6162610000000000000000000000000000000000000000000000000000000000

故在结合上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的合约地址

回文逻辑

{
//要比较的字符串在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 &lt; 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费用：

使用returndatasize()来代替 push1 0x00
使用selfbalance()来代替 Push1 0x01
使用calldataload(ptr)来代替 mstore(), mload(), 减少一次内存拷贝，直接使用calldataload
使用 i == len(calldata)/2 来判定是否成功，如果相等则返回True，如果不等，则返回False。而不是上面写的分别return True和return False

我们根据上述特点，改进一下我们的代码：

{
//要比较的字符串在calldata中，其是一个只读的数据结构，需要首先拷贝到内存A中
//初始化两个指针，left指向首位A，right指向末位(A+calldatasize()-1)
    let left := returndatasize()
    let right := sub(calldatasize(),selfbalance())
//比较指针left，right指向的值，如果不等就return false。如果相等，就left++, right--, 直到不满足left &lt; 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)
}

节省GAS

利用EVM 的OPCODE来节省Gas消耗的几点建议：

技巧1：用环境变量和区块变量替换常数

这个技巧的应用是为了优化官方解决方案中常量0和1的使用。如上所示，returndatasize()和callvalue()替换了常量0，而selfbalance()替换了常量1。通过这种方法，0和1的使用达到了每次使用1字节的最佳效果。选择returndatasize()和selfbalance()来替换常数的原因是，前者总是0（在任何函数调用之前），而后者通常是我们可以控制的。请记住，平衡表是以wei计算的。其他变量如chainid()或number()也可能被利用，但一般来说用处不大。

技巧2：push一次，dup多次

对于其他经常使用的常量，不能由环境或区块变量来呈现，把它们推到堆栈中（例如，PUSH2 0x9453），然后每当使用它们时，就重复它们（例如，DUP1），以节省（至少）每个额外使用的1个字节。

技巧3：利用特殊操作码的优势

使用强大的操作码，如ADDMOD、MULMOD、BYTE来简化算术操作。例如，为了得到x的第一个字节，使用byte(0, x)而不是shr(248, x)来节省1个字节。如果不需要改变输入的数据，可以考虑用calldataload将其推入堆栈，而不是用calldatacopy推入内存，然后再用mload推入堆栈。

提示4：通过重复使用变量的旧拷贝来避免POP

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]