[bitcoin-dev] Transition to post-quantum

[Erik Aronesty]

- 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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev