Bitcoin's Paradox of Scarcity

For a medium of exchange scarcity is essential: There have to be meaningful limits on its supply (or on the growth in its supply) and it has to be impossible to spend one and the same unit of the medium of exchange in more than one place simultaneously.

In the case of a commodity money such as gold these requirements are satisfied as a result of the physical nature of the commodity: the potential supply of gold is limited by the total amount of mined or mineable gold in existence and by the cost of mining gold; moreover, if you give a gold coin to one person you cannot simultaneously give it to another person.

In the case of fiat money governments typically have a monopoly on its creation (although in the exercise of this monopoly they partner with and/or can delegate some of this creative power to central banks and commercial banks) so that everybody else can't go around creating new units of the fiat money at will.

And the problem of double spending is taken care of by either banks (if you use your bank account to pay somebody the bank makes sure that you don't spend the same money somewhere else at the same time) or the physical good itself (you can't give a coin or a bank note to one person and to another person at the same time).

Bitcoins, on the other hand, are wholly virtual and immaterial. Moreover, the bitcoin network is maintained in a decentralized way. So how can bitcoins still be scarce and rivalrous goods?