Exploiting EC-Recover For Efficient Borromean Ring Signatures

Attempting to implement the Borromean Ring Signature algorithm with Schnorr for the EVM results in rather costly transactions. However, the EVM has one pre-compile contract available that executes several point addition and multiplication operations on the classical secp256k1n curve for a very cheap price: $\text{ecrecover}$. This article shows how it can not only be used to validate an ECDSA signature but also, how one may use it as a gadget for other use cases requiring multiple EC addition and multiplication operations.
尝试使用 Schnorr 为 EVM 实现 Borromean 环签名算法会导致相当昂贵的交易。但是，EVM 有一个可用的预编译合约，可以以非常便宜的价格在经典的 secp256k1n 曲线上执行多个点加法和乘法运算： $\text{ecrecover}$ .本文展示了它不仅可以用于验证 ECDSA 签名，还可以将其用作需要多个 EC 加法和乘法运算的其他用例的小工具。

The Math 数学

ECDSA Public Key Recovery
ECDSA 公钥恢复

When verifying an ECDSA signature where the public key $A$ (as $A=aG$) of the signer is known, the following equation must hold for the signature to be valid:
在验证签名者的公钥 $A$ （as $A=aG$ ） 已知的 ECDSA 签名时，必须满足以下等式才能使签名有效：

$R=(hash\left(m\right)\cdot s^{-1})G+(r\cdot s^{-1})A$

But, as you might know, the $\text{ecrecover}$ pre-compile in the EVM is only passed
但是，您可能知道，EVM 中的 $\text{ecrecover}$ 预编译仅通过

• The $\text{keccak256}$ hash of the transaction/message ($hash\left(m\right)$)
  事务/消息的 $\text{keccak256}$ 哈希值 （ $hash\left(m\right)$ ）
• The signature components $r$ and $v$ which are used to derive $R$ (as $R=kG$)
  签名组件 $r$ 和 $v$ 用于派生 $R$ （作为 $R=kG$ ）
• The signature component $s$
  签名组件 $s$

The result is the address of the signer – which is a partial hash of public key $A$. The validity is then based on whether the expected signer address is returned. If not, or if the address returned is the zero-address, the signature is considered invalid.
结果是签名者的地址 – 它是公钥 $A$ 的部分哈希值。然后，有效性基于是否返回预期的签名者地址。如果不是，或者返回的地址为零地址，则认为签名无效。

So obviously, it must be possible to rearrange the equation and solve for $A$:
所以很明显，必须能够重新排列方程并求解 $A$ ：

$(r\cdot s^{-1})A=R-(hash\left(m\right)\cdot s^{-1})G$

$A=\frac{R-(hash\left(m\right)\cdot s^{-1})G}{r\cdot s^{-1}}$

$A=\frac{sR-hash\left(m\right)\cdot G}{r}$

$A=(sR-hash\left(m\right)\cdot G)\cdot r^{-1}$

Therefore $\text{ecrecover}$ basically takes in two scalars $hash\left(m\right)$, $s$, and a point $R$ and returns $address\left(A\right)$ which is the (partial) hash of a resulting point from handling the input variables.
因此 $hash\left(m\right)$ ， $\text{ecrecover}$ 基本上接受两个标量 ， ， 和一个点， $s$ 并返回 $address\left(A\right)$ 处理输入变量的结果点 $R$ 的（部分）哈希值。

$address\left(A\right)=\text{ecrecover}(hash\left(m\right),v,r,s)=address((sR-hash\left(m\right)\cdot G)\cdot r^{-1})$

Exploiting EC-Recover 利用 EC-Recover

This doesn’t seem too dissimilar from what is happening in a single forward-step in the Borromean Ring Signature algorithm:
这似乎与Borromean Ring Signature算法中单个向前步骤中发生的情况没有太大区别：

$e_{+1}=hash(m,(sG+eP))$

So can’t we then exploit this precompile to implement a more efficient EVM-based Borromean Ring Signature validation by
因此，我们难道不能利用这个预编译来实现更高效的基于 EVM 的 Borromean 环签名验证吗？

• Using the input point $R$ as $P$ (public key of a ring member, with the signer’s private key being $x$ for $P=xG$) by $r$ being the x-coordinate of $P$ and $v$ to derive the correct y-coordinate of $P$
  使用输入点 $R$ 作为 $P$ （环成员的公钥，签名者的私钥为 $x$ ） $P=xG$ 作为 $r$ 的 x 坐标 $P$ $v$ ，并得出 $P$
• Using what is expected to be the hashed transaction/message as $s$ component for the ring
  使用预期的散列事务/消息作为 $s$ 环的组件
• Using the ECDSA’s $s$ component as input hash $e$ of the ring
  使用 ECDSA 的 $s$ 组件作为环 $e$ 的输入哈希
• Mixing in the message $m$ by hashing it with the resulting address
  通过将消息与生成的地址进行哈希处理来混合消息 $m$

$e_{+1}=hash(m,\text{ecrecover}(s,v,r,e))=hash(m,address((eP-sG)\cdot r^{-1}))$

Chameleon Hashes within EC-Recover
EC-Recover中的Chameleon Hashes

As before, the signer of the Ring Signature must be able to make use of a Chameleon Hash in order to determine $e_{+1}$ before knowing what $e$ will be.
和以前一样，环签名的签名者必须能够使用变色龙哈希，以便在知道将是什么 $e$ 之前确定 $e_{+1}$ 。

We can follow the original pattern of choosing a random scalar $k$. Thankfully, we already know the signer’s public key point $P$, therefore we also know $r^{-1}$.
我们可以遵循选择随机标量 $k$ 的原始模式。值得庆幸的是，我们已经知道了签名者的公钥点 $P$ ，因此我们也知道 $r^{-1}$ 了。

$e_{+1}=hash(m,address(kG\cdot r^{-1}))$

After using this to step through the entire ring, we will know what the input $e$ will be. Therefore we can replace $k$ by solving for $s$:
使用它来逐步执行整个环之后，我们将知道输入 $e$ 的内容。因此，我们可以通过求解来 $s$ 替换 $k$ ：

$kG\cdot r^{-1}=(eP-sG)\cdot r^{-1}$

$kG\cdot r^{-1}=(eP-sG)\cdot r^{-1}$

$kG=exG-sG$

$k\cdot G=ex\cdot G-s\cdot G$

$k=ex-s$

$s=ex-k$

This resulting $s$ of the signer should then be indistinguishable from the randomly chosen $s$ values of the other ring members.
然后，签名者的这种结果 $s$ 应该与其他环成员的随机选择 $s$ 值无法区分。

$hash(m,address(kG\cdot r^{-1}))=hash(m,address((eP-sG)\cdot r^{-1}))$

The Code 守则

Off-Chain Signing 链下签名

from Crypto.Hash import keccak
from ecdsa import ellipticcurve, numbertheory, SECP256k1
import secrets
from eth_abi import encode
from collections import defaultdict

curve = SECP256k1.curve
n = SECP256k1.order
G = SECP256k1.generator

def H(data, encoding):
    return int.from_bytes(keccak.new(digest_bits=256).update(encode(encoding, data)).digest(), 'big') % n

# Signs a message with a structure of rings of members similar to this:
#
# [ [ (P,0), (P,0), (P,x), (P,0) ], [ (P,0), (P,x), (P,0) ] ]
# ^ ^               ^^^^^        ^  ^ ^^^^^               ^ ^
# ^ ^               Signer       ^  ^ Member (unknown x)  ^ ^
# ^ ^                            ^  ^                     ^ ^
# ^ ^---------- Ring 0 ----------^  ^------- Ring 1 ------^ ^
# ^                                                         ^
# ^------------------- Borromean Rings ---------------------^
#
def sign(message, members):
    # Determine v and r values for each public key point P.
    v = [[28 if P.y() & 1 else 27 for P, _ in ring] for ring in members]
    r = [[P.x() for P, _ in ring] for ring in members]
    M = H([message, v, r], ["bytes", "uint8[][]", "uint256[][]"])

    # Create Chameleon Hashes for each signer.
    k = defaultdict(int)
    e = defaultdict(lambda: defaultdict(int))
    signer_idx = defaultdict(int)
    for i, ring in enumerate(members):
        # Random scalar for Chameleon Hash (later replaced by e & s).
        k[i] = secrets.randbelow(n) + 1

        for j, (P, x) in enumerate(ring):
            # Set Chameleon Hash as e of signer.
            if x != 0:
                # e = hash(m, address(kG * r^(-1)))
                R = (k[i] * G) * numbertheory.inverse_mod(r[i][j], n)
                address = '0x' + keccak.new(digest_bits=256).update(R.to_bytes()).digest()[-20:].hex()
                e[i][j + 1] = H([M, address, i, j], ["uint256", "address", "uint8", "uint8"])
                # Remember signer's index in current ring.
                signer_idx[i] = j

    # Determine e for each member after signer.
    s = defaultdict(lambda: defaultdict(int))
    for i, ring in enumerate(members):
        for j in range(signer_idx[i] + 1, len(ring)):
            (P, _) = ring[j]
            # Random scalar s for non-signers.
            s[i][j] = secrets.randbelow(n) + 1
            # e' = hash(m, address((eP - sG) * r^(-1)))
            R = (e[i][j]*P + (-(s[i][j] * G))) * numbertheory.inverse_mod(r[i][j], n)
            address = '0x' + keccak.new(digest_bits=256).update(R.to_bytes()).digest()[-20:].hex()
            e[i][j + 1] = H([M, address, i, j], ["uint256", "address", "uint8", "uint8"])

    # Gather the last e value for each ring (e[i][-1]).
    ring_ends = [e[i][max(e[i].keys())] for i in e]
    # And determine e0 based on each ring's last member.
    e0 = H([ring_ends], ["uint256[]"])

    # Starting from e0, determine e for each member before the signer.
    for i, ring in enumerate(members):
        e[i][0] = e0
        for j in range(signer_idx[i]):
            (P, _) = ring[j]
            # Random scalar s for non-signers.
            s[i][j] = secrets.randbelow(n) + 1
            # e' = hash(m, address((eP - sG) * r^(-1)))
            R = (e[i][j]*P + (-(s[i][j] * G))) * numbertheory.inverse_mod(r[i][j], n)
            address = '0x' + keccak.new(digest_bits=256).update(R.to_bytes()).digest()[-20:].hex()
            e[i][j + 1] = H([M, address, i, j], ["uint256", "address", "uint8", "uint8"])

    # Finally, calculate s for each Chameleon Hash to replace k with.
    for i, ring in enumerate(members):
        j = signer_idx[i]
        (P, x) = ring[j]
        s[i][j] = (e[i][j]*x - k[i]) % n
        # Sanity-check: Hash with s & e should be the same as hash with k.
        R_ = (e[i][j]*P + (-(s[i][j] * G))) * numbertheory.inverse_mod(r[i][j], n)
        address_ = '0x' + keccak.new(digest_bits=256).update(R_.to_bytes()).digest()[-20:].hex()
        e_ = H([M, address_, i, j], ["uint256", "address", "uint8", "uint8"])
        assert e[i][j + 1] == e_

    return (e0, v, r, [ [s[i][j] for j in sorted(s[i])] for i in sorted(s) ])


# ---------------------- Playground ----------------------------------

def member(signer = False):
    x = secrets.randbelow(n) + 1
    P = G*x
    return (P, x if signer else 0)

m = b"hello"
signature = sign(m,  [
    [ member(), member(), member(True),  member() ],
    [ member(), member(True), member() ]
])

print(f'''BorromeanRing.validate(
  m = 0x{m.hex()}
  e0 = {signature[0]}
  v = {signature[1]}
  r = {signature[2]}
  s = {signature[3]}
)''')

$ python borromean-ecdsa.py 
BorromeanRing.validate(
  m = 0x68656c6c6f
  e0 = 109125325252662397704443391788259493773533497479890032494653283252810772602958
  v = [[27, 27, 27, 28], [27, 28, 28]]
  r = [[55150867365147610330436483336757752946760082639320608573853394922858405031248, 44324768931115417252417103419087001014616806521272598659415820542004032154792, 85740849830320470813451766704578545536484323110426743630330214133618289818508, 40093116712223621022063979627270424589535872400915748056121284698792389206752], [67638234765727728523624259252248319317865344202198443209806192542902514194911, 79101705934303499580660335186719424455362081223457855793876495474664908758285, 108775676743731072371387601891326407936759016425842354275036641669646997537653]]
  s = [[57239406502032993091643979135786211342444107443510211006808219707319777747289, 16848866492206211083856507954968088143833099320997232323930353416909551719419, 69888003942361774324397468790806152708741706628862979889227810665815345552676, 85553560707166780066278918897902846075897912973709723370418788677963503376623], [98599600510980798246984761639501715191746992931585718902740505965772955348078, 68672496231270726515305844924296592732589210054688804822920292004641009329066, 65829000216344475900388419547580193157261411351990824781389896139499037837904]]
)

On-Chain Verification 链上验证

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

contract BorromeanRing {

    uint256 internal constant secp256k1n = 115792089237316195423570985008687907852837564279074904382605163141518161494337;

    function validate(
        bytes calldata m,
        uint256 e0,
        uint8[][] calldata v,
        uint256[][] calldata r,
        uint256[][] calldata s
    ) external pure returns (bool) {
        // M = H(m, P)
        uint256 M = uint256(keccak256(abi.encode(m, v, r))) % secp256k1n;

        uint256[] memory e = new uint256[](v.length);

        // For each Ring i
        for (uint8 i = 0; i < v.length; i++) {
            // Each Ring starts from the same e0
            e[i] = e0;
            // For each Member j
            for (uint8 j = 0; j < v[i].length; j++) {
                require(v[i][j] == 27 || v[i][j] == 28);
                // (Mis-)Use ecrecover as a widget to calculate (eP - sG) * r^(-1)
                // e = hash(m, address((eP - sG) * r^(-1)))
                address R = ecrecover(bytes32(s[i][j]), v[i][j], bytes32(r[i][j]), bytes32(e[i]));
                require(R != address(0x0));
                e[i] = uint256(keccak256(abi.encode(M, R, i, j))) % secp256k1n;
            }
        }

        // Each Ring's last e value build e0
        // e'0 = H(e, e, ...)
        uint256 e0_ = uint256(keccak256(abi.encode(e))) % secp256k1n;

        // The signature is valid if when
        // e0 == e'0
        return e0 == e0_;
    }

}