Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 8B772C000E for ; Thu, 8 Jul 2021 08:12:13 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 7384083104 for ; Thu, 8 Jul 2021 08:12:13 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: 0.4 X-Spam-Level: X-Spam-Status: No, score=0.4 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, URIBL_SBL_A=0.1] autolearn=ham autolearn_force=no Authentication-Results: smtp1.osuosl.org (amavisd-new); dkim=pass (1024-bit key) header.d=protonmail.com Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id mMb8ZcgsdojT for ; Thu, 8 Jul 2021 08:12:10 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-4324.protonmail.ch (mail-4324.protonmail.ch [185.70.43.24]) by smtp1.osuosl.org (Postfix) with ESMTPS id D45F382F6F for ; Thu, 8 Jul 2021 08:12:09 +0000 (UTC) Date: Thu, 08 Jul 2021 08:12:01 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1625731926; bh=LqyRtd/90F1VNDq832MSuVP5f968NbeoRR4FEM4X610=; h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From; b=j7moGfRymXOMhpYHucrXZe4O86WKSG3f1qwFWN5e6FGDdiwEXuN6N1m7GHi9tc6hY 3PRd4hmkCRTygZBtR+vP7K/E4vlX4EX7L8NpVkMRhQnhZrg68t5eXay/JKCCvYBgGd 2sCuRIlTrlRSGmVxH447ra5PaYkALMak6qHJZV+4= To: Jeremy , Bitcoin Protocol Discussion From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values] X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 08 Jul 2021 08:12:13 -0000 Good morning Jeremy, Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple ki= lobytes)... blocksize increase *cough* Since a quantum computer can derive the EC privkey from the EC pubkey and t= his scheme is resistant to that, I think you can use a single well-known EC= privkey, you just need a unique Lamport keypair for each UTXO (uniqueness = being mandatory due to Lamport requiring preimage revelation). Regards, ZmnSCPxj > Dear Bitcoin Devs, > > As mentioned previously, OP_CAT (or similar operation) can be used to mak= e Bitcoin "quantum safe" by signing an EC signature. This should work in bo= th Segwit V0 and Tapscript, although you have to use HASH160 for it to fit = in Segwit V0. > > See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for the = specific construction, reproduced below. > > Yet another entry to the "OP_CAT can do that too" list. > > Best, > > Jeremy > ----- > > I recently published [a blog > post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about signing up= to a > 5 byte value using Bitcoin script arithmetic and Lamport signatures. > > By itself, this is neat, but a little limited. What if we could sign long= er > messages? If we can sign up to 20 bytes, we could sign a HASH160 digest w= hich > is most likely quantum safe... > > What would it mean if we signed the HASH160 digest of a signature? What t= he > what? Why would we do that? > > Well, as it turns out, even if a quantum computer were able to crack ECDS= A, it > would yield revealing the private key but not the ability to malleate the > content of what was actually signed.=C2=A0 I asked my good friend and cry= ptographer > [Madars Virza](https://madars.org/) if my intuition was correct, and he > confirmed that it should be sufficient, but it's definitely worth closer > analysis before relying on this. While the ECDSA signature can be malleat= ed to a > different, negative form, if the signature is otherwise made immalleable = there > should only be one value the commitment can be opened to. > > If we required the ECDSA signature be signed with a quantum proof signatu= re > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing= scheme > we discussed previously is a Lamport signature, which is quantum secure. > Unfortunately, we need at least 20 contiguous bytes... so we need some so= rt of > OP\_CAT like operation. > > OP\_CAT can't be directly soft forked to Segwit v0 because it modifies th= e > stack, so instead we'll (for simplicity) also show how to use a new opcod= e that > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a= string > for equality. > > ``` > ... FOR j in 0..=3D5 > =C2=A0 =C2=A0 <0> > =C2=A0 =C2=A0 ... FOR i in 0..=3D31 > =C2=A0 =C2=A0 =C2=A0 =C2=A0 SWAP hash160 DUP EQUAL IF DROP <= 2**i> ADD ELSE EQUALVERIFY ENDIF > =C2=A0 =C2=A0 ... END FOR > =C2=A0 =C2=A0 TOALTSTACK > ... END FOR > > DUP HASH160 > > ... IF CAT AVAILABLE > =C2=A0 =C2=A0 FROMALTSTACK > =C2=A0 =C2=A0 ... FOR j in 0..=3D5 > =C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK > =C2=A0 =C2=A0 =C2=A0 =C2=A0 CAT > =C2=A0 =C2=A0 ... END FOR > =C2=A0 =C2=A0 EQUALVERIFY > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE > =C2=A0 =C2=A0 ... FOR j in 0..=3D5 > =C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVE= RIFY DROP DROP DROP > =C2=A0 =C2=A0 ...=C2=A0 END FOR > =C2=A0 =C2=A0 DROP > ... END IF > > CHECKSIG > ``` > > That's a long script... but will it fit? We need to verify 20 bytes of me= ssage > each bit takes around 10 bytes script, an average of 3.375 bytes per numb= er > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of program spac= e and 21 > bytes of witness element per bit. > > It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than the li= mit for > the rest of the logic, which is plenty (around 15-40 bytes required for t= he rest > of the logic, leaving 1100 free for custom signature checking). The stack= size > is 160 elements for the hash gadget, 3360 bytes. > > This can probably be made a bit more efficient by expanding to a ternary > representation. > > ``` > =C2=A0 =C2=A0 =C2=A0 =C2=A0 SWAP hash160 DUP EQUAL =C2=A0IF = DROP =C2=A0ELSE <3**i> SWAP DUP EQUAL IF DROP SUB ELSE EQUALVERIFY ADD =C2=A0ENDIF ENDIF > ``` > > This should bring it up to roughly 85 bytes per trit, and there should be= 101 > trits (`log(2**160)/log(3) =3D=3D 100.94`), so about 8560 bytes... a bit = cheaper! > But the witness stack is "only" `2121` bytes... > > As a homework exercise, maybe someone can prove the optimal choice of rad= ix for > this protocol... My guess is that base 4 is optimal! > > ## Taproot? > > What about Taproot? As far as I'm aware the commitment scheme (`Q =3D pG = + hash(pG > || m)G`) can be securely opened to m even with a quantum computer (findin= g `q` > such that `qG =3D Q` might be trivial, but suppose key path was disabled,= then > finding m and p such that the taproot equation holds should be difficult = because > of the hash, but I'd need to certify that claim better).=C2=A0 Therefore = this > script can nest inside of a Tapscript path -- Tapscript also does not imp= ose a > length limit, 32 byte hashes could be used as well. > > Further, to make keys reusable, there could be many Lamport keys comitted= inside > a taproot tree so that an address could be used for thousands of times be= fore > expiring. This could be used as a measure to protect accidental use rathe= r than > to support it. > > Lastly, Schnorr actually has a stronger non-malleability property than EC= DSA, > the signatures will be binding to the approved transaction and once Lampo= rt > signed, even a quantum computer could not steal the funds. > > -- > @JeremyRubin