Date: Sun, 04 Jul 2021 00:22:18 +0000
To: Erik Aronesty <erik@q32.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <5g9bzPMinzlRiQhDmlVBo1OQyR516-RABcphP1QiiLBbS47dZwvz_ufqLndLcUZL4OApEZvP60k4hliVuK50lEJkN1qY0QppKx2uUXpEkLY=@protonmail.com>
In-Reply-To: <CAJowKgJxsknJ_TnQU1bvz3VyBHFaykXjDQAfsnxSzoeE1KJhbw@mail.gmail.com>
References: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
 <YEsEkExygpn5zEqfCXSt8duo9C0tgyx9YBTRejVn8ccwX2SQCPQVP5r2Nav6isQIbK8ED2Z-fYNwcN0VhXpxAIhCd3TWeU1et85cZFIVWdA=@protonmail.com>
 <CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com>
 <CAJowKgJxsknJ_TnQU1bvz3VyBHFaykXjDQAfsnxSzoeE1KJhbw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values
Precedence: list

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 <bitcoin-dev@lists=
.linuxfoundation.org> 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 <ZmnSCPxj@protonmail.com> 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:
> > > > ```
> > > > <pk> checksigverify
> > > > 0
> > > > SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQ=
UALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD ELSE <H(K_1_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD ELSE <H(K_3_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD ELSE <H(K_4_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD ELSE <H(K_5_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD ELSE <H(K_6_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD ELSE <H(K_7_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD ELSE <H(K_8_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD ELSE <H(K_9_0)>=
 EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> ADD ELSE <H(K_10_=
0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> ADD ELSE <H(K_11_=
0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> ADD ELSE <H(K_12_=
0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> ADD ELSE <H(K_13_=
0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> ADD ELSE <H(K_14_=
0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> ADD ELSE <H(K_15_=
0)> 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..=
..
> > >
> > > > ```
> > > > <pk> checksigverify
> > > > 0
> > > > SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQ=
UALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <2> ADD ELSE <H(K_1_0)> EQ=
UALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <4> ADD ELSE <H(K_2_0)> EQ=
UALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <8> ADD ELSE <H(K_3_0)> EQ=
UALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <16> ADD ELSE <H(K_4_0)> E=
QUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <32> ADD ELSE <H(K_5_0)> E=
QUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <64> ADD ELSE <H(K_6_0)> E=
QUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <128> ADD ELSE <H(K_7_0)> =
EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <256> ADD ELSE <H(K_8_0)> =
EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <512> ADD ELSE <H(K_9_0)> =
EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1024> ADD ELSE <H(K_10_0=
)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <2048> ADD ELSE <H(K_11_0=
)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <4096> ADD ELSE <H(K_12_0=
)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <8192> ADD ELSE <H(K_13_0=
)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <16384> ADD ELSE <H(K_14_=
0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <32768> ADD ELSE <H(K_15_=
0)> 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