Open problem: improving stealth addresses

Stealth addresses in their most basic form work as follows:

  • Every recipient publishes an elliptic curve point P (they know the corresponding private key p)
  • If I want to send a payment to you, I generate a random value r, and I send the payment to an address with the public key P * r (I can generate the address locally)
  • I tell you r offline so you can claim the funds using the private key p * r

This allows paying a recipient without the public learning even that the recipient has been paid (think of the recipient’s key P as being publicly associated with some real-world identity, eg. via ENS). However, this protocol has the downside that some offline channel is required to learn r. One option is to encrypt r with P and publish this to the blockchain, which solves the problem but it comes at an efficiency cost: the recipient now has to scan through all stealth transactions to learn about any payments that are for them.

Some of the proposals in the above link can solve this problem by assuming that the recipient knows which sender will send them funds, but this is not always the case; sometimes, the sender may even want to be anonymous.

The challenge is: can we improve these protocols in such a way that reduces the scanning overhead for the recipient? The approach above has ~64 bytes and one elliptic curve multiplication per transaction in the anonymity set; can we do better?

There are information-theoretic arguments that show some limits: there must be at least O(N) information that the total set of recipients must listen to, as it must somehow contain for every recipient the information of whether or not they received a transaction. If each sender only modifies O(1) elements in this information, then the recipients would have to do an O(N)-sized scan, or else the senders would have to know which portion of the data the recipient is scanning, which can be used to detect transactions that are more likely going to the recipient.

Note that enlisting off-chain actors to perform complicated work (eg. updating the entire dataset after each transaction) to assist the recipients is acceptable.

Here is one fairly inefficient and complicated (but reasonably elementary in the mathematical sense) solution that seems to work:

  • Every recipient r picks a prime d_r and generates a hidden-order RSA group (ie. a modulus n_r = p_rq_r) such that the order of 2 is a multiple of d_r. They publish n_r. The list of all d_r values is published through a mixing protocol, so which d_i corresponds to which n_i is unknown. (note: this assumes phi-hiding)
  • For every recipient, publicly store a state variable S_i, an integer modulo n_i, which is initialized to 1.
  • To send a bit to some recipient r, perform the following procedure. Let n_1 ... n_k be the list of moduli. For every 1 \le j \le k, compute w = 2 ^ {d_1 * d_2 * ... * d_{j-1} * d_{j+1} * ... * d_k} (note that d_j is skipped). Set S_i \leftarrow S_i * w.
  • Note that the discrete log base 2 of S_r modulo d_r changes, but the discrete log base 2 or S_t modulo d_t for t \ne r does not change. Hence, only recipient r gets a message and other recipients do not, but no one other than r learns that r got a message. Recipient r can check for messages at any time by computing the discrete log using the factors (p_r, q_r) as a trapdoor.

This does involve a lot of work, though it could be outsourced and incentivized and verified via some ZK-SNARK-based plasma scheme (the dataset would be stored off-chain to avoid huge on-chain gas costs for rewriting it).

Another alternative is to use fully homomorphic encryption to outsource checking: use FHE to allow some third party to walk through the entire set of encrypted values, decrypt each value, and return the values that decrypt correctly. Given FHE as a “black box protocol” this is conceptually simpler; it also means that complicated constructions to store and maintain data off-chain are not necessary. However, the FHE approach may be more expensive.

Edit: this problem feels very conceptually similar to PIR (either the access variant or the search variant) but not quite the same; the main difference is that each recipient must only be able to read their own values.

1 Like

What I can think of is that, there are two directions to optimise the verification overhead of stealth address: 1) optimising the verification overhead of each tx, 2) reducing the number of txs to verify by filtering.
For 1), the optimisation space is very small, as scalar multiplication on an elliptic curve seems to be the cheapest trapdoor function already. For 2), there seems to be a trade-off between privacy and verification overhead.
Let me informally prove this statement below. I cannot guarantee it’s fully correct, and I’m happy to be proven wrong.

We shatr from proving the necessity of the randomness r for constructing stealth address.

Lemma 1: To receive money without revealing the receiver’s address, 1) the sender should always use a secret r and send r to the receiver privately, and 2) the receiver should always scan all txs on the blockchain to find txs going to himself.
Proof: Without the first condition, each stealth address can be mapped to a real address deterministically, which leaks the real address.The second condition is always necessary regardless of the stealth address. Consider payments without stealth address, the receiver should still compare his address with addresses in txs on the blockchain.

Then, we identify the security foundation of the stealth address, namely the CDH.

Lemma 2: To break the privacy guarantee of stealth address, one should break Computational Diffie-Hellman.
Proof: Easy from the security proof of the stealth address, i.e., prG = pR = Pr.

