public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Jeremy <jlrubin@mit.edu>
To: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org>
Subject: [bitcoin-dev] CheckSigFromStack for Arithmetic Values
Date: Fri, 2 Jul 2021 15:20:16 -0700	[thread overview]
Message-ID: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com> (raw)

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

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
```

In order to sign a 16 bit value V, the owner of K simply puts on the stack
the
binary representation of V indexed into the K. E.g., to sign `53593`, first
expand to binary `0b1101000101011001`, then put the appropriate K values on
the
stack.

```
K_15_1
K_14_1
K_13_0
K_12_1
K_11_0
K_10_0
K_9_0
K_8_1
K_7_0
K_6_1
K_5_0
K_4_1
K_3_1
K_2_0
K_1_0
K_0_1
<sig>
```


This technique is kind of bulky! It's around 80x16 = 1280 length for the
gadget, and 528 bytes for the witnesses. So it is _doable_, if not a bit
expensive. There might be some more efficient scripts for this -- would a
trinary representation be more efficient?

The values that can be signed can be range limited either post-hoc (using
OP\_WITHIN) or internally as was done with the 16 bit value circuit where
it's
impossible to do more than 16 bits.

Keys *can* be reused across scripts, but signatures may only be constructed
one
time because a third party could take two signed messages and construct an
unintended value (e.g., if you sign both 4 and 2 then a third party could
construct 6).

There are certain applications where this could be used for an effect -- for
example, an oracle might have a bonding contract whereby possessing any
K\_i\_0
and K\_i\_1 allows the burning of funds.

--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>

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

             reply	other threads:[~2021-07-02 22:20 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-07-02 22:20 Jeremy [this message]
2021-07-02 23:58 ` [bitcoin-dev] CheckSigFromStack for Arithmetic Values ZmnSCPxj
2021-07-03  4:01   ` Jeremy
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='CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com' \
    --to=jlrubin@mit.edu \
    --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