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 > <[email protected]> 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 <[email protected]> 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 > > [email protected] > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev _______________________________________________ bitcoin-dev mailing list [email protected] https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
