Quantum Recovery Of Hashed Address Secured Coins With No Confiscatory Risk

[shinobimonkey]

Currently the discussion around how to address the potential risk of a viable quantum computer centers around two primary issues: the quantum-safe signature schemes (or schemes) to integrate for users to migrate to and use if need be, and what (if anything) to do about any coins that remain secured by vulnerable ECC based scripts, specifically should these coins be frozen, and what mechanisms are available to allow legitimate owners to recover those coins if possible without an attacker having the ability to do so. 

This second issue is (and always has been) a very socially contentious one, as the common understanding is it is impossible to guarantee with certainty that no user is being left in a position where they are incapable of generating a recovery proof, and therefore are forever prevented from accessing their coins. 

My motivation for writing this is to solve this contention (at least partially) in a manner that can hopefully move discussions forward in a productive direction rather than lead to two opposing plans of action eventually colliding in the real world with live implementations of conflicting rules. 

The current solution landscape as it stands to my understanding is: 

• BIP 32 hierarchical proofs, as proposed a decade or so ago by Adam Back and recently implemented as a proof-of-concept by roasbeef. 
• Non-deterministic stateful proofs constructed and timestamped before a deadline, showing a vulnerable ECC key signing off on a quantum-safe authentication mechanism to be used for spending after a post-quantum spending restriction is activated
• Tim Ruffing/Tadge Dryja's idea (I apologize, but I forget who was the actual originator of the proposal) of a commit-reveal migration scheme where a transaction spending vulnerable ECC inputs must have an encrypted commitment to that exact transaction confirmed in a block with a pre-determined number of confirmations prior to the decrypted plaintext transaction's confirmation, or the decrypted transaction is invalid. 

All three of these proposals leave some subset of coins uncovered. HD proofs are useless for users who generated their keys any other way than BIP 32, stateful timestamped proofs are useless for any inactive user or someone who for any reason does not create them before the creation deadline, and the commit-reveal migration is useless for anyone with an address type that isn't hashed because any attacker would have access to the material needed to create a valid pre-commitment for a spend. 

However, by layering them, and allowing any single one of them to be used, complete coverage of any conceivable key generation method can be achieved for hashed address types. Coverage of non-hashed address types is fundamentally impossible, because the requirement to allow use of commit-reveal migration would inherently leave such address types still exposed to a quantum attacker. 

• Hierarchical proofs cover any BIP 32 user
• Stateful timestamped proofs cover any active/observant non-BIP 32 user
• Commit-reveal covers any non-BIP 32 user who is inactive/not observant 

The only case in which I can see a restriction of hashed address type spends using this layered approach of recovery would leave a user unable to recover their coins is if they have lost access to their private keys. That case is completely outside of the scope of any of these proposals, and inherently impossible to cover. 

Shinobi

Sent with Proton Mail secure email.

[conduition]

Hi Shinobi, 

Thanks for raising this item. It's a heavily contentious subject with a lot of misinformation flying around.

Before we even think about rescue protocols like ZKPs, pre-registration, or commit/reveal, it is important to understand what a rescue protocol even does. So let me first define another term: Knowledge Asymmetry. 

In this context, a knowledge asymmetry (or KA for short) is a witness to a quantum-hard relation that has been committed on-chain before Q-day. In plain words, a KA is some piece of high-entropy information which an honest coin-holder knows, but which a future CRQC will not know and cannot easily compute or guess.

Examples of knowledge asymmetries include:

• BIP32 parent keys and chain codes (this is what Lalu used in his RISC0 benchmarks)
• EC keys hidden behind a hash, e.g.
• Hashed address types which haven't been spent from
• MuSig peer keys
• Taproot internal keys
• Pre-registered commitments 

KA's are distinct from private keys because currently there exists no standardized means to authenticate oneself using these KA's in consensus, and because KA's are not always perfectly private (e.g. hashed public keys). 

The rescue protocols you cite as examples are all merely different ways to modify consensus so that KA's can be used to rescue coins that don't move onto explicitly quantum-safe addresses in time.

• Lalu's ZK-STARK benchmarks show how to authenticate a BIP32 KA using the RISC0 STARK prover, but generally a ZKP can prove any computation, and allows fast verification. 
• Commit/reveal strategies can prove any KA that can be verified by publishing a witness (e.g. by publishing a preimage and recomputing its hash, in the case of hashed addresses, but it's more general than that).
• Pre-registration is a way to create new KA's where they may not already exist (e.g. for exposed-pubkey JBOK wallets), under the assumption we will introduce a way to authenticate those KA's later.

Pre-registration is a bit of a red-herring in my view. If a user can pre-register to create a new KA, why not simply move to a quantum-safe address? Or move to any standard BIP32 wallet or hashed address, where known KA's abound? So i will discount pre-registration as a rescue scheme for now because it seems excessively complex and redundant.

The other two, ZKPs and commit/reveal, are far more interesting as they let us authenticate existing KA's present on Bitcoin UTXOs, such as BIP32 keys or hashed addresses. Both have their trade-offs. 

The more relevant fact to consider in regards to your OP is: No matter what tool we use to authenticate KA's, there will exist some UTXOs which have no knowledge asymmetries on Q-day. I suspect Satoshi's coins are chief among them, since they are stored on P2PK addresses generated by Bitcoin Core's old JBOK wallet system.

We could theoretically partition the set of all Bitcoin UTXOs into two subsets: Those with KA's, and those without. I like to call these the "recoverable" and "unrecoverable" sets of UTXOs. 

The unrecoverable set unfortunately cannot be rescued from a QC, no matter what rescue protocol we devise, because there exists no provable mathematical distinction between the honest user and the future CRQC. The only route left there is KYC or "trusted salvage" by a CRQC.

For the recoverable set (those with KA's), we can further classify them based on the types of KA available to each UTXO: some UTXOs have multiple KA's. 

However, these sets all have unknown size and volume because - with the exception of hashed addresses - it's hard to tell at a glance which KA's a particular address has available. This makes it hard to justify what KA's to prioritize authenticating, so we kinda just have to go by dead-reckoning.

With this in mind, I would like to correct a few statements in your OP:

However, by layering them, and allowing any single one of them to be used, complete coverage of any conceivable key generation method can be achieved for hashed address types.

It is still possible to have a UTXO on a hashed address which contains no KA. Consider a paper wallet, generated randomly (not from BIP32), which has already been spent from previously and so has an EC pubkey exposed on chain. Unless a new KA is introduced (by moving coins or pre-registration), no rescue protocol can save this UTXO: it will either be stolen or frozen.

Coverage of non-hashed address types is fundamentally impossible, because the requirement to allow use of commit-reveal migration would inherently leave such address types still exposed to a quantum attacker.

Not true. P2TR UTXOs can be rescued using internal keys as a KA, which are essentially preimages hidden to the quantum attacker. Pick an internal pubkey P​ with output key P' = P + H(P) * G​, and give P'​ to the CRQC. Though they can factor P'​, they cannot guess P other than by brute-force (or Grover's search).

By default most P2TR software generates the output key with a hidden internal key in this way even if no scripts are present (example), and this is standardized in BIP86 so I believe most P2TR wallets have a KA and so can be rescued. Even if they didn't have an internal key, any P2TR address can use BIP32 as a KA since most P2TR addresses are derived from an HD wallet. 

The same would apply to any P2PK key generated using hashes, though I think these would be very rare.

regards,

conduition

--
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+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/sdGGYMMWowlFff6Yh8usMel61HVYmV8KPMqT9np2kK7GxPbVaogJ2aJSFe4v16VNLef4eDwNgfReiK-7j-sYn1jlXHPoAPWAwNBbSJxEz3M%3D%40protonmail.com.

[shinobimonkey]

• No matter what tool we use to authenticate KA's, there will exist some UTXOs which have no knowledge asymmetries on Q-day. I suspect Satoshi's coins are chief among them, since they are stored on P2PK addresses generated by Bitcoin Core's old JBOK wallet system.
  

I don't see what the point of your response is here, given I specifically and explicitly state in the original post that address types revealing public keys on-chain are out of scope here, uncoverable in this way due to the proposal involving commit-reveal as an allowed mechanism. The whole point of this proposal of these three (or as you pointed out validly, just the ZKP + commit/reveal would achieve the same coverage and the stateful proofs is redundant) specific mechanisms is that they can be applied only to hashed address types, leaving P2TR and P2PK as a separate matter. 

• Not true. P2TR UTXOs can be rescued using internal keys as a KA, which are essentially preimages hidden to the quantum attacker. Pick an internal pubkey P​ with output key P' = P + H(P) * G​, and give P'​ to the CRQC. Though they can factor P'​, they cannot guess P other than by brute-force (or Grover's search).
  

Again, I don't see the point of the reply here, as this would be a completely separate recovery mechanism than the combination of these two/three specific things. These specific mechanisms layered together, and applied as an additional encumbrance only on hashed address types, ignoring P2TR and P2PK, would achieve complete coverage of any feasible key generation scheme. 

• It is still possible to have a UTXO on a hashed address which contains no KA. Consider a paper wallet, generated randomly (not from BIP32), which has already been spent from previously and so has an EC pubkey exposed on chain.
  

Whether it was generated with BIP 32 or not is irrelevant if the address is reused, obviously in a quantum threat scenario address reuse is a fatal mistake. The same thing is true of revealing your xpubs, which is just as widespread (if not moreso) of a practice. That completely undermines the KA that HD recovery proofs depend on. I don't see how this is a useful response or criticism, unless you also want to apply the same degree of criticism to HD recovery proofs in general as well. 

Preparing for a post quantum Bitcoin will require lots of ancillary hygiene practice changes and tightening up when it comes to managing data like that if we don't want these type of preparatory schemes to be undermined by poor practices.  

Accepting this reality, and only applying these three (or I guess two) additional recovery encumbrances to hashed address types (i.e. not P2PK and P2TR), any user should be able to recover all of their hashed address secured coins in all situations except key loss or address reuse (and this is ultimately not special to this proposal, any recovery or preparatory scheme to deal with quantum short of just giving users a new address type and them outright migrating will require that users begin to treat and handle public key material differently for it to work).

Shinobi

Sent with Proton Mail secure email.

[conduition]

I don't see what the point of your response is here, given I specifically and explicitly state in the original post that address types revealing public keys on-chain are out of scope here, uncoverable in this way due to the proposal involving commit-reveal as an allowed mechanism.

The words you quoted were written as a counterpoint to your claim that "by layering them, and allowing any single one of them to be used, complete coverage of any conceivable key generation method can be achieved for hashed address types." My point was that your claim is not true because some coins don't have KA's (because of how their address was generated and used previously) and thus can't be rescued. I used satoshi's coins as an example but the same is true of some coins on hashed address types (see my reused paper wallet example).

Any UTXO which does have a KA is perfectly rescuable, regardless of the type of address it sits on. It just so happens that some address types encourage more KA's than others (e.g. hashed addresses), but not all coins on such addresses will have a KA and be recoverable after Q-day rolls around. Often it's impossible to identify those cases with certainty.

Again, I don't see the point of the reply here, as this would be a completely separate recovery mechanism than the combination of these two/three specific things. These specific mechanisms layered together, and applied as an additional encumbrance only on hashed address types, ignoring P2TR and P2PK, would achieve complete coverage of any feasible key generation scheme.

You said in your OP that "Coverage of non-hashed address types is fundamentally impossible", and so you focus mostly on hashed addresses in your proposal. My point is that your claim there was wrong, that P2TR coins can be rescued because they have one or more KA's, and the text you quoted shows an example of a KA in P2TR which can be used for rescue.

I point this out because any rescue protocol proposal should seek to cover as many UTXOs as possible (within reason), so we ought to cover P2TR coins as well if it's feasible to do so, which it clearly is.

Whether it was generated with BIP 32 or not is irrelevant if the address is reused, obviously in a quantum threat scenario address reuse is a fatal mistake.

That's not true, it is highly relevant. If a hashed address has an EC public key exposed on-chain prior to the activation height of the rescue protocol fork, then we can mark that address as having no "hashed address knowledge asymmetry", and disallow the use of that specific KA for coins on that specific address. Other KA's like BIP32 derivation would remain completely usable for rescue.

The same thing is true of revealing your xpubs, which is just as widespread (if not moreso) of a practice. That completely undermines the KA that HD recovery proofs depend on.

Also not true. Revealing your account-level (i.e. m/44'/0'/0'​) xpub does not give a quantum adversary any information about the extended key at the coin-level (i.e. m/44'/0'​). Wallets typically never share these keys, even in complex multisig setups. The hardened derivation of the account-level xpriv key (at m/44'/0'/0') is exactly the quantum hard relation that the BIP32 KA relies upon, and knowing the account-level xpriv doesn't give you any help in deriving it from the coin-level parent key. I'd encourage you to revisit Laolu's thread on the ML and you'll see this is exactly what his best ZKP benchmark does.

However, revealing your xpub does give a CRQC the ability to forge the hashed-address KA proof, because they can re-derive the hidden public key, crack it, and forge a signature + KA-proof to steal the coins. Since xpubs are shared off-chain, validator nodes won't know that they should disable the hashed-address KA for children of the exposed xpub. So there is some meat to the argument that we ought not to allow hashed address KA's at all, because they would encourage selling of xpubs to CRQCs and enable more theft than would otherwise be possible. I'm personally still undecided on this problem.

I don't see how this is a useful response or criticism, unless you also want to apply the same degree of criticism to HD recovery proofs in general as well.

I'm not trying to criticize you or your proposal, other than by correcting false statements. I'm sorry if my prior reply was confusing, I can write a bit indirectly at times.

The general idea of layering different KA's is excellent, and I fully support it. But it's also important we be accurate about which coins can and can't be rescued, as this is a very important factor which ML readers will use to weigh the pros/cons of supporting or rejecting a rescue protocol soft-fork, and as i said earlier, misconceptions abound here.

The most common misconception I see in this field of research is that people think too much about the proving mechanism and not enough about the knowledge asymmetries and hard relations. The exact tooling used to prove & authenticate KA's (ZKPs, commit/reveal, etc) should IMO be decoupled from the discussion of which coins can/can't be rescued. Pretty much any KA you can authenticate with a ZKP can be authenticated with commit/reveal, and vice-versa.

So there should really be two discussions:

1. Which knowledge asymmetries should be allowed for rescue?
2. Which proving system should we use to authenticate knowledge asymmetries?

On the subject of (1), I parsed the point of your OP roughly as "more is better" when it comes to KA's, and mostly I agree. Unfortunately we can't recover every UTXO, even if you scope it strictly to certain address types as you do. There will always be confiscation with rescue protocols, unless you limit yourself only to KA's whose existence can be checked on-chain, like the hashed address KA, leaving all other addresses untouched, which IMO is a bad plan because we'll have poor practical results (1/3 of the supply remains to be siezed or frozen).

On (2), I think you may have some misunderstandings about how commit/reveal works, because you claimed commit/reveal is not useful for proving KA's in non-hashed address types, which is incorrect: Commit/reveal can prove any KA for any UTXO just as well as ZKPs, no matter what address type the coins sit on.

regards,

conduition

[shinobimonkey]

This is just a rewrite of the original message to address some of conduition’s remarks in his reply, and more concisely state the implicit assumptions of the overall idea. I just belted out the original post in a few minutes while I was buried under work, so hopefully this gets across the scope and assumptions more clearly.

There are a number of proposed mechanisms for facilitating the recovery of coins by their legitimate owner by applying new additive encumbrances specifying a new proof of secret knowledge in addition to a signature by a private key, as well as commit-reveal schemes to allow for committing to a transaction spending vulnerable coins and requiring such a commitment to attain a certain number of blocks built upon it before the committed transaction is consensus valid.

None of these schemes is capable of providing complete recovery coverage for all coins whose owners still possess a private key if applied blanketly to a given address type. I believe that by layering multiple recovery schemes together additively, and allowing any single one of them to meet the threshold required for spending, 100% coverage can be achieved by taking on only one new security assumption: the requirement to keep your public key/internal script paths secret.

It should also be possible to account for the fact that most users not running their own full node are leaking master public keys to a third party backend server for balance querying.

To deal with the xpub problem, a new set of derivation paths can be defined for each address type which is specced to only use the Electrum protocol for balancing fetching. By only using individual address queries, you avoid the disclosure of the xpub for these sets of addresses and create a path where for end users a transition can happen potentially even without their awareness. New wallet updates can simply start generating addresses using the new derivation paths and new protocol for balance fetching.

The only complications I can see with this is out-of-box middle-ware that is being used to connect wallets to users’ nodes are built around the assumption of xpubs and using Core’s internal wallet. This is almost certain to be a non-issue in the vast majority of cases as it will be a user connecting to their own node, but even in the small number of cases where a user is connecting to a third party node with such software, it can be adapted to use something like Electrum protocol. I don’t see this being a major show stopper.

The xpub issue mitigated, now the interaction of the of different recovery mechanisms.

Xpub derivation based recovery:

This will cover any BIP 32 based wallet, regardless of what derivation path (?) is used. So this recovery path should encompass both any address generated using legacy derivation paths with exposed public keys, as well as newer derivation paths securing them through the use of the Electrum protocol.

For any hashed-address type (P2PKH, P2SH, P2WPKH, P2WSH) the derivation proof alone is sufficient, and as conduition pointed out in response to my initial post the internal key can additively be used to make this workable for P2TR addresses that do not use the NUMS point.

This specifically ensures that any user with coins using these address types can produce a recovery proof without having to take any kind of proactive action before the activation of a fork implementing additive encumbrances on address types. (It’s worth noting however these proofs will be pretty big, which is relevant for stateful proofs).

Stateful timestamped proofs

This has been pitched multiple times before I can recall but never really described in detail. Simply the basic components of a signature from the existing encumbrance condition over a new authentication mechanism (a public key for a quantum safe scheme), and a timestamp to prove that this attestation was produced before some pre-defined deadline chosen to expire before a viable quantum computer exists.

This could be pretty simply boiled down to the 1) the signature over the new public key/authentication commitment, 2) the timestamp. Given the potential size of ZKPs, and the fact that hash-based signatures can be optimized to ~580 bytes, I think these are still worth considering looking at how much smaller and more efficient with blockspace stateful proofs can be compared to ZKPs.

They do require proactive action, but in the event of failing to do so or losing the proofs after the deadline, the possibility of HD recovery and commit-reveal migration would cover users in that case.

Commit-reveal migration

For any hashed address type, the old commit-reveal migration scheme requiring an encrypted commitment to a transaction be confirmed in the blockchain for a pre-defined number of blocks before the plain-text transaction can be considered consensus valid. The secrecy of public keys can be maintained using the new derivation specification, but this will still be consensus valid for coins in legacy derived addresses.

Again, as conduition pointed out in his reply to my original post, the internal key forms the basis for a secret inaccessible to an attacker, and can be applied as a requirement for P2TR keyspends as an additional validity requirement while using commit-reveal migration. Any tapscript spends using commit-reveal should work as long as those tapscript paths have never been reused with the same internal variables like public keys.

Wrap up

So I think I’ve covered all my bases in terms of implicit assumptions and responding to conduitions comments.

Unless I am fundamentally missing something, or have overlooked important implementation details like those conduition corrected in his replies from my initial post, I believe this combination of these recovery mechanisms can achieve 100% recovery coverage for every address type live on the network except P2PK outputs and custom bare scripts with the singular new security assumption of maintaining the secrecy of public keys (which as noted above can be accomplished with a rather painless migration behind the scenes for users and without the need to go through the process of generating a new master key and migrating funds across seeds).

So I guess, yeah…what am I overlooking here?

Shinobi

Sent with Proton Mail secure email.

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/XeI-rNO4AO9UCO-CL4K8scZ8VZjc_5ctaY4sw98wepKsOgEQkpExB8eagrO_TqplOUpt9WERYxitzsoCaIjoz99M9mfrrIYMKkdMij1_Pls%3D%40proton.me.