Discussion:
Transition to post-quantum
Add Reply
Tristan Hoy via bitcoin-dev
2018-02-12 14:13:11 UTC
Reply
Permalink
Raw Message
Hi all,

Recently I've been exploring what a post-quantum attack on Bitcoin would
actually look like, and what options exist for mitigating it.

I've put up a draft of my research here:
https://medium.com/@tristanhoy/11271f430c41

In summary:
1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are scalable
2) This is a rapidly advancing space and committment to a specific
post-quantum DSA now would be premature
3) I've identified a strategy (solution 3 in the draft) that mitigates
against the worst case scenario (unexpectedly early attack on ECDSA)
without requiring any changes to the Bitcoin protocol or total committment
to a specific post-quantum DSA that will likely be superseded in the next
3-5 years
4) This strategy also serves as a secure means of transferring balances
into a post-quantum DSA address space, even in the event that ECDSA is
fully compromised and the transition is reactionary

The proposal is a change to key generation only and will be implemented by
wallet providers.

Feedback would be most appreciated.

Regards,

Tristan
Tim Ruffing via bitcoin-dev
2018-02-12 15:50:50 UTC
Reply
Permalink
Raw Message
Hi Tristan,

Regarding the "Post-Quantum Address Recovery" part (I haven't read the
other parts), you may be interested in my message to the list from last
month and the rest of the thread:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015659.html

This is an approach which aims to avoid the issues that you've
mentioned in your blog post.

Best,
Tim
Post by Tristan Hoy via bitcoin-dev
Hi all,
Recently I've been exploring what a post-quantum attack on Bitcoin
would actually look like, and what options exist for mitigating it.
oy/11271f430c41
1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are scalable
2) This is a rapidly advancing space and committment to a specific
post-quantum DSA now would be premature
3) I've identified a strategy (solution 3 in the draft) that
mitigates against the worst case scenario (unexpectedly early attack
on ECDSA) without requiring any changes to the Bitcoin protocol or
total committment to a specific post-quantum DSA that will likely be
superseded in the next 3-5 years
4) This strategy also serves as a secure means of transferring
balances into a post-quantum DSA address space, even in the event
that ECDSA is fully compromised and the transition is reactionary
The proposal is a change to key generation only and will be
implemented by wallet providers.
Feedback would be most appreciated.
Regards,
Tristan
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Tristan Hoy via bitcoin-dev
2018-02-12 21:32:35 UTC
Reply
Permalink
Raw Message
Hi Tim,

Just read through your post, thanks for the heads up - I only just joined
this mailing list.

In a post-quantum world, your second "d" type transaction is completely
forgeable, which means it is vulnerable to front-running. An adversary
capable of breaking ECDSA needs only listen for these transactions, obtain
"classic_sk" and then use a higher fee (or relationship with a miner) to
effectively turn your original "d" transaction into a double-spend, with
the forged transaction sending all your funds to the adversary.

I'm pretty confident that a PQ DSA is required to prevent front-running,
and that no "commit-reveal" scheme will be secure without one.

The other issue with your approach is that if it is rolled out today, it
will effectively double transaction volumes - this is what I tried to solve
in solutions 2 and 3 in my article by instead modifying the address
generation process.

Regards,

Tristan

On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <
Post by Tim Ruffing via bitcoin-dev
Hi Tristan,
Regarding the "Post-Quantum Address Recovery" part (I haven't read the
other parts), you may be interested in my message to the list from last
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
2018-January/015659.html
This is an approach which aims to avoid the issues that you've
mentioned in your blog post.
Best,
Tim
Post by Tristan Hoy via bitcoin-dev
Hi all,
Recently I've been exploring what a post-quantum attack on Bitcoin
would actually look like, and what options exist for mitigating it.
oy/11271f430c41
1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are scalable
2) This is a rapidly advancing space and committment to a specific
post-quantum DSA now would be premature
3) I've identified a strategy (solution 3 in the draft) that
mitigates against the worst case scenario (unexpectedly early attack
on ECDSA) without requiring any changes to the Bitcoin protocol or
total committment to a specific post-quantum DSA that will likely be
superseded in the next 3-5 years
4) This strategy also serves as a secure means of transferring
balances into a post-quantum DSA address space, even in the event
that ECDSA is fully compromised and the transition is reactionary
The proposal is a change to key generation only and will be
implemented by wallet providers.
Feedback would be most appreciated.
Regards,
Tristan
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Tim Ruffing via bitcoin-dev
2018-02-13 06:46:14 UTC
Reply
Permalink
Raw Message
Post by Tristan Hoy via bitcoin-dev
In a post-quantum world, your second "d" type transaction is
completely forgeable, which means it is vulnerable to front-running.
An adversary capable of breaking ECDSA needs only listen for these
transactions, obtain "classic_sk" and then use a higher fee (or
relationship with a miner) to effectively turn your original "d"
transaction into a double-spend, with the forged transaction sending
all your funds to the adversary.
That's not true. The d(ecommit) transaction, or better let's call it
"decommit step" of a two-step transaction does not specify the effects
(output script). This is what I denote by "tx" in the writeup, and it's
already fixed by the c(ommit) step.

So yes, if the user finally reveals
d = classic_pk||Sign(classic_sk, tx)
a quantum attacker can indeed forge
d' = classic_pk||Sign(classic_sk, tx')
for tx' != tx of his choice. But that won't help him, because the first
valid c step in the chain is for tx and not for tx'.
Post by Tristan Hoy via bitcoin-dev
The other issue with your approach is that if it is rolled out today,
it will effectively double transaction volumes - this is what I tried
to solve in solutions 2 and 3 in my article by instead modifying the
address generation process.
Yep, it needs two entries in the blockchain, and that does not mean
that it doubles the data. It will need some more bytes in the
blockchain but also proper PQ-transactions could need more bytes in the
blockchain, so I don't think that's the major issue.
Post by Tristan Hoy via bitcoin-dev
Regards,
Tristan
On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
Post by Tim Ruffing via bitcoin-dev
Hi Tristan,
Regarding the "Post-Quantum Address Recovery" part (I haven't read the
other parts), you may be interested in my message to the list from last
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar
y/015659.html
This is an approach which aims to avoid the issues that you've
mentioned in your blog post.
Best,
Tim
Post by Tristan Hoy via bitcoin-dev
Hi all,
Recently I've been exploring what a post-quantum attack on
Bitcoin
Post by Tristan Hoy via bitcoin-dev
would actually look like, and what options exist for mitigating
it.
tanh
Post by Tristan Hoy via bitcoin-dev
oy/11271f430c41
1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are scalable
2) This is a rapidly advancing space and committment to a
specific
Post by Tristan Hoy via bitcoin-dev
post-quantum DSA now would be premature
3) I've identified a strategy (solution 3 in the draft) that
mitigates against the worst case scenario (unexpectedly early
attack
Post by Tristan Hoy via bitcoin-dev
on ECDSA) without requiring any changes to the Bitcoin protocol
or
Post by Tristan Hoy via bitcoin-dev
total committment to a specific post-quantum DSA that will likely
be
Post by Tristan Hoy via bitcoin-dev
superseded in the next 3-5 years
4) This strategy also serves as a secure means of transferring
balances into a post-quantum DSA address space, even in the event
that ECDSA is fully compromised and the transition is reactionary
The proposal is a change to key generation only and will be
implemented by wallet providers.
Feedback would be most appreciated.
Regards,
Tristan
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Tristan Hoy via bitcoin-dev
2018-02-13 10:06:31 UTC
Reply
Permalink
Raw Message
Post by Tim Ruffing via bitcoin-dev
Post by Tristan Hoy via bitcoin-dev
In a post-quantum world, your second "d" type transaction is
completely forgeable, which means it is vulnerable to front-running.
An adversary capable of breaking ECDSA needs only listen for these
transactions, obtain "classic_sk" and then use a higher fee (or
relationship with a miner) to effectively turn your original "d"
transaction into a double-spend, with the forged transaction sending
all your funds to the adversary.
That's not true. The d(ecommit) transaction, or better let's call it
"decommit step" of a two-step transaction does not specify the effects
(output script). This is what I denote by "tx" in the writeup, and it's
already fixed by the c(ommit) step.
So yes, if the user finally reveals
d = classic_pk||Sign(classic_sk, tx)
a quantum attacker can indeed forge
d' = classic_pk||Sign(classic_sk, tx')
for tx' != tx of his choice. But that won't help him, because the first
valid c step in the chain is for tx and not for tx'.
Thank you for clarifying, I should have caught that.
Post by Tim Ruffing via bitcoin-dev
Post by Tristan Hoy via bitcoin-dev
The other issue with your approach is that if it is rolled out today,
it will effectively double transaction volumes - this is what I tried
to solve in solutions 2 and 3 in my article by instead modifying the
address generation process.
Yep, it needs two entries in the blockchain, and that does not mean
that it doubles the data. It will need some more bytes in the
blockchain but also proper PQ-transactions could need more bytes in the
blockchain, so I don't think that's the major issue.
The worst-case outcome is that ECDSA is broken before PQ addresses are
rolled out. There is no reactive response to this - all the existing
ECDSA addresses will be compromised. A proactive measure is required,
and it should be deployed sooner rather than later.

Any two-step approach adopted now as a proactive measure will not only
bloat the blockchain, it will also double the effective confirmation
time - for all transactions between now and when PQ addresses are rolled
out, which seems unlikely to happen in the next 5 years. The bloat will
be permanent.

Either way, would you mind if I included your approach in the article,
with credit? I will seek your review before publishing.
Post by Tim Ruffing via bitcoin-dev
Post by Tristan Hoy via bitcoin-dev
Regards,
Tristan
On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
Post by Tim Ruffing via bitcoin-dev
Hi Tristan,
Regarding the "Post-Quantum Address Recovery" part (I haven't read the
other parts), you may be interested in my message to the list from last
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar
y/015659.html
This is an approach which aims to avoid the issues that you've
mentioned in your blog post.
Best,
Tim
Post by Tristan Hoy via bitcoin-dev
Hi all,
Recently I've been exploring what a post-quantum attack on
Bitcoin
Post by Tristan Hoy via bitcoin-dev
would actually look like, and what options exist for mitigating
it.
tanh
Post by Tristan Hoy via bitcoin-dev
oy/11271f430c41
1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are scalable
2) This is a rapidly advancing space and committment to a
specific
Post by Tristan Hoy via bitcoin-dev
post-quantum DSA now would be premature
3) I've identified a strategy (solution 3 in the draft) that
mitigates against the worst case scenario (unexpectedly early
attack
Post by Tristan Hoy via bitcoin-dev
on ECDSA) without requiring any changes to the Bitcoin protocol
or
Post by Tristan Hoy via bitcoin-dev
total committment to a specific post-quantum DSA that will likely
be
Post by Tristan Hoy via bitcoin-dev
superseded in the next 3-5 years
4) This strategy also serves as a secure means of transferring
balances into a post-quantum DSA address space, even in the event
that ECDSA is fully compromised and the transition is reactionary
The proposal is a change to key generation only and will be
implemented by wallet providers.
Feedback would be most appreciated.
Regards,
Tristan
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Tim Ruffing via bitcoin-dev
2018-02-15 15:59:27 UTC
Reply
Permalink
Raw Message
First of all, there is indeed an issue in my proposal:

The idea was to include a classic signature to make sure that, if (for
whatever reason) you have revealed classic_pk already.

However, the problem is that if you have revealed classic_pk, then
everybody can effectively prevent you from spending the funds as you
wish by just including the first commit entry with an arbitrary tx in
the blockchain. That's bad obviously.

Here is a fixed variant, which does not only work with normal P2PKH but
1) supports basically with any (hash-based) addresses, for which the
preimage has not been revealed and 2) does not change the conditions
under which a UTXO can be spent.

