Re: [bitcoin-dev] Transition to post-quantum

From: Erik Aronesty <erik@q32•com>
To: Tim Ruffing via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Transition to post-quantum
Date: Thu, 24 Oct 2019 11:34:14 -0400	[thread overview]
Message-ID: <CAJowKgL9-1WxEHxNdwO36vN7JcqiO7HWH=7T2hBBfxLX2nY4xg@mail.gmail.com> (raw)
In-Reply-To: <1518738259.3550.170.camel@mmci.uni-saarland.de>

- 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