For your information, your post is essentially my goal in (BTC) life.  I suspect I may never actually finish a working client, in which case this just becomes a wishlist I hope other developers will consider.

Some additional features I plan to implement (or wish others would implement):

• "Watching-only" wallets/accounts.  Using a deterministic wallet on an offline computer, only pass the public key of the first address and the "chaincode" to your primary (online) computer.  Using some crypto-magic, this allows the online computer to generate a new address for the offline computer without actually needing any of the private keys.  The private keys never touch the internet, yet you can create addresses and confirm payments from your primary computer!  (The chaincode is sensitive for privacy purposes, but not security purposes--if this chaincode is compromised, someone could figure out that all the addresses are related, but can't get access to the money). 
• Easy transfer of blockchain data to offline computer, and completed/signed transactions back to online computer.  If your private key never touches the network, but it's not too cumbersome to send money from that account, BTC security gets a major upgrade.
• Extreme keystretching for encrypted online wallets. Your private keys are protected by encryption based on a passphrase.  But in order to get from the passphrase to the encryption key, it must be hashed/mangled 10 million times.  This means it will take on the order of 1-2s just unlock your wallet, which is acceptable for the user who enters the correct passphrase every time.  But for an attacker, he's gotta do 10 million hashes/operations just to brute-force-check 1 key.  This makes even simple passphrases much difficult to brute force, as it could take the attacker hours to test a million passphrases instead of seconds.
• Linking of phone accounts to computer accounts.  Computer has smartphone private keys but won't use them unless the user hits the "HELP!" button.  The wallet can then monitor/refill the phone account, and if the device is lost, the program can empty the money that was on the phone into non-phone addresses.  With key-stretching above, you only need to hit the HELP! button within a 1-10 days of losing your phone to re-secure your funds.

I've got all the algorithmic design capability to implement these things, but who knows if I've got the software skills to pull it off.  Regardless, I hope other developers consider these ideas.

Well certainly, that would be idiot-proof for the ((A and B) or C) transaction type.  However, I think users benefit a lot more if the capability is built into a "standard" client, and then the security company only has to focus on the second-factor authentication.  It would cost literally 10-100 times as much to also have to do software development, deployment, maintenance, and support for the software.  Not to mention, users would then have to juggle multiple programs just to use Bitcoin and that's not good for general acceptance.

It would be amazing to the success of Bitcoin if these features weren't too complicated to use and didn't require third-party involvement.  Perhaps a family would put a bunch of money into an account encumbered by 2-of-3 transactions between you, your wife, and your kid -- the kid can spend/withdraw the money only if at least one parent agrees, and the parents can't take the money from the kid unless they both agree.  However, these ideas may build hype and then be unrealizable because of implementation/interface details that can't be worked out. 

I'm not up to par with my understanding of the nlocktime field, but what does "replacement" mean in this context?  We say the tx can be replaced, but if it's expected to have the exact same hash as the original transaction, it can only be replaced with an identical copy of itself, which isn't very useful. 

From what I understand, you have to increment the sequence numbers on the TxIn in order to issue replacement transactions.  Regardless of signatures, this would change the Tx hash as well.  Although I don't understand how this is implemented, it sounds like the protocol expects the tx hash to change when nlocktime/nsequence fields are utilized.

I don't usually bump threads because I think it's rude, but I'm doing it.  With Gavin talking about enabling multi-signature transactions, the community is going to have to start deciding how to bring them to the 99.99% of users that can't or don't want to construct them manually.  It's not very useful if no one can use it.

I'd like to figure out the CONOPS (concept-of-operations) for users that will use these transactions.   My mock-up contains a lot of ideas, but it's not the entire solution.

For instance, what is the most efficient way to execute a 2-of-3 transactions for the buyer-seller escrow case?
- Online buyer wants to purchase item for X BTC
- Buyer commits 110%*X to a 2-of-3 transaction between buyer, seller and third-party arbitrator.
- If buyer receives product and everyone is happy, buyer and seller both contribute signatures to send X to seller and 10% return to buyer (so buyer has incentive to complete the tx).
- If buyer and seller cannot agree, no one gets the money (so both parties have incentive to agreeably resolve situation).
- In event of dispute, both buyer and seller can appeal to third-party to arbitrate.  3rd party gets the 10% as fee.

This may not even be the best way to execute this kind of transaction, but it's feasible, and it will involve juggling a lot of different things.  Proposing distributions of the encumbered money, collecting signatures, serializations, constructing final tx to be broadcast, and all with an "idiot-proof" interface for users that don't understand entirely how these things work.

Your request is quite vague.  I don't know what kind of application you are talking about, and what kind of configuration you need.  From the language of your post, I can't even tell if this application is BTC-related.

I have a bit of experience with Python, but I have no context to determine if I can help you.

Since I like making pictures, here's one that should clear up everything I've said so far.  The "DHSS Key Gen" is your proposed solution that I have already declared is brilliant.  It represents the way to create "friends" that can generate new keys for each other after a handshake.

Everything else is the full puzzle I was trying to convey.  If you re-read my previous posts, you'll see this is what I was trying to communicate, but did so very poorly.



Full-sized image is at:  http://dl.dropbox.com/u/1139081/BitcoinImg/overflow/Unified_DHSS_Solution.png

Keep in mind that this only shows other people sending me money.  The handshake would also enable me to send them money without requesting a new address.

Whoa, I missed something here.  I wasn't proposing an alternative to your idea.  Your idea is absolutely elegant & brilliant, but I don't see how it solves the problem of one-time wallet backup and privacy-preserving key generation,  it's simply one (critical) piece of the puzzle.  This isn't off-topic, I was trying to fill in what else would be needed to complete this puzzle.  I think you misunderstood.  Or I misunderstood the puzzle.

EDIT:  look at the picture in my next post before continuing

Take the example:  you run a small business.  You have 100 customers every week paying you with one-time addresses who will never engage in your solution because it's not necessary.  But you have relationships with banks, distributors, maybe frequent customers that do benefit from your solution.  So you set up your client to use your (ByteCoin's) solution.  
  
The problem is your client is checking all those one-time addresses for DHSS-based addresses and at some point it just can't keep up anymore because your wallet is so huge.  Should your client check every key in every global transaction going forward forever?  I argue that it's not only best, but actually necessary to encode this into the blockchain via some kind of handshake -- if we want this solution to accommodate all use cases.

• If you don't do some kind of filtering/revocation, the computation required for a large wallet will become prohibitive.  The CPU will be calculating DHSS's for thousands of your own keys in every transaction that goes by just to see if money was received (even though 99% of your keys will never have your proposed address scheme applied to them).    
• You can't rely on the user to tell the client what to search for, it needs to be evident to your BTC client.  If the user doesn't do it right, they could end up missing transactions that they should've been searching for, or make their computer unusable while it searches everything.
• Even if you could trust the user, the wallet was only backed up once, which means in the event of recovery all this information is lost forever.  There's no way to recover it and thus you run into the problem above.
• By encoding the rules into two transactions, once, you enable your client to automatically apply your solution with minimum, bounded computation.
• Your solution is likely to be used by parties who expect to execute many transactions over the course of their financial relationship.  Two tx's exchanged once to initiate this agreement is noise.
• Maybe I don't want people assuming I accept these chained address transactions unless there's an explicit agreement
• This handshake allows you to encode the start of the agreement and the revocation into the blockchain with the same degree of anonymity that your solution provides for actually generating addresses

