Jackjack,

Since I don't know French, I can't tell what the "solution" was that you linked to.  What problem did you have with my diagram?  I'd like to update it to clarify whatever difficulties you had.

If I had to guess, I'd bet there was some endian-ness issues.  That's always the problem.  Scripts and key-data are usually big-endian, just about everything is little-endian.  Except for those times that it isn't...

This is a very complete breakdown of the bytemap of a transaction, all the way down to the signature pieces and the DER encoding:

http://dl.dropbox.com/u/1139081/BitcoinImg/TxBinaryMap.png

This is from my thread here where I created quite a few visualizations to help clarify questions like this.

P.S. - In case it's too small to read:

The 0x8c is the var_int describing the length of the entire script.  Following that, you're going to see inside the signature:

Byte 0: length of signature (73 bytes in your case)
Byte 1: 0x30 (DER code)
Byte 2: length of DER encoded (r,s) pair with extra DER encoding bytes (yes, seems redundant)
Byte 3: 0x02 (DER code)
Byte 4: length of signature r-value
Byte 4+x:  r-value (approx 31-34 bytes)
Byte 4+x+1: 0x02 (DER code)
Byte 4+x+2: length of s-value (approx 31-34 bytes)
Byte [end]: 0x01 (end of sig)

That describes the first piece of the script--the signature part--the second part is the public key, for reference:

Byte 0: length of public key  (this will always be 65)
Byte 1: 0x04
+32 Bytes:  x-value of EC public key point
+32 Bytes:  y-value of EC public key point

One thing to keep in mind, which is often overlooked is that the "difficulty" is not just arbitrary waste-of-time to slow down BTC generation.  It is actually directly related to how "difficult" it is to attack the network.  The higher the difficulty, the harder it is for one person/organization start re-writing the block chain and reversing transactions.  Every extra hash that's needed to solve a block is a little bit of extra security against an attacker.   We can't just arbitrarily replace hashing with other things, without compromising the security.  Even if we tried, we'd likely end up leaving open holes for people to skip the non-hashing parts of the mining and get an advantage over other miners (which isn't dangerous but it won't be a popular revision to the protocol).

In order for something to do what you suggest (replace hashing as proof-of-work and be useful), the problem must satisfy the criteria:
(1) The solution is a piece of information that is extremely difficult to find
(2) A given solution can be checked extremely fast

To find a nonce that creates a block header with 40 leading zero bits will take 2^40 SHA256 calculations (on average), but once you've done it, it takes everyone else in the world exactly 1 SHA256 calculation to verify the solution.  I don't know much about FAH calculations, but I don't think they fall into this category.

Allow me to inject some sanity into this adventure (although it is fun):

(1) An ECDSA private key is literally a random number, between 1 and slightly less than 2^256 (something like 0.999999999*(2^256))
(2) Any number greater than that range is identical to private key that is in in the range of (1)

Therefore, you can pick yourself a 4000-bit ECDSA key if you wanted, but there's an equivalent 256-bit key, and you might as well use that one because it's shorter.  

Speaking of this, I miscalculated in my previous post.  The maximum address size is actually 33 Base58 characters, so I shouldn't have given you a hard time about wanting to calculate 58^33.  Sorry!

-Eto

If you're doing it in Python, you just "58**33" since it can handle arbitrarily large integers.   If you're doing it in another language such as C++, there is no native integer representation larger than 64-bits, so you have need a special class.  I believe the OpenSSL C++ library uses a "bignum" class, or you can google for a open-source solutions, such as this one. There will be an option somewhere ,for just about every language...

Btw, why do you need 58**33?  For bitcoin, most Base58 addresses are about 25 characters long.  This means, the biggest int you would need would be about 58**26

Excellent point.

I'm not saying any of this is a bad idea or we should use shortcuts.  It just surprises me because it seems like a "sloppy" way to do/enforce the calculation.  Almost everything else in the specification is extremely explicit, so it just seems a little out of place that you need to collect the crumbs from a bunch of unrelated transactions to find the answer.

