public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Peter Todd <pete@petertodd.org>
To: Jeremy Spilman <jeremy@taplink.co>
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Stealth Addresses
Date: Tue, 14 Jan 2014 07:10:51 -0500	[thread overview]
Message-ID: <20140114121051.GA2583@savin> (raw)
In-Reply-To: <op.w9ne31oqyldrnw@laptop-air.hsd1.ca.comcast.net>

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

On Mon, Jan 13, 2014 at 03:20:15PM -0800, Jeremy Spilman wrote:
> On Mon, 13 Jan 2014 13:27:52 -0800, Peter Todd <pete@petertodd.org> wrote:
> 
> >There is a catch however: if you need the prefix to be against
> >H(scriptPubKey) rather than scriptPubKey directly the sender needs to
> >grind the OP_RETURN output at 2^len(prefix) cost. Fortunately that
> >grinding can be done with hash operations rather than ECC - even if we
> >needed 32-bit prefixes eventually computing 32-bit hash collisions is
> >plausible, and more reasonable 8-bit is quite doable now.
> 
> I'll be updating my test code to support a prefix on the OP_RETURN
> TxOut, for either where we expect to have an index on scriptPubKey,
> or where we have an index on H(scriptPubKey) and have to grind with
> a nonce.
> 
> Where do we say what prefix we are targeting, or how many bits
> should match with Q? I assume the only place to communicate this,
> dare I say it, is in the address string.

That's exactly where you need to put it.

Incidentally a prefix nonce, either direct or grind-style, is a bit of a
privacy leak by suggestion how long the prefix was in the original
stealth address. Code should be written such that grinding routines
start at a random nonce, and nonces of any length are accepted. The
easiest way to do that is to just stick the grind nonce at the end after
the 33 bytes of pubkey.

I dunno yet what hashing algorithm to target for grinding. I'd assume
SHA256^2 on the basis that it's identical to what the merkle tree uses
and thus will have the same security properties in a committed index,
but I can see people pushing for the shorter 20-byte HASH160 too.

> Also, for symmetric encryption of P in the OP_RETURN TxOut using a
> key H(Q), what cipher did you have in mind? Since P is ephemeral and
> random, I don't follow, why does encrypting it 'gives a slightly
> larger anonymity set'?

The idea was to make the anonymity set include other uses of OP_RETURN
txouts, however Gregory Maxwell pointed out that it'd easily lead to a
much reduced anonymity set because someone could trial decrypt the
encrypted P and check if it was a valid pubkey. If you encrypted the
full 33 bytes that'd be a total disaster - only 1/256 candidate stealth
keys would work. There are ways to do it right, but it's tricky and
there may be other attacks I don't know about, so I'm inclined to just
drop that idea for now unless a professional cryptographer wants to take
it on.

> You made an interesting point in the original post that payer should
> hold onto their ephemeral privKey 'e' corresponding to pubKey P if
> they need to later prove the payment was actually sent to Q.

Yup. You can even use that pubkey to disambiguate/prove payments with
Timo Hanke's pay-to-contract ideas by deriving it from some root and a
contract hash.

Conversely Amir Taaki pointed out on the unsystem list that once a nonce
is agreed on, it can be used directly with BIP32 derivation so that
future payments don't have to use an OP_RETURN txout. Interesting idea,
although I worry that the statelessness advantage of stealth payments
gets lost if you do that. Probably best to look at that one after an
initial implementation happens and we get some experience with them in
the real world - adding that can be done in a backwards compatible
fashion.

> Finally, I hope you can take a look at the Gist and sample Test-Net
> TXs I sent out this morning. I just went back and re-read your
> original post, and compared to what I implemented there are some
> differences, I'd like to make sure you think it's on track.

Will do.

-- 
'peter'[:-1]@petertodd.org
0000000000000001420349f2276e53e5b087faea67c7c40aa12383c416067364

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

  parent reply	other threads:[~2014-01-14 12:11 UTC|newest]

