What is the order of operations to verify a transaction?

Question

I am not asking if all nodes run each transaction. I'm asking for a rough time sequence of events. For example, in the case of a double spend attempt, and the double spender is colluding with the miner who is adding the next block. At what point does a random node in the network, who is participating in mining, verify this was incorrect and flag the issue?
- Is it only the next miner who gets to add a block who detects this issue?
- Does each node only verify/run the transaction the next time they participate in mining or only when they solve the PoW and get to add a new block?
- Next time they are online?
- Is there a trigger such that a full node who may be idle, needs to run the contract code and verify?

What if the next N miners are also colluding? Does it require just one miner to flag the transaction as incorrect or N+1?

Obviously, all nodes cannot run that transaction before another block is built, so i'm hoping there is a ballpark timeline of events.

Answer 1

When a miner solves the proof of work puzzle on the block he/she is mining, he puts it in the block's header, and propagates it to the other nodes he knows about. They could be other miners, or other non-mining full nodes.

The new block is now being propagated. The nodes that receive the new block have to validate it.

Non-mining full nodes will do the following:

• Check the PoW in the block header is valid;
• Propagate the block to peer nodes;
• Check the state transitions in the block are valid.

Mining nodes do the same, but in a slightly different order, allowing them to start mining more quickly on the next block:

• Check the PoW in the block header;
• Check the state transitions in the block are valid;
• Propagate the block to peer nodes.

Checking the state transitions in a full 8Mgas block takes in the order of 100-200ms on a decent machine.

Onto your specific questions.

I am not asking if all nodes run each transaction.

They do, to ensure their state is internally consistent. (There's actually game theoretical argument that goes against this. I've heard that some miners aren't actually checking the contents of the block are valid, and are just assuming it is to allow them a head start on mining the next block.)

At what point does a random node in the network, who is participating in mining, verify this was incorrect and flag the issue?

It should be flagged by the miner's first set of peers, who should be validating the state transitions.

Is it only the next miner who gets to add a block who detects this issue?

No, as above.

Does each node only verify/run the transaction the next time they participate in mining or only when they solve the PoW and get to add a new block?

No, when they receive a newly propagated block.

Next time they are online?

If they go offline, when they come back online, and before they start mining again, they'll need to sync back up to the chain head. Validation is part of this sync.

Is there a trigger such that a full node who may be idle, needs to run the contract code and verify?

The trigger is that it'll have the new block pushed to it.

Obviously, all nodes cannot run that transaction before another block is built, so i'm hoping there is a ballpark timeline of events.

In theory they do, else they don't know that they're building on a valid state.

Answer 2

The transaction are only been checked during mining, so by the nodes who mines. All the other nodes, when they receive the block, check if the solution, according to the difficulty, is correct for the block. So they only verify the solution provided by the miner. If it is correct, then they accept it, if not, it gets rejected.

You can find more about block validity in the yellow paper, part 4.4.2: http://yellowpaper.io/

Concerning execution order, I am not sure at all, sa I prefer sayig nothing. You should have a look into the yellow paper as well about it: http://yellowpaper.io/