From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 277B7C000E for ; Fri, 9 Jul 2021 23:25:46 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 08BB240272 for ; Fri, 9 Jul 2021 23:25:46 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.1 X-Spam-Level: X-Spam-Status: No, score=-2.1 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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7JBX4UzQSTF3 for ; Fri, 9 Jul 2021 23:25:44 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com [IPv6:2a00:1450:4864:20::52a]) by smtp2.osuosl.org (Postfix) with ESMTPS id 930B24015F for ; Fri, 9 Jul 2021 23:25:44 +0000 (UTC) Received: by mail-ed1-x52a.google.com with SMTP id v1so16197403edt.6 for ; Fri, 09 Jul 2021 16:25:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=l85IvvPuO+YkTJgFMR1IBr/bZpDuegKDME/neQkVzEg=; b=bqNa+T4L9XTdHtNczp4aOR5TpoRaD4xepZSGiBHV3UCEAOqkI4ZX9Rj01xCTD+SuYc dZjDHI1xhvJYffYT0aJ/l8WSlPnbGpX0fiBRf+P+ErCsO/NvuTh2IaJkTz6CMQ94LlFP dzqXXt5xO9d8a1xxACSUp5h3Ujczo7EVjadlBCVDlhJu6i/iazyQS933ggT+DPEq1SvJ GWPtyD5WOKBraFDer0keiC/PZrP1wxAgiyLwQ4+6rdH7JrmvzMdRBbYpuDRdQa4Kkf5u W4IJQcXCJLmv7+RBaOYdytTy7R6cCzNRY+y7YhrmM71C8Y4uJUDPNSDuud5kT+TENjUP fTLA== 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:cc:content-transfer-encoding; bh=l85IvvPuO+YkTJgFMR1IBr/bZpDuegKDME/neQkVzEg=; b=XQmT9So4xiNV8M6RIRm2n2dqGmpsjU9fXnz4evqdHY1FrLZ4WUNazRHX1Tr1uj1AAh fI/sbsh+ekhX2f/PbutIEoYPTl0P7ADgqwG0VG8pokEOZk+jhQI1BFy5yyhijBbsjLwF on1hPMfDJaa2YHGUNRuglPf03WTuZh7V/eBdltceQ4GzgBn5toN+4Y+RVrm8pxjpIC/S 8mThz6Lyq5hXczkI1PJ4eX0gePbj09tkwfL+QAvLVjtIfGS6khcdhwo6UJ5YJudGxqq4 VG+bjDroYvTFrPjU0XS/aHaGf2gCBH0WYuniB8KsUTBCaldPsgWwp7khOK+WcWvtmhgP p8qg== X-Gm-Message-State: AOAM532N4DL6KWyVlne9SkpCSGJrZlhifJgpZ5l/w4d/i3cRmw5M1qJ0 4KaxT2u7UNE5nbZnPldeME3Qt6kzs5kz4/9XOig= X-Google-Smtp-Source: ABdhPJzJ/Cljtbd0QxiW8oRGisHjPgQxca1DKhRadbTGEBuDdZ6loWen3dIG/xfomBsKWIVTjRfRdjzvUsAEZt2iGGo= X-Received: by 2002:a05:6402:18c4:: with SMTP id x4mr21502231edy.350.1625873142745; Fri, 09 Jul 2021 16:25:42 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Ethan Heilman Date: Fri, 9 Jul 2021 19:25:06 -0400 Message-ID: To: ZmnSCPxj 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 23:25:46 -0000 >To implement Winternitz we need some kind of limited-repeat construct, whi= ch is not available in SCRIPT, but may be emulatable with enough `OP_IF` an= d sheer brute force. But what you gain in smaller signatures, you lose in a more complex and longer SCRIPT, and there are limits to SCRIPT size (in order to limit the processing done in each node). Using depth 4 Winternitz would increase the number of instructions in SCRIPT by 4*(signature bits/2) instructions, but decrease the signature size by (signature bits/2) hash preimages. Given that instructions are significantly smaller in size than the hash preimages used, it seems like this would significantly reduce total size. >Merkle signatures trade off shorter pubkeys for longer signatures (signatu= res 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 act= ually a loss compared to Lamport. I wasn't proposing using plain merkle signatures, rather I was thinking about something where if particular chunks of the message fit a pattern you could release a seed higher in the commitment tree. For instance 1,1,1 could be signed as by releasing H(01||H(01||H(01||x))), H(11||H(11||H(11||x))), H(21||H(21||H(21||x))), or by releasing X. However, you would want to only release X in that one specific case (1,1,1) but no others. Again this would bloat the SCRIPT and decrease signature size but at a favorable ratio. I am not convinced anyone should do these things, but they are fun to think about and I suspect with more thought such signature sizes and SCRIPT sizes could be even further reduced. On Fri, Jul 9, 2021 at 6:38 PM ZmnSCPxj wrote: > > Good morning Ethan, > > > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a cou= ple 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, wh= ich is not available in SCRIPT, but may be emulatable with enough `OP_IF` a= nd sheer brute force. > But what you gain in smaller signatures, you lose in a more complex and l= onger SCRIPT, and there are limits to SCRIPT size (in order to limit the pr= ocessing done in each node). > > Merkle signatures trade off shorter pubkeys for longer signatures (signat= ures need to provide the hash of the *other* preimage you are not revealing= ), but in the modern post-SegWit Bitcoin context both pubkeys and signature= s are stored in the witness area, which have the same weight, thus it is ac= tually a loss compared to Lamport. > > > So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy= refers 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 cou= ple kilobytes)... blocksize increase cough > > > Since a quantum computer can derive the EC privkey from the EC pubkey= and this scheme is resistant to that, I think you can use a single well-kn= own EC privkey, you just need a unique Lamport keypair for each UTXO (uniqu= eness 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= in both Segwit V0 and Tapscript, although you have to use HASH160 for it t= o 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 u= sing Bitcoin script arithmetic and Lamport signatures. > > > > By itself, this is neat, but a little limited. What if we could sig= n longer > > > > messages? If we can sign up to 20 bytes, we could sign a HASH160 di= gest which > > > > is most likely quantum safe... > > > > What would it mean if we signed the HASH160 digest of a signature? = What the > > > > what? Why would we do that? > > > > Well, as it turns out, even if a quantum computer were able to crac= k ECDSA, it > > > > would yield revealing the private key but not the ability to mallea= te the > > > > content of what was actually signed. I asked my good friend and cry= ptographer > > > > Madars Virza if my intuition was correct, and he > > > > confirmed that it should be sufficient, but it's definitely worth c= loser > > > > analysis before relying on this. While the ECDSA signature can be m= alleated to a > > > > different, negative form, if the signature is otherwise made immall= eable there > > > > should only be one value the commitment can be opened to. > > > > If we required the ECDSA signature be signed with a quantum proof s= ignature > > > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte s= igning scheme > > > > we discussed previously is a Lamport signature, which is quantum se= cure. > > > > Unfortunately, we need at least 20 contiguous bytes... so we need s= ome sort of > > > > OP\_CAT like operation. > > > > OP\_CAT can't be directly soft forked to Segwit v0 because it modif= ies the > > > > stack, so instead we'll (for simplicity) also show how to use a new= opcode that > > > > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splic= e 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 = ELSE 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 = DROP DROP > > > > ... END FOR > > > > DROP > > > > ... END IF > > > > > > > > CHECKSIG > > > > > > > > > > > > That's a long script... but will it fit? We need to verify 20 bytes= of message > > > > each bit takes around 10 bytes script, an average of 3.375 bytes pe= r number > > > > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of progra= m space and 21 > > > > bytes of witness element per bit. > > > > It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than = the limit for > > > > the rest of the logic, which is plenty (around 15-40 bytes required= for the 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 te= rnary > > > > representation. > > > > > > > > SWAP hash160 DUP EQUAL IF DROP ELSE <3**= i> SWAP DUP EQUAL IF DROP SUB ELSE EQUALVERIFY AD= D ENDIF ENDIF > > > > > > > > > > > > This should bring it up to roughly 85 bytes per trit, and there sho= uld 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 c= omputer (finding `q` > > > > such that `qG =3D Q` might be trivial, but suppose key path was dis= abled, then > > > > finding m and p such that the taproot equation holds should be diff= icult because > > > > of the hash, but I'd need to certify that claim better). Therefore = this > > > > script can nest inside of a Tapscript path -- Tapscript also does n= ot impose a > > > > length limit, 32 byte hashes could be used as well. > > > > Further, to make keys reusable, there could be many Lamport keys co= mitted inside > > > > a taproot tree so that an address could be used for thousands of ti= mes before > > > > expiring. This could be used as a measure to protect accidental use= rather than > > > > to support it. > > > > Lastly, Schnorr actually has a stronger non-malleability property t= han ECDSA, > > > > the signatures will be binding to the approved transaction and once= Lamport > > > > 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 > >