1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
Return-Path: <earonesty@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id E33B21361
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 24 Oct 2019 15:34:27 +0000 (UTC)
Received: by mail-ot1-f41.google.com with SMTP id 89so20996748oth.13
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <CAFEpHQHP7XXBYUP6CF1OeYoBpj0UwK+qpYG-14_zQZDX4Md7UA@mail.gmail.com>
<1518450650.7829.87.camel@mmci.uni-saarland.de>
<CAFEpHQHYdE3m2GUtN=ijvtYUudwtcG52rRxzH66VFbgO1KEihw@mail.gmail.com>
<1518504374.9878.24.camel@mmci.uni-saarland.de>
<882306fa-3ea0-99bd-61c6-f646d27c2ab6@gmail.com>
<1518710367.3550.111.camel@mmci.uni-saarland.de>
<CAAt2M1-JtmcMH2WCx5T5U8B-B+Ob61WPSvX4JoOcWzYFCLSTmw@mail.gmail.com>
<1518731861.3550.131.camel@mmci.uni-saarland.de>
<CAAt2M1-0-c1-OC0g0_6aBueR8wU+ipPw4U_zSLkdoh3K79PWsw@mail.gmail.com>
<1518738259.3550.170.camel@mmci.uni-saarland.de>
In-Reply-To: <1518738259.3550.170.camel@mmci.uni-saarland.de>
From: Erik Aronesty <erik@q32.com>
Date: Thu, 24 Oct 2019 11:34:14 -0400
Message-ID: <CAJowKgL9-1WxEHxNdwO36vN7JcqiO7HWH=7T2hBBfxLX2nY4xg@mail.gmail.com>
To: Tim Ruffing via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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
<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
|
