This topic of PQC transaction output types in Bitcoin has been discussed in many different places, but often in somewhat unrelated threads. So I’m creating this thread in the hope to have those discussions in one place.
Before starting, I want to give an overview of what output types I have seen discussed so far, their variations, and their properties. I hope to keep this objective, and will go into my own opinion below. Feel free to suggest corrections or omissions, as I haven’t followed this debate very actively until recently, and the list below is mostly informed by my own interests and the discussions I participated in.
Output types
P2MR “Pay to Merkle Root” (BIP-360): The txout stores the Merkle root of a tree of leaf scripts. Spending reveals the Merkle path, the leaf script, and the inputs to satisfy it. I assume the addition of opcodes or leaf script versions that introduce PQC functionality (not included in BIP-360). This loses some spending efficiency compared to P2TR (see below), but does not reveal EC points on chain before spending.
P2TRv2 “Pay to Taproot v2” (unclear origin): The exact same semantics as BIP-341 P2TR, but with PQC opcodes/leaf types added, and with an expectation that a future consensus change will disable ECC keypath/opcodes just within the output type itself. Leaves an EC point exposed on chain for every output, but is most similar to today’s usage.
P2TRH “Pay to Taproot Hash” (proposed here): Like P2TRv2, but the scriptPubKey contains a hash of the tweaked point Q. Key path spending uses public key recovery (see below), giving it the same weight profile as P2TRv2, without EC point on chain. Needs a new BIP-340 variant, and breaks batch validation.
P2QR “Pay to Quantum Resistant” (unclear origin): Identical to P2MR, but all ECC opcodes are disabled from the start. This makes it unconditionally quantum-resistant, but loses the efficiency of ECC even before Q-day.
Variations
Public Key Recovery (PKR) (proposed here): a special leaf version is added whose “script” is just an EC public key hash. Spending needs just a signature, and verification is done through EC public key recovery to match against the hash. This reduces the spending size by ~32 bytes by not publishing the public key explicitly at spend time, at the cost of needing a BIP-340 variant, and breaking batch validation. This could also be done through a separate opcode instead.
New witness style (proposed here, discussed more here): this allows a new output type (or a new opcode) to access an additional witness extension to the transaction format, which can have arbitrary discount/costing rules for new witness data. This comes at the cost of needing to deploy a transaction serialization change and P2P protocol extension.
Tripwire (proposed on ML): a proof for ECDLP breaking can be published on-chain, and this automatically disables ECC opcodes/keyspaths just within the output type itself. This makes it unambiguously clear that EC disabling is expected.
Miner lockdown (proposed on ML): a softfork signalling mechanism (e.g. BIP-9) is used, not for a separate softfork, but to let a hashrate majority trigger disabling of ECC opcodes/keypaths just within the output type itself. This avoids the need for ecosystem action for EC disabling, at the cost of giving miners more power.
Hybrid PQC opcodes (one scheme discussed here): instead of offering pure PQC opcodes/paths, have them accept hybrid ECC+PQC signatures. This provides security if a PQC scheme were broken (possibility classically) or used incorrectly (especially with efficient hash-based schemes being stateful), as long as ECC is not broken. The downside is (even) larger signatures and higher verification costs.
Separate PQC leaf version (proposed on ML): restrict PQC opcodes to a separate leaf version which has no ECC opcodes. Depending on tripwire/lockdown/disabling semantics, this may avoid surprises when mixing both, at the cost of preventing the usage of (user-defined) hybrid schemes in script.
: only secure if ECC was disabled, or no CRQC exists.
: also secure under the combination of (a) there is no address reuse, (b) there is no pubkey sharing3, (c) no short-range CRQC exists, and (d) there is no collusion between long-range CRQCs and a hashrate majority
: also secure under the combinaton of (a) no reuse and (b) no pubkey sharing, without the need for (c) or (d).
: CRQC is no threat
: not applicable
1: P2MR can be used in a PQC-only mode, which has equivalent security to P2QR.
2: The bytes under “Efficiency” correspond to WU when used with the existing segwit witness. With new witness styles, they can be given arbitrary WU.
3: P2MR can be used in a way that remains secure under a limited form of descriptor sharing before ECC spend, if all ECC opcodes are inside PKH constructions, and no actual EC points are shared. It is not compatible with xpub sharing, MuSig, adapter signatures, or FROST.
Next I’ll give my own (current) view. It is an opinion, and I would like to convince others of its merits, but is by no means a NACK of alternative options.
I believe the best solution is a combination of P2TRv2 and P2MR, covering distinct use cases.
To make “emergency” PQC available to as many users as possible: a P2TRv2 output type, with Tripwire and Miner Lockdown, and with a hash-based PQC signature opcode.
The primary design goal is maximizing ease/incentives for adoption: every user/coin that adopts it, is one that is no longer subject to the steal-or-freeze dilemma. I consider that dilemma an severe threat to Bitcoin (a more urgent one than CRQCs themselves even), because both options involve giving up a fundamental value proposition Bitcoin has. Still, all coins that move to PQC-enabled outputs beforehand are taken out of the equation, and that long tail is something near-future development can have an impact on. Thus, I believe maximizing those ought to be our #1 priority. To that end:
P2TRv2 preserves the same fee profile as P2TR, avoiding “not migrating because it costs more”, and does not lose the P2TR incentives that brings. This also minimizes negative impacts on Bitcoin prior to Q-day.
For developers/infrastructure, it is maximally close to today’s world, avoids the complexity of adding a new witness style or a new ECC signature scheme.
It is compatible with most/all workflows I’m familiar with, including xpub/descriptor sharing (it would mean a static/short list of PQC keys in the descriptor, which isn’t great for privacy, but much better than users not being able to adopt PQC at all).
I’m ambivalent about making the PQC opcode hybrid. Stateful signature schemes are scary, and only permitting them to be used in conjunctions with ECC would give me more confidence about not losing security due to incorrect usage. It however also adds complexity for adoption, and as mostly an emergency mechanism, users may opt for the safer stateless signature schemes anyway.
No P2MR or P2TRH. These add additional complexity, cost, or both, to users that may stifle adoption, and I believe the additional security to be had from the ability to not expose EC points on chain before ECC spending requires careful and uncommon workflows from users anyway (no key reuse, no xpub/descriptor sharing, very different hardware wallet designs, …). Those who are willing to adopt those clearly do not need “ease of adoption”, can thus use P2MR (see below) instead.
The primary goal is having something available that can be adopted quickly. The actual automatic ECC-disabling mechanisms (especially Miner Lockdown) that may be more bikeshed-prone could be introduced later when/if CRQC threats are closer.
To prepare for longer-term full migration, a P2MR-based output type, with Tripwire and Miner Lockdown as well, plus a new witness style to give its ECC usage the same fee structure as P2TR. It comes with hash-based PQC opcodes as well, and post EC disabling, newly discounted versions of those can be added.
The primary design goal is putting the pieces in place for a longer-term migration plan, even if the actual cryptographic schemes to make that realistic don’t exist yet, are too slow/large, or have too low long-term confidence in their security. To that end:
No more P2TR variants, to avoid the overhead/complexity of a privileged ECC-only path which is useless in a post-ECC world.
Starts by adding infrastructure for new witness styles, even though that adds complexity, because a full migration post-CRQC will need those anyway. This likely complicates rollout and adoption, but that is fine; this is mostly intended for usage after Q-day.
Urgency is not as important here, and this can be deployed on a longer timescale than the P2TRv2 output type above. The use of a new witness style may need a lengthy upgrade anyway, because it needs a transaction serialization / P2P change to rely new witness data.
This can also functions as a fallback option for users to send theirs coins to post-CRQC if somehow ECC disabling does not happen in time, or users who want to safeguard their coins for that eventuality. I think the benefits of that option are limited, but recognize there is demand for it.
Depending on which PQC scheme is added here, and CRQC sentiment at the time, hybridization may be more important here, as there is less downside to its complexity and size, and this is intended for longer-term migration.
Use of PKR is possible here, but given that PKR verification is (slightly) slower than normal ECC verification, I don’t think it’s unreasonable to just use normal BIP-340 for ECC instead, and use a costing/discount model that compensates for it.
Regarding “relying on EC disabling”
Let’s zoom out for a bit. All continued use of ECC in the face of rising CRQC probability relies on some entities making the call as to when ECC is to be considered vulnerable, and none of them have perfect visibility into whether a CRQC might exist. The differences between the various schemes are just in which entities those are:
Any scheme implicitly allows the future Bitcoin ecosystem to make that call, through an ECC-disabling consensus change.
With Tripwire, any cooperative CRQC can make that call.
With Miner Lockdown, the hashrate majority can make that call.
With P2MR and P2TRH, the owners of the coins can make that call too, under certain conditions.
The EC-disabling timing problem, as you call it, is the P2TRv2-specific lack of (4), I believe? That is undeniably a difference, but I think it is easy to overstate its importance, as in practice many if not most users of other other output types will equally rely on (1)-(3). Many casual users are likely not paying close enough attention, and will defer to others regardless. Any user that shared public keys/xpubs/descriptors to untrusted parties or reused addresses, gave up their ability to make that call, possibly in ways beyond their control (how can they stop being paid to the same address twice?), or even unknowingly.
So seen in perspective, P2TRv2 is effectively offering users the ability to opt out of making that call themselves. Given that many likely weren’t going to exercise that anyway, and it comes with reduced cost, simplicity, and/or impact on the ecosystem, possibly increasing adoption before Q-day, I think that is a win. And once P2MR is available too, (4) remains an option for those actually willing and able to take advantage of it.
I’m not disagreeing that this results in a tenuous position of needing to rely on timely ECC-disabling, but I don’t think it is unique to P2TRv2. It is the price we pay for wanting to continue to use ECC for as long as possible.
I don’t think things are that black & white.
If you want a “cryptographic” level of confidence, the only option is P2QR (or even disabling ECC entirely). Anything else, e.g. P2MR, involves some hope that one of (1)-(4) above can act in time before a CRQC emerges. We don’t do just P2QR, because of a (very reasonable) trade-off between adoption and security: P2QR would only be adopted by a tiny minority, so we accept (1)-(4) in addition to purely cryptographic assumptons, in exchange for (likely) far more coins being able to move to PQC outputs in the first place. Those who do not want to rely on (1)-(4) have the option of using P2MR in a PQC-only fashion.
Going from P2MR to P2TRv2 is a (IMO small) further step in the same direction: it accepts just (1)-(3) is enough, in exchange for getting an output type that is possibly more easily adopted, cheaper, with less impact on Bitcoin before Q-day. Those who do not want to rely on (1)-(3) alone and want (4) have the option of using P2MR still if both are available.
You can argue that that step is a step too far, and that this trade-off is not worth it. I would disagree with that, but it is a defensible position. Dismissing it as “not cryptography” is not a constructive stance, however.
Regarding “Timing Q-day accurately”
A common theme I see being brought up in predicting Q-day is that we shouldn’t expect a nice progressing of milestones being broken along the way, quipped by Scott Aaronson as:
asking “so when are you going to factor 35 with Shor’s algorithm?” becomes sort of like asking the Manhattan Project physicists in 1943, “so when are you going to produce at least a small nuclear explosion?”
I accept that view, and the conclusion that one shouldn’t wait to deploy PQC until there are measurable milestones. That is, we should be working now towards providing PQC output types in Bitcoin. But that is what we’re doing, I think, and this discussion is part of that.
But I also think it’s good to not take this too far; I expect there will still be milestones, they will likely just happen at a compressed pace, shortly before CRQCs become feasible. The fact that we shouldn’t wait to deploy PQCs isn’t the same as saying we shouldn’t wait to disable ECC. Even a few weeks notice may be enough with Miner Lockdown. If it’s something that’s clearly close to CRQC-levels, I can see that happening without much drama (note, again, I’m just talking about ECC disabling within the PQC output type(s), not general freezing).
This is an optimistic scenario. I obviously cannot promise that this is how things will go. If CRQCs happen entirely unexpectedly, and come into non-cooperative/malicious hands, we inevitably have a problem. However, I think there is little we can do today (besides providing a PQC output type) that improves the outcome in that situation: there will be chaos, forks with emergency general freezes, and various techniques implemented for recovery of old coins. Since it’s likely an undermining of Bitcoin’s value proposition anyway (“altcoin bootstrapped with Bitcoin’s UTXO set”), I see little reason why recovery techniques couldn’t be hardforked in even.
On the other hand, preparing for outcomes where ECC disabling can be timed correctly is something we can do today, so that is where I think our focus should lie.
A small data contribution to the table: I implemented BIP-360 P2MR in Bitcoin Core on regtest and measured spends end to end, so some of the Efficiency estimates can be grounded in actual transaction numbers.
Measured with identical transactions where only the input side differs (one input, one P2TR output, SIGHASH_DEFAULT, a <key> OP_CHECKSIG leaf):
spend
control block
weight
vsize
P2MR, 2-leaf tree
33 B
513
129
P2MR, 4-leaf tree
65 B
545
137
P2TR script path, 2-leaf tree
65 B
545
137
The P2MR witness comes out 32 bytes lighter than the equivalent P2TR script path spend at every depth (except m = 7, where the control blocks fall on opposite sides of a compact size boundary and it is 34), so P2MR effectively gets one extra tree level for the price of a P2TR script path. These are script paths on both sides: a P2TR key path spend at 64 witness bytes stays far cheaper, consistent with the 64 vs 128 comparison in the table.
One omission that may be worth a line in the comparison, since adoption complexity comes up repeatedly: implementation cost. The consensus delta for P2MR as specified is ~96 lines on top of Core’s existing taproot machinery, because witness v2 reuses tapscript execution, the BIP-342 sighash and the Merkle walk unchanged; only the commitment check differs. Of the types listed, P2MR (and P2QR, which shares its structure) is the only one that is nearly free to implement given taproot; P2TRH and PKR need a BIP-340 variant, and the new witness styles need serialization and P2P changes.
Happy to measure other configurations on regtest if concrete numbers would be useful here.
It’s completely the wrong analogy for me. Bombs are the activation of something, not the stabilisation of that thing. QCs require control, not release; they are not bombs. So if you’re going to compare with nuclear you have to argue it’s more like fission reactors (that were created within a span of years) than fusion reactors (which were promised every decade since the 80s but still don’t exist (economically), nearly 100 years after we knew they were possible in theory…).
Hey @sipa and thank you for aggregating all this important information. I think your OP summary and analysis is correct, modulo small discrepancies in byte sizes (e.g. for pushdata length prefixing).
Seeing @fjahr’s impressive CISA proposal has forced me to reevaluate my opinions on PQ output type candidates. CISA provides a natural vessel for P2TRv2 which is asymptotically (as the number of outputs inputs grows) so efficient as to only require 1 byte witnesses for full-agg EC spends. This is exactly the kind of incentive we want in a PQ output type: Better efficiency than even P2TR, so much better that even users who don’t care about PQ-security will migrate to it. The problem of course is that, like P2TRv2, CISA’s output type requires we post bare EC pubkeys on-chain in the SPK and so it has the same PQ-security profile as P2TRv2.
P2MR can also be deployed with CISA, but we cannot use public-key recovery (except for with one input, according to @starius), and we must instead publish the EC public key for each aggregated signature. This would lower P2MR’s asymptotic per-input EC spend cost from 96 bytes (with PKR), but only to 64 bytes (with CISA), almost at par with P2TR today.
This trick works for P2TRH as well, with asymptotic EC witness weight reduced to 32 bytes per input (just one pubkey per full-agg output).
Of course, in all cases, these EC efficiency gains evaporate on Q-Day.
If CISA didn’t exist, i think deploying both P2TRv2 and P2MR in tandem as you suggest would be reasonable.
However, if CISA is deployed concurrently, then P2TRv2+CISA will be so overwhelmingly efficient compared to P2MR (with or without CISA), that I expect most users will gravitate towards P2TRv2, and the economic security of P2MR coins will still ultimately hinge on P2TRv2’s key-spend path being safely disabled in time.
That’s not necessarily a bad thing - more users on addresses with PQ keys is a win. But this makes the stakes higher: With CISA, disabling ECC and switching to PQC is now even more expensive than it would’ve been without CISA. More users will be affected by such a change. We can expect even more fierce debate over when and how to activate the EC disable fork, and harsher consequences for timing it wrong.
Possibly the risk is worth it, in return for the migration incentive. I’m not sure, haven’t made up my mind yet. But regardless, we’ll still want P2MR (possibly deployed without any ECC?) for maximum efficiency after Q-day. So it’s just a question of whether we want P2TRv2+CISA as an (extremely enticing) intermediate stage in that migration path.
The far more interesting research avenue IMO is to try to bring P2MR’s PQ efficiency up to speed with that of CISA, to the point that P2MR outcompetes legacy EC output types.
For the uninitiated, this would allow us to aggregate thousands of hash-based signatures across a whole block into one succinct (few hundred KB) proof which would suffice to convince any validator that they verified a signature for every message/pubkey pair in a given block. The actual signatures never need to be saved, even by archival nodes.
My biggest concern with this approach is the complexity of circuit design. We don’t want a repeat of the Zcash inflation bug. But if this risk can be mitigated through formal verification or other modern cryptographic tooling, then maybe SNARK aggregation could be the silver bullet to incentivize migration to PQ.
With a mostly constant-size block-wide proof of sig-validity, individual signatures would need to be weighed not by size, but by proving cost, which can be reduced to a few hundred hash compressions (or less with stateful signatures). Flock can prove validation of hundreds of such signatures per second, especially when parallelized.
It would require some very careful re-engineering of Bitcoin’s traditional size-based fee accounting systems, but if done correctly we could massively increase the network’s throughput while also incentivizing migration to natively PQ-secure wallets, with no EC cruft carried over.
I’m not sure how viable this strategy will be yet, but i want to mention it for consideration. The game board is very large, and we have many more and better options than I used to believe.
I love signature aggregation, primarily because of its privacy-incentive mechanism (it was the original motivation for MuSig(1), and the broken scheme that preceded it), but I’m not convinced that it matters that much in this context.
There are two hurdles to overcome when getting users to adopt new output types:
Software/infrastructure needs to be available. This is the hard one: you need to convince developers of open source wallets, hardware wallets, proprietary wallet software, and centralized custodians to implement it. Especially the last one seems to take a long time even for small changes like sending to new address formats, and even longer for changing receiving/managing. As I see it, the latter is mostly through:
Companies out of business / projects being abandoned, and their users migrating to others, especially newer ones built in more feature-rich software stacks.
Companies seeing a business advantage directly, e.g. because there is a high-fee environment and they pay transaction fees as a business cost. It’s possible that for some, PQC itself is sufficient here (maybe if thou-shall-use-PQC regulations would appear in some legislatures), but not the long tail.
Users demanding it at scale.
Users must want to adopt it. Software/infrastructure forcing users to migrate is somewhat possible but rare and frowned upon, and more commonly it’s presented as an option (“legacy wallet” / “segwit wallet”) retaining compatibility.
In my view, (1) is unlikely to be influenced significantly by feerate gains (IIRC CISA has a max WU reduction of ~28%, and only for extreme many-inputs few-outputs transactions), unless we re-enter a high-feerate environment that persists for a long time (months at least, business/project decisions tend to move slowly), unlike today where feerates are pretty much their historic lowest ever (in BTC terms, at least). On the other hand, (2) may be influenced more by feerate, but I don’t think that’s really the bottleneck. Rather, I think the converse effect is more relevant: users may not want to adopt things that increase cost. This is why I argued against (pure) P2MR before.
On the other hand, (1) is likely influenced significantly by implementation complexity, and CISA does add to that. Of course, I expect the actual aggregation to be optional, allowing adoption of P2TRv2 without it, but then the benefits and incentives of feerate reduction through aggregation also disappear. I even have a mild concern about entities taking a stance of “we’ll do a big rewrite one day and switch from P2TR to P2TRv2+PQC+CISA, but stick with P2TR for now”, causing them (and the ecosystem with it) to miss out on PQC adoption until that time.
I’m happy to hear more thoughts here, but (and I hate to say that) my initial reaction is actually that adding CISA to the mix may be a net negative for the goal of getting the long tail to adopt PQC, due to more complexity in getting the output type spec’ed and softforked in, and (probably) little change in incentives for adoption.
Unless we enter a high-feerate environment again (which I think we need in the long term, but I’m not very hopeful), I don’t think CISA will change much here. If P2TRv2 and P2MR are both available, I expect some of the more sophisticated (users+software stacks) to choose P2MR, but P2TRv2 can act as default catering to the long tail (“just stick a PQC script path in there, and bump the witness version”).
I agree.
It depends on what the PQC, or even ECC, usage in P2MR is like. Have you seen the discussion on new witness styles? In a post-CRQC world, we likely need to move away further from witness-serialized-size as resource limiting metric, and give more relative weight to computation, because in particular hash-based schemes have a much larger size per CPU than ECC, so size stops being a good proxy.
We may want to use a scheme like the one discussed in that thread in P2MR, even for the ECC part. This would complicate matters for deployment and adoption (needs P2P changes to relay additional witnesses), but if/when it is clear CRQC are coming, we’ll want that complexity adopted as much as possible before Q-day anyway. I wouldn’t do this for the intermediary-step P2TRv2 output type, but if the differentiation becomes that P2MR is more for the longer term, it does make sense to have it there from the beginning even if that delays P2MR somewhat.
With that, it becomes possible to assign arbitrary cost functions (as long as they’re 32 WU per transaction or per input, depending on design) to new output types / spending mechanisms. For example, P2MR with a key-like script at depth 1 could be given the same cost as P2TR today. Or, it may even be reasonable to assign it a cost that’s similar to CISA, without actually needing aggregation of the signatures. This can be justified too, due to batch validation at the transaction level actually having similar performance for validation as half-aggregation (full aggregation is still better).
The actual signatures never need to be saved, even by archival nodes.
They still need to be relayed, however, to reach miners who can then aggregate them into blocks. I am very skeptical about the idea of having aggregation be done incrementally by third-party relay nodes, as the bundling of transactions removes the ability to reason about them individually. I worry this will quickly incentivize direct submission to miners instead, entrenching existing mining pools.
It’s a really cool development, but I do worry about it effectively hiding the real cost of bandwidth within the consensus layer that still exists. One possible future outcome, if we lose sight of that cost, is that the real consensus network is just mining pools + a few fast relays between them, and the rest of the network with weaker network connectivity lagging behind after just receiving the aggregate proofs. That’s sufficient for auditing after the fact, but removes them real participation in the form of feerate estimation / mempool / replacement reasoning, …
Now, all of this at the level of individual transactions is fine. If it were the case that an aggregate proof can be constructed that has a size comparable to say a dozen individual signatures, it would allow for effectively PQ CISA, where network users are (possibly very strongly) incentivized to self-aggregate prior to submission to the network already. I would be much more comfortable with such an evolution, but I suspect the numbers won’t really work out for that.
I would caution about thinking of anything as a silver bullet; most if not all things come with significant trade-offs. I may also just have seen a few too many such claims
I think this is the case regardless of block-wide aggregation or not: a PQC world will need resource metric limits that take weigh CPU more and bandwidth less (but still some). The constants/metrics involved will of course depend greatly on the technology used (what type of PQC, aggregation or not, …), but we have options even without aggregation.
Interesting, so your take is essentially that the fee efficiency of an output type only matters beyond the point where it becomes less efficient than what currently exists?
That’s fair, but CISA isn’t so complex to implement locally, e.g. for single-signer wallets. I think @AdamISZ has even pointed out there are ways to simplify the execution of the aggregation protocol for the common special case where all cosigners are the same entity. And even if devs don’t want to invest the time up-front in doing even the most rudimentary (half) aggregation, they could still very easily deploy the CISA output type using non-aggregated BIP340 signatures for spending. Adding half or full aggregation later is as simple as a software update without any user-action needed (e.g. v3.2.1 changelog: “We made your transactions 26% cheaper!”). So even if devs don’t use CISA’s advantages right away, the CISA output type is still a desirable target for devs and users, more so with PQC in the mix.
I’ve seen the thread but I’m still forming an opinion. Currently i gravitate away from the idea, even for P2MR. On one hand, verification cost is critical for performance and hash-based sigs do offer the advantage of blazing fast hardware-accelerated verification and lost cost-per-byte compared to Schnorr… but witness sizes do still matter.
Verification costs are a one-time cost per-node, but storage costs for archival nodes are eternal. A block size increase of the magnitude needed to make even the smallest (XMSS) hash-based sigs fee-competitive with ECC would be an 8 fold increase (4mb → 32mb per block) at least, larger (more like 64x) if we consider stateless signatures. Someone has to store all that witness data.
This amplifies the absolute cost for archival node storage massively. We’d move from a world where bitcoin’s chain grows by a few hundred gigabytes per year, to a world where chain growth is measured in terabytes per year, quickly pricing out amateur archival node runners like myself.
Think of it this way: If verification of signatures suddenly became 8x slower, most node runners and users - except maybe those who run raspi nodes - wouldn’t notice that much. IBD would get slower, but that’s a one-time cost. We could even mitigate by exploiting multithreaded verification which I believe core currently doesn’t do.
OTOH if signatures and blocks suddenly became 8x larger, that’d be a big problem for the network even if the fee market also became 8x cheaper. IBD and block propagation would also slow down, esp for users with low network bandwidth, and many node runners would need to start pruning witnesses once they run out of HDD space.
Therefore, my stance is currently that to increase the block size, we must also allow retroactive aggregation of signatures (or blocks) via SNARKs to curtail chain growth, and while I think that road is worth researching, it is not in the cards in the near future IMO.
With SHRINCS we have not coupled our proposal to a blocksize increase - at least, not initially. If that’s what the community wants, SHRINCS can be reparameterized accordingly to reduce cost-per-byte, but for our initial draft (coming soon!) we’re not assuming such a controversial change will be necessary. Adding a new sig algo, especially a semi-stateful one, is controversial enough as it is!
I agree the bandwidth cost must be accounted for somehow even in the best case scenario where signatures can be aggregated block-wide with zero cost by miners. I’m not sure how that’d look, still trying to determine if the current SNARK technology would even work for our use-case. Maybe there would be a fixed “min fee per byte” policy requirement for nodes to relay transactions, even though the size of the signature doesn’t really count towards blockspace in that scenario, so that minimum might be very small depending on the size of signatures.
Re: TX-level aggregation, i agree. I am hopeful a more “fancy” PQ signature algo will support CISA-style aggregation someday. Currently the best I know of is Falcon + LaBRADOR, based on lattices, with aggregated sizes of about 80-100 kilobytes. But in the near-term it seems like SNARKs will remain far too large to be practical within bitcoin transactions.
In the long term, I believe/hope that fee effects matter. There will likely be times of mempool congestion with feerate spikes, and future businesses and projects will make decisions that are conscious of fee impact.
But for P2TRv2, which IMO ought to prioritize adoption by the long tail, and ideally soon to give a long window for that adoption. For that long tail, I expect the bottleneck to be software/wallet/custodian support by existing providers, and with high probability in the relatively short term, I don’t think fee arguments will affect them much.
Your point here is about easy of implementation by developers. I agree in principle, except for a minor concern about “we’ll look into this later” if the change seems complex, which I commented on earlier:
The part you’re responding to above is about timing consensus changes, not wallet implementation however. In short, I think adding CISA to the P2TRv2 bundle will increase the time it takes for P2TRv2 to become available, and that will likely reduce adoption before Q-day by the long tail more than fee incentives will increase it. I’m sympathetic to the fact that CISA inherently needs a new output type, which makes it a natural fit for combining, but I still think it distracts from P2TRv2’s goal. If it’s not bundled with P2TRv2, it will need yet another output type, be bundled with P2MR, or not done at all.
Post-Q-day, if hash-based PQC is adopted, I think the need for a different witness costing rule (and thus larger (pre-aggregated) serialized block sizes) is almost an inevitability, regardless of whether block-wide aggregation is involved. The actual formula will of course be greatly influenced by the details, ideally accounting for all facets of resource impact (bandwidth, storage, validation, relay). Historically, serialized size and CPU validation costs were roughly proportional, justifying a largely size-based formula. But with cryptography that has a different CPU/size ratio, it seems inappropriate to only account for size. That doesn’t need to mean that PQC sigs need to be competitive with ECC ones, but some capacity (in bytes) increase seems warranted if it doesn’t come with a proportional CPU increase:
IMO, we will need a new witness extension if Q-day happens, and it seems reasonable to aim to have the technology ready for that before Q-day. A way of doing that in a structured way that improves some of segwit’s pain points is described in the witness styles thread (but that’s just one option), and it seems reasonable (but not necessary) to combine that with the later-stage P2MR construction, as it can give a fee structure even for ECC that matches the incentive structure of P2TR, or even exceeding it by matching (half-agg) CISA.
Sure, someone has to store the full block data, but not everyone. Nodes and their operators themselves don’t need full data (pruning doesn’t reduce security or functionality), and if pressure on non-pruned nodes by IBD’ing new nodes grows too big, block storage could be sharded. Using FEC techniques it is possible to for example let every node store 20% of every block, in such a way that any combination of 5 nodes together can let you reconstruct everything.
Of all the potential ways additional block data impacts network properties, I consider archive node storage size the least concerning. It’s simply never even been close to a problem, and disks have been growing faster than the chain has for a long time already, and furthermore technological solutions exist that can push it further away even.
Yes, it does, since 2013 (inside blocks, not for individually relayed transactions).
IBD is for most users not bandwidth constrained (but we’re getting closer in the upcoming 32.0 release thanks to a number of performance improvements), and I don’t think pruning is an issue.
Bandwidth and CPU cost for validation at the tip however is much more concerning to me, as it’s what allows the network to stay in sync, both between miners, and between nodes. But I also don’t think we need to stick to limits set 9 years ago with the adoption of segwit.
Aggregation, even at the block level, won’t remove the need for bandwidth for transaction relay prior to block building. It removes one facet of the impact of increased sizes (the ability for weak nodes to keep up with auditing the chain). The ability for nodes to participate in providing the market for block space (i.e., the mempool), which is also an important facet of decentralization (allows for permissionless entry into the mining market, without centralized block-building services), isn’t really affected by aggregation. Improving one may justify an increase in the resource limit on pre-aggregated block data, but I don’t think it’s reasonable to disregard that limit entirely and only look at aggregated size.
My stance is that resource limits in blocks should, for the time being, be set in terms of the CPU usage and pre-aggregated bandwidth imposed on validation nodes. Some increases in bandwidth are warranted, both because network and processing capacities have increased the past decade, and because with hash-based signatures, the CPU cost of validation doesn’t have the same per-byte cost anymore. Aggregation is something that can be explored independently, and when it’s ready, maybe that’s a justification for future resource costing.
I agree, it shouldn’t. I think in general the “near-term P2TRv2” idea shouldn’t include any such thing in general.
I don’t really see what that has to do with the signature scheme. To give a different weight to block data (below 1 WU/byte) you need a new witness extension, which is a combination of P2P-level and consensus-level changes, reaching beyond script or signature logic.
Yes…
Policy won’t suffice here. The reason for having resource limits is to prevent miners from creating blocks that have a too large impact, on the network and on each other.
I see what you mean… If we bundle CISA+P2TRv2 then P2TRv2 can’t deploy until CISA consensus validation rules are ready. Perhaps you’re right. I don’t know enough about CISA’s development progress to gauge how big a lift it would be to bundle. @fjahr would be a better source.
However I do think you underestimate the mass appeal of an output type with PQC support which is also the cheapest output type available. Heck, people seem to like P2MR quite a bit even though until very recently it was twice as expensive as P2TR.
If hash-based sigs become the default, then I agree we’ll need to do something drastic, and maybe that’ll be SNARK aggregation, or maybe it’ll be an extension block. Recently i’ve also started thinking maybe we could do both: SNARK aggregation happening after blocks are mined, to assuage the long-term storage impact and make IBD faster.
My hope is that it won’t come to that, and someone will discover a highly efficient PQ signature scheme based on isogenies or lattices or something in 5-10 years’ time, and this can be backstopped by hash-based signatures for safety. But i do appreciate that we should prepare first for the worst-case, and work with what we have without assuming something better will magically appear.
Neat idea. how would one do this in a robust way without some central directory?
aha, i stand corrected!
I’m somewhat undereducated here. Could you tell me, what are the key metrics you care most about in this vein? Block propagation speed? Transaction relay speed?
Do you know of any research on the effects of larger signatures on these metrics?
Agreed. Block-wide aggregation wouldn’t affect the efficiency of mempool transaction relay, so any costing adjustments that consider aggregation also have to keep TX relay in mind too. We can’t just fork in super huge signatures even if they have near zero verification cost. But we can try to strike a balance between performance and size. Thankfully hash-based sigs are extremely configurable.
I’m saying that if compute cost is a more important metric, and a witness extension with a new steeper discount is acceptable, then SHRINCS can be parameterized to target a low computational cost per byte to match the discount offered in the the witness extension.
For example, currently SHRINCS parameters are designed such that verification cost per byte is about \frac{1}{16} of BIP340 schnorr (\frac{1}{4} \times schnorr in the rare case where SHA256 hardware acceleration is not available). Therefore we could justify putting 16x more signature bytes into a block and still incur roughly same CPU cost during signature validation.
However, we could go steeper, to as low as \frac{1}{64} th of the cost per byte of Schnorr, without gaining too much in size. For example, SLH-DSA with parameter set h=40 d=4 a=13 k=12 w=4 would give us 7696 byte sigs (about the same size as standard SLH-DSA-SHA2-128s) but which only cost about 1000 SHA256 compressions to verify. If you use hardware acceleration, that’s about 64x cheaper per byte to verify than Schnorr, so a 64x block size increase would be feasible (modulo bandwidth and storage considerations). Stateful signatures can be made even cheaper.
We’ve been basing our decisions mostly around Schnorr as a yardstick for verifier performance, but if one is comfortable throwing the Schnorr yardstick out the window, we could do even wackier things, like budget for a specific number of SHA256 compressions per block and parameterize for that instead.
The 246/10 approach described there has you divide nodes into 246 groups, each storing 10% of total blockchain data, and you need to connect to (at least) 10 peers from distinct groups, not absolutely any combination of 10 peers.
Happy to chime in, but maybe I am also the worst source since I am biased pro CISA
The two aggregation scheme BIPs (458, 459) as well as the CISA BIP 460 have had a few eyes on them. More would be better, of course, but as far as I am concerned they are complete with reference implementations and pretty extensive test vectors. There are pull requests to secp256k1 for BIP458 and BIP459. Review of the secp256k1 implementations is probably the biggest lift looking at how long Silent Payments took. I consider this the primary blocker in terms of implementation. The Bitcoin Core code is IMO comparatively simple and there should be enough review power if consensus is formed around the change.
I have been thinking about PQ P2TRv2 + CISA since @conduition started raising this as an idea on the ML. This discussion now even prompted me to make a revision of the BIP. This new version of BIP 460 that makes opted-out inputs plain BIP 341 key path spends, details in this BIP pull comments: BIP460: CISA for Taproot Key Path Spends by fjahr · Pull Request #2212 · bitcoin/bips · GitHub (will update the PR after some initial feedback). What this should do is take wallet adoption out of the equation since there is no need for them to adopt any new signing logic. From their perspective P2TRv2 should initially be equivalent with or without CISA since a CISA-enabled witness v2 is a strict superset of P2TRv2’s ECC key path. Wallet support for aggregation can be added at any time without pressure.
I don’t think it has to. I think this is not an unreasonable take given how long Silent Payments has taken to make it into secp256k1 but I am much more optimistic.
I think there are primarily three dimensions that could introduce delays in user adoption: forming community consensus, technical implementation and review, and wallet adoption.
As mentioned above with the latest change using plain BIP341 key path spends as the opt-out in CISA, I think the wallet part can be taken out of the equation. The existence of CISA should not prevent any wallet from adopting P2TRv2 unless I am overlooking something here. I agree that the low fee market may mean that the savings are not compelling enough for everyone but at the very least Payjoin and Coinjoin users and by extension anyone that cares about their on-chain privacy are a developer and user group in the long tail that would be very excited and quick to adopt anyway based on the conversations I have had.
In terms of technical implementation and review I think CISA is currently far ahead of whatever the PQ part of P2TRv2 would look like. Sure, using hash-based signatures mostly takes care of security assumptions but the proposed schemes are all developed very recently and it feels like the whole field is still evolving. The first serious attempt at a library for such a scheme was published less than 2 weeks ago: Libshrincs: A C implementation with a machine-checked security proof . This also goes for the design details of the necessary companion pieces: tripwire, miner lockdown etc. And while certainly some of the most capable people in this space are focusing on this, compared to CISA I think there are still a lot more unknowns and discussions to be had (take this with a huge grain of salt obviously since I know a lot about one but not the other). The most interesting question here IMO is if the review work needed to get CISA across the line draws resources away from the PQ part which then delays that side. I think this is the case to a certain degree since we want the most experienced researchers and developers to review both ideally. But in the range of realistic timelines I don’t think this should make a meaningful difference. On secp256k1 for example, where resources have been very scarce for a while, a group of new people are contributing and reviewing and afaik none of them are working on hash-based PQ stuff in parallel (I did not try to verify this). Part of the work on these hash-based and PQ in general seems to be new contributors that have joined the space recently and have experience in this particular area. The low-ish overlap between these two parts appears to be a strength here. But this is still new territory since we never had a soft fork that implemented two consensus changes that are so different. And I certainly didn’t think I would argue there is enough review power for any big project in Bitcoin but in this case I am optimistic that if we have community consensus we can get both done without delay.
Last, community consensus. It’s impossible to predict what will happen but I can see this going both ways: Either adding CISA gets more people on board quicker, particularly CRQC skeptics, or CRQC believers will argue against it as a waste of time since it wastes resources on ECC stuff. I think that offering benefits for the case that CRQCs are delayed or never happen should help to form community consensus much faster but I have been speaking with people interested in CISA much more frequently than people working on PQ stuff. And thinking a bit more in scenarios: It is highly likely that (in public perception at least) CRQC development with either slow down or speed up in the coming 1-2 years compared to current expectations. If there is a speed-up happening it is relatively easy to drop the CISA part from the soft fork that is in development. But if CISA is not part of the proposal but CRQC development slows down, there may be no appetite for it at all in the community and development/deployment/adoption could stall (wherever we are at that point). CISA can be an insurance to keep driving adoption in this scenario when CRQCs may be closer than they appear. The fact that CISA “distracts from P2TRv2’s goal” may not be a negative for reaching the goal regardless.
@sipa Curious where you see the bottlenecks that would lead to a delay of P2TRv2 if CISA is bundled with it.
I wish you were right, that was the whole idea behind Taproot! But we’re five years in, have seen multiple periods of mempool congestion in that time (some taking months), and not even all providers support sending to it, let alone use it as default for new addresses. Adoption is mostly within systems built around newer features or technology stacks, and stupid hype stuff. Not the large-scale migration we’d want to see for PQC security, neither in terms of BTC nor in terms of users.
Realistically, I don’t think we should expect CISA to have a bigger impact than that, I think. That’s not to say it won’t influence behavior at all, but as I said, I think it’s more a long term thing that will affect future software projects/companies when people inevitably migrate anyway, not existing wallets.
To back this up with actual numbers, here are graphs with logscale vsize savings for P2WPH inputs → P2TR key path spends, and then from P2TR key path spends to CISA. Full-agg CISA can improve over P2TR more than P2TR did over P2WPH, but only for sufficiently complex transactions. That’s the point of course: incentivizing those, but adopting workflows that allow such transactions is an even bigger task than adding PQC as it will typically involve adding interactivity (for CoinJoin/PayJoin like constructions):
That sounds more like an argument that people like P2MR for other reasons than its economics. I don’t see how you’d conclude from this that feerates are relevant to them?
Just to make sure we’re talking about the same thing. An extension block, as discussed years ago as a scalability proposal, is something very different and much more invasive than what we’re talking about here. It’s a completely new block area, with its own transactions and separate UTXO set, and mechanisms to move coins in both directions between the two areas. It’s completely incompatible with existing wallet designs; you need transfers between the two blocks to pay to an old address. It can be done as a soft-fork, but it’s probably the most invasive thing you can imagine that still qualifies.
I am just talking about a new witness in transaction serialization, like Segwit did, and the design discussed here is somewhat less invasive than that even (no need for new wtxids or P2P changes beyond the transaction serialization). I don’t want to minimize the impact either, it’s still a big change, much bigger than just adopting a new output type or introducing a new signature opcode, but it is something the ecosystem has done before.
And I think we’ll want this even if the long-term migration plan ends up using something else than hash-based. Because it’s very unlikely it’ll have the same size/verification characteristics as ECC, even if it’s not as extreme as hash-based. And if we’re going to need it anyway, I’d rather have the infrastructure in place beforehand.
See the thread AJ linked to for a concrete idea, but I’d like to give an intuitive description.
Split your block up into 10-byte chunks. Then extend each of those chunks (implicitly, we won’t actually compute/store these) to 256 bytes, by adding 246 error-correction bytes, in such a way that you can recover the whole chunk if you have any 10 bytes of it (and know which positions those bytes are from).
Every node now picks one (or a few) random numbers in range [0,255], and just stores those position bytes of every chunk. So for every number they pick, they store 1/10th of each block. For reconstruction, it suffices to pick peers which together have 10 distinct numbers. So it is indeed not quite the case you can have any 10 peers (or 5 or whatever, depending on the constants chosen), they need to be peers that chose distinct numbers. It’s possible to switch to more complex codes which offer a larger range of numbers (making the probability of collisions in them lower), in exchange for more reconstruction complexity.
The big one is block propagation speed: practically, minimizing the time between a miner finding a block, getting it across the network, up to the point where other miners can start hashing on top of a successor block. So this includes:
time to relay transactions (if those weren’t already relayed before)
time to validate it along each hop (compact blocks typically allow relay before full validation, but it still needs reconstruction/PoW checking)
time to validate it by the miner (which cannot be skipped; only for transactions not yet validated beforehand)
time to build a new block template on top from mempool (in miner’s nodes)
time for that block template to make it to hashers (internal to miner setup, protocol changes have little impact here).
It’s really only the first one that is directly impacted by block/transaction size, and it is hard to measure its real-life worst-case impact, because in practice most blocks are primarily filled with transactions that were relayed and validated ahead of time. That said, KIT has a page with block and transaction relay statistics going back many years, which shows the impact of adoption of certain technologies and transaction composition changes.
Ah, of course!
I think aiming for roughly the same signature verificiation as BIP-340 seems like a reasonable rule of thumb. It does sound like a potential for bikeshedding, though.
I have one concern here, but it is admittedly a weak one that’s probably addressable with education/communication. If a custodial company CEO hears “a simple change that just adds quantum protection”, they may agree to put resources on implementing it quickly. If they hear “a new output type with several features like key aggregation and PQC”, they may decide “We’ll implement that whenever we need to rewrite that part of our stack anyway”.
Yeah, they would be the obvious parties who would want CISA. But I also expect them to be relatively quick adopters of a PQC output type without CISA? Just by virtue of being users/developers willing to be at the forefront of development. Under “long tail”, I mostly think of many custodial and multi-currency software solutions; they tend to put more effort into supporting more altcoins/tokens than keeping up with (from their perspective, relatively) stable Bitcoin that won’t gain them more customers.
I think that’s fair. CISA adds a fair bit of complexity, but it may well be further ahead than some other aspects we’d also need.
This is where my concern lies mostly.
I feel like P2TRv2 and CISA kind of pull in opposite directions in terms of messaging. The output’s goal is preparing for CRQCs, but then it also adds an optimization that stops working when that actually happens.
Maybe I’m wrong, and there is a good synergy between those parts of the community who would favor it, and I’m happy to support the idea if there is momentum. Still, my belief is that the large class of users we’d want to adopt PQC with a P2TRv2 output type will at scale not really adopt CISA anyway, so that doesn’t help them. And in the other direction, if CRQC-skeptical CISA-fans exist, they may be annoyed at being required to add PQC support to get CISA?
I don’t think five years is the right figure there: rather I think there’s largely four types of common payment paths:
single sig: taproot is very slightly more expensive than p2wpkh due to the larger output (ignoring the prisoner’s dilemma aspect that mildly encourages taproot adoption)
n-of-n multisig: wasn’t more efficient until musig became available which was either late 2024 for libsecp, earlier this year with 31.0 for core, and added to the spec for lightning in May 2026 but still only usable for private channels
k-of-n multisig: we’ve got FROSTsnap signing devices, but as I understand it we don’t have a spec/standard for FROST yet
complicated alternative scripts (hash-path or timelock path for HTLCs, eg): afaik in practice we don’t have any complicated enough scripts in common use (ie, not “new features/tech stacks/stupid hype stuff”) that they would be significantly cheaper with taproot
So I’d say the timeframe for fee-driven adoption of taproot has only been at most 6 months (for n-of-n; still waiting for k-of-n), and that’s been in a time of record low fee levels. So I don’t think you can draw any meaningful conclusions: prior to this year, getting cheaper fees was an open research problem; during this year, getting discounted fees probably doesn’t justify the engineering time.
I think for exchanges it could be significant – maybe reducing tx fees by 30% for larger consolidation txs; perhaps 60% if you got to switch from CHECKMULTISIG to FROST key path sigs at the same time. Still only meaningful if fee rates rise, though.
I think you want a relatively high chance of collisions because the set of nodes you collide with is also your anonymity set as a node (because changing your number after you’ve picked it is only possible if you store 100% of the blockchain, which defeats the purposes).
8MB blocks with w=64 seems almost appealing (pq sigs ending up 2.77x as expensive as a schnorr sig, while being 5.5x the size of a schnorr sig, if I’m not totally off base with the maths); would probably require new p2p messages for chunking blocks or something though. Perhaps also a limit on an individual tx to not having more than… 100kB of pq sig data?
I was mostly talking about single-sig; the situation is indeed more complicated for (efficient) multisig.
I think it’s unlikely that the prisoner’s dilemma played much of a role here. Senders were/are (almost completely) willing to send to P2WSH already, with a similar per-output cost as P2TR. With that, the choice to give our a P2TR address just reduces spending costs. A more plausible explanation is that receivers didn’t want a different output type for change and for receiving, and that P2TR for both combined didn’t seem sufficiently beneficial (or just that the potential fee gains were not interesting enough to them in general).
Ah, fair point.
I’d argue for a general tx weight limit (which would implicitly limit serialized size up to style=1). Some limit is necessary for verifiable chunking of blocks (send some range of transactions within a block, plus Merkle path for the transaction before and Merkle path for the transaction after) to be guaranteed to be possible. But a tx weight limit might not be a bad thing in general (from a block template optimization perspective).
I tend to agree with Pieter that it’s somehow slightly ‘off’ to merge CISA into this. CISA, I agree, does not have nearly as big of a selling point in practice as some people want to believe.
It would be better to have it available as a “here’s an output type that will be cheaper for your ordinary wallet when it matters, which is to say, when you have to consolidate a bunch of utxos” and, without overselling it, talk about 25% cheaper as a typical figure.
When taproot was about to release I was telling people “it’ll take years for this to get adoption and it’ll only really get any adoption when we get MuSig/PTLC in Lightning”. My reasoning was: people are slow to switch and reluctant to switch unless they see a reason, which is either, cheaper fees or “there’s a big chunk of the ecosystem using it”. That was the case with segwit - it was very non-trivially cheaper so the ecosystem moved and then you got a snowball effect. If we’d actually got PTLC and so on in LN in a reasonable timeframe, it could have pulled a lot of the ecosystem with it. But as of now, it’s only the tinkerer or functionally heavier wallets like Sparrow or the heavier ones like Liana that have it. The LN/PTLC angle didn’t turn out to be straightforward.
The best CISA can hope for is that a 20-25% discount for consolidation matters, I think. The whole coinjoin/batching etc. etc. angle is going to remain niche unless something big changes. Big operators with a lot of backend stuff going on will perhaps care, though. And it would be nice if they didn’t have to overlay another technical decision on top of it (quantum stuff).
One reason to be much more optimistic this time around is that in the end these are simply software changes and I think one major reason for slow adoption of Taproot in provider support is that there are many understaffed projects that had the will but not the manpower to make these changes safely. AI has made making such changes a lot faster, cheaper and (arguably) safer, especially when there is a spec that you can point the bots to. Generally I am not that concerned with the technical hurdles hindering adoption of wallets etc. because of this. Apathy of users to move coins and general disbelief in CRCQs happening are where I see the bigger issues.
We currently don’t think that implementing fullagg in Payjoin requires additional communication rounds but we will confirm it with a PoC soon (work/research in progress between me, Payjoin Foundation, and others).
As the concepts stand today (if I understand the PQC side correctly), P2TRv2 + PQC + CISA could be implemented and used without CISA (only use plain BIP341 opted-out) or without PQC (not implementing the required paths). So if there are just multiple options, I don’t see how the decision would block anyone. If this was a concern to do everything at once I would expect that they first add it without CISA and then add CISA when they have additional resources for it.
I think that’s mostly fair, though some have not adopted P2TR yet and many only did so recently so not all are on the bleeding edge. My AI comment above also means that I am not that concerned about custodial solutions. They can just move the funds for the users and they are a single point of contact that should be relatively easy to reach. I think reaching all self-custodial users and motivating them to move their funds is the harder part, even when their favorite wallet already has released an upgrade that supports the new output type.
Generally I would never advocate for bundling unrelated, even contradicting changes that could never even be used on-chain at the same time. But in this unprecedented situation that the potential danger from CRQCs put us in, it is the only situation I can imagine where it makes sense IMO. Based on the conversations I have had so far I think only few people believe that CRQCs in the short/mid term are a 100% certainty and that basically everyone wishes (for Bitcoin’s sake at least) that they never materialize because no matter what happens the transition will be extremely painful and we will lose many nice properties in the process. It is a pill we have to swallow, a preventative medication. I also think that there will be doubters of the existence of CRQCs until the last minute and, as written before, I see a high chance that we will see some leveling off of the Quantum progress before it happens. This is why I think bundling would help PQC adoption in many possible scenarios. It makes the pill not as bitter and gives the doubters a reason to still be interested in the change.
The messaging for the people that believe that CRQCs are a serious threat IMO doesn’t matter that much because they will take what they need to be secure. They don’t need to be convinced. But for those that don’t see it as a danger (yet) the messaging matters much more and it may be better for them to hear “efficiency upgrade with PQC included just in case CRQCs do happen”.
Another, weaker, angle how this is a natural match: As CRQCs appear to get closer and migration takes action demand for block space will rise necessarily. People will be interested in consolidating coins and going through coinjoins with coins they may be forced to move before transactions generally become a lot more expensive on-chain when PQC is the only option.
Having a P2TRv2 with PQC and another P2TRv3 with CISA seems to be worse for adoption in my mind. Wallet implementers, custodial operators and non-custodial users would constantly need to make a decision between having quantum safety and cheaper fees/higher privacy (assuming payjoin/coinjoin has adopted CISA at this point). I think it would likely hurt adoption of both concepts more than a combined output type would. UI challenges and marketing/messaging still remain tough even with AI.
I hope I am not overselling it? I am always trying to be careful to give correct numbers while simply being optimistic about the outlook of CISA adoption if it were to be deployed. Without being optimistic on that front it wouldn’t really make sense for me to argue for it and work on it.
I don’t think that this situation is still comparable because those are mostly off-chain concepts and network-effects are at play whereas CISA is validated on-chain (we can’t do a CISA softfork without the finalized and implemented DahLIAS spec) and current Payjoin/Coinjoin implementations only need to implement it for themselves and don’t need to coordinate on it (only some more advanced concepts will do that). We will have demo implementations soon, for Payjoin certainly this year. In the case of MuSig in particular there was the indirection of the switch to MuSig2 which caused things to be delayed even further so BIP327 was merged into the BIPs repo ~1.5 years after Taproot activated and the MuSig2 module was merged into libsecp256k1 almost 3 years after Taproot activated. So it seems to me we are currently years ahead of that schedule for CISA in a hypothetical P2TRv2.
Some people, myself included, do believe that CISA can help move Coinjoin/Payjoin out of the niche but I don’t think this is the right place for this discussion. CISA inclusion would need to achieve community consensus and I think as long as the underlying information is correct (like savings numbers) it’s fine that people have hope for the changes to have as big of an impact as possible. Without optimism I don’t think we can get any softfork done.
But I don’t understand what you mean by “overlay another technical decision”, (taken mostly from my response to one of sipa’s points above) as the concepts stand today (if I understand the PQC side correctly), P2TRv2 + PQC + CISA could be implemented and used without CISA (only use plain BIP341 opted-out) or without PQC (not implementing the required paths). If this was a concern I would expect that they first add it without CISA and then add CISA when they have additional resources for it. The other way around would also be possible, just adding CISA and ignoring PQC, with the separate output types for each concept you are actually forcing them to make a decision for either one, the change becomes more complicated and stretches into UI/UX, marketing etc. where decisions are less straight forward than simply making the code work.
Sorry by the way, I didn’t want to hijack this thread on PQC output types (the overview is very helpful btw, thank you @sipa ) and turn it into a CISA discussion. I should have probably put my last responses in a new topic already. Happy to fork off into a new topic if the CISA thread continues.
In my view, the high-level problem underscored by Pieter is on the pains minimization path forward for the Bitcoin ecosystem in the ocurrence of a CRQC happening in the wild.
The occurrence of a CRQC is a probability that each one in the community might evaluate differently in function of one’s her or his level of scientifically knowledge and level of information about the advances in the field of quantum computer, though if you have sufficient knowledge and information, and you understand there is no null chance practical quantum computer might happen over the next decades and the severity impact might be disastrous, one might believe, at least speaking for myself, that is worthy to take preemptive defensive actions, while conserving bitcoin properties.
This disclaimer said first, I do see the P2TRv2 with an ulterior disablement of ECC spends within the output type itself as a reasonable path forward. The fact it’s happening with the clear design goal of a potential future disablement means that users have voluntary opted-in by sending their funds to the new P2TRv2 (or delegated in a *knowledgeable fashion* to a centralized custodian to do this choice, if they use one it’s a matter between their custodians and themselves).
This avoids any kind of generic freezing debate. Whatever the view one can have on the more political aspect of damaging the censorship resistance property of bitcoin, by some kind of large freezing, designing a new dedicated output type with self-containing freezing effect avoid any uncertain future liability due to the retroactive effect the technical change would have for users that would never had consent to this change, CQRC or not.
That an adversarial CQRC user goes to steal users funds by leveraging its capabilities, it’s might be very adversarial for the chain finality, as it has been observed on the mailing list. However, from the viewpoint of a protocol designer or bitcoin full node maintainer, it’s more a “force majeure” event, with all its exoneration of legal responsibility.
Apart of those social considerations, I think we can make a P2TRv2 proposal far better on few many technical dimensions:
(A) We can introduce many leaves types where for the first one the ECC spend path would be disable when the disable flag event is reached and for the second one the ECC spend path is not disabled by the the flag event. Indeed, we might have some “activation residual malleability” for the inclusion of the flag event, especially if we go for a miner lockdown.
Some advanced users, that are concerned about classical break of any PQ scheme, as noted by Pieter, might wish to hybrid secure their coins under classical and post-quantum assumptions, and decide when they wish to move their coins to PQ safe only.
(B) We can introduce different class of flag events for the spend by using some space bit flags in the leaves versioning itself to say if the user commits to the effect of Tripwire or the effect of Miner lockdown or whatever another “flag event”. This adds more spending flexibility policy for the users who do not wish to rely on a Miner Lockdown a locking effect.
About the idea bundling P2TRv2 with CISA, I would rather suggest a no. In my view, with P2TRv2, we are aiming to address a critical security risk to bitcoin, in the occurence of a CRQC happening in the wild. Nothing of the same significance with CISA, which is a performance and privacy improvement, as far as I’m aware off.
From a cold viewpoint, we should all keep in mind that some top industry hardware wallets are not able to generate correctly entropy, and all the post-quantum changes for an eventual P2TRv2 are going to be a novel stack of complexity for them already…
tl;dr: i’m +1 with a flexible no-special witness no CISA version of P2TR2 and a latter P2MR based output with a new witness structure and consensus accounting optimization of the whole. let’s try to avoid to rock the consensus boat the less we can.
I’m not saying it will. Quantum-resistance is the greater selling point, which is why i think P2MR is still the best option on the table.
Rather, I’m pointing out that if your goal is to maximize migration for the “long-tail” of retail wallets who don’t care about PQ, then it seems like P2TRv2+CISA is the best choice for you: it gives devs a reason to migrate without committing them to any up-front work supporting CISA. Supporting PQC will be far more challenging by comparison.
Without CISA, we might as well do P2MR. Then at least we can correctly claim we have deployed a quantum secure output type, and shame wallets who don’t migrate.
With P2TRv2 (minus CISA), we kinda have to forgive wallets that don’t migrate, because they may have a legitimate concern that users’ funds could be stolen if the EC path isn’t disabled in time. With CISA, users can at least plead “this new address format is cheaper AND has a quantum migration path, you should support it or i’m going elsewhere.”
Ah sorry, I think we were talking about the same thing, but I was using the wrong lingo.
I see it exactly the other way around: this is the biggest advantage of bundling CISA.
By bundling PQC with an ECC optimization, we can simultaneously please the quantum bears and the quantum bulls in one self-consistent package.
Here’s how I’d frame it: “We present a new output type that’s even more efficient than before. Also if CRQCs appear, we have PQC now, but if QC turns out to be a larp, then we can keep using this very efficient address format and nothing much will change.”
FWIW this would implicitly cap the number of inputs in a transaction, depending on signature size, and would mean some large multisignature scripts would be completely unspendable.
E.g. with 5kb signatures (as proposed in SHRINCS’ current stateless parameter set), a 100kb TX size cap would mean less than 20 inputs per transaction.
Measuring in weight units seems more reasonable if you assume the PQ signatures have a discount. But still something to watch out for.
Can you elaborate? Why is it “off”?
Are you saying that improving security and privacy and performance simultaneously isn’t a worthy goal? Killing three birds with one stone seems like a win to me. P2TR did exactly the same thing back in the day: it improved efficiency, privacy, and performance, all in one elegant upgrade package. Should we note strive for the same here?
Also note that P2TRv2 by itself does not address the critical security risk (ECDLP being broken). The critical security risks are only addressed after EC is disabled. Until then, everyone is still vulnerable. At best P2TRv2 (with or without CISA) gives users an option to migrate to a wallet that might someday be quantum-secure, without any hard guarantees.
As mentioned earlier, @fjahr has updated CISA to be drop-in compatible with legacy wallets. All a wallet has to do to support CISA key-spending (opt-out path) now is to bump their witness version. This is exactly the same level of integration difficulty as stock P2TRv2 (without CISA), so i don’t think wallet-side complexity is a valid argument anymore.
The complexity added by CISA is then mainly on the consensus validation side, which compared to PQ signature validation is minor IMO. @fjahr can correct me here, but the implementation work seems on par with batch verification.
If you’ll indulge me in a moment of historical reflection…
In the taproot upgrade, a significant amount of additional cryptographic design and implementation complexity was devoted to removing just a single byte from every key and signature (x-only arithmetic), so i am rather confused that a vastly more significant space saving opportunity is now somehow seen as too complicated to be worth it, especially when it helps incentivize migration that - according to @sipa - needs to happen for Bitcoin’s future to remain interesting (i disagree but i just want to point out the contradiction here).
Realized something else today. We’ve been talking about P2TRv2 as if it will be an easy upgrade that even lazy wallet devs can manage, or at least that it’s easier than supporting P2MR. I’m not so sure that’s the case.
Whatever output type we deploy will need to come with new wallet standards for how to derive PQ keys securely - relevant discussion here. Even if the wallet developer can handle the tiny amount of work to support P2TRv2, they’d also need to completely change how key derivation for P2TRv2 works for Bitcoin, shifting away from BIP32 and towards some entirely new multi-algorithm HD wallet standard that nobody has even defined yet. Wallets will also need to implement the PQ key generation algorithms, and probably test that against static test vectors.
So I should correct what I said earlier: Simply “bumping the witness version” is insufficient even for P2TRv2, with or without CISA. A lot more work is needed for any wallet that actually cares about PQ security.
I fully agree with you that improving security and privacy and performance are worthy goals, though we’re living in the mere world of engineering where there is never a free lunch. Where I can be skeptical, it’s on the wallet and node complexity changes required to support CISA in itself.
More after that, there is a confusion to clarify first. Thanks to point that P2TRv2 does not address the critical security risk. A cursory read of the conversation made me first thinking that P2TRv2 *would* include support for a post-quantum scheme, be it sphincs, falcon or whatever, and that we we mere discussing the overall approach. So yes with this information in mind, a *naked* P2TRv2 sounds less interesting.
Now, even if we go to assume a *naked* P2TRv2, it does sounds to me technically possible to introduce discount for a future post-quantum scheme by introducing a novel witness scheme at the same time. E.g a BIP141 extension structure where the novel witness weight unit would be discounted from the 4 MB limit (I would have to verify the code paths in `CheckBlock()` thought at first we might be able to do so).
That’s a concurrent approach of CISA if the end goal is to incentive migration as much as we can, as in my view you’re making the point to justify that we bundle P2TRv2 + CISA. Now, about CISA while I’m supportive of the idea, the part where it’s unclear and where I’m a bit skeptical is on the half-aggregastion and full aggregation flow.
The BIPs say nothing about how it would be done in practice, if it would be done by the wallets only, with not special support from network full-node, or that for half-aggregation we would have magic mempool logic to enable this. This approach has been done naively in the past on some cryptocurrencies e.g Mimblewimble and it was the source of subtle privacy deanonymization attacks (remember discussing this one with Gleb Naumenko, and if we could have the same risk for bitcoin tx-relay network). If it’s wallet only for how the concrete aggregation protocol would play off, yes that’s another conversation.
More generally, in my position there is a bit off of soft-fork pessismism. If we go to take changes that are argued for fixing security issues, post quantum ones are far to be the only ones (e.g BIP 54) and realistically for post quantum changes we might need multiple soft fork changes spread on multiple years, to make the Bitcoin network as robust as we can.
Even if I see your point in the fact that CISA might incentivize the migration, the change in itself is for pure privacy and performance reason, and in my subjective scale of value, I’m not ranking it as importantly than soft-fork changes justified for network security. Beyond, we should still strive for a high review standard for any consensus change and have a lot of people partaking to the design and review / testing process of any change. Can we say we have more skilled eyes that have partaked in BIP 54 design and implementation process than we had for Taproot / Schnorr.
In my impression of someone who have seen the two I’m not sure, and in pure terms of social dynamics one we should keep the technical surface as much reduced as we can for post-quantum change. Somehow, it’s one the first consensus change in modern Bitcoin history, where the constraints are coming from a timeline which is “exogeneous” to us, than purely “endogenous” to the Bitcoin community.
I don’t believe there is a significant synergy here. I think wallet providers/services who are keeping up with technological advances will adopt PQC output types without or without CISA. Those who don’t, which will tend to be those with users who don’t care either, are the ones we have to convince. Unless we see very significant fee rate increases, I think they’re mostly immune to fee arguments, and won’t be swayed by CISA. (Perceived) complexity of adoption may hurt, however, though that is admittedly a weak point.
My main view is simply that CISA won’t help adoption, and is thus not worth the additional complexity of consensus changes. I don’t think it significantly worsens things, and I’m not against it, but I think it’s unnecessary and a distraction.
Neither P2TRv2 nor P2MR are a “quantum secure output type” in an absolute sense. As I pointed out before, all continued use of ECC has risks, and relies on an assumption that some entity will make a correct call about when to disable it. The only distinction between the two is that with P2TRv2, that does not include the owner(s) themselves. Given the arduous restrictions (no hardware wallets as we know them, no xpub/description sharing, …), I believe this isn’t a practical possibility for many if not most users to exercise that ability even with P2MR. Furthermore, I believe that the more interesting CRQC survival scenarios inevitably rely on large-scale migration and coordinated disabling in time anyway.
I understand the psychological appeal of wanting an output type that’s categorically not subject to ECC, or at least gives users that option, and lack thereof may cause some to panic. Having a separate, and possibly later-dated, separate P2QR or P2MR output type (with new witness styles etc) can fill that need. But for the long tail, my belief is that we ought to make something that is as smooth as possible to adopt, both in terms of technology (for developers/companies to provide) and not costing more (so users don’t refuse).
I really very strongly disagree with this line of thinking. Our goal as protocol designers is not to be able to claim we did enough by providing people a good option. Our goal is trying to design something people will actually use correctly.
I believe that it is a practical impossibility for many software and users to adopt workflows in which P2MR provides quantum-resistance, due to ingrained use of public key sharing. Claiming that it does provide that is at best ignoring reality to make your job easier, and at worst actively misleading people by providing a false sense of security. Shaming them won’t change that reality.
If they have that concern (whether justified or not), they shouldn’t use P2TRv2 at all, with or without CISA. In fact, if one has that concern they could be even more strongly against combining with CISA, as they shouldn’t want the extra incentive it may provide to others to adopt an output type that they perceive as risky.
I won’t deny that such users/developers likely exist, but I think for that the better option is providing a separate P2MR or P2QR type at a later stage. Not giving up on the P2TRv2 advantages that may sway much less sophisticated wallets/users to adopt.
Yeah, that’s fair. Though it has a disadvantage too: people may choose to adopt it in an “unprepared” way (without PQC path) because the output type has advantages beyond quantum protection. I don’t think that’s very likely unless we see a significant and persistent feerate spike, but it would be a pretty bad outcome, as it could lead to arguing against an ECC-disabling softfork, against deploying Miner Lockdown, or for disabling Tripwire.
The discussion you’re responding to here was in context of a new witness type which introduces a new discount. So the weight limit would be on the newly discounted cost.
The implementation is probably the easiest aspect of a consensus change. It is an aspect though, and I agree that CISA probably compares relatively favorably to any PQC addition.
I understand the apparent contradiction, but I don’t think the situation is comparable. That byte was in the transaction output, paid by the sender, not by the wallet adopting the change. We needed to avoid a situation where non-Taproot wallets would refuse to send to P2TR because it’s more expensive than all other existing address-enabled output types at the time. P2TR needed a new address type (BIP350) to be accepted by senders before real P2TR adoption could even begin. Getting rid of the extra byte made it as expensive to send to as P2WSH, which was already widely supported.
This is also in line with my argument against (just) P2MR: we shouldn’t give a reason for people to refuse upgrading because it makes things more expensive than they already are. I truly believe there is an asymmetry here: making things more expensive can have a stronger discouraging effect than making things cheaper has an encouraging effect. This is because there are multiple ecosystem entities involved in upgrades that all need to be convinced. It suffices for one to care about fees to refuse, while adoption requires convincing all of them.
Taproot was also not time sensitive in its adoption. I won’t deny that I would certainly have wished for faster adoption than we see today, but for getting Bitcoin quantum-ready I think we hope for a faster rollout.
That said, in retrospect I agree the complexity of saving that one byte was probably not worth it.
I imagine completely static per-wallet PQC keys, with no key derivation. Wallet descriptors move to store xpubs + static stateless PQC pubkeys or pubkey hashes (one per wallet/user/device), which is compatible with all of today’s use cases I can imagine. For very simple non-sharing non-HWW single-party wallets, an equivalent for hardened derivation is possible, which would be compatible (but still icky) with stateful signing. Longer term it may be possible to move to sharing complete sets of future PQC pubkeys, but I don’t think that’s for everything, and probably not realistic in the short term.
The privacy implications here are pretty bad after ECC disabling, but I think it’s the best we can reasonably see adopted at scale. And the goal is just avoiding disaster. Long-term, we’ll need PQC that’s compatible with homomorphic derivation, or so much time that the ecosystem moves on to entirely different approaches.
Absolutely. Any change requires extensive design and testing, even if it’s minor. But CISA does add more to it, a little bit without actual aggregation, and possibly quite a lot with aggregation (because signing is no longer per-txin thing, which may need significant redesigns).
Finally I’d like to suggest we consider replay protection, from the start.
Any activation earlier than the tripwire, or some other deterministic mechanism, is going to be controversial. And it seems inevitable that some group people will emphatically want to freeze existing coins (<v2), while another group emphatically not, and others ambivalent. If such a fork is unavoidable, adding a (simple) replay-protection mechanism seems reasonable.
The reason to do it from the start, is because hitch-hiking with a new SegWit version offers the largest possible design space. Second shameless plug, see e.g. Universal opt-in replay protection? - #11 by sjors .
Is it possible to design a v2 SegWit such that CISA can soft-forked into it later, rather than needing yet another version bump? From a user-experience point of view, once their wallet adopts CISA, it can gradually migrate coins over to it, in a way that’s not noticeable / distracting. And of course the anonymity set doesn’t need to splinter again.
Update: we could allocate 1 bit of the public key to mark it anyone-can-spend, with the later CISA fork using that as the opt-in all wallets set it by default (regardless of support). This “just” means extending the existing x-only grinding mess by one more bit. Or, we could add a byte, get rid of x-only keys, and use the remaining 7 bits as flags. Neither helps with the anonymity set , and moving forward such a flag would likely reveal wallet capability.
Indeed. It boils down to a way to add segwit subversions. Either at the expense of making every output 1 byte larger, or extra complexity due to having to grind an extra bit. Neither is hugely appealing.
Sorry for the confusion there. i wasn’t suggesting naked P2TRv2 - I think that’s a bad idea, because it’d be unsafe to use due to the risk of later confiscation via tripwire. I was pointing out that P2TRv2 is not actually quantum-secure unless key-spending is disabled punctually later.
@fjahr can correct me here, but I believe half and full agg should be done by signers, either interactively (full agg) or non-interactively (half agg). I don’t believe relay nodes are expected to do any half-aggregation themselves. They would see unaggregated half-agg signatures as invalid when checking a transaction. Though it’d be very easy to write TX broadcast middleware that aggregates half-agg signatures, if they can be identified.
Agreed, but let me add: Our goal is to design something people will use correctly AND which effectively secures their coins. P2TRv2 is easy to use “correctly” but even with correct usage your coins are not necessarily safe. With P2MR, perfectly “correct” usage is harder, but has meaningful impact on security.
I think you’re overselling how hard this is?
if i just use a regular single-signer phone or desktop wallet, all my wallet has to do is (1) not reuse addresses and (2) not transmit my xpubs off-site. With all the light node tech out there now, and AI to speed up implementation, it’s never been easier to manage, and it’ll keep getting easier.
But OK, maybe for some low-effort wallets, or complex use-cases like hardware wallets and multisig, that stuff will be more in difficult. In truth, we have no evidence one way or the other to predict what wallets will or won’t do with their EC pubkeys in P2MR (unless you have a crystal ball?). A lot depends on the new HD wallet standards that nobody has fully spec’d out yet. It’s unknowable.
What we can say for sure is that however “leaky” P2MR is or isn’t when put into practice, P2TRv2 will be at least as leaky and almost certainly worse, because 100% of P2TRv2 EC keys are exposed from the get-go.
With CISA in play, i feel like we can accept that insecurity as a trade-off in exchange for the better classical performance, and as a hedge against CRQCs maybe never appearing.
Without CISA though, the efficiency gap between P2MR and P2TR is tiny: smaller than the gap between P2WPKH and P2TR (see next paragraph). This is why I don’t buy your argument that P2MR’s inefficiency compared to P2TRv2 (without CISA) would be a dissuading factor for any meaningful number of users, and it’s why my preference shifts firmly back to P2MR in this case.
P2MR is more expensive than P2TR yes, but most people don’t use P2TR, and those who do are typically early adopters who will more readily adopt a PQ output type (and/or CISA) if it were deployed anyway. Most users in the “long tail” that you’re concerned about, and PQ-cautious users like myself, use P2WPKH.
P2MR can be cheaper than P2WPKH. With @fjahr’s CISA or @starius’ EC recovery implemented on top of P2MR, then P2MR is actually more efficient than P2WPKH which is what most retail wallets are using today. The double-whammy of P2MR+CISA specifically is almost as efficient as P2TR for many-input transactions. P2WPKH users actually stand to reduce fees by adopting P2MR with classical optimizations, and they get plausible quantum security to boot.
So the class of users you’re concerned about in this argument seems tiny. You’re talking about users who (1) hold funds on P2TR, and (2) run wallets that aren’t well maintained, and (3) are steadfast opposed to paying a few percent more per TX even in exchange for quantum security. I would guess the pie slice that your argument optimizes for is smaller than a rounding error, and motivating that tiny minority of users doesn’t meaningfully move the dial on maximizing migration for the whole network.
“No key derivation”? You mean ephemeral, randomly generated PQ keys? That would make wallets unrecoverable from seed phrases. No, we’d need to derive the PQ key from something deterministically linked to the user’s seed phrase.
Most obvious would be to derive the static key from the seed phrase directly (no intermediate BIP32 step) using something like HKDF or HMAC.
But then, if you can derive one key that way, why not derive many? It’s not hard to do. Boom, we’re already defining a new multi-algo multi-key wallet standard.
There’s no way to save effort here that doesn’t compromise security. So we might as well do the work once, correctly, so we don’t have to do it again later. It doesn’t have to be complicated.
Actually it is possible to deploy P2TRv2 with a time-based upgrade hook that transmutes P2TRv2 outputs into anyone-can-spend after a specific deadline block height T (e.g. 10 years after initial flag day). We then have to commit to deploying a 2nd soft fork that enforces new rules for P2TRv2 at block height T to avert the mass chaos.
If CISA is ready by height T, we could deploy CISA as a soft fork. If CISA isn’t ready in time, we can kick the can down the road by extending the existing rules for another X years.
Same idea can also be applied to enable patchable SNARK systems, patchable signature schemes, or a number of other forwards-compatibility and engineering agility tricks.
To those against CISA today: would you at least consider putting in an upgrade hook like this so we can activate it on P2TRv2 in a few years if QCs don’t work out?
Because they’re two radically different proposals with radically different motivations, that’s all I meant.
I guess (but am not sure) that this relates to @fjahr 's :
I see this as (very vaguely) analogous to old discussions about cryptographic blinding on blockchains: as written down in a theoretical paper, combining X and Y together may not affect security property Z, and you can even prove it. But the real world is not like that sometimes : sometimes the way you put the pieces together has unexpected side effects. Homomorphic commitments to amounts is balance preserving, mathematically, but that doesn’t mean you don’t introduce risk factors.
Some people would want a CISA soft fork, but not the PQC one (or want a different PQC one). They might be orthogonal elements of a proposal on paper, but might not be in practice. This line of thinking is not exclusive to CISA of course.
Indeed, it would/will be more complicated to do separate changes instead of combined ones. I don’t think that should affect choices about proposals though.
…
Sorry for answering late, I thought we’d stopped talking about CISA, and anyway the conversation has moved on … quite a lot
It is correct that the BIP specifies how signers produce their signatures and how those get combined, but it does not make rules about who runs the combining step. I don’t think it could even do that if we tried, it is outside of consensus and a P2P protocol/application that does this could not be prevented by the BIP. But I don’t see why anyone would build it, because there is basically nothing to gain. Half-agg is explicitly opt-in, each signer commits to the aggregation mode already in its signature message, so a node could only ever aggregate signatures whose creators already chose to aggregate. Those signers can combine their signatures themselves, it is a cheap operation that any of them should be able to run before broadcasting and they already have done some integration work for making the signatures anyway. A node would just be doing the same work a little later but it also wouldn’t have the data to do it without a P2P extension or something similar: the s-values of the individual signatures never appear in the actual transaction, a member witness only carries the nonce share. To do anything, nodes would have to receive the full signatures through this new P2P protocol and the mempool would need to accept and hold transactions that are not valid yet. That is a significant change for no conceivable benefit. The situation in Mimblewimble was different, there aggregation across transactions (“cut-through” if I remember correctly) during relay was part of the protocol explicitly. Here aggregation is within one transaction and happens before broadcast.
That’s correct. Broadcast middleware that aggregates would need the full signatures handed to it out of band, e.g. in PSBT fields, since they are not in the transaction as explained above. At that point it is simply the aggregating party as described in the BIP, not really something that makes sense as a network service.
I did spend some time initially thinking about if allowing for any kind of aggregation by third parties but I couldn’t find any significant upsides that would result from this and could justify the additional complexity. And I think this decision works well with what is being discussed here: The best case for a third-party aggregation would be if the BIP341 signatures were not actually protected as an opt-out but could be aggregated despite the signer/wallet not even being aware of CISA. This is prevented with the explicit opt-out rules for these signatures which works well with a potential second reason that motivated adoption of the output type, like the PQC stuff discussed here.
Yes, in a vacuous sense, because it is so hard that it’ll be impossible to get most users to do it. You cannot expect people to stop reusing addresses, because it doesn’t fall within the purview of software that protocol designers and developers control. Address reuse is something humans do, and remains possible as long as addresses exist as shareable strings. Getting rid of that requires migrating to different approaches, like payment protocols. I tried 15 years ago, in what motivated the BIP70 payment protocol to be developed. It never took off, and was abandoned. Addresses, and their ability to be reused, is so ingrained in how Bitcoin (on-chain) payments work that in my opinion the only realistic way to avoid it is having everything and everyone move to a different layer (like Lightning’s BOLT11 invoices / BOLT12 payment codes) where the need for compatibility does not exist. I don’t think this is feasible in the timelines people are thinking of for CRQC, and probably needs decades.
Yes, it’s possible. But most users won’t, and not recognizing that is not responsible design.
(This ignores that just using “correctly” is not enough; the user also has to actually still switch to the PQC path in time, which most users are not particularly well placed for either)
This isn’t a software problem; it requires workflow/social changes and reimagining how people use Bitcoin.
They’re certainly more complex, but they are very important use cases, used by large amounts of users. And in particular for hardware wallets, by users who are likely not keen to touch their coins.
I really don’t understand this. What is your goal? If you view P2TRv2 as insufficiently secure, why would you want anyone to use it, and worse, incentivize it with CISA? If you’re okay with the security of P2TRv2+CISA, then none of the worsened security arguments ought to apply, with or without CISA.
(1) would be users who use P2TR or would be migrating there anyway the next few years, which I expect to be a substantial portion. In terms of users (but maybe not in terms of BTC), I think most are on software/providers (2) that aren’t particularly up to date (think exchanges, multi-coin wallets, …). And (3), don’t you think that many users would hesitate if they see a “migrate to PQC wallet? everything will become a bit more expensive once you do”?
My goal isn’t motivating, I wish we could but I don’t think we can. I want to remove friction that may stand in the way of adoption. Fee increases may be one of them. Another big push, post P2TR, to yet something else, may also be one of them.
Sorry, I meant no per-address derivation. The actual PQC key would obviously be derived from a hardware-generated or provided seed still.
Because it requires workflow changes, not just software changes. Large amounts of keys cannot be reliably written on a piece of paper or a metal backup. They may not fit in a QR code. They may not fit on a tiny hardware screen for manual comparison. A push towards “bag of preshared keys” may work in some settings, but there will be many where it just won’t. You need to deal with those too.
Changing how humans do things is the hardest thing.
I don’t consider that acceptable. You’re proposing an output type that, barring a future consensus change, automatically becomes insecure.
I’m aware that is not practically different from the appearance of a malicious CRQC prior to a tripwire triggering, but there it is an inevitability we’re already facing. Adding a guaranteed time-based one just in order to be able to get a neat upgrade hook seems like entirely the wrong trade-off to me.
I understand the appeal of killing two birds with one stone if we are introducing a new output type, but i agree with Pieter that P2TRv2 and CISA pull in opposite directions. Not only in terms of features, but also in terms of expectations. I don’t think CRQC-skeptic CISA enthusiasts would accept an expectation that their EC spending path becomes unspendable before CRQCs materialize. If so, this would at best lead to them not adopting it, and at worst would undermine the expectation of an EC disabling.
On the other hand, it may be that the lack of CISA support hinders migration to P2TRv2. The alternative of the P2TRv2 and CISA soft forks advancing in parallel also presents the possibility that CISA becomes available or gains traction before P2TRv2. It is admittedly more of a stretch, but this scenario could result in misaligned incentives unless P2TRv2 also supports CISA.
However, i am skeptical this scenario would result in a systemic risk, because P2TRv2 targets wallets / service providers different from those likely to adopt CISA. And those wallets / users likely to first adopt latest technologies like CISA are not the primary targets of the P2TRv2 strategy: they are paying attention to developments and are able to move more swiftly if/when CRQC risk increases.
They would however keep using distinguishable output types until then, which may be forever. So an argument for bundling the two would be to avoid this footprint. If Bitcoin users desire CISA, and there is a push to get the vast majority of utxos to use P2TRv2 on the basis of CRQC risk mitigation, it’s would be quite the missed opportunity that they be separate output types. That’s a lot of if’s though.
Regarding the fee savings, i too don’t expect the ~5% off for the vast majority of users to have much of an impact on the wallet developers’ decision to migrate to a new output type. Of course i agree savings become non-trivial where interactivity is minimised and input count maximised, as in the example of an exchange. I don’t think this makes much of a difference for P2TRv2: exchanges would migrate to it with or without CISA, because it’s already no more expensive and because it would keep them safe if/when CRQC risks materialize.
Regarding the plan, i (unsurprisingly, we’ve discussed this at length) largely agree with Pieter’s.
I believe Tripwire without miner lockdown is a non-binding constraint and as such does not really provide “teeth” to EC disabling, outside of a psychological effect which may help bootstrap the collective reliance on EC eventually being disabled (which is, in my view, the real “teeth”).
I think the major challenge with EC disabling is to prevent it from happening too soon. A premature disabling would undermine the individual (lack of dis)incentives to migrate, and thereby the PQ migration. Miner Lockdown, while it gives the collective of miners the ability to (i believe irrationally) trigger it prematurely, may help in reassuring those stakeholders who might otherwise push for an early disabling out of fear of an unexpected CRQC breakthrough.
I think risk mitigation (P2TRv2 + Tripwire) and full migration (P2MR + eventual EC disabling + Witness style) should be provided in separate deployments. Most of the complexity is concentrated in the latter, which is also the least pressing. It can also be argued that the full migration path should only be made available once we have a higher degree of certainty that CRQCs will become a reality, while the risk mitigation should be provided regardless. We may also learn things from the deployment of P2TRv2, and a couple more years of development in PQ land, that could be applied to the later deployment of P2MR.
The values in the table look correct to me, but i don’t understand the inclusion of the orange threat model (). Under these assumptions, why would you ever use the PQ spending path? That would make even today’s P2WSH “secure”. I don’t think that makes sense.
While you obviously cannot strictly control address reuse in general, there are major use cases where address reuse is perfectly controllable and manageable. Crucially, address reuse is not a problem for properly managed long-term holding addresses, simply because address reuse per se does not cause funds to have an exposed public key, only address reuse of an address that has previously been spent from does.
I think the point here is that P2TR and P2TRv2 are both clearly a regression from a PQ perspective compared to P2WPKH and other address types with hashed keys, until/unless ECC spending is disabled. As such, moving such funds to P2MR rather than P2TRv2 would certainly feel less risky to someone who is informed about the potential threat of a CRQC. Whether it would matter in practice to keep those funds safe if significant parts of the coin supply end up getting stolen is a different discussion, of course.
As a bit of an aside, since it’s come up I can also briefly elaborate on why P2TR “failed” from my perspective:
For the “taking payments” use case, it largely comes down to wallets and (especially) exchanges being excruciatingly slow to add support for sending to new address types. While I would love the ~20% savings on consolidation transactions, I still see people needing to use legacy P2SH-segwit to make payments, even NINE YEARS after bech32 was introduced. Adding yet another address option to the mix would simply confuse end users who aren’t generally crypto-savvy.
For the “holding funds” use case, P2TR is more expensive for both one-input/two-output and two-input/two-output transactions, loses the inherent PQ resistance of P2WPKH, and has a much smaller anonymity set. It therefore seems like a strict downgrade unless you specifically need tapscript.
I don’t think this is specific to CISA users though. Adoption of P2TRv2 generally hinges on people trusting that the disabling triggers will work as intended, not too early and not too late, and that is the same for every user. If the disabling triggers worked perfectly (only happens magically in the exact moment the first CRQC comes into existence), adopting P2TRv2 should be an absolute no-brainer compared to the other output types discussed here. If people believe they are too risky, P2TRv2 likely won’t reach consensus in the first place, with or without CISA. You mention further down that getting the disabling timing/incentives right is the hard part of P2TRv2 as well.
I personally agree, and think we should treat and identical, because their difference only matters under a tenuous condition (no address reuse/pubkey sharing), and then depends on an unknowable hypothetical (CRQCs being slow). But since these conditions are both things have brought up regularly in discussions, I felt it appropriate for completeness to treat them as distinct security assumptions.
That’s fair. But I also don’t think these are the target audience for P2TRv2. If they’re properly managed they can migrate in time to a later P2MR output type too.
Yes, of course, and I recognize the psychological appeal of an output type that doesn’t have conditions attached (which is part of the reason for favoring also adding a later-stage P2MR output type in addition to the long-tail P2TRv2 one).
But my comment here was more meta. Namely, why is it that (to @conduition) whether or not P2TRv2 has acceptable security have anything to do with its price of usage? Why is CISA relevant in this context?
These things should be debated separately. Either the security of P2TRv2 is acceptable to the ecosystem, or not. And maybe adding CISA to it (or to P2MR) is a good idea, or not. But I do not see why they interact. If CISA truly does make P2TRv2 more appealing (which I’m skeptical of), that shouldn’t be a reason to let it compromise on your sense of security about it.
I don’t think it’s possible to accurately predict what portion of users will or won’t have exposed pubkeys on Q-day. You think “most users” will be exposed anyway; I think (with education and smart wallet design) the fraction exposed would be quite small. Neither of us can really prove our arguments on this axis of the debate. All we can say for sure is that P2MR would protect some unknown fraction of coins from long-exposure attacks.
The question is, is that juice worth the squeeze? You think no, because you estimate the protected fraction will be low. I think yes, because I think the protected fraction will be high. Without evidence I’m not sure how we can resolve this question.
First, workflow/social changes will be needed either way. If Q-day happens, it’d be a complete paradigm shift in the world of cryptography. Drop-in replacements for existing workflows do not yet exist, so we can’t afford to shy away from changing workflows.
Second, this is a software problem. There are ways to do almost everything we’d need to, they’d just require some (reasonable) compromises.
Examples:
Wallets don’t give out xpubs freely anymore, they only offer addresses.
Wallets warn users about coins sitting on addresses whose EC keys are exposed.
QR codes can be animated to store more data. Cashu uses this technique today to transfer many kilobytes of proof data across a visual channel. Or a static QR code can encode a URI to load E2EE data blobs from an untrusted server.
Short-term multisigs can use musig/FROST as they do today, as long as the keys are retired before Q-day.
Long-term multisigs between untrusted parties can use hashed keys in script. E.g. OP_DUP OP_SHA256 <H(pk_1)> OP_EQUALVERIFY OP_CHECKSIGVERIFY ... OP_DUP OP_SHA256 <H(pk_n)> OP_EQUALVERIFY OP_CHECKSIG
If one really needs full EC functionality and is OK with accepting some short-term risk, they can expose their EC pubkeys to do whatever it is they need to do, as long as they move the coins to a fresh secure address before Q-day. But honestly in some cases like silent payments, it may be better to just abandon the feature due to the unavoidable risks involved.
And if devs or users screw any of this up, it’s still not the end of the world, because the EC disabling fork may happen in time to save everyone.
i think PQ hardware wallet security under P2MR is completely doable. A bit harder than today yes, and with a slightly different thread model: If you are using a hardware wallet to spend via EC, you have to assume either (1) the host device is not controlled by a quantum adversary, or (2) the EC disable fork happens before the host device has a chance to collude with a quantum adversary. Still, completely surmountable, and better than P2TRv2.
My goal is for Bitcoin and its users to survive Q-day with as little technical and economic damage as possible.
I believe CISA’s efficiency would significantly help move the needle on migration to a PQC-enabled address type, while also making the address type easier to argue in consensus by pleasing PQ bulls & bears simultaneously. I figured you guys would actually be all over CISA as it effectively provides a pre-written vehicle for P2TRv2 - just add PQC and a tripwire. Clearly i was wrong
I don’t necessarily view P2TRv2 as “insufficiently secure” as an absolute. I believe that the benefits of P2TRv2 compared to P2MR (drop-in compat, 8vb efficiency gain) are negligible compared to the existential risk of all the P2TRv2 coins being exposed on Q-day. CISA changed that calculus for me, by offering way better classical efficiency, blowing P2MR out of the water, which gives a new political factor that neither P2TRv2 or P2MR has: it can please PQ-skeptics, which is the class of user i am most worried about, second only to offline users who will need rescue protocols to reclaim their coins.
I’m by no means happy with encouraging migration to a PQ-unsafe address format. My stance is still that P2MR is the only truly post-quantum address format. P2MR would be needed too, to cover users with higher risk profiles like big institutions or HNWIs. But life is full of little compromises, and I figured this would be the perfect compromise in the interim to please all parties, as a first step on a larger migration path. Perhaps I was wrong.
Based on P2TR usage rates over time (in terms of either UTXO count, or BTC volume), it doesn’t seem like (1) is very large. I don’t know of a way to accurately predict what fraction of users are “migrating there anyway” so i can’t speak to that.
Re (2): Yes I agree that most users are using outdated software, but my point is that the venn diagram overlap between “slow-moving outdated software” and “P2TR enabled software” is slim, and that slim minority is who P2TRv2 optimizes for. Even if the “P2TR” and “outdated walet” sets of UTXOs are independently large, their intersection isn’t.
I do believe that a fraction of users will refuse a migration, but not because of fees. Procrastinators are probably either (a) offline or don’t update their software, and so never see any pop-up at all, or (b) quantum-skeptics who would refuse to migrate to P2TRv2 just as well as to P2MR, or (c) lazy/indifferent: The efficiency gap between P2MR and P2TRv2 is tiny compared to the absolute cost (tens of thousands of sats in some cases), privacy impact, and most of all inconvenience of moving one’s entire UTXO stack to a new fresh wallet. Of all the factors weighing on a user’s mind, an 8vb/input fee to spend after migration seems small potatoes.
Sidenote: the same argument applies to CISA as well: The savings from CISA may not easily outpace the economic or practical cost of migration. But CISA’s savings compared to P2TRv2 or P2MR are are much larger even in absolute terms, and would recoup the up-front migration cost much quicker than plain P2TRv2 could.
I think we may be picturing the same thing here in slightly different ways.
An upgrade hook’s deadline is significantly different from the Q-day tripwire situation. Q-day is unpredictable and requires proactive migration before it. An upgrade hook’s deadline is fixed, certain, can be deferred at will, and requires no migration (provided the upgrade is completed or deferred in time).
@fjahr is on the money here. I can and have used this argument against P2TRv2. If a user is skeptical of QC, why would she use P2TRv2 at all? Or P2MR? Both are strictly worse than existing formats, in a purely classical context. With CISA, at least some of these users have reason to migrate, and maybe some will even be foresighted enough to actually use a PQC leaf script.
The only way to incentivize PQ skeptics to use PQC is to make PQC more scalable than ECC, which is why i opened this thread.
Are you picturing CISA being deployed without PQC support? If P2TRv2 has PQC support via a new opcode or tapleaf version, CISA would inherit the same.
Or are you imagining CISA without an EC-disable expectation/tripwire? i think that is unlikely. Why would it be acceptable to deploy P2TRv2 with a tripwire, but not CISA? It seems a bit odd to me, to assume that because output type X is more “fancy” than output type Y, its users should have better adaptive security or agility and therefore don’t require this critical safety belt that output type Y has, and then bake that perspective into consensus.
I think we all seem to agree on a rough shape for the migration plan (yay!): first step should be simple and designed for mitigating risk and not necessarily for long-term usability; Second step should be scalable and thorough and usable, possibly using more complex cryptography developed in the intervening period. We just disagree on the specifics of what should go into each stage of the migration.
I’m still partial to P2MR (and/or CISA) + tripwire with a rudimentary hash-based PQC spending path as the first stage. Second stage should be a new discount (aka “witness styles”) and/or SNARKs, or sufficiently advanced and efficient native PQC.
It’s a complicated argument to bring through education, and wallet design only has a small ability to influence behavior: never showing the same address twice (which has been a best practice since 2009…). Beyond that, it could prompt the user “only hand this address out to one party and tell them not to use it more than once!”. But most users don’t read, and even if they do it may backfire: people might refuse to upgrade “because those new addresses can’t be used more than once”, if the more nuanced point (that other/existing addresses are also subject to it) isn’t made across.
Address reuse is entrenched, you need people to change behavior, and to do so, you need to provide a better workflow than the existing one (or make the existing one hard/impossible). You won’t, and without it I think it is very naive to think that documentation and education will make a dent here. You can even barely affect design decisions wallet and infrastructure authors make.
As for the bigger point of exposed fraction, address reuse is just one aspect. Any design that relies on sharing public keys or xpubs (with unhardened derivation) will need to change too. For some of those (but possibly a minority), that will be harder than changing address reuse practices even.
And of course, this distinction between P2MR and P2TRv2 only matters in cases where users are actually capable of independently deciding when to stop using ECC spend paths at the right time. If they don’t, there is no difference. You may say that their wallets can make that decision for them, but that’s not particularly far from requiring ecosystem agreement (users might leave wallets that decide before “everyone else” does so), at which point ecosystem-scale disabling (lockdown, separate consensus change, or even tripwire if CRQC is cooperative) may also remove the distinction between them. And all of that is conditional on the whole system not imploding over CRQC FUD before then still.
I think the distinction between the two (ignoring the possibility of a combination) is largely psychological. Perhaps that is on itself a good reason if it would affect adoption, I don’t know.
I believe my experience can be helpful here. But yes, ultimately we may need to agree to disagree.
I disagree. It’s essential to minimize the need to change workflows, because that will hinder adoption even more than the technical changes themselves. That doesn’t mean we shouldn’t work on new more PQC-compatible ones, but you can’t rely on changes happening prior to Q-day.
There may be situations where significant changes are inevitable, but for almost all use cases I can think of, they’re pretty small, as I pointed out earlier:
Key reuse, sharing xpubs, compact descriptors, … all remain fine (descriptors would store xpubs for ECC + static PQC keys). Software changes are needed, but users don’t need to change anything about their ways of interacting with it and with each other. It relies on timely ECC disabling, but as you know, I believe in practice most things do anyway.
How will you register a hardware wallet? Coordinate a multisig wallet? Those are the reasons for exposing xpubs. You need alternatives for these, and those require workflow changes. The user needs to do things differently; it’s not simply a software change.
Users and devs will screw this up, for all the reasons above and more. I think we’re much better off not wasting time trying to get everyone to change their ways, only to end up still relying on ECC disabling anyway.
This is perhaps the biggest vision difference between P2MR and P2TRv2 proponents. To me, we cannot rely on the ecosystem making the workflow changes needed for a security difference between the two to appear. We’re better off designing things that are to the extent possible drop-in replacements instead, for everyone, including P2TR users and prospective ones, to avoid resistance in upgrading.
I’m not sure about how valuable that is as a security model. If an adversarial CRQC exists, and an attacker that breaks into your software wallet, why wouldn’t they conspire and split the gains? And if no adversarial CRQC exists, none of this matters, and if you don’t worry about an attacker breaking into your software wallet, why are you using a hardware wallet / signing device?
Of course, this may not be economical if the CRQC running costs are high per key. But this applies equally to setups without hardware wallet.
EDIT: scratch that. If you assume a lower bound on BTC amount exposed on a key exists below which CRQCs are not economical, and your hardware wallet controls less than that, it is not inconsistent to assume the software wallet attack won’t collude with the CRQC, as the HWW is still interesting to protect against classical attackers.
Yeah, I understand. My perspective is really that we need to minimize change, as we can’t rely on economic incentives to matter in the short-to-medium term. They might, if persistent and significant mempool congestion reappears, but I don’t think that’s likely enough to rely on in the timeframe we need it.
But is it negligible compared to the difference in existential risk from exposure between P2TRv2 and P2MR? To me these are nearly identical, so any reduction in friction in adoption is a gain.
I think the mixed messaging makes it worse in this respect. Is it an attempt at making PQC secure, then why is it adding an optimization that increases reliance on ECC? Is it an efficiency improvement that sneaks in a PQC upgrade, then aren’t you worried about people using it without PQC path, undermining the planned ECC disabling plan?
Also, and perhaps I haven’t highlighted this enough before: I consider the focus on reducing byte size an artifact of the weight formula established by SegWit. This made sense in the past (i.e., with Taproot) as introducing new witnesses with new discounts would be a difficult upgrade (far harder than an initial P2MR or P2TRv2, probably even with CISA included). But in the longer term, I think a post-CRQC world will demand it anyway, and if we embrace that, most of the advantages of CISA (at least halfagg) can be had with just a better formula that accounts for batch validation costs. This makes it also less appealing to me to stack it in with P2TRv2.
I really wish you would stop saying that. It’s unambiguously stronger in this regard, but it comes with so many conditions that’s very misleading to think of it as “truly quantum-resistant”: it needs users capable of deciding when CRQCs might exist, curated workflows that avoid exposing public keys, lack of address reuse, and even Bitcoin as a whole surviving for it all to make a difference.
You’re right, and it’s wrong for me to focus on the long tail of slow-moving software for this part of my argument. They matter of course, and I think the existing availability of tooling/libraries around P2TR probably makes P2TRv2 probably very slightly easier to adopt for them than P2MR. However, my “increasing fees may turn away users” argument does not apply to those who are are on pre-P2TR output types still.
That said, the new output type(s) we are designing here is/are for everyone. Having (just) P2MR as PQC upgrade path is asking the ecosystem that adopted P2TR as a softfork, its users and prospective users, to choose between P2TR’s advantages and PQC. I think that’s a controversial choice.
I hadn’t, but it looks similar in broad lines. I’m imagining having the PQC pubkey be added at the output descriptor level rather than the xpub, as it’s composable (e.g. MuSig in the internal key across xpubs, and a recovery path with multisig over the PQC pubkeys), but for single-party cases it looks equivalent. So you’d have trv2(XPUB/.../*,[shrincs(PQCKEY)]) instead of tr(XPUB/.../*) now.
Pieter Wuille · 
JP · 
Adam Gibson · 
conduition · 
Anthony Towns · 
Fabian · 
Antoine Riard · 
Sjors Provoost · 
Antoine Poinsot · 
ArmchairCryptologist · 