path: root/f5/c6bb89e2fcb60f3faa55d98e147bbc15b3e42a

Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 3878EC000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <jlrubin@mit.edu>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <YEsEkExygpn5zEqfCXSt8duo9C0tgyx9YBTRejVn8ccwX2SQCPQVP5r2Nav6isQIbK8ED2Z-fYNwcN0VhXpxAIhCd3TWeU1et85cZFIVWdA=@protonmail.com>
In-Reply-To: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
References: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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:
> ```
> <pk> checksigverify
> 0
> SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD ELSE <H(K_1_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD ELSE <H(K_3_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD ELSE <H(K_4_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD ELSE <H(K_5_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD ELSE <H(K_6_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD ELSE <H(K_7_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD ELSE <H(K_8_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD ELSE <H(K_9_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> ADD ELSE <H(K_10_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> ADD ELSE <H(K_11_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> ADD ELSE <H(K_12_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> ADD ELSE <H(K_13_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> ADD ELSE <H(K_14_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> ADD ELSE <H(K_15_0)> 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....

> ```
> <pk> checksigverify
> 0
> SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <2> ADD ELSE <H(K_1_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <4> ADD ELSE <H(K_2_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <8> ADD ELSE <H(K_3_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <16> ADD ELSE <H(K_4_0)> EQUALVE=
RIFY ENDIF
> SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <32> ADD ELSE <H(K_5_0)> EQUALVE=
RIFY ENDIF
> SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <64> ADD ELSE <H(K_6_0)> EQUALVE=
RIFY ENDIF
> SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <128> ADD ELSE <H(K_7_0)> EQUALV=
ERIFY ENDIF
> SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <256> ADD ELSE <H(K_8_0)> EQUALV=
ERIFY ENDIF
> SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <512> ADD ELSE <H(K_9_0)> EQUALV=
ERIFY ENDIF
> SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1024> ADD ELSE <H(K_10_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <2048> ADD ELSE <H(K_11_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <4096> ADD ELSE <H(K_12_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <8192> ADD ELSE <H(K_13_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <16384> ADD ELSE <H(K_14_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <32768> ADD ELSE <H(K_15_0)> 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