Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values

From: Erik Aronesty <erik@q32•com>
To: Jeremy <jlrubin@mit•edu>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values
Date: Sat, 3 Jul 2021 07:31:04 -0400	[thread overview]
Message-ID: <CAJowKgJxsknJ_TnQU1bvz3VyBHFaykXjDQAfsnxSzoeE1KJhbw@mail.gmail.com> (raw)
In-Reply-To: <CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 7738 bytes --]

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.

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
>

[-- Attachment #2: Type: text/html, Size: 9597 bytes --]