My question is:  what is the client supposed to do when this happens?  It has the correct block headers, but doesn't read the correct tx.  So does he go to the network and request the tx list for that block, again?  If so, then wouldn't the replacement be appended to the end of the file, effectively making blk0001.dat file contain out-of-order block data?

I've never experienced a bit error like this in any application on any computer, ever (or at least never noticed).  It seems like one of those boundary conditions where I bet the client isn't prepared to handle this...

While testing my blockchain scanning tools I have been able to match up block explorer on every single blockheader hash and tx hash except for a single transaction.  I get the correct answer for 1.5 million transactions, and the wrong answer for exactly 1.  I have spent a lot of time investigating this and I believe I've narrowed it down to a single bit error!?!  How on earth this would happen?  Shouldn't the client choke on this?  Does anyone else have this?

It is in Block 108009, in transaction #23.  In the blk0001.dat file, the tx starts at byte 77,582,676 and is 258 bytes long.  More specifically, the byte in question should be a sequence of four zero-bytes around byte 77,582,930.

Here is the raw transaction as it appears in my blockchain:

The last 4 bytes (8 characters) represent nLockTime.  This transaction appears to have an nLockTime of 0x00040000 (1024)!?!  BlockExplorer says it should be 0 (as expected).  This couldn't be malicious, because nLockTime is disabled and an nLockTime of 1024 in block 108009 is pointless.   This has been driving me crazy, and now I am baffled how my client has let me get away with this.  What is the client supposed to do if it reads a tx from the blk0001.dat that doesn't match the merkle root in the header?

Sorry to revive an old thread, but I finally got my technique implemented for reading the blockchain, and I believe it represents a lower-bound on computational time for reading in the blockchain.   I am posting because this is empirical data on what I believe to be the most efficient blockchain scanning technique possible. 

Note: I recognize that a full-RAM implementation is not ideal for the general user, but it's feasible for modern computers (at current tx volume for the next couple years) and this was for the purpose of finding the lower-bound on processing time.

• Allocate 500MB contiguous space in RAM, do a single file-read of the entire blk0001.dat file into this memory
• Create maps of blockheader pointers and tx pointers indexed by hash (pointers reference memory locations in RAM).
• Organize all blockheaders into a chain, calculate the longest one, create a headersByHeight vector of pointers
• Read in a wallet of a few addresses and do a fresh rescan for relevant transactions
• Does not do any ECDSA verification in the scan
• Does not check merkle roots/trees
• Does not check validity of anything -- assumes if it's in the blockchain, it's valid

I have a quad-core AMD CPU (64-bit), and ran this method on a WinXP virtual machine.  I applied the above process to 135,000 blocks. 
-- Read blockchain into memory:  4s (120MB/s HDD sounds about right)
-- Construct the header and tx maps from scratch in 9s. 
-- Blockchain organization and finding longest chain from scratch:  0.5s. 
-- The full wallet scan takes about 15s. 

So, making the assumption that the longest chain contains only valid data, I can do a full rescan in about 30 seconds.  With 145k blocks, I assume this will be more like 40-45s.  I believe this is a very favorable result.   I recognize there is no fair comparison to the existing client, because I believe the existing client does all the ECDSA signature verifications. 

I don't see the necessity of getting ahead of ourselves.  What hashcoin suggested enables more functionality than just the multi-sig scripts alone.  There's plenty of unique functionality available through standardized multi-sig scripts, and those are going to be plenty valuable to the Bitcoin community as a whole.  My concern is that nLockTime opens up a can of worms w.r.t. security & complexity of the network, so that's not something to just "throw into the client." 

If you believe the nLockTime stuff should be higher priority than the multi-sig scripts, that's a different debate.  It sounds like Gavin has already decided to start standardizing the multi-sig stuff, so I was curious if he ever concluded anything...

Gavin, what is the status of the new standard transactions?  Did anyone actually authoritatvely decide on how the new transactions will look in the blockchain (specifically, the OP_CODE structure of the transactions)?  Any decision on the how they will be serialized (for the purpose of handing out addresses)? 

I recognize that you are probably working on the updated client, but I wanted to know if you reached any conclusions, since this thread seems to have been left dangling a month ago...

So I haven't worked much with SQL other than the fact that I know SQLite is pretty convenient in python, and I can read the blockchain from python -- so I should be able to figure out how to put the two together.   If you write out explicitly what you want the database/tables to look like, and toss me a couple BTC (upon delivery) I should be able to produce a .sqlite file for you.

For instance, I assume you want two tables, one of block headers, one of transactions.  The headers table would have all the core information in it (hashes, difficulty, nonce, etc).  The transaction table would have the header hash, but be a little more complicated since each transaction actually has a variable list of inputs and outputs.   I suppose you could go a step further and add a table of TxIn objects and a table of TxOut objects, each of which contain the parent Tx hash.   

If it's not too intense, I can probably figure it out.  I already have most of the tools made to do it, I just gotta learn the python-sqlite interface (is simply including hashes of the parent objects enough to consider the DB "relational?")

-Eto 

Do you want to maintain a running, up-to-date version of the blockchain in SQL?  Or are you looking for a snapshot of the blockchain at a point in time?

The reason I ask is because there's plenty of folks who could use their blockchain management code to give you an SQL snapshot, but if you want a persistent, updating SQL database, you're going to have to do something more creative.  Maybe modify and recompile the client to maintain a parallel SQL DB, to be updated when new blockdata is received.  Or, as you said, scrape a website/service that offers up-to-the-minute blockchain data.  I guess it depends on your application/requirements.

I don't agree.   I don't see how the GPUs can be "not as memory limited as you are thinking."  We know the total RAM on the card, and we can count on a little bit extra for local memory and registers, but not on the order of 100s of MB.  I program CUDA on NVIDIA GPUs, and you're pretty much limited by the RAM amount stated on the box (and OpenCL isn't much different).  You can use CPU RAM if you want, but there's massive latencies associated with transferring data over the PCIe bus.  Perhaps the latencies aren't all that important in this application but the point is to make the computation memory-limited, not computation-limited.

Right now the computation requires virtually no RAM, beyond a few round constants and storing the original 80-byte header.  A GPU with 1600 shaders might have 2 GB of RAM-- that's 1-2MB per core.  But a CPU typically has 250-1000MB/core.  If the each thread only required 100 MB RAM, then even semi-older computers could apply all their core(s) to computation without impacting system usability dramatically (if at all).  But it would limit the 1600 shaders on a GPU to only 20 simultaneous threads (about 1-2% GPU capacity).  

As for GZIP... the point was to apply a process that needs the entirety of the data in order to run and can't be broken into smaller pieces.  I'm sure there's a billion existing algorithms that can do this, I just guessed that gzip was one of them (incorrectly).

Personally though, I think the biggest threat is actually botnets, so the dominance of GPUs is actually preferable to me.  You don't have to agree, though.

You don't need a raw hashing algorithm to impose these kinds of requirements on the system.  You just need a unparallelizable process that ultimately leads to a random string of bits--i.e. only the last step needs to be hashing.  This is a silly, off-the-top-of-my-head idea, but it should illustrate the point:

The current process for POW looks like this:


Instead you could make it:


The idea here is that each thread must compute N sequential hashes and save all the intermediate results so it can make one huge string and gzip it (I believe gzip needs the entire string in memory to operate... if not, then pick a different operation that does require it).  Then the result is hashed to 32 bytes to get the final proof-of-work.  

The reason something like this works is that N can be chosen to enforce any kind of per-thread memory requirement.   If N is 10,000,000, then each thread has to hold 320 MB of data at once to do the GZIP.  That means that a 6990 would only be able to run 10 threads at once:  possibly faster than your 4-core CPU, maybe not.  Most GPUs with 1 GB of mem would only run 2 or 3 threads.  At best, your GPU would be like an extra CPU, and a modern quad-core computer with 4 GB of RAM could probably run fine with this in the background (or the user could scale it down to 1-2 cores when they need the resources).

