[Bitcoin-development] Stealth Addresses
* Abstract A Stealth Address is a new type of Bitcoin address and related scriptPubKey/transaction generation scheme that allowers payees to publish a single, fixed, address that payors can send funds efficiently, privately, reliably and non-interactively. Payors do not learn what other payments have been made to the stealth address, and third-parties learn nothing at all. (both subject to an adjustable anonymity set) * Acknowledgments Credit goes to ByteCoin for the original idea.(1) Gregory Maxwell, Adam Back, and others on #bitcoin-wizards contributed valuable input on the implementation. Finally thanks goes to Amir Taaki for input on the general idea of stealth addresses and use-cases. * Background Viewed generally a Bitcoin address is a mechanism by which a payee instructs a payor to create a transaction such that the payee can spend one or more of the transaction outputs. Of course, typically the address is simply the hash of a pubkey, and the mechanism by which the funds are made available to the payee is to simply create a scriptPubKey of the following form: DUP HASH160 pubKeyHash EQUALVERIFY CHECKSIG The problem however is address reuse: it is convenient for payees to give one or more payor a single address and use it multiple times for various purposes. This results in all those payments becoming trivially linkable to each other by an attacker - a threat not only to the privacy of the user, but also to all users of Bitcoin.(2) BIP32 hierarchical deterministic wallets are frequently proposed as a solution. Now an address is a chain code and the mechanism by which a scriptPubKey is generated is to derive a one-time-use pubkey from that chain code and some index i. However, this quickly runs into two main problems: 1) Lack of privacy: While someone not in possession of the address can't link payments together, someone who is can. 2) State: If the index is not to be re-used wallets must either maintain per-address state, or somehow query for already used indexes, or somehow generate them in a sufficiently small range that the payee can recover the indexes. All these solutions are problematic. A good example of where the BIP32-derivation solutions fails come up at the Dark Wallet Hackathon where it was suggested by the author that for the purpose of securing person-to-person payments OpenPGP public keys and X.509 certificates be extended with a new user-id field containing a Bitcoin address. Wallet software could then use either certificate system to ensure funds were being sent to the intended recipients - essentially a non-interactive way of solving what the BIP70 payment protocol solves interactively. Of course, without stealth addresses the scheme would likely have little or no privacy. * Requirements 1) Generated scriptPubKey must be globally unique 2) Must be only spendable by payee 3) scriptPubKey and associated transaction must be indistinguishable to third-parties from other transactions in some anonymity set. 4) Method must be fully deterministic and funds recoverable from a wallet seed and blockchain data for both payee and payor. 5) Funds must be efficiently recoverable by payee with reasonable, and configurable, computation and bandwidth costs. 6) Must be compatible with CoinJoin/Must not leak information to payee about what txins were used to pay them. 7) Must be compatible with multisig-protected wallets. 8) Must not make assumptions about txin scriptSig form. 9) Must be possible to prove to third parties that payment was made in accordance to instructions without revealing any other information. ** Payment Reliability Schemes for making payments by transmitting nonces to the recipient through some other medium, such as Bitmessage, were discussed at the Dark Wallet Hackathon. However using any medium but the blockchain itself for the communication means that the reliability of the payment getting to the recipient is less than that of a standard transaction. For instance Bitmessage nodes only keep messages for two weeks. We decided that anything less than reliable atomic transactions was unacceptable. * Applying encryption to payments, simple explanation Using Elliptic curve Diffie-Hellman (ECDH) we can generate a shared secret that the payee can use to recover their funds. Let the payee have keypair Q=dG. The payor generates nonce keypair P=eG and uses ECDH to arrive at shared secret c=H(eQ)=H(dP). This secret could be used to derive a ECC secret key, and from that a scriptPubKey, however that would allow both payor and payee the ability to spend the funds. So instead we use BIP32-style derivation to create Q'=(Q+c)G and associated scriptPubKey. As for the nonce keypair, that is included in the transaction in an additional zero-valued output: RETURN P The payee recovers the funds by scanning the blockchain for candiate P's in transactions, regenerating the scriptPubKey, and finally checking if any txouts in the
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
On Sun, Jan 05, 2014 at 07:43:58PM +0100, Thomas Voegtlin wrote: Hello and happy new year to this mailing list! Thank you Mark for the incredible work you've been doing on this. I am following this very closely, because it is of primary importance for Electrum. I have written a Python-levelDB implementation of this UTXO hashtree, which is currently being tested, and will be added to Electrum servers. Along the lines of my recent post on blockchain data: Is it going to be possible to do partial prefix queries on that tree? Also have you considered creating per-block indexes of all scriptPubKeys, spent or unspent, queryable via the same partial prefix method? I too believe that BIPs should define interoperability points, but probably not implementation details. For the UTXO hashtree, this means that a BIP should at least specify how the root hash is constructed. This might be the only thing that needs to be specified. However, I see no pressing issue with writing a BIP; it might be preferable to implement and test different options first, and learn from that. It'd be very good to test this stuff thoroughly on Electrum first and get a feel for the performance and usability before any soft-fork to make it a miner commitment. Similarly a C++ implementation should be simply added to Bitcoin Core as a bloom filter replacement and made available over the P2P network. -- 'peter'[:-1]@petertodd.org 09bc28e08b41a74801c5878bf87978c2486aee7ed8a85778 signature.asc Description: Digital signature -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 01/06/2014 10:13 AM, Peter Todd wrote: On Sun, Jan 05, 2014 at 07:43:58PM +0100, Thomas Voegtlin wrote: I have written a Python-levelDB implementation of this UTXO hashtree, which is currently being tested, and will be added to Electrum servers. Along the lines of my recent post on blockchain data: Is it going to be possible to do partial prefix queries on that tree? There's really two tree structures being talked about here. Correct me if I'm wrong Thomas, but last time I looked at your code it was still implementing a 256-way PATRICIA trie, correct? This structure lends itself to indexing either scriptPubKey or H(scriptPubKey) with approximately the same performance characteristics, and in the Ultimate blockchain compression thread there is much debate about which to use. In the process of experimentation I've since moved from a 256-way PATRICIA trie to a bitwise, non-level-compressed trie structure - what I call proof-updatable trees in the BIP. These have the advantage of allowing stateless application of one proof to another, and as consequence enable mining mempool operations without access to the UTXO set, so long as proofs are initially provided in the transaction block wire format. The disadvantage is that performance is closely tied to key length, making H(scriptPubKey) the much more desirable option. I'm sure you see that as an advantage, however :) Also have you considered creating per-block indexes of all scriptPubKeys, spent or unspent, queryable via the same partial prefix method? This would be quite easy to do, separate from the UTXO structure but using the same trie format. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.14 (GNU/Linux) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJSy0iFAAoJEAdzVfsmodw434MQAIA/fDYT7SfMtfLEgDQKhXCn slRqFEx/HXjvgHHSYnbr9V+8LrGzNvT2ImebbV9ge8VlziAFNGIUq2EYhFs4kHWu GVm9aL8Jj/27SvM0tRwr9n2XIifKOh2sVINAjbv+UwPv/O+cULU95/b53DEF6aqI OWxioOR50TPe4t9AevAGVypNLm1DsyDdymhO9xyBN92xGTNj5QKL5hHG3kcsLIl1 7KaxO0w4UC2sdSGj9FeyH1b0zYg8FlzjJHc1CUshHwUwyYo8LRJtRypL5lrayERg Er/kIGEDovcenNBW8G79l+8VKPfB/lMTssT2pDiQL+1e1fg46CIQxHSyap2JSFTE jgleRk/+1NK/ZjOQ8dEBPZK3TE1WY3qlm/ekjG/8W5kXqcxzFBoAkeBNXuJ/8UMi mKe+DTmbp0xnvLO1p+hpugXKfrQSpcFL+ZvJHlFS1lz7O1N3WvuDCNP9El+L6ueM nFzjr1NTnX0z4vYtscI7qBKVqUrB7Z84c3O/lSYpw4Jilxl4trzV4cn7+AF7KWGM ktR9JJeIoNcJ2Zx4EpRp6OSwhtLkWZyLpPnidQ2p6ev2ytXpTpGsW/i5XS2w57UD 2IG5E0Q7Xzvd58lI/YollWQcagVOZdyzYXa+wVZoFQ6gLF47andpUmtUJOhI7gxv T/rWhPhkTMUn8TdvUcV/ =N9zM -END PGP SIGNATURE- -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
Le 07/01/2014 01:21, Mark Friedenbach a écrit : -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 01/06/2014 10:13 AM, Peter Todd wrote: On Sun, Jan 05, 2014 at 07:43:58PM +0100, Thomas Voegtlin wrote: I have written a Python-levelDB implementation of this UTXO hashtree, which is currently being tested, and will be added to Electrum servers. Along the lines of my recent post on blockchain data: Is it going to be possible to do partial prefix queries on that tree? There's really two tree structures being talked about here. Correct me if I'm wrong Thomas, but last time I looked at your code it was still implementing a 256-way PATRICIA trie, correct? This structure lends itself to indexing either scriptPubKey or H(scriptPubKey) with approximately the same performance characteristics, and in the Ultimate blockchain compression thread there is much debate about which to use. You are right. The 256-way branching follows from the fact that the tree was implemented using a key-value database operating with byte strings (leveldb). With this implementation constraint, a different branching would probably be possible but wasteful. My recent code creates one leaf per unspent, and uses 56-byte keys built as: H(scriptPubKey) + txid + txpos (This is not pushed yet, it needs cleanup. Previous code created one leaf per address) Partial prefix queries are possible with database iterators. In the process of experimentation I've since moved from a 256-way PATRICIA trie to a bitwise, non-level-compressed trie structure - what I call proof-updatable trees in the BIP. These have the advantage of allowing stateless application of one proof to another, and as consequence enable mining mempool operations without access to the UTXO set, so long as proofs are initially provided in the transaction block wire format. I see the advantage of doing that, but this looks really far-fetched.. My understanding is that it would require a complete change in the way clients and miners work. Could such a change be brought iteratively? -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
