Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values

[ZmnSCPxj <ZmnSCPxj@protonmail.com>]

Good morning Erik,

> i may be ignorant here but i have a question:
>
> Given that schnorr signatures now allow signers to perform complex arithmetic signing operations out-of-band using their own communications techniques, couldn't you just perform the publishing and accumulation of these signature components without using a bitcoin script?
>
> In other words, push the effort of combination and computation off of 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 operation `OP_ADD`.
Jeremy in the initial post is not doing arithmetic, he is using arithmetic to implement Lamport signatures (which cannot support arithmetic signing operations 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_ADD`.

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 signature made with checksig with the lamport.
> >
> > There are a couple gotchas wrt crypto assumptions on that but I'll write it up soon 🙂 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 signature in script for arithmetic values by using a binary expanded representation. There 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 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 script:
> > > > ```python
> > > > def add_bit(idx, preimage, image_0, image_1):
> > > >     s = sha256(preimage)
> > > >     if s == image_1:
> > > >         return (1 << idx)
> > > >     if s == image_0:
> > > >         return 0
> > > >     else:
> > > >         assert False
> > > > def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Hash, Hash]]):
> > > >     acc = 0
> > > >     for (idx, preimage) in enumerate(witnesses):
> > > >         acc += add_bit(idx, preimage, keys[idx][0], keys[idx][1])
> > > >     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 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)> EQUALVERIFY 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 SCRIPT 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 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)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <2> ADD ELSE <H(K_1_0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <4> ADD ELSE <H(K_2_0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <8> ADD ELSE <H(K_3_0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <16> ADD ELSE <H(K_4_0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <32> ADD ELSE <H(K_5_0)> EQUALVERIFY ENDIF
> > > > SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <64> ADD ELSE <H(K_6_0)> EQUALVERIFY 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 representable 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 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 towards 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 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