Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 5D040C000E for ; Sun, 4 Jul 2021 00:22:28 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 3644B827D2 for ; Sun, 4 Jul 2021 00:22:28 +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_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 8_RSQPV27dGO for ; Sun, 4 Jul 2021 00:22:26 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-40130.protonmail.ch (mail-40130.protonmail.ch [185.70.40.130]) by smtp1.osuosl.org (Postfix) with ESMTPS id 4D8CB802BB for ; Sun, 4 Jul 2021 00:22:26 +0000 (UTC) Date: Sun, 04 Jul 2021 00:22:18 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1625358143; bh=AzXd1iHLjFo0y2WoQLuhqlJZpMtpd277+qtL+1pj9do=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=BAwf5dfI/dHpAvFc8VK35QqAbBp76zqlesu3zSFIkiOWET4Ky5x9Kb84IhR1Zg0gS c9TFGN2TAUQIwGF5R1jj7tpvOGPhJxQilEMap1UhQZWX6wTHqdX/Lz3EtAL4hJsodL qOCCcqs5kaRzUHrFWcE1IrrwdtUJj27cwpSi69UU= To: Erik Aronesty From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: <5g9bzPMinzlRiQhDmlVBo1OQyR516-RABcphP1QiiLBbS47dZwvz_ufqLndLcUZL4OApEZvP60k4hliVuK50lEJkN1qY0QppKx2uUXpEkLY=@protonmail.com> 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] 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: Sun, 04 Jul 2021 00:22:28 -0000 Good morning Erik, > i may be ignorant here but i have a question: > > Given that schnorr signatures now allow signers to perform complex arithm= etic signing operations out-of-band using their own communications techniqu= es, couldn't you just perform the publishing and accumulation of these sign= ature components without using a bitcoin script? > > In other=C2=A0words, push the effort of combination and computation off o= f the bitcoin network and nodes. Actually the post is not about *doing* Arithmetic using signing operations,= it is about enabling signing operations *at all* using arithmetic operatio= n `OP_ADD`. Jeremy in the initial post is not doing arithmetic, he is using arithmetic = to implement Lamport signatures (which cannot support arithmetic signing op= erations anyway, being a hash-based signing scheme). The "for" arithmetic here is largely to mean that this cleverness allows an= implementation of `OP_CHECKSIGFROMSTACK`, using arithmetic operation `OP_A= DD`. To my mind this cleverness is more of an argument against ever enabling `OP= _ADD` and friends, LOL. This is more of a "bad but ridiculously clever thing" post than a "Bitcoin = should totally use this thing" post. Regards, ZmnSCPxj > > On Sat, Jul 3, 2021 at 12:01 AM Jeremy via bitcoin-dev wrote: > > > Yep -- sorry for the confusing notation but seems like you got it. C++ = templates have this issue too btw :) > > > > One cool thing is that if you have op_add for arbitrary width integers = or op_cat you can also make a quantum proof signature by signing the signat= ure made with checksig with the lamport. > > > > There are a couple gotchas wrt crypto assumptions on that but I'll writ= e it up soon =F0=9F=99=82 it also works better in segwit V0 because there's= no keypath spend -- that breaks the quantum proofness of this scheme. > > > > On Fri, Jul 2, 2021, 4:58 PM ZmnSCPxj wrote: > > > > > Good morning Jeremy, > > > > > > > Dear Bitcoin Devs, > > > > > > > > It recently occurred to me that it's possible to do a lamport signa= ture in script for arithmetic values by using a binary expanded representat= ion. There are some applications that might benefit from this and I don't r= ecall seeing it discussed elsewhere, but would be happy for a citation/refe= rence to the technique. > > > > > > > > blog post here, https://rubin.io/blog/2021/07/02/signing-5-bytes/, = text reproduced below > > > > > > > > There are two insights in this post: > > > > 1. to use a bitwise expansion of the number > > > > 2. to use a lamport signature > > > > Let's look at the code in python and then translate to bitcoin scri= pt: > > > > ```python > > > > def add_bit(idx, preimage, image_0, image_1): > > > > =C2=A0 =C2=A0 s =3D sha256(preimage) > > > > =C2=A0 =C2=A0 if s =3D=3D image_1: > > > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 return (1 << idx) > > > > =C2=A0 =C2=A0 if s =3D=3D image_0: > > > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 return 0 > > > > =C2=A0 =C2=A0 else: > > > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 assert False > > > > def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Has= h, Hash]]): > > > > =C2=A0 =C2=A0 acc =3D 0 > > > > =C2=A0 =C2=A0 for (idx, preimage) in enumerate(witnesses): > > > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 acc +=3D add_bit(idx, preimage, keys[id= x][0], keys[idx][1]) > > > > =C2=A0 =C2=A0 return x > > > > ``` > > > > So what's going on here? The signer generates a key which is a list= of pairs of > > > > hash images to create the script. > > > > To sign, the signer provides a witness of a list of preimages that = match one or the other. > > > > During validation, the network adds up a weighted value per preimag= e and checks > > > > that there are no left out values. > > > > Let's imagine a concrete use case: I want a third party to post-hoc= sign a sequence lock. This is 16 bits. > > > > I can form the following script: > > > > ``` > > > > checksigverify > > > > 0 > > > > SWAP sha256 DUP EQUAL IF DROP <1> ADD ELSE EQ= UALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<1> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<2> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<3> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<4> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<5> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<6> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<7> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<8> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<9> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<10> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<11> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<12> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<13> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<14> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1<<15> ADD ELSE EQUALVERIFY ENDIF > > > > CHECKSEQUENCEVERIFY > > > > ``` > > > > > > This took a bit of thinking to understand, mostly because you use the= `<<` operator in a syntax that uses `< >` as delimiters, which was mildly = confusing --- at first I thought you were pushing some kind of nested SCRIP= T representation, but in any case, replacing it with the actual numbers is = a little less confusing on the syntax front, and I think (hope?) most peopl= e who can understand `1<<1` have also memorized the first few powers of 2..= .. > > > > > > > ``` > > > > checksigverify > > > > 0 > > > > SWAP sha256 DUP EQUAL IF DROP <1> ADD ELSE EQ= UALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <2> ADD ELSE EQ= UALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <4> ADD ELSE EQ= UALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <8> ADD ELSE EQ= UALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <16> ADD ELSE E= QUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <32> ADD ELSE E= QUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <64> ADD ELSE E= QUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <128> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <256> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <512> ADD ELSE = EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <1024> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <2048> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <4096> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <8192> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <16384> ADD ELSE EQUALVERIFY ENDIF > > > > SWAP sha256 DUP EQUAL IF DROP <32768> ADD ELSE EQUALVERIFY ENDIF > > > > CHECKSEQUENCEVERIFY > > > > ``` > > > > > > On the other hand LOL WTF, this is cool. > > > > > > Basically you are showing that if we enable something as innocuous as= `OP_ADD`, we can implement Lamport signatures for **arbitrary** values rep= resentable in small binary numbers (16 bits in the above example). > > > > > > I was thinking "why not Merkle signatures" since the pubkey would be = much smaller but the signature would be much larger, but (a) the SCRIPT wou= ld be much more complicated and (b) in modern Bitcoin, the above SCRIPT wou= ld be in the witness stack anyway so there is no advantage to pushing the s= ize towards the signature rather than the pubkey, they all have the same we= ight, and since both Lamport and Merkle are single-use-only and we do not w= ant to encourage pubkey reuse even if they were not, the Merkle has much la= rger signature size, so Merkle sigs end up more expensive. > > > > > > Regards, > > > ZmnSCPxj > > > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev