So I've been mulling pieces of this idea for a while and finally found a way to make it click.  I will use simplified system with example numbers for clarity of explanation, but if of course it's all configurable.

Situation:

• User has encrypted wallet, but can't remember the passphrase.  And no paper backup, of course. (Assumption: they know something about their passphrase, just not all of it)
• Will pay some amount for individuals with significant computing power to help brute-force the passphrase.
• Doesn't want to give the whole wallet to brute-forcers because they can just take all the funds when they find the passphrase
• Brute-forcer should be able to prove they found the passphrase without giving it away
• If they can prove that they found the passphrase, they don't want to simply give it to the user, because the user might not pay out

My solution has the following CONOPs (concept of operations):

• User's wallet is setup to save extra data about the passphrase that does not compromise its security or the benefits of keystretching.
• User distributes an encrypted test string that is half known data, half secret data (perhaps in a forum post)
• User also provides a description of what they know about the passphrase
• Brute-forcers will test passphrases until they find one with the correct prefix (the known data).  At this point they have the secret data.
• Brute-forcer will send the user their address using the secret as an HMAC key, to prove that he found the passphrase
• User verifies HMAC and constructs a finder's fee tranasaction to the brute-forcer that requires both their signature and the encryption key to redeem it.

Yes, the encryption key goes into the blockchain -- it's the only way to claim the coins.
Therefore, zero trust is required to exchange the private key for a finder's fee!

Details:

Assume simple key-stretching that produces an encryption key from a passphrase by simply doing SHA256^1,000(passphrase).  The specifics of the key-stretching don't really matter -- this can be adapted to any key-stretching scheme.   When the user sets/changes their passphrase on their wallet, it will encrypt the private keys using AES256, using key = SHA256^1,000(passphrase).  The wallet will additionally save the following three pieces of information with the wallet:

• plainTestStr = "WalletTestString" + SecureRandom(16))
• encrTestStr = aes256_encrypt(SHA256^1,000(passphrase), plainTestStr)
• revealKeyStr = SHA256^1,002(passphrase) = SHA256²(key)

When the user forgets their passphrase, there will be a way to pop up a recovery window, where they can describe everything they know about their passphrase.  It will then generate a message that says something like the following, which can be posted on a mailing list, forum, etc:


The brute-forcer will test passphrases until they find one that decrypts the test string to "WalletTestString87cca180a167".  The brute-forcer then constructs an email or forum message reply:


Where the hex at the end is

(the first hex arg is the secret part of the test string)

The user will plug the message into their wallet app which has the encrypted wallet they can't recover.  It has the 87cc verification string stored in the wallet (but was never revealed to the brute-forcers), and then they use that to verify the HMAC.  This proves that the person found the passphrase and proves they want the funds send to 1xK39z375mPHn7aa.  

Last step: the user constructs the following transaction TxOut script, for 25 BTC:


NOTE: It's not the passphrase that the claimant puts in the script, it's the actual encryption key (SHA256^1,000(passphrase)) that they put in the script.  Then the script will double hash it to get SHA256^1,002(passphrase) and compare to the target string.  SHA256^1,000(passphrase) must be stored in the wallet at encryption time, in addition to the test string.  Note that you don't lose the benefits of key-stretching because the SHA256^1,000(passphrase) has the full 256-bits of entropy.  It's still quicker to brute-force the lower-entropy passphrase hashed 1,000 times, than brute-force the 256-bit key without any hashing.