Setup
=====
We will need multiple hash functions KDF, H, and authenticated
symmetric encryption Enc/Dec.

Let's assume we have an UTXO with address addr = H_addr(chal), where
chal is a challenge, i.e., typically a scriptPubKey (what I called
classic_pk initially) and H_addr is the hash function used to form
addresses. (If there are multiple UTXO sharing the same address, they
can be spent simultaneously with this approach.) To spend this UTXO
with a transaction tx, the user performs the following two steps.

Note that -- in contrast to my earlier emails -- tx is assumed to
include a solution to the challenge in its input, i.e., a string which
proves that you are allowed to spend the UTXO (typically a scriptSig).

Commit step
===========
Derive a symmetric key k = KDF(chal).

Create and publish a commitment in the blockchain that references the
UTXO as inputs and contains the following data:
c = Enc(k, tx)

Wait until c is confirmed. (If it does not confirm, send it again as
usual.)

Decommit step
=============
Create and publish a decommitment with the following data:
d = chal

Consensus rules
===============
A decommitment d = chal spends a UTXO with address H_addr(chal), if
there exists a commitment c in the blockchain which references the UTXO
and which is the first commitment (among all referencing the UTXO) in
the blockchain such that
1. k = KDF(chal) correctly decrypts Dec(k, c)
and
2. tx = Dec(k, c) is a valid transaction to spend UTXO

The UTXO is spent as described by tx.
Commitments never expire.

The second condition covers that tx contains a classic signature under
the public key specified in chal in normal P2PKH addresses.

The trick here is that the encryption ensures that the user commits to
tx (including the classic signature) already in the commit step, while
still keeping the decommitment unique. If I'm not mistaken, this scheme
is a variant of Adam Back's proposal for committed transactions from
2013, which he invented for an entirely different goal, namely
censorship resistance:
https://bitcointalk.org/index.php?topic=206303.msg2162962#msg2162962

