This is a shower thought I had after seeing the idea of a post-quantum witness:
Adding another witness area is certainly technically doable, and might be inevitable if/when large-scale usage of PQC schemes is needed, depending on how large the scheme’s signature/keys are. However, if done in a similar way to the segwit witness area, it adds some complications that may pose a burder to adoption, which may be more time-sensitive now:
New pqwtxid for transactions that includes also the pqdata in addition to the segwit data.
New block commitment in coinbase to the pqwtxids, requiring mining infrastructure changes.
Possibly a pqwtxidrelay relay feature, matching the BIP339 wtxid relay (something whose need was only discovered after segwit was deployed).
Several places inside P2P logic that now need to track transactions by 3 identifiers instead of 2, for compatibility with older nodes/protocols that use wtxids.
I think it may be possible to avoid some of that headache for a future post-quantum witness area: by placing a commitment to the pqdata of an input inside that same input’s own segwit area. That would make it so that wtxids still commit to all data relevant to a transaction’s validity, allowing it to remain usable as the sole transaction identifier, and avoiding some of the complications listed above.
There are two downsides, but both are addressable I think:
Extra storage/bandwidth: this obviously adds 32 bytes in a naive serialization format. However, since it’s just a hash of other data, it could be omitted from these formats. More interestingly, this can be done as an independent optimization, local to the node implementation, or negotiated as a P2P protocol extension, so it doesn’t burden deployment of the pqdata feature itself.
Impact on weight/cost: the same 32 bytes in the segwit witness (i.e., 8 vbytes) are inevitable as pre-softfork nodes see them. However, since this is being discussed in the context of a new output type, it’s also possible to just move all witness data to the pqdata area for spends of such outputs, allowing it to be costed arbitrarily, and it can start off with a cost of -8 vbytes to compensate for the pqdata commitment in the witness (of course, rounding up to 0 if it somehow remained negative still).
Without having thought too long about this, it seems like an obvious improvement to me over the approach used with segwit (though, the same approach couldn’t have worked as well there, as witnesses under 128 bytes - which are common now - would have been counted as 32 vbytes still).
I think ECDSA signature can simply commit to the quantum one inside R-value. And then, the quantum space can be just sigops-based: we allow up to N quantum signatures, which would have some constant size.
Abstractly, every transaction gains a per-txin witness style number (0 = segwit, 1 = pqdata, 2+ = future stuff).
Every style is associated with a P2P protocol extension, so nodes can opt into receiving specific styles or not. A full node would be expected to receive all styles known to its consensus rules. The reason for having multiple styles is to allow each to have its own discount/costing function, as those might need to change over time depending on signature schemes that are adopted. To not impose a bound on future ones, they must be optional to fetch for those that don’t have their cost rules known.
Serialization:
Use flag byte 0x02 after the 0x00 marker (instead of flag 0x01 used by segwit) if at least one style>0 witness is present in the transaction.
The encoding of witness data remains the same, except there is an additional style byte for every txin.
For relay to nodes that don’t support certain styles, witnesses can be “collapsed” to style 0, by replacing them with a commitment to the full data. Specifically, with a witness stack consisting of a single element of 34 bytes, of the form 0xff + style_byte + tagged_hash(style_byte + serialized non-collapsed witness data).
The wtxid and txid of a transaction are defined as the normal segwit ones, after collapsing all styles > 0.
The weight of a transaction is defined as the that of the normal segwit one as well, plus any additions due to style-specific rules.
All existing witness output types (P2TR, P2WPKH, P2WSH) get an “input has style=0” consensus rule.
Transaction inputs with a single-element style=0 witness of 34 bytes whose first byte is 0xff, followed by a known style number, are outlawed. This makes it possible to recognize “this is a downgraded witness for which I should have been given the full data instead”, without needing access to the UTXO being spent, or performing full script validation. Violations of this kind are a “witness stripped” type of error, so they don’t cause the block/tx it’s in to be marked (permanently) invalid.
So instead of having a “naive” serialization with both the full witness data, and a commitment to it in the normal witness, this just treats the abstract transactions as having at most one of the two. The backward compatibility is achieved by adding a “collapse” operation instead of (the equivalent of) witness stripping.
@garlonicon I think that works in theory, but it needs a rather ugly layer violation in that the p2p/serialization logic needs to pierce the script down to the opcode level, to understand whether/where/how many pqdatas are permitted.
Conceptually, I think this means “every input has authorisation data that gets a particular weight formula applied to it – legacy has the original 1:1 weighting, segwit has the 1:4 weighting, pqdata and future things have new weightings”.
In particular, this implies that spending an input uses only one authorisation type; you don’t have a taproot spend with a bip340 signature in segwit witness data and also an additional post-quantum signature via pqdata, eg. That prohibits the non-hard-fork “rescue protocol” method suggested in this list post.
For composite approaches like TRv2, I wonder if that approach is really what we want? If you spend a TRv2 coin via an bip340 path, should you get any “pqdata”-esque discounts? If you had a script that requires you to reveal 10kB worth of preimage data and also provide a signature, and provide (a) a 64 byte bip340 signature, or (b) a 3kB post-quantum signature, should you get pqdata-esque discounts at all in case (a)? Should you get a discount on the full 13kB in case (b) or just the 3kB?
Seems like this might as well be a minimal CompactSize?
I wonder if this would be better specified as an annex entry?
If we consider the annex as a place where we can extend the tx with additional “nSequence” and “nLockTime” like behaviours (eg, per-input locktimes, larger range relative locktimes, or block at height X has hash Y assertions), then it would probably be good to have those assertions be available independently of new transaction authorisation encodings/weightings, ie have the “collapsed” encoding includes the annex assertions (regarding locktimes, etc) still available, despite the other data being absent.
If it was desirable to have witness data in multiple styles (ie 1:4 ratio for hash preimages and 1:6 ratio for pqdata used for post-quantum signatures), having an annex commitment could be a reasonable way to signal that, eg:
annex encoding: “50” then a sequence of length-tag-value entries, ordered by tag, with no duplicate tags; tag 0 is the witness-style commitment, the value is an array of style/sha256 hash pairs
rules:
every input with a styled-witness, must include an annex commitment of that styled-witness
commitment of the styled-witness must
non-segwit-inputs and p2wpkh ad p2wsh can’t have a styled witness
style-2 witness data can only be used for p2trv2 inputs, and can only be used for data that’s read via CHECKPQSIG op
So a 41-byte annex of [50 22 00 02 [hash] 04 01 40420f] could represent a pqdata commitment plus a per-input lockheight of 1,000,000 (tag 1, little-endian encoding), eg. The “22 00 02 [hash]” component is derivable from the styled-witness-per-input data, but the bandwidth saving probably wouldn’t be worth the complexity, I guess?
It’s necessary to do things this way because if you don’t support the style, you not only don’t know how to interpret it, you also don’t know how much data you can accept in a block – is 4MB okay? 28MB? 500PB? So you have to discard unknown styles entirely and just store the commitment.
That also means that if anyone mines transactions with future/undefined witness styles, everyone will discard the associated data, so if a new style=3 pqdata2 is introduced one day, any blocks prior to the activation of that feature that has style=3 txs will be collapsed for everyone, not just nodes that haven’t upgraded to support pqdata2.
That’s certainly the easiest approach, but it’s not the only one. For example, the witness stack could be “typed” and different types of data can have different discounts, even within a single witness type. It’s annoying because that may mean a need to track the types throughout the script execution logic too, but it’s not infeasible. If more invasive changes to the scripting language are considered, you could have a design where the witness stack pretty much contains a sequence of (pubkey,signature) pairs (or just signature if the pubkey can be recovered from it) that are checked up front, and the script then contains assertions of the form “pubkey(hash) X signed”.
But maybe taking a step back: how should cost accounting occur, if we have the freedom to redesign it in abstract? I think it should be a per-txin monotonic function of (I/O costs, storage/bandwidth costs, CPU costs). The first is a constant (UTXO lookup). The second is proportional to the serialized size of the witness(es), and objectively speaking this is independent of how that data is used. The third is a function of executed opcodes.
I could imagine a design where the witness stack consists of just (a) a declared computation budget number (used by the opcodes in the script) and (b) script input data. Each witness style is then a formula for mapping the (computation budget, script input size) to WU. Newly introduced opcodes can have new/different computation cost from existing one without needing a new witness style. It is only when the formula changes, so practically when the cost per script input byte changes, that a new style is needed. Perhaps with such a design, a single style per txin suffices?
Sure, why not.
That seems reasonable. I think we could also simplify things by just permitting multiple annexes per txin, avoiding the complexity of encoding it into a single witness. Witness style commitments could then be an annex, but they could also be just something else, very much like annexes, but with a different prefix byte. Maybe that’s just a aesthetical difference; witness style commitments feel much more like a P2P/serialization thing, while annexes a script thing.
I don’t think that’s the case. The consensus rule that no style=0 commitments to a style=3 witness are allowed itself would activate along with the consensus change that gives meaning to style=3 data. Before that point, they’d just be style=0 witness data that happens to look like a commitment, but be relayed as style=0, and everyone would accept it without giving it special meaning.
I think it would be a lot easier to deal with if different weighting rules were separated structurally? In that case the “type” is just the “style”.
I think you could have non-constant I/O costs by allowing multiple “UTXO” lookups per-input; eg looking up 7be22151bc96041932830d79c2af4472e40e9dedaa29018fff6757501e7855c6:0 could give you up to 10kB of script data in a pubkey, which if it were reused across multiple transactions might be more efficient than repeating the same snippet in multiple transactions.
Perhaps it’s better to think of this as a way of dealing with storage costs reducing over time, that doesn’t involve (a) hard forks, (b) predicting the future and locking in a schedule in advance, (c) having regular soft forks to put in place a new temporary limit, where the risk is that if some soft fork fails, we don’t have any reasonable limit at all?
It’s not quite clear to me if “independent of how that data is used” is the right call here. It might be that the decision matrix is for the next decade should be something like:
ideal block size if Q-day doesn’t happen is 3.23MB – that maximises decentralisation
ideal block size if Q-day does happen is 12.76MB – that trades off some losses in decentralisation, versus avoiding a significant decrease in transaction capacity
If that’s the case, then it might make sense to provide ~10MB of capacity in a “pqdata” area, but require as consensus that the pqdata area is only used for post-quantum signatures. That way if Q-day doesn’t happen, people don’t use the pqdata area and blocks stay closers to 3.23MB target (because a post-quantum signature uses a higher percentage of 10MB than an ECC signature does of 4MB), but if Q-day does happen, the additional capacity is already available.
I think that’s true provided you don’t want to make tradeoffs like the above; but my impression is we probably do want to make tradeoffs like the above? That is, I think the ideal block size for TRv2 spends (eg) with current technology (node hardware, and post-quantum cryptosystems) is different before / after Q-day. I might be wrong ofc.
I think your description there is just a different way of saying what I intended.
I think the way to look at it is just that witness styles just don’t “exist” unless there are consensus rules (or any rules) that need to observe them. Before a softfork that introduces style=3, there is just no way to hand style=3 witness data to a node, because it either doesn’t know about it (pre-softfork software), or because it knows it doesn’t need it (pre-activation).
I think that means each new “style” introduction is a combination soft-fork, block storage and p2p upgrade much like segwit was, with the benefit that all the logic is pre-written with the first new style, so enabling new styles is just “define a new weighting rule, and the activation trigger”. For nodes that upgrade to the new logic late, you’d still need to re-download blocks after activation to get the additional data. That could theoretically involve “invalidating” post-activation blocks that were previously valid if you’re not able to obtain new style data that matched the commitment you already had.
So in theory just as complicated as segwit’s deployment, but in practice much simpler because it’s just repeating the same logic multiple times, I think.
That, but also no new transaction identifier (like wtxid, with associated P2P logic), and presumably no new weight units (I think 1 WU has enough granularity, so whatever formula is used, I think it can be rounded up to the next WU at the txin, or the tx level).
Annexes vs whole-witness commitment. There is another advantage to annex-style commitment over “the commitment is the entirely style=0 witness”, in that it means new witness styles can be introduced specific to new leaf version or opcodes even, without needing a new output type.
Chaining witness style commitments? I think we may be able to get away with just a single 32 WU commitment cost though, by chaining them. The style=0 witness would contain a single annex that commits to the witness of the lowest non-zero style if any. That witness would have 1 reserved/free spot for placing a commitment to an even higher witness style, and so forth. I think this is justified from a recourse cost perspective too: actually serialized data will only have at most 1 such non-expanded piece of witness commitment anyway, so there is no reason to account for more (except the single SHA256 verification cost for the witness…). This does require a sequential allocation of witness styles, where consensus changes that introduce a new witness style are aware of all previous ones, and nodes would never care about non-contiguous subsets of styles. I don’t think these are unreasonable constraints.
Mixed-discount witnesses. I’ve also thought a bit about how you’d construct mixed-cost witness data, where you e.g. want to prevent applying the highest-discount factor to anything but SHRINCS signatures. One possibility is reusing an assertion-style mechanism like OP_CLTV with annexes:
For every signature check a spend wants to perform, it adds a “check with (sig, pubkey)” annex to the input. If the scheme supports pubkey recovery, just the signature suffices.
The script itself then just issues checks of the form “require a check with pubkey(hash) X”, which searches the list of annexes of that form.
The weight computation code just needs to look at the annexes, and apply the right discount factors to each, which can be done entirely independent from script execution.
Hmm, should these be per-input commitments or per-transaction commitments? If you had a consolidation transaction (single signer, single output, multiple inputs, signature includes both a taproot bip340 signature and a post-quantum signature, in case either turns out to already be broken), would it be better to have that be constructed as:
* in 1:
* annex: 32B commit to PQ sig
* witness: script + 32B pubkey + 64B bip340 sig + 32B pq pubkey
* pq-style=1 witness: 3000B pq sig
* in 2..in 20:
* same
or to have a single 32B annex in the first input that has a pq-style-1 witness commit to all the style-1 witnesses?
Alternatively, maybe this isn’t worth worrying about (saving 32 bytes versus a 3000 byte signature?)? Or maybe it’s better solved as part of supporting CISA, so that the single-signer is also only generating a single bip340 signature that covers all their inputs, and perhaps combines the pq-signatures into that same input, so only one annex commitment is needed. Or, if you’re discounting the style=1+ data by the fact that you have to spend 32B of style=0 witness data to commit to it anyway, perhaps it just doesn’t matter at all.
Chaining and requiring sequential support (“if you support style n, you must support style 0..n-1”) seem pretty reasonable.
I think you might mean “adds a 'check with (msg, pubkey) annex to the input”? The sig is the thing you want to discount, and the annex isn’t discounted. I don’t really think that’s ideal – if you just added it to the annex, then an attacker could modify the msg or pubkey (possibly via breaking the bip340 sig that commits to the annex), so that wouldn’t achieve the security we want. If you have the script validating the annex, that would work, but I’m not sure there’s a meaningful benefit vs just having “pk msg CHECK_PQ_SIG_VERIFY” opcode that grabs the sig from the pq-style witness and does/schedules the actual signature check. I guess I’m implying that this introduces a new “pq-altstack” to the interpreter, and the only opcode that uses it is the pq-version of checksig, and there’s no other way to access the stack, and no way to add to the stack?
I think a per-input commitment is cleaner, but other than that I have little arguments against per-tx. There shouldn’t be a bandwidth difference (the commitment is elided in serialization), and the impact of verifying the hashing structure should be pretty minimal (if the commitment to the per-tx set of all higher-style witnesses uses per-txin hash that gets aggregated into a per-tx hash, the impact may even be zero).
One downside to per-txin is that it places a per-txin lower bound of 32 WU on the (combination of) all future-style witnesses. That’s immaterial if the future-style witnesses are hash-based pqdata, but is perhaps a concern if it’s just an P2MR ECC construction that aims for a CISA-like fee profile (which is justified for half-aggregation possibly, as its CPU cost equals that of batch validation).
Per-tx sounds like something natural for combining with CISA, as that naturally adds more per-tx context to both signing and verification.
I meant in an annex-like thing inside the new-style witness, which could be arbitrarily discounted by whatever rules that new style has.
Yeah, I guess that makes more sense. That also avoids the need for duplicating the public key (in the witness/annex) and public key commitment (in the script).
disclaimer, i haven’t read the whole thread yet. Before i do, I would like to suss out a radical alternative. What if we do not commit to the PQ signatures in the block extension?
There are some ideas i’ve been playing around with vis-a-vis SNARK aggregation where having malleable signature data could be extremely useful on an architectural/mining level to make SNARKification of blocks more efficient and and less burdensome for miners, making PQ block relay much faster too.
But before spending more cycles on this idea I would like to see if the premise is even feasible from a security perspective.
Let’s first assume a few things:
No PQ adaptor signatures (i.e. we never need proof of signature publication).
PQ signatures are constant-size (e.g. SLH-DSA).
The PQ extension block contains only PQ signatures, no other witness data.
Now with those assumptions, would it really be so bad if signatures were malleable?
If all we care about is authenticating messages (i.e. checking that pubkey X authorized message m), then what does it matter if the signature changes while the TX is in the mempool, or after the block is mined?
If you have a TX with valid signatures and someone else has the same TX with different valid signatures, do you really need to send any messages to update one-another?
To me at least, it seems that any valid signature on m by X is fungible with any other for the purposes of authentication. Are there other purposes for signatures besides adaptor schemes that i’m not seeing?
As you might imagine, the exact same question came up around the 2015-2017 segregated witness proposal. You can probably find records of discussions then.
The main reason is that block hashes, and PoW, are no longer committing to all data that is relevant for validation. Blocks, in the worst case, are pretty expensive to validate, and the latency in doing so is critical for block validation purposes. Thankfully, it is also very expensive to create a block (~10 minutes worth of global PoW), which is an extremely effective rate limiter on the creation of invalid blocks, and simultaneously a strong economic incentive not to create them. However, this only works because PoW commits to the witness data. Without it, any relay node can create infinitely many invalid versions of a valid (or inherently invalid) block, at basically zero cost, and verification logic cannot cache the result; it needs to check each and every one. Unlike for individual transactions, nodes do not have the option of dropping too-expensive blocks; they must accept them if they are valid.
Practically speaking, it means block validation failures wouldn’t be cacheable anymore, because a block’s identity (its hash) would just commit to its effects, not whether it is valid.
Another reason which may not apply as strongly in this specific case is auditability: if someone steals coins from a 2-of-3 multisig e.g. you may want the ability to see which signers did that. That’s especially relevant for OP_CHECKMULTISIG where the signature themselves choose the subset. That opcode doesn’t exist anymore in BIP-342 Tapscript, and could easily be avoided for future script proposals.
In the context of block-wide SNARK proofs, I think this means you want solutions that either:
Have the proof be part of the consensus rules, i.e., have the block commit to the SNARK proof, and have block validity defined in terms of that.
Have an “after the fact” proof that some nodes may accept, sort of like utreexo, which falls outside of the consensus rules. It would just need to make sure that it proves “a specific pqdata exists, which matches the commitments in the revealed data, that combined with the revealed non-pqdata, pass validity rules.”.
what about other layers of validation caching? e.g. most valid blocks contain signatures that active nodes have already seen and validated in the mempool, so worst-case when seeing a new block the node only needs to verify signatures on TXs which are covered by the block hash but that the node hasn’t positively validated previously.
Say a malicious node Bob takes a valid block and scrambles its signatures, then relays the invalid block to peer Alice.
Alice may have already seen the valid version of the same block (both valid and invalid blocks have the same block hash) and can ignore the invalid block.
If Alice hasn’t seen the block before, she only needs to check the signatures in transactions she hasn’t seen before, i.e. TXs not in her mempool, and those will probably be very few, yes?
Of course it’s possible for someone to mine a block containing a bunch of garbage transactions which weren’t previously validated by most nodes and thus triggering a lot of cache misses, but that’s already possible today if you have the hashpower. Thankfully it’s not economical to do so.
Still, even with TX-level validation caching, adversaries would have access to slightly more DoS attack surface. Perhaps there could also be some other way to rate-limit peers from proposing blocks with invalid witnesses. I will think on this some more and read the thread before throwing further ideas around.
Pieter Wuille · 
Garlo Nicon · 
Anthony Towns · 
conduition ·