I don't see why this scheme is problematic.  It's guaranteed to be at least as safe as your regular filesystem operations of modifying a file, which is already extraordinarily reliable.  Perhaps, the argument worth making is that I should avoid any "automatic" recovery based on flag files.  Luckily, I do have error detection/correction built-in, but it's not used to determine which file is potentially corrupt... maybe I should...

So is there a scheme that is guaranteed to work?   I mean, I'm not sure how you could guarantee ACID-based DB operations if you can never count on in-order filesystem ops.

I don't know if wallet corruptability problems still exist, but 6 months ago when I first got in to Bitcoin, I was constantly getting corrupted wallet files.  Probably due to the client or OS crashing, somehow getting interrupted during an update.  Gavin even wrote a tool to help recover corrupted wallets... instead I pulled all the keys out of my wallet and decided I was going to make my own client

I completely agree with this.  I think it's much more important to have a "transparent" wallet, than one that is easily corruptable in a DB format.  Of course, the benefit of the DB is the fact that I should have ACID operations (guaranteeing integrity of changes even if the computer loses power at the wrong time).  But there comes other problems, like the fact that the DB doesn't necessarily overwrite data you wanted to remove:  I was actually the one that discovered the bug of unencrypted private keys left in your wallet after encrypting.

I will be releasing my client soon (Armory), and I decided to go the polar opposite route.  Flat, transparent, binary file, with in-place operations for encryption, and a synchronous backup that is updated with the main file in such a way that I can always tell if one is corrupted and which on it is.   It was a bit of work getting it together, but I think it's critical that any wallet-file implementation have such atomic operations -- I would agree with Berkeley DB for this reason, except that it seems to get corrupted all the time, anyway.

Specifically, I have file A and backup file A'.  Every time I modify A, I first make sure A and A' are the same, then I touch a flag file to identify I'm about to modify A.  Once A is done, I write a flag specifying I'm about to modify A' (identically), remove the flag for A, and then start modifications of A'.  Once that is done, I delete the last flag.  If the computer crashes during update of either one, I will see the files are different, and see which update flag is there to let me know which one is corrupted.  Then I just restore from the other one.  (and I never give the user any data until the whole operation is complete).

As for the topic of too many keys... I don't know how many bytes are stored by the Satoshi client for each address, but Armory uses 237 bytes... which means that if I get a million customers (which is ludicrous), I will be at 237 MB of storage used.  And anyone processing that many transactions will have dozens of GB of RAM on their system, so they will have no problem keeping it in RAM, much less keeping it on their HDD.  I imagine the Satoshi client is on the same order-of-magnitude...

A couple months ago, I extracted all the non standard scripts in the testnet blockchain.  There's some pretty interesting ones:

https://gist.github.com/1329788

However, there's no guarantee that each TxOut is spendable, so, only the ones that have corresponding TxIn scripts spending the TxOuts should be used.  Luckily, if it's a non-std TxOut script, there's usually a non-std TxIn script to spend it, so they should both be in that list.  Since TxHashes are listed you can do a search for matching scripts...

Of those, I extracted three for my unit tests (in Armory):

https://gist.github.com/1421550

That is the complete debugging state at every step of a 2-of-2 and 2-of-3 (with addr-verify but no OP_CHECKMULTISIG) and another 2-of-3 that does addr-verify and uses OP_CHECKMULTISIG.  Not only do they make good unit tests, but the debugging states are great for seeing how these scripts actually work. 

Keep in mind, those multi-sig txs are not the "standard" multi-sig types that will be in the upcoming client releases, but they will stress your script processor, and they are correct since they were accepted by the Satoshi client on the Testnet.

-Eto

I don't quite agree about falling between two stools.  The benefit of this implementation is that private key data never touches your hard-drive, encrypted or not.  This is a nice benefit for the ultra-paranoid.  Honestly, it's not a feature I really want for myself, but I've seen enough people muttering about how they wanted it, so I decided I should support it.

But I suppose I could implement it with some extremely high requirement on entropy of their passphrase.  Or use a much shorter chaincode to help prevent collisions.  Or force a passphrase on the user that has the desired entropy, and they won't have a choice about it. 

As I said before, my codebase has the flexibility to use either deterministic, or PRNG chaincodes.  I can just revert to using a deterministic value in case the chaincode is not specified.  You're right I don't have great reasons for needing them to be random, but I built the code so I can go either way. 

As for the argument about creating phone keys on the phone, I guess it's not actually that hard.  Most smartphones have a built-in share/email function:  I could use the phone to create the wallet, then email myself the watching-only wallet to get it onto my primary computer.  This would be less convenient, but it would prevent the private keys from ever being on the same system, and it would be a one-time thing.

But I also have no experience with Android/iPhone apps... I'll have to leave it to someone else (for now) to actually execute the phone-part of this idea.  If anyone is interested in developing a sister app to close the loop on this functionality, I'll be happy to give a tutorial on Armory wallet files, algorithms, BIP 0010 details, QR codes, etc.  My first release next month will have all the computer-side code needed... even the multi-sig support is implemented, it just needs some testing.

As I write out my arguments, I realize that this isn't really a feasible situation.  You still have to use hashing in order to convert public keys to address strings.  Additionally, sha256 is an extremely compact algorithm, both in terms of space to implement, and RAM to run (hence why it's so good on GPUs).  In reality, the ECDSA operations are quite heavy in implementation and computation... I can't imagine a device that could do ECDSA but not hashing...

Then of course, I don't have much experience with microcontrollers...

There's a lot of stuff it could do, but not implemented yet.  However, accessing it via Python CLI gets you just about anything you want in the blockchain.  It could easily be ported to support piping from regular CLI, but loading the blockchain every call would be slow.  However, my current focus is on full-fledged client with all its innovative features.  But I don't want to get too derailed on that... (PM me if you want more info about how you might use it). 

The point was that for importing new addresses, it helps to be able to do a full blockchain scan for its balance in reasonable time without contacting a separate service.  If one is going to implement an "import private key" function, you should be able to tell the user, in a reasonable amount of time, what is that balance of that key.  In this case, a separate client that uses none of my code, could still make a dll/system call to my library, which will load the entire blockchain from disk and scan for a full list of TxOuts, within 20s. 

On that note, I would argue I didn't exactly reinvent the wheel.... the Satoshi client is a wheel that spins at 1000 RPM permanently attached to a satoshi axle.  My code is a wheel that spins at 10,000 RPM and can be used with any axle.  I'm not sure it's possible to do (single-threaded) blockchain scanning any faster (after all, I am an expert on C++ data structures).

I'm one of those developers!  I'll be releasing a client in the near future, and I can pretty easily support Firstbits.  And with the full-RAM version of the client (that holds the entire blockchain in RAM), I can resolve a firstbits address in 0.5 seconds without contacting any server... pretty slick

I went to the firstbits site but didn't see the technical information I needed to be able to implement it.  Any links?

Btw, my client will have a completely decoupled blockchain interface and wallet.  In fact, you don't even need to wait for Armory to be released, because you can already use the full-set of blockchain tools that I have, written in C++.  https://github.com/etotheipi/BitcoinArmory/tree/master/cppForSwig  It's a ton of code, but it can all be boiled down to a small interface of a couple-dozen calls.   It can do a full blockchain scan from cold boot in about 20s (collect all tx for any address directly from disk).  PM me if you have any interest in leveraging it.

Bytecoin asked me a question about why not use a deterministic chaincode in the wallet design.  I think it's worth discussing in the open, so I hope he doesn't take offense that I am replying to a PM, here.


I had thought long and hard about using a deterministic chaincode, because it cuts in half the amount of information that is needed to restore a wallet.  But ultimately I decided against it for three reasons:

• (1.) Take the case of a determinstic chaincode based on public key or first address:  this is actually a non-starter, because it means that anyone who has access to your first public key can immediately link all your transactions/addresses together.  You completely lose anonymity/privacy.  So you say, well how about making the chaincode based on your private key?  
• (2.) In the near future I plan to support "brainwallets": where your private keys are uniquely generated by your passphrase (passed through a KDF).  This has the benefit that no private data, encrypted or not, ever touches your harddrive.  As such, your private key is actually kept "in your brain."  However, I cannot allow them to be based PURELY on the passphrase, or else you will have multiple users generating identical, way-too-simple passphrases, and end up "sharing" wallets.   Additionally, it allows someone with a lot of computing power to start generating millions of wallets based on simple passphrases and eventually "colliding" with other users' wallets.  Sure, my KDF is hardc0re and will help prevent this, but the attacker gets to attack all brainwallet users all at once by doing this, which is a profitable attack.  Thus, I need the extra entropy provided by the PRNG-generated chaincode.
• (3.) The solution I implemented is more versatile.  If you like the deterministic chaincode, then you can still use it... you just calculate the chaincode from the private key and plug it in instead of using a PRNG.  The real pain would be if I implemented the simpler solution, did not put chaincodes into my wallet format, calculations, etc, and then wanted to upgrade to use it later.  I'm saving myself a lot of trouble in the future if I ultimately decide I do need them to be part of my design (and I do want brainwallets).  This is also why I left plenty of space in my wallet format for extra flags, just like the BTC protocol has.

EDIT:  I suppose a 16-byte chaincode could've been a good compromise...

This is actually a very good point.  It's not a situation I would normally consider, but one of the benefits of BIP 0010 is that extremely lightweight devices can be used for signing -- why not make that a little easier if it comes at no cost to security?  Most likely, this is another use for the spare flags in the wallet file.

I think it's much easier to get data from the computer to the phone (via QR codes) than the other way around.  100% of phones that support Android/iPhone apps have a camera.  Not all computers do.  Manually typing in this data is tedious, even for 64-bytes.  I should know... I've done it quite a lot while testing wallet-restore in my client...  it would get quite a bit more cumbersome with TxDPs that are hundreds of bytes.

I had pondered ways that you might be able to exchange data by text message or email (I'm desperately trying to avoid third-parties).  The problem is, I don't want to get in the business of monitoring peoples' emails or personal data.  I just don't want to go there.  And no matter how you look at it, you're going to need a private key on both devices, so I don't see any benefit to switching the order of operations -- both devices have to be compromised in order to lose your wallet, and I'm not particularly concerned about the initial wallet creation being compromised, as the private keys for B never have to touch the hard-drive.

Netrin, I sympathize with your arguments, but I can't concede to them.  As an application developer where I will be implicitly responsible the for well-being of a lot of peoples' money, I just simply cannot do it.  It's not to say that it shouldn't ever be done: maybe another developer would have the patience and creativity to design such a system and add more value than risk, but that's not me.  When something goes wrong, my fault or the users', I'll still be dealing with it.  And I will deal with it by putting in the 90% solution as we just discussed... so far I haven't been compelled by this discussion otherwise.

But it's not a lost cause for the argument you made.  Yes, throwing away the key is strange.  The default for "sweep" will be to for them to put in the private key, the client sweeps it, and then it's never seen again.    But that's not really the end of the story... the user still has the private key.   If they disagree with the fact that they don't have the option to sweep and import... then just run the dialog again and make it a permanent part of your wallet.  Done.   

So my client effectively "supports" that option and advanced/smart users who want this behavior can get it.  I just refuse to directly support/encourage it, because as has been described above, it opens up much more risk to the user than the value it adds.

Don't forget that GPUs are not the only way to contribute hashing to the network.  FPGAs really cut down dramatically on everything you mentioned in your counter-arguments.   Sure FPGAs are much more expensive material cost, but you avoid most of the problems above, or at least a couple orders of magnitude of such problems.  You're probably cutting down energy consumption and heat by a factor of 20.  And with a really creative setup, you can probably get many dozen FPGAs onto a single computer (especially since the bandwidth required between CPU and device is basically negligible).

Yes, still requires a lot of work, but probably an order of magnitude less work.

My only concern with this is that it does leave open an attack vector for the person who gave you the key.  By importing that key into your wallet permanently, it's funds look like they belong 100% to you.  The person who gave you that key, can then send you money to that key to make you believe you received it, and then transfer the money back to themselves once the exchange is complete.

You could argue for an "auto-sweep" function/option, but I am not fond of any kind of automated transaction... anything that moves money when the user isn't looking, especially when it might require a tx fee, is asking for people to stop trusting your software.  Not to mention, I would have to create a new class of keys/wallets in my software to handle "kind of trusted" private keys, and it would confuse users who now have to understand this new class of information.

I prefer the option of sweep once, throw away the key.  If the user is importing an untrusted key to be used once, then they should only use it once to sweep, and not leave themselves open to such games as above.  Otherwise, it leaves the door open for not-even-so-creative attackers to plant a key in your wallet that they own, and then start pulling your funds out from under you when you use it for other transactions.  By throwing it away, we avoid the mess entirely.

It depends what kind of tree structure you're using.   If you keep a tree of every address as the key, and a list of block numbers as the values, then a trie/patricia tree will have constant access time (actually, a function of the length of the addresses).  But, it requires prefix searching and C++ doesn't have this kind of tree available in the STL.

So I have to settle for map<key,val> which is a binary tree ~ O(log(n)).  But in the grand scheme of things O(log(n)) is much "closer" to O(1) than O(n).  In this application, it's probably indistinguishable.

I don't disagree with you, and my goal for the first release of Armory is feature-based proof-of-concept, with no concern for how heavy the client is.  In the future, I will be converting to index-based approaches, as you suggested.  I actually already have a method for indexing all addresses, I just don't have it integrated as the "go-to" source of information for addresses.  That will be investigated for the next release.

But it doesn't change the fact that is still works right now, and even it's 30s-60s for a scan, it's a still "workable" as a client feature for users that want their money.  If someone wants to use the library in their own client for this purpose, I can help them get it integrated/linked.

This is a good discussion, and thanks for letting me know how I can add $500 income to my first release of Armory.  I hope that bounty is still valid   But I'm also interested to converge on a good way to "responsibly" implement these features...

Regardless of the Armory software itself, I have proven with the PyBtcEngine/ArmoryEngine that it's possible to scan the entire blockchain for a new address within a reasonable amount of time:

• If you're holding the entire blockchain in memory, the code can find all transactions in less than one second. 
• If it's not in memory, then I can load the blockchain from disk, index it, and scan for the address in less than 15s.

(the top-layer is Python, but I have a super-optimized C++ layer doing all the blockchain operations).

It might be possible to wrap the C++ engine and link it as a dll, purely for doing these types of scans.  It sidesteps a lot of the issues expressed in this thread (in the medium term, when it's still feasible to hold the entire blockchain), as you don't have to trust anyone more than you trust the blockchain itself in order to find and sweep funds for a given address/key. 

As for the Armory software itself, I already have the ability to import external private keys, and appropriate warnings have been displayed on the import dialog.  You can always add a new wallet just for importing untrusted private keys, though I recognize that it can still be dangerous for folks who don't quite understand the under-the-hood stuff.   The default behavior is to import the key as a permanent address in your wallet, but after reading this thread, I might make "sweeping" be the default behavior.  I might also move this feature to the "advanced" mode.  Recommendations are welcome.

Keep an eye out for Armory which is a client I've spent 6 months developing, and should be released (alpha) within the next month.  Among the plethora of fantastic features is that it uses Type-2 deterministic wallets for everything, and it gives you an option to print a paper backup of the wallet when it is created.  And because it's type-2, it also supports watching-only wallets, so that you can create your offline wallet, make a no-private-key copy of it, and use it to generate addresses and monitor transactions from an online computer.

Teaser:  below is a screenshot of Armory's paper-backup dialog -- yes, it only needs to be backed up once (unless you manually import addresses)


At the moment, it's about as far from lightweight as it can get.  But the current goal is proof-of-concept of the features, and I have a development plan to scale-down/fork a "lightweight" version, and eventually release a sister Android/iPhone app. 

P.S. - It will be open-source (AGPL v3) and the code can be found here.  (trying to drum up some hype for it before the first release)

I have the solution for most of the concerns presented here and it's not terribly difficult in concept, but one does need the infrastructure in place in order to impelment it.

Luckily, I'm going to have 90% of this problem solved with my first release of Armory next month, and hopefully the full solution implemented by v2.0... whenever that is.  There are three key things that make this possible:

(1) Deterministic wallets that can be extended by someone without the private keys

• The determinism of the wallet comes from the public key, not the private key.  In the case of Armory, a chain code xor'd with the 32-byte hash of the public key is used as the chain to the next address:  multiply the private key by this number mod N (order of the group) and you have a new private key.  The benefit is that someone holding just the public keys can still predict/generate the address chain, but can't spend the money (they EC multiply the public key by this number which they can compute if they have the chaincode)
• This allows someone who has only the chaincode and the public key, to produce the next public key/address in the chain.  This means that my computer can generate addresses for my phone wallet, without actually having access to the phone wallet keys.  If my computer is compromised, my phone isn't.  

(2) BIP 0010 or some variant thereof.

• BIP 0010 solves a lot of problems in this area of BTC.  It is targeted at multi-sig transactions but actually works for any kind of transaction.  The critical benefit of BIP 0010 is that the other parties signing the TxDP do not need the blockchain.  
• In this case, it would be your phone.  Your phone only needs the private keys/wallet, an ECDSA module and the TxDP, and it has the capability to present the tx to the user, ask for confirmation, sign the TxDP, convert it to a completed transaction and broadcast.  This enables key-storage on just about any kind of device that can do ECDSA, which is a significantly broader subset than the one that can store and process the blockchain.
• This works just as well for offline wallet transactions as well, which is why Armory generates all transactions by going through a TxDP:  if it's got the key to sign it, it does... if not, it presents it to the user who can copy the TxDP to the correct computer/phone/email of someone who does have the private keys.
• I really hope to see BIP 0010 expanded and implemented (in some form) because of its extreme versatility.  There's nothing stopping someone else from making an Android app that implements BIP 0010, and then can use their app to sign TxDPs from Armory.  (in fact, I hope someone will, so I can avoid making the app myself -- this is the 10% I'll be missing in my first release).
  

(3) Paper backups

• This is exactly as it sounds.  Generate your wallet, print off a "paper backup" and scan it with your phone to absorb the private keys.
• This also means that for non-third-party WPS, you dont' actually need a C party... you simply backup A and B to paper
• The screenshot from Armory shows the ideal form of paper backup for my deterministic wallets:  allows you to recover your keys if the wallet is lost, or transfer to another device (especially easy if it reads QR codes).

Putting it all together:
(1)  Computer creates new wallets A and B.
(2)  Computer prints paper backups for both A and B
(3)  Computer deletes private keys for B
(4)  Phone scans QR code on paper backup for B to absorb the wallet.  Phone does not need blockchain
(5)  Paper backups are stored in a safe or safety-deposit box

Now, you make sure that all your money is encumbered by a 2-of-2 transaction using A and B.  To send money:
(1) Computer generates appropriate TxDP spending the 2-of-2 transaction.
(2) Computer signs for party A
(3) Computer converts partially-signed TxDP to QR code
(4) Phone scans the QR code, and displays the transaction to the the user
(5) The user accepts the transaction, and the phone signs and broadcasts the transaction.

If the computer HDD fails, or the phone is lost/stolen, you still have both A and B backed up on paper and can still access the funds.  So you get all the benefits of WPS, without a third party, and using only a 2-of-2 transaction, which will already be supported by the network in the near future.

QED



(P.S. - This is a testnet wallet, so don't get excited trying to recover the 2.35 BTC in it )

Here's exactly how the Tx is laid out: 
https://bitcointalk.org/index.php?topic=29416.0

That should be the same as show on the protocol wiki, and is the same as it's stored in the blk0001.dat file and also as it's sent over the network.  Once you have that in binary form, apply sha256 twice to get your final answer.

If you want to hash a Tx for ECDSA signing/verification, that's a whole different story (although, the link above also shows how to do that, too).

Thanks!   And sorry, I can't resist but to send the $0.60 worth of BTC for helping me out

Can someone please mine 1-2 testnet blocks?  I need to get my tx's into the blockchain so I can start testing my software...

This post was faster than figuring out how to set up mining locally.  (and please no comments about testnet-in-a-box... I know it's there, but really I have everything I need on testnet if I just get these tx into the chain).  

0.2 BTC bounty!