This is a bad argument.  It assumes that people are rational, and/or have some kind of nominal, predictable intentions.  People don't always do things for good reasons, or maybe that have reasons others didn't think about.

• Perhaps a government/company pays a botnet owner to do it
• Perhaps the government takes over a botnet and decides to kill two birds with one stone.
• Perhaps a botnet owner thinks that BTC has no future, so he finds someone who is willing to let him short-sell $1million in BTC and then he crashes the network for immediate payout.

They don't need to persist this attack forever to do damage.  It only takes one time to permanently scar BTC (maybe make the final KO), and it doesn't make me sufficiently happy to say "see, I was right!"  I want to see it not happen, and not have it possible to happen.   We've seen what happens to the BTC market when non-security breaches happen (not related to the functional security of BTC itself), what do you think is going to happen when someone pulls off a massive double-spend once which actually does reflect on the security of BTC? 

This brings up a really good point.  The miners who are computing for the pools should be aware of what the "current" block really is (they are regular nodes, too, aren't they?).  If so, they could be programmed to pay attention to the current longest-chain, and reject doing work for the pool if it sends headers to be hashed that use a different previous-block hash.  This assumes that the only type of attack someone would want to execute is a blockchain rewrite/double-spend attack. 

This would seem to shut down this kind of attack very quickly.  And as you pointed out... some pools already have a "dangerous" amount of computing power.  Though now that I think about it, my miners are using Phoenix which actually doesn't learn of the blockchain.  Perhaps this is a worthy functionality to try to fit into the GPU-miner code (such as Pheonix). 

(Yes, yes, I know, there's no good reason for a pool operator to attack the network.  But people don't always do things for good reasons.  I'd rather just avoid the possibility entirely)

I have my own python library I started building from Sam's code a few months ago.  I have all calculations implemented (including scripting!) but not networking.  Perhaps we should team up.  Though I suspect you (Sam) may not like the fact I replaced all your BTC classes with my own:  I did it for the fun of implementing the stuff myself in my own way, and learned a LOT.  I know from my job that the best way to understand a system is to try implementing it yourself--and holy hell I've learned a lot from this process...

This library does all scripting except for a few OP_codes, but it does do OP_CHECKSIG, meaning that the library can successfully verify and sign transactions (using Lis' raw ECDSA-in-python module).  I wanted to get some networking implemented, and was actually planning to just pull your code in, but maybe you'd be interested in contributing to this library and doing it yourself...? 

I've been caught up the last couple months trying to implement a C++/SWIG backend because python is slow as dirt.   Unfortunately I've been getting nowhere, and finding I need to do some more planning and reorganization before I'll get it right.  So right now, I don't have anyway to scan the blockchain or maintain a wallet.   But I have grand plans for doing so, and am anxious to get this functionality implemented!

If you're interested, the project is here:

https://github.com/etotheipi/PyBtcEngine

The file unittest.py might show you how to use the library as implemented... it tests just about every method in my library, including OP_CHECKSIG.    PM me if you have any interest in teaming up!

First of all, this is exactly the question I was asking in my post here (Anyone else concerned about the global hashrate?).  This scares me because you're right, it's prohibitive, but still completely feasible for an individual/corporation/mafia/government with enough motivation. 

One thing that should offer some comfort is that running 20,000 GPUs is a lot harder in practice than theory.  You're going to have to buy, at minimum, a warehouse and probably have your own power plant as you would need about 10 megawatts of constant output to run those GPUs.  Not to mention hire lots of people to build and maintain all those systems.  Alternatively, you could buy a 100,000 FPGAs and get away with 1 MW of power, but at substantially higher cost.  Of course, you don't need to maintain it very long to execute the attack, but it's still a pretty substantial investment of time an money, well in excess of the cost of the raw hardware.

My concern was more about botnets.  It would seem that the biggest botnet is capable of generating the same order of magnitude as the current global hashrate, though it's tough to tell if they could achieve 10% or 51%.  Either way, it concerns me, and it's not going to get any better, unless BTC goes up to $100 and then people start buying more hardware.  In times like now, it appears to be profitable to run existing hardware, but too risky/long-term to justify buying new hardware.  If BTC floats this way until the generation rate drops from 50 BTC/block to 25 BTC/block, I think we're "screwed."  I put it in quotes, because the feasibility of an attack does not guarantee it.  But certainly, the fact that it's feasible will have an impact on general acceptance of the currency.

In regards to botnets, I think the current POW is actually better.  If users were solely using their CPUs for such calculations, then even a "small" botnet would have no problem overpowering the base of 20,000 BTC users using 1-2 CPUs.  The computers controlled by botnets typically don't have big GPUs, and thus are at a significant disadvantage relative to the base of BTC nerds with 20+ GPUs in their basement.  Of course this may not hold when talking about the threat of governments that want to attack the network, but I would guess their existing hardware is similarly limited-- at least right now, most "computing clusters" still consist mainly of CPUs and not GPUs.  Getting up to 15 THash/s on CPUs is a lot harder.

So what you're saying is that by letting my home computer run at idle (50W) with my 750W PSU, I'm actually doing more harm that loading it 80-100%?  I don't buy that.  I agree the efficiency might be lower at lower loads, but the longevity of the device isn't going to be negatively affected.

Regardless, I think we're in agreement about high loads--you want to keep the actual power consumption to about 50-70% of the PSU rating, unless you don't mind changing the PSUs every couple months. They're not guaranteed to fail, but PSU problems tend to show up as problems with other components, and thus are a complete pain to diagnose.  I prefer to pay 10%-20% extra to avoid it entirely.

My strategy has been not to base anything on manufacturer power consumption numbers.  Look at something like the mining hardware comparison which shows the typical range based on users measuring actual, from-the-wall power consumption.  I have a bunch of 5850s, 5870s, and 6950s, and I've measured all of them with a Kill-a-watt meter myself, and my numbers have always matched up with what's on the page. 

On that note, that page shows an non-overclocked 6990 using about 350W at full load, higher once you start cranking up the clock rates.  Unfortunately, I don't actually have any of these GPUs, so I can't measure it myself.  Just saying that in the past, I have found the power consumption numbers there to be reliable.

However, I believe it is a poor decision to design to you 100% of max power consumption unless you buy top-of-the-line power supplies.  If you anticipate 1200W of consumption, don't get a 1200W PSU.  It can work for a few weeks maybe even months at 100% load, but it's going to wear out eventually.    On the other hand, if you only pull 100W from a 700W PSU, it will probably run forever, no matter how crappy that PSU is.

I try to keep the max power consumption around 60-70% of max rating of the combined power supplies, and really prefer 50% unless it's a high-end PSU like a Corsair HX.  Perhaps it's paranoia, but a failing power supply can take a lot of other hardware with it, so I usually err on the side of too much power.  It's worth it to me to spend 10% more, and sleep well knowing that my hardware won't be on fire when I wake up.

I don't know what codebase miners use.  I thought it was satoshi code, but the GPU miners perhaps do accept them.  I was told if I wanted to use non-std scripts in the main-network, I need to send them directly to Eligius, as that pool is the "only one" that is willing to accept them into a block.  That was a couple months ago.  It may have changed, it may have been an error by the original poster that told me that, or the testnet is different...

Your TxOut script looks fine to me: your TxIn should just be a regular Sig&Pubkey.  Just make sure you're hashing the right thing for your tx signature.  You can verify you're doing it right by looking at my OP_CHECKSIG diagram that I made specifically for this purpose.  Please note that you need to copy the entire TxOut script (the one with the OP_DROP) into the TxIn script before signing.  Yes, it's complicated... that's why I made the diagram!  

It is my understanding that the GPU takes in the block header than needs to be hashed, and splits up the array of potential nonces between the threads/cores.  Each thread can, itself, determine whether it's own result meets the difficulty threshold and throws it away if it doesn't.  The only communication that needs to happen is for the GPU to send the 1/2^32 results that meet the difficulty threshold (i.e. finishes computing a share), and the CPU only needs to send new work to be done after a share is complete.   We're probably looking at a few kB/sec... I think a 1x slot can handle that.

There might be a little bit more going on here, but not a lot.  As another poster said:  the bandwidth req't is nil

First, I wanted to make sure that there was a differentiation between WEP and ECC, as WEP was a joke of a security protocol, and ECC is blessed by the NSA in Crypto Suite B.  The two protocols are in different galaxies.  A crypto-algorithm needs to be rock-f***ing-solid to get NIST and NSA approval (barring all conspiracy theories). 

Second, I recognize that there could be implementation issues with ECDSA in BTC that makes it less than 100.0000% of the theoretical security.  But the kinds of side-channel attacks in this environment are extremely limited.  Messages are signed on demand and the inputs to the signings are very specific, limiting plaintext injection attacks.   The number of messages ever signed by a single key would be so low and spread out, that timing attacks would never get enough samples to be useful.  Most other attacks would have to have a level of access to the computer that is already game-over for the regular user.   I would argue that the biggest risk would probably be the random number generator. 

Third, I would argue that the security decrease of a perfectly-implemented ECC protocol using the same key for two messages is so negligible, it should have no bearing on one's decision to recycle keys.  Bitcoin isn't the only system in the world that uses ECDSA, and most other systems don't get the luxury of changing their keys after every exchange.  In fact, using ECDSA for authentication isn't very useful if you have to send a new public key every time, as you would open yourself up to MITM attacks -- you want to send and thoroughly verify public keys once, and then use those as your identity going forward.  It is for this purpose that the NSA/NIST has blessed ECDSA, and probably one of the reasons the algorithm was chosen for BTC (not for recycling keys, but because it's so respected).

I'm interested to hear of feasible side-channel attacks I neglected to consider, but I'm not convinced that there is a tangible threat.  People with millions of dollars in BTC might be motivated to use new keys every time because it's good practice, but it's misleading to suggest that somehow the average user is compromising their own security by recycling keys.

The extra OP-codes outside of the standard transactions are not "supported" by the Satoshi client.  This means that it will evaluate non-standard scripts if they show up in the blockchain (as you have done), but those transactions won't be displayed on the client, and clearly can't be spent by the client, either.   It has to be able to evaluate them or else it would invalidate blocks that are otherwise valid.  It just won't let you create those scripts yourself, and I believe the miners will actually rejects transactions with non-standard scripts.  However, there's nothing stopping someone from mining their own block with these non-std scripts, and so the client needs to be able to evaluate them.

But, how is the client to know whether you can actually spend the coins?  I can create a TxOut with your address but with a script for which there is no TxIn that can evaluate to true.  The client has no way to know whether such a script is even spendable, or what conditions are required, so it just ignores it completely.  You have to go look for the transaction yourself, in the blockchain.

In the future, I hope to see the client recognize when one of your addresses appears in a non-standard transaction, but do nothing other than raise a red flag and let you look at the script.  It wouldn't know how to spend them, but if you are intending to receive such transactions, you probably know how to manually construct the tx to spend them, too.

This is not a well-researched statement.  There is no reduction in security of ECDSA by using the same key on multiple signatures.   If there was, then no one would use ECDSA, as most other applications for it cannot accommodate new keys for every exchange.

The only known weakness of ECDSA in this regard is if the same random number is used in the signature algorithm on two different signed messages.  Of course, with 2^256 possible random numbers to apply here, it just doesn't happen.  As such, ECDSA is an extraordinarily secure signature algorithm, proven to be as difficult as the elliptic curve discrete logarithm problem.  The only thing that will compromise ECDSA (or any other asymmetric encryption such as RSA) is going to be quantum computers or an extraordinary breakthrough in mathematics.  Luckily, there are potentially decades between now and when QCs will be good enough to hack 256-bit ECDSA.  A breakthrough in mathematics that solves the discrete logarithm problem is going to break all internet security not just bitcoin.

BTW, WEP was a joke.  The creators can name it whatever they want, it doesn't mean that the community of informed people actually believed it.  I studied WEP in my cryptography class, and there are half a dozen security holes clear as day if you know what you're looking for.  It is an insult to cryptographers/mathematicians to, in any way, compare WEP to elliptic curve cryptography.