I am new to this forum, but I have been reading the technical paper behind bitcoin and while I like many of its claimed properties, I would like to see something with a bit more explanation, as I am used from reading other cryptographic papers, which while dense can at least be shown to be wrong. To be able to analyze a system mathematically you need the equations. Pointing at the source code is not a substitute for that.
In a paper I shouldn't be the one who has to figure out why something is true; there should be proofs and a stupid computer should be able to follow it.
I am surprised you already got this far, since I would have expected people to demand that the system is solid first, before using it.
Next to the mathematical points there is also the issue of someone discovering a constructive method to generate blocks. Is there a way to switch to a different hash function if so required?
There are several threads that have been talking about this specific issue, and it is something under consideration. There is a plan in place to deal with the possibility that the SHA-256 algorithm, which is the one currently being used by Bitcoins, would eventually be replaced. There is also an effort by the NSA and others involve with the cryptology community in general (much more than just Bitcoins) that is trying to find something more secure than this algorithm and put it through a rigorous analysis in terms of ensuring that it really is more secure.
This thread goes into much more detail about this issue and includes a quote from the lead developer that is relevant to you question:http://bitcointalk.org/index.php?topic=1854.0
There is another efficiency issue: how much energy or machine operations of the whole network does it cost to verify one transaction? If it costs more to verify a microtransaction than its value, there seems to be something wrong; it might be that this is a fundamental limitation. A new money system would have to be able to scale billions of users. Is that manageable? If not, why is bitcoin presented as a new money system as opposed to just a cool hack?
So, lots of questions, I hope you can answer them.
In terms of the ability to verify a transaction is valid, the effort to do that is trivial, on the order of a few cycles and a fraction of a second for even an ordinary computer. The transactions get incorporate into the hash blocks in terms of getting put into the network and recorded on a "permanent" basis as having been confirmed. In this regard a considerable amount of effort is put into confirming the transactions and in fact is one of the major functions that is "rewarded" by giving those nodes who are processing these blocks some bitcoins for performing that effort.
In terms of scaling this effort to billions of people, there may have to be some modifications to the network and include some core machines doing a "backbone" effort with Bitcoins and some leaf nodes who are accepting and transmitting transactions. Some of that has been discussed on these forums already, and I'm not really sure what the specific plans are, if any, when that happens. It is certainly scalable to many thousand computers even in its present form and a whole lot more room to deal with the current scalability with the network as it stands. If it may be approaching something of a problem, I'm sure there will be plenty of people very capable of coming up with alternative solutions to fixing this problem. The main issue is simply getting people to show up and participate... a much larger problem I would think.
Scaling issues would be a problem we would all wish to have here.