Topic: [Want Feedback] Improved Stealth Address send/discovery method. (Read 2337 times)

spend_pubkey = public
shared_secret_pub = private
vout_pub = public

Since the shared_secret_pub is already private (as it is the scan_privkey x Ephem_pubkey (or vice versa)) there is no need to have the vout_pub be secret.

The vout_pub only serves the purpose of removing the possibility of address reuse when sending multiple outputs to the same stealth address.

Not to mention that if you used scan_privkey, the sender would not be able to calculate the address's point.



Back to OT, I have been working on this sporadically, and a lot of security concerns arise from allowing private keys to stay in memory for longer than necessary...


I was thinking of other solutions... one of which would involve using the k value (the one used to generate the r value of the signature) with the scan pubkey to generate the shared secret... this way the receiver would multiply his scan privkey with the r value to get the shared secret... the problem with this is that it would mess with the deterministic signatures of Electrum. (you need the final tx to be signed in order to be a truly deterministic signature... I think that replacing the output script with the hex representation of the stealth address for the k generation, and this should be sufficient... but the security implications of such tomfoolery is beyond my scope of studies)


I guess the best way to deal with it is:
1. Move to create a new standard script template that can accommodate stealth in one output.
2. Just hope everyone uses stealth to lower the standing out of OP_RETURN stealth on the blockchain.


Maybe I'm just over-thinking things...

ok, several things:

first, the fact is the current mechanism's goal is that we don't need to do any communication between sender and receiver since otherwise we might as well communicate a new address.

so, having to scan all tx and having no way to pre-filter makes it unfeasible from the (light) client side, I have to scan all incoming tx and will have to calculate on all of them to make sure there is no stealth. with the other method, we just need to scan all tx but calculate just on OP_RETURN against the next output. also a matrix op_return, address can be generated to avoid needing to download that much data to scan.

so, having a stealth matrix in the server is a not requisite with the current darkwallet method (just helps for light clients), if you're willing to scan all tx then no need for server table, it just makes it more convenient. and also, even if you need to scan all tx you can still discard most as not having stealth, if they do we still dont need to calculate all in*out to make sure.

also little bug (i think), the mechanism how you avoid address reuse:

vout_priv = sha256((scan_pubkey + prev_hash + vout + index).decode('hex'))

maybe you want scan_privkey instead of pubkey there otherwise the secret is public...

