public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Peter Todd <pete@petertodd.org>
To: Adam Back <adam@cypherspace.org>
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Bloom bait
Date: Fri, 6 Jun 2014 12:46:39 -0400	[thread overview]
Message-ID: <20140606164639.GB14891@savin> (raw)
In-Reply-To: <20140606104543.GA31085@netbook.cypherspace.org>

[-- Attachment #1: Type: text/plain, Size: 4080 bytes --]

On Fri, Jun 06, 2014 at 12:45:43PM +0200, Adam Back wrote:

(changed subject line as this discussion has nothing to do with
NODE_BLOOM)

> As I recall prefix brute forcing was a bit twiddle saving, ie searching for
> EDH key that has the users public prefix.  That does not improve privacy
> over an explicit prefix, it saves a byte or so at the expense of average 128
> EDH exchanges to send and provides also some probably relatively ineffective
> plausible deniability by enabling the transaction to be indistinguishable
> from some other (not very common) types of transaction.

I think you should re-read my original proposal; there's a whole host of
misunderstandings above, for instance I have no idea where you got the
idea that it has anything to do with "saving a byte" came from, or where
the number 128 came from.

> >don't do that they have privacy equal or better than bloom filters, but
> >with better scalability.
> 
> either its full node only where prefixes are not used, which is less
> scalable than bloom; or prefixes are used explicitly or implicitly
> (brute-force) and either way privacy is weakened by the extra correlation
> hook provided by elimination from the network graph of payments with
> mismatched prefixes.

Again, you have a misunderstanding. Both bloom filters and prefix
filters are just ways of giving a peer a probabalistic filter to match
transactions against. Where they differ is that bloom filters has O(n)
scaling, where n is the size of a block, and prefix filters have O(log n)
scaling with slightly(1) higher k. Again, if you *don't* use brute forcing
in conjunction with prefixes they have no different transactional graph
privacy than bloom filters, but the better scalability lets you do
things like split your queries across multiple peers that give you
better protection against hostile nodes.  Additionally prefix filters
are compatible with future miner committed indexes to make the data
authenticated.

1) see Amir's experience implementing prefix lookup in Obelisk

> We need to consider the two types of privacy involved.  Privacy from the
> full node an SPV client is relying on to find its payments, vs privacy from
> analysis of the public transaction graph.

Agreed

> The latter is more damaging.

Maybe! If adversaries are operating a significant fraction of the peers
you are connecting to the current design of bloom filters + HD wallets
results in situations where those adversaries have better transactional
graph information than the alternative.

> Better to design for privacy against future analysis of
> public info, than
> privacy by argument to select non-hostile nodes.  Tor has changed recently
> to account for the fact that chosing fresh random nodes is actually
> worse. ie you have a probability of identity/address identification
> per route/node,
> and repeatedly selecting routes/nodes just cumulatively increases the chance
> you'll be identified.  Better to pick a random node, identify it and stick
> to it and hope you chose well.

That's basically what Electrum and Obelisk already do - by default you
connect to a relatively small set of blockchain data servers operated by
well known people and use the same server repeatedly.

Applying that to the P2P network however is tricky as there is a huge
amount of churn in the nodes:

    #bitcoin-dev/14/06/14-06-06.log:11:18 < hearn> bitcoinj can't use
    [service bits] as it relies on DNS seeds and that is unlikely to change
    any time soon due to the general churn rate in the network making it
    hard to bootstrap quickly using just remembered sets of IPs.

> Maybe other simpler, but yes there was the proof of concept that the math
> exists in the form of the weil pairing.
> 
> https://bitcointalk.org/index.php?topic=431756.new

I know, where can I find running code? Remember that a bug can easily
lose thousands of dollars worth of Bitcoins.

-- 
'peter'[:-1]@petertodd.org
00000000000000001d2af1653c415b7801ce4c9b18ac7e87bef597e652b203e6

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

  reply	other threads:[~2014-06-06 16:45 UTC|newest]

Thread overview: 20+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-06-06  8:19 [Bitcoin-development] NODE_BLOOM service bit Peter Todd
2014-06-06  8:48 ` Adam Back
2014-06-06  9:03   ` Gregory Maxwell
2014-06-06  9:11     ` Peter Todd
2014-06-06  9:04   ` Peter Todd
2014-06-06 10:45     ` Adam Back
2014-06-06 16:46       ` Peter Todd [this message]
2014-06-06 16:58         ` [Bitcoin-development] Bloom bait Gregory Maxwell
2014-06-06 17:05           ` Peter Todd
2014-06-06 17:10             ` Gregory Maxwell
2014-06-06 17:45               ` Peter Todd
2014-06-07 11:22                 ` Mike Hearn
2014-06-07 19:44                   ` Alan Reiner
2014-06-08 21:45                     ` Peter Todd
2014-06-10 10:41                       ` Mike Hearn
2014-06-08 21:35                   ` Peter Todd
2014-06-10 10:38                     ` Mike Hearn
2014-06-10 13:02                       ` Jeff Garzik
2014-06-10 17:08                       ` Peter Todd
2014-06-11  8:57                         ` Mike Hearn

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20140606164639.GB14891@savin \
    --to=pete@petertodd.org \
    --cc=adam@cypherspace.org \
    --cc=bitcoin-development@lists.sourceforge.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox