【EOSIO】EOS/WAX签名错误 is_canonical( c ): signature is not canonical 问题

回顾

《【区块链】发布一个纯Python实现的EOSIO WAX SDK》
在之前的文章中，我们动手重新实现了一个轻量级的 EOSIO SDK，但使用了一段时间，发现有时候提交交易到 EOS/WAX 网络的 RPC 节点时，会返回如下错误：

{“code”:500,“message”:“Internal Service Error”,“error”:{“code”:10,“name”:“assert_exception”,“what”:“Assert Exception”,“details”:[{“message”:“is_canonical( c ): signature is not canonical”,“file”:“elliptic_secp256k1.cpp”,“line_number”:164,“method”:“public_key”}]}}

大概原因是签名不规范，R 或 S 值过大

规范签名

规范签名实际上在BTC中就有所规定:

【Low S values in signatures】:https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#Low_S_values_in_signatures

BTC中 bip62 规定了签名中的 S 值不能大于 N/2，因为对于一个规范的R值和S值，(R, S)、(N-R, S)、(R, N-S)、(N-R, N-S)都是合法的签名值，如果不对其进行约束的话，会导致一个问题，对于同一笔交易，有四种合法的签名结果，当你的交易提交到网络上后，恶意攻击者可以利用你的签名 (R, S)，生成一个一模一样的交易，并附上签名(N-R, S)，进行重放攻击 (Replay Attacks)。

结果就是原本你的交易是给B君转账500个币，被恶意者重放攻击后，会变成两笔交易，重复给B君转账500个币两次，从而蒙受损失。

实际上，只需规范 R 或 S 值小于 N/2 即可避免该问题，不过在EOSIO中，这个规范更严格：

https://steemit.com/steem/@dantheman/steem-and-bitshares-cryptographic-security-update

EOSIO 要求 R 和 S 都要同时小于 N/2 才行

排查问题

我们的【eosapi】 签名部分的代码，参考的是【ueosio】，我们来看看 is_canonical() 的实现：

def is_canonical(r, s):
	C = int((2 ** 256 - 1) / 2)
    return r <= C and s <= C

确实没问题啊，签名是256位的，N为256位数的最大值 2 ** 256 - 1，代码检查了 R 和 S 均小于 N/2
但为什么EOS RPC服务端还是报错了呢？

解决问题的最佳方式就是查看源码

返回的错误信息已经告诉我们：

{“message”:“is_canonical( c ): signature is not canonical”,“file”:“elliptic_secp256k1.cpp”,“line_number”:164,“method”:“public_key”}

这个错误来自【elliptic_secp256k1.cpp】的第164行，于是我们在 EOSIO 官方 github 中找到这行代码，并找到【is_canonical】这个函数的实现：
https://github.com/EOSIO/fc/blob/master/src/crypto/elliptic_common.cpp

bool public_key::is_canonical( const compact_signature& c ) {
    
        return !(c.data[1] & 0x80)
               && !(c.data[1] == 0 && !(c.data[2] & 0x80))
               && !(c.data[33] & 0x80)
               && !(c.data[33] == 0 && !(c.data[34] & 0x80));
    }

然后就破案了，原来它不仅要求 R 和 S 均小于 N/2，还要求 R 和 S 均大于等于 (2 ** (256-8) - 1) / 2

理解原理

先解释一下这个算法怎么理解，首先 compact_signature& c 是什么，compact_signature& c 就是签名数据，我们再看看【ueosio】是怎么生成这个签名的：

def sign_hash(h, pk):
    nonce = 0
    while True:
        v, r, s = ecdsa_raw_sign_nonce(h, pk, nonce)
        if is_canonical(r, s):
            signature = '00%02x%064x%064x' % (v, r, s)
            break
        nonce += 1
    sig = DataStream(bytes.fromhex(signature)).unpack_signature()
    return sig

这个【signature】实际上就是 V / R / S 拼接出来的，一共66个字节，开头的 ‘\x00’ 表示签名类型，忽略去掉，那么最终服务端解析的 compact_signature& c 实际就是 V / R / S 拼接出来 65 个字节，其中 V 占 1 个字节，R 和 S 分别占32字节，因为签名是256位的。

那么在【is_canonical】里，c.data[1] 指的就是 R 值的最高字节（高8位），c.data[33] 指的就是 S 值的最高字节（高8位）

那么

 c.data[1] & 0x80

是什么意思呢？

首先 c.data[1] 是 1 个字节，0x80 的二进制是什么，是 10000000

c.data[1] 按位与上0x80，什么时候结果为 True ？当然是要求 c.data[1] 的二进制最高位也为 1 的时候，表达式才为True，当 c.data[1] 的二进制最高位为 0 的时候，表达式返回 False

c.data[1] 的二进制最高位为 1 的话，那么 c.data[1] 至少要 >= 0x80, c.data[1] 的二进制最高位为 0 的话，那么c.data[1] 必须 < 0x80

所以这个按位与的表达式实际上等同于

 c.data[1] >= 128

所以

!(c.data[1] & 0x80)

实际上等同于

c.data[1] < 128

而一个32字节的256位数的最高字节（高8位）小于128是什么意思呢？

首先，一个字节的最大值是255，小于128就是小于这一个字节所表示的最大值的一半

而一个32字节数的最高字节小于128，就意味着这个32字节的数字，小于32字节所能表示的最大值的一半，那不就是小于 N/2 嘛

所以绕去绕来，这个代码的意思还是要求 R 和 S 均小于 N/2

但除此之外，它还加了两个条件：

&& !(c.data[1] == 0 && !(c.data[2] & 0x80))

&& !(c.data[33] == 0 && !(c.data[34] & 0x80));

那意思不就是说， R 的最高字节如果等于0的话，R的次高字节不能小于128嘛，S值同理

而 R 的次高字节不能小于128，不就意味着要求 R 大于等于 (2 ** (256-8) - 1) / 2

解决

所以，【ueosio】的【is_canonical】函数理论上这样改就可以了：

def is_canonical(r, s):
    C1 = int((2 ** 256 - 1) / 2)
    C2 = int((2 ** (256-8) - 1) / 2)
    return C2 <= r < C1 and C2 <= s < C1

当然，最严谨的改法还是完全和 EOSIO 官方的代码保持一致，最终我们这样改：

def is_canonical(c):
    return not (c[1] & 0x80) \
           and not (c[1] == 0 and not (c[2] & 0x80)) \
           and not (c[33] & 0x80) \
           and not (c[33] == 0 and not (c[34] & 0x80))

并且已将代码提交更新：
https://github.com/encoderlee/eosapi/commit/5ffd1235dd938cc8836be58f9f12622e7f3d08ae

请大家及时更新，以避免这个问题：

pip install --upgrade eosapi

题外话

我什么我们的签名代码要参考【ueosio】，而不参考【eospy】？

其实主要是性能问题，同样的一个交易，【eospy】签名耗时20ms，而【ueosio】仅耗时2ms，相差10倍之多！！！

20ms 是什么概念？我这里到上海电信的机房延迟 20ms 都不到，如果你提交交易比别人慢了 20ms，做交易机器人的时候怎么抢得过别人呢。

【eospy】内部使用的签名库是【ecdsa】
而
【ueosio】内部使用的签名库是【cryptos】

按理说【ecdsa】比【cryptos】更受欢迎，也做的更完善，而且【ecdsa】宣称的测试数据也没有那么拉跨，那么很可能是【eospy】的使用姿势问题导致的慢

【cryptos】在github上的star虽然没那么多，但是！

【cryptos】在github上的项目名字是【pybitcointools】，它的最初版本是以太坊的创始人V神亲自写的，后来V神没有时间精力维护，便交给开源社区打理，详情见这里：
https://github.com/vbuterin/pybitcointools

I really don’t have time to maintain this library further. If you want to fork it or use it despite lack of maintenance, feel free to clone locally and revert one commit.
This externally-maintained fork looks good though I did not personally
write it so can’t vouch for security:
https://github.com/primal100/pybitcointools

除了效率问题，再一次证明了我们的【eosapi】 选择V神的【cryptos】实现底层签名算法是正确的选择！

交流讨论