Can a transaction be included into the same block that some of it's input transactions are included? Doesn't the protocol require that an txin dependency reference back to a prior block?
As far as I'm aware, it only requires a reference back to a prior transaction. It should still be able to reference that transaction if it is in the same block. If I'm mistaken, hopefully someone with more knowledge of the matter will respond here.
Yes, a transaction can have an input in the same block. The reference client requires that the input come before the output, whether in a previous block, or in the same block.
Philosophically, I prefer to think of all of the transactions in a block as being simultaneous, but officially, they happen in the order they appear in the block. The official view has a few advantages, such as avoiding loops.
No, the official view is how transactions are actually processed in the code. When a bitcoin node receives a block it doesn't know about it tries going through the transaction list from beginning to end, processing each transaction as it goes. Thus if you are at transaction #4, the block transaction processor simply does not know that the output of transaction #6 exists at all and will reject the whole block if #4 tries to spend the output of #6
In addition remember that an input to a transaction is specified by giving a cryptographic hash of a previous transaction and the hash of a transaction includes the part where the inputs to the transaction are specified. Cryptographic hashes are one way, so if you have the output of a hash function there is no way to find a sequence of bytes for the input that gives that output. Since you can't do that creating a transaction loop just isn't possible.
This property actually lead to an interesting bug. So, ask your self, where did the first input come from? Well, that's the special coinbase transaction, where coins are created in the first place, and the part of the transaction where the input would normally be specified is just a set of bytes that are ignored. Now normally part of the mining process puts some totally random bytes into that input, but it is possible, albeit very hard, for two transactions to have the same coinbase. Thus it's possible for two valid transactions to have the same hash, and what the Bitcoin software does in that case is simply overwrites the entry in the transaction database for the first transaction with the second.
However a fix is being deployed where a coinbase input is now required to always have the block number as the first few bytes, so this won't be possible even in theory for that much longer. Satoshi should have done this in the first place, but contrary to popular belief he wasn't omniscient.