I would expect one of the hashtypes to allow for the last TxOut to be left out of the signature, and then the miner can inject their own script that transfers that last output to themselves, without breaking the signature.  Then a coinbase transaction requires no verification beyond the fact that the block is valid, and then the Tx fee looks any other TxOut.

But it works as is, so I'm not proposing changes.  Thanks for the clarification.

So, this is not a modification of the transaction at all... if a sender explicitly puts more total inputs than outputs in his transaction, they miner can simply declare the leftover his by adding it to his coinbase transaction?

Doesn't this complicate things considerably, by creating dependencies between unrelated transactions?  i.e. in order to verify the validity of a coinbase transaction, you need to add up all the other transactions in the same block...?

So far, I have found no information about how transaction fees are included in a transaction, other than the higher-level description found on the wiki:

https://en.bitcoin.it/wiki/Transaction_fees

All it says is that the outputs add up to less than the inputs, so that the miner can include themself for the "leftover" output.  However, after finally understanding OP_CHECKSIG, I don't see how this possible with SIGHASH_ALL hash code.  SIGHASH_ALL includes all output scripts in the TxCopy that is serialized and signed by the sender, so the miner cannot modify/add any outputs without breaking the signature.  But I also heard that the other hash codes are not used.   Even if they were used, I'm having a tough time figuring out what they do.

Can anyone clarify how this is handled?
 

So I misread the specification originally: NIST and SECG actually make no reference to encryption/decryption or signing/verification in their specification:

"NIST Recommended Elliptic Curves for Government Use"
http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf

and

"SEC 2: Recommended Elliptic Curve Domain Parameters"
http://www.secg.org/collateral/sec2_final.pdf  (secp256k1 defined here)

They simply recommend elliptic curves and provide the associated parameters needed for implementation.  These curves can be used with any EC-based algorithms, including ECDSA and ECIES.

Elliptic Curve DSA and Elliptic Curve encryption are almost as closely related to one another as signing and encryption in RSA.  

   RSA Signing and Decryption:        both are exponentiation mod N with the private key
   RSA Verification and Encryption:   both are exponentiation mod N with the public key

In ECDSA and ECIES, the key-pair relationship is similar, but instead of simple exponentiation mod N, you're applying a different mathematical equation for all four operations (signing, verification, encrypting, decrypting).  The only real difference is that NIST has blessed different elliptic curves for ECDSA and ECIES.  That doesn't meant that the secp256k1 curve can't be used for encryption, it just means that people smarter than us have decided that different curves should be used for cryptography and signing.  

Unfortunately, in my graduate cryptography class, we didn't dive into elliptic curves far enough for me to know what kinds of vulnerabilities there are with naive elliptic curve selection, but there was also no reason why security of the two would be different on the same curve.  I would say that the security of ECDSA keys on the secp256k1 curve will provide sufficient security for encryption as well.  I wouldn't guard nuclear launch codes with it, but I would venture that your 256-bit key will give you at least 128-bits of security.

A more-likely explanation is that the security is actually identical between the two.  But it's standard practice in cryptographic protocols/implementations to use different keys for signing and encryption.  Perhaps this is why NIST chose two different curves:  so that if you decide to use NIST curves, you can't pick the same key for both, even if you wanted to.

But as has been said before:  you don't have the person's public key until they either give it to you, or you see a transaction signed with it.  Having their BTC address is not enough.

-Eto

I'm actually less concerned about flooding out other transactions, than I am concerned that someone could inject gigabytes of bloat to the blockchain (for free!), making it even more prohibitive for regular/light users to use the software.  Both in terms of computation time and disk space resources.

So, are there any transactions that the default client won't accept without a transaction fee?  If a node/miner doesn't want to process the transaction, it still forwards it to other nodes that might process it, correct?

It sounds like it's still possible for one individual to connect to each of a thousand nodes and pass off 20 tx each, and without a single fee.  He could just transfer to himself.   That would add 10 MB of pointless Tx data to the blockchain, in a relatively short time.   Seems like a good way for someone who does like BTC to cause "deterioration" in the network... or at least cause the core developers to have to switch to optimizations they weren't planning to implement yet.

When you execute a transaction, you are actually passing two tests:
(1) You provide a public key that, when hashed, matches the address that the previous coins were sent to
(2) The transaction is signed with the private key associated with the public key from part (1)

Up until the first time you sign a transaction, no one actually knows your private or your public key.  Of course they never get your private key, but they don't know the public key, either.  The interesting part about this is that even if someone knew a vulnerability in the ECDSA algorithm, they can't even begin applying it until they see your first transaction -- because they don't have your public key until that point.  And, if you always use a new address for every transaction, then the first and only time they see your public key is after you have transferred the coins to a new address. 

I don't know if this was an intentional "feature" of BTC, but it's pretty cool.  Even if ECDSA was broken, the network could probably still function, as long as it takes longer than one block to break a private key once you have the public key -- by the time they break the key, the transaction is already in the blockchain.

I recognize the freedom of miners to include whatever transactions they want, and the flexibility of transaction fee schedules.  My question was more about why this particular scheme was chosen in the default client configuration?  I thought part of the purpose of the transaction fees was to discourage penny-flood attacks, but it would seem that most transactions are currently going through without any fees, so I don't see what's stopping a someone from executing an attack right now.
 
I'm also a little biased because one time I didn't include a tx fee and 3 months later it's still 0/Unconfirmed.  I assumed that it was because the network was designed to reject zero-fee tx's.  Clearly this is not the case...

As someone who decided to jump into client development, myself, please hear my 0.02 BTC as well:

Building a BTC client is f***ing hard.  This is many months' worth of effort, even for very experienced programmers with knowledge of all the cryptography, networking, protocols, etc.   Additionally, there really isn't an easy "public beta" phase, because the last thing you want is for someone to use your client and lose 100 BTC because your wallet-encryption algorithm got dorked up by some boundary case that only happens once in a million times.  That event gets broadcast through forums/BTCnews and no one is willing to try your client again for fear they might lose their coins.  I tell you, there's nothing more satisfying than spending months developing a client that no one wants to use...   (this didn't happen to me, I'm just giving a glimpse of what could go wrong).

The fact that 0.3.24 client is "beta" really means "freakin-awesome-but-a-little-short-on-features."  I agree, the community needs more-and-or-better clients, more usability, less tech-savy-ness-required, etc.  But to be fair, BTC is extremely complicated under the hood and extremely sensitive to functional- and security-related bugs.  With my experience, I'm not surprised it's taking so long. 

Additionally, I'm sure you noticed what happened each time there has been a BTC disaster:  MtGox getting hacked, and MyBitcoin stealing/losing everyone's money.  These events had nothing to do with the Bitcoin itself being weak, yet the price dropped pretty substantially on both events due to lack of confidence.  Imagine now if there was a plethora of buggy clients out there, people losing coins, losing wallets, encryption not actually working, security holes in the networking, etc.  That actually would look like BTC itself is crappy.   At least the current client is literally usable.  It doesn't lose your coins, or open up your network to attacks.  I'd rather it be slow than insecure.

I hear your pain.  But be patient... there's no other way...

Now my turn to ask a question:  I notice from looking at the blockexplorer that most transactions don't actually have any fees.  I thought fees were generally required by the miners in order to prevent DoS/penny-flood attacks.  If the zero-fee transactions do actually go through, what is stopping someone from executing such an attack?

I know that the client has a built-in node-disconnect if it starts getting spammed from that node.   But what is stopping the node from connecting to each of 5000 peers and giving them each 20, zero-fee transactions?  Seems like that would be a pretty big inconvenience for the entire network...

Ouch!  That's a little harsh, don't you think?   

Each block contains a list of transactions since the last block.  As we all know already, whichever miner solves the next block gets to include a transaction for 50 BTC to themself from "coinbase."  It turns out that  that if any of the transactions the miner included in your block had a fee attached to it, then the miner gets to include those, too.  Therefore, when a miner solves a block, it typically gets something like 50.75 BTC instead of 50.  The more transactions there were, the more fees received.

If you look at the BTC webpage description about what happens when there's no more rewards for solving blocks, it mentions that they expect the network to be big enough by then that it will be worth solving blocks solely for the fees.  If there are 10,000 transactions per block, at 0.005 per transaction fee, that's 50 BTC in fees.  If BTC really catches on, this is a realistic volume of transactions

Right now, because of the low volume of transactions, most pools only distribute the 50 BTC coinbase, and keep the transaction fees, which are small, but add up over time...

This is one of the main features I wanted to implement in my own client, but I'm not sure I understand your implementation.  I'm not sure why you would have to format your key after using it.

I believe the best way is to have a program on your offline computer that scans the blockchain and your wallet, finds all your available TxOuts that can be used, and then saves a signed transaction packet to  file.  The offline computer would ask "To whom and how much?"  You put in the target address and amount, and it spits out a transaction.tx file which you copy to your USB key.  You bring the key to your online computer and the client (perhaps a special program) would load the .tx file and broadcast it. 

At least that's what I plan on doing if I can ever get my client together.  This seems like the most straightforward way, and guarantees that no private key data ever touches the USB key. 

P.S. - In fact, I know there's a website someone made that allows you to copy the raw binary transaction into the textbox and it will broadcast it for you, so you don't even need any special client on the online computer.  If someone has the link for that site, I think it would be very useful.

As Will said, this is not as easy as it sounds.  A user's BTC address is not their public key, but the hash of their public key.  The only way to know their public key is if they have ever sent coins from that address before, because that's the only time their actual pubkey enters the network.  So you have to search the blockchain for any transaction they've ever signed with their key.  However, since their client permanently saves all their keys, there's no reason it couldn't be used, even if they only used it once.

As for the encryption aspect... I don't see why the ECDSA signature keys can't be used as encryption keys.  The BTC ECDSA is based on a NIST-blessed elliptic curve (secp256k1), and you have a public-key-point and private-key on that curve.  If it's secure for signing, it will be at least very secure for encryption. 

Despite being a mathematician and studied cryptography before, I'm not a black-hat kind of guy.  I know that this will be very secure, but I don't know if there's maybe weaknesses in using a recommende ECDSA curve for encryption.  I just know it's possible to use it, and the security of the signature process implies a high degree of security in the encryption process.

-Eto

I doubt it checks everything as I think that would take much longer than 12 seconds.  But I don't really know what else it would be doing... unless it's loading the entire blockchain into memory.  Seems like that could be done after the GUI loads, though...

On client startup speed:  Mike Hearn mentioned that the biggest thing that can be done to improve speeds of... everything... is for everyone to upgrade.  Now, this is a very difficult task with no automatic update/notify code in the client.  Certainly, if it's that critical to the network for smooth operation, we should at least have the client notify the user they are out of date.  But this doesn't work until we put the patch in and get most people to upgrade to that one, so there's a Catch-22.

I just emailed the owner of bitcoinwatch.com, and requested that he put a persistent, high-visibility link on his page that advertises the current client version with a link to bitcoin.org.  He probably gets a high proportion of all BTC users as visitors to his site.  However, I'm not too familiar with the other sites where BTC users go, besides the exchanges.  If you know of such sites, please send them an email asking them to advertise as such, perhaps something along the lines of:

"Current Bitcoin version is 0.3.24.  Please upgrade now!"

It sounds like this is the only chance we have of getting users to upgrade.  I wouldn't have even known about the upgrade myself if I hadn't checked Bitcoinwatch on the day the update was released and saw it on "current news."