The user can redeem their coins (in the event they're not claimed) by simply putting "OP_0 <SigUser>" into the spending script.  
The brute-forcer can redeem the coins by putting "<HA256^1,000(passphrase)> <SigBruteForcer>" into the spending script

Welcome to my office:



Just gotta keep the door open at the proper angle or else it doesn't look right

Whoa, how'd you do that?  Isn't that the ramreduceleveldb branch?  2.7 hours is almost twice as fast as my system did it!  Do you have an SSD?  I ask especially because 14 GB seems too low.  Did you scan the whole blockchain up to like 257k blocks?

No detail is too small for me   Glad to see people appreciating the time I put into those details!


Still a 2 BTC bounty available! (I'm looking in goatpig's direction).

I've determined that I don't care what version of MSVS is used for compiling the C++ side of Armory.  I've been meaning to upgrade to MSVS 2010 or 2012 anyway... if someone gives me a solution using one of those, you get the 2 BTC.  The "checkout" criteria for the bounty is that the project must successfully compile leveldb (or I must be able to do it myself), and then it must link properly to the code in the ramreduceleveldb branch.  And of course, some documentation on how it was done...

The reason I haven't upgraded to MSVS 2010 or 2012 is because there's a bit of pain doing so (like MSVS 2010 now supports the equiv of <cstdint> in Linux, so it complains about my redefinitions).   Whatever, if someone can take a shot at it, or at least give me a partial solution, you get part of the bounty!

UPDATE:  Plan B

Unfortunately, there was just too many problems with super-node Armory.  LevelDB has been extremely inconsistent in keeping up with the stress of constantly updating address ledgers.  On slower systems, I observed random "missing tx" messages and seg faults on one run, then I would re-run on the same data and it would cruise through that part.    I cannot attest that my code was bug-less (though, there's like 2,000 lines of unit-testing code to test the new database stuff, including re-orgs).  But it appears that I cannot worry about code bugs if it's not going to work even without those bugs.

Super-node Armory is likely to be put on hold for a while.  Now, I know that sounds like it's going to be a serious disruption to my progress...

---

The good news:

All of the modularization I have put into Armory just paid off.  Tremendously!  In 8 hours I was able to swap out the super-node DB operations with something that resembles the previous version, but without super-node capability.  Super-node code would process all the headers, find the longest chain, write out all the raw blocks to disk, apply all the blocks (updated addr histories, mark TxOuts spent/unspent, etc), and then grab all the transactions relevant your wallets and scan them.

Now, it skips the "apply blocks" section entirely, and does a blockchain scan on the raw blocks in the DB to find all the transactions relevant to your wallets.  It injects them into the wallet and everything operates the same!  In those 8 hours, I now have a mostly-working version of Armory that rescans the blockchain on every load, but has the database backing so that it uses dramatically less RAM.  Also, it will be trivial to save the registered tx data between loads, now, so rescanning will only be necessary on the first load or import/restore wallets.  When I originally tried to do this, there was too many subtle issues with where the transactions were on disk, swapping blkfiles/homedirs, etc.  With Armory managing its own database, it can do this reliably now!

I am in the process of reverting many of the skip-this-operation-because-not-needed-for-super-node operations to the old way, so that it still pops up with all the original warnings about needing rescans etc. This should be done today, meaning it only cost me two days to do a major operational shift!  

If you want to play on the new branch, it has been renamed rrld_planB.  It is a fork of ramreduceleveldb, which I wanted to keep around for when it's time to revisit super-node Armory.   Still some UI feedback issues, and doesn't handle being interrupted on the initial build, but it is usable on Linux for simple use (and testing!).  

Stay tuned!  

That's not even possible.  The github repo is public and forever.  And even if it went away, any version created in the past 2 years can read your wallet, so you'd only need to find one person who has an old copy of Armory.  AND, the wallet format is public: https://bitcoinarmory.com/armory-wallet-files/

There's no way to make you cry

You can't create transactions in offline mode.  That's why the offline computer setup needs an online version of Armory to create the tx for you.  It needs to be online to know what coins you have so that it can sign them.  Technically, even brief access to a computer able to run online Armory would be sufficient - import your watching-only wallet, create a tx that sweeps your funds to another non-Armory address, then take it to the offline computer for signing.

If you're not even using online-offline split, you can do this with your primary wallet (without any extra steps between creating and signing), but I would try to limit the number of devices that your private keys have touched.

In the next couple days I'll have something that will help you get your coins out of Armory.  This week I finally converged on a working DB system and it requires less than 300 MB RAM to run.  A version is currently available for linux that works if you wait 4-6 hours for the DB build (done once).  I'm in the process of trying to get it running on Windows, but Windows isn't playing nice.

Be patient just a couple more days!

BACKUP CENTER MERGED:

I have merged the new backup center into the ramreduceleveldb branch.  If you went to the Bitcoin conference and you saw the fragmented-backup and SecurePrint demos, then you already know what's there.  Please test it!   (p.s. new backups now only have two lines of data to copy/print!).    There's still a few quirks that need to be fixed, but it's just about fully functional.

At the moment, it looks like Armory is "usable" in Linux.   The biggest problems remaining are:

• (1) Lack of interface feedback on initial blockchain build.  Just wait 4-5 hours, don't worry if it looks like it's not doing anything.
• (2) Slowness and a screen full of harmless errors and warnings on load -- if you shut down Armory and start it later, it can take a couple minutes to sync with the latest blocks.  Will have to investigate, since it clearly builds the database much faster than that on an initial sync.
• (3) Restored wallets appear to have incorrect balances until you restart.  Luckily, restarting only takes about about 5 sec now

I will track down some of the slowness issues later, since it technically works right now.  At the moment, have a long list of tweaks that have been waiting a few months to go in, and a few quirks to fix in the backup center.  Please keep testing!  (if you can)

Awesome!  Finally some encouraging news on this front.  I don't know how I missed the leveldbwin project...

Fixed the wallet balance issue.  What a strange bug!   If you saw strange balances, it should be resolved when you pull, recompile and run.  I finally get all the right balances on all of my wallets, and I have some pretty active wallets! (stretching back 2 years and hundreds of tx).

It appears to work, strictly speaking.  A couple things to note:

(1) There's clearly a very large inefficiency in startup.  I already noticed it rewrites the entire headers DB on each load -- which is actually not that slow, but it's also unnecessary.  Similarly, it reapplies a bunch of block on each load even though it isn't supposed to.  Neither of these cause inaccuracies, but they do slow it down dramatically and represent issues to be to be fixed.
(2) It appears that the new backup stuff was merged before the latest version.  I might merge the latest backup stuff ASAP so that people can test it, then I'll work on fixing #1

Getting closer!  At least I think I have all the issues contained.  Except for that battle with leveldb+windows.  Btw, I'm still offering 2 BTC to anyone who helps me get leveldb built in Windows and integrated into my project.  It is remarkably unpleasant.

Quick update:

• With snappy, my last rebuild took 4.5 hours after deleting the .armory/databases directory.  There's a lot of room for improvement on that one, but a lot of the options are kind of heavy changes, and it's not critical for stability.  I'll try now it without snappy and see if it improves.
• Displayed balances are really incorrect when used on mainnet.  Perhaps it has to do with length of history.  But luckily, it's an "aesthetic" error -- I just confirmed that the raw DB entries are 100% correct, the interface is just reading the DB incorrectly.
• You can expect a whole bunch of errors and warnings when you restart, because my code accidentally rescans the last few blocks and then triggers those log entries because things that it's expecting to be unspent are already marked spent, etc.

And most importantly:

• Armory uses 288 MB of RAM after the DB build is complete (on Linux).  That's means that Armory online mode should be usable on even a lot of older hardware!
• There's a compile-time configurable parameter to adjust how much RAM is used when it's building the DB.  Right now, it's set so that it won't use more than 1 GB of RAM while building.   I will make that run-time configurable and do some testing on it RAM-vs-performance.

The documentation suggests that most applications will benefit from it, and that it's very lightweight and much faster than most file I/O operations so it shouldn't hurt you in terms of performance.  I guess that's why it's enabled by default.  But Bitcoin is special in that the blockchain data is very dense and hardly compressible.  I had suspected it would be of no benefit here and thus no reason to use it (and meant the baseline to disabled it).  I didn't realize it would actually hurt you!  Yeah, good to know...

Oh, duh.  I'm not! (or rather, I didn't mean to)  I committed leveldb as part of the project for that reason, and it should be part of the (poorly made) Makefile.  Perhaps I am building leveldb but actually linking to the system libraries by accident.  I'll check.

Also, I thought I had disabled snappy.  But perhaps I didn't.  I assumed the linker error could happen even when you weren't using it.

EDIT: Okay I misread the documentation, I didn't realize it uses snappy by default.  I thought I had to tell it to use it.  I guess I never got around to testing with and without.  I'll disable it and see if I get a performance improvement.

That's not strictly true, here, since i didn't giveyou an installer.  If you have previously compiled the project and then checkout the new branch and/or pull, it will update the code, but you might have to do a "make clean; make" from the base directory to get it to discard the previous binaries and recompile all of them.  You may know this, but I've frequently forgotten to recompile after pulling an update and been confused by the errors that look like what you just showed.

However, it's also possible that when Gentoo installs leveldb it does not install the snappy compression library which is needed for leveldb.  While trying to get leveldb working I've seen that topic come up a few times even though I didn't have the problem myself on Ubuntu.  But it might be an issue on other system.

Did you recompile?  Also, did you install the libleveldb package?

Unfortunately that is actually a bitcoin-qt problem that cropped up today.  From the mailing list:  prepare for some turbulence.


You'll have to turn off auto-bitcoind in the Armory preferences and run it yourself using the checklevel command.  I did that today and it worked fine.

ARGH.  I somehow reverted one armorymodels.py to the pre-leveldb version.   Just about to commit the fixed version to the ramreduceleveldb branch.

The log file you sent indicates you're still on version 0.88.2.  But if you were on the ramreduceleveldb branch, it would say 0.89.95.

After battling multiple issues destroying mainnet DB (all user error), I did notice that a bunch of my wallet balances were totally wrong on mainnet, but not testnet (frequently reporting "total received", not "current balance").   I confirmed that the DB actually has the correct data, and the GUI just happens to be reading it incorrectly.  Not sure why I'm not seeing the problem on testnet, but at least it'll be easier than tracking down a DB error...