Increasing currency divisibility is listed as a hardfork in bitcoin wiki:
https://en.bitcoin.it/wiki/Hardfork_Wishlist#Currency_changesActually it could be done with a soft-fork. (This is only for academic discussion. I don't think we will ever need to divide a satoshi)
1. Redefine OP_NOP1 as OP_PBTC (1pBTC = 1,000 nBTC = 10,000 satoshi)
2a. To mint pBTC, the total output value must be smaller than the total input value (let it be n satoshi)
2b. With n satoshi sacrificed, the user may, in the scripts of other outputs, embed this command
The sum of <amount> must be equal to or less than 10000n
2c. Instead of taking n satoshi as fee, miner can only take not more than
So SUM(<amount>/10000) satoshi will be destroyed in the minting process
3. Transfer of pBTC follows existing rules: the total amount of pBTC in the outputs must be less than or equal to the total amount of pBTC in inputs. In the "less than" case, miner will take it as fee by embedding OP_PBTC in coinbase output(s)
4. In about 2049, the miner reward will drop from 0.09765625 to 0.04882812, with 0.5 satoshi lost. At that time, miners will be allowed to include extra 5000pBTC in their coinbase output(s).
5. The effective value of an output is amount of satoshi + amount of pBTC/10000 .
6. It will not break existing clients, but they will underestimate the true value of an OP_PBTC output.
Notes:
1. Minting of pBTC is an one way process. It is not possible to "merge" 10000 pBTC to make it become a traditional satoshi again. This will be a hard-fork
2. pBTC is actually a special type of smart property/colored coin
3. Comparing with a hard-fork, there is at least 3 bytes of overhead (an OP_PBTC, an OP_DROP, and an extra OP_PUSH for <amount>). However, it is more economic than a hard-fork if there is no pBTC in output.
4. We will face the same miner reward problem again after a few reward-halve: 5000pBTC->2500->1250->625->312->156
5. With a similar scheme, we can further divide pBTC with soft-fork