* [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
@ 2025-05-28 17:14 Tadge Dryja
2025-05-28 18:20 ` Sergio Demian Lerner
` (2 more replies)
0 siblings, 3 replies; 10+ messages in thread
From: Tadge Dryja @ 2025-05-28 17:14 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 16638 bytes --]
One of the tricky things about securing Bitcoin against quantum computers
is: do you even need to? Maybe quantum computers that can break secp256k1
keys will never exist, in which case we shouldn't waste our time. Or maybe
they will exist, in not too many years, and we should spend the effort to
secure the system against QCs.
Since people disagree on how likely QCs are to arrive, and what the timing
would be if they do, it's hard to get consensus on changes to bitcoin that
disrupt the properties we use today. For example, a soft fork introducing
a post-quantum (PQ) signature scheme and at the same time disallowing new
secp256k1 based outputs would be great for strengthening Bitcoin against an
oncoming QC. But it would be awful if a QC never appears, or takes decades
to do so, since secp256k1 is really nice.
So it would be nice to have a way to not deal with this issue until *after*
the QC shows up. With commit / reveal schemes Bitcoin can keep working
after a QC shows up, even if we haven't defined a PQ signature scheme and
everyone's still got P2WPKH outputs.
Most of this is similar to Tim Ruffing's proposal from a few years ago here:
https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/
The main difference is that this scheme doesn't use encryption, but a
smaller hash-based commitment, and describes activation as a soft fork.
I'll define the two types of attacks, a commitment scheme, and then say
how it can be implemented in bitcoin nodes as a soft fork.
This scheme only works for keys that are pubkey hashes (or script hashes)
with pubkeys that are unknown to the network. It works with taproot as
well, but there must be some script-path in the taproot key, as keypath
spends would no longer be secure.
What to do with all the keys that are known is another issue and
independent of the scheme in this post (it's compatible with both burning
them and leaving them to be stolen)
For these schemes, we assume there is an attacker with a QC that can
compute a quickly compute a private key from any secp256k1 public key. We
also assume the attacker has some mining power or influence over miners for
their attacks; maybe not reliably, but they can sometimes get a few blocks
in a row with the transactions they want.
"Pubkey" can also be substituted with "script" for P2SH and P2WSH output
types and should work about the same way (with caveats about multisig).
The equivalent for taproot outputs would be an inner key proving a script
path.
## A simple scheme to show an attack
The simplest commit/reveal scheme would be one where after activation, for
any transaction with an EC signature in it, that transaction's txid must
appear in a earlier transaction's OP_RETURN output.
When a user wants to spend their coins, they first sign a transaction as
they would normally, compute the txid, get that txid into an OP_RETURN
output somehow (paying a miner out of band, etc), then after waiting a
while, broadcast the transaction. Nodes would check that the txid matches
a previously seen commitment, and allow the transaction.
One problem with this scheme is that upon seeing the full transaction, the
attacker can compute the user's private key, and create a new commitment
with a different txid for a transaction where the attacker gets all the
coins. If the attacker can get their commitment and spending transaction
in before the user's transaction, they can steal the coins.
In order to mitigate this problem, a minimum delay can be enforced by
consensus. A minimum delay of 100 blocks would mean that the attacker
would have to prevent the user's transaction from being confirmed for 100
blocks after it showed up in the attacker's mempool. The tradeoff is that
longer periods give better safety at the cost of more delay in spending.
This scheme, while problematic, is better than nothing! But it's possible
to remove this timing tradeoff.
## A slightly more complex scheme with (worse) problems
If instead of just the txid, the commitment were both the outpoint being
spent, and the txid that was going to spend it, we could add a "first seen"
consensus rule. Only the first commitment pointing to an outpoint works.
So if nodes see two OP_RETURN commitments in their sequence of confirmed
transactions:
C1 = outpoint1, txid1
C2 = outpoint1, txid2
They can ignore C2; C1 has already laid claim to outpoint1, and the
transaction identified by txid1 is the only transaction that can spend
outpoint1.
If the user manages to get C1 confirmed first, this is great, and
eliminates the timing problem in the txid only scheme. But this introduces
a different problem, where an attacker -- in this case any attacker, even
one without a QC -- who can observe C1 before it is confirmed can flip some
bits in the txid field, freezing the outpoint forever.
We want to retain the "first seen" rule, but we want to also be able to
discard invalid commitments. In a bit flipping attack, we could say an
invalid commitment is one where there is no transaction described by the
txid. A more general way to classify a commitment as invalid is a
commitment made without knowledge of the (secret) pubkey. Knowledge of the
pubkey is what security of coins is now hinging on.
The actual commitment scheme
We define some hash function h(). We'll use SHA256 for the hashing, but it
needs to be keyed with some tag, for example "Alas poor Koblitz curve, we
knew it well".
Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoin
output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin
terms, HASH160(pubkey). Due to the hash functions being different, A =
HASH160(pubkey) and B = h(pubkey) will be completely different, and nobody
should be able to determine if A and B are hashes of the same pubkey
without knowing pubkey itself.
An efficient commitment is:
C = h(pubkey), h(pubkey, txid), txid
(to label things: C = AID, SDP, CTXID)
This commitment includes 3 elements: a different hash of the pubkey which
will be signed for, a proof of knowledge of the pubkey which commits to a
transaction, and an the txid of the spending transaction. We'll call these
"address ID" (AID), sequence dependent proof (SDP), and the commitment txid
(CTXID).
For those familiar with the proposal by Ruffing, the SDP has a similar
function to the authenticated encryption part of the encrypted commitment.
Instead of using authenticated encryption, we can instead just use an
HMAC-style authentication alone, since the other data, the CTXID, is
provided.
When the user's wallet creates a transaction, they can feed that
transaction into a commitment generator function which takes in a
transaction, extracts the pubkey from the tx, computes the 3 hashes, and
returns the 3-hash commitment. Once this commitment is confirmed, the user
broadcasts the transaction.
Nodes verify the commitment by using the same commitment generator function
and checking if it matches the first valid commitment for that AID, in
which case the tx is confirmed.
If a node sees multiple commitments all claiming the same AID, it must
store all of them. Once the AID's pubkey is known, the node can
distinguish which commitments are valid, which are invalid, and which is
the first seen valid commitment. Given the pubkey, nodes can determine
commitments to be invalid by checking if SDP = h(pubkey, CTXID).
As an example, consider a sequence of 3 commitments:
C1 = h(pubkey), h(pubkey', txid1), txid1
C2 = h(pubkey), h(pubkey, txid2), txid2
C3 = h(pubkey), h(pubkey, txid3), txid3
The user first creates tx2 and tries to commit C2. But an attacker creates
C1, committing to a different txid where they control the outputs, and
confirms it first. This attacker may know the outpoint being spent, and
may be able to create a transaction and txid that could work. But they
don't know the pubkey, so while they can copy the AID hash, they have to
make something up for the SDP.
The user gets C2 confirmed after C1. They then reveal tx2 in the mempool,
but before it can be confirmed, the attacker gets C3 confirmed. C3 is a
valid commitment made with knowledge of the pubkey.
Nodes can reject transactions tx1 and tx3. For tx1, they will see that the
SDP doesn't match the data in the transaction, so it's an invalid
commitment. For tx3, they will see that it is valid, but by seeing tx3
they will also be able to determine that C2 is a valid commitment (since
pubkey is revealed in tx3) which came prior to C3, making C2 the only valid
commitment for that AID.
## Implementation
Nodes would keep a new key/value store, similar to the existing UTXO set.
The indexing key would be the AID, and the value would be the set of all
(SDP, CTXID) pairs seen alongside that AID. Every time an commitment is
seen in an OP_RETURN, nodes store the commitment.
When a transaction is seen, nodes observe the pubkey used in the
transaction, and look up if it matches an AID they have stored. If not,
the transaction is dropped. If the AID does match, the node can now "clean
out" an AID entry, eliminating all but the first valid commitment, and
marking that AID as final. If the txid seen matches the remaining
commitment, the transaction is valid; if not, the transaction is dropped.
After the transaction is confirmed the AID entry can be deleted. Deleting
the entries frees up space, and would allow another round to happen with
the same pubkey, which would lead to theft. Retaining the entries takes up
more space on nodes that can't be pruned, and causes pubkey reuse to
destroy coins rather than allow them to be stolen. That's a tradeoff, and
I personally guess it's probably not worth retaining that data but don't
have a strong opinion either way.
Short commitments:
Since we're not trying to defend against collision attacks, I think all 3
hashes can be truncated to 16 bytes. The whole commitment could be 48
bytes long. Without truncation the commitments would be 96 bytes.
## Activation
The activation for the commit/reveal requirement can be triggered by a
proof of quantum computer (PoQC).
A transaction which successfully spends an output using tapscript:
OP_SHA256 OP_CHECKSIG
is a PoQC in the form of a valid bitcoin transaction. In order to satisfy
this script, the spending transaction needs to provide 2 data elements: a
signature, and some data that when hashed results in a pubkey for which
that signature is valid. If such a pair of data elements exists, it means
that either SHA256 preimage resistance is broken (which we're assuming
isn't the case) or someone can create valid signatures for arbitrary
elliptic curve points, ie a cryptographically relevant quantum computer (or
any other process which breaks the security of secp256k1 signatures)
Once such a PoQC has been observed in a confirmed transaction, the
requirements for the 3-hash commitment scheme can be enforced. This is a
soft fork since the transactions themselves look the same, the only
requirement is that some OP_RETURN outputs show up earlier. Nodes which
are not aware of the commitment requirement will still accept all
transactions with the new rules.
Wallets not aware of the new rules, however, are very dangerous, as they
may try to broadcast signed transactions without any commitment. Nodes
that see such a transaction should drop the tx, and if possible tell the
wallet that they are doing something which is now very dangerous! On the
open p2p network this is not really enforceable, but people submitting
transactions to their own node (eg via RPC) can at least get a scary error
message.
## Issues
My hope is that this scheme would give some peace of mind to people holding
bitcoin, that in the face of a sudden QC, even with minimal preparation
their coins can be safe at rest and safely moved. It also suggests some
best practices for users and wallets to adopt, before any software changes:
Don't reuse addresses, and if you have taproot outputs, include some kind
of script path in the outer key.
There are still a number of problems, though!
- Reorgs can steal coins. An attacker that observes a pubkey and can reorg
back to before the commitment can compute the private key, sign a new
transaction and get their commitment in first on the new chain. This seems
unavoidable with commit/reveal schemes, and it's up to the user how long
they wait between confirming the commitment and revealing the transaction.
- How to get op_returns in
If there are no PQ signature schemes activated in bitcoin when this
activates, there's only one type of transaction that can reliably get the
OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to
the miners and paying them out of band is not great, but is possible and we
see this kind of activity today. Users wouldn't need to directly contact
miners: anyone could aggregate commitments, create a large transaction with
many OP_RETURN outputs, and then get a miner to commit to that parent
transaction. Users don't need to worry about committing twice as identical
commitments would be a no op.
- Spam
Anyone can make lots of OP_RETURN commitments which are just random
numbers, forcing nodes to store these commitments in a database. That's
not great, but isn't much different from how bitcoin works today. If it's
really a problem, nodes could requiring the commitment outputs to have a
non-0 amount of bitcoin, imposing a higher cost for the commitments than
other OP_RETURN outputs.
- Multiple inputs
If users have received more than one UTXO to the same address, they will
need to spend all the UTXOs at once. The commitment scheme can deal with
only the first pubkey seen in the serialized transaction.
- Multisig and Lightning Network
If your multisig counterparties have a QC, multisig outputs become 1 of N.
Possibly a more complex commit / reveal scheme could deal with multiple
keys, but the keys would all have to be hashed with counterparties not
knowing each others' unhashed pubkeys. This isn't how existing multisig
outputs work, and in fact the current trend is the opposite with things
like Musig2, FROST and ROAST. If we're going to need to make new signing
software and new output types it might make more sense to go for a PQ
signature scheme.
- Making more p2wpkhs
You don't have to send to a PQ address type with these transactions -- you
can send to p2wpkh and do the whole commit/reveal process again when you
want to spend. This could be helpful if PQ signature schemes are still
being worked on, or if the PQ schemes are more costly to verify and have
high fees in comparison to the old p2wpkh output types. It's possible that
in such a scenario a few high-cost PQ transactions commit to many smaller
EC transactions. If this actually gets adoption though, we might as well
drop the EC signatures and just make output scripts into raw hash /
preimage pairs. It could make sense to cover some non-EC script types with
the same 3-hash commitment requirement to enable this.
## Conclusion
This PQ commit / reveal scheme has similar properties to Tim Ruffing's,
with a smaller commitment that can be done as a soft fork. I hope
something like this could be soft forked with a PoQC activation trigger, so
that if a QC never shows up, none of this code gets executed. And people
who take a couple easy steps like not reusing addresses (which they should
anyway for privacy reasons) don't have to worry about their coins.
Some of these ideas may have been posted before; I know of the Fawkscoin
paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent
discussion which linked to Ruffing's proposal. Here I've tried to show how
it could be done in a soft fork which doesn't look too bad to implement.
I've also heard of some more complex schemes involving zero knowledge
proofs, proving things like BIP32 derivations, but I think this gives some
pretty good properties without needing anything other than good old SHA256.
Hope this is useful & wonder if people think something like this would be a
good idea.
-Tadge
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 17576 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-05-28 17:14 [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork Tadge Dryja
@ 2025-05-28 18:20 ` Sergio Demian Lerner
2025-05-28 20:24 ` Nagaev Boris
2025-05-31 16:07 ` [bitcoindev] " waxwing/ AdamISZ
2 siblings, 0 replies; 10+ messages in thread
From: Sergio Demian Lerner @ 2025-05-28 18:20 UTC (permalink / raw)
To: Tadge Dryja; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 18237 bytes --]
Without in-depth reading of your e-mail, but related to Fawkescoin, you can
read Mave paper from 2012 , which addressed DoS problems that exist in
Fawkescoin.
https://bitslog.com/wp-content/uploads/2012/04/mave1.pdf
regards
On Wed, May 28, 2025 at 10:28 AM Tadge Dryja <rx@awsomnet•org> wrote:
> One of the tricky things about securing Bitcoin against quantum computers
> is: do you even need to? Maybe quantum computers that can break secp256k1
> keys will never exist, in which case we shouldn't waste our time. Or maybe
> they will exist, in not too many years, and we should spend the effort to
> secure the system against QCs.
>
> Since people disagree on how likely QCs are to arrive, and what the timing
> would be if they do, it's hard to get consensus on changes to bitcoin that
> disrupt the properties we use today. For example, a soft fork introducing
> a post-quantum (PQ) signature scheme and at the same time disallowing new
> secp256k1 based outputs would be great for strengthening Bitcoin against an
> oncoming QC. But it would be awful if a QC never appears, or takes decades
> to do so, since secp256k1 is really nice.
>
> So it would be nice to have a way to not deal with this issue until
> *after* the QC shows up. With commit / reveal schemes Bitcoin can keep
> working after a QC shows up, even if we haven't defined a PQ signature
> scheme and everyone's still got P2WPKH outputs.
>
> Most of this is similar to Tim Ruffing's proposal from a few years ago
> here:
>
> https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/
>
> The main difference is that this scheme doesn't use encryption, but a
> smaller hash-based commitment, and describes activation as a soft fork.
> I'll define the two types of attacks, a commitment scheme, and then say how
> it can be implemented in bitcoin nodes as a soft fork.
>
> This scheme only works for keys that are pubkey hashes (or script hashes)
> with pubkeys that are unknown to the network. It works with taproot as
> well, but there must be some script-path in the taproot key, as keypath
> spends would no longer be secure.
>
> What to do with all the keys that are known is another issue and
> independent of the scheme in this post (it's compatible with both burning
> them and leaving them to be stolen)
>
> For these schemes, we assume there is an attacker with a QC that can
> compute a quickly compute a private key from any secp256k1 public key. We
> also assume the attacker has some mining power or influence over miners for
> their attacks; maybe not reliably, but they can sometimes get a few blocks
> in a row with the transactions they want.
>
> "Pubkey" can also be substituted with "script" for P2SH and P2WSH output
> types and should work about the same way (with caveats about multisig).
> The equivalent for taproot outputs would be an inner key proving a script
> path.
>
> ## A simple scheme to show an attack
>
> The simplest commit/reveal scheme would be one where after activation, for
> any transaction with an EC signature in it, that transaction's txid must
> appear in a earlier transaction's OP_RETURN output.
>
> When a user wants to spend their coins, they first sign a transaction as
> they would normally, compute the txid, get that txid into an OP_RETURN
> output somehow (paying a miner out of band, etc), then after waiting a
> while, broadcast the transaction. Nodes would check that the txid matches
> a previously seen commitment, and allow the transaction.
>
> One problem with this scheme is that upon seeing the full transaction, the
> attacker can compute the user's private key, and create a new commitment
> with a different txid for a transaction where the attacker gets all the
> coins. If the attacker can get their commitment and spending transaction
> in before the user's transaction, they can steal the coins.
>
> In order to mitigate this problem, a minimum delay can be enforced by
> consensus. A minimum delay of 100 blocks would mean that the attacker
> would have to prevent the user's transaction from being confirmed for 100
> blocks after it showed up in the attacker's mempool. The tradeoff is that
> longer periods give better safety at the cost of more delay in spending.
>
> This scheme, while problematic, is better than nothing! But it's possible
> to remove this timing tradeoff.
>
>
> ## A slightly more complex scheme with (worse) problems
>
> If instead of just the txid, the commitment were both the outpoint being
> spent, and the txid that was going to spend it, we could add a "first seen"
> consensus rule. Only the first commitment pointing to an outpoint works.
>
> So if nodes see two OP_RETURN commitments in their sequence of confirmed
> transactions:
>
> C1 = outpoint1, txid1
> C2 = outpoint1, txid2
>
> They can ignore C2; C1 has already laid claim to outpoint1, and the
> transaction identified by txid1 is the only transaction that can spend
> outpoint1.
>
> If the user manages to get C1 confirmed first, this is great, and
> eliminates the timing problem in the txid only scheme. But this introduces
> a different problem, where an attacker -- in this case any attacker, even
> one without a QC -- who can observe C1 before it is confirmed can flip some
> bits in the txid field, freezing the outpoint forever.
>
> We want to retain the "first seen" rule, but we want to also be able to
> discard invalid commitments. In a bit flipping attack, we could say an
> invalid commitment is one where there is no transaction described by the
> txid. A more general way to classify a commitment as invalid is a
> commitment made without knowledge of the (secret) pubkey. Knowledge of the
> pubkey is what security of coins is now hinging on.
>
>
> The actual commitment scheme
>
>
> We define some hash function h(). We'll use SHA256 for the hashing, but
> it needs to be keyed with some tag, for example "Alas poor Koblitz curve,
> we knew it well".
>
> Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoin
> output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin
> terms, HASH160(pubkey). Due to the hash functions being different, A =
> HASH160(pubkey) and B = h(pubkey) will be completely different, and nobody
> should be able to determine if A and B are hashes of the same pubkey
> without knowing pubkey itself.
>
> An efficient commitment is:
>
> C = h(pubkey), h(pubkey, txid), txid
> (to label things: C = AID, SDP, CTXID)
>
> This commitment includes 3 elements: a different hash of the pubkey which
> will be signed for, a proof of knowledge of the pubkey which commits to a
> transaction, and an the txid of the spending transaction. We'll call these
> "address ID" (AID), sequence dependent proof (SDP), and the commitment txid
> (CTXID).
>
> For those familiar with the proposal by Ruffing, the SDP has a similar
> function to the authenticated encryption part of the encrypted commitment.
> Instead of using authenticated encryption, we can instead just use an
> HMAC-style authentication alone, since the other data, the CTXID, is
> provided.
>
> When the user's wallet creates a transaction, they can feed that
> transaction into a commitment generator function which takes in a
> transaction, extracts the pubkey from the tx, computes the 3 hashes, and
> returns the 3-hash commitment. Once this commitment is confirmed, the user
> broadcasts the transaction.
>
> Nodes verify the commitment by using the same commitment generator
> function and checking if it matches the first valid commitment for that
> AID, in which case the tx is confirmed.
>
> If a node sees multiple commitments all claiming the same AID, it must
> store all of them. Once the AID's pubkey is known, the node can
> distinguish which commitments are valid, which are invalid, and which is
> the first seen valid commitment. Given the pubkey, nodes can determine
> commitments to be invalid by checking if SDP = h(pubkey, CTXID).
>
> As an example, consider a sequence of 3 commitments:
>
> C1 = h(pubkey), h(pubkey', txid1), txid1
> C2 = h(pubkey), h(pubkey, txid2), txid2
> C3 = h(pubkey), h(pubkey, txid3), txid3
>
> The user first creates tx2 and tries to commit C2. But an attacker
> creates C1, committing to a different txid where they control the outputs,
> and confirms it first. This attacker may know the outpoint being spent,
> and may be able to create a transaction and txid that could work. But they
> don't know the pubkey, so while they can copy the AID hash, they have to
> make something up for the SDP.
>
> The user gets C2 confirmed after C1. They then reveal tx2 in the mempool,
> but before it can be confirmed, the attacker gets C3 confirmed. C3 is a
> valid commitment made with knowledge of the pubkey.
>
> Nodes can reject transactions tx1 and tx3. For tx1, they will see that
> the SDP doesn't match the data in the transaction, so it's an invalid
> commitment. For tx3, they will see that it is valid, but by seeing tx3
> they will also be able to determine that C2 is a valid commitment (since
> pubkey is revealed in tx3) which came prior to C3, making C2 the only valid
> commitment for that AID.
>
>
> ## Implementation
>
> Nodes would keep a new key/value store, similar to the existing UTXO set.
> The indexing key would be the AID, and the value would be the set of all
> (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is
> seen in an OP_RETURN, nodes store the commitment.
>
> When a transaction is seen, nodes observe the pubkey used in the
> transaction, and look up if it matches an AID they have stored. If not,
> the transaction is dropped. If the AID does match, the node can now "clean
> out" an AID entry, eliminating all but the first valid commitment, and
> marking that AID as final. If the txid seen matches the remaining
> commitment, the transaction is valid; if not, the transaction is dropped.
>
> After the transaction is confirmed the AID entry can be deleted. Deleting
> the entries frees up space, and would allow another round to happen with
> the same pubkey, which would lead to theft. Retaining the entries takes up
> more space on nodes that can't be pruned, and causes pubkey reuse to
> destroy coins rather than allow them to be stolen. That's a tradeoff, and
> I personally guess it's probably not worth retaining that data but don't
> have a strong opinion either way.
>
> Short commitments:
>
> Since we're not trying to defend against collision attacks, I think all 3
> hashes can be truncated to 16 bytes. The whole commitment could be 48
> bytes long. Without truncation the commitments would be 96 bytes.
>
>
> ## Activation
>
> The activation for the commit/reveal requirement can be triggered by a
> proof of quantum computer (PoQC).
>
> A transaction which successfully spends an output using tapscript:
>
> OP_SHA256 OP_CHECKSIG
>
> is a PoQC in the form of a valid bitcoin transaction. In order to satisfy
> this script, the spending transaction needs to provide 2 data elements: a
> signature, and some data that when hashed results in a pubkey for which
> that signature is valid. If such a pair of data elements exists, it means
> that either SHA256 preimage resistance is broken (which we're assuming
> isn't the case) or someone can create valid signatures for arbitrary
> elliptic curve points, ie a cryptographically relevant quantum computer (or
> any other process which breaks the security of secp256k1 signatures)
>
> Once such a PoQC has been observed in a confirmed transaction, the
> requirements for the 3-hash commitment scheme can be enforced. This is a
> soft fork since the transactions themselves look the same, the only
> requirement is that some OP_RETURN outputs show up earlier. Nodes which
> are not aware of the commitment requirement will still accept all
> transactions with the new rules.
>
> Wallets not aware of the new rules, however, are very dangerous, as they
> may try to broadcast signed transactions without any commitment. Nodes
> that see such a transaction should drop the tx, and if possible tell the
> wallet that they are doing something which is now very dangerous! On the
> open p2p network this is not really enforceable, but people submitting
> transactions to their own node (eg via RPC) can at least get a scary error
> message.
>
>
> ## Issues
>
> My hope is that this scheme would give some peace of mind to people
> holding bitcoin, that in the face of a sudden QC, even with minimal
> preparation their coins can be safe at rest and safely moved. It also
> suggests some best practices for users and wallets to adopt, before any
> software changes: Don't reuse addresses, and if you have taproot outputs,
> include some kind of script path in the outer key.
>
> There are still a number of problems, though!
>
> - Reorgs can steal coins. An attacker that observes a pubkey and can
> reorg back to before the commitment can compute the private key, sign a new
> transaction and get their commitment in first on the new chain. This seems
> unavoidable with commit/reveal schemes, and it's up to the user how long
> they wait between confirming the commitment and revealing the transaction.
>
> - How to get op_returns in
> If there are no PQ signature schemes activated in bitcoin when this
> activates, there's only one type of transaction that can reliably get the
> OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to
> the miners and paying them out of band is not great, but is possible and we
> see this kind of activity today. Users wouldn't need to directly contact
> miners: anyone could aggregate commitments, create a large transaction with
> many OP_RETURN outputs, and then get a miner to commit to that parent
> transaction. Users don't need to worry about committing twice as identical
> commitments would be a no op.
>
> - Spam
> Anyone can make lots of OP_RETURN commitments which are just random
> numbers, forcing nodes to store these commitments in a database. That's
> not great, but isn't much different from how bitcoin works today. If it's
> really a problem, nodes could requiring the commitment outputs to have a
> non-0 amount of bitcoin, imposing a higher cost for the commitments than
> other OP_RETURN outputs.
>
> - Multiple inputs
> If users have received more than one UTXO to the same address, they will
> need to spend all the UTXOs at once. The commitment scheme can deal with
> only the first pubkey seen in the serialized transaction.
>
> - Multisig and Lightning Network
> If your multisig counterparties have a QC, multisig outputs become 1 of
> N. Possibly a more complex commit / reveal scheme could deal with multiple
> keys, but the keys would all have to be hashed with counterparties not
> knowing each others' unhashed pubkeys. This isn't how existing multisig
> outputs work, and in fact the current trend is the opposite with things
> like Musig2, FROST and ROAST. If we're going to need to make new signing
> software and new output types it might make more sense to go for a PQ
> signature scheme.
>
> - Making more p2wpkhs
> You don't have to send to a PQ address type with these transactions -- you
> can send to p2wpkh and do the whole commit/reveal process again when you
> want to spend. This could be helpful if PQ signature schemes are still
> being worked on, or if the PQ schemes are more costly to verify and have
> high fees in comparison to the old p2wpkh output types. It's possible that
> in such a scenario a few high-cost PQ transactions commit to many smaller
> EC transactions. If this actually gets adoption though, we might as well
> drop the EC signatures and just make output scripts into raw hash /
> preimage pairs. It could make sense to cover some non-EC script types with
> the same 3-hash commitment requirement to enable this.
>
> ## Conclusion
>
> This PQ commit / reveal scheme has similar properties to Tim Ruffing's,
> with a smaller commitment that can be done as a soft fork. I hope
> something like this could be soft forked with a PoQC activation trigger, so
> that if a QC never shows up, none of this code gets executed. And people
> who take a couple easy steps like not reusing addresses (which they should
> anyway for privacy reasons) don't have to worry about their coins.
>
> Some of these ideas may have been posted before; I know of the Fawkscoin
> paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent
> discussion which linked to Ruffing's proposal. Here I've tried to show how
> it could be done in a soft fork which doesn't look too bad to implement.
>
> I've also heard of some more complex schemes involving zero knowledge
> proofs, proving things like BIP32 derivations, but I think this gives some
> pretty good properties without needing anything other than good old SHA256.
>
> Hope this is useful & wonder if people think something like this would be
> a good idea.
>
> -Tadge
>
> --
> You received this message because you are subscribed to the Google Groups
> "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to bitcoindev+unsubscribe@googlegroups•com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAKzdR-rLT-QDoawED%3Dwf1DQKfYcVa_LPWBbHbK5GzekGhAFvZg%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 19158 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-05-28 17:14 [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork Tadge Dryja
2025-05-28 18:20 ` Sergio Demian Lerner
@ 2025-05-28 20:24 ` Nagaev Boris
2025-05-30 22:00 ` Jonathan Voss
2025-06-02 17:38 ` waxwing/ AdamISZ
2025-05-31 16:07 ` [bitcoindev] " waxwing/ AdamISZ
2 siblings, 2 replies; 10+ messages in thread
From: Nagaev Boris @ 2025-05-28 20:24 UTC (permalink / raw)
To: Tadge Dryja; +Cc: Bitcoin Development Mailing List
Hi Tadge,
Thanks for writing this up! The proposal is very thoughtful, and it's
great to see concrete work on post-quantum commit/reveal schemes.
I've been exploring a related approach based on a similar
commit/reveal idea. In my scheme, a user creates a QR output that
commits to a hash of a pubkey inside a Taproot leaf. This commitment
is hidden until revealed at spend time. Later, when the user wants to
spend a legacy EC output, they must spend this QR output in the same
transaction, and it must be at least X blocks old.
https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ
This approach has a few potential advantages:
1. No need for nodes to track a new commitment store
Because the commitment remains hidden in a Tapleaf until the spend,
observers (including attackers) don't see it, and nodes don't need to
store or validate any external commitment set. The only requirement is
that the QR output must be old enough, and Bitcoin Core already tracks
coin age, which is needed to validate existing consensus rules.
2. Commitment can be made before the transaction is known
Since the commitment doesn't include a txid, the user can precommit to
the pubkey hash far in advance, before knowing the details of the
eventual transaction. This allows greater flexibility: you can delay
choosing outputs, fee rates, etc., until spend time. Only knowledge of
the EC pubkey needs to be proven when creating the QR output.
3. More efficient use of block space
Multiple EC coins can be spent together with a single QR output,
holding EC pubkey commitments in Taproot leaves. If EC coins share the
same EC pubkey (e.g., come from the same address), they can reuse the
same commitment.
Would love to hear your thoughts on this variant. I think this one
might be a simpler, lower-overhead option for protecting EC outputs
post-QC.
Best,
Boris
On Wed, May 28, 2025 at 2:28 PM Tadge Dryja <rx@awsomnet•org> wrote:
>
> One of the tricky things about securing Bitcoin against quantum computers is: do you even need to? Maybe quantum computers that can break secp256k1 keys will never exist, in which case we shouldn't waste our time. Or maybe they will exist, in not too many years, and we should spend the effort to secure the system against QCs.
>
> Since people disagree on how likely QCs are to arrive, and what the timing would be if they do, it's hard to get consensus on changes to bitcoin that disrupt the properties we use today. For example, a soft fork introducing a post-quantum (PQ) signature scheme and at the same time disallowing new secp256k1 based outputs would be great for strengthening Bitcoin against an oncoming QC. But it would be awful if a QC never appears, or takes decades to do so, since secp256k1 is really nice.
>
> So it would be nice to have a way to not deal with this issue until *after* the QC shows up. With commit / reveal schemes Bitcoin can keep working after a QC shows up, even if we haven't defined a PQ signature scheme and everyone's still got P2WPKH outputs.
>
> Most of this is similar to Tim Ruffing's proposal from a few years ago here:
> https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/
>
> The main difference is that this scheme doesn't use encryption, but a smaller hash-based commitment, and describes activation as a soft fork. I'll define the two types of attacks, a commitment scheme, and then say how it can be implemented in bitcoin nodes as a soft fork.
>
> This scheme only works for keys that are pubkey hashes (or script hashes) with pubkeys that are unknown to the network. It works with taproot as well, but there must be some script-path in the taproot key, as keypath spends would no longer be secure.
>
> What to do with all the keys that are known is another issue and independent of the scheme in this post (it's compatible with both burning them and leaving them to be stolen)
>
> For these schemes, we assume there is an attacker with a QC that can compute a quickly compute a private key from any secp256k1 public key. We also assume the attacker has some mining power or influence over miners for their attacks; maybe not reliably, but they can sometimes get a few blocks in a row with the transactions they want.
>
> "Pubkey" can also be substituted with "script" for P2SH and P2WSH output types and should work about the same way (with caveats about multisig). The equivalent for taproot outputs would be an inner key proving a script path.
>
> ## A simple scheme to show an attack
>
> The simplest commit/reveal scheme would be one where after activation, for any transaction with an EC signature in it, that transaction's txid must appear in a earlier transaction's OP_RETURN output.
>
> When a user wants to spend their coins, they first sign a transaction as they would normally, compute the txid, get that txid into an OP_RETURN output somehow (paying a miner out of band, etc), then after waiting a while, broadcast the transaction. Nodes would check that the txid matches a previously seen commitment, and allow the transaction.
>
> One problem with this scheme is that upon seeing the full transaction, the attacker can compute the user's private key, and create a new commitment with a different txid for a transaction where the attacker gets all the coins. If the attacker can get their commitment and spending transaction in before the user's transaction, they can steal the coins.
>
> In order to mitigate this problem, a minimum delay can be enforced by consensus. A minimum delay of 100 blocks would mean that the attacker would have to prevent the user's transaction from being confirmed for 100 blocks after it showed up in the attacker's mempool. The tradeoff is that longer periods give better safety at the cost of more delay in spending.
>
> This scheme, while problematic, is better than nothing! But it's possible to remove this timing tradeoff.
>
>
> ## A slightly more complex scheme with (worse) problems
>
> If instead of just the txid, the commitment were both the outpoint being spent, and the txid that was going to spend it, we could add a "first seen" consensus rule. Only the first commitment pointing to an outpoint works.
>
> So if nodes see two OP_RETURN commitments in their sequence of confirmed transactions:
>
> C1 = outpoint1, txid1
> C2 = outpoint1, txid2
>
> They can ignore C2; C1 has already laid claim to outpoint1, and the transaction identified by txid1 is the only transaction that can spend outpoint1.
>
> If the user manages to get C1 confirmed first, this is great, and eliminates the timing problem in the txid only scheme. But this introduces a different problem, where an attacker -- in this case any attacker, even one without a QC -- who can observe C1 before it is confirmed can flip some bits in the txid field, freezing the outpoint forever.
>
> We want to retain the "first seen" rule, but we want to also be able to discard invalid commitments. In a bit flipping attack, we could say an invalid commitment is one where there is no transaction described by the txid. A more general way to classify a commitment as invalid is a commitment made without knowledge of the (secret) pubkey. Knowledge of the pubkey is what security of coins is now hinging on.
>
>
> The actual commitment scheme
>
>
> We define some hash function h(). We'll use SHA256 for the hashing, but it needs to be keyed with some tag, for example "Alas poor Koblitz curve, we knew it well".
>
> Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin terms, HASH160(pubkey). Due to the hash functions being different, A = HASH160(pubkey) and B = h(pubkey) will be completely different, and nobody should be able to determine if A and B are hashes of the same pubkey without knowing pubkey itself.
>
> An efficient commitment is:
>
> C = h(pubkey), h(pubkey, txid), txid
> (to label things: C = AID, SDP, CTXID)
>
> This commitment includes 3 elements: a different hash of the pubkey which will be signed for, a proof of knowledge of the pubkey which commits to a transaction, and an the txid of the spending transaction. We'll call these "address ID" (AID), sequence dependent proof (SDP), and the commitment txid (CTXID).
>
> For those familiar with the proposal by Ruffing, the SDP has a similar function to the authenticated encryption part of the encrypted commitment. Instead of using authenticated encryption, we can instead just use an HMAC-style authentication alone, since the other data, the CTXID, is provided.
>
> When the user's wallet creates a transaction, they can feed that transaction into a commitment generator function which takes in a transaction, extracts the pubkey from the tx, computes the 3 hashes, and returns the 3-hash commitment. Once this commitment is confirmed, the user broadcasts the transaction.
>
> Nodes verify the commitment by using the same commitment generator function and checking if it matches the first valid commitment for that AID, in which case the tx is confirmed.
>
> If a node sees multiple commitments all claiming the same AID, it must store all of them. Once the AID's pubkey is known, the node can distinguish which commitments are valid, which are invalid, and which is the first seen valid commitment. Given the pubkey, nodes can determine commitments to be invalid by checking if SDP = h(pubkey, CTXID).
>
> As an example, consider a sequence of 3 commitments:
>
> C1 = h(pubkey), h(pubkey', txid1), txid1
> C2 = h(pubkey), h(pubkey, txid2), txid2
> C3 = h(pubkey), h(pubkey, txid3), txid3
>
> The user first creates tx2 and tries to commit C2. But an attacker creates C1, committing to a different txid where they control the outputs, and confirms it first. This attacker may know the outpoint being spent, and may be able to create a transaction and txid that could work. But they don't know the pubkey, so while they can copy the AID hash, they have to make something up for the SDP.
>
> The user gets C2 confirmed after C1. They then reveal tx2 in the mempool, but before it can be confirmed, the attacker gets C3 confirmed. C3 is a valid commitment made with knowledge of the pubkey.
>
> Nodes can reject transactions tx1 and tx3. For tx1, they will see that the SDP doesn't match the data in the transaction, so it's an invalid commitment. For tx3, they will see that it is valid, but by seeing tx3 they will also be able to determine that C2 is a valid commitment (since pubkey is revealed in tx3) which came prior to C3, making C2 the only valid commitment for that AID.
>
>
> ## Implementation
>
> Nodes would keep a new key/value store, similar to the existing UTXO set. The indexing key would be the AID, and the value would be the set of all (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is seen in an OP_RETURN, nodes store the commitment.
>
> When a transaction is seen, nodes observe the pubkey used in the transaction, and look up if it matches an AID they have stored. If not, the transaction is dropped. If the AID does match, the node can now "clean out" an AID entry, eliminating all but the first valid commitment, and marking that AID as final. If the txid seen matches the remaining commitment, the transaction is valid; if not, the transaction is dropped.
>
> After the transaction is confirmed the AID entry can be deleted. Deleting the entries frees up space, and would allow another round to happen with the same pubkey, which would lead to theft. Retaining the entries takes up more space on nodes that can't be pruned, and causes pubkey reuse to destroy coins rather than allow them to be stolen. That's a tradeoff, and I personally guess it's probably not worth retaining that data but don't have a strong opinion either way.
>
> Short commitments:
>
> Since we're not trying to defend against collision attacks, I think all 3 hashes can be truncated to 16 bytes. The whole commitment could be 48 bytes long. Without truncation the commitments would be 96 bytes.
>
>
> ## Activation
>
> The activation for the commit/reveal requirement can be triggered by a proof of quantum computer (PoQC).
>
> A transaction which successfully spends an output using tapscript:
>
> OP_SHA256 OP_CHECKSIG
>
> is a PoQC in the form of a valid bitcoin transaction. In order to satisfy this script, the spending transaction needs to provide 2 data elements: a signature, and some data that when hashed results in a pubkey for which that signature is valid. If such a pair of data elements exists, it means that either SHA256 preimage resistance is broken (which we're assuming isn't the case) or someone can create valid signatures for arbitrary elliptic curve points, ie a cryptographically relevant quantum computer (or any other process which breaks the security of secp256k1 signatures)
>
> Once such a PoQC has been observed in a confirmed transaction, the requirements for the 3-hash commitment scheme can be enforced. This is a soft fork since the transactions themselves look the same, the only requirement is that some OP_RETURN outputs show up earlier. Nodes which are not aware of the commitment requirement will still accept all transactions with the new rules.
>
> Wallets not aware of the new rules, however, are very dangerous, as they may try to broadcast signed transactions without any commitment. Nodes that see such a transaction should drop the tx, and if possible tell the wallet that they are doing something which is now very dangerous! On the open p2p network this is not really enforceable, but people submitting transactions to their own node (eg via RPC) can at least get a scary error message.
>
>
> ## Issues
>
> My hope is that this scheme would give some peace of mind to people holding bitcoin, that in the face of a sudden QC, even with minimal preparation their coins can be safe at rest and safely moved. It also suggests some best practices for users and wallets to adopt, before any software changes: Don't reuse addresses, and if you have taproot outputs, include some kind of script path in the outer key.
>
> There are still a number of problems, though!
>
> - Reorgs can steal coins. An attacker that observes a pubkey and can reorg back to before the commitment can compute the private key, sign a new transaction and get their commitment in first on the new chain. This seems unavoidable with commit/reveal schemes, and it's up to the user how long they wait between confirming the commitment and revealing the transaction.
>
> - How to get op_returns in
> If there are no PQ signature schemes activated in bitcoin when this activates, there's only one type of transaction that can reliably get the OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to the miners and paying them out of band is not great, but is possible and we see this kind of activity today. Users wouldn't need to directly contact miners: anyone could aggregate commitments, create a large transaction with many OP_RETURN outputs, and then get a miner to commit to that parent transaction. Users don't need to worry about committing twice as identical commitments would be a no op.
>
> - Spam
> Anyone can make lots of OP_RETURN commitments which are just random numbers, forcing nodes to store these commitments in a database. That's not great, but isn't much different from how bitcoin works today. If it's really a problem, nodes could requiring the commitment outputs to have a non-0 amount of bitcoin, imposing a higher cost for the commitments than other OP_RETURN outputs.
>
> - Multiple inputs
> If users have received more than one UTXO to the same address, they will need to spend all the UTXOs at once. The commitment scheme can deal with only the first pubkey seen in the serialized transaction.
>
> - Multisig and Lightning Network
> If your multisig counterparties have a QC, multisig outputs become 1 of N. Possibly a more complex commit / reveal scheme could deal with multiple keys, but the keys would all have to be hashed with counterparties not knowing each others' unhashed pubkeys. This isn't how existing multisig outputs work, and in fact the current trend is the opposite with things like Musig2, FROST and ROAST. If we're going to need to make new signing software and new output types it might make more sense to go for a PQ signature scheme.
>
> - Making more p2wpkhs
> You don't have to send to a PQ address type with these transactions -- you can send to p2wpkh and do the whole commit/reveal process again when you want to spend. This could be helpful if PQ signature schemes are still being worked on, or if the PQ schemes are more costly to verify and have high fees in comparison to the old p2wpkh output types. It's possible that in such a scenario a few high-cost PQ transactions commit to many smaller EC transactions. If this actually gets adoption though, we might as well drop the EC signatures and just make output scripts into raw hash / preimage pairs. It could make sense to cover some non-EC script types with the same 3-hash commitment requirement to enable this.
>
> ## Conclusion
>
> This PQ commit / reveal scheme has similar properties to Tim Ruffing's, with a smaller commitment that can be done as a soft fork. I hope something like this could be soft forked with a PoQC activation trigger, so that if a QC never shows up, none of this code gets executed. And people who take a couple easy steps like not reusing addresses (which they should anyway for privacy reasons) don't have to worry about their coins.
>
> Some of these ideas may have been posted before; I know of the Fawkscoin paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent discussion which linked to Ruffing's proposal. Here I've tried to show how it could be done in a soft fork which doesn't look too bad to implement.
>
> I've also heard of some more complex schemes involving zero knowledge proofs, proving things like BIP32 derivations, but I think this gives some pretty good properties without needing anything other than good old SHA256.
>
> Hope this is useful & wonder if people think something like this would be a good idea.
>
> -Tadge
>
> --
> You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com.
--
Best regards,
Boris Nagaev
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAFC_Vt6gqV-8aoTKt2it1p9LAnvaADueHnC1cM6LQojZf6fjCw%40mail.gmail.com.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-05-28 20:24 ` Nagaev Boris
@ 2025-05-30 22:00 ` Jonathan Voss
2025-06-02 11:24 ` Peter Todd
2025-06-02 17:38 ` waxwing/ AdamISZ
1 sibling, 1 reply; 10+ messages in thread
From: Jonathan Voss @ 2025-05-30 22:00 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 21135 bytes --]
As far as I can tell, the main flaw in commit/reveal protocols is in the
commit phase: if revealing a commitment with N confirmations is required to
spend bitcoins, then, without spending any bitcoins, how do you get the
commitment into the blockchain in the first place? Maybe I am just
misunderstanding this. If so, then a commit/reveal scheme may be a workable
solution.
I really like the PoQC trigger mechanism, but I doubt that a real quantum
attacker would voluntarily activate the network's QC defense soft-fork
instead of just attacking -- it seems to assume that an honest node will
spend the PoQC transaction before a real adversary shows up.
-- Jonathan
On Wednesday, May 28, 2025 at 5:54:21 PM UTC-4 Nagaev Boris wrote:
> Hi Tadge,
>
> Thanks for writing this up! The proposal is very thoughtful, and it's
> great to see concrete work on post-quantum commit/reveal schemes.
>
> I've been exploring a related approach based on a similar
> commit/reveal idea. In my scheme, a user creates a QR output that
> commits to a hash of a pubkey inside a Taproot leaf. This commitment
> is hidden until revealed at spend time. Later, when the user wants to
> spend a legacy EC output, they must spend this QR output in the same
> transaction, and it must be at least X blocks old.
>
> https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ
>
> This approach has a few potential advantages:
>
> 1. No need for nodes to track a new commitment store
>
> Because the commitment remains hidden in a Tapleaf until the spend,
> observers (including attackers) don't see it, and nodes don't need to
> store or validate any external commitment set. The only requirement is
> that the QR output must be old enough, and Bitcoin Core already tracks
> coin age, which is needed to validate existing consensus rules.
>
> 2. Commitment can be made before the transaction is known
>
> Since the commitment doesn't include a txid, the user can precommit to
> the pubkey hash far in advance, before knowing the details of the
> eventual transaction. This allows greater flexibility: you can delay
> choosing outputs, fee rates, etc., until spend time. Only knowledge of
> the EC pubkey needs to be proven when creating the QR output.
>
> 3. More efficient use of block space
>
> Multiple EC coins can be spent together with a single QR output,
> holding EC pubkey commitments in Taproot leaves. If EC coins share the
> same EC pubkey (e.g., come from the same address), they can reuse the
> same commitment.
>
> Would love to hear your thoughts on this variant. I think this one
> might be a simpler, lower-overhead option for protecting EC outputs
> post-QC.
>
> Best,
> Boris
>
> On Wed, May 28, 2025 at 2:28 PM Tadge Dryja <r...@awsomnet•org> wrote:
> >
> > One of the tricky things about securing Bitcoin against quantum
> computers is: do you even need to? Maybe quantum computers that can break
> secp256k1 keys will never exist, in which case we shouldn't waste our time.
> Or maybe they will exist, in not too many years, and we should spend the
> effort to secure the system against QCs.
> >
> > Since people disagree on how likely QCs are to arrive, and what the
> timing would be if they do, it's hard to get consensus on changes to
> bitcoin that disrupt the properties we use today. For example, a soft fork
> introducing a post-quantum (PQ) signature scheme and at the same time
> disallowing new secp256k1 based outputs would be great for strengthening
> Bitcoin against an oncoming QC. But it would be awful if a QC never
> appears, or takes decades to do so, since secp256k1 is really nice.
> >
> > So it would be nice to have a way to not deal with this issue until
> *after* the QC shows up. With commit / reveal schemes Bitcoin can keep
> working after a QC shows up, even if we haven't defined a PQ signature
> scheme and everyone's still got P2WPKH outputs.
> >
> > Most of this is similar to Tim Ruffing's proposal from a few years ago
> here:
> > https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/
> <https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/>
> >
> > The main difference is that this scheme doesn't use encryption, but a
> smaller hash-based commitment, and describes activation as a soft fork.
> I'll define the two types of attacks, a commitment scheme, and then say how
> it can be implemented in bitcoin nodes as a soft fork.
> >
> > This scheme only works for keys that are pubkey hashes (or script
> hashes) with pubkeys that are unknown to the network. It works with taproot
> as well, but there must be some script-path in the taproot key, as keypath
> spends would no longer be secure.
> >
> > What to do with all the keys that are known is another issue and
> independent of the scheme in this post (it's compatible with both burning
> them and leaving them to be stolen)
> >
> > For these schemes, we assume there is an attacker with a QC that can
> compute a quickly compute a private key from any secp256k1 public key. We
> also assume the attacker has some mining power or influence over miners for
> their attacks; maybe not reliably, but they can sometimes get a few blocks
> in a row with the transactions they want.
> >
> > "Pubkey" can also be substituted with "script" for P2SH and P2WSH output
> types and should work about the same way (with caveats about multisig). The
> equivalent for taproot outputs would be an inner key proving a script path.
> >
> > ## A simple scheme to show an attack
> >
> > The simplest commit/reveal scheme would be one where after activation,
> for any transaction with an EC signature in it, that transaction's txid
> must appear in a earlier transaction's OP_RETURN output.
> >
> > When a user wants to spend their coins, they first sign a transaction as
> they would normally, compute the txid, get that txid into an OP_RETURN
> output somehow (paying a miner out of band, etc), then after waiting a
> while, broadcast the transaction. Nodes would check that the txid matches a
> previously seen commitment, and allow the transaction.
> >
> > One problem with this scheme is that upon seeing the full transaction,
> the attacker can compute the user's private key, and create a new
> commitment with a different txid for a transaction where the attacker gets
> all the coins. If the attacker can get their commitment and spending
> transaction in before the user's transaction, they can steal the coins.
> >
> > In order to mitigate this problem, a minimum delay can be enforced by
> consensus. A minimum delay of 100 blocks would mean that the attacker would
> have to prevent the user's transaction from being confirmed for 100 blocks
> after it showed up in the attacker's mempool. The tradeoff is that longer
> periods give better safety at the cost of more delay in spending.
> >
> > This scheme, while problematic, is better than nothing! But it's
> possible to remove this timing tradeoff.
> >
> >
> > ## A slightly more complex scheme with (worse) problems
> >
> > If instead of just the txid, the commitment were both the outpoint being
> spent, and the txid that was going to spend it, we could add a "first seen"
> consensus rule. Only the first commitment pointing to an outpoint works.
> >
> > So if nodes see two OP_RETURN commitments in their sequence of confirmed
> transactions:
> >
> > C1 = outpoint1, txid1
> > C2 = outpoint1, txid2
> >
> > They can ignore C2; C1 has already laid claim to outpoint1, and the
> transaction identified by txid1 is the only transaction that can spend
> outpoint1.
> >
> > If the user manages to get C1 confirmed first, this is great, and
> eliminates the timing problem in the txid only scheme. But this introduces
> a different problem, where an attacker -- in this case any attacker, even
> one without a QC -- who can observe C1 before it is confirmed can flip some
> bits in the txid field, freezing the outpoint forever.
> >
> > We want to retain the "first seen" rule, but we want to also be able to
> discard invalid commitments. In a bit flipping attack, we could say an
> invalid commitment is one where there is no transaction described by the
> txid. A more general way to classify a commitment as invalid is a
> commitment made without knowledge of the (secret) pubkey. Knowledge of the
> pubkey is what security of coins is now hinging on.
> >
> >
> > The actual commitment scheme
> >
> >
> > We define some hash function h(). We'll use SHA256 for the hashing, but
> it needs to be keyed with some tag, for example "Alas poor Koblitz curve,
> we knew it well".
> >
> > Thus h(pubkey) is not equal to the pubkey hash already used in the
> bitcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in
> bitcoin terms, HASH160(pubkey). Due to the hash functions being different,
> A = HASH160(pubkey) and B = h(pubkey) will be completely different, and
> nobody should be able to determine if A and B are hashes of the same pubkey
> without knowing pubkey itself.
> >
> > An efficient commitment is:
> >
> > C = h(pubkey), h(pubkey, txid), txid
> > (to label things: C = AID, SDP, CTXID)
> >
> > This commitment includes 3 elements: a different hash of the pubkey
> which will be signed for, a proof of knowledge of the pubkey which commits
> to a transaction, and an the txid of the spending transaction. We'll call
> these "address ID" (AID), sequence dependent proof (SDP), and the
> commitment txid (CTXID).
> >
> > For those familiar with the proposal by Ruffing, the SDP has a similar
> function to the authenticated encryption part of the encrypted commitment.
> Instead of using authenticated encryption, we can instead just use an
> HMAC-style authentication alone, since the other data, the CTXID, is
> provided.
> >
> > When the user's wallet creates a transaction, they can feed that
> transaction into a commitment generator function which takes in a
> transaction, extracts the pubkey from the tx, computes the 3 hashes, and
> returns the 3-hash commitment. Once this commitment is confirmed, the user
> broadcasts the transaction.
> >
> > Nodes verify the commitment by using the same commitment generator
> function and checking if it matches the first valid commitment for that
> AID, in which case the tx is confirmed.
> >
> > If a node sees multiple commitments all claiming the same AID, it must
> store all of them. Once the AID's pubkey is known, the node can distinguish
> which commitments are valid, which are invalid, and which is the first seen
> valid commitment. Given the pubkey, nodes can determine commitments to be
> invalid by checking if SDP = h(pubkey, CTXID).
> >
> > As an example, consider a sequence of 3 commitments:
> >
> > C1 = h(pubkey), h(pubkey', txid1), txid1
> > C2 = h(pubkey), h(pubkey, txid2), txid2
> > C3 = h(pubkey), h(pubkey, txid3), txid3
> >
> > The user first creates tx2 and tries to commit C2. But an attacker
> creates C1, committing to a different txid where they control the outputs,
> and confirms it first. This attacker may know the outpoint being spent, and
> may be able to create a transaction and txid that could work. But they
> don't know the pubkey, so while they can copy the AID hash, they have to
> make something up for the SDP.
> >
> > The user gets C2 confirmed after C1. They then reveal tx2 in the
> mempool, but before it can be confirmed, the attacker gets C3 confirmed. C3
> is a valid commitment made with knowledge of the pubkey.
> >
> > Nodes can reject transactions tx1 and tx3. For tx1, they will see that
> the SDP doesn't match the data in the transaction, so it's an invalid
> commitment. For tx3, they will see that it is valid, but by seeing tx3 they
> will also be able to determine that C2 is a valid commitment (since pubkey
> is revealed in tx3) which came prior to C3, making C2 the only valid
> commitment for that AID.
> >
> >
> > ## Implementation
> >
> > Nodes would keep a new key/value store, similar to the existing UTXO
> set. The indexing key would be the AID, and the value would be the set of
> all (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is
> seen in an OP_RETURN, nodes store the commitment.
> >
> > When a transaction is seen, nodes observe the pubkey used in the
> transaction, and look up if it matches an AID they have stored. If not, the
> transaction is dropped. If the AID does match, the node can now "clean out"
> an AID entry, eliminating all but the first valid commitment, and marking
> that AID as final. If the txid seen matches the remaining commitment, the
> transaction is valid; if not, the transaction is dropped.
> >
> > After the transaction is confirmed the AID entry can be deleted.
> Deleting the entries frees up space, and would allow another round to
> happen with the same pubkey, which would lead to theft. Retaining the
> entries takes up more space on nodes that can't be pruned, and causes
> pubkey reuse to destroy coins rather than allow them to be stolen. That's a
> tradeoff, and I personally guess it's probably not worth retaining that
> data but don't have a strong opinion either way.
> >
> > Short commitments:
> >
> > Since we're not trying to defend against collision attacks, I think all
> 3 hashes can be truncated to 16 bytes. The whole commitment could be 48
> bytes long. Without truncation the commitments would be 96 bytes.
> >
> >
> > ## Activation
> >
> > The activation for the commit/reveal requirement can be triggered by a
> proof of quantum computer (PoQC).
> >
> > A transaction which successfully spends an output using tapscript:
> >
> > OP_SHA256 OP_CHECKSIG
> >
> > is a PoQC in the form of a valid bitcoin transaction. In order to
> satisfy this script, the spending transaction needs to provide 2 data
> elements: a signature, and some data that when hashed results in a pubkey
> for which that signature is valid. If such a pair of data elements exists,
> it means that either SHA256 preimage resistance is broken (which we're
> assuming isn't the case) or someone can create valid signatures for
> arbitrary elliptic curve points, ie a cryptographically relevant quantum
> computer (or any other process which breaks the security of secp256k1
> signatures)
> >
> > Once such a PoQC has been observed in a confirmed transaction, the
> requirements for the 3-hash commitment scheme can be enforced. This is a
> soft fork since the transactions themselves look the same, the only
> requirement is that some OP_RETURN outputs show up earlier. Nodes which are
> not aware of the commitment requirement will still accept all transactions
> with the new rules.
> >
> > Wallets not aware of the new rules, however, are very dangerous, as they
> may try to broadcast signed transactions without any commitment. Nodes that
> see such a transaction should drop the tx, and if possible tell the wallet
> that they are doing something which is now very dangerous! On the open p2p
> network this is not really enforceable, but people submitting transactions
> to their own node (eg via RPC) can at least get a scary error message.
> >
> >
> > ## Issues
> >
> > My hope is that this scheme would give some peace of mind to people
> holding bitcoin, that in the face of a sudden QC, even with minimal
> preparation their coins can be safe at rest and safely moved. It also
> suggests some best practices for users and wallets to adopt, before any
> software changes: Don't reuse addresses, and if you have taproot outputs,
> include some kind of script path in the outer key.
> >
> > There are still a number of problems, though!
> >
> > - Reorgs can steal coins. An attacker that observes a pubkey and can
> reorg back to before the commitment can compute the private key, sign a new
> transaction and get their commitment in first on the new chain. This seems
> unavoidable with commit/reveal schemes, and it's up to the user how long
> they wait between confirming the commitment and revealing the transaction.
> >
> > - How to get op_returns in
> > If there are no PQ signature schemes activated in bitcoin when this
> activates, there's only one type of transaction that can reliably get the
> OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to
> the miners and paying them out of band is not great, but is possible and we
> see this kind of activity today. Users wouldn't need to directly contact
> miners: anyone could aggregate commitments, create a large transaction with
> many OP_RETURN outputs, and then get a miner to commit to that parent
> transaction. Users don't need to worry about committing twice as identical
> commitments would be a no op.
> >
> > - Spam
> > Anyone can make lots of OP_RETURN commitments which are just random
> numbers, forcing nodes to store these commitments in a database. That's not
> great, but isn't much different from how bitcoin works today. If it's
> really a problem, nodes could requiring the commitment outputs to have a
> non-0 amount of bitcoin, imposing a higher cost for the commitments than
> other OP_RETURN outputs.
> >
> > - Multiple inputs
> > If users have received more than one UTXO to the same address, they will
> need to spend all the UTXOs at once. The commitment scheme can deal with
> only the first pubkey seen in the serialized transaction.
> >
> > - Multisig and Lightning Network
> > If your multisig counterparties have a QC, multisig outputs become 1 of
> N. Possibly a more complex commit / reveal scheme could deal with multiple
> keys, but the keys would all have to be hashed with counterparties not
> knowing each others' unhashed pubkeys. This isn't how existing multisig
> outputs work, and in fact the current trend is the opposite with things
> like Musig2, FROST and ROAST. If we're going to need to make new signing
> software and new output types it might make more sense to go for a PQ
> signature scheme.
> >
> > - Making more p2wpkhs
> > You don't have to send to a PQ address type with these transactions --
> you can send to p2wpkh and do the whole commit/reveal process again when
> you want to spend. This could be helpful if PQ signature schemes are still
> being worked on, or if the PQ schemes are more costly to verify and have
> high fees in comparison to the old p2wpkh output types. It's possible that
> in such a scenario a few high-cost PQ transactions commit to many smaller
> EC transactions. If this actually gets adoption though, we might as well
> drop the EC signatures and just make output scripts into raw hash /
> preimage pairs. It could make sense to cover some non-EC script types with
> the same 3-hash commitment requirement to enable this.
> >
> > ## Conclusion
> >
> > This PQ commit / reveal scheme has similar properties to Tim Ruffing's,
> with a smaller commitment that can be done as a soft fork. I hope something
> like this could be soft forked with a PoQC activation trigger, so that if a
> QC never shows up, none of this code gets executed. And people who take a
> couple easy steps like not reusing addresses (which they should anyway for
> privacy reasons) don't have to worry about their coins.
> >
> > Some of these ideas may have been posted before; I know of the Fawkscoin
> paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent
> discussion which linked to Ruffing's proposal. Here I've tried to show how
> it could be done in a soft fork which doesn't look too bad to implement.
> >
> > I've also heard of some more complex schemes involving zero knowledge
> proofs, proving things like BIP32 derivations, but I think this gives some
> pretty good properties without needing anything other than good old SHA256.
> >
> > Hope this is useful & wonder if people think something like this would
> be a good idea.
> >
> > -Tadge
> >
> > --
> > You received this message because you are subscribed to the Google
> Groups "Bitcoin Development Mailing List" group.
> > To unsubscribe from this group and stop receiving emails from it, send
> an email to bitcoindev+...@googlegroups•com.
> > To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com
> .
>
>
>
> --
> Best regards,
> Boris Nagaev
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/c8bbcbbb-036b-4e72-9bb5-4490e43dda21n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 23523 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* [bitcoindev] Re: Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-05-28 17:14 [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork Tadge Dryja
2025-05-28 18:20 ` Sergio Demian Lerner
2025-05-28 20:24 ` Nagaev Boris
@ 2025-05-31 16:07 ` waxwing/ AdamISZ
2 siblings, 0 replies; 10+ messages in thread
From: waxwing/ AdamISZ @ 2025-05-31 16:07 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 18777 bytes --]
Hi Tadge, list,
Appreciate this writeup. I found that the discursive detail avoided some
confusions I had with Tim's and Adam's earlier descriptions, though there
are clearly a ton of subtle differences in the various designs.
Anyway, one detail: you have h(pubkey), h(pubkey,txid), txid. You note
earlier that h should be tagged for domain separation purposes. But if you
meant literally the same h for the first two components of the tuple,
there's a flaw, depending on h; length extension attacks could allow the
creation of h(pubkey,txid') without knowing pubkey. I'm going to ignore the
trickier question of whether that matters based on how txid is derived from
a transaction (given txid vs wtxid, I guess it actually really does).
Presumably just use h2 which differs from h, either a different hash or a
different prefix, to avoid this. And/or swapping h(txid,pubkey) etc.
Obviously using h() that is not susceptible to LEA avoids the Q being
raised, but that may be more or less easy in Bitcoin-land.
Cheers,
AdamISZ/waxwing
On Wednesday, May 28, 2025 at 2:28:25 PM UTC-3 Tadge Dryja wrote:
> One of the tricky things about securing Bitcoin against quantum computers
> is: do you even need to? Maybe quantum computers that can break secp256k1
> keys will never exist, in which case we shouldn't waste our time. Or maybe
> they will exist, in not too many years, and we should spend the effort to
> secure the system against QCs.
>
> Since people disagree on how likely QCs are to arrive, and what the timing
> would be if they do, it's hard to get consensus on changes to bitcoin that
> disrupt the properties we use today. For example, a soft fork introducing
> a post-quantum (PQ) signature scheme and at the same time disallowing new
> secp256k1 based outputs would be great for strengthening Bitcoin against an
> oncoming QC. But it would be awful if a QC never appears, or takes decades
> to do so, since secp256k1 is really nice.
>
> So it would be nice to have a way to not deal with this issue until
> *after* the QC shows up. With commit / reveal schemes Bitcoin can keep
> working after a QC shows up, even if we haven't defined a PQ signature
> scheme and everyone's still got P2WPKH outputs.
>
> Most of this is similar to Tim Ruffing's proposal from a few years ago
> here:
> https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/
> <https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/>
>
> The main difference is that this scheme doesn't use encryption, but a
> smaller hash-based commitment, and describes activation as a soft fork.
> I'll define the two types of attacks, a commitment scheme, and then say
> how it can be implemented in bitcoin nodes as a soft fork.
>
> This scheme only works for keys that are pubkey hashes (or script hashes)
> with pubkeys that are unknown to the network. It works with taproot as
> well, but there must be some script-path in the taproot key, as keypath
> spends would no longer be secure.
>
> What to do with all the keys that are known is another issue and
> independent of the scheme in this post (it's compatible with both burning
> them and leaving them to be stolen)
>
> For these schemes, we assume there is an attacker with a QC that can
> compute a quickly compute a private key from any secp256k1 public key. We
> also assume the attacker has some mining power or influence over miners for
> their attacks; maybe not reliably, but they can sometimes get a few blocks
> in a row with the transactions they want.
>
> "Pubkey" can also be substituted with "script" for P2SH and P2WSH output
> types and should work about the same way (with caveats about multisig).
> The equivalent for taproot outputs would be an inner key proving a script
> path.
>
> ## A simple scheme to show an attack
>
> The simplest commit/reveal scheme would be one where after activation, for
> any transaction with an EC signature in it, that transaction's txid must
> appear in a earlier transaction's OP_RETURN output.
>
> When a user wants to spend their coins, they first sign a transaction as
> they would normally, compute the txid, get that txid into an OP_RETURN
> output somehow (paying a miner out of band, etc), then after waiting a
> while, broadcast the transaction. Nodes would check that the txid matches
> a previously seen commitment, and allow the transaction.
>
> One problem with this scheme is that upon seeing the full transaction, the
> attacker can compute the user's private key, and create a new commitment
> with a different txid for a transaction where the attacker gets all the
> coins. If the attacker can get their commitment and spending transaction
> in before the user's transaction, they can steal the coins.
>
> In order to mitigate this problem, a minimum delay can be enforced by
> consensus. A minimum delay of 100 blocks would mean that the attacker
> would have to prevent the user's transaction from being confirmed for 100
> blocks after it showed up in the attacker's mempool. The tradeoff is that
> longer periods give better safety at the cost of more delay in spending.
>
> This scheme, while problematic, is better than nothing! But it's possible
> to remove this timing tradeoff.
>
>
> ## A slightly more complex scheme with (worse) problems
>
> If instead of just the txid, the commitment were both the outpoint being
> spent, and the txid that was going to spend it, we could add a "first seen"
> consensus rule. Only the first commitment pointing to an outpoint works.
>
> So if nodes see two OP_RETURN commitments in their sequence of confirmed
> transactions:
>
> C1 = outpoint1, txid1
> C2 = outpoint1, txid2
>
> They can ignore C2; C1 has already laid claim to outpoint1, and the
> transaction identified by txid1 is the only transaction that can spend
> outpoint1.
>
> If the user manages to get C1 confirmed first, this is great, and
> eliminates the timing problem in the txid only scheme. But this introduces
> a different problem, where an attacker -- in this case any attacker, even
> one without a QC -- who can observe C1 before it is confirmed can flip some
> bits in the txid field, freezing the outpoint forever.
>
> We want to retain the "first seen" rule, but we want to also be able to
> discard invalid commitments. In a bit flipping attack, we could say an
> invalid commitment is one where there is no transaction described by the
> txid. A more general way to classify a commitment as invalid is a
> commitment made without knowledge of the (secret) pubkey. Knowledge of the
> pubkey is what security of coins is now hinging on.
>
>
> The actual commitment scheme
>
>
> We define some hash function h(). We'll use SHA256 for the hashing, but
> it needs to be keyed with some tag, for example "Alas poor Koblitz curve,
> we knew it well".
>
> Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoin
> output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin
> terms, HASH160(pubkey). Due to the hash functions being different, A =
> HASH160(pubkey) and B = h(pubkey) will be completely different, and nobody
> should be able to determine if A and B are hashes of the same pubkey
> without knowing pubkey itself.
>
> An efficient commitment is:
>
> C = h(pubkey), h(pubkey, txid), txid
> (to label things: C = AID, SDP, CTXID)
>
> This commitment includes 3 elements: a different hash of the pubkey which
> will be signed for, a proof of knowledge of the pubkey which commits to a
> transaction, and an the txid of the spending transaction. We'll call these
> "address ID" (AID), sequence dependent proof (SDP), and the commitment txid
> (CTXID).
>
> For those familiar with the proposal by Ruffing, the SDP has a similar
> function to the authenticated encryption part of the encrypted commitment.
> Instead of using authenticated encryption, we can instead just use an
> HMAC-style authentication alone, since the other data, the CTXID, is
> provided.
>
> When the user's wallet creates a transaction, they can feed that
> transaction into a commitment generator function which takes in a
> transaction, extracts the pubkey from the tx, computes the 3 hashes, and
> returns the 3-hash commitment. Once this commitment is confirmed, the user
> broadcasts the transaction.
>
> Nodes verify the commitment by using the same commitment generator
> function and checking if it matches the first valid commitment for that
> AID, in which case the tx is confirmed.
>
> If a node sees multiple commitments all claiming the same AID, it must
> store all of them. Once the AID's pubkey is known, the node can
> distinguish which commitments are valid, which are invalid, and which is
> the first seen valid commitment. Given the pubkey, nodes can determine
> commitments to be invalid by checking if SDP = h(pubkey, CTXID).
>
> As an example, consider a sequence of 3 commitments:
>
> C1 = h(pubkey), h(pubkey', txid1), txid1
> C2 = h(pubkey), h(pubkey, txid2), txid2
> C3 = h(pubkey), h(pubkey, txid3), txid3
>
> The user first creates tx2 and tries to commit C2. But an attacker
> creates C1, committing to a different txid where they control the outputs,
> and confirms it first. This attacker may know the outpoint being spent,
> and may be able to create a transaction and txid that could work. But they
> don't know the pubkey, so while they can copy the AID hash, they have to
> make something up for the SDP.
>
> The user gets C2 confirmed after C1. They then reveal tx2 in the mempool,
> but before it can be confirmed, the attacker gets C3 confirmed. C3 is a
> valid commitment made with knowledge of the pubkey.
>
> Nodes can reject transactions tx1 and tx3. For tx1, they will see that
> the SDP doesn't match the data in the transaction, so it's an invalid
> commitment. For tx3, they will see that it is valid, but by seeing tx3
> they will also be able to determine that C2 is a valid commitment (since
> pubkey is revealed in tx3) which came prior to C3, making C2 the only valid
> commitment for that AID.
>
>
> ## Implementation
>
> Nodes would keep a new key/value store, similar to the existing UTXO set.
> The indexing key would be the AID, and the value would be the set of all
> (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is
> seen in an OP_RETURN, nodes store the commitment.
>
> When a transaction is seen, nodes observe the pubkey used in the
> transaction, and look up if it matches an AID they have stored. If not,
> the transaction is dropped. If the AID does match, the node can now "clean
> out" an AID entry, eliminating all but the first valid commitment, and
> marking that AID as final. If the txid seen matches the remaining
> commitment, the transaction is valid; if not, the transaction is dropped.
>
> After the transaction is confirmed the AID entry can be deleted. Deleting
> the entries frees up space, and would allow another round to happen with
> the same pubkey, which would lead to theft. Retaining the entries takes up
> more space on nodes that can't be pruned, and causes pubkey reuse to
> destroy coins rather than allow them to be stolen. That's a tradeoff, and
> I personally guess it's probably not worth retaining that data but don't
> have a strong opinion either way.
>
> Short commitments:
>
> Since we're not trying to defend against collision attacks, I think all 3
> hashes can be truncated to 16 bytes. The whole commitment could be 48
> bytes long. Without truncation the commitments would be 96 bytes.
>
>
> ## Activation
>
> The activation for the commit/reveal requirement can be triggered by a
> proof of quantum computer (PoQC).
>
> A transaction which successfully spends an output using tapscript:
>
> OP_SHA256 OP_CHECKSIG
>
> is a PoQC in the form of a valid bitcoin transaction. In order to satisfy
> this script, the spending transaction needs to provide 2 data elements: a
> signature, and some data that when hashed results in a pubkey for which
> that signature is valid. If such a pair of data elements exists, it means
> that either SHA256 preimage resistance is broken (which we're assuming
> isn't the case) or someone can create valid signatures for arbitrary
> elliptic curve points, ie a cryptographically relevant quantum computer (or
> any other process which breaks the security of secp256k1 signatures)
>
> Once such a PoQC has been observed in a confirmed transaction, the
> requirements for the 3-hash commitment scheme can be enforced. This is a
> soft fork since the transactions themselves look the same, the only
> requirement is that some OP_RETURN outputs show up earlier. Nodes which
> are not aware of the commitment requirement will still accept all
> transactions with the new rules.
>
> Wallets not aware of the new rules, however, are very dangerous, as they
> may try to broadcast signed transactions without any commitment. Nodes
> that see such a transaction should drop the tx, and if possible tell the
> wallet that they are doing something which is now very dangerous! On the
> open p2p network this is not really enforceable, but people submitting
> transactions to their own node (eg via RPC) can at least get a scary error
> message.
>
>
> ## Issues
>
> My hope is that this scheme would give some peace of mind to people
> holding bitcoin, that in the face of a sudden QC, even with minimal
> preparation their coins can be safe at rest and safely moved. It also
> suggests some best practices for users and wallets to adopt, before any
> software changes: Don't reuse addresses, and if you have taproot outputs,
> include some kind of script path in the outer key.
>
> There are still a number of problems, though!
>
> - Reorgs can steal coins. An attacker that observes a pubkey and can
> reorg back to before the commitment can compute the private key, sign a new
> transaction and get their commitment in first on the new chain. This seems
> unavoidable with commit/reveal schemes, and it's up to the user how long
> they wait between confirming the commitment and revealing the transaction.
>
> - How to get op_returns in
> If there are no PQ signature schemes activated in bitcoin when this
> activates, there's only one type of transaction that can reliably get the
> OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to
> the miners and paying them out of band is not great, but is possible and we
> see this kind of activity today. Users wouldn't need to directly contact
> miners: anyone could aggregate commitments, create a large transaction with
> many OP_RETURN outputs, and then get a miner to commit to that parent
> transaction. Users don't need to worry about committing twice as identical
> commitments would be a no op.
>
> - Spam
> Anyone can make lots of OP_RETURN commitments which are just random
> numbers, forcing nodes to store these commitments in a database. That's
> not great, but isn't much different from how bitcoin works today. If it's
> really a problem, nodes could requiring the commitment outputs to have a
> non-0 amount of bitcoin, imposing a higher cost for the commitments than
> other OP_RETURN outputs.
>
> - Multiple inputs
> If users have received more than one UTXO to the same address, they will
> need to spend all the UTXOs at once. The commitment scheme can deal with
> only the first pubkey seen in the serialized transaction.
>
> - Multisig and Lightning Network
> If your multisig counterparties have a QC, multisig outputs become 1 of N.
> Possibly a more complex commit / reveal scheme could deal with multiple
> keys, but the keys would all have to be hashed with counterparties not
> knowing each others' unhashed pubkeys. This isn't how existing multisig
> outputs work, and in fact the current trend is the opposite with things
> like Musig2, FROST and ROAST. If we're going to need to make new signing
> software and new output types it might make more sense to go for a PQ
> signature scheme.
>
> - Making more p2wpkhs
> You don't have to send to a PQ address type with these transactions -- you
> can send to p2wpkh and do the whole commit/reveal process again when you
> want to spend. This could be helpful if PQ signature schemes are still
> being worked on, or if the PQ schemes are more costly to verify and have
> high fees in comparison to the old p2wpkh output types. It's possible that
> in such a scenario a few high-cost PQ transactions commit to many smaller
> EC transactions. If this actually gets adoption though, we might as well
> drop the EC signatures and just make output scripts into raw hash /
> preimage pairs. It could make sense to cover some non-EC script types with
> the same 3-hash commitment requirement to enable this.
>
> ## Conclusion
>
> This PQ commit / reveal scheme has similar properties to Tim Ruffing's,
> with a smaller commitment that can be done as a soft fork. I hope
> something like this could be soft forked with a PoQC activation trigger, so
> that if a QC never shows up, none of this code gets executed. And people
> who take a couple easy steps like not reusing addresses (which they should
> anyway for privacy reasons) don't have to worry about their coins.
>
> Some of these ideas may have been posted before; I know of the Fawkscoin
> paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent
> discussion which linked to Ruffing's proposal. Here I've tried to show how
> it could be done in a soft fork which doesn't look too bad to implement.
>
> I've also heard of some more complex schemes involving zero knowledge
> proofs, proving things like BIP32 derivations, but I think this gives some
> pretty good properties without needing anything other than good old SHA256.
>
> Hope this is useful & wonder if people think something like this would be
> a good idea.
>
> -Tadge
>
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/6ca6d847-1b15-48fd-89e1-09c4d5e42e38n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 19594 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-05-30 22:00 ` Jonathan Voss
@ 2025-06-02 11:24 ` Peter Todd
2025-06-02 15:50 ` Q C
0 siblings, 1 reply; 10+ messages in thread
From: Peter Todd @ 2025-06-02 11:24 UTC (permalink / raw)
To: Jonathan Voss; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 1217 bytes --]
On Fri, May 30, 2025 at 03:00:41PM -0700, Jonathan Voss wrote:
> As far as I can tell, the main flaw in commit/reveal protocols is in the
> commit phase: if revealing a commitment with N confirmations is required to
> spend bitcoins, then, without spending any bitcoins, how do you get the
> commitment into the blockchain in the first place? Maybe I am just
> misunderstanding this. If so, then a commit/reveal scheme may be a workable
> solution.
You can always purchase new BTC to perform the commitment.
Indeed, this problem is often seen in alt-coins where fees must be paid in a
native asset, while users are trying to send some kind of tokenized asset like
a USD token. You can have funds that you can't move because you don't have the
correct asset. While annoying, this isn't a fatal problem.
--
https://petertodd.org 'peter'[:-1]@petertodd.org
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/aD2J9HNJUqaod0n2%40petertodd.org.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-06-02 11:24 ` Peter Todd
@ 2025-06-02 15:50 ` Q C
0 siblings, 0 replies; 10+ messages in thread
From: Q C @ 2025-06-02 15:50 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 1836 bytes --]
*>>> You can always purchase new BTC to perform the commitment.*Jonathan's
was probably referring to the public-key being exposed when performing the
commitment (since this would defeat the purpose).
From first post from Tadge in this thread, the payment needs to be made out
of band, so the public key isn't exposed during the commitment phase:
>>> get that txid into an OP_RETURN output somehow (paying a miner out of
band, etc)
On Monday, June 2, 2025 at 6:53:55 AM UTC-7 Peter Todd wrote:
> On Fri, May 30, 2025 at 03:00:41PM -0700, Jonathan Voss wrote:
> > As far as I can tell, the main flaw in commit/reveal protocols is in the
> > commit phase: if revealing a commitment with N confirmations is required
> to
> > spend bitcoins, then, without spending any bitcoins, how do you get the
> > commitment into the blockchain in the first place? Maybe I am just
> > misunderstanding this. If so, then a commit/reveal scheme may be a
> workable
> > solution.
>
> You can always purchase new BTC to perform the commitment.
>
> Indeed, this problem is often seen in alt-coins where fees must be paid in
> a
> native asset, while users are trying to send some kind of tokenized asset
> like
> a USD token. You can have funds that you can't move because you don't have
> the
> correct asset. While annoying, this isn't a fatal problem.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/77c90109-6f21-4f92-b122-0a7034fb1a87n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 2879 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-05-28 20:24 ` Nagaev Boris
2025-05-30 22:00 ` Jonathan Voss
@ 2025-06-02 17:38 ` waxwing/ AdamISZ
2025-06-02 19:34 ` 'conduition' via Bitcoin Development Mailing List
2025-06-02 22:50 ` Nagaev Boris
1 sibling, 2 replies; 10+ messages in thread
From: waxwing/ AdamISZ @ 2025-06-02 17:38 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 24767 bytes --]
Hi Boris, list,
> In my scheme, a user creates a QR output that
commits to a hash of a pubkey inside a Taproot leaf. This commitment
is hidden until revealed at spend time. Later, when the user wants to
spend a legacy EC output, they must spend this QR output in the same
transaction, and it must be at least X blocks old.
There's some nuances here that seem quite interesting. If an output commits
(in a quantum-resistant way, i.e. hashing let's say) only to a pubkey, and
not a pubkey plus spending-transaction, then, in the general case, that has
the weakness that the commitment can be replicated, in another commitment
tx, at the time of insertion of commitment into the blockchain; so that if
the tiebreaker is "first commitment in the block(chain)" an attacker can
mess with you. In your case you refer to "a QR output that commits to the
hash of a pubkey inside a taproot leaf" but I'm finding it a tiny bit
unclear what you mean there. Taproot itself isn't quantum resistant (QR),
so Q = P + H(P,S)G is not QR even if P is NUMS. Whereas you might mean:
that same system but with keypath spending invalidated, so it's QR because
of the hash function, but also, the tapleaf contains a QR or PQC signing
scheme in it (I guess this is what you actually mean). Or, you might mean
something that is structurally the same as taproot but not using
secp/BIP340, but instead a PQC scheme with a homomorphism so that that same
design can be reused; call that "taproot2" .. though I don't think I've
heard people talking about that.
Then there's what I think you focus on: the commitment is hidden. To other
readers, in case of confusion: I believe the *real* point here is not
"nobody knows you committed something" though that may be practically
significant, it's instead "nobody knows the exact commitment value (hash)
you used".
So, I believe that's a correct/valid point that actually *doesn't* depend
on which "version" of taproot as per above. Focusing on
current-taproot-but-script-path-only-with-QR-in-tapleaf: we have a
protection that the quantum attacker cannot find the S in the (P,S) tuple
(indeed, they cannot even know the H in P + H(P,S)G). This commitment is
*not* literally perfectly hiding as in a properly formed Pedersen
commitment ([1]) but I do think you have the normal preimage resistance
against revelation as expected even in post-quantum. So that prevents the
"copy the commitment" problem I started out by mentioning. [2]
If "taproot2" instead then we have something for which even the keypath
isn't crackable so I guess it's obvious.
> Since the commitment doesn't include a txid, the user can precommit to
the pubkey hash far in advance, before knowing the details of the
eventual transaction.
Again, I believe you're right here, but we should try to unpack what's
different; because the "reveal" step of commit-reveal is accompanied by the
QR signing event of the pre-existing QR output, we have a sane security
model, so there's no need to commit to the transaction in the preliminary
step, as far as I can tell.
> More efficient use of block space
Makes sense.
I think the only downside I see here is that the initial commitment step
requires the PQC scheme to actually exist. That may not seem like a big
deal, but I have a suspicion it actually will be. I think a protocol in
which we just rely on existing hash primitives and put off the PQC scheme
choosing event may be necessary .. though I could be for sure wrong, in
more than one way, in saying that.
Apart from that point I think this scheme seems good (as you mention, it
has the virtue of not requiring new databases etc which is pretty huge).
Cheers,
AdamISZ/waxwing
[1] In these analyses, I think it's common to overlook a potentially
crucial point: the utxo set is enumerable in practical time, so we must
always remember that we can check our calculations against existing
addresses, even if they are hash-covered keys.
[2] The only caveat is if you're considering the possibility of the
attacker knowing the key in advance of even the commitment step; generally,
that's "game over", but i know that there is some attempt to analyze that
case in some places, too. Not here.
On Wednesday, May 28, 2025 at 6:54:21 PM UTC-3 Nagaev Boris wrote:
> Hi Tadge,
>
> Thanks for writing this up! The proposal is very thoughtful, and it's
> great to see concrete work on post-quantum commit/reveal schemes.
>
> I've been exploring a related approach based on a similar
> commit/reveal idea. In my scheme, a user creates a QR output that
> commits to a hash of a pubkey inside a Taproot leaf. This commitment
> is hidden until revealed at spend time. Later, when the user wants to
> spend a legacy EC output, they must spend this QR output in the same
> transaction, and it must be at least X blocks old.
>
> https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ
>
> This approach has a few potential advantages:
>
> 1. No need for nodes to track a new commitment store
>
> Because the commitment remains hidden in a Tapleaf until the spend,
> observers (including attackers) don't see it, and nodes don't need to
> store or validate any external commitment set. The only requirement is
> that the QR output must be old enough, and Bitcoin Core already tracks
> coin age, which is needed to validate existing consensus rules.
>
> 2. Commitment can be made before the transaction is known
>
> Since the commitment doesn't include a txid, the user can precommit to
> the pubkey hash far in advance, before knowing the details of the
> eventual transaction. This allows greater flexibility: you can delay
> choosing outputs, fee rates, etc., until spend time. Only knowledge of
> the EC pubkey needs to be proven when creating the QR output.
>
> 3. More efficient use of block space
>
> Multiple EC coins can be spent together with a single QR output,
> holding EC pubkey commitments in Taproot leaves. If EC coins share the
> same EC pubkey (e.g., come from the same address), they can reuse the
> same commitment.
>
> Would love to hear your thoughts on this variant. I think this one
> might be a simpler, lower-overhead option for protecting EC outputs
> post-QC.
>
> Best,
> Boris
>
> On Wed, May 28, 2025 at 2:28 PM Tadge Dryja <r...@awsomnet•org> wrote:
> >
> > One of the tricky things about securing Bitcoin against quantum
> computers is: do you even need to? Maybe quantum computers that can break
> secp256k1 keys will never exist, in which case we shouldn't waste our time.
> Or maybe they will exist, in not too many years, and we should spend the
> effort to secure the system against QCs.
> >
> > Since people disagree on how likely QCs are to arrive, and what the
> timing would be if they do, it's hard to get consensus on changes to
> bitcoin that disrupt the properties we use today. For example, a soft fork
> introducing a post-quantum (PQ) signature scheme and at the same time
> disallowing new secp256k1 based outputs would be great for strengthening
> Bitcoin against an oncoming QC. But it would be awful if a QC never
> appears, or takes decades to do so, since secp256k1 is really nice.
> >
> > So it would be nice to have a way to not deal with this issue until
> *after* the QC shows up. With commit / reveal schemes Bitcoin can keep
> working after a QC shows up, even if we haven't defined a PQ signature
> scheme and everyone's still got P2WPKH outputs.
> >
> > Most of this is similar to Tim Ruffing's proposal from a few years ago
> here:
> > https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/
> <https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/>
> >
> > The main difference is that this scheme doesn't use encryption, but a
> smaller hash-based commitment, and describes activation as a soft fork.
> I'll define the two types of attacks, a commitment scheme, and then say how
> it can be implemented in bitcoin nodes as a soft fork.
> >
> > This scheme only works for keys that are pubkey hashes (or script
> hashes) with pubkeys that are unknown to the network. It works with taproot
> as well, but there must be some script-path in the taproot key, as keypath
> spends would no longer be secure.
> >
> > What to do with all the keys that are known is another issue and
> independent of the scheme in this post (it's compatible with both burning
> them and leaving them to be stolen)
> >
> > For these schemes, we assume there is an attacker with a QC that can
> compute a quickly compute a private key from any secp256k1 public key. We
> also assume the attacker has some mining power or influence over miners for
> their attacks; maybe not reliably, but they can sometimes get a few blocks
> in a row with the transactions they want.
> >
> > "Pubkey" can also be substituted with "script" for P2SH and P2WSH output
> types and should work about the same way (with caveats about multisig). The
> equivalent for taproot outputs would be an inner key proving a script path.
> >
> > ## A simple scheme to show an attack
> >
> > The simplest commit/reveal scheme would be one where after activation,
> for any transaction with an EC signature in it, that transaction's txid
> must appear in a earlier transaction's OP_RETURN output.
> >
> > When a user wants to spend their coins, they first sign a transaction as
> they would normally, compute the txid, get that txid into an OP_RETURN
> output somehow (paying a miner out of band, etc), then after waiting a
> while, broadcast the transaction. Nodes would check that the txid matches a
> previously seen commitment, and allow the transaction.
> >
> > One problem with this scheme is that upon seeing the full transaction,
> the attacker can compute the user's private key, and create a new
> commitment with a different txid for a transaction where the attacker gets
> all the coins. If the attacker can get their commitment and spending
> transaction in before the user's transaction, they can steal the coins.
> >
> > In order to mitigate this problem, a minimum delay can be enforced by
> consensus. A minimum delay of 100 blocks would mean that the attacker would
> have to prevent the user's transaction from being confirmed for 100 blocks
> after it showed up in the attacker's mempool. The tradeoff is that longer
> periods give better safety at the cost of more delay in spending.
> >
> > This scheme, while problematic, is better than nothing! But it's
> possible to remove this timing tradeoff.
> >
> >
> > ## A slightly more complex scheme with (worse) problems
> >
> > If instead of just the txid, the commitment were both the outpoint being
> spent, and the txid that was going to spend it, we could add a "first seen"
> consensus rule. Only the first commitment pointing to an outpoint works.
> >
> > So if nodes see two OP_RETURN commitments in their sequence of confirmed
> transactions:
> >
> > C1 = outpoint1, txid1
> > C2 = outpoint1, txid2
> >
> > They can ignore C2; C1 has already laid claim to outpoint1, and the
> transaction identified by txid1 is the only transaction that can spend
> outpoint1.
> >
> > If the user manages to get C1 confirmed first, this is great, and
> eliminates the timing problem in the txid only scheme. But this introduces
> a different problem, where an attacker -- in this case any attacker, even
> one without a QC -- who can observe C1 before it is confirmed can flip some
> bits in the txid field, freezing the outpoint forever.
> >
> > We want to retain the "first seen" rule, but we want to also be able to
> discard invalid commitments. In a bit flipping attack, we could say an
> invalid commitment is one where there is no transaction described by the
> txid. A more general way to classify a commitment as invalid is a
> commitment made without knowledge of the (secret) pubkey. Knowledge of the
> pubkey is what security of coins is now hinging on.
> >
> >
> > The actual commitment scheme
> >
> >
> > We define some hash function h(). We'll use SHA256 for the hashing, but
> it needs to be keyed with some tag, for example "Alas poor Koblitz curve,
> we knew it well".
> >
> > Thus h(pubkey) is not equal to the pubkey hash already used in the
> bitcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in
> bitcoin terms, HASH160(pubkey). Due to the hash functions being different,
> A = HASH160(pubkey) and B = h(pubkey) will be completely different, and
> nobody should be able to determine if A and B are hashes of the same pubkey
> without knowing pubkey itself.
> >
> > An efficient commitment is:
> >
> > C = h(pubkey), h(pubkey, txid), txid
> > (to label things: C = AID, SDP, CTXID)
> >
> > This commitment includes 3 elements: a different hash of the pubkey
> which will be signed for, a proof of knowledge of the pubkey which commits
> to a transaction, and an the txid of the spending transaction. We'll call
> these "address ID" (AID), sequence dependent proof (SDP), and the
> commitment txid (CTXID).
> >
> > For those familiar with the proposal by Ruffing, the SDP has a similar
> function to the authenticated encryption part of the encrypted commitment.
> Instead of using authenticated encryption, we can instead just use an
> HMAC-style authentication alone, since the other data, the CTXID, is
> provided.
> >
> > When the user's wallet creates a transaction, they can feed that
> transaction into a commitment generator function which takes in a
> transaction, extracts the pubkey from the tx, computes the 3 hashes, and
> returns the 3-hash commitment. Once this commitment is confirmed, the user
> broadcasts the transaction.
> >
> > Nodes verify the commitment by using the same commitment generator
> function and checking if it matches the first valid commitment for that
> AID, in which case the tx is confirmed.
> >
> > If a node sees multiple commitments all claiming the same AID, it must
> store all of them. Once the AID's pubkey is known, the node can distinguish
> which commitments are valid, which are invalid, and which is the first seen
> valid commitment. Given the pubkey, nodes can determine commitments to be
> invalid by checking if SDP = h(pubkey, CTXID).
> >
> > As an example, consider a sequence of 3 commitments:
> >
> > C1 = h(pubkey), h(pubkey', txid1), txid1
> > C2 = h(pubkey), h(pubkey, txid2), txid2
> > C3 = h(pubkey), h(pubkey, txid3), txid3
> >
> > The user first creates tx2 and tries to commit C2. But an attacker
> creates C1, committing to a different txid where they control the outputs,
> and confirms it first. This attacker may know the outpoint being spent, and
> may be able to create a transaction and txid that could work. But they
> don't know the pubkey, so while they can copy the AID hash, they have to
> make something up for the SDP.
> >
> > The user gets C2 confirmed after C1. They then reveal tx2 in the
> mempool, but before it can be confirmed, the attacker gets C3 confirmed. C3
> is a valid commitment made with knowledge of the pubkey.
> >
> > Nodes can reject transactions tx1 and tx3. For tx1, they will see that
> the SDP doesn't match the data in the transaction, so it's an invalid
> commitment. For tx3, they will see that it is valid, but by seeing tx3 they
> will also be able to determine that C2 is a valid commitment (since pubkey
> is revealed in tx3) which came prior to C3, making C2 the only valid
> commitment for that AID.
> >
> >
> > ## Implementation
> >
> > Nodes would keep a new key/value store, similar to the existing UTXO
> set. The indexing key would be the AID, and the value would be the set of
> all (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is
> seen in an OP_RETURN, nodes store the commitment.
> >
> > When a transaction is seen, nodes observe the pubkey used in the
> transaction, and look up if it matches an AID they have stored. If not, the
> transaction is dropped. If the AID does match, the node can now "clean out"
> an AID entry, eliminating all but the first valid commitment, and marking
> that AID as final. If the txid seen matches the remaining commitment, the
> transaction is valid; if not, the transaction is dropped.
> >
> > After the transaction is confirmed the AID entry can be deleted.
> Deleting the entries frees up space, and would allow another round to
> happen with the same pubkey, which would lead to theft. Retaining the
> entries takes up more space on nodes that can't be pruned, and causes
> pubkey reuse to destroy coins rather than allow them to be stolen. That's a
> tradeoff, and I personally guess it's probably not worth retaining that
> data but don't have a strong opinion either way.
> >
> > Short commitments:
> >
> > Since we're not trying to defend against collision attacks, I think all
> 3 hashes can be truncated to 16 bytes. The whole commitment could be 48
> bytes long. Without truncation the commitments would be 96 bytes.
> >
> >
> > ## Activation
> >
> > The activation for the commit/reveal requirement can be triggered by a
> proof of quantum computer (PoQC).
> >
> > A transaction which successfully spends an output using tapscript:
> >
> > OP_SHA256 OP_CHECKSIG
> >
> > is a PoQC in the form of a valid bitcoin transaction. In order to
> satisfy this script, the spending transaction needs to provide 2 data
> elements: a signature, and some data that when hashed results in a pubkey
> for which that signature is valid. If such a pair of data elements exists,
> it means that either SHA256 preimage resistance is broken (which we're
> assuming isn't the case) or someone can create valid signatures for
> arbitrary elliptic curve points, ie a cryptographically relevant quantum
> computer (or any other process which breaks the security of secp256k1
> signatures)
> >
> > Once such a PoQC has been observed in a confirmed transaction, the
> requirements for the 3-hash commitment scheme can be enforced. This is a
> soft fork since the transactions themselves look the same, the only
> requirement is that some OP_RETURN outputs show up earlier. Nodes which are
> not aware of the commitment requirement will still accept all transactions
> with the new rules.
> >
> > Wallets not aware of the new rules, however, are very dangerous, as they
> may try to broadcast signed transactions without any commitment. Nodes that
> see such a transaction should drop the tx, and if possible tell the wallet
> that they are doing something which is now very dangerous! On the open p2p
> network this is not really enforceable, but people submitting transactions
> to their own node (eg via RPC) can at least get a scary error message.
> >
> >
> > ## Issues
> >
> > My hope is that this scheme would give some peace of mind to people
> holding bitcoin, that in the face of a sudden QC, even with minimal
> preparation their coins can be safe at rest and safely moved. It also
> suggests some best practices for users and wallets to adopt, before any
> software changes: Don't reuse addresses, and if you have taproot outputs,
> include some kind of script path in the outer key.
> >
> > There are still a number of problems, though!
> >
> > - Reorgs can steal coins. An attacker that observes a pubkey and can
> reorg back to before the commitment can compute the private key, sign a new
> transaction and get their commitment in first on the new chain. This seems
> unavoidable with commit/reveal schemes, and it's up to the user how long
> they wait between confirming the commitment and revealing the transaction.
> >
> > - How to get op_returns in
> > If there are no PQ signature schemes activated in bitcoin when this
> activates, there's only one type of transaction that can reliably get the
> OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to
> the miners and paying them out of band is not great, but is possible and we
> see this kind of activity today. Users wouldn't need to directly contact
> miners: anyone could aggregate commitments, create a large transaction with
> many OP_RETURN outputs, and then get a miner to commit to that parent
> transaction. Users don't need to worry about committing twice as identical
> commitments would be a no op.
> >
> > - Spam
> > Anyone can make lots of OP_RETURN commitments which are just random
> numbers, forcing nodes to store these commitments in a database. That's not
> great, but isn't much different from how bitcoin works today. If it's
> really a problem, nodes could requiring the commitment outputs to have a
> non-0 amount of bitcoin, imposing a higher cost for the commitments than
> other OP_RETURN outputs.
> >
> > - Multiple inputs
> > If users have received more than one UTXO to the same address, they will
> need to spend all the UTXOs at once. The commitment scheme can deal with
> only the first pubkey seen in the serialized transaction.
> >
> > - Multisig and Lightning Network
> > If your multisig counterparties have a QC, multisig outputs become 1 of
> N. Possibly a more complex commit / reveal scheme could deal with multiple
> keys, but the keys would all have to be hashed with counterparties not
> knowing each others' unhashed pubkeys. This isn't how existing multisig
> outputs work, and in fact the current trend is the opposite with things
> like Musig2, FROST and ROAST. If we're going to need to make new signing
> software and new output types it might make more sense to go for a PQ
> signature scheme.
> >
> > - Making more p2wpkhs
> > You don't have to send to a PQ address type with these transactions --
> you can send to p2wpkh and do the whole commit/reveal process again when
> you want to spend. This could be helpful if PQ signature schemes are still
> being worked on, or if the PQ schemes are more costly to verify and have
> high fees in comparison to the old p2wpkh output types. It's possible that
> in such a scenario a few high-cost PQ transactions commit to many smaller
> EC transactions. If this actually gets adoption though, we might as well
> drop the EC signatures and just make output scripts into raw hash /
> preimage pairs. It could make sense to cover some non-EC script types with
> the same 3-hash commitment requirement to enable this.
> >
> > ## Conclusion
> >
> > This PQ commit / reveal scheme has similar properties to Tim Ruffing's,
> with a smaller commitment that can be done as a soft fork. I hope something
> like this could be soft forked with a PoQC activation trigger, so that if a
> QC never shows up, none of this code gets executed. And people who take a
> couple easy steps like not reusing addresses (which they should anyway for
> privacy reasons) don't have to worry about their coins.
> >
> > Some of these ideas may have been posted before; I know of the Fawkscoin
> paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent
> discussion which linked to Ruffing's proposal. Here I've tried to show how
> it could be done in a soft fork which doesn't look too bad to implement.
> >
> > I've also heard of some more complex schemes involving zero knowledge
> proofs, proving things like BIP32 derivations, but I think this gives some
> pretty good properties without needing anything other than good old SHA256.
> >
> > Hope this is useful & wonder if people think something like this would
> be a good idea.
> >
> > -Tadge
> >
> > --
> > You received this message because you are subscribed to the Google
> Groups "Bitcoin Development Mailing List" group.
> > To unsubscribe from this group and stop receiving emails from it, send
> an email to bitcoindev+...@googlegroups•com.
> > To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com
> .
>
>
>
> --
> Best regards,
> Boris Nagaev
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/402db6ba-2497-4aab-9f84-0d66b4b8efccn%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 27429 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-06-02 17:38 ` waxwing/ AdamISZ
@ 2025-06-02 19:34 ` 'conduition' via Bitcoin Development Mailing List
2025-06-02 22:50 ` Nagaev Boris
1 sibling, 0 replies; 10+ messages in thread
From: 'conduition' via Bitcoin Development Mailing List @ 2025-06-02 19:34 UTC (permalink / raw)
To: waxwing/ AdamISZ; +Cc: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 27308 bytes --]
Hi list,
One problem I see with Tadge's commit/reveal approach is that verifying
nodes must have an ordering over ALL commitments, including those which
haven't yet been opened. We need every commitment to be visible on-chain
to know if a different commitment for the same pubkey was published
earlier.
This prevents commitment aggregation, and it means we would need one
OP_RETURN output to publish a commitment for every legacy UTXO rescued
by Tadge's protocol.
Let me demonstrate by trying to scale Tadge's proposal with aggregated
commitments. For instance, instead of directly publishing
C = (AID, SDP, CTXID) in an OP_RETURN, we might publish a merkle tree
root which is derived from a list of such commitments. Nodes store all
such merkle roots in a DB. When spending an EC UTXO, we reveal the
pubkey along with a merkle proof for the commitment. The node computes
the merkle root from the proof+pubkey+TXID, and then checks the
database to verify the commitment is sufficiently old.
This won't be secure though. The verifying nodes have no way of
checking if this specific commitment was the FIRST valid commitment
for the relevant pubkey/AID. There might be another commitment hidden
in the same merkle tree, or in an earlier one.
Maybe someone else has a better way to scale this commit/reveal protocol,
but unless that's possible, I think Martin's idea [0] has better potential
because we can rescue multiple EC outputs at once with a single
quantum-resistant UTXO.
As waxwing noted though, we need to better define the commitment protocol
there, including whether to use a post-quantum taproot-like construction,
or an inscription-like envelope with P2SH and a post-quantum checksig
opcode. I'd suggest we move further discussion on that to the relevant
thread [0].
[0]: https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/qN-pAMS7AgAJ
I do recognize that Tadge's proposal has the advantage of not needing any
quantum-resistant signing algos, which won't be available on BTC for a
long time... but if we don't have a QR signing algo, then where are
you even trying to move your coins to? I agree with waxwing that we
should not pin down our PQ signing algo yet, but we should assume one will
eventually be available. Otherwise why should we bother at all.
regards,
conduition
On Monday, June 2nd, 2025 at 2:41 PM, waxwing/ AdamISZ <ekaggata@gmail•com> wrote:
> Hi Boris, list,
>
> > In my scheme, a user creates a QR output that
> commits to a hash of a pubkey inside a Taproot leaf. This commitment
> is hidden until revealed at spend time. Later, when the user wants to
> spend a legacy EC output, they must spend this QR output in the same
> transaction, and it must be at least X blocks old.
>
> There's some nuances here that seem quite interesting. If an output commits (in a quantum-resistant way, i.e. hashing let's say) only to a pubkey, and not a pubkey plus spending-transaction, then, in the general case, that has the weakness that the commitment can be replicated, in another commitment tx, at the time of insertion of commitment into the blockchain; so that if the tiebreaker is "first commitment in the block(chain)" an attacker can mess with you. In your case you refer to "a QR output that commits to the hash of a pubkey inside a taproot leaf" but I'm finding it a tiny bit unclear what you mean there. Taproot itself isn't quantum resistant (QR), so Q = P + H(P,S)G is not QR even if P is NUMS. Whereas you might mean: that same system but with keypath spending invalidated, so it's QR because of the hash function, but also, the tapleaf contains a QR or PQC signing scheme in it (I guess this is what you actually mean). Or, you might mean something that is structurally the same as taproot but not using secp/BIP340, but instead a PQC scheme with a homomorphism so that that same design can be reused; call that "taproot2" .. though I don't think I've heard people talking about that.
>
> Then there's what I think you focus on: the commitment is hidden. To other readers, in case of confusion: I believe the *real* point here is not "nobody knows you committed something" though that may be practically significant, it's instead "nobody knows the exact commitment value (hash) you used".
>
> So, I believe that's a correct/valid point that actually *doesn't* depend on which "version" of taproot as per above. Focusing on current-taproot-but-script-path-only-with-QR-in-tapleaf: we have a protection that the quantum attacker cannot find the S in the (P,S) tuple (indeed, they cannot even know the H in P + H(P,S)G). This commitment is *not* literally perfectly hiding as in a properly formed Pedersen commitment ([1]) but I do think you have the normal preimage resistance against revelation as expected even in post-quantum. So that prevents the "copy the commitment" problem I started out by mentioning. [2]
>
> If "taproot2" instead then we have something for which even the keypath isn't crackable so I guess it's obvious.
>
> > Since the commitment doesn't include a txid, the user can precommit to
> the pubkey hash far in advance, before knowing the details of the
> eventual transaction.
>
> Again, I believe you're right here, but we should try to unpack what's different; because the "reveal" step of commit-reveal is accompanied by the QR signing event of the pre-existing QR output, we have a sane security model, so there's no need to commit to the transaction in the preliminary step, as far as I can tell.
>
> > More efficient use of block space
>
> Makes sense.
>
> I think the only downside I see here is that the initial commitment step requires the PQC scheme to actually exist. That may not seem like a big deal, but I have a suspicion it actually will be. I think a protocol in which we just rely on existing hash primitives and put off the PQC scheme choosing event may be necessary .. though I could be for sure wrong, in more than one way, in saying that.
>
> Apart from that point I think this scheme seems good (as you mention, it has the virtue of not requiring new databases etc which is pretty huge).
>
> Cheers,
> AdamISZ/waxwing
>
> [1] In these analyses, I think it's common to overlook a potentially crucial point: the utxo set is enumerable in practical time, so we must always remember that we can check our calculations against existing addresses, even if they are hash-covered keys.
>
> [2] The only caveat is if you're considering the possibility of the attacker knowing the key in advance of even the commitment step; generally, that's "game over", but i know that there is some attempt to analyze that case in some places, too. Not here.
>
> On Wednesday, May 28, 2025 at 6:54:21 PM UTC-3 Nagaev Boris wrote:
>
> > Hi Tadge,
> >
> > Thanks for writing this up! The proposal is very thoughtful, and it's
> > great to see concrete work on post-quantum commit/reveal schemes.
> >
> > I've been exploring a related approach based on a similar
> > commit/reveal idea. In my scheme, a user creates a QR output that
> > commits to a hash of a pubkey inside a Taproot leaf. This commitment
> > is hidden until revealed at spend time. Later, when the user wants to
> > spend a legacy EC output, they must spend this QR output in the same
> > transaction, and it must be at least X blocks old.
> >
> > https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ
> >
> > This approach has a few potential advantages:
> >
> > 1. No need for nodes to track a new commitment store
> >
> > Because the commitment remains hidden in a Tapleaf until the spend,
> > observers (including attackers) don't see it, and nodes don't need to
> > store or validate any external commitment set. The only requirement is
> > that the QR output must be old enough, and Bitcoin Core already tracks
> > coin age, which is needed to validate existing consensus rules.
> >
> > 2. Commitment can be made before the transaction is known
> >
> > Since the commitment doesn't include a txid, the user can precommit to
> > the pubkey hash far in advance, before knowing the details of the
> > eventual transaction. This allows greater flexibility: you can delay
> > choosing outputs, fee rates, etc., until spend time. Only knowledge of
> > the EC pubkey needs to be proven when creating the QR output.
> >
> > 3. More efficient use of block space
> >
> > Multiple EC coins can be spent together with a single QR output,
> > holding EC pubkey commitments in Taproot leaves. If EC coins share the
> > same EC pubkey (e.g., come from the same address), they can reuse the
> > same commitment.
> >
> > Would love to hear your thoughts on this variant. I think this one
> > might be a simpler, lower-overhead option for protecting EC outputs
> > post-QC.
> >
> > Best,
> > Boris
> >
> > On Wed, May 28, 2025 at 2:28 PM Tadge Dryja <r...@awsomnet•org> wrote:
> > >
> > > One of the tricky things about securing Bitcoin against quantum computers is: do you even need to? Maybe quantum computers that can break secp256k1 keys will never exist, in which case we shouldn't waste our time. Or maybe they will exist, in not too many years, and we should spend the effort to secure the system against QCs.
> > >
> > > Since people disagree on how likely QCs are to arrive, and what the timing would be if they do, it's hard to get consensus on changes to bitcoin that disrupt the properties we use today. For example, a soft fork introducing a post-quantum (PQ) signature scheme and at the same time disallowing new secp256k1 based outputs would be great for strengthening Bitcoin against an oncoming QC. But it would be awful if a QC never appears, or takes decades to do so, since secp256k1 is really nice.
> > >
> > > So it would be nice to have a way to not deal with this issue until *after* the QC shows up. With commit / reveal schemes Bitcoin can keep working after a QC shows up, even if we haven't defined a PQ signature scheme and everyone's still got P2WPKH outputs.
> > >
> > > Most of this is similar to Tim Ruffing's proposal from a few years ago here:
> > > https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/
> > >
> > > The main difference is that this scheme doesn't use encryption, but a smaller hash-based commitment, and describes activation as a soft fork. I'll define the two types of attacks, a commitment scheme, and then say how it can be implemented in bitcoin nodes as a soft fork.
> > >
> > > This scheme only works for keys that are pubkey hashes (or script hashes) with pubkeys that are unknown to the network. It works with taproot as well, but there must be some script-path in the taproot key, as keypath spends would no longer be secure.
> > >
> > > What to do with all the keys that are known is another issue and independent of the scheme in this post (it's compatible with both burning them and leaving them to be stolen)
> > >
> > > For these schemes, we assume there is an attacker with a QC that can compute a quickly compute a private key from any secp256k1 public key. We also assume the attacker has some mining power or influence over miners for their attacks; maybe not reliably, but they can sometimes get a few blocks in a row with the transactions they want.
> > >
> > > "Pubkey" can also be substituted with "script" for P2SH and P2WSH output types and should work about the same way (with caveats about multisig). The equivalent for taproot outputs would be an inner key proving a script path.
> > >
> > > ## A simple scheme to show an attack
> > >
> > > The simplest commit/reveal scheme would be one where after activation, for any transaction with an EC signature in it, that transaction's txid must appear in a earlier transaction's OP_RETURN output.
> > >
> > > When a user wants to spend their coins, they first sign a transaction as they would normally, compute the txid, get that txid into an OP_RETURN output somehow (paying a miner out of band, etc), then after waiting a while, broadcast the transaction. Nodes would check that the txid matches a previously seen commitment, and allow the transaction.
> > >
> > > One problem with this scheme is that upon seeing the full transaction, the attacker can compute the user's private key, and create a new commitment with a different txid for a transaction where the attacker gets all the coins. If the attacker can get their commitment and spending transaction in before the user's transaction, they can steal the coins.
> > >
> > > In order to mitigate this problem, a minimum delay can be enforced by consensus. A minimum delay of 100 blocks would mean that the attacker would have to prevent the user's transaction from being confirmed for 100 blocks after it showed up in the attacker's mempool. The tradeoff is that longer periods give better safety at the cost of more delay in spending.
> > >
> > > This scheme, while problematic, is better than nothing! But it's possible to remove this timing tradeoff.
> > >
> > >
> > > ## A slightly more complex scheme with (worse) problems
> > >
> > > If instead of just the txid, the commitment were both the outpoint being spent, and the txid that was going to spend it, we could add a "first seen" consensus rule. Only the first commitment pointing to an outpoint works.
> > >
> > > So if nodes see two OP_RETURN commitments in their sequence of confirmed transactions:
> > >
> > > C1 = outpoint1, txid1
> > > C2 = outpoint1, txid2
> > >
> > > They can ignore C2; C1 has already laid claim to outpoint1, and the transaction identified by txid1 is the only transaction that can spend outpoint1.
> > >
> > > If the user manages to get C1 confirmed first, this is great, and eliminates the timing problem in the txid only scheme. But this introduces a different problem, where an attacker -- in this case any attacker, even one without a QC -- who can observe C1 before it is confirmed can flip some bits in the txid field, freezing the outpoint forever.
> > >
> > > We want to retain the "first seen" rule, but we want to also be able to discard invalid commitments. In a bit flipping attack, we could say an invalid commitment is one where there is no transaction described by the txid. A more general way to classify a commitment as invalid is a commitment made without knowledge of the (secret) pubkey. Knowledge of the pubkey is what security of coins is now hinging on.
> > >
> > >
> > > The actual commitment scheme
> > >
> > >
> > > We define some hash function h(). We'll use SHA256 for the hashing, but it needs to be keyed with some tag, for example "Alas poor Koblitz curve, we knew it well".
> > >
> > > Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin terms, HASH160(pubkey). Due to the hash functions being different, A = HASH160(pubkey) and B = h(pubkey) will be completely different, and nobody should be able to determine if A and B are hashes of the same pubkey without knowing pubkey itself.
> > >
> > > An efficient commitment is:
> > >
> > > C = h(pubkey), h(pubkey, txid), txid
> > > (to label things: C = AID, SDP, CTXID)
> > >
> > > This commitment includes 3 elements: a different hash of the pubkey which will be signed for, a proof of knowledge of the pubkey which commits to a transaction, and an the txid of the spending transaction. We'll call these "address ID" (AID), sequence dependent proof (SDP), and the commitment txid (CTXID).
> > >
> > > For those familiar with the proposal by Ruffing, the SDP has a similar function to the authenticated encryption part of the encrypted commitment. Instead of using authenticated encryption, we can instead just use an HMAC-style authentication alone, since the other data, the CTXID, is provided.
> > >
> > > When the user's wallet creates a transaction, they can feed that transaction into a commitment generator function which takes in a transaction, extracts the pubkey from the tx, computes the 3 hashes, and returns the 3-hash commitment. Once this commitment is confirmed, the user broadcasts the transaction.
> > >
> > > Nodes verify the commitment by using the same commitment generator function and checking if it matches the first valid commitment for that AID, in which case the tx is confirmed.
> > >
> > > If a node sees multiple commitments all claiming the same AID, it must store all of them. Once the AID's pubkey is known, the node can distinguish which commitments are valid, which are invalid, and which is the first seen valid commitment. Given the pubkey, nodes can determine commitments to be invalid by checking if SDP = h(pubkey, CTXID).
> > >
> > > As an example, consider a sequence of 3 commitments:
> > >
> > > C1 = h(pubkey), h(pubkey', txid1), txid1
> > > C2 = h(pubkey), h(pubkey, txid2), txid2
> > > C3 = h(pubkey), h(pubkey, txid3), txid3
> > >
> > > The user first creates tx2 and tries to commit C2. But an attacker creates C1, committing to a different txid where they control the outputs, and confirms it first. This attacker may know the outpoint being spent, and may be able to create a transaction and txid that could work. But they don't know the pubkey, so while they can copy the AID hash, they have to make something up for the SDP.
> > >
> > > The user gets C2 confirmed after C1. They then reveal tx2 in the mempool, but before it can be confirmed, the attacker gets C3 confirmed. C3 is a valid commitment made with knowledge of the pubkey.
> > >
> > > Nodes can reject transactions tx1 and tx3. For tx1, they will see that the SDP doesn't match the data in the transaction, so it's an invalid commitment. For tx3, they will see that it is valid, but by seeing tx3 they will also be able to determine that C2 is a valid commitment (since pubkey is revealed in tx3) which came prior to C3, making C2 the only valid commitment for that AID.
> > >
> > >
> > > ## Implementation
> > >
> > > Nodes would keep a new key/value store, similar to the existing UTXO set. The indexing key would be the AID, and the value would be the set of all (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is seen in an OP_RETURN, nodes store the commitment.
> > >
> > > When a transaction is seen, nodes observe the pubkey used in the transaction, and look up if it matches an AID they have stored. If not, the transaction is dropped. If the AID does match, the node can now "clean out" an AID entry, eliminating all but the first valid commitment, and marking that AID as final. If the txid seen matches the remaining commitment, the transaction is valid; if not, the transaction is dropped.
> > >
> > > After the transaction is confirmed the AID entry can be deleted. Deleting the entries frees up space, and would allow another round to happen with the same pubkey, which would lead to theft. Retaining the entries takes up more space on nodes that can't be pruned, and causes pubkey reuse to destroy coins rather than allow them to be stolen. That's a tradeoff, and I personally guess it's probably not worth retaining that data but don't have a strong opinion either way.
> > >
> > > Short commitments:
> > >
> > > Since we're not trying to defend against collision attacks, I think all 3 hashes can be truncated to 16 bytes. The whole commitment could be 48 bytes long. Without truncation the commitments would be 96 bytes.
> > >
> > >
> > > ## Activation
> > >
> > > The activation for the commit/reveal requirement can be triggered by a proof of quantum computer (PoQC).
> > >
> > > A transaction which successfully spends an output using tapscript:
> > >
> > > OP_SHA256 OP_CHECKSIG
> > >
> > > is a PoQC in the form of a valid bitcoin transaction. In order to satisfy this script, the spending transaction needs to provide 2 data elements: a signature, and some data that when hashed results in a pubkey for which that signature is valid. If such a pair of data elements exists, it means that either SHA256 preimage resistance is broken (which we're assuming isn't the case) or someone can create valid signatures for arbitrary elliptic curve points, ie a cryptographically relevant quantum computer (or any other process which breaks the security of secp256k1 signatures)
> > >
> > > Once such a PoQC has been observed in a confirmed transaction, the requirements for the 3-hash commitment scheme can be enforced. This is a soft fork since the transactions themselves look the same, the only requirement is that some OP_RETURN outputs show up earlier. Nodes which are not aware of the commitment requirement will still accept all transactions with the new rules.
> > >
> > > Wallets not aware of the new rules, however, are very dangerous, as they may try to broadcast signed transactions without any commitment. Nodes that see such a transaction should drop the tx, and if possible tell the wallet that they are doing something which is now very dangerous! On the open p2p network this is not really enforceable, but people submitting transactions to their own node (eg via RPC) can at least get a scary error message.
> > >
> > >
> > > ## Issues
> > >
> > > My hope is that this scheme would give some peace of mind to people holding bitcoin, that in the face of a sudden QC, even with minimal preparation their coins can be safe at rest and safely moved. It also suggests some best practices for users and wallets to adopt, before any software changes: Don't reuse addresses, and if you have taproot outputs, include some kind of script path in the outer key.
> > >
> > > There are still a number of problems, though!
> > >
> > > - Reorgs can steal coins. An attacker that observes a pubkey and can reorg back to before the commitment can compute the private key, sign a new transaction and get their commitment in first on the new chain. This seems unavoidable with commit/reveal schemes, and it's up to the user how long they wait between confirming the commitment and revealing the transaction.
> > >
> > > - How to get op_returns in
> > > If there are no PQ signature schemes activated in bitcoin when this activates, there's only one type of transaction that can reliably get the OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to the miners and paying them out of band is not great, but is possible and we see this kind of activity today. Users wouldn't need to directly contact miners: anyone could aggregate commitments, create a large transaction with many OP_RETURN outputs, and then get a miner to commit to that parent transaction. Users don't need to worry about committing twice as identical commitments would be a no op.
> > >
> > > - Spam
> > > Anyone can make lots of OP_RETURN commitments which are just random numbers, forcing nodes to store these commitments in a database. That's not great, but isn't much different from how bitcoin works today. If it's really a problem, nodes could requiring the commitment outputs to have a non-0 amount of bitcoin, imposing a higher cost for the commitments than other OP_RETURN outputs.
> > >
> > > - Multiple inputs
> > > If users have received more than one UTXO to the same address, they will need to spend all the UTXOs at once. The commitment scheme can deal with only the first pubkey seen in the serialized transaction.
> > >
> > > - Multisig and Lightning Network
> > > If your multisig counterparties have a QC, multisig outputs become 1 of N. Possibly a more complex commit / reveal scheme could deal with multiple keys, but the keys would all have to be hashed with counterparties not knowing each others' unhashed pubkeys. This isn't how existing multisig outputs work, and in fact the current trend is the opposite with things like Musig2, FROST and ROAST. If we're going to need to make new signing software and new output types it might make more sense to go for a PQ signature scheme.
> > >
> > > - Making more p2wpkhs
> > > You don't have to send to a PQ address type with these transactions -- you can send to p2wpkh and do the whole commit/reveal process again when you want to spend. This could be helpful if PQ signature schemes are still being worked on, or if the PQ schemes are more costly to verify and have high fees in comparison to the old p2wpkh output types. It's possible that in such a scenario a few high-cost PQ transactions commit to many smaller EC transactions. If this actually gets adoption though, we might as well drop the EC signatures and just make output scripts into raw hash / preimage pairs. It could make sense to cover some non-EC script types with the same 3-hash commitment requirement to enable this.
> > >
> > > ## Conclusion
> > >
> > > This PQ commit / reveal scheme has similar properties to Tim Ruffing's, with a smaller commitment that can be done as a soft fork. I hope something like this could be soft forked with a PoQC activation trigger, so that if a QC never shows up, none of this code gets executed. And people who take a couple easy steps like not reusing addresses (which they should anyway for privacy reasons) don't have to worry about their coins.
> > >
> > > Some of these ideas may have been posted before; I know of the Fawkscoin paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent discussion which linked to Ruffing's proposal. Here I've tried to show how it could be done in a soft fork which doesn't look too bad to implement.
> > >
> > > I've also heard of some more complex schemes involving zero knowledge proofs, proving things like BIP32 derivations, but I think this gives some pretty good properties without needing anything other than good old SHA256.
> > >
> > > Hope this is useful & wonder if people think something like this would be a good idea.
> > >
> > > -Tadge
> > >
> > > --
> > > You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
> > > To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups•com.
> > > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com.
> >
> >
> >
> > --
> > Best regards,
> > Boris Nagaev
>
> --
> You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/402db6ba-2497-4aab-9f84-0d66b4b8efccn%40googlegroups.com.
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/G4RQ-XfZ50oMGil2qiIgdMQoYlZ_lPG7asIo2e0vyKGjfWBn6diRJXbjNqtUTEw1fSeux01_BxWqUJpKhiP-i1q6EU_RawfqrFeUutkFDDY%3D%40proton.me.
[-- Attachment #1.2: publickey - conduition@proton.me - 0x474891AD.asc --]
[-- Type: application/pgp-keys, Size: 649 bytes --]
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 343 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork
2025-06-02 17:38 ` waxwing/ AdamISZ
2025-06-02 19:34 ` 'conduition' via Bitcoin Development Mailing List
@ 2025-06-02 22:50 ` Nagaev Boris
1 sibling, 0 replies; 10+ messages in thread
From: Nagaev Boris @ 2025-06-02 22:50 UTC (permalink / raw)
To: waxwing/ AdamISZ; +Cc: Bitcoin Development Mailing List
Hi Adam, hi list,
Thank you for clarifying the nuances of the scheme!
> that same system but with keypath spending invalidated, so it's QR because of the hash function, but also, the tapleaf contains a QR or PQC signing scheme in it
I assume that some future QR signing algorithm might be added in a new
segwit version, resembling the current Taproot structure but with
keypath spending disabled (or otherwise addressed, so it doesn't
present a way to steal funds in a post-quantum world), and a new
opcode added to tapscript to enable QR signing. Also, such an address
type would need to handle the EC opcodes if they remain enabled in
tapscript. I didn't go deep into the details of this hypothetical
address type, as it's a separate complex topic. For the purpose of
this discussion, I assume that some version of it will be deployed
before or alongside the proposed scheme.
> I believe the *real* point here is not "nobody knows you committed something" though that may be practically significant, it's instead "nobody knows the exact commitment value (hash) you used".
I think this is a good observation! We can clarify it further: *nobody
should be able to replicate your commitment*.
I've identified a potential attack that, if it were possible, would
undermine this property. Let's assume, for a second, that a new
address type is just a Merkle root of a Merkle tree. Then an attacker
could build their own Merkle tree on top of the original Merkle root.
The attacker's tree would include the legitimate Merkle tree as a
subtree. If they learn the EC pubkey and the full path in the original
Merkle tree from the pubkey to the root, they could reconstruct the
full path in their tree embedding the original. They could learn this
information when the output is spent, so they would have everything
needed to produce a malicious proof.
Fortunately, with the Taproot we have today, such an extension isn't
possible. There's a step (among others) involving a tagged hash
function (h_tapTweak) that hashes the internal pubkey and Merkle root
together before producing the final public key. This prevents
constructing a Taproot output embedding another tree as a subtree
based solely on the output address. We should ensure that any future
taproot-like address type retains this property to prevent the attack
described above.
The scheme must be carefully analyzed to ensure it satisfies this
crucial property: nobody should be able to replicate your commitment.
I'm curious if anyone sees further edge cases we should consider.
> In these analyses, I think it's common to overlook a potentially crucial point: the UTXO set is enumerable in practical time, so we must always remember that we can check our calculations against existing addresses, even if they are hash-covered keys.
I would propose hardening the requirement further: assume the attacker
already knows exactly which EC address is protected with which QR
output from the beginning. Even with this knowledge, the attacker
should not be able to succeed. If we prove the scheme secure under
these strong assumptions (which are very favorable for the attacker),
then it is also secure under weaker assumptions where the attacker has
less information.
> This commitment is *not* literally perfectly hiding as in a properly formed Pedersen commitment
I agree that the hiding property of a properly formed Pedersen
commitment is stronger than in the proposed scheme. A Pedersen
commitment is perfectly hiding: the committed value is statistically
independent of the commitment, and even an attacker with unbounded
computational power cannot learn anything about the value. In
contrast, the proposed scheme relies on a hash of the pubkey for
hiding, which is only computationally hiding: it depends on the
preimage resistance of the hash function and can be weakened if
quantum attacks on hash functions improve.
However, I believe we cannot use Pedersen commitments here, because
their binding property would be broken by a quantum computer. Pedersen
commitments rely on the hardness of the discrete logarithm problem
(DLP) in an elliptic curve group for binding, and Shor's algorithm can
efficiently solve DLP on a quantum computer. This would allow an
attacker, once the legitimate opening (v,r) is revealed, to compute an
alternative opening (v',r') for the same commitment C. As a result, if
Pedersen commitments were used in the scheme, they would be vulnerable
during the reveal phase under a quantum attack.
Best,
Boris
On Mon, Jun 2, 2025 at 3:41 PM waxwing/ AdamISZ <ekaggata@gmail•com> wrote:
>
> Hi Boris, list,
>
> > In my scheme, a user creates a QR output that
> commits to a hash of a pubkey inside a Taproot leaf. This commitment
> is hidden until revealed at spend time. Later, when the user wants to
> spend a legacy EC output, they must spend this QR output in the same
> transaction, and it must be at least X blocks old.
>
> There's some nuances here that seem quite interesting. If an output commits (in a quantum-resistant way, i.e. hashing let's say) only to a pubkey, and not a pubkey plus spending-transaction, then, in the general case, that has the weakness that the commitment can be replicated, in another commitment tx, at the time of insertion of commitment into the blockchain; so that if the tiebreaker is "first commitment in the block(chain)" an attacker can mess with you. In your case you refer to "a QR output that commits to the hash of a pubkey inside a taproot leaf" but I'm finding it a tiny bit unclear what you mean there. Taproot itself isn't quantum resistant (QR), so Q = P + H(P,S)G is not QR even if P is NUMS. Whereas you might mean: that same system but with keypath spending invalidated, so it's QR because of the hash function, but also, the tapleaf contains a QR or PQC signing scheme in it (I guess this is what you actually mean). Or, you might mean something that is structurally the same as taproot but not using secp/BIP340, but instead a PQC scheme with a homomorphism so that that same design can be reused; call that "taproot2" .. though I don't think I've heard people talking about that.
>
> Then there's what I think you focus on: the commitment is hidden. To other readers, in case of confusion: I believe the *real* point here is not "nobody knows you committed something" though that may be practically significant, it's instead "nobody knows the exact commitment value (hash) you used".
>
> So, I believe that's a correct/valid point that actually *doesn't* depend on which "version" of taproot as per above. Focusing on current-taproot-but-script-path-only-with-QR-in-tapleaf: we have a protection that the quantum attacker cannot find the S in the (P,S) tuple (indeed, they cannot even know the H in P + H(P,S)G). This commitment is *not* literally perfectly hiding as in a properly formed Pedersen commitment ([1]) but I do think you have the normal preimage resistance against revelation as expected even in post-quantum. So that prevents the "copy the commitment" problem I started out by mentioning. [2]
>
> If "taproot2" instead then we have something for which even the keypath isn't crackable so I guess it's obvious.
>
> > Since the commitment doesn't include a txid, the user can precommit to
> the pubkey hash far in advance, before knowing the details of the
> eventual transaction.
>
> Again, I believe you're right here, but we should try to unpack what's different; because the "reveal" step of commit-reveal is accompanied by the QR signing event of the pre-existing QR output, we have a sane security model, so there's no need to commit to the transaction in the preliminary step, as far as I can tell.
>
> > More efficient use of block space
>
> Makes sense.
>
> I think the only downside I see here is that the initial commitment step requires the PQC scheme to actually exist. That may not seem like a big deal, but I have a suspicion it actually will be. I think a protocol in which we just rely on existing hash primitives and put off the PQC scheme choosing event may be necessary .. though I could be for sure wrong, in more than one way, in saying that.
>
> Apart from that point I think this scheme seems good (as you mention, it has the virtue of not requiring new databases etc which is pretty huge).
>
> Cheers,
> AdamISZ/waxwing
>
> [1] In these analyses, I think it's common to overlook a potentially crucial point: the utxo set is enumerable in practical time, so we must always remember that we can check our calculations against existing addresses, even if they are hash-covered keys.
>
> [2] The only caveat is if you're considering the possibility of the attacker knowing the key in advance of even the commitment step; generally, that's "game over", but i know that there is some attempt to analyze that case in some places, too. Not here.
>
> On Wednesday, May 28, 2025 at 6:54:21 PM UTC-3 Nagaev Boris wrote:
>>
>> Hi Tadge,
>>
>> Thanks for writing this up! The proposal is very thoughtful, and it's
>> great to see concrete work on post-quantum commit/reveal schemes.
>>
>> I've been exploring a related approach based on a similar
>> commit/reveal idea. In my scheme, a user creates a QR output that
>> commits to a hash of a pubkey inside a Taproot leaf. This commitment
>> is hidden until revealed at spend time. Later, when the user wants to
>> spend a legacy EC output, they must spend this QR output in the same
>> transaction, and it must be at least X blocks old.
>>
>> https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ
>>
>> This approach has a few potential advantages:
>>
>> 1. No need for nodes to track a new commitment store
>>
>> Because the commitment remains hidden in a Tapleaf until the spend,
>> observers (including attackers) don't see it, and nodes don't need to
>> store or validate any external commitment set. The only requirement is
>> that the QR output must be old enough, and Bitcoin Core already tracks
>> coin age, which is needed to validate existing consensus rules.
>>
>> 2. Commitment can be made before the transaction is known
>>
>> Since the commitment doesn't include a txid, the user can precommit to
>> the pubkey hash far in advance, before knowing the details of the
>> eventual transaction. This allows greater flexibility: you can delay
>> choosing outputs, fee rates, etc., until spend time. Only knowledge of
>> the EC pubkey needs to be proven when creating the QR output.
>>
>> 3. More efficient use of block space
>>
>> Multiple EC coins can be spent together with a single QR output,
>> holding EC pubkey commitments in Taproot leaves. If EC coins share the
>> same EC pubkey (e.g., come from the same address), they can reuse the
>> same commitment.
>>
>> Would love to hear your thoughts on this variant. I think this one
>> might be a simpler, lower-overhead option for protecting EC outputs
>> post-QC.
>>
>> Best,
>> Boris
>>
>> On Wed, May 28, 2025 at 2:28 PM Tadge Dryja <r...@awsomnet•org> wrote:
>> >
>> > One of the tricky things about securing Bitcoin against quantum computers is: do you even need to? Maybe quantum computers that can break secp256k1 keys will never exist, in which case we shouldn't waste our time. Or maybe they will exist, in not too many years, and we should spend the effort to secure the system against QCs.
>> >
>> > Since people disagree on how likely QCs are to arrive, and what the timing would be if they do, it's hard to get consensus on changes to bitcoin that disrupt the properties we use today. For example, a soft fork introducing a post-quantum (PQ) signature scheme and at the same time disallowing new secp256k1 based outputs would be great for strengthening Bitcoin against an oncoming QC. But it would be awful if a QC never appears, or takes decades to do so, since secp256k1 is really nice.
>> >
>> > So it would be nice to have a way to not deal with this issue until *after* the QC shows up. With commit / reveal schemes Bitcoin can keep working after a QC shows up, even if we haven't defined a PQ signature scheme and everyone's still got P2WPKH outputs.
>> >
>> > Most of this is similar to Tim Ruffing's proposal from a few years ago here:
>> > https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/
>> >
>> > The main difference is that this scheme doesn't use encryption, but a smaller hash-based commitment, and describes activation as a soft fork. I'll define the two types of attacks, a commitment scheme, and then say how it can be implemented in bitcoin nodes as a soft fork.
>> >
>> > This scheme only works for keys that are pubkey hashes (or script hashes) with pubkeys that are unknown to the network. It works with taproot as well, but there must be some script-path in the taproot key, as keypath spends would no longer be secure.
>> >
>> > What to do with all the keys that are known is another issue and independent of the scheme in this post (it's compatible with both burning them and leaving them to be stolen)
>> >
>> > For these schemes, we assume there is an attacker with a QC that can compute a quickly compute a private key from any secp256k1 public key. We also assume the attacker has some mining power or influence over miners for their attacks; maybe not reliably, but they can sometimes get a few blocks in a row with the transactions they want.
>> >
>> > "Pubkey" can also be substituted with "script" for P2SH and P2WSH output types and should work about the same way (with caveats about multisig). The equivalent for taproot outputs would be an inner key proving a script path.
>> >
>> > ## A simple scheme to show an attack
>> >
>> > The simplest commit/reveal scheme would be one where after activation, for any transaction with an EC signature in it, that transaction's txid must appear in a earlier transaction's OP_RETURN output.
>> >
>> > When a user wants to spend their coins, they first sign a transaction as they would normally, compute the txid, get that txid into an OP_RETURN output somehow (paying a miner out of band, etc), then after waiting a while, broadcast the transaction. Nodes would check that the txid matches a previously seen commitment, and allow the transaction.
>> >
>> > One problem with this scheme is that upon seeing the full transaction, the attacker can compute the user's private key, and create a new commitment with a different txid for a transaction where the attacker gets all the coins. If the attacker can get their commitment and spending transaction in before the user's transaction, they can steal the coins.
>> >
>> > In order to mitigate this problem, a minimum delay can be enforced by consensus. A minimum delay of 100 blocks would mean that the attacker would have to prevent the user's transaction from being confirmed for 100 blocks after it showed up in the attacker's mempool. The tradeoff is that longer periods give better safety at the cost of more delay in spending.
>> >
>> > This scheme, while problematic, is better than nothing! But it's possible to remove this timing tradeoff.
>> >
>> >
>> > ## A slightly more complex scheme with (worse) problems
>> >
>> > If instead of just the txid, the commitment were both the outpoint being spent, and the txid that was going to spend it, we could add a "first seen" consensus rule. Only the first commitment pointing to an outpoint works.
>> >
>> > So if nodes see two OP_RETURN commitments in their sequence of confirmed transactions:
>> >
>> > C1 = outpoint1, txid1
>> > C2 = outpoint1, txid2
>> >
>> > They can ignore C2; C1 has already laid claim to outpoint1, and the transaction identified by txid1 is the only transaction that can spend outpoint1.
>> >
>> > If the user manages to get C1 confirmed first, this is great, and eliminates the timing problem in the txid only scheme. But this introduces a different problem, where an attacker -- in this case any attacker, even one without a QC -- who can observe C1 before it is confirmed can flip some bits in the txid field, freezing the outpoint forever.
>> >
>> > We want to retain the "first seen" rule, but we want to also be able to discard invalid commitments. In a bit flipping attack, we could say an invalid commitment is one where there is no transaction described by the txid. A more general way to classify a commitment as invalid is a commitment made without knowledge of the (secret) pubkey. Knowledge of the pubkey is what security of coins is now hinging on.
>> >
>> >
>> > The actual commitment scheme
>> >
>> >
>> > We define some hash function h(). We'll use SHA256 for the hashing, but it needs to be keyed with some tag, for example "Alas poor Koblitz curve, we knew it well".
>> >
>> > Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin terms, HASH160(pubkey). Due to the hash functions being different, A = HASH160(pubkey) and B = h(pubkey) will be completely different, and nobody should be able to determine if A and B are hashes of the same pubkey without knowing pubkey itself.
>> >
>> > An efficient commitment is:
>> >
>> > C = h(pubkey), h(pubkey, txid), txid
>> > (to label things: C = AID, SDP, CTXID)
>> >
>> > This commitment includes 3 elements: a different hash of the pubkey which will be signed for, a proof of knowledge of the pubkey which commits to a transaction, and an the txid of the spending transaction. We'll call these "address ID" (AID), sequence dependent proof (SDP), and the commitment txid (CTXID).
>> >
>> > For those familiar with the proposal by Ruffing, the SDP has a similar function to the authenticated encryption part of the encrypted commitment. Instead of using authenticated encryption, we can instead just use an HMAC-style authentication alone, since the other data, the CTXID, is provided.
>> >
>> > When the user's wallet creates a transaction, they can feed that transaction into a commitment generator function which takes in a transaction, extracts the pubkey from the tx, computes the 3 hashes, and returns the 3-hash commitment. Once this commitment is confirmed, the user broadcasts the transaction.
>> >
>> > Nodes verify the commitment by using the same commitment generator function and checking if it matches the first valid commitment for that AID, in which case the tx is confirmed.
>> >
>> > If a node sees multiple commitments all claiming the same AID, it must store all of them. Once the AID's pubkey is known, the node can distinguish which commitments are valid, which are invalid, and which is the first seen valid commitment. Given the pubkey, nodes can determine commitments to be invalid by checking if SDP = h(pubkey, CTXID).
>> >
>> > As an example, consider a sequence of 3 commitments:
>> >
>> > C1 = h(pubkey), h(pubkey', txid1), txid1
>> > C2 = h(pubkey), h(pubkey, txid2), txid2
>> > C3 = h(pubkey), h(pubkey, txid3), txid3
>> >
>> > The user first creates tx2 and tries to commit C2. But an attacker creates C1, committing to a different txid where they control the outputs, and confirms it first. This attacker may know the outpoint being spent, and may be able to create a transaction and txid that could work. But they don't know the pubkey, so while they can copy the AID hash, they have to make something up for the SDP.
>> >
>> > The user gets C2 confirmed after C1. They then reveal tx2 in the mempool, but before it can be confirmed, the attacker gets C3 confirmed. C3 is a valid commitment made with knowledge of the pubkey.
>> >
>> > Nodes can reject transactions tx1 and tx3. For tx1, they will see that the SDP doesn't match the data in the transaction, so it's an invalid commitment. For tx3, they will see that it is valid, but by seeing tx3 they will also be able to determine that C2 is a valid commitment (since pubkey is revealed in tx3) which came prior to C3, making C2 the only valid commitment for that AID.
>> >
>> >
>> > ## Implementation
>> >
>> > Nodes would keep a new key/value store, similar to the existing UTXO set. The indexing key would be the AID, and the value would be the set of all (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is seen in an OP_RETURN, nodes store the commitment.
>> >
>> > When a transaction is seen, nodes observe the pubkey used in the transaction, and look up if it matches an AID they have stored. If not, the transaction is dropped. If the AID does match, the node can now "clean out" an AID entry, eliminating all but the first valid commitment, and marking that AID as final. If the txid seen matches the remaining commitment, the transaction is valid; if not, the transaction is dropped.
>> >
>> > After the transaction is confirmed the AID entry can be deleted. Deleting the entries frees up space, and would allow another round to happen with the same pubkey, which would lead to theft. Retaining the entries takes up more space on nodes that can't be pruned, and causes pubkey reuse to destroy coins rather than allow them to be stolen. That's a tradeoff, and I personally guess it's probably not worth retaining that data but don't have a strong opinion either way.
>> >
>> > Short commitments:
>> >
>> > Since we're not trying to defend against collision attacks, I think all 3 hashes can be truncated to 16 bytes. The whole commitment could be 48 bytes long. Without truncation the commitments would be 96 bytes.
>> >
>> >
>> > ## Activation
>> >
>> > The activation for the commit/reveal requirement can be triggered by a proof of quantum computer (PoQC).
>> >
>> > A transaction which successfully spends an output using tapscript:
>> >
>> > OP_SHA256 OP_CHECKSIG
>> >
>> > is a PoQC in the form of a valid bitcoin transaction. In order to satisfy this script, the spending transaction needs to provide 2 data elements: a signature, and some data that when hashed results in a pubkey for which that signature is valid. If such a pair of data elements exists, it means that either SHA256 preimage resistance is broken (which we're assuming isn't the case) or someone can create valid signatures for arbitrary elliptic curve points, ie a cryptographically relevant quantum computer (or any other process which breaks the security of secp256k1 signatures)
>> >
>> > Once such a PoQC has been observed in a confirmed transaction, the requirements for the 3-hash commitment scheme can be enforced. This is a soft fork since the transactions themselves look the same, the only requirement is that some OP_RETURN outputs show up earlier. Nodes which are not aware of the commitment requirement will still accept all transactions with the new rules.
>> >
>> > Wallets not aware of the new rules, however, are very dangerous, as they may try to broadcast signed transactions without any commitment. Nodes that see such a transaction should drop the tx, and if possible tell the wallet that they are doing something which is now very dangerous! On the open p2p network this is not really enforceable, but people submitting transactions to their own node (eg via RPC) can at least get a scary error message.
>> >
>> >
>> > ## Issues
>> >
>> > My hope is that this scheme would give some peace of mind to people holding bitcoin, that in the face of a sudden QC, even with minimal preparation their coins can be safe at rest and safely moved. It also suggests some best practices for users and wallets to adopt, before any software changes: Don't reuse addresses, and if you have taproot outputs, include some kind of script path in the outer key.
>> >
>> > There are still a number of problems, though!
>> >
>> > - Reorgs can steal coins. An attacker that observes a pubkey and can reorg back to before the commitment can compute the private key, sign a new transaction and get their commitment in first on the new chain. This seems unavoidable with commit/reveal schemes, and it's up to the user how long they wait between confirming the commitment and revealing the transaction.
>> >
>> > - How to get op_returns in
>> > If there are no PQ signature schemes activated in bitcoin when this activates, there's only one type of transaction that can reliably get the OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to the miners and paying them out of band is not great, but is possible and we see this kind of activity today. Users wouldn't need to directly contact miners: anyone could aggregate commitments, create a large transaction with many OP_RETURN outputs, and then get a miner to commit to that parent transaction. Users don't need to worry about committing twice as identical commitments would be a no op.
>> >
>> > - Spam
>> > Anyone can make lots of OP_RETURN commitments which are just random numbers, forcing nodes to store these commitments in a database. That's not great, but isn't much different from how bitcoin works today. If it's really a problem, nodes could requiring the commitment outputs to have a non-0 amount of bitcoin, imposing a higher cost for the commitments than other OP_RETURN outputs.
>> >
>> > - Multiple inputs
>> > If users have received more than one UTXO to the same address, they will need to spend all the UTXOs at once. The commitment scheme can deal with only the first pubkey seen in the serialized transaction.
>> >
>> > - Multisig and Lightning Network
>> > If your multisig counterparties have a QC, multisig outputs become 1 of N. Possibly a more complex commit / reveal scheme could deal with multiple keys, but the keys would all have to be hashed with counterparties not knowing each others' unhashed pubkeys. This isn't how existing multisig outputs work, and in fact the current trend is the opposite with things like Musig2, FROST and ROAST. If we're going to need to make new signing software and new output types it might make more sense to go for a PQ signature scheme.
>> >
>> > - Making more p2wpkhs
>> > You don't have to send to a PQ address type with these transactions -- you can send to p2wpkh and do the whole commit/reveal process again when you want to spend. This could be helpful if PQ signature schemes are still being worked on, or if the PQ schemes are more costly to verify and have high fees in comparison to the old p2wpkh output types. It's possible that in such a scenario a few high-cost PQ transactions commit to many smaller EC transactions. If this actually gets adoption though, we might as well drop the EC signatures and just make output scripts into raw hash / preimage pairs. It could make sense to cover some non-EC script types with the same 3-hash commitment requirement to enable this.
>> >
>> > ## Conclusion
>> >
>> > This PQ commit / reveal scheme has similar properties to Tim Ruffing's, with a smaller commitment that can be done as a soft fork. I hope something like this could be soft forked with a PoQC activation trigger, so that if a QC never shows up, none of this code gets executed. And people who take a couple easy steps like not reusing addresses (which they should anyway for privacy reasons) don't have to worry about their coins.
>> >
>> > Some of these ideas may have been posted before; I know of the Fawkscoin paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent discussion which linked to Ruffing's proposal. Here I've tried to show how it could be done in a soft fork which doesn't look too bad to implement.
>> >
>> > I've also heard of some more complex schemes involving zero knowledge proofs, proving things like BIP32 derivations, but I think this gives some pretty good properties without needing anything other than good old SHA256.
>> >
>> > Hope this is useful & wonder if people think something like this would be a good idea.
>> >
>> > -Tadge
>> >
>> > --
>> > You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
>> > To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups•com.
>> > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com.
>>
>>
>>
>> --
>> Best regards,
>> Boris Nagaev
>
> --
> You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/402db6ba-2497-4aab-9f84-0d66b4b8efccn%40googlegroups.com.
--
Best regards,
Boris Nagaev
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAFC_Vt6t9QvjUVJ_N2kYh60iiB3MgPkrahQ97CoTQSPFqdQ3yg%40mail.gmail.com.
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2025-06-02 23:03 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-05-28 17:14 [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork Tadge Dryja
2025-05-28 18:20 ` Sergio Demian Lerner
2025-05-28 20:24 ` Nagaev Boris
2025-05-30 22:00 ` Jonathan Voss
2025-06-02 11:24 ` Peter Todd
2025-06-02 15:50 ` Q C
2025-06-02 17:38 ` waxwing/ AdamISZ
2025-06-02 19:34 ` 'conduition' via Bitcoin Development Mailing List
2025-06-02 22:50 ` Nagaev Boris
2025-05-31 16:07 ` [bitcoindev] " waxwing/ AdamISZ
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox