From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id C06BFC000E for ; Fri, 9 Jul 2021 22:38:34 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id AEC544014C for ; Fri, 9 Jul 2021 22:38:34 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.599 X-Spam-Level: X-Spam-Status: No, score=-1.599 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp4.osuosl.org (amavisd-new); dkim=pass (1024-bit key) header.d=protonmail.com Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EPCOyoEDPotm for ; Fri, 9 Jul 2021 22:38:32 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-4318.protonmail.ch (mail-4318.protonmail.ch [185.70.43.18]) by smtp4.osuosl.org (Postfix) with ESMTPS id 9AA6140443 for ; Fri, 9 Jul 2021 22:38:32 +0000 (UTC) Date: Fri, 09 Jul 2021 22:38:18 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1625870309; bh=X0HtAW+uNZuNGwL3cmBzaVtsxk0Nk8fboAS8nTh0qoY=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=CWJ77NLfNKvNUuSw2B5DinaGbkOcc9/0U1/Qm48hW1M5fDZv3I6wYCA/MaclrFz3Y 1CmNSxuj9vClgVvZtyiRgft6eVp2cW7CMFNo7v9ERtM0jftW8SINt8TrfoxoclLRMs OW5n7UXYnmTSrrw//dTMZj3n6DKo4HWKd2CylJS0= To: Ethan Heilman 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 Cc: Bitcoin Protocol Discussion 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: Fri, 09 Jul 2021 22:38:34 -0000 Good morning Ethan, > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a coupl= e kilobytes)... blocksize increase cough > > Couldn't you significantly compress the signatures by using either > Winternitz OTS or by using OP_CAT to build a merkle tree so that the > full signature can be derived during script execution from a much > shorter set of seed values? To implement Winternitz we need some kind of limited-repeat construct, whic= h is not available in SCRIPT, but may be emulatable with enough `OP_IF` and= sheer brute force. But what you gain in smaller signatures, you lose in a more complex and lon= ger SCRIPT, and there are limits to SCRIPT size (in order to limit the proc= essing done in each node). Merkle signatures trade off shorter pubkeys for longer signatures (signatur= es need to provide the hash of the *other* preimage you are not revealing),= but in the modern post-SegWit Bitcoin context both pubkeys and signatures = are stored in the witness area, which have the same weight, thus it is actu= ally a loss compared to Lamport. So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy r= efers to), Merkle not so much. Regards, ZmnSCPxj > On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev > bitcoin-dev@lists.linuxfoundation.org wrote: > > > Good morning Jeremy, > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a coupl= e kilobytes)... blocksize increase cough > > Since a quantum computer can derive the EC privkey from the EC pubkey a= nd this scheme is resistant to that, I think you can use a single well-know= n EC privkey, you just need a unique Lamport keypair for each UTXO (uniquen= ess 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= make Bitcoin "quantum safe" by signing an EC signature. This should work i= n both Segwit V0 and Tapscript, although you have to use HASH160 for it to = fit in Segwit V0. > > > See my blog for the specific construction, reproduced below. > > > Yet another entry to the "OP_CAT can do that too" list. > > > Best, > > > > > > Jeremy > > > > > > ------- > > > > > > I recently published a blogpost about signing up to a5 byte value usi= ng Bitcoin script arithmetic and Lamport signatures. > > > By itself, this is neat, but a little limited. What if we could sign = longer > > > messages? If we can sign up to 20 bytes, we could sign a HASH160 dige= st which > > > is most likely quantum safe... > > > What would it mean if we signed the HASH160 digest of a signature? Wh= at the > > > what? Why would we do that? > > > Well, as it turns out, even if a quantum computer were able to crack = ECDSA, it > > > would yield revealing the private key but not the ability to malleate= the > > > content of what was actually signed. I asked my good friend and crypt= ographer > > > Madars Virza if my intuition was correct, and he > > > confirmed that it should be sufficient, but it's definitely worth clo= ser > > > analysis before relying on this. While the ECDSA signature can be mal= leated to a > > > different, negative form, if the signature is otherwise made immallea= ble there > > > should only be one value the commitment can be opened to. > > > If we required the ECDSA signature be signed with a quantum proof sig= nature > > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte sig= ning scheme > > > we discussed previously is a Lamport signature, which is quantum secu= re. > > > Unfortunately, we need at least 20 contiguous bytes... so we need som= e sort of > > > OP\_CAT like operation. > > > OP\_CAT can't be directly soft forked to Segwit v0 because it modifie= s the > > > stack, so instead we'll (for simplicity) also show how to use a new o= pcode that > > > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice = of a string > > > for equality. > > > > > > ... FOR j in 0..=3D5 > > > <0> > > > ... FOR i in 0..=3D31 > > > SWAP hash160 DUP EQUAL IF DROP <2**i> ADD EL= SE EQUALVERIFY ENDIF > > > ... END FOR > > > TOALTSTACK > > > ... END FOR > > > > > > DUP HASH160 > > > > > > ... IF CAT AVAILABLE > > > FROMALTSTACK > > > ... FOR j in 0..=3D5 > > > FROMALTSTACK > > > CAT > > > ... END FOR > > > EQUALVERIFY > > > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE > > > ... FOR j in 0..=3D5 > > > FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DR= OP DROP > > > ... END FOR > > > DROP > > > ... END IF > > > > > > CHECKSIG > > > > > > > > > That's a long script... but will it fit? We need to verify 20 bytes o= f message > > > each bit takes around 10 bytes script, an average of 3.375 bytes per = number > > > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of program = space and 21 > > > bytes of witness element per bit. > > > It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than th= e limit for > > > the rest of the logic, which is plenty (around 15-40 bytes required f= or the rest > > > of the logic, leaving 1100 free for custom signature checking). The s= tack size > > > is 160 elements for the hash gadget, 3360 bytes. > > > This can probably be made a bit more efficient by expanding to a tern= ary > > > representation. > > > > > > SWAP hash160 DUP EQUAL IF DROP ELSE <3**i>= SWAP DUP EQUAL IF DROP SUB ELSE EQUALVERIFY ADD = ENDIF ENDIF > > > > > > > > > This should bring it up to roughly 85 bytes per trit, and there shoul= d 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= radix 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 comp= uter (finding `q` > > > such that `qG =3D Q` might be trivial, but suppose key path was disab= led, then > > > finding m and p such that the taproot equation holds should be diffic= ult because > > > of the hash, but I'd need to certify that claim better). Therefore th= is > > > script can nest inside of a Tapscript path -- Tapscript also does not= impose a > > > length limit, 32 byte hashes could be used as well. > > > Further, to make keys reusable, there could be many Lamport keys comi= tted inside > > > a taproot tree so that an address could be used for thousands of time= s before > > > expiring. This could be used as a measure to protect accidental use r= ather than > > > to support it. > > > Lastly, Schnorr actually has a stronger non-malleability property tha= n ECDSA, > > > the signatures will be binding to the approved transaction and once L= amport > > > signed, even a quantum computer could not steal the funds. > > > -- > > > @JeremyRubin > > > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev