Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3878EC000E for ; Fri, 2 Jul 2021 23:58:25 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 1ADD8400EF for ; Fri, 2 Jul 2021 23:58:25 +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: smtp2.osuosl.org (amavisd-new); dkim=pass (1024-bit key) header.d=protonmail.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 cxKcX-Uv0pVK for ; Fri, 2 Jul 2021 23:58:22 +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 smtp2.osuosl.org (Postfix) with ESMTPS id 9A75D40259 for ; Fri, 2 Jul 2021 23:58:22 +0000 (UTC) Date: Fri, 02 Jul 2021 23:58:14 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1625270299; bh=BwmJK0ioikbQymotCRGL3brfF8yJ2QLMPQYm95+Elm8=; h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From; b=FNzdIFNoCZvb+M/s1JC1hGY9a8clto8XQ/rBnJdl7swvsUjRJxA13CmvtSnvj3RBF W3dGuhm+srlYMaHE7exA2CIr6sH1JoyLYsJN9kNQDtKsv2+ECxmFnuGo0LCWiXWOqX fws3K0DLk1D+RsvAL8ybpGaqWsQWZDNk8vUysPy8= 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] 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, 02 Jul 2021 23:58:25 -0000 Good morning Jeremy, > Dear Bitcoin Devs, > > It recently occurred to me that it's possible to do a lamport signature i= n script for arithmetic values by using a binary expanded representation. T= here are some applications that might benefit from this and I don't recall = seeing it discussed elsewhere, but would be happy for a citation/reference = to the technique. > > blog post here, https://rubin.io/blog/2021/07/02/signing-5-bytes/, text r= eproduced 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 script: > ```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[Hash, Has= h]]): > =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[idx][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 pa= irs 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 preimage 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 EQUALVER= IFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<1> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<2> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<3> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<4> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<5> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<6> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<7> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<8> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<9> ADD ELSE EQUAL= VERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<10> ADD ELSE EQ= UALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<11> ADD ELSE EQ= UALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<12> ADD ELSE EQ= UALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<13> ADD ELSE EQ= UALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<14> ADD ELSE EQ= UALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1<<15> ADD ELSE EQ= UALVERIFY 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 confus= ing --- at first I thought you were pushing some kind of nested SCRIPT repr= esentation, but in any case, replacing it with the actual numbers is a litt= le less confusing on the syntax front, and I think (hope?) most people 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 EQUALVER= IFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <2> ADD ELSE EQUALVER= IFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <4> ADD ELSE EQUALVER= IFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <8> ADD ELSE EQUALVER= IFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <16> ADD ELSE EQUALVE= RIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <32> ADD ELSE EQUALVE= RIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <64> ADD ELSE EQUALVE= RIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <128> ADD ELSE EQUALV= ERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <256> ADD ELSE EQUALV= ERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <512> ADD ELSE EQUALV= ERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <1024> ADD ELSE EQU= ALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <2048> ADD ELSE EQU= ALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <4096> ADD ELSE EQU= ALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <8192> ADD ELSE EQU= ALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <16384> ADD ELSE EQ= UALVERIFY ENDIF > SWAP sha256 DUP EQUAL IF DROP <32768> ADD ELSE EQ= UALVERIFY ENDIF > CHECKSEQUENCEVERIFY > ``` On the other hand LOL WTF, this is cool. Basically you are showing that if we enable something as innocuous as `OP_A= DD`, we can implement Lamport signatures for **arbitrary** values represent= able in small binary numbers (16 bits in the above example). I was thinking "why not Merkle signatures" since the pubkey would be much s= maller but the signature would be much larger, but (a) the SCRIPT would be = much more complicated and (b) in modern Bitcoin, the above SCRIPT would be = in the witness stack anyway so there is no advantage to pushing the size to= wards the signature rather than the pubkey, they all have the same weight, = and since both Lamport and Merkle are single-use-only and we do not want to= encourage pubkey reuse even if they were not, the Merkle has much larger s= ignature size, so Merkle sigs end up more expensive. Regards, ZmnSCPxj