I thought for a long time, how to create a decentralized lottery system, which could work efficiently, without producing too many on-chain transactions, and executing complex on-chain scripts, like HMAC-SHA512.
The first thing we should note is that users are already putting their coins into the system, by paying their transaction fees. Which means, that lottery runner should not require any additional payments, because fees alone should be sufficient to collect all of them, and create an additional output in the coinbase transaction, paid to the winner.
In general, if we analyze the chain history, then for each block, we can easily grab all successfully validated signatures. This is our base for selecting the winner. Because you
can't use a coin without exposing its pubkey, by checking all signatures, you will already know, that a given key is spendable, and it was successfully used to move some coins in the current block.
Then, we pick a single public key, no matter in which script type, and which context it was used. Different lottery runners can use different criteria for selecting the winner, because different nodes accept different transactions, some accept free transactions, some may put higher limit, like 10 sat/vB as a minimum, and so on. One winner per block is the highest load we could handle. And it probably should be even lower, like "one winner per N blocks", because lottery runner will obviously not have 100% hashrate domination.
After selecting the winner, we simply create 1-of-2 multisig, where one key is owned by the lottery runner, and another one belongs to the winning user. This is needed, because the default behaviour is to collect 100% transaction fees, which means, that the user lost his bet. Also, during the initial stage of the project, many users will probably be unaware, that they won anything, so there is a need to clean up on-chain UTXOs, if nobody will collect them for a long time.
Also, we should remember, that winning users should have the ability to move their coins. Which means, that if someone paid 110 satoshis for some transaction, and it was the only payment in a given block, then we should not split the coinbase into 50 tBTC for the miner, and 110 satoshis for the lottery. Which means, that there should be some minimal amount of fees, which triggers the lottery, for example set into 1000 satoshis. In other cases, users may end up with dust UTXOs, which they could never move, without some help from the miners.
Another important thing is to use a single pubkey, as a winner, instead of trying to reproduce an exact Script, which was used by a given user. This is needed to make sure, that people can easily spot "lottery vs non-lottery blocks", make sure, that the system is provably fair, and also to avoid huge fees, if someone would win by moving a coin out of 1-of-20 multisig.
When it comes to the exact Script types, then using 1-of-2 bare multisig sounds like a good option. However, it has many drawbacks. First, there are
proposals, related to making them non-standard. Which means, that even though coinbase transactions are obviously non-standard, and spending them may be standard for a long time, then still, creating new bare multisig outputs will be considered as spamming, so it should not be used.
However, by avoiding bare multisig, it simply means, that lottery winners will be wrapped in some kind of hash. This is another reason for 1-of-2 multisig, because hashing will hide the fact, that someone won, and it will probably be needed to sweep the prize more often than not.
Another option is to use 1-of-2 Taproot output, where one key is in exposed key, and another is in the TapScript. However, many Taproot outputs are used for spamming, when spending by TapScript, so picking that path would probably create more spam, and we should not encourage that.
Which leaves us with the last option: a regular Segwit single-key address. It is the only case, where something is non-legacy (so it won't be made non-standard soon), and it has predictable transaction size (because a single signature is not a choice, like in Taproot, but a requirement). The drawback is, that it pushes us away from Schnorr signatures, and forces us to use DER encoding, but it is better, than being censored by some nodes, mistakenly marking our address as "maybe Ordinal".
All of that leads us to the final state of the lottery, from the perspective of on-chain observers: usually a single P2WPKH address, when the fees are below 1000 satoshis, and sometimes two P2WPKH addresses, one with the base amount of 50 tBTC, and another one with fees, sent to the 1-of-2 multisig of the winner, and the miner.
Then, the last question remains: how to convert 1-of-2 multisig into a single key? Well, by exploring concepts like Silent Payments, we can find answers. Simply, we take the winner's public key, and multiply it by miner's private key. In this way, we create a shared key, which can be computed only by the winner, and the miner. If we would send it directly into this key, we would achieve 2-of-2 multisig, so we are almost there.
The final modification is to apply SHA-256 on that public key, and use it as a private key. Then, we would have 1-of-2 multisig, but without any information, who spent those coins. Which leads us to yet another concept:
Reality Keys.
Of course, the concept of Reality Keys mentions publishing two public keys, but here, we have a single key for the winner. So, how to solve it properly? Well, there is one important key, which is not that well-exposed: the R-value inside the signature. It is obligatory to put something here, when spending the coin, which means, that we can put either miner's R-value here, or winner's R-value.
To achieve that, we can consider building a commitment, as described here:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022176.htmlAs "data", we can use "<winnerSig> <winnerKey> OP_CHECKSIG". Then, any of two parties could release a commitment, but only the winner would have the proper key to create a valid commitment. Which means, that because of 1-of-2 multisig, a miner could potentially broadcast a commitment, containing winner's key, but still: only a winner would have the private key to make this commitment in the first place.
And this fact would be enough to count properly, how many rounds were won by miners, and how many were won by regular users. This is needed, because nodes could exchange those kinds of commitments in a P2P way, and use it as an indicator to pick the winner of the next round (for example by not selecting the same winner over and over again).
Show Posts
