Print Page - What is the status of the stealth addresses?

Title: What is the status of the stealth addresses?
Post by: piotr_n on April 30, 2014, 01:11:13 PM

I'm kind of bored recently and even though I was never very enthusiastic about the stealth addresses, it still seems to be the most exciting feature to add to my wallet software.
I know that there are all kind of mailing lists with less and more outdated specs flying around, but since I don't monitor them, could anyone please update me on the most recent status?

Today I have been playing with DarkWallet a bit and from what I see each wallet there has by default one stealth address assigned to it.
I also figured out what this address represents.
For all I know, there are two public keys - one is to encrypt the message (nonce or whatever it is called), while the other one is there to calculate the actual destination for the coins that are being spent.

So, for instance, I got an address vJmyoyfHgvkW2fRbqpANQircWiWDFMHtzyUxbcGsnUCX6z1jEjfArypDBNMeQdmsczkLVoSwYRZ5pS8 YAxxQY7Q2m8SUXB2sZWjB6q - it decodes to:

Code:

2a - version
00 - options
03b5ca63d7bda5b8f70a68864fafa0587e446c52be23150da2b95ad9d6f3e6f71f - scan_pubkey
01 - number of spend keys
0351bec154c01c4f26794da8b0a3019b163b633ea933387f48288ed35cbc833f53 - spend pubkey 1
01 - number sigs
00 - prefix_length
b3fe7b1a - standard checksum of the address

Now, I want to extend my wallet so it would be able to send coins to such an address.
How do I build the transaction?

Is there any spec that I can read?
Any actually working code that makes a transaction which sends money to such an address?

Title: Re: What is the status of the stealth addresses?
Post by: sickpig on April 30, 2014, 07:42:17 PM

Quote from: piotr_n on April 30, 2014, 01:11:13 PM

Code:

2a - version
00 - options
03b5ca63d7bda5b8f70a68864fafa0587e446c52be23150da2b95ad9d6f3e6f71f - scan_pubkey
01 - number of spend keys
0351bec154c01c4f26794da8b0a3019b163b633ea933387f48288ed35cbc833f53 - spend pubkey 1
01 - number sigs
00 - prefix_length
b3fe7b1a - standard checksum of the address

https://en.bitcoin.it/wiki/Sx/Stealth
http://sx.dyne.org/

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on April 30, 2014, 09:05:01 PM

I tried that today but cannot get this sx tool to build on my Ubuntu.
So I cannot execute these commands.

Also I'm curious about the encryption part and how the actual transaction looks inside.
I guess there is some extra null output with this encrypted nonce.

I'm asking about a format of a stealth payment transaction - is such thing even defined yet?

Title: Re: What is the status of the stealth addresses?
Post by: Abdussamad on May 01, 2014, 04:29:45 AM

Quote from: piotr_n on April 30, 2014, 09:05:01 PM

I tried that today but cannot get this sx tool to build on my Ubuntu.
So I cannot execute these commands.

Yeah, common problem. Try this script instead:

https://github.com/mastercoin-MSC/install-msc/blob/master/res/install-sx.sh

Ref: https://bitcointalk.org/index.php?topic=259999.msg6099554#msg6099554

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 01, 2014, 09:03:47 AM

Quote from: Abdussamad on May 01, 2014, 04:29:45 AM

Quote from: piotr_n on April 30, 2014, 09:05:01 PM

I tried that today but cannot get this sx tool to build on my Ubuntu.
So I cannot execute these commands.

Yeah, common problem. Try this script instead:

https://github.com/mastercoin-MSC/install-msc/blob/master/res/install-sx.sh

Ref: https://bitcointalk.org/index.php?topic=259999.msg6099554#msg6099554

Thanks, but this one didn't solve it.
Other issues. Seems to need boost 1.49 when my OS has 1.46. After changing the script to use 1.46, still crashes on building getx_responder.lo

EDIT:
nvm, took me a few hours, but somehow managed to build it already.
but it doesn't even seem to support the "New stuff" so it doesn't really help me.

EDIT2:
Found it: https://wiki.unsystem.net/index.php/DarkWallet/Stealth
:)

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 01, 2014, 07:40:32 PM

OK. It seems that I have a proof of concept software that I am able to run and use as a reference.
Now, if someone could please advise me...
This function (that's javascrip from the darkwallet):

Code:

// Simple NAF (Non-Adjacent Form) multiplication algorithm
// TODO: modularize the multiplication algorithm
function pointFpMultiply(k) {
    if(this.isInfinity()) return this;
    if(k.signum() == 0) return this.curve.getInfinity();

    var e = k;
    var h = e.multiply(new BigInteger("3"));

    var neg = this.negate();
    var R = this;

    var i;
    for(i = h.bitLength() - 2; i > 0; --i) {
	R = R.twice();

	var hBit = h.testBit(i);
	var eBit = e.testBit(i);

	if (hBit != eBit) {
	    R = R.add(hBit ? this : neg);
	}
    }

    return R;
}

It seems to multiply this(x,y,z) point, by a big int k - to return R(x,y,z)

Non-Adjacent Form - right, that explains a lot! ;)
Except that I have no idea what it means :)

Anyway, such a function had not been used for anything else in Bitcoin before - had it?
I mean, I need to code it in, if I want my wallet to be able to send coins to stealth addresses - right?

Is there some simpler (less optimized) version of such a function?
One that would operate solely on big-int arithmetic, instead of this for/if/bit/add stuff?
Just so I'd be able to understand what it actually does and the actual math behind it.

Title: Re: What is the status of the stealth addresses?
Post by: caedes on May 02, 2014, 03:30:36 PM

The sx implementation uses an old spec, we just published some more information about how we do it in darkwallet:

https://bitcointalk.org/index.php?topic=592518.0

We have some test vectors in our unit tests, check the above link, i can provide you test vectors in a different format if you so prefer.

I would say is the status now is need to make a spec but it should be production ready (the stealth address idea), we have it working in real world and seems to work as advertised.

Title: Re: What is the status of the stealth addresses?
Post by: caedes on May 02, 2014, 03:33:10 PM

Quote from: piotr_n on May 01, 2014, 07:40:32 PM

OK. It seems that I have a proof of concept software that I am able to run and use as a reference.

Anyway, such a function had not been used for anything else in Bitcoin before - had it?
I mean, I need to code it in, if I want my wallet to be able to send coins to stealth addresses - right?

Is there some simpler (less optimized) version of such a function?
One that would operate solely on big-int arithmetic, instead of this for/if/bit/add stuff?
Just so I'd be able to understand what it actually does and the actual math behind it.

That's elliptic curve point multiplication, you should have a library in your language of preference taking care of that.

Title: Re: What is the status of the stealth addresses?
Post by: caedes on May 02, 2014, 05:05:38 PM

Also, bip32 code may be doing similar calculations.

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 03, 2014, 10:44:31 AM

Quote from: caedes on May 02, 2014, 03:33:10 PM

That's elliptic curve point multiplication, you should have a library in your language of preference taking care of that.

That is what I had initially thought, but the thing is that for the example test vector:

Code:

X = f46a67e20804f956a1ce64566d96a42658a9a7a4c9a0be924615bef881a4a3f2
Y = 3a8218cdf4156c60585f5721189289cc89500eab79480a109eb1d0684e560996
k = 84e5f7d329c3dab1160dbf9cb0b1a3c82e6058c06260f4101b1660b865ce98c5

... the JS function returns:

Code:

x = eb8d6a5c12e70b0d5e05336e9103318e89ca4445004afc3640d3e47e488a4d0f
y = 8fabd090eade40104431906d3bc0c25d988270aa017bfa8ce3707c0d72649571

while the EC multiplication k*(x,y) that I have here would return:

Code:

x = 61537944f9b1245a76be6bf1d49e5ea0aa44a9a4da657c7b04598c702b440db8
y = f96de684e701f3bc48ef2e86a2e9e0be122b741331b926023ab346a82e81b8e9

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 03, 2014, 02:17:36 PM

Quote from: piotr_n on May 03, 2014, 10:44:31 AM

Quote from: caedes on May 02, 2014, 03:33:10 PM

That's elliptic curve point multiplication, you should have a library in your language of preference taking care of that.

That is what I had initially thought, but the thing is that for the example test vector:
[...]

sorry, never mind - I was printing wrong values.
didn't realize that pub.x.x is not the actual x.
what a sucker I am :)

now everythign makes much more sense.

Title: Re: What is the status of the stealth addresses?
Post by: caedes on May 04, 2014, 05:04:48 AM

Quote from: piotr_n on May 03, 2014, 02:17:36 PM

now everythign makes much more sense.

Cool, keep us updated!

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 05, 2014, 02:34:42 PM

I'm still a bit confused, to be honest.
I wanted to use DW to send some money to my own stealth addresses, just to see how it works.
But my transactions have been pending for days already, so I am now trying to send it myself, using my own s/w.

Anyway, please explain me one thing. I have a stealth address with two public keys: scanKey and spendKey - I want to send some coins there.
So what I would do is:

1. I pick up a secret C - some random 32 bytes

2. Do I have to do anything with C here???

3. I calculate C*scanKey - and put it inside the first null-ouptut, like this:

Code:

6a2606 <4_random_bytes> <compressed(C*scanKey)>

4. I calculate C*spenKey - and use it in the next output (one that actually spends the coins):

Code:

76a914 <hash160(C*spenKey)> 88ac

5. I sign and broadcast the transaction.

In general it seems pretty clear, but the devil is in the details.
Obviously I want my txs to be compatible with the existing solution (not just with my own), so I have these questions:
1. Do I need to do anything with my random C, between point 1 and 3?
2. You have this StealthDH() function that takes X from a result of EC multiplication, prefixes it with 03 and then does sha256 on it - at which point is it actually used?
3. The 4 random bytes in point 3 - are they just random, or what?

Title: Re: What is the status of the stealth addresses?
Post by: dabura667 on May 05, 2014, 07:13:41 PM

Quote from: piotr_n on May 05, 2014, 02:34:42 PM

Code:

6a2606 <4_random_bytes> <compressed(C*scanKey)>

4. I calculate C*spenKey - and use it in the next output (one that actually spends the coins):

Code:

76a914 <hash160(C*spenKey)> 88ac

You are getting mixed up.

First let's see what you have to do first to send to a stealth address:

1. check the checksum! (convert from base58 to hex, strip last 4 bytes, SHA256 twice, compare first 4 bytes with checksum, if match then continue)
2. check if mainnet
3. check version byte (not used)
4. check N (number of keys for multisig)
5. check required number of sigs (for multisig)

6. create a new pub/priv keypair (lets call its pubkey "ephemkey" and privkey "e")
7. IF there is a prefix in the stealth address, brute force a nonce such that SHA256(nonce.concate(ephemkey)) first 4 bytes are equal to the prefix. IF NOT, then just run through the loop once and pickup a random nonce. (probably make the while condition include "or prefix = null" or something to that nature.
8. Once you have the nonce and the ephemkey, you can create the first output, which is

Code:

OP_RETURN <nonce:4bytes> <ephemkey:33bytes>

9. Now use ECC multiplication to calculate e*Q where Q = scan_pubkey and e = privkey to ephemkey and then hash it.
10. That hash is now "c". use ECC multiplication and addition to calculate D + (c*G) where D = spend_pubkey, and G is the reference point for secp256k1. This will give you a new pubkey. (we'll call it D')
11. Create a normal P2KH output spending to D' as public key.
12. make the tx with the two outputs from #8 and #11 and broadcast it. (Don't forget to create any change outputs you need!)

Edit: I forgot to say, if it is multisig, then repeat #10 for every spend_pubkey, A becomes A' B becomes B' etc... then take all the pubkeys from A' B' C' D' etc etc. and make a p2sh multisig address. Then in step 11 create normal P2SH output to multisig. so with multisig only #10 and #11 will change. everything else is same.

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 05, 2014, 08:03:07 PM

That's very useful - thanks!

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 06, 2014, 12:17:45 AM

I think it works. :)

Just one more question.

When you say "brute force a nonce such that SHA256(nonce.concate(ephemkey)) first 4 bytes are equal to the prefix" - what if the prefix is not 4 bytes long?

Title: Re: What is the status of the stealth addresses?
Post by: dabura667 on May 06, 2014, 02:56:45 AM

Quote from: piotr_n on May 06, 2014, 12:17:45 AM

If it is not than 4. The only difference is the first x bytes must match the prefix of a length x / 8 rounded up.

Also remember that prefix_length is in bits, so to get the number of bytes to compare you must take x / 8 rounded up.

Edit: sorry for all the edits, i just woke up...

Sorry last edit I swear.

Here's the function for comparing the hash with the prefix.

https://github.com/darkwallet/darkwallet/blob/42bb91761555c078f386be2ff6f61f7c033c60f0/js/util/stealth.js
Stealth.checkPrefix is the function.

The function at the very bottom is the loop to brute force the prefix.

Title: Re: What is the status of the stealth addresses?
Post by: genjix on May 06, 2014, 04:39:25 AM

https://wiki.unsystem.net/index.php/Install_entire_toolchain

https://wiki.unsystem.net/index.php/Sx/Stealth

https://wiki.unsystem.net/index.php/DarkWallet/Stealth

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 06, 2014, 08:30:36 AM

@dabura667
cheers.
so the prefix length cannot be bigger than 32 bits?
and if it was all 32 bits, but I could not find a matching nonce - what then? pick up a different "ephemkey"?

@genjix
yeah, I had gone through these specs.
none of them was even close to be as useful as one post from dabura667 :)

btw, building the tools on my old ubuntu 12.04 was a real fight.
first I needed gcc 4.7 (I had 4.6)
then leveldb version was apparently too old
and libbboost - I also had to upgrade this one to 1.49.
the biggest problem was that the errors I saw did not help much to diagnose the problems.
the second biggest: this version of ubuntu would not just upgrade any of these packages in a simple way.

Title: Re: What is the status of the stealth addresses?
Post by: ShadowOfHarbringer on May 06, 2014, 09:14:10 AM

Quote from: piotr_n on April 30, 2014, 01:11:13 PM

Code:

2a - version
00 - options
03b5ca63d7bda5b8f70a68864fafa0587e446c52be23150da2b95ad9d6f3e6f71f - scan_pubkey
01 - number of spend keys
0351bec154c01c4f26794da8b0a3019b163b633ea933387f48288ed35cbc833f53 - spend pubkey 1
01 - number sigs
00 - prefix_length
b3fe7b1a - standard checksum of the address

Offtopic: It is nice to finally see you taking matter in your own hands instead of walking around and complaining.

Respect.

Title: Re: What is the status of the stealth addresses?
Post by: genjix on May 06, 2014, 10:22:49 AM

Quote from: piotr_n on May 06, 2014, 08:30:36 AM

cmon man upgrade your ubuntu. that is super old! ubuntu 14 is a new LTS

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 06, 2014, 03:47:25 PM

Quote from: genjix on May 06, 2014, 10:22:49 AM

cmon man upgrade your ubuntu. that is super old! ubuntu 14 is a new LTS

It's because I usually don't upgrade something that works, especially an entire OS.
The only reason I upgraded WinXP to Win7 was that I needed a support for two graphic cards at the same time.

But I did listen to your advise and have upgraded it to 14.04.
The result is that I lost all my user accounts and all the apps, and now... I cannot build the tools again.
Not that I would not had expected it :)

Code:

  CXXLD    obworker
/usr/bin/ld: warning: libicuuc.so.48, needed by /usr/local/lib/libboost_regex.so, not found (try using -rpath or -rpath-link)
/usr/bin/ld: warning: libicui18n.so.48, needed by /usr/local/lib/libboost_regex.so, not found (try using -rpath or -rpath-link)
/usr/local/lib/libboost_regex.so: undefined reference to `u_charType_48'
/usr/local/lib/libboost_regex.so: undefined reference to `icu_48::Locale::~Locale()'
/usr/local/lib/libboost_regex.so: undefined reference to `icu_48::Collator::createInstance(icu_48::Locale const&, UErrorCode&)'
/usr/local/lib/libboost_regex.so: undefined reference to `u_digit_48'
/usr/local/lib/libboost_regex.so: undefined reference to `icu_48::Locale::Locale(icu_48::Locale const&)'
/usr/local/lib/libboost_regex.so: undefined reference to `u_tolower_48'
/usr/local/lib/libboost_regex.so: undefined reference to `icu_48::Locale::Locale()'
/usr/local/lib/libboost_regex.so: undefined reference to `u_isblank_48'
/usr/local/lib/libboost_regex.so: undefined reference to `u_charFromName_48'
/usr/local/lib/libboost_regex.so: undefined reference to `u_isspace_48'
collect2: error: ld returned 1 exit status

Anyway, its just my Linux test machine - I don't care about it.
But I did have a working sx, before upgrading - no more, though.

From the good news.
I think the stealth addresses are already working in Gocoin.
It's a bit of a hassle to spend money from such. You need to arm the online part with the scankey's secret and then use TextUI to fetch its balance data.
But using the wallet for spending to a stealth address - this is as easy as it can be; just use a stealth address in place of a regular one and voila.
Although... I cannot quite test it because currently whatever I send to any of my DW testnet addresses (stealth, or not) ends up in a limbo.
So I can only test it against my own client - this one can receive coins via a stealth address and spend it further, using own wallet.

Also I learned that a prefix of 32 bits would kill any wallet, unless you'd hook it to some kind of a mining board.
So my wallet does not support prefixes longer than 24 bits. And no multisig yet.

Thanks anyone for your help. That was fun. Now time to clean up the house a bit :)

Title: Re: What is the status of the stealth addresses?
Post by: dabura667 on May 06, 2014, 06:57:25 PM

Quote from: piotr_n on May 06, 2014, 08:30:36 AM

@dabura667
cheers.
so the prefix length cannot be bigger than 32 bits?
and if it was all 32 bits, but I could not find a matching nonce - what then? pick up a different "ephemkey"?

Yes, this is how the current implementation of Dark Wallet does it.

If you run through all the nonces and no match is made, it breaks one do loop and returns to the ephemkey generation in the outer do loop.

Title: Re: What is the status of the stealth addresses?
Post by: genjix on May 06, 2014, 10:06:53 PM

piotr you will need to eventually upgrade anyway ;D

we're on freenode irc #darkwallet too if you have any questions https://webchat.freenode.net/ or use XChat

I'm currently improving the stealth commands in SX then will merge to master after.

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 06, 2014, 10:37:16 PM

Yep, and clean up the house.
But since it's after midnight here already, I decided to just have another beer now and postpone any such work till at least tomorrow. :)
I will like to exchange some test coins with another wallets' stealth addresses, so I'll try to catch you later.
Cheers

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 09, 2014, 07:01:48 PM

If I may, I'd like to say that despite of my initial complaints the idea of the stealth addresses, as it has been implemented in DW, is actually pretty cool and works really nice.

Checking an output on whether it belongs to a specific stealth address is not so much time consuming, especially considering the fact that a node usually needs to do a several ECDSA_Verify operations on each transaction anyway.
And the idea with the prefix - very good one.
You can just start with prefix length 0, to protect your anonymity when there are just a few stealth addresses out there..
But when the volume of stealth outputs rises, you can increase the length of your prefix, saving the node's computing power though still staying anonymous.

Whoever designed it, great job!
And thanks - finally somebody not only invented/described, but also delivered an actually useful feature to the bitcoin ecosystem.

Title: Re: What is the status of the stealth addresses?
Post by: genjix on May 10, 2014, 07:37:54 AM

piotr, http://sx.dyne.org/stealth.html

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 10, 2014, 08:45:28 AM

Yep, I saw it already - thx.

But it seems to be already working well in my s/w (sending and receiving).
I can exchanging coins via stealth addresses with DW - don't need sx for it anymore.

Unfortunately sx nor DW support stealth addresses with non-zero length prefixes ATM, so I cannot test that part of mine.
But zero length prefixes seem to work just fine.

Title: Re: What is the status of the stealth addresses?
Post by: genjix on May 10, 2014, 09:56:41 AM

Quote from: piotr_n on May 10, 2014, 08:45:28 AM

correct. glad to hear that.

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 10, 2014, 10:29:57 AM

btw, can I have the sx tools for testnet?

the ones I finally managed to build cannot even do

Code:

$ sx stealth-show-addr waPV5rHToBq3NoR7y5J9UdE7aUbuqJybNpE88Dve7WgWhEfvMrcuaSvF6tSQ3Fbe8dErL6ks8byJPcp3QCK2HHviGCSjg42VgMAPJb
sx: Invalid stealth address.

Title: Re: What is the status of the stealth addresses?
Post by: genjix on May 10, 2014, 01:27:41 PM

Quote from: piotr_n on May 10, 2014, 10:29:57 AM

btw, can I have the sx tools for testnet?

the ones I finally managed to build cannot even do

Code:

$ sx stealth-show-addr waPV5rHToBq3NoR7y5J9UdE7aUbuqJybNpE88Dve7WgWhEfvMrcuaSvF6tSQ3Fbe8dErL6ks8byJPcp3QCK2HHviGCSjg42VgMAPJb
sx: Invalid stealth address.

In the install-sx.sh script, in the function called install_libbitcoin, change ./configure with --enable-testnet

this line:

https://github.com/spesmilo/sx/blob/master/install-sx.sh#L313

Code:

install_libbitcoin(){
    ...
    ./configure --enable-leveldb --prefix $INSTALL_PREFIX --with-libsecp256k1=$INSTALL_PREFIX --enable-testnet
    ...
}

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 10, 2014, 01:39:24 PM

Quote from: genjix on May 10, 2014, 01:27:41 PM

In the install-sx.sh script, in the function called install_libbitcoin, change ./configure with --enable-testnet

I think I did that.
Also added "--enable-testnet" for libwallet

I'm looking at config.log in libbitcoin-git and libwallet-git - they both show "ENABLE_TESTNET 1"
But the "sx stealth-show-addr" still says "Invalid stealth address" for any testnet stealth.

At the other hand it has no problems to decode a non-testnet stealth addresses.

EDIT:
I think I know where is the problem.
In libwallet-git/src/stealth.cpp, there should be:

Code:

#ifdef ENABLE_TESTNET
constexpr uint8_t stealth_version_byte = 0x2b;
#else
constexpr uint8_t stealth_version_byte = 0x2a;
#endif

Title: Re: What is the status of the stealth addresses?
Post by: genjix on May 10, 2014, 07:30:06 PM

Quote from: piotr_n on May 10, 2014, 01:39:24 PM

Quote from: genjix on May 10, 2014, 01:27:41 PM

In the install-sx.sh script, in the function called install_libbitcoin, change ./configure with --enable-testnet

Code:

#ifdef ENABLE_TESTNET
constexpr uint8_t stealth_version_byte = 0x2b;
#else
constexpr uint8_t stealth_version_byte = 0x2a;
#endif

I added that in git.

Also now there is a --develop switch: bash install-sx.sh PREFIX --develop

Title: Re: What is the status of the stealth addresses?
Post by: ViewSonic on May 11, 2014, 01:39:16 PM

I will be really interesting to exchange some test coins with another wallets' stealth addresses. If someone will do this - leave a feedback!

Title: Re: What is the status of the stealth addresses?
Post by: piotr_n on May 11, 2014, 06:00:16 PM

Quote from: ViewSonic on May 11, 2014, 01:39:16 PM

I will be really interesting to exchange some test coins with another wallets' stealth addresses. If someone will do this - leave a feedback!

be my guest :)

Code:

waPV5rHToBq3NoR7y5J9UdE7aUbuqJybNpE88Dve7WgWhEfvMrcuaSvF6tSQ3Fbe8dErL6ks8byJPcp3QCK2HHviGCSjg42VgMAPJb

Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: piotr_n on April 30, 2014, 01:11:13 PM