From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id E33B21361 for ; Thu, 24 Oct 2019 15:34:27 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ot1-f41.google.com (mail-ot1-f41.google.com [209.85.210.41]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 467598A7 for ; Thu, 24 Oct 2019 15:34:27 +0000 (UTC) Received: by mail-ot1-f41.google.com with SMTP id 89so20996748oth.13 for ; Thu, 24 Oct 2019 08:34:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=q32-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=WxrO+fJhJ3liv6lUtYYcXcFIN/1e8pJ9MdQ56/1sAgI=; b=vZ7cZ6Ce/EQsPHAqo1vRhHGtOd5iRVBJN9lFr7QqQki3cEBlosEWMu4W6RuyOzD+Xz URC9ejsjgTVth7KUc7Y2hzBTv7MtoqrMAhnUfXgrs9a++gdiDQfqoX+Ps+ZLb49xMnee d4lOr4zByYy5u0lcpY/t+qVNjRTsO/E9m/W8NM4lIEzNpXwqOLvF1xYxPWuf9KSw4fKK D05XSAa2XHjgXONi+Hp1rAWI6JRBr/z94rGfM7CU69LbqOflRiJj/2KiAHNF+dJVBzGF th9drgJOdzZRGPgmGVjl0dnlD7S5g8Z+Wn25GA5x0w9/64UoQyO9IoV+OvZLpn+v2QT9 qCIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=WxrO+fJhJ3liv6lUtYYcXcFIN/1e8pJ9MdQ56/1sAgI=; b=B/3oZfFpuqyuHa8WYD9jcvIfsveNESlmsN+91loEzr1ikbAEh2g8mowdLCgRZE22oT 39NFZfeG+u5Yozk5WFXMWAPiu4v6WovLKjnA/r4EksSl+3aKtZmNZjJI175Am6quwe9w t2Ofxye0y+rRlN5XJL2PA4qeVsXfivAa7VBHRyyhvG7enAICtbqdvqrsmsc2mPBg653/ c7r5sVIPifUP+VidhMCIRtzCcLowoSG/YD02yIXgF2IZUYM7BiCGJO8+LPf+NnY9FH+x M2Qs1eFiox8NVxk8U8tRCYFDDzbhLpri/BGxpCVqgMopzbA1MgVTIV8EEMLUrh4reL+X nSSg== X-Gm-Message-State: APjAAAWMDqbWErcPsnMNjs8ZXwxFG9sppwnNKWPUy7NRHdFNxZ2kwDMT MXPPej7+c6rW7UffaxFFFO81l5KMh/HrH6ATSdQho/iy0sdWJog= X-Google-Smtp-Source: APXvYqyPqDYhp4NLv2keGYY7sqJ8nb4/s4ygU4fpbfd4k7WbI5DR3ypPHad8pp6MhMCUCK4SpZCdr7b78mMmY9+dg/8= X-Received: by 2002:a05:6830:4c1:: with SMTP id s1mr12928797otd.280.1571931265832; Thu, 24 Oct 2019 08:34:25 -0700 (PDT) MIME-Version: 1.0 References: <1518450650.7829.87.camel@mmci.uni-saarland.de> <1518504374.9878.24.camel@mmci.uni-saarland.de> <882306fa-3ea0-99bd-61c6-f646d27c2ab6@gmail.com> <1518710367.3550.111.camel@mmci.uni-saarland.de> <1518731861.3550.131.camel@mmci.uni-saarland.de> <1518738259.3550.170.camel@mmci.uni-saarland.de> In-Reply-To: <1518738259.3550.170.camel@mmci.uni-saarland.de> From: Erik Aronesty Date: Thu, 24 Oct 2019 11:34:14 -0400 Message-ID: To: Tim Ruffing via bitcoin-dev Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DOS_RCVD_IP_TWICE_B, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Thu, 24 Oct 2019 15:58:26 +0000 Subject: Re: [bitcoin-dev] Transition to post-quantum X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Oct 2019 15:34:28 -0000 - 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 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