I've had fun discussing these rough ideas regarding post-quantum migration to a few people in the last week. Rather than describing mechanics of how to do any of the below via soft fork, which I do believe to be possible, I'm leaving those details to a future exercise. The purpose of this post is just to introduce the ideas as thought experiments. For the below, I'm assuming a future where: - We have a new quantum-safe output type pre-qday - Some new validation rules are activated post-qday (Something like Tripwire and/or manually) - Post qday, all legacy output spends must be fully collateralized in order to be spent (more on this later) - Post qday, all legacy output spends must be have outputs that meet certain conditions (time-locks and alternate spend paths) Note that the last two requirements are similar to vault/covenant constructions, but in this case their behavior could be enforced implicitly by soft-fork rules. ## Quantum Landmines This is a commit/reveal scheme, similar to those which have been discussed here, but with the addition of a payout in the case of proven theft. Alice has 3 unspent outputs: 1btc in a legacy output type, 1btc in a quantum-safe output, and a trivial amount of btc in another quantum-safe output (the landmine). Let's say that her legacy output is p2pk, though any legacy output type would work. Pre-qday, when Alice funded her trivial quantum-safe output, she also embedded within it a proof-of-knowledge. For the sake of example, imagine this is a taproot-like tree. So in addition to its script-spend-path, it also contains a leaf which commits to a new quantum-safe pubkey and is signed by her legacy p2pk private key. The existence of this leaf is never revealed unless/until it is used as a proof. Post-qday, in order to spend her legacy p2pk coin, recall that the new rules require that it must be fully collateralized. So she creates a transaction consisting of both of her 1btc inputs and a 2btc quantum-safe output. The output has the following implicit spending conditions: - If re-spent within (say) 30 days, a proof of pre-qday knowledge of the private key is sufficient to spend - If a proof is provided, the output's pubkey must be the same as the one signed for in the above proof - If re-spent after the time-out, no proof is required and it can be spent as usual. To see why this is useful, let's now consider the same scenario, except that a quantum attacker is attempting to steal her p2pk coin after finding her private key. The attacker creates a transaction consisting of their own quantum-safe 1btc coin (for collateral) as well as Alice's vulnerable 1btc as inputs, and a 2btc output with the same required spending conditions described above. Because they have no pre-qday proof-of-knowledge of Alice's key, the attacker would have to wait the 30 days before they can re-spend the output. However, Alice notices the transaction in the meantime and spends the in-limbo output to her committed-to key by including her landmine as an input and revealing the proof. In doing so, she moves her own coins while also taking the attacker's collateral. Unbeknownst to the attacker, Alice's trivial output, which looked just like any other quantum-safe output, actually contained a landmine. This scheme is especially interesting because it actually incentivizes Alice to bait a quantum attacker pre-qday in order to double her vulnerable coins later, and thus makes quantum attackers wary of stealing coins as they may be secretly guarded by mines. It also muddies the waters so that on qday, it's not possible to analyze how many coins are vulnerable to theft. ## Staked Auction The obvious problem with relying on landmines alone is that the associated private keys for many vulnerable outputs are believed to be lost, thus a quantum attacker could reasonably assume that they are not guarded by landmines. But what if we could devise a similar collateral/commit/reveal scheme to empower users who stake their coins pre-qday in order to thwart a quantum attacker post-qday and take their collateral? Let's add a new required spending condition, so there are now 3 ways to spend a legacy output: - If re-spent before the initial landmine timeout, a proof of pre-qday knowledge of the private key is sufficient to spend - If re-spent after the landmine timeout but before the auction timeout, a bid is sufficient to spend - If re-spent after the auction time-out, no proof is required and it can be spent as usual. Bob suspects that an old legacy unspent output of 50btc has no associated landmine and thus a quantum attacker will try to steal it in the future. Pre-qday, He creates a quantum-safe output of 50btc with a secret leaf, but in this case it commits to a the vulnerable output, a bid amount of 40btc, and a new pubkey. This unspent transaction represents a staked bid of 40btc in the event that a particular vulnerable output is ever spent. In order to keep bidding sane, the allowed depth of bid-leaves could be constrained. Post-qday, a quantum attacker finds the private key associated with the vulnerable 50btc unspent output and spends it, along with the required 50btc of their own as collateral, to an output which has the above spending conditions and is worth 95btc. This represents a bid of 45btc. Because no landmine exists, the initial timeout comes and goes. Now an auction begins and continues until a second time-out. During this auction period, Bob reveals his staked 50btc output with a 40btc bid, and uses it to take 40btc of the attacker's collateral. The original stolen coins are lost, the attacker loses some or all of their collateral, and the auction continues. If nobody outbids him, Bob takes the 40btc as profit. Carol sees Bob's winning bid and repeats the same process, using her staked 50btc to reveal her secret bid of 30btc. The auction continues, but nobody outbids her and the auction times out. She can now claim the 30 coins as profit. The staking requirement limits how many vulnerable coins a future quantum attacker can bid on before qday. There are many ways this could be designed. Bob could get his coins back so that a bid carries no risk, or be slashed for a losing bid. Unused collateral could be burned, or given to Carol, or given to miners, or thrown into a pot for later use. Staking requirements could be 1:1 or x:y. Staked time (coin age) could be taken into consideration. Etc. Notice that in this design, as long as there is a landmine or a staked lower bid on the vulnerable coins, they are never successfully stolen by the quantum attacker. The vulnerable coins are burned, and it's the attacker's collateral that is claimed by the auction winner. The attacker only ever makes away with the stolen coins if no one outbids them. Thus they're incentivized to make a very conservative bid. ## Sats Auction When describing the above auction scheme to Neha Narula, she suggested that the well-understood Dollar Auction game [0] could be used as well. See the link for more details and intuition, but I'll summarize briefly how it could be used here. In this case, there's no need for pre-qday staking. The spending/timeout mechanics are similar to a Staked Auction. Every spend of legacy coins triggers an auction after the landmine timeout. The highest bid wins the coins minus the bid, and the second-highest bid loses its bid and collects nothing. The auction continues until there are no more bids. Participants may keep bidding more in order to prevent themselves from ending up as the second-highest bid and thus having to pay. As a result, it's possible that a quantum attacker trying to spend a vulnerable 50btc output ends up losing all their collateral. Bidders could even attach additional inputs to keep the auction going beyond the value of the vulnerable output. This is interesting because, as the Wikipedia article mentions, the logical conclusion is for the attacker not to play. Also, because there is no pre-qday commitment requirement, the original coin owner (outwardly indistinguishable from an attacker) would actually have a chance at partial recovery if they chose to start the auction themselves. Similar to auction A, there are lots of knobs and levers here: - Collateral ratio - Min/Max bids and intervals - Where do the loser's coins go? ## Desired Auction Outcome Having thought about these for a week or so, it's clear that there are lots of interesting ways to dissuade a quantum attack via a vulnerable coin auction using incentives and game theory. However, it's unclear what the best design would be because it's not even clear to me what the most desirable outcome would be. - Attempt to prevent a quantum attacker from ever attempting to steal in the first place? - Attempt to encourage staking via auctions, with quantum attackers sometimes winning to encourage the process? - Attempt to redistribute the coins as randomly as possible? If so, an auction could be designed to work more like a lottery, where every unspent output is a lottery ticket or authorization to bid. To complicate things even further, the most desirable outcome may even change as time goes on after qday, as the vulnerable coin spender is increasingly likely to be an attacker as opposed to the original owner. [0]: https://en.wikipedia.org/wiki/Dollar_auction -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/40a9f73d-481f-47e6-a64b-acfb2c7f4fa8n%40googlegroups.com.