It can be debated whether the fact that X and Y are handshaking needs to be concealed (per the last bullet point).  But my solution solves all the problems described above, and perfectly compliments your solution.  (it may not be a great/simple solution, but it does work, and we're here to discuss these things)

As for alternative clients, I don't think it's your place to tell me I shouldn't be working on alternative clients.  Not all ideas (like this one!) can un-controversially go into the main client.  The main client doesn't work on Android/iPhone.  Not everyone can program C++.  Not everyone wants the full blockchain on their computer.  No one will ever agree on all the features that should go into it.  What if I don't like the file formats, data structures and encryption schemes?  What if I wanted to do something different?  How many people can really understand Bitcoin without getting their hands dirty writing the protocol themselves?  I could go on, but I'm trying to stay on-topic...[/list]

Bytecoin,

I will PM you later, as I put together a more formal proposal relating to this idea. But I want to hear your thoughts on two other things:

(1) My current proposal will suggest a hash-based generation method for generating new keys for parties that you have never communicated with.  This means that you generate new addresses yourself with secure hashing methods, all based on your original 256-bits of entropy.  There is, of course, EC-related ways you could do this, but I believe hashing is "better" as you don't need reversible transformation.  In the end, it's probably moot since all of these techniques are extremely secure.  But if you see some reason to use the crypto methods to generate new keys for new parties, I'd like to hear them.

(2) One major drawback to your idea is the risk that if your base key was compromised, someone may send you money not realizing that it's no longer a secure address.  This could be a devastating problem, especially with parties that exchange money frequently.  I'd like to propose a HaltChain message based on the initial key exchange between parties A and B that will let the other party know to stop sending money to these addresses.   Here's the proposal and the CONOPS for it (concept-of-operations) for A and B to initiate a long-term financial relationship :

EDIT:  I have rewritten the following from the original post, to reflect a new, better handshake process than the original without diluting this thread any further.   Note that DHSS is "Diffie-Hellman shared secret."

• (1)  A and B both create new addresses specifically for establishing this relationship.  Use hash-generation to create these new keys.
• (2) A sends B a Base58 version of his public key -- this only has to be done once (and really not any more burdensome than sending the address alone).
• (3) B will fund his new address and from that address construct a Tx to the address provide by A's public key.  It's important to note that B is sending directly to the address, not some computed version of it . The Tx amount containse the relevant information: it is the DHSS value computed based on both public keys, modulo 1e6.  If the DHSS is 19284183992249101 the transaction value will be 0.00249101.
• (4) A will look for such transactions, but only has to look at his own transactions, not the entire blockchain since he knows that such handshake tx's will be sent directly to one of his own addresses (massive computation saver!).
• (5) A will construct a reply transaction for the exact same amount, to a new computed address for B, based on the Diffie-Hellman sender-generation technique.
• This completes the handshake.  A and B both flag these two addresses as "chain-bearing" addresses, and compute a shared haltcode:  DHSS^249101 mod N (where N is the size of the EC group).
• In the event that one party's keys are compromised, or one party just wishes to reset the chain for security reasons, they simply send a transaction for any amount to the address ripemd160(sha256(HaltCode)).
• Before either party generates a new address for the other one, they will search the blockchain for any tx sent to the halt-code (a small price to pay for security).  If the halt-code is observed, the sender knows that the chain has been canceled and they need to contact the recipient to obtain a new address

Now, let's say A and B both lose their wallets and need to reconstruct their transaction history.

A only needs to search through transactions that were sent to one of his hash-generated keys.  A can calculate the DHSS for each of those [limited number of] Tx's, and see if the value matches the computed DHSS value.  If it does, he should check if that address then signed an identical transaction to another address.  If so, that's a chained tx handshake.

B only needs to search for transactions from his own keys and check whether the value is a computed DHSS code.  If so, he can check for the reply transaction from that address and confirm that he actually owns that address.

Actually, both parties need to search for both, because they don't know whether the were the originator or responder, but neither of them have to search the entire blockchain.  And the only identifying information here is that one address sent a transaction to another unrelated address for its entire balance, which really isn't all that uncommon.

This process provides a lot of explicit benefits for both parties:

• Explicit agreement before parties start executing the Diffie-Hellman address generation.  For most transactions (one-time sales on ebay), you wouldn't want or need to establish this relationship.
• Dramatically reduces the number of your own public keys that you have to search the blockchain for, and thus reduce computation.  Most of your keys will not follow this protocol and you won't need to search for chained transactions on those addresses.
• A related benefit is that the HaltCode also lets you know when you can stop searching for transactions on that chain.  This means that you can remove public keys from the pool of keys you search for.
• It provides a way for parties to communicate that they wish to change their key generations chains for any reason.  Businesses may choose to do this a couple times a year to invalidate any key chains that might be compromised by malicious employees.

Perhaps this is completely overkill.  Let me know what you think.  Either way, I want to start combining all these ideas into a unified proposal for a specification like this.  Even if it wouldn't be included in the main client, I have my own lite-client I'm working on, and if we can create a "standard implementation" it allows client developers to support it so that different clients can still communicate in this fashion.

-Eto

Ack, that was pretty stupid -- B always has A's public key because it's in the TxIn script.  Just ignore the second half of my previous post

So B doesn't need to know anything about A in advance, and A only needs a public key of B.  Even if A picked any transaction he knew belonged to B, he could send him such a transaction, and B would eventually be able to find it if he scanned every transaction, trying all of his keys on each one looking for ones that match.  A would be wise to request a specific key from B before doing this the first time, otherwise it's going to be a lot of EC calculations for B to find such transactions to himself.  But it's still possible either way.

I really like this idea.  This makes any key in your wallet a generator of keys/addresses, the next one is generated by whoever is sending you money.  And people who know your public key can't identify it as belonging to you.  

My main problem with using this as the primary source of communication is that EC multiplies are expensive, and when transaction volume increases, you're going to be spending a lot of CPU time just scanning new transactions for whether one of them is yours.  At some point, it will take an average of more than 10 minutes to scan incoming transactions.  Then what?  And we will certainly hit that threshold a lot sooner with devices like Android apps: they will be draining the users' batteries just to check all incoming transactions!

Similarly, if B loses his wallet and has to recover from an initial set of keys, that's going to be a very long scan.  It gets longer as you receive more transactions, as you accumulate more addresses from which someone could've based another tx to you.  Still better than losing all your coins, though!

Bytecoin, this is great stuff.   The general idea of executing Diffie-Hellman using the existing public keys is pretty smart, and only works because the EC public key calculation is already one side of a Diffie-Hellman exchange.  I don't see an analogous procedure if we were using some other asymmetric op, such as RSA.

First of all, what is the point of using the TxInSig_r after the Diffie-Hellman calculation?  You already have a shared secret established at this point, which is GenPt*PrivKeyA*PrivKeyB (I'm using A for sender, B for recipient).  Why do you need to add the TxInSigA_r?  And why addition and not multiplication?

Why not just use the x-coordinate as the session key, and use PubKeyB*DH_Session_X as the target public key? Then B can redeem the funds using PrivKeyB*DH_Session_X as the private key, and I don't see any loss of security.

EDIT:  remainder of post edited out for being stupid

That's fantastic, Maged.  He also mentions in that thread an idea which I've wanted to figure out for a while:  how to create a generator that can be kept offline, but still generate it's public addresses/keys from an online computer without the private key.

That's a very fascinating thread, and I will also need to read ByteCoin's proposal a little more closely.  Thanks!  And sorry for the repost!  I'll work on my searching skills...

-Eto

I agree, but that doesn't mean we can't have both.  There's so many other rewarding places the conference can be held in Thailand.  Pattaya is going to blazing hot, full of lady-boys, gay Russians and child-sex  tourism.  If you're going to pick a country, why not listen to people who've spent a lot of time there for recommendations?

Chiang Mai is cheaper, safer, easier to get to, cool at night, people are friendlier and the less-social folks will have more to do than fighting off lady-boys hitting on them in the streets everywhere they go.  It's really win-win for everyone (unless you're into the child sex thing).

The organizer may have picked the location for the same reason my girlfriend and I picked Pattaya the first time we went to Thailand:  we didn't know any better.  Pattaya is very close to Bangkok, and the bus is like $2.50 each way, making it very attractive for a short trip.

However, I have quite a bit of experience with Thailand (I even speak a little Thai), and I've never met a Thai person who thought positively of Pattaya.  Our experience reflected that.  I just want to make sure that whoever is setting this up is a aware that there's a lot of terrible reputation surrounding Pattaya, and there are so many phenomenal other places in the country that are perfectly suitable.

If you're looking for financial hubs, perhaps Thailand isn't the best.  Though, I don't think Bangkok is a bad choice.  It's a large, bustling city.  But there's also airports in Chiang Mai and Phuket, which are both fantastic locations, so I'd recommend any of those three.

Raize,

I completely agree with everything you just said.  I recognize that there's more to the calculation than the order-of-magnitude estimate I provided in my first post.  But it doesn't change the fact that:

• (1) For the same reason someone with more than 50% can get unlucky and fail to execute a large double-spend, someone with less than 50% can get lucky and pull it off. 
• (2) There is potentially irreparable harm done to the network by anyone executing this kind of attack for any reason.  We can argue about the unlikelihood of it happening all we want, but the folks designing the Japanese nuclear plants probably would've said the same thing about the liklihood of a 9.0 earthquake+tsunami hitting them (I believe that plant was designed to withstnad 7.0)
• (3) Some might argue that the value of Bitcoin as it stands is completely irrational.  It's based entirely on speculation and imagination.  It doesn't take a rational reason for people to start jumping ship and for the program to come crashing down, even from just one legit attack.  Everyone could see the huge blockchain re-organization, and it would make news headlines.
  
• (4) I don't want to focus on the degree of feasibility so much as the fact that it is possible for someone, whether botnet or government or Warren Buffet, to collect the resources to execute the attack.  It wouldn't be easy, but Bitcoin is a high-profile network with almost $100 million of value, so the possibility that someone would want to do it can't be ruled out.

If it's feasible now, it's only going to become more feasible in the future if nothing changes.  At current rates, the best we can hope for is that BTC will more than 100% ROI when the reward gets halved, and the current mining community sticks around then.  I just don't want to get lost arguing about whether any botnet has precise enough computers to execute the attack, I'm just operating on the assumption that there are people/organizations out there with the same order-of-magnitude of resources needed and that it can't be ruled out. 

Of all the great places in Thailand, Pattaya must be one of the worst choices possible.  It is really shitty (for reasons mentioned in my last post), and I've had locals in other cities there tell me not to go there due to the organized crime elements, among other things.

Seriously, Thailand is a phenomenal country for so many reasons:  there no other country you can go that simultaneously is so inexpensive, yet also relatively safe and has amazing people everywhere you go... except for Pattaya.  I'm sure there's other places that are shady too, but there's no reason to pick any of them.  If the beach is preference Phuket, Ko Phi Phi, or Hua Hin are excellent choices.  Phuket and Hua Hin are at least as easy to access as Pattaya, but without the reputation as child sex havens.

If beach isn't required, I think Chiang Mai should be first choice, which I believe is one of the best cities in the country, especially for tourists.  It's astoundingly cheap, it gets cool at night (unlike the rest of Thailand which is right next to the equator), it's a lot more laid back than the city-scape of Bangkok, and even after spending two weeks there I never met anyone I didn't like (besides other tourists).  There's also an airport for folks to fly into directly, or take an overnight air-conditioned sleeper train from Bangkok for $20 (I love the train). 

I absolutely love Thailand.  I've spent 6 weeks there, and I am mildly conversation in the Thai Language .  Yet, the one place my girlfriend and I never want to go again, is Pattaya.  We went there because it was close to Bangkok, but it was a huge mistake.  I should say I have nothing against homosexuals at all, but this place was disturbing.  Seeing 50 yr old men walking around in Speedos arms locked with a 15 year old boy, and the countless young boys and girls running around asking for money or making sexual gestures.  The beach seemed to be full of guys wearing speedos getting massages from Thai boys wearing speedos.  

I was looking forward to the BTC conference in Thailand, but I will have second thoughts if Pattaya is the choice location.  There's plenty of other beaches near Bangkok that would be appropriate.  Alternatively, it's a very short plane ride, or a $20 overnight train-ride to get to Chiang Mai, which I think is the best part of Thailand.  It's way in the North where it sometimes actually cools down, and it's even cheaper and the people are even friendlier.  

I can't believe I'm the first person to ever mention this idea, but I can't find reference to it anywhere else on the forums.  Perhaps I just suck at searching.  I found a few similar posts, but most are based on remember-able passwords, which I am not proposing.  Sorry I've mentioned this in a few different posts, but I wanted to start a dedicated thread for wider feedback.

I would like to see the current address pool technique in the wallet replaced with a process of deterministic key generation.  The idea is that when a user first fires up Bitcoin, it will either generate a random 256-bit key for them, or the user can supply their their own random bits (flip a coin 256 times, put results in a file).  The point is for them to have a full 256-bits of entropy in this "generator," so there is no need for key stretching or any kind of salting, nonces, etc.   This would be the "master" key for that user forever (or until they decide to change it).  After that, every time the user needs a new address, the client calculates it via:


This provides a semi-infinite number of private keys that can always be recreated only from the original generator key.  Then the user only has to backup one file, ever.  Save it to paper in a safe-deposit box, or get it tattooed to the underside of your eyelid, because you never need to update your backup.

I only see three potential problems:

• (1) Weakest link would be the random number generator. 
• (2) If master key is compromised, so is every wallet address.
• (3) Weaknesses due to "relationship" of keys via SHA256

Problem (1) is "easily" addressed.   If the client creates the generator key for the user, it could go through a process of pulling entropy from mouse and keyboard events, or known physical processes that can be measured from the user's computer, such as thermal/voltage oscillations in CPU/PSU, RAM cell values after reset, etc.   The client could be set to reject anything that isn't exactly 256-bits or contains too much human-esque entropy.  The user would have to either use the client dialog for creating the generator, or figure out how to supply real entropy.

Problem (2) doesn't actually seem like much of a problem to me.  I can't think of any attack that would compromise one private key of a user and not all of them.  They're all stored in a single wallet file, and any attacker is going to copy the whole file if they get access to it.  So, by reducing your entire wallet to one private key, I'm not sure any security is lost.

Problem (3) is a problem only if double-sha256 hashing is broken, and if so, all of BTC is screwed.  It could be replaced by sha256^10 if it makes anyone feel better, or a mixture of hashes, and self encryptions (perhaps use itself as an AES password to encrypt itself before hashing).

Simple, secure, and useful.  Thoughts?

Yes, it is a deterministic wallet.  In hindsight I realize is not precisely the purpose of this original post, but it is related.  Pywallet is the perfect tool for enabling this technique.  The command line interface would look like:

   
This would calculate the first 10,000 keys based on the generator, and add them to key pool in wallet.dat.  If you run out of keys, you can re-run with a higher number, and it will add the new keys to it.  Perhaps it could eventually be included in the client so you never have to run anything:  just create your generator-key once, back it up, and the client will create endless keys from it.

You don't have to be snarky about the idea... it's simply a suggestion and you guys are a very short way from having this enabled using pywallet.py.  If you don't like it, let's have a discussion about what problems it might have and how they could be resolved.

Also, I don't know why you would question the security of safe-deposit boxes, but that wasn't the point at all.  People want to be able to backup their wallet once and know that they always have a backup somewhere they consider safe in case their hard-drive fails.  With the current wallets, they have to backup every 100 transactions.  Additionally, there is no warning when their key pool is exhausted, so there's a risk of using non-backed-up keys without realizing it.  This deterministic wallet solves a lot of problems, and I don't see where the reduced security is.

I mis-read a post by Gavin thinking he was talking about how it multi-signature tx's might be used by users, and I created some mock-ups of a potential user-interface.  I am reposting in a new thread where it is more appropriate.   I am working (very slowly) on creating my own light client, though I have no anticipation of getting it done any time in the near future.  However, I already made these mock-ups, and thought they might be inspirational for other developers who might be working on the reference client or their own clients.

The complexities of multi-signature transactions will require a very polished, clean interface for less-savvy users to have a chance to use these transactions properly.  My goal is to nail down what features (buttons, options, input validation) are needed in the GUI, and also try to converge on a consistent terminology for each of the various complexities.  For instance, I have used "distribution proposal" to denote how a user might propose a Tx spend and collect signatures from the other parties.



Full-sized image is here:  http://dl.dropbox.com/u/1139081/BitcoinImg/AdvTxDialogsFiveEx.png

It would be nice to discuss the various features presented here, figure out what is missing, and kind of vet design ideas before I get to the point of actually programming the GUI. 

Are you talking about SHA256?  The wiki is always a good place to start for that:  http://en.wikipedia.org/wiki/SHA-2

If you're talking about something more specific to BTC, there are three places that hashes are used that I can think of, off the top of my head:

(1) 80-byte block headers  {sha256(sha256((...)}
(2) Full transactions       {sha256(sha256(...))}
(3) Converting public keys to BTC addresses  {ripemd160(sha256(...))}
 

You can see illustrations of a full Transaction (2) and the conversion from ECDSA public key to BTC address (3) in my post: 
https://bitcointalk.org/index.php?topic=29416.0