That is how banks work today. It depends on trusting them to use good bookkeeping practices and not cheating. It is a good system if people were honest. If the banks would only work that way, then there would be no reason for Bitcoin. The problem is that they don't behave honestly, so we need Bitcoin mining.
Theres a similar trust when making a transaction, you hope that the miner will include it. But you can always hope that the next miner will include it. Similar to my system, you just broadcast to as many nodes as possible and possibly wait for an OK response from a few.