Let's start with the assumption that the ability to identify a set of
outputs as a stealth payment reduces the stealthiness of the payment. One
can argue the *degree* to which that makes a difference in real privacy, but
it of course makes a difference.

There are two aspects to detecting the existence of a potential stealth
payment. The pattern of transaction outputs (metadata before spend):

* out #1 - metadata for spend A
* out #2 - stealth spend A
* out #3 - metadata for spend B
* out #4 - stealth spend B
...

https://wiki.unsystem.net/en/index.php/DarkWallet/Stealth#Transaction_format

And the specific format of the outputs:

-> RETURN <version:1=6> <nonce:4> <P:33>
-> DUP HASH160 <pkh:20> EQUALVERIFY CHECKSIG

https://wiki.unsystem.net/en/index.php/DarkWallet/Stealth#Actual_output_form
at

The spend (#2) output looks exactly like a very/most typical non-stealth
spend, which is great. The metadata output (#1) seems problematic in that it
can be easily used to identify all stealth payments, with what would seem to
be a very small false positive rate.

The two things that identify the metadata as probably stealth are length (37
bytes) and a version byte (0x06). The odds of a 38 byte RETURN starting with
0x06 and immediately preceding the required form of the spend script and
*not* being a stealth payment seem very low.

This is of course a performance optimization. We can index this pattern in
obelisk. However, so can everyone else.

Ideally we want stealth payments to look exactly like other outputs, with no
way to filter out the bulk of other information on the blockchain apart from
the prefices that people are advertising in their stealth addresses and
using in scans. We could improve privacy by eliminating the version byte,
the ordering requirement, the fixed length (by adding a random length of
data to the metadata RETURN) and even encouraging other unused random RETURN
output in the transaction. By retaining a pattern of 37 bytes minimum and at
least two outputs there is still some ability to narrow an attack, but this
pattern would be so commonplace as to effectively eliminate the value of
such an effort.

Also, it would seem that prefix search for non-stealth payments would
eliminate any value gained in this optimization.

So is the performance optimization worth the reduction in privacy, for a
system that is designed specifically for privacy?

Thanks to Peter Todd for pointing out the issue of the stealth version byte
(and of prefix search for non-stealth) to me some time ago.

e