I have a newbie question. As I understand, ethereum internal transactions are not stored on-chain. One can replay them when replaying the blocks. This seems to assume that smart contracts' behavior is deterministic. What if there are oracles? Does that make the smart contract's behavior nondeterministic and therefore one can't always replay the same internal transactions?
A blockchain oracle is any device or entity that connects a deterministic blockchain with off-chain data. The way they work is these oracles actually enter data on the blockchain through an external transaction. this way we can guarantee that the blockchain has all the information needs to verify itself. So instead of calling an API, an off-chain oracle will actually get the API and then report it on chain in a transaction. that way there is no API calling in the ethereum. Oracles are known as blockchain middlewares as they bridge the blockchain world to the real world.
Oracles are trusted entities because they are capable of digitally signing or digitally attesting the data to prove that the data is authentic. This proof is called proof of validity or proof of authenticity.
Oracles should not be able to manipulate the data they provide and must be able to provide factual data. Even though oracles are trusted, it may still be possible that, in some cases, the data is incorrect due to manipulation or a fault in the system. Therefore, oracles must not be able to modify the data. This validation can be provided by using various cryptographic proofing schemes. Some mechanisms to produce proof of data security:
TLSNotary
Android proof
Ledger proof
Trusted hardware-assisted proofs
As blockchain platforms such are fully decentralized, it is expected that oracle services should also be decentralized. This type of oracle can be built based on a distributed mechanism. For more You can read here:
https://medium.com/stakin/the-top-decentralized-oracles-169b94dfbb83