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 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: >> > ``` >> > checksigverify >> > 0 >> > SWAP sha256 DUP EQUAL IF DROP <1> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<1> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<2> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<3> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<4> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<5> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<6> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<7> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<8> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<9> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<10> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<11> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<12> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<13> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<14> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1<<15> ADD ELSE >> 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.... >> >> > ``` >> > checksigverify >> > 0 >> > SWAP sha256 DUP EQUAL IF DROP <1> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <2> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <4> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <8> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <16> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <32> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <64> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <128> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <256> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <512> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <1024> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <2048> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <4096> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <8192> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <16384> ADD ELSE >> EQUALVERIFY ENDIF >> > SWAP sha256 DUP EQUAL IF DROP <32768> ADD ELSE >> 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 >