* [bitcoin-dev] Transition to post-quantum
@ 2018-02-12 14:13 Tristan Hoy
2018-02-12 15:50 ` Tim Ruffing
0 siblings, 1 reply; 12+ messages in thread
From: Tristan Hoy @ 2018-02-12 14:13 UTC (permalink / raw)
To: bitcoin-dev
[-- Attachment #1: Type: text/plain, Size: 1068 bytes --]
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
[-- Attachment #2: Type: text/html, Size: 1791 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-12 14:13 [bitcoin-dev] Transition to post-quantum Tristan Hoy
@ 2018-02-12 15:50 ` Tim Ruffing
2018-02-12 21:32 ` Tristan Hoy
0 siblings, 1 reply; 12+ messages in thread
From: Tim Ruffing @ 2018-02-12 15:50 UTC (permalink / raw)
To: 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
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
On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote:
> 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/@tristanh
> oy/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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-12 15:50 ` Tim Ruffing
@ 2018-02-12 21:32 ` Tristan Hoy
2018-02-13 6:46 ` Tim Ruffing
0 siblings, 1 reply; 12+ messages in thread
From: Tristan Hoy @ 2018-02-12 21:32 UTC (permalink / raw)
To: Tim Ruffing, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 3065 bytes --]
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 <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> 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
>
> On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote:
> > 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/@tristanh
> > oy/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
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists•linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 4487 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-12 21:32 ` Tristan Hoy
@ 2018-02-13 6:46 ` Tim Ruffing
2018-02-13 10:06 ` Tristan Hoy
0 siblings, 1 reply; 12+ messages in thread
From: Tim Ruffing @ 2018-02-13 6:46 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote:
> 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'.
> 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.
>
> Regards,
>
> Tristan
>
> On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
> -dev@lists•linuxfoundation.org> wrote:
> > 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-Januar
> > y/015659.html
> >
> > This is an approach which aims to avoid the issues that you've
> > mentioned in your blog post.
> >
> > Best,
> > Tim
> >
> > On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev
> > wrote:
> > > 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/@tris
> > tanh
> > > oy/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
> > > _______________________________________________
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists•linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists•linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-13 6:46 ` Tim Ruffing
@ 2018-02-13 10:06 ` Tristan Hoy
2018-02-15 15:59 ` Tim Ruffing
0 siblings, 1 reply; 12+ messages in thread
From: Tristan Hoy @ 2018-02-13 10:06 UTC (permalink / raw)
To: bitcoin-dev
On 13/02/2018 5:46 PM, Tim Ruffing via bitcoin-dev wrote:
> On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote:
>> 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.
>> 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.
>> Regards,
>>
>> Tristan
>>
>> On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
>> -dev@lists•linuxfoundation.org> wrote:
>>> 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-Januar
>>> y/015659.html
>>>
>>> This is an approach which aims to avoid the issues that you've
>>> mentioned in your blog post.
>>>
>>> Best,
>>> Tim
>>>
>>> On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev
>>> wrote:
>>>> 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/@tris
>>> tanh
>>>> oy/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
>>>> _______________________________________________
>>>> bitcoin-dev mailing list
>>>> bitcoin-dev@lists•linuxfoundation.org
>>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists•linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-13 10:06 ` Tristan Hoy
@ 2018-02-15 15:59 ` Tim Ruffing
2018-02-15 20:27 ` Natanael
0 siblings, 1 reply; 12+ messages in thread
From: Tim Ruffing @ 2018-02-15 15:59 UTC (permalink / raw)
To: bitcoin-dev
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).
On Tue, 2018-02-13 at 21:06 +1100, Tristan Hoy via bitcoin-dev wrote:
> 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.
>
> 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.
> 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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-15 15:59 ` Tim Ruffing
@ 2018-02-15 20:27 ` Natanael
2018-02-15 21:57 ` Tim Ruffing
0 siblings, 1 reply; 12+ messages in thread
From: Natanael @ 2018-02-15 20:27 UTC (permalink / raw)
To: Tim Ruffing, Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2243 bytes --]
Den 15 feb. 2018 17:00 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-dev@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.
[-- Attachment #2: Type: text/html, Size: 3211 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-15 20:27 ` Natanael
@ 2018-02-15 21:57 ` Tim Ruffing
2018-02-15 22:44 ` Natanael
0 siblings, 1 reply; 12+ messages in thread
From: Tim Ruffing @ 2018-02-15 21:57 UTC (permalink / raw)
To: Bitcoin Dev
On Thu, 2018-02-15 at 21:27 +0100, Natanael wrote:
> 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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-15 21:57 ` Tim Ruffing
@ 2018-02-15 22:44 ` Natanael
2018-02-15 22:45 ` Natanael
2018-02-15 23:44 ` Tim Ruffing
0 siblings, 2 replies; 12+ messages in thread
From: Natanael @ 2018-02-15 22:44 UTC (permalink / raw)
To: Tim Ruffing, Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1623 bytes --]
Den 15 feb. 2018 22:58 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-dev@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.
[-- Attachment #2: Type: text/html, Size: 2448 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-15 22:44 ` Natanael
@ 2018-02-15 22:45 ` Natanael
2018-02-15 23:44 ` Tim Ruffing
1 sibling, 0 replies; 12+ messages in thread
From: Natanael @ 2018-02-15 22:45 UTC (permalink / raw)
To: Tim Ruffing, Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 204 bytes --]
Small correction, see edited quote
Den 15 feb. 2018 23:44 skrev "Natanael" <natanael.l@gmail•com>:
Allowing expiration retains insecurity, while *NOT* allowing expiration
makes it a trivial DoS target.
[-- Attachment #2: Type: text/html, Size: 601 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-15 22:44 ` Natanael
2018-02-15 22:45 ` Natanael
@ 2018-02-15 23:44 ` Tim Ruffing
2019-10-24 15:34 ` Erik Aronesty
1 sibling, 1 reply; 12+ messages in thread
From: Tim Ruffing @ 2018-02-15 23:44 UTC (permalink / raw)
To: Natanael, Bitcoin Dev
On Thu, 2018-02-15 at 23:44 +0100, Natanael wrote:
> 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.
>
> [...] 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.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [bitcoin-dev] Transition to post-quantum
2018-02-15 23:44 ` Tim Ruffing
@ 2019-10-24 15:34 ` Erik Aronesty
0 siblings, 0 replies; 12+ messages in thread
From: Erik Aronesty @ 2019-10-24 15:34 UTC (permalink / raw)
To: Tim Ruffing via bitcoin-dev
- It would be hard to prove you have access to an x that can produce
H(g^x) in a way that doesn't expose g^x and isn't one of those slow,
interactive bit-encryption algorithms.
- Instead a simple scheme would publish a transaction to the
blockchain that lists:
- pre-quantum signature
- hash of post-quantum address
- Any future transactions would require both the pre *and*
post-quantum signatures.
That scheme would need to be implemented sufficient number of years
before quantum became a pressing issue, but it's super simple,
spam-proof (requires fees), and flexible enough that it can change as
post-quantum addressing improves.
Imagine there are 2 quantum addressing schemes in order of discovery.
1. Soft-fork 1 accepts the first scheme and people begin publishing
PRE/POST upgrades.
2. Discovery is made that shows a second scheme has smaller
transactions and faster validation.
3. Soft-fork 2 refuses to accept upgrades to the first scheme in
transactions beyond a certain block number in order to improve
performance.
On Thu, Feb 15, 2018 at 6:44 PM Tim Ruffing via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> On Thu, 2018-02-15 at 23:44 +0100, Natanael wrote:
> > 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.
>
> >
> > [...] 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.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2019-10-24 15:34 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-02-12 14:13 [bitcoin-dev] Transition to post-quantum Tristan Hoy
2018-02-12 15:50 ` Tim Ruffing
2018-02-12 21:32 ` Tristan Hoy
2018-02-13 6:46 ` Tim Ruffing
2018-02-13 10:06 ` Tristan Hoy
2018-02-15 15:59 ` Tim Ruffing
2018-02-15 20:27 ` Natanael
2018-02-15 21:57 ` Tim Ruffing
2018-02-15 22:44 ` Natanael
2018-02-15 22:45 ` Natanael
2018-02-15 23:44 ` Tim Ruffing
2019-10-24 15:34 ` Erik Aronesty
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox