[Bitcoin-development] reusable address privacy problems & fuzzy bait limitations (Re: Stealth Addresses)

[Adam Back <adam@cypherspace.org>]

On Thu, Jan 16, 2014 at 10:14:24AM +0000, Drak wrote:
>   On 16 January 2014 00:05, Jeremy Spilman <[1]jeremy@taplink.co> wrote:
>   > Might I propose "reusable address".
>
>   The problem is all addresses are reusable and to an average user,
>   addresses are already reusable so there is little to distinguish the
>   address format.
>   It might be better to call it a "public address" in common terminology.

Yeah I called my variant "(unlinkable) public" but I also think I prefer
Jeremy's "reusable address" which has the added bonus of being yet another
implied admonishment not to reuse the non-reusable ones :)

Anyway my primary concern so far is that the reusable addresses/(unlinkable)
public addresses are actually worse for privacy than SPV bloom mechanism by
any reasonable definition.  So I think we have some work to do yet, on a
tough problem which may not have an efficient index precomputable solution
(or a solution period.)  I would also have been promoting this as an
alternative solution to bloom privcy mechanism and address-reuse, if I
could've found a mechansim for the unlinkable public proposal...

Whats different so far I think is that Peter just went with it anyway
despite that problem, where as I put it in the pile of interesting but not
quite workable for privacy reasons ideas.  (Bearing in mind that my bloom
bait concept is the same as the prefix concept so I had functional
equivalence).  The additional feature of Peter's variant is to stealthify
the payment, which I do think is a useful additioanl consideration, however
as I said I think its fair to say it so far largely fails to do that,
because the exposed P parameter.  (And using the input instead of the P
parameter breaks CoinJoin, which is also thereby damaging to privacy).

So also about Greg Maxwell's improved prefix/bloom bait (lets call it fuzzy
bloom bait), while I agree that H(nonce)[rand(32)] ^ prefix is an
interesting incremental improvement, over raw bloom bait/prefix (with an
example 8-bit prefix, and [] being byte index, ^=xor), it is
index-precomputable, but it still publicly allows statistical elimination
which is still nearly as dangerous in lieu of the remarkable success people
have had doing statistical network flow analysis.  ie with probability
(255/256)^32=88% it eliminates you as a payee of any given reusable payment. 
(And that effect remains with any parameter set and conflicts with bandwidth
efficiency for the requestor - ie lower elimination probability seems
unavoidably to imply higher false positive match, right down to the point of
downloading the entire set, giving with 0 probability).

Thinking-hats time people.

(As I said I still like reusable-addr for full-node recipient scenarios.)

Adam