From what I see, a single check operation you need to do at the receiver side takes something like 1ms, for my optimized secp256k1 lib (it's generally faster than openssl).
And that operations are on top of accessing the required transaction input data - note that to check past blocks, you need to dig inside the blocks db.

For a real time blocks processing, there are blocks (e.g. #321848) where you'd need to perform tens of thousands of such ops - multiply it by 1ms and the number of scan-keys you'd want to monitor. Well you can make it in parallel, so divide it by two or three...

Still IHMO, to make this method useful, we'd need to come out with some off-chain way of communicating which txs a wallet should check.
Otherwise a user would need to have a pretty powerful dedicated server, to monitor stealth payments going into his wallet - java script client is totally out of the question here.
And even having a powerful dedicated server, you won't be able to monitor thousands of stealth addresses on it - maybe a few hundreds at most.
Moreover, re-scanning for an unspent outputs in the past blocks would be taking a lot of time.

cool thinking, go for it!

Pretty much.

Also another downside is that it would be nearly impossible (without a change in the current firmware) to send TO one of these addresses with this method from a Trezor etc. (As you need to multiply their scan_pubkey with the private key of your first input's address.)


This COULD be remedied by inserting the scan_pubkey into the trezor, having the trezor multiply the appropriate privkey with the inserted scan_pubkey and returning the shared secret pubkey.
Also, this would make it difficult to send TO from an offline wallet (a la Electrum offline wallet) but that would just be a pain in the *** rather than an impossibility. It would involve changing the format of an unsigned transaction for signing offline into a format that would not be backwards compatible with older software... which is not ideal.

Anywho, my main goal for this test is to learn more about the server load caused by checking every input of every transaction.

So basically the good thing is that stealth payments are indistinguishable and smaller,  but the bad thing is that because of that you need to scan all the outputs  looking for those belonging to a wallet.
Right?

I'm busy this week,  but in general I'm into it and will gladly get to do it with my client.

Will be looking into this topic

Don't have time to help out as much as I'd like, but go for it! With stealth we're still at the point where getting data on how various possible standards perform and what the tradeoffs are is very useful prior to developing the first "set-in-stone" standard; changing stuff now based on feedback will be much less work than doing so later.

Just wanted to:

1. bump this.

2. Let anyone know that I am going to be implementing this into mr_burdell's testnet branch of Electrum (because testnet FTW) starting today and maybe have it running early next week.

3. I will be testing discovery methods while communicating with mr_burdell to see what the load on his server is like. (he is the only testnet server afaik)

4. If anyone else would want to test it out with us, idle in #electrum for the next week or so and I'll pop up when I'm done.

> The most important is the one you've noticed, but I think it's worse than you think it is:   It prevents any delegation of scanning because you cannot scan without putting one of you spending keys at risk.

This is where the "Dual-key" method of Dark Wallet comes into play. The "Scan keypair" is a special key that is down a predetermined BIP32 oath of all hardened keys. This key is only used to generate the shared secret for discovery, but the private key is not used for spending. This key's private key remains unencrypted in the wallet file for Dark Wallet so that it can be multiplied to the ephemeral pubkey.

I think that if you are ok with giving someone your extended public key, the equivalent in this scheme would be to give them your scan PRIVATE key (as this is what is needed for discovery, but not spending)

I agree that this would be difficult to do with something like a Trezor... (I'm sure no matter what the circumstances, they don't want ANY private key to leave the device) but to be honest I don't find that to be a problem. Trezor is compatible with BIP32 (and 39 and 44), and that's it, that's fine. Not every wallet must support receiving to this scheme.

I also realize it would be difficult to send TO one of these types of addresses FROM a Trezor, unless you could somehow send the pubkey to Trezor, have it perform the ECmult and spit out the shared secret point... but again, I think if there was enough demand, it would not be impossible.

> It creates an assumption that you have access to the private keys on the coins you're spending. In the case of a shared wallet, vault service, escrow, or coinjoin you do not (or only have some of them). If it relaxes which keys can be used for inputs, it would at least still support the coinjoins but require N fold more ECDH work for the scanner (as it much check each input).

In the case of hosted wallets. By this point, static addresses are almost useless. Sending to a coinbase hosted address of this scheme would only have the merit of not letting the outside user see Coinbase's funds... but to begin with most people don't post Bitcoin addresses from Coinbase to begin with (they have payment pages etc.) So I don't see this as an issue. Different use cases for different people.

I also though of the N fold problem for coinjoin. My thoughts were that someone could just scan every input from every transaction, OR the sequence value of the input used could be changed from 0xffffffff to some other set value, and the client would only check inputs with that value etc. (This is similar, in effect, to the prefix's role in the current Stealth system) This would be where you could trade off privacy for performance. ie. SPV wallets could require a specific value in sequence for all payments (in other words, any address generated by the SPV wallet will place a specific prefix value) and the sender would always follow the prefix value included in the address. This way weaker clients could be slightly less private, but keep the merit of not reusing addresses, and having a static address to send to, and clients like Armory could have 100% private addresses that scan every single input for possible matches as they come in.

> It also makes the user pair mapping staionary. If I pay you some coins, and then later pay you some coins recieved to the same key... it'll use the same address, and thats bad for both our privacy. This also means that I cannot forget where I've sent funds without also forgetting my spending keys.

This is not true. My method states that the address generation requires 3 EC points, 1 from ECDH, 1 from the scan pubkey (contained in the stealth address) and 1 from the hash of the prevout hash || vout of the input || index=0x00 (The index is only used when the same person sends to the same stealth address more than once in the same transaction. A rare use case, but need to account for it) because of this, using the same prevout hash and vout would mean it was a double spend... so the addresses should never generate the same... in regards to the index. In the situation where the client scans every input of every transaction, the client would say, if a stealth send is found, try the same input again but changing index to 0x01, and increment until you find no more matches.

> Then, related to the assumption of private key access, there is the issue that it it creates a bad coupling beyween the spender and the recivers pubkey types. If I start using some new kind of multisig script, or perhaps a hash based signature or something else to control my own funds, then suddenly there are all these addresses which I can no longer directly send to.

This is true. However, I think as long as the ScriptSig has ANY pubkey in it that the person generating the tx has access to, it should be fine. (aka, discovery might be something like "if input is p2sh, check the redeemscript for pubkeys and iterate through them, etc.) and the person who generated the transaction on the senders side would use their keypair to generate the output when they sign the incomplete transaction.

> I'd originally thought it might be useful to _optionally_ support doing something like this, when the stars and moon align to make it possible... but the required bad security practices and huge slowdowns from having to do lots of extra ecdh to scan made it seem much less attractive. Plus there is a risk that the one side of the optional configuration doesn't exist and you get people unable to use different pubkey types, or people losing funds that were sent to them because their software won't notice the payments.

I also think that this is an optional thing to do. Similar to the way p2sh is optional, and BIP32 is optional...
I think the idea of the current implementation of Stealth and my method are similar in their main goal which is privacy, but static addresses.
There are a lot of hurdles that can be overcome by removing privacy, like for instance, making a 4 byte prefix and placing it on your address, then anyone sending to that address must change their ECDH input's sequence value to that or something else. Heck, if it becomes widespread enough maybe doing a fork like p2sh could happen somehow to give it it's own place on the transaction etc.


I think your points are valid, but most of them seem non-issue / would be known as accepted by anyone wanting privacy.

Thanks a lot for the feedback. If you have any more questions let me know!

Also, > If I start using some new kind of multisig script, or perhaps a hash based signature or something else to control my own funds, then suddenly there are all these addresses which I can no longer directly send to.

I am curious what other kinds of scripts you had in mind here.

What you're proposing there isn't new -- it's older than "stealth adresses", but it has many limitations which the current design was constructed to avoid.

The most important is the one you've noticed, but I think it's worse than you think it is:   It prevents any delegation of scanning because you cannot scan without putting one of you spending keys at risk.  This means that it's not ony incompatible with trezor and other hardware devices,  it's also incompatible with good wallet encryption which keeps your private keys out of memory when not in use.  Keeping spending keys offline is an important security practice, and it would be really terrible to have a design which prevented it.

It also prevents you from using a third party scanning service (at the cost of some privacy), meaning you can only use it if you download the whole blockchain yourself.

It creates an assumption that you have access to the private keys on the coins you're spending. In the case of a shared wallet, vault service, escrow, or coinjoin you do not (or only have some of them). If it relaxes which keys can be used for inputs, it would at least still support the coinjoins but require N fold more ECDH work for the scanner (as it much check each input).

It also makes the user pair mapping staionary. If I pay you some coins, and then later pay you some coins recieved to the same key... it'll use the same address, and thats bad for both our privacy. This also means that I cannot forget where I've sent funds without also forgetting my spending keys.

Then, related to the assumption of private key access, there is the issue that it it creates a bad coupling beyween the spender and the recivers pubkey types. If I start using some new kind of multisig script, or perhaps a hash based signature or something else to control my own funds, then suddenly there are all these addresses which I can no longer directly send to.

I'd originally thought it might be useful to _optionally_ support doing something like this, when the stars and moon align to make it possible... but the required bad security practices and huge slowdowns from having to do lots of extra ecdh to scan made it seem much less attractive. Plus there is a risk that the one side of the optional configuration doesn't exist and you get people unable to use different pubkey types, or people losing funds that were sent to them because their software won't notice the payments.

Prerequisite: Understanding how DarkWallet currently implements stealth addresses.
See: https://wiki.unsystem.net/en/index.php/DarkWallet/Stealth

Remember: Don't turn this into a thread about yes/no to stealth in general. I would like to keep the discussion on how to make my method better, AND possible merits / demerits of this method compared to how DarkWallet currently handles them.

Here's my proposal in psuedo-Python format. (this is not a script, so don't try to run it :-P)
http://pastebin.com/bcs8XFNG

Caveats:
1. Can't send to stealth from Trezor using this method. (as you need to multiply your private key with the scan_pubkey)
    Unless Trezor allowed for performing ECmultiplication on the device, and Trezor returns the shared secret.

2. When thinking about coinjoin and other aspects where multiple people spending to multiple stealth addresses, if we consider coinjoin, we must check every input of every transaction against our info... which is costly. Doing things to mark inputs as stealth info (maybe changing the sequence value) could be considered... but for 100% stealth and 100% no way to discern stealth from normal... there seems to be no other way than to check every input.

However: that being said... it eliminates the requirement for the OP_RETURN table on Obelisk servers... and it's not much more strenuous than running a full node. (having to scan every input of every transaction etc. when blocks come in) but it will be more strenuous for SPV servers, as upon every block they will have to send every transaction to each user... it will also be hard to do on mobile devices (drain battery)... obviously the wallet file would store the most recently checked block so that it doesn't check from the beginning every time.

Perhaps a mode where the wallet doesn't actively search, but users need to input the txid or something that they receive from the sender might be good for mobile...


I am open to comments. Currently I think that the OP_RETURN usage is a hurdle to making stealth addresses ubiquitous... and I'm sure my method won't get us all the way there.

Just wanted you guys to know I'm thinking about you. :-D

PS. Electrum 2.0 /w Send-to stealth support? https://github.com/spesmilo/electrum/pull/817
      Anyone who can help test this commit, please thank you! :-)