Thread overview: 88+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-01-06 12:03 [Bitcoin-development] Stealth Addresses Peter Todd
2014-01-08 10:20 ` Jeremy Spilman
2014-01-10 10:20   ` Peter Todd
2014-01-10 11:28     ` Drak
2014-01-10 12:00       ` Peter Todd
2014-01-12 10:33     ` Jeremy Spilman
2014-01-12 12:51       ` Mike Hearn
2014-01-12 18:20         ` Jeremy Spilman
2014-01-12 18:26           ` Mike Hearn
2014-01-13  9:13             ` Jeremy Spilman
2014-01-14 14:15               ` Peter Todd
2014-01-14 17:54                 ` Odinn Cyberguerrilla
2014-01-12 21:18       ` Gavin Andresen
2014-01-13  9:52         ` Gregory Maxwell
2014-01-13 10:39           ` Mike Hearn
2014-01-13 13:37             ` Roy Badami
2014-01-13 15:58               ` Mike Hearn
2014-01-13 20:11                 ` Roy Badami
2014-01-14 22:53                 ` Roy Badami
2014-01-15  0:19                   ` Drak
2014-01-15 20:22                     ` Ben Davenport
2014-01-15 20:38                       ` Gregory Maxwell
2014-01-15 20:44                         ` Jeff Garzik
2014-01-15 22:38                           ` [Bitcoin-development] Static addresses on chains encouraging address *RE* use Troy Benjegerdes
2014-01-15 23:01                           ` [Bitcoin-development] Stealth Addresses Mike Hearn
2014-01-15 23:04                           ` Roy Badami
2014-01-15 23:07                             ` Jeff Garzik
2014-01-15 23:17                               ` Roy Badami
2014-01-15 23:19                                 ` Roy Badami
2014-01-15 23:09                           ` [Bitcoin-development] unlinakble static address? & spv-privacy (Re: Stealth Addresses) Adam Back
2014-01-16  1:02                             ` Jeremy Spilman
2014-01-16  1:32                               ` Gregory Maxwell
2014-01-18 17:44                                 ` Troy Benjegerdes
2014-01-18 20:25                                   ` Christophe Biocca
2014-01-20 11:11                                   ` Peter Todd
2014-01-21  4:00                                 ` Jeremy Spilman
2014-01-24  9:17                                   ` Peter Todd
2014-01-16 11:42                               ` Adam Back
2014-01-16 18:19                                 ` Troy Benjegerdes
2014-01-16  0:05                           ` [Bitcoin-development] Stealth Addresses Jeremy Spilman
2014-01-16  0:10                             ` Gregory Maxwell
2014-01-16  0:24                             ` Mark Friedenbach
2014-01-16  0:44                             ` Eric Martindale
2014-01-16  6:26                               ` Gary Rowe
2014-01-16  9:48                                 ` Wladimir
2014-01-16  1:16                             ` Odinn Cyberguerrilla
2014-01-16 10:14                             ` Drak
2014-01-16 10:19                               ` Mike Hearn
2014-01-16 11:12                               ` [Bitcoin-development] reusable address privacy problems & fuzzy bait limitations (Re: Stealth Addresses) Adam Back
2014-01-16 21:28                             ` [Bitcoin-development] Stealth Addresses Peter Todd
2014-01-17  2:30                               ` Johnathan Corgan
2014-01-17  3:13                               ` Jeremy Spilman
2014-01-17  7:49                               ` Drak
2014-01-17  9:15                                 ` Mike Hearn
2014-01-17  9:19                                   ` Mark Friedenbach
2014-01-17  9:23                                   ` Natanael
2014-01-17  9:59                                   ` Drak
2014-01-17 20:16                                     ` Cameron Garnham
2014-01-17 14:46                                   ` Peter Todd
2014-01-17 19:21                                     ` Ben Davenport
2014-01-18  4:55                                       ` Alan Reiner
2014-01-18  5:09                                         ` Gregory Maxwell
2014-01-18 23:12                                           ` Jeremy Spilman
2014-01-18 23:50                                             ` Gregory Maxwell
2014-01-20 11:08                                             ` Peter Todd
2014-01-13 19:53               ` Roy Badami
2014-01-13 19:57                 ` Mike Hearn
2014-01-13 20:01                   ` Roy Badami
2014-01-13 19:40           ` Roy Badami
2014-01-13 19:44             ` Drak
2014-01-13 19:59               ` Alan Reiner
2014-01-13 20:10                 ` Gregory Maxwell
2014-01-13 20:15                   ` Peter Todd
2014-01-13 22:02                   ` Jeremy Spilman
2014-01-14 14:19                     ` Peter Todd
2014-01-14 19:12                       ` Jeremy Spilman
2014-01-14 20:48                         ` Peter Todd
2014-01-14 21:51                         ` Adam Back
2014-01-14 22:34                           ` Jeremy Spilman
2014-01-13 20:14                 ` Peter Todd
2014-01-13 20:41                   ` Alan Reiner
2014-01-13 20:47                     ` Gregory Maxwell
2014-01-13 21:02                     ` Roy Badami
2014-01-13 21:15                       ` Alan Reiner
2014-01-13 21:27                         ` Peter Todd
     [not found]                           ` <op.w9ne31oqyldrnw@laptop-air.hsd1.ca.comcast.net>
2014-01-14 12:10                             ` Peter Todd [this message]
2014-03-06 12:23 ` Dan Carter
     [not found] <mailman.417890.1389952750.21953.bitcoin-development@lists.sourceforge.net>
2014-01-17 12:16 ` joseph

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=20140114121051.GA2583@savin \
    --to=pete@petertodd.org \
    --cc=bitcoin-development@lists.sourceforge.net \
    --cc=jeremy@taplink.co \
    /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