CDH relies on a trapdoor function. So far the most practical trapdoor function seems to be the elliptic curve scalar multiplication already. I don’t know any trapdoor function that is more lightweight than this. If there exists one, replacing EC scalar multiplication with this trapdoor can speedup verification directly.

Then, we consider the second possibility: filtering txs so that the receiver only needs to perform trapdoor functions on a subset of txs rather than all txs.

Here is a simple solution. In a nutshell, each tx attaches a short prefix of the receiver’s PK, and the receiver only needs to run trapdoor functions over txs with his PK’s prefix.
Each tx attaches an extra byte b equal to the first byte of the receiver’s PK. Upon a tx, the receiver checks whether his PK’s first byte equals to this tx’s b. If no, then this tx is not for the receiver. If yes, the receiver further computes the trapdoor function to see whether this tx is really for himself.

This allows the receiver to run trapdoor functions on \frac{1}{16} of all txs only.
However, the privacy downgrades for 16 times in the meantime, as the search space narrows down for 16 times.

It’s easy to see that, given a fixed trapdoor function, there is a trade-off between privacy and verification overhead.
Less verification overhead -> fewer txs to verify using trapdoor function -> fewer txs to search for identifying the receiver.

Yeah I agree the linear privacy / efficiency tradeoff exists and can be exploited. I do think there may be fancier tricks that let us go down from 1 ECsig per transaction (in the anonymity set) to something closer to the theoretical minimum of a few bits per transaction though.

Then we should eliminate all asymmetric crypto operations. Consider using something like one-time address scheme. Assuming Bob wants to transfer 1ETH to Alice.

  • Alice chooses a random string x
  • Alice constructs a transaction tx with input of 1ETH in Bob’s address and output of 1ETH in Alice’s one-time address H(alice\_addr || x)
  • Alice sends Bob tx, and Bob commits tx to the blockchain
  • Alice scans txs on the blockchain to see if there is a transaction with output H(alice\_addr || x)
  • When spending tx, Alice should show x

In short, this embeds a hashlock to the address, and Alice generates a one-time address scheme for receiving money everytime.
If Alice doesn’t want to construct tx herself, she can just send Bob H(alice\_addr || x) and let Bob do that.
If you want even more security, say anyone other than Alice can know who receives this money even with the knowledge of x, you can replace hash using a VRF. Only Alice can generate a proof. Unfortunately this requires EC operations again.

In this scheme, Bob cannot know Alice’s address, so cannot prove he sent Alice money. In addition, it only needs a hash function and Alice can scan txs efficiently, as she only needs to compare the one-time address with all addresses in existing txs (or just compare txid as she generated this tx).
The downside is that, creating receipts can be hard in this scheme.
Note that this approach requires hard forks. Not sure if there is any other design consideration.

To me stealth address may not need asymmetric crypto.
Homomorphism (of EC scalar multiplication) adds no more security than the scheme above.
In the original stealth address scheme,

  • Bob is responsible to choose r
  • Bob can send Alice either r or R
  • Bob still needs interaction with Alice, namely sending r/R

Bob sending R to Alice seems to hide the real value of r. This can somewhat prevent Alice from proving “she receives money from Bob”, as Alice should show her sk to prove this. I see no point of making “Alice receiving money from Bob” deniable and unprovable. Meanwhile, with r Bob can still prove he sent some money to Alice’s address by revealing r.

When spending tx , Alice should show x

One big challenge with the scheme is here; showing x allows anyone else to create a spending transaction and potentially front-run her.

Additionally, third parties can’t generate stealth addresses by themselves; Alice has to generate the address for them, so it doesn’t quite fit into the same pattern.

One big challenge with the scheme is here; showing x allows anyone else to create a spending transaction and potentially front-run her.

The output is hold by Alice. How can others create a transaction spending this money without knowing Alice’s secret key?

Additionally, third parties can’t generate stealth addresses by themselves; Alice has to generate the address for them, so it doesn’t quite fit into the same pattern.

Like I said, Alice (the receiver) can be the one who creates transactions for Bob (the sender). And what do you mean by “third party” here? There seems to only have sender Bob and receiver Alice.

Ah sorry, I mean Bob can’t perform the entire procedure offline, and it requires interaction from Alice. That’s the property I was trying to achieve.

I see. Indeed Bob needs to wait for Alice to send the transaction to him. If we don’t want Bob to reveal Alice’s identity, then this is inevitable.
To make this protocol non-interactive (for Bob), what we can do is to let Bob choose the random number x, construct/commit a transaction with output H(alice\_addr || x), and sends x to Alice. This achieves the same security guarantee as the original stealth address, yet minimises Alice’s scanning overhead.