public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
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


      reply	other threads:[~2019-10-24 15:34 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
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 message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAJowKgL9-1WxEHxNdwO36vN7JcqiO7HWH=7T2hBBfxLX2nY4xg@mail.gmail.com' \
    --to=erik@q32.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox