Running testnet lottery by miners

[ercewubam]

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.html

As "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).

[BlackHatCoiner]

What problem does this solve? What's a "lottery system"? I think I've encountered the term before, but I'm not sure what it means. The way I understand it, and please correct me if I'm wrong, is that I can verify that the lottery is provably fair. For example, random numbers are selected based on the block hash, which is, from a game theoretical point of view, provably random.

[ercewubam]

What problem does this solve?

The problem of using complex scripts, like OP_LOTTERY, to introduce that kind of system in the first place.

What's a "lottery system"?

For example, you have a famous HI-LO game (but not only that). Your deposit is your transaction fee, so everyone is playing, except for example miners, doing transactions in a range of 0-1 sat/vB.

An example of getting numbers in range 0-10000, to determine the result of some round: https://s3.amazonaws.com/roll-verifier/verify.html

If you would want to get it on-chain, you would need something, like an additional OP_LOTTERY opcode, which would return you a single number in range 0-10000, and then you would have some "OP_IF <winnerKey> OP_ELSE <minerKey> OP_ENDIF OP_CHECKSIG", to claim the reward.

I can verify that the lottery is provably fair

For this purpose, all that is needed, is having a blockchain (which every full node has). Also, pruned nodes keep the last N blocks, so it should be sufficient for verification of the latest lottery rounds.

In general, verification is easy: you observe the chain, and you know, how many nodes are running the lottery, and how many are not supporting it. Then, you can make some statistics, and determine, how many coins should be sent to the users, to keep the lottery running. And as long as there are enough miners, willing to share their fees with the community, the lottery can run indefinitely, and encourage new users to participate in next rounds.

[Ambatman]

In general, verification is easy: you observe the chain, and you know, how many nodes are running the lottery, and how many are not supporting it. Then, you can make some statistics, and determine, how many coins should be sent to the users, to keep the lottery running. And as long as there are enough miners, willing to share their fees with the community, the lottery can run indefinitely, and encourage new users to participate in next rounds.

I think I read something about the lottery relying on transaction fee and would reach a threshold before it would be implemented.
What about in a scenario where the fee couldn't meet the threshold wouldn't that reduce engagememt if it becomes continuous?
Again on the payout, I think from my understanding it seems like lottery been triggered relies on the miners
Wouldn't this lead to centralization where the miners can delay payout for their benefit?

Like am always seeing miners in almost every step especially since miners can choose the transaction they include in the blocks
They can pick transactions from the broadcasted Pubkeys
Wouldn't using block hash or some Part of it increase randomness thus reduces miners control?

It looks Good because nothing majorly new or complex is introduced to the blockchain
Since you relied on existing activity like transaction fee and Pubkeys.


And I don't even know the essence to be honest or the bigger picture.

[ercewubam]

What about in a scenario where the fee couldn't meet the threshold wouldn't that reduce engagememt if it becomes continuous?

If you have a block, where all fees are below 1000 satoshis, then it means, that you basically have less than 1 kvB of data to confirm. Which simply means, that nobody is using the network at all. And then, it doesn't make any sense to run any kind of lottery, if nobody would receive those coins.

Also, another reason for the minimal amount, is to allow the winner to spend it. Imagine winning 110 satoshis. A miner could obviously send it, but how the user is supposed to make a non-standard transaction, when that user is not mining?

Another thing is that nobody stops you from counting 110 satoshis as a winning amount. But in this case, it should be batched, and for example if someone will win 10 times, then that player can receive 1100 satoshis once, instead of receiving dust amounts in every round.

Ideally, coins from the lottery would be accumulated on a single UTXO, and users would know, how to withdraw the amount they won, at any time. But we are not there yet, because the main network does not support batching things on that level, and forming such coinpools in a decentralized way.

Wouldn't this lead to centralization where the miners can delay payout for their benefit?

1. By default, every user is losing, and all fees goes to miners. Which means, that any non-zero amount of lottery nodes is better for users, than no such nodes.
2. As long as testnet4 is in its infancy, transactions could be free, or almost free, and it won't be harmful. So, that kind of lottery is just some kind of workaround for "free transactions during the early stage". Processing all transactions for free is hard, because even though there are some nodes doing that, then users are not really using that feature. So, it is a way to reward at least some of them, to imitate the initial stage, where early adopters could get their transactions processed for free. Ideally, it could be handled as 1-of-N multisig on all public keys, but it would be too spammy, so it is reduced to a "winner takes all" scheme.

Wouldn't using block hash or some Part of it increase randomness thus reduces miners control?

If you think about alternative implementation of a magic OP_LOTTERY opcode, handling the whole thing, then it is still not resistant to being manipulated by miners. Given enough incentive, a miner can try to drop some block, and mine an alternative version, if it could give a bigger reward in a lottery. It is similar to reorging a block with 10k tBTC fee: if you have some transaction, with some payment to the winner, and the miner can check, if he is winning or not, then that miner can try to game the system, by trying different inputs, as long as it is profitable.

But yes, when selecting the winner, any reasonable input can be used. The bare minimum is the client seed (first pubkey), and the server seed (second pubkey), connected with some kind of nonce (for example as a block number). Then, by mining a block with a hash of some public key, it is an equivalent of revealing some server seed hash. Which means, that in any later block, a client can specify nonce in the locktime field, and reveal some public key, when spending the transaction.

They can pick transactions from the broadcasted Pubkeys

If some transaction is standard, and it is broadcasted to the whole network, then any non-lottery node can also include it, even if some lottery node will exclude it. And then, a winning bet will still be considered, because after reaching a single confirmation, all nodes will count a valid winning bet, as a valid winning bet. The transaction locktime will give us the nonce, the client seed will be revealed as the public key, and there will always be a chance to get a match, if not in this lottery client, then another.

Also, for that reason, sharing commitments in a P2P way is important, because in this way, we can avoid a situation, where every key is rewarded by half of the lottery nodes.

And I don't even know the essence to be honest or the bigger picture.

One reason is that the centralized website, from which I linked the provably fair model, is getting worse and worse, so there is some room, to make a decentralized alternative. Another reason is that testnet4 is in its infancy, and users are unnecessarily paying 1 sat/vB, instead of getting free transactions, or paying 0.01 tBTC, as it was, during the early stages of the mainnet.

And of course, another reason is that I mined more than enough testnet4 coins, so I think about a good use case for them. Or rather: a use case for transaction fees, which reached something around 0.03 tBTC in my case, and it is growing. Because when dealing with coins before the first halving, their amounts are so huge, that limiting all tests into 0.01 tBTC (as the smallest unit) is good enough for everything.

Also, I thought about models like "collect 0.01 tBTC in fees, and then release it to a single winner, picked from everyone, who contributed into that pot". However, I wonder, if it wouldn't take too many blocks to get there, so people can get impatient, if they will have to wait that long, for claiming their reward.

[Ambatman]

Edited

Wow the explanation is quite understandable even for someone that lacks inept knowledge on the technical part of the Bitcoin Blockchain.
So in a nutshell the script would make it possible for users to gain from transactions fee by accumulating dust that would barely have effect on the fee of miners.

Would the fee threshold be fixed? Or subject to fee and if so Who would have the authority to and what's the time interval.

Given enough incentive, a miner can try to drop some block, and mine an alternative version, if it could give a bigger reward in a lottery. It is similar to reorging a block with 10k tBTC fee:

Wouldn't this be too expensive to implement.

[ercewubam]

Would the fee threshold be fixed?

No, because it would require different rules for testnets, and mainnet. In the mainnet, you have "satoshis per virtual byte" model, where 1 sat/vB is the bare minimum. It works well for the network, which is already 15 years old. But not so well for a brand new network, started from scratch. And many altcoins repeat the same mistake, by picking 1 sat/vB, and starting from zero coins, and then wondering, why they are getting a different outcome, than Bitcoin in 2009.

In general, testnets should not start from scratch. There is a difference between testnet and altcoin, we should do the former, not the latter. Testnet miners should not get 50 coins per block, when mainnet miners are getting 3.125 BTC plus fees. And more conditions should be more similar to the mainnet, than they really are. However, it is, what it is. The network was deployed, and we can only stick with some existing rules, and make simple changes, because it is too late for a brand new Genesis Block, for a brand new network model, and for a brand new rules. Testnet4 will succeed or fail, but the whole skeleton is already set in stone, and won't be changed. People will rather deploy testnet5, than fix testnet4, if there will be some bigger failure.

Wouldn't this be too expensive to implement.

There is a command called "invalidateblock", often combined with "reconsiderblock". Usually, it is used in a scenario of re-validating a block (so there probably should be a single command, called "herewegoagainblock" or something). But miners can also abuse those commands, for forking a chain programmatically (which is a soft-fork).

So, no new commands are needed, it is all about re-using, what is already there. But so far, Garlo Nicon passed 9950 tBTC as fees, and it was not reorged. Maybe a bigger amount can be pushed in that way, we don't know yet.

However, cheating in a lottery is a double-edged sword: the traffic in testnet4 is quite low, so miners should be interested in getting new users on the board. And also, if users will abuse the lottery, for example by winning too many times, and using full-RBF, to replace lost bets with different transactions, then miners will stop running the lottery, and start claiming the full reward again.

Basically, that kind of lottery reminds me about a game of trust: https://ncase.me/trust/

And I wonder, how many things can be tested in that way. Can a no-fork sidechain run on testnet, without being wiped by dishonest users? Can some kind of lottery be deployed, without having 100% on miners' side, and 100% on users' side, but reaching a more natural equilibrium instead? There are many things, which can be tested (and which require producing your own coinbase transaction). As long as CPU mining test coins is possible, I am trying to test things, which require mining, also because I know, that when more competition will appear, then the opportunity to test those things could vanish again.

Edit:

Or subject to fee and if so Who would have the authority to

Oh, I guess I misunderstood the question. But well, 1 sat/vB was the de-facto standard for a long time, so I guess nobody will change it soon. Which also means, that picking 1000 satoshi as the bare minimum sounds reasonable. But of course, if people would really want to be pedantic, then they should pick 3 sat/vB of the output winning script. However, I think in case of amounts from 330-1000 satoshis range, they should really be batched before sending.

Also note, that in general, full nodes have the authority to change minimal fees as they please. And if they are mining, then they can actually enforce those rules. And now, for better or worse, we have 1 sat/vB, instead of "free vs 0.01", which would probably be a better fit.

and what's the time interval

The coinbase maturity is set to 100 blocks. Which means, that a lottery node can send some reward first, and then for the next 100 blocks, nobody will touch that, but everyone will carefully observe it. And then, if some user won it, then that user should be ready to claim it (or notify the network of lottery nodes, that the miner lost the game, and didn't pay those fees properly). By sharing a valid commitment (or by the lack of it, for sufficient time), it should be obvious, what happened.

So, the short answer is: all default values are kept, which means 100 blocks coinbase maturity.

[ertil]

As you can probably see, the testnet4 faucet is now running on this anchor: https://mempool.space/testnet4/address/tb1pfees9rn5nz

If fees are set to 1000 sats or more, then the new output is created, and coins are allocated there. Then, coinbase maturity will make sure, that they won't be sweeped instantly, but it will be some kind of lottery, based on network propagation. Also, if users will start using full-RBF to claim them, then they will probably pay some fees, and then, they will simply be used to refill the faucet for next users.