(Adam noted the similarity of the problems on Twitter recently:
https://twitter.com/adam3us/status/948219461345075201)

The above variant is pretty simple. If it really works and is secure,
it has the advantage over Adam's proposal that it does not rely on
ECDSA specifically and can be used for any address type.

The aforementioned thread in the Bitcoin forum discusses the main
problem of an approach like that: Everybody can flood the blockchain
with commitments. Of course, one can require fees to create
commitments, but that's pretty ugly: If this UTXO is the only money you
have, then you need to borrow some to pay the transaction fees upfront.
But this may be the price you need to pay for recovery. This can be
acceptable, because recovery should be the exception (see below).
Post by Tristan Hoy via bitcoin-dev
The worst-case outcome is that ECDSA is broken before PQ addresses are
rolled out. There is no reactive response to this - all the existing
ECDSA addresses will be compromised. A proactive measure is
required,
and it should be deployed sooner rather than later.
The proposal above does not require any changes to existing ECDSA
addresses, so there is no need to change something now already.

At some point in the future, PQ addresses will be deployed. And at some
(potentially different) point in the future, we should deploy a
solution to recover UTXOs. But there's no need to do this today. A
recovery solution can be deployed even when DLOG has been broken
already -- not optimal but possible.
Post by Tristan Hoy via bitcoin-dev
Any two-step approach adopted now as a proactive measure will not only
bloat the blockchain, it will also double the effective confirmation
time - for all transactions between now and when PQ addresses are rolled
out, which seems unlikely to happen in the next 5 years. The bloat will
be permanent.
I don't think that's true due to the situation I describe above. We
don't need to act now.

And even if we act now, i.e., even if we enable the above proposal (or
any other protocol that enables recovery of UTXOs with addresses)
today, people are not forced to use it. As long as ECDSA and the other
schemes we use today remain secure, people can and will continue to
perform conventional transactions. Ideally, people will need a recovery
protocol only for those UTXOs which they haven't touched for years and
have forgotten to convert to PQ in time.

You mentioned confirmation time. A nice thing is that the above
protocol does not double confirmation times. The sender needs to wait
for confirmation of the commitment. But as soon as the commitment is
confirmed, double-spending is excluded already, because the sender is
committed to the transaction. So the recipient does not need to wait
for confirmation of the decommitment. As soon as the recipient sees the
decommitment, everything is good. (If the decommitment is not
confirmed, the recipient can just re-broadcast it.)

In practice, we could even go further and call the transaction done
after the commitment is confirmed and the sender sends the data for the
second step to the recipient off-chain. Only when the recipient wants
to spend the funds again, the recipient will reveal this data.

The fact that double-spending is excluded after the first step is
confirmed, is exactly what makes the protocol secure against quantum
attackers who want to steal the money. As soon as the user reveals the
ECDSA public key, a quantum attacker has access to all secrets: The
attacker knows the preimage of the hash can compute the secret key.
So from this point on, there is no hope that we can distinguish the
honest user from the attacker. But since the correct transaction has
been committed to the blockchain, and cannot be changed anymore, we
don't need to distinguish the honest user from the attacker.
Post by Tristan Hoy via bitcoin-dev
Either way, would you mind if I included your approach in the
article,
with credit? I will seek your review before publishing.
Sure, feel free to include. You don't need to seek my review but I can
certainly have a look if desired.

Tim
Natanael via bitcoin-dev
2018-02-15 20:27:27 UTC
Reply
Permalink
Raw Message
Den 15 feb. 2018 17:00 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-***@lists.linuxfoundation.org>:


Consensus rules
===============
A decommitment d = chal spends a UTXO with address H_addr(chal), if
there exists a commitment c in the blockchain which references the UTXO
and which is the first commitment (among all referencing the UTXO) in
the blockchain such that
1. k = KDF(chal) correctly decrypts Dec(k, c)
and
2. tx = Dec(k, c) is a valid transaction to spend UTXO

The UTXO is spent as described by tx.
Commitments never expire.


I addressed this partially before, and this is unfortunately incomplete.

Situation A: Regardless of expiration of commitments, we allow doubles. (Or
no doubles allowed, but commitments expire.)

If I can block your transaction from confirming (censorship), then I can
make my own commitment + transaction. The miners will see two commitments
referencing the same UTXO - but can see only one transaction which match a
valid challenge and spends them, which is mine. You gained nothing from the
commitment.

Situation B: We don't allow conflicting commitments, and they never expire.
I can now freeze everybody's funds trivially with invalid commitments,
because you can't validate a commitment without seeing a valid transaction
matching it - and exposing an uncommitted transaction breaks the security
promise of commitments.

Any additional data in the commitment but hash it the transaction is
pointless, because the security properties are the same. You can't freeze
an UTXO after only seeing a commitment, and for any two conflicting
transactions you may observe it does not matter at all if one references
UTXO:s or not since you already know both transactions' commitment ages
anyway. Oldest would win no matter the additional data.

Commitments work when the network can't easily be censored for long enough
to deploy the attack (at least for 2-3 blocks worth of time). They fail
when the attacker is capable of performing such an attack.

As I said previously, the only completely solid solution in all
circumstances is a quantum resistant Zero-knowledge proof algorithm, or
some equivalent method of proving knowledge of the key without revealing
any data that enables a quantum attack.
Tim Ruffing via bitcoin-dev
2018-02-15 21:57:41 UTC
Reply
Permalink
Raw Message
Post by Natanael via bitcoin-dev
I addressed this partially before, and this is unfortunately
incomplete.
Situation A: Regardless of expiration of commitments, we allow
doubles. (Or no doubles allowed, but commitments expire.)
If I can block your transaction from confirming (censorship), then I
can make my own commitment + transaction. The miners will see two
commitments referencing the same UTXO - but can see only one
transaction which match a valid challenge and spends them, which is
mine. You gained nothing from the commitment.
Yes, I assume situation A:
* commitments never expire
* and there is no limit on the number of commitment for the same UTXO

As I understand, you mean "decommitment" when you say "transaction".
Please correct me if I'm wrong. I'll stick with "decommitment".

Let's assume the attacker blocks the decommitment by the honest user,
inserts his own malicious commitment and his own decommitment, which
should be valid for the malicious commitment. Then the miners will see
two commitments (the earlier commitment by the honest user and the
later one by the attacker).

Also, the miners will indeed see one valid decommitment. This
decommitment may have been sent by the attacker but it's the preimage
chal of the address, because otherwise it's not valid for the malicious
commitment. But if the decommitment is chal, then this decommitment is
also valid for the commitment of the honest user, which is earliest
additionally. So the honest commitment wins. The attacker does not
succeed and everything is fine.

The reason why this works:
There is only one unique decommitment for the UTXO (assuming H_addr is
collision-resistant). The decommitment does not depend on the
commitment. The attacker cannot send a different decommitment, just
because there is none.

Maybe I'm wrong and I just don't understand your attack. In this case,
please explain it more detail.

Regards,
Tim
Natanael via bitcoin-dev
2018-02-15 22:44:05 UTC
Reply
Permalink
Raw Message
Den 15 feb. 2018 22:58 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-***@lists.linuxfoundation.org>:


Also, the miners will indeed see one valid decommitment. This
decommitment may have been sent by the attacker but it's the preimage
chal of the address, because otherwise it's not valid for the malicious
commitment. But if the decommitment is chal, then this decommitment is
also valid for the commitment of the honest user, which is earliest
additionally. So the honest commitment wins. The attacker does not
succeed and everything is fine.

The reason why this works:
There is only one unique decommitment for the UTXO (assuming H_addr is
collision-resistant). The decommitment does not depend on the
commitment. The attacker cannot send a different decommitment, just
because there is none.


If your argument is that we publish the full transaction minus the public
key and signatures, just committing to it, and then revealing that later
(which means an attacker can't modify the transaction in advance in a way
that produces a valid transaction);

Allowing expiration retains insecurity, while allowing expiration makes it
a trivial DoS target.

Anybody can flood the miners with invalid transaction commitments. No miner
can ever prune invalid commitments until a valid transaction is finalized
which conflicts with the invalid commitments. You can't even rate limit it
safely.

Like I said in the other thread, this is unreasonable. It's much more
practical with simple hash commitment that you can "fold away" in a Merkle
tree hash and which you don't need to validate until the full transaction
is published.
Natanael via bitcoin-dev
2018-02-15 22:45:09 UTC
Reply
Permalink
Raw Message
Small correction, see edited quote

Den 15 feb. 2018 23:44 skrev "Natanael" <***@gmail.com>:

Allowing expiration retains insecurity, while *NOT* allowing expiration
makes it a trivial DoS target.
Tim Ruffing via bitcoin-dev
2018-02-15 23:44:19 UTC
Reply
Permalink
Raw Message
Post by Natanael via bitcoin-dev
If your argument is that we publish the full transaction minus the
public key and signatures, just committing to it, and then revealing
that later (which means an attacker can't modify the transaction in
advance in a way that produces a valid transaction);
Almost. Actually we reveal the entire transaction later.
Post by Natanael via bitcoin-dev
[...] while *NOT* allowing expiration makes it a trivial DoS target.
Anybody can flood the miners with invalid transaction commitments. No
miner can ever prune invalid commitments until a valid transaction is
finalized which conflicts with the invalid commitments. You can't
even rate limit it safely.
Yes, that's certainly true. I mentioned that issue already.

You can rate limit this: The only thing I see is that one can require
transaction fees even for commitments. That's super annoying, because
you need a second (PQ-)UTXO just to commit. But it's not impossible.

You can call this impractical and this may well be true. But what will
be most practical in the future depends on many parameters that are
totally unclear at the moment, e.g., the efficiency of zero-knowledge
proof systems. Who knows?

If you would like to use zero-knowledge proofs to recover an UTXO with
an P2PKH address, you need to prove in zero-knowledge that you know
some secret key x such that H(g^x)=addr. That seems plausible. But
P2PKH is by far the simplest example. For arbitrary scripts, this can
become pretty complex and nasty, even if our proof systems and machines
are fast enough.

Loading...