Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values

[ZmnSCPxj <ZmnSCPxj@protonmail.com>]

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