I think I understand the basic operation of the Bitcoin protocol.
Blocks are the "long-term memory" of the network used to prevent double spending (and the way the network agrees in first place). Proof of work is sort of brute-forcing the nonce so that the hash has at least the desired number of zeros. When a dishonest node generates a new block other nodes will refuse it should it contain transactions that were not seen by them, so the network will "converge".
I guess the transactions need to be included in that PoW (or else it would be simple to alter them afterwards). So every time a new transaction is seen it will require the miner to start brute-forcing "from scratch"? I read some sort of tree is formed, so it actually doesn't mean the input to the hash function gets longer, but still every transaction will change the "root value", won't it?
Why would a miner even bother to include all transactions that occurred on the network (given that transaction fees are minimal)? There is no lower limit on the tx number per block (perhaps in that time there were really no transactions). It would be simpler for them to just include perhaps one and then use their (CPU) time to solve the puzzle and earn the reward.
There must be some sort of thing in the Bitcoin design which I don't get yet...