This is looking good!   

A couple questions/comments.

--GPG keeps the armored blocks to 64-characters wide, not 80.
--Does this do proper dash-escaping? 
--Handles newlines properly?
--Signs the non-dash-escaped, windows-styled-newline string, or something like that (I don't remember the details, that was your job )
--Make it say "-----BEGIN BITCOIN SIGNED MESSAGE-----" and "-----BEGIN BITCOIN SIGNATURE-----"
--Is the v1-Base64 you identified correctly?  It says "BEGIN SIGNATURE", but it should probably be "BEGINE BITCOIN MESSAGE", I assume the text and signature are both bundled in there.

And these signatures use the key recovery?  I assume that's what the 1+64 bytes comment is. 

I really did want python signing.  But I was saying I would pay an extra 0.5 BTC to additionally implement key recovery in cppForSwig/EncryptionUtils.cpp using Crypto++, but it's not strictly necessary or part of the original bounty.

My point was you don't need any pointers at all, and finding the children isn't actually that long since the database is efficient at these kinds of operations.  If you are node "ABCD" and want to go to pointer P, you don't need a pointer to know how to get there.  Just iter->Seek("ABCDP") and you'll end up at the first elemtent equal to or greater than it.  At the deeper levels, the iterators will efficiently seek directly in front of themselves, and may already have your next target in cache already. 

If it starts with "ABCD" you know you are still in a child of ABCD, and if not, you know you are in a parallel branch and can finish processing the "ABCD" node.  Yes, there may be a lot of seek operations, but with the built-in optimizations, there's a very good chance that they will be fast, and because it's a PATRICIA tree, you'll rarely be doing more than 6 such operations to get the branch updated. 

On the other hand, I haven't thought this through thoroughly.  I only know that it seems like you can avoid the pointers altogether which I was expecting to make up the bulk of the storage overhead.  i.e. each node currently will only hold a sum (8 bytes) and its own hash (32 bytes).  If you need the pointers, you could end up 256, 8-byte pointers per node in addition to it, which is actually quite heavy at the higher, denser levels. 


There's a liitle room for negotation on this topic, but ultimately and "address" is a TxOut script.  In a totally naive world, your "addresses" would just be the exact serialization of the TxOut script -- so a 25-byte "address" for each standard, Pay2Hash160 script.  Or 35 or 67 for pay-to-public-key scripts.    23 bytes for a P2SH script.  And then anything that is non-standard would be simply serialized raw.

However, I don't like this, because a single address ends up with multiple equivalent representation.  Even though pay-to-public-key scripts are rare, there are addresses that use both (such as multi-use addresses that were used for mining and regular transactions).  Even though it's rare, you'd have to ask your peers for 2 different scripts per address (the Pay2Hash160 and PayToPubKey scripts).  I'd almost prefer making special cases for these addresses, given that they are so standard and fundamental to Bitcoin transactions.

So, I would vote for:

{Pay2Hash160, Pay2PubKey65, Pay2PubKey33} all be serialized as 21 bytes:  0x00 + Hash160.  Any Pay2PubKey variants will be bundled under that single key.
{P2SH} scripts will be serialized as 21 bytes:  0x05 + Hash160{script}. 
{EverythingElse} Will simply be the raw script. 

One problem I see with this is that it doesn't make it clean to adopt new standard scripts, without reconstructing the database in the future.  I suppose it wouldn't be the end of the world, but we also don't want to make an inflexible protocol decision.  This isn't just personal preference for storing address/scripts, it's actually describing the authenticated structure of the Reiner-tree.  So if we would be adding a new std script type, and we'd want a short form of it to store in the DB, we'd have to update the "protocol".  If this had been adopted already, that would be a hard fork.   If we just do raw scripts all around, this isn't really a problem, except that we may have to ask for extra branches to make sure we get all possible variants of a single public key.

---

@ ThomasV

I noticed you asked something about "SumValue" before.  I don't know if you got the question answered, but the idea was to recursively store the sum-of-value of each sub-branch, and have it authenticated along with the hashes.  Quite a few users, including gmaxwell (who was original only luke-warm on this whole idea), determined that was an extremely valuable addition to this spec to deal with miners who lie about their reward knowing that the network is made up almost entirely of lite-nodes who have no way to determine otherwise.  But those lite nodes know what the total coins in circulation should be, and thus would only have to look at the root-sum-value to determine if someone cheated. 

I don't know if I completely captured that concept.  I'm sure someone like gmaxwell or d'aniel can jump in and explain it better.  But it is an easy add-on to the original idea.  And also makes it possible to simply query your balance without downloading all the raw TxOuts (though, if you are using each address once, that doesn't actually save you a lot).

Crap.  I hadn't considered the fact that the ECDSA keys could be used in conjunction with OpenPGP.  I actually just wanted the message formatting/armoring, which could then be signed with a Bitcoin private key exactly as Bitcoin-Qt does it now.  But I never wanted interoperability with OpenGPG.  On the upside, you may have already finished this, actually.

Right now, Bitcoin-Qt takes in a message and a private key, and spits out a bare signature.  Verison 0 matches that.   Right?  I assume you tested that it's interoperable with Bitcoin-Qt.

Version 1 would instead spit out an ASCII-armored block that follows RFC 2440 formatting, and only the part specified by RFC 2440 would be signed, but it would be signed "the Bitcoin way."  Which is to HMAC it with "Bitcoin Signed Message:" and sign the result just like you would sign a Bitcoin transaction.  But the signed text and signature would be included together in a single block, using dash-escaped formatting.  Even if there's a slight variation between making a Bitcoin signature fit/make sense where an OpenGPG signature would go, that's fine.  The goal was just to have the message encoding and data-to-be-signed serialized the same way.  Please don't spend any more time digging into OpenGPG. 

Can you post a few examples of what you have?  Specifically, what the input and output looks like the way you have implemented Version 1 (for both Base64 and clearsign)? 

LvM, I don't know what the problem is.  That protocol page very precisely lays out all of the serializations of block data and messages.  And it's accurate.  Everyone who has developed any Bitcoin software has used the information on that page, and errors subsequently flushed out if they were found.  It's not 100% complete, but it's accurate in what it says, even if it's not the most visually pleasing/organized descriptions possible. 

What kjj was alluding to was that there's deeper meanings to a lot of these things.  And while documentation could be improved, a lot of you just get from experience.  If the documentation is lacking, help fix it.  But for where you're at, there is more than enough there. It describes the binary maps exactly as you wanted.  Like I said, just open blocks/blk00000.dat and look at the first 300 bytes in a hex editor and compare against the data on that page.  You'll get it.  But it can't be spoon-fed to you.

I forgot to mention, you need to completely uninstall the previous version.  For some reason, switching from 32-bit to 64-bit or vice versa leads to crashes because the installer decides not to replace all the installed files.  I have tried fixing it, but it never worked

By the way, I'm temporarily disabling this.  The last thing I need right now is to go hunting small bugs while I have a usability "crisis" to deal with.  I'll re-enable this bounty later.
 
Are you running the 64-bit version?  If not, get the latest 64-bit version from the downloads page.  A lot of these crashing issues were actually due to the 32-bit build (and resource usage).  All that is being fixed soon.

This is such a perfect match for Bitcoin (trading geeky digital goods for digital money). At least, for the "default" user base of nerds & geeks.  I just donated 1 BTC for the latest bundle.  I was so excited about this, I forgot to even look at what was in the bundle before donating!  

That's exactly how Armory wallets work, right now. 

Okay, great. 

I mentioned expanding the Armory C++ utilities because it doesn't use OpenSSL.  It uses Crypto++.  I definitely want that code upgraded, and it might just be one night's worth of work to match the EC-math operations I already have, with the key-recovery algorithm.  Maybe a tad bit of Crypto++ doc searches looking for the needed operations.  That's worth 0.5 BTC to me.

For now, if the key recovery only works in python, that's fine.  It will fit into my interface.  I just wanted the key recovery as part of the C++ operations for other reasons.

The effect of a mining pool is to consolidate all the hashing power under the pool operator's control, in terms of what transactions and blocks are to be included and considered valid.  Miners would prefer to make those decisions themselves, but if you control only 0.0001% of mining power, you'd usually prefer the lower variance of getting a small payout every 30 blocks (by the pool) vs 1 full block every 3 years (mining solo).

P2Pool provides the same variance reduction for miners, without centralizing the decision making process.  Someone who has 51% of all hashing power can do what you are speaking of, regardless of whether they are mining solo or in P2Pool.  If they mine in a regular pool, they are effectively "handing the keys" to the pool operator.  But with 51%+ you have no incentive to use a regular pool or P2Pool.  

Wait... you're running this on the offline computer?  You don't need Bitcoin-Qt on the offline computer.  Please uninstall it so Armory isn't even tempted to try to run it.  You only need Armory on the offline computer, and the offline computer can be any PoS with 256 MB of RAM or more.  The online computer is the one that needs all the RAM and bitcoin-qt.

Unfortunately, that error isn't terribly useful, except for noting that bitcoind.exe seems to have triggered the error.  Can you run Bitcoin-Qt standalone? 

Also, have you downloaded the 64-bit version of Armory?  I've noticed a lot of these crashing issues go away with the latest 64-bit version.  I actually just removed the 32-bit link from the webpage for that reason.

LvM - the point was that you are going to have to put in some elbow grease like the rest of us and figure out the minutiae.  Once you look at some binary maps and match them up against the serializations described on the protocol page, it will seem a lot simpler.  Only so much of it can be spelled out for you.  Trying to spell it out even further isn't all that productive, because you're not going to "get it" until you dive in anyway, and then those documents will seem entirely sufficient.  

100% of the details may not be there.  But most of them are.  It's accurate.  Ask questions.  Look at other implementations.  

Open blocks/blk00000.dat and read the first 300 bytes.  Then match it up against the protocol page and what I wrote above.  You'll see the magic bytes, the numBytes, the 80-byte header, the numTx, then a list of Tx.  You can then jump to an arbitrary block.  Jump to block 170 which has the first real transaction (it has two tx: a coinbase tx and then are regular pay-to-address transaction).  

Thanks scintill,

That's a nice compact implementation.  I like it.  I was just looking through the code...

@jackjack

I forgot that Bitcoin-Qt uses key recovery for the signatures.  Meaning, that you only need to provide the signature, and the public key can only be one of four different values.  Thus, signature and a couple extra bits.  This is something I don't have implemented in any of libraries yet, and it doesn't look trivial.   But the code is all there in the C++ from scintill, and I am considering putting it into my own "EncryptionUtils.h/.cpp".

I assume you're not going into the C++ code in Armory...?  Just making standalone python files?  That will work for now, though I can see that having the C++ key recovery would be useful.

If you want to take a shot at implementing it in EncryptionUtils.h/.cpp, I will throw in another 0.5 BTC (on success, of course!).  I already have EC math operations available in the library.  I'm pretty sure you can do most of it with what's already there.  Though, you might have to add a sqrt-function or something (I cheated with UncompressPoint, by just letting Crypto++ do the uncompression for me, so  I didn't actually implement it).

Actually, Armory implemented message signing before Bitcoin-Qt did.  Thus, Armory had no way to know how Bitcoin_Qt was going to implement it, and thus we ended up with different, incompatible signing algorithms.  So, while Armory has a "message signing" feature, it's not compatible with anyone else.

There's an active bounty out to fix this.  Hopefully, it will happen soon.  But if you are compiling the list for inter-compatible signing, Armory is not one of them.   This is also why Armory's signing is kind of intermixed with an ECDSA calculator... I started with that, then decided not to upgrade/polish it until I got a compatible algorithm implemented.

The 51% attack is only if one person/entity can decide which transactions to into the blockchain.  This is a concern for big pools where there's a single pool operator making the decision about which tx are accepted, and the miners are just "drones" that follow along.  If that pool operator modifies his software to execute a double-spend, then he gets the mass of miners in the pool to come along with him by default (though, if it was proven he did this, many of those miners would jump ship and mine at a different pool). 

But with P2Pool, each individual miner gets to decide for him/herself which transactions go into the chain, as if each miner was mining solo.  So you get the decentralization of a bunch of independent miners, but they all still get to share the reward of the blocks. 

You do bring up some interesting context.  And I will spend some time thinking about it.  But I wholly dispute this statement:


Replacing unconfirmed transactions doesn't do harm to the Bitcoin ecosystem.  It's how the system operates.  We're not "removing" security, it was never there to begin with.  The success of Bitcoin never depended on it, in any way.  We're just guaranteeing that no one is ever misled about that aspect of the system.

Also, your comment about blacklisting is really not the same at all (nor feasible).  Zero-conf replacement requires only a few miners to participate for it to make zero-conf transactions pretty much useless in zero-trust transactions.  That's not the same as blacklisting, which needs 100% miner participation to work.  Or rather, I only need a few miners to agree to mine my transaction for it to be eventually accepted.  And convincing miners to not mine the top block is going to cost you a $#!+load of money...every 10 minutes...forever.

Your point is not lost on me, I just didn't like your specific examples

False sense of security.

The point of all this is that zero-conf tx should not be used for zero-trust situations.  But merchants will, because it "seems to work" right now.  What we want is merchants to recognize this lack of security and decrease required trust, say, by having the buyer show ID before they walk out with the merchandise.  Just like they do for cashing a check (which carries much of the same risks).  As long as there is a way to use the legal system as backup, then they have appropriately compensated for the lack of security behind the zero-conf tx.  

Merchants could learn the hard way, and then they'll stop trusting zero-conf tx.  But if they do that, there's no reason any more to artificially maintain this illusion that they are somehow secure.  Might as well just write it off now and let everyone start adapting now. 

128 bits is more than sufficient.  There's a reason it was chosen.

Consider that the entire bitcoin network, over the course of the last 4.5 years, has "only" produced about 2⁶⁹ hashes.  You'd have to do about 500 quintillion times that amount of work to have a 50% chance to brute-force a single 128-bit seed.  It's just not feasible.

Also, I would argue that that even the "unstealing" aspect of random wallets is irrelevant.  If someone has access to your unencrypted wallet, they can fill your keypool with more addresses than you'd ever use, then copy your private keys.

Therefore, there really isn't a downside to deterministic wallets.  The upside is phenomenal, though. Armory users rave about being able to do one-time backups and never have to worry about it again.  It also makes securing your backup easier, since it doesn't have to be easily replaceable.  Secure it hardc0re, once.  Then leave it alone for the next 3 years until you need it.