How to prevent signature input double spending

Question

Let's say I have implemented a contract that allows you to transfer a token to a recipient for whom you do not have the address.

Let's say I have 5 of token x and I want to give 1 to my friend and I do not know her address, as a result I send her a message (e.g. give one token from my account to anyone who claims this) and a corresponding signature.

My friend can then broadcast the function call claimToken(message, signature) and get the token from me in the smart contract.

My question is: how do I prevent a node from seeing this transaction in the mempool and taking the inputs (message, signature) and sending the transaction with a higher fee, essentially getting confirmed before my friend and taking the token for themselves?

I understand that this is solved if you sign the message with the recipients address, but this cannot happen when you do not know the address of the recipient.

Answer 1

You can have the recipient self-sign if your contract can be designed to support that.

Let E'(E(m, k), k') = m where E is an asymmetric encryption algorithm and E' is its inverse, m is a message, and k' is a public key and k is a private key; WLOG, E could be E'. Let S be the sender and R be the recipient of the token; let R be R's Ethereum account.

I believe the following scheme is not vulnerable to the out-spending attack:

1. S securely sends k to R.
2. R computes m' = E(R, k) and calls claimToken(m').
3. In claimToken, the function allows claiming of tokens if and only if E(m', k') == R.

This, by itself, does not prevent R from reusing k to claim the token multiple times. If you wanted to have, say, five claimable sets of tokens, you could do something like this:

1. S securely sends k_i to R where k_i is the ith private key (corresponding to k'_i).
2. R computes m' = E(R, k_i) and calls claimToken(m', i).
3. In claimToken, the function allows claiming of tokens if and only if E(m', k_i') == R AND used[i] is false.
4. The claimToken function then sets used[i] to true.

This requires the public keys to be pre-programmed into the contract. You could alternately have an arbitrary number of keys by having the owner of the contract or a delegate update the verifying public key to a new value each time tokens are claimed and only allowing claimToken to succeed if the public key has not been previously successfully used to claim tokens.