Exploiting EC-Recover For Efficient Borromean Ring Signatures

October 21, 2023 by patrickd

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: ${\mathtt{\text{ecrecover}}}$ (opens in a new tab). 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.

The Math

💡

Vitalik actually described this technique in 2018 (opens in a new tab) and hinted that it could indeed be used for things like ring signatures.

ECDSA Public Key Recovery

When verifying an ECDSA signature where the public key ${A}$ (as ${A}={a}{G}$ ) of the signer is known, the following equation must hold for the signature to be valid:

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

But, as you might know, the ${\mathtt{\text{ecrecover}}}$ pre-compile in the EVM is only passed

The ${\mathtt{\text{keccak256}}}$ hash of the transaction/message ( ${h}{a}{s}{h}{\left({m}\right)}$ )
The signature components ${r}$ and ${v}$ which are used to derive ${R}$ (as ${R}={k}{G}$ )
The signature component ${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.

So obviously, it must be possible to rearrange the equation and solve for ${A}$ :

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

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

${A}=\frac{{{s}{R}-{h}{a}{s}{h}{\left({m}\right)}\cdot{G}}}{{{r}}}$

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

Therefore ${\mathtt{\text{ecrecover}}}$ basically takes in two scalars ${h}{a}{s}{h}{\left({m}\right)}$ , ${s}$ , and a point ${R}$ and returns ${a}{d}{d}{r}{e}{s}{s}{\left({A}\right)}$ which is the (partial) hash of a resulting point from handling the input variables.

${a}{d}{d}{r}{e}{s}{s}{\left({A}\right)}={\mathtt{\text{ecrecover}}}{\left({h}{a}{s}{h}{\left({m}\right)},{v},{r},{s}\right)}={a}{d}{d}{r}{e}{s}{s}{\left({\left({s}{R}-{h}{a}{s}{h}{\left({m}\right)}\cdot{G}\right)}\cdot{r}^{{-{1}}}\right)}$

Exploiting EC-Recover

This doesn't seem too dissimilar from what is happening in a single forward-step in the Borromean Ring Signature algorithm:

${e}_{{+{1}}}={h}{a}{s}{h}{\left({m},{\left({s}{G}+{e}{P}\right)}\right)}$

So can't we then exploit this precompile to implement a more efficient EVM-based Borromean Ring Signature validation by

Using the input point ${R}$ as ${P}$ (public key of a ring member, with the signer's private key being ${x}$ for ${P}={x}{G}$ ) by ${r}$ being the x-coordinate of ${P}$ and ${v}$ to derive the correct y-coordinate of ${P}$
Using what is expected to be the hashed transaction/message as ${s}$ component for the ring
Using the ECDSA's ${s}$ component as input hash ${e}$ of the ring
Mixing in the message ${m}$ by hashing it with the resulting address

${e}_{{+{1}}}={h}{a}{s}{h}{\left({m},{\mathtt{\text{ecrecover}}}{\left({s},{v},{r},{e}\right)}\right)}={h}{a}{s}{h}{\left({m},{a}{d}{d}{r}{e}{s}{s}{\left({\left({e}{P}-{s}{G}\right)}\cdot{r}^{{-{1}}}\right)}\right)}$

Chameleon Hashes within EC-Recover

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.

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}}}$ .

${e}_{{+{1}}}={h}{a}{s}{h}{\left({m},{a}{d}{d}{r}{e}{s}{s}{\left({k}{G}\cdot{r}^{{-{1}}}\right)}\right)}$

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}$ :

${k}{G}\cdot{r}^{{-{1}}}={\left({e}{P}-{s}{G}\right)}\cdot{r}^{{-{1}}}$

${k}{G}\cdot\cancel{{{r}^{{-{1}}}}}={\left({e}{P}-{s}{G}\right)}\cdot\cancel{{{r}^{{-{1}}}}}$

${k}{G}={e}{x}{G}-{s}{G}$

${k}\cdot\cancel{{{G}}}={e}{x}\cdot\cancel{{{G}}}-{s}\cdot\cancel{{{G}}}$

${k}={e}{x}-{s}$

${s}={e}{x}-{k}$

This resulting ${s}$ of the signer should then be indistinguishable from the randomly chosen ${s}$ values of the other ring members.

${h}{a}{s}{h}{\left({m},{a}{d}{d}{r}{e}{s}{s}{\left({k}{G}\cdot{r}^{{-{1}}}\right)}\right)}={h}{a}{s}{h}{\left({m},{a}{d}{d}{r}{e}{s}{s}{\left({\left({e}{P}-{s}{G}\right)}\cdot{r}^{{-{1}}}\right)}\right)}$

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_;
    }
 
}

← Cryptocurrency Privacy Technologies: Borromean Ring Signatures Cryptocurrency Privacy Technologies: Confidential Transaction Values →