Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 5C33911FC for ; Thu, 15 Feb 2018 15:59:34 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from jupiter.mpi-klsb.mpg.de (jupiter.mpi-klsb.mpg.de [139.19.86.15]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 493BC405 for ; Thu, 15 Feb 2018 15:59:33 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=mmci.uni-saarland.de; s=mail200803; h=Content-Transfer-Encoding:Mime-Version:Content-Type:References:In-Reply-To:Date:To:From:Subject:Message-ID; bh=oUyWIulUWm2i5CUgXge085y46Jcxdp/kxGmXgUdf660=; b=pGqZAAS0zfLRm60y/v+hjScRlhZjqJGBhBekAwBtvH6d4iOjGDXHMK+77+pYbmXQjCq3OeEiDbslYNzkSV9kmROxoLJfiuwGAZrwKpviQy5+m76z8dmGLYa//M6BhQjDz4PG6wWwua589OBHueFUzevYqBva9Z7Nf25RJypqlqg=; Received: from srv-00-61.mpi-klsb.mpg.de ([139.19.86.26]:49720 helo=sam.mpi-klsb.mpg.de) by jupiter.mpi-klsb.mpg.de (envelope-from ) with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) id 1emLwW-0008Tw-OL for bitcoin-dev@lists.linuxfoundation.org; Thu, 15 Feb 2018 16:59:31 +0100 Received: from x590ec036.dyn.telefonica.de ([89.14.192.54]:40352 helo=tonno.fritz.box) by sam.mpi-klsb.mpg.de (envelope-from ) with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) id 1emLwW-0005uR-Fx for bitcoin-dev@lists.linuxfoundation.org; Thu, 15 Feb 2018 16:59:28 +0100 Message-ID: <1518710367.3550.111.camel@mmci.uni-saarland.de> From: Tim Ruffing To: bitcoin-dev@lists.linuxfoundation.org Date: Thu, 15 Feb 2018 16:59:27 +0100 In-Reply-To: <882306fa-3ea0-99bd-61c6-f646d27c2ab6@gmail.com> References: <1518450650.7829.87.camel@mmci.uni-saarland.de> <1518504374.9878.24.camel@mmci.uni-saarland.de> <882306fa-3ea0-99bd-61c6-f646d27c2ab6@gmail.com> Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.26.5 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-MPI-Local-Sender: true X-Spam-Status: No, score=-4.3 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org 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, 15 Feb 2018 15:59:34 -0000 First of all, there is indeed an issue in my proposal: The idea was to include a classic signature to make sure that, if (for whatever reason) you have revealed classic_pk already. However, the problem is that if you have revealed classic_pk, then everybody can effectively prevent you from spending the funds as you wish by just including the first commit entry with an arbitrary tx in the blockchain. That's bad obviously. Here is a fixed variant, which does not only work with normal P2PKH but 1) supports basically with any (hash-based) addresses, for which the preimage has not been revealed and 2) does not change the conditions under which a UTXO can be spent. Setup ===== We will need multiple hash functions KDF, H, and authenticated symmetric encryption Enc/Dec. Let's assume we have an UTXO with address addr = H_addr(chal), where chal is a challenge, i.e., typically a scriptPubKey (what I called classic_pk initially) and H_addr is the hash function used to form addresses. (If there are multiple UTXO sharing the same address, they can be spent simultaneously with this approach.) To spend this UTXO with a transaction tx, the user performs the following two steps. Note that -- in contrast to my earlier emails -- tx is assumed to include a solution to the challenge in its input, i.e., a string which proves that you are allowed to spend the UTXO (typically a scriptSig). Commit step =========== Derive a symmetric key k = KDF(chal). Create and publish a commitment in the blockchain that references the UTXO as inputs and contains the following data: c = Enc(k, tx) Wait until c is confirmed. (If it does not confirm, send it again as usual.) Decommit step ============= Create and publish a decommitment with the following data: d = chal Consensus rules =============== A decommitment d = chal spends a UTXO with address H_addr(chal), if there exists a commitment c in the blockchain which references the UTXO and which is the first commitment (among all referencing the UTXO) in the blockchain such that 1. k = KDF(chal) correctly decrypts Dec(k, c) and 2. tx = Dec(k, c) is a valid transaction to spend UTXO The UTXO is spent as described by tx. Commitments never expire. The second condition covers that tx contains a classic signature under the public key specified in chal in normal P2PKH addresses. The trick here is that the encryption ensures that the user commits to tx (including the classic signature) already in the commit step, while still keeping the decommitment unique. If I'm not mistaken, this scheme is a variant of Adam Back's proposal for committed transactions from 2013, which he invented for an entirely different goal, namely censorship resistance: https://bitcointalk.org/index.php?topic=206303.msg2162962#msg2162962 (Adam noted the similarity of the problems on Twitter recently: https://twitter.com/adam3us/status/948219461345075201) The above variant is pretty simple. If it really works and is secure, it has the advantage over Adam's proposal that it does not rely on ECDSA specifically and can be used for any address type. The aforementioned thread in the Bitcoin forum discusses the main problem of an approach like that: Everybody can flood the blockchain with commitments. Of course, one can require fees to create commitments, but that's pretty ugly: If this UTXO is the only money you have, then you need to borrow some to pay the transaction fees upfront. But this may be the price you need to pay for recovery. This can be acceptable, because recovery should be the exception (see below). On Tue, 2018-02-13 at 21:06 +1100, Tristan Hoy via bitcoin-dev wrote: > The worst-case outcome is that ECDSA is broken before PQ addresses > are > rolled out. There is no reactive response to this - all the existing > ECDSA addresses will be compromised. A proactive measure is > required, > and it should be deployed sooner rather than later. The proposal above does not require any changes to existing ECDSA addresses, so there is no need to change something now already. At some point in the future, PQ addresses will be deployed. And at some (potentially different) point in the future, we should deploy a solution to recover UTXOs. But there's no need to do this today. A recovery solution can be deployed even when DLOG has been broken already -- not optimal but possible. > > Any two-step approach adopted now as a proactive measure will not > only > bloat the blockchain, it will also double the effective confirmation > time - for all transactions between now and when PQ addresses are > rolled > out, which seems unlikely to happen in the next 5 years. The bloat > will > be permanent. > I don't think that's true due to the situation I describe above. We don't need to act now. And even if we act now, i.e., even if we enable the above proposal (or any other protocol that enables recovery of UTXOs with addresses) today, people are not forced to use it. As long as ECDSA and the other schemes we use today remain secure, people can and will continue to perform conventional transactions. Ideally, people will need a recovery protocol only for those UTXOs which they haven't touched for years and have forgotten to convert to PQ in time. You mentioned confirmation time. A nice thing is that the above protocol does not double confirmation times. The sender needs to wait for confirmation of the commitment. But as soon as the commitment is confirmed, double-spending is excluded already, because the sender is committed to the transaction. So the recipient does not need to wait for confirmation of the decommitment. As soon as the recipient sees the decommitment, everything is good. (If the decommitment is not confirmed, the recipient can just re-broadcast it.) In practice, we could even go further and call the transaction done after the commitment is confirmed and the sender sends the data for the second step to the recipient off-chain. Only when the recipient wants to spend the funds again, the recipient will reveal this data. The fact that double-spending is excluded after the first step is confirmed, is exactly what makes the protocol secure against quantum attackers who want to steal the money. As soon as the user reveals the ECDSA public key, a quantum attacker has access to all secrets: The attacker knows the preimage of the hash can compute the secret key. So from this point on, there is no hope that we can distinguish the honest user from the attacker. But since the correct transaction has been committed to the blockchain, and cannot be changed anymore, we don't need to distinguish the honest user from the attacker. > Either way, would you mind if I included your approach in the > article, > with credit? I will seek your review before publishing. Sure, feel free to include. You don't need to seek my review but I can certainly have a look if desired. Tim