I have yet to find a coherent explanation of how a smart contract - that potentially can have complex interactions with other smart contracts - is actually validated. Please no hand waving here. What I have read so far implies that each node - miners and non-miners - must execute the software - the contract. How can this possibly work? Is ever public function in the contract(s) called? Are all inter-contract message passings called?
I just don't see how this could possibly work.
It works.
The first thing is to filter out malformed transactions and settle on a canonical transaction order all nodes eventually agree on. Transaction order is a critical concern as there can be no consensus about the present state without consensus about the order of the inputs.
To avoid repetition, these posts describe the same process from slightly different viewpoints:
See here: How Ethereum consensus validates same transaction from different miners?
And here: Ethereum fork that implements transaction ordering
What I have read so far implies that each node - miners and non-miners - must execute the software - the contract. How can this possibly work?
Consider this (pseudo) function:
function adder(uint x, uint y) return(uint sum) { return(x+y); }
Let's put (2,2) into it. Do you know what will come back? Me too. You ran it and got 4. I ran it and got 4. Everyone who wants to agree with us or disagree with us needs to run it as well. Of course, we will think anyone who disagrees with 4 is wrong and we will start disregarding their comments.
The "immutable" part of this is the input and the order in which the inputs arrived. Given this, the only possible conclusion a well-functioning node can reach is 4.
Yes, all full nodes and miners run every transaction in the order laid out in the blocks. They reach agreement at block heights. Every properly functioning node agrees on the state at block heights. So, for example, a node that has synced to block 2,000,000 agrees with every other node, in every detail about the correct interpretation of the world at block 2,000,000.
Another node may be way ahead. Say, it's 10 blocks ahead. More precisely, the others are 10 blocks behind. The node that's ahead will have knowledge of recent transactions and that means it's "current" state will be somewhat ahead of the others. That's okay because the others will hear about recent transactions soon. They will reach complete agreement when they catch up.
You might be wondering how it's possible to process transactions with an out-of-sync blockchain state. In summary, they don't. They only submit transactions (via gossip) and hopefully, a miner will pick up the transactions and include in a block. By definition, that block will be in the future. it will be processed, by all nodes, in the context of the block it's included in, not the context of the world state of the node that sent it.
To say that another way, the sending node doesn't shout out "4!" with the expectation that everyone else should agree. It says someone signed a transaction with (2,2) and wants that transaction to mined into a block. When it's mined into a block, the nodes can all agree on the previous state (if it matters), the code to run and the only possible result of that code, in that context.
Consider this not uncommon scenario.
A newbie starts syncing a node but is waaaay behind. The newbie gives a wallet address to someone else who sends some funds. The wallet balance on Etherscan shows the received funds but the newbie's local wallet does not. The node has not caught up to the block with the transaction that increases the newbie's balance. It will get there, eventually.
Any time a node processes a transaction, it does so in the context of all the transactions that came before, according to the blockchain. The best a node can say about a proposed transaction or a state query is the way it looks in the context of the transactions (and state) it already knows about, a.k.a. at a certain block height.
In practical terms reads and changes (transactions) are treated differently. A software client might use callbacks to update a UI or off-chain database as updates are received. The best it can ever know about is the latest block it knows about. It's possible to make displays etc., that update as new information is received (as blocks arrive).
State-changing transactions are always sent to the network and must be included in a block to have any effect. If a node is far behind, it might send a transaction and not be aware of the result until long after everyone else knows, owing to the fact that it needs to catch up to the block where the transaction appeared.
Hope it helps.
A transaction is validated as part of a block. A block consists of an ordered list of transactions, and a reference to the previous block it builds on top of.
During validation, every step in processing every one of the transactions is repeated by every validating node. This includes all messages passed from one contract to another. Every step in the list is deterministic: There are no operations that could result in different results for different nodes, such as random numbers or external http calls - such things are deliberately excluded from the list of operations available to contracts. All the nodes start with the same database (state) from the previous block and apply the same changes in order. They should therefore end up producing the same database at the end of each transaction, and if a validating node comes up with a different result at the end of the block, it considers the block invalid.
This design has two serious implications.
Firstly, the system can only run at the speed of the slowest node that should be able to validate its blocks. This puts a serious constraint on its capacity. There are proposals to improve this with sharding, where nodes only validate a subset of the system's transactions.
Secondly, the system cannot make direct contact to the world outside its database, transactions and block headers, eg by making external HTTP requests, since this cannot be guaranteed to return the same result for every validating node. Instead, if a contract needs information from HTTP requests, someone else must make the request and send the data they find as part of a transaction.
I think your problem is the same as smart contract integration with outside blockchain services (external SOA, REST or alike). I see this as a limitation of blockchain.
As you said, all miners can execute the contract and it should receive the same answer for same input and block sequence. If there are miners getting different results, it will be keep on the chain the one that it's first 51% confirmed.
There are some 3rd solutions (or they say) that solves the service integration problem, like Oraclize or Reality Keys
I don't know exactly how they work, but it might use something like a cache or a map of results to return always the same result for same input.
