public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Jeremy <jlrubin@mit.edu>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values
Date: Fri, 2 Jul 2021 21:01:01 -0700	[thread overview]
Message-ID: <CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com> (raw)
In-Reply-To: <YEsEkExygpn5zEqfCXSt8duo9C0tgyx9YBTRejVn8ccwX2SQCPQVP5r2Nav6isQIbK8ED2Z-fYNwcN0VhXpxAIhCd3TWeU1et85cZFIVWdA=@protonmail.com>

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

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
>

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

  reply	other threads:[~2021-07-03  4:01 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-07-02 22:20 [bitcoin-dev] CheckSigFromStack for Arithmetic Values Jeremy
2021-07-02 23:58 ` ZmnSCPxj
2021-07-03  4:01   ` Jeremy [this message]
2021-07-03 11:31     ` Erik Aronesty
2021-07-04  0:22       ` ZmnSCPxj
2021-07-04 13:10         ` ZmnSCPxj

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com \
    --to=jlrubin@mit.edu \
    --cc=ZmnSCPxj@protonmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox