The minting algorithm for staking is different for various coins; for example, it is different in BlackCoin from Cardano.
There are several approaches to staking, but most of them are susceptible to "grinding attacks" and almost none of them are proven secure against every attack (only argued secure intuitively by showing that certain specific attacks do not work).
To give a concrete answer to your question, I will describe a specific case of a proof-of-stake protocol which is proven secure: the Ouroboros Praos protocol.
In the Praos protocol, you can imagine each satoshi corresponds to a public/private key pair. The Praos protocol for staking works as follows: If you are an honest staker, you look at the current date and time and round it to the nearest second (the time unit you round it to is configurable in general and corresponds to the synchronous "slots" of the protocol). Say, for example, that you get d = "2018-07-01 00:19:24". You take that date and time as input, and you sign it with your private key corresponding to your satoshi, obtaining a signature s. You then compare that signature against the difficulty target T to see if s <= T, similar to how bitcoin compares block hashes against the difficulty. If it is, then you have been "elected leader" and you are allowed to generate a block. You first generate the block contents x which consist of the transactions in your mempool as well as a pointer to the previous block. You then sign x using your public key, and produce another signature s'. You then broadcast to the network your signature s illustrating that you have been elected; the current date and time d for election confirmation; the confirmed transactions x which also include the reference to the previous block; and your signature over the block contents s'. The tuple (s, d, x, s') is the block.
Now, other validators can check that you are the rightfully elected leader. They check that s is a signature for d, that s' is a signature for x, that x contains valid transactions and points to the tip of a previous blockchain (with an older timestamp and non-conflicting transactions). Finally they must verify that you meet the target: s must be below T.
This is quite a simple protocol, but, perhaps surprisingly, it can be proven secure. This is what makes it elegant. It's also quite similar to how bitcoin generates blocks. If you are intrigued about why this protocol is secure, I encourage you to read the paper.
A few details:
- It is possible for bad actors to generate multiple block contents for the same datetime that they have been elected leader. This doesn't cause a problem because honest parties will only generate blocks committing to one older block, thereby breaking ties.
- It's possible that two honest parties generate a block at the same time. This is not a problem and can also happen in bitcoin. Such ties will be resolved, as long as the protocol parameters are tweaked to not allow blocks to occur very often among slots (the exact parameters are specified in the paper)
- I said above that
s is a "signature" on the current time d, but a technical point is that it's not a signature but actually what we call a VRF - Verifiable Random Function. This is like a signature, except it has the assurance that the output behaves like a random output (such as a perfect hash behaving like a "random oracle").
