First of all is my understanding accurate? In other words are the only degrees of freedom the following?:
- choice of coinbase transaction message
If by that you mean the scriptSig of the coinbase transaction input, yes. Subject to the consensus rules which require it to be between 2 and 100 bytes, and to start with a push of the block height (see BIP34), miners have complete freedom about what to put there.
But in addition to just the scriptSig, the entire coinbase transaction can be chosen by the miner. This includes the payout address(es), and if there are multiple, how the subsidy/fees are distributed over those. Also miscellaneous things like the transaction version number, locktimes, and sequence values of the coinbase transaction could in theory be modified. Lastly, miners could insert dummy 0-value outputs to the coinbase transaction even.
- choice of list of transactions to be included in the next block
Indeed. And the order of those transaction (subject to the constraint that if the block contains spends of outputs created within the same block, the creator transaction must come before the spender transaction).
And, miners could also come up with their own transactions to stuff into the block – though that carries the opportunity cost of not being able to use that block space for other fee-paying transactions.
Yes, with the restriction that is has to be strictly higher than the median timestamp of the previous 11 blocks, and not more than 2 hours in the future.
Yes.
(what is the concept of extranonce? is it just part of the arbitrary message string for coinbase transaction?)
Indeed.
Second, what guarantees that within this search space, a valid block will be found? (is it just a probabilistic guarantee?)
Yes, it is just probabilistic. Every attempt has an independent chance of being a valid block equal to the target value over 2256, or as of 2023 Nov 11, roughly one in 268282661671783234208589.
