Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[Ethan Heilman via bitcoin-dev]

>To implement Winternitz we need some kind of limited-repeat construct, which 
>is not available in SCRIPT, but may be emulatable with enough `OP_IF` and 
>sheer brute force.
But what you gain in smaller signatures, you lose in a more complex
and longer SCRIPT, and there are limits to SCRIPT size (in order to
limit the processing done in each node).

Using depth 4 Winternitz would increase the number of instructions in
SCRIPT by 4*(signature bits/2) instructions, but decrease the
signature size by (signature bits/2) hash preimages. Given that
instructions are significantly smaller in size than the hash preimages
used, it seems like this would significantly reduce total size.

>Merkle signatures trade off shorter pubkeys for longer signatures (signatures 
>need to provide the hash of the *other* preimage you are not revealing), but 
>in the modern post-SegWit Bitcoin context both pubkeys and signatures are 
>stored in the witness area, which have the same weight, thus it is actually a 
>loss compared to Lamport.

I wasn't proposing using plain merkle signatures, rather I was
thinking about something where if particular chunks of the message fit
a pattern you could release a seed higher in the commitment tree. For
instance 1,1,1 could be signed as by releasing H(01||H(01||H(01||x))),
 H(11||H(11||H(11||x))), H(21||H(21||H(21||x))), or by releasing X.
However, you would want to only release X in that one specific case
(1,1,1) but no others. Again this would bloat the SCRIPT and decrease
signature size but at a favorable ratio.

I am not convinced anyone should do these things, but they are fun to
think about and I suspect with more thought such signature sizes and
SCRIPT sizes could be even further reduced.

On Fri, Jul 9, 2021 at 6:38 PM ZmnSCPxj  wrote:
>
> Good morning Ethan,
>
> > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple 
> > > kilobytes)... blocksize increase cough
> >
> > Couldn't you significantly compress the signatures by using either
> > Winternitz OTS or by using OP_CAT to build a merkle tree so that the
> > full signature can be derived during script execution from a much
> > shorter set of seed values?
>
> To implement Winternitz we need some kind of limited-repeat construct, which 
> is not available in SCRIPT, but may be emulatable with enough `OP_IF` and 
> sheer brute force.
> But what you gain in smaller signatures, you lose in a more complex and 
> longer SCRIPT, and there are limits to SCRIPT size (in order to limit the 
> processing done in each node).
>
> Merkle signatures trade off shorter pubkeys for longer signatures (signatures 
> need to provide the hash of the *other* preimage you are not revealing), but 
> in the modern post-SegWit Bitcoin context both pubkeys and signatures are 
> stored in the witness area, which have the same weight, thus it is actually a 
> loss compared to Lamport.
>
>
> So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy 
> refers to), Merkle not so much.
>
> Regards,
> ZmnSCPxj
>
> > On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
> > bitcoin-dev@lists.linuxfoundation.org wrote:
> >
> > > Good morning Jeremy,
> > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple 
> > > kilobytes)... blocksize increase cough
> > > Since a quantum computer can derive the EC privkey from the EC pubkey and 
> > > this scheme is resistant to that, I think you can use a single well-known 
> > > EC privkey, you just need a unique Lamport keypair for each UTXO 
> > > (uniqueness being mandatory due to Lamport requiring preimage revelation).
> > > Regards,
> > > ZmnSCPxj
> > >
> > > > Dear Bitcoin Devs,
> > > > As mentioned previously, OP_CAT (or similar operation) can be used to 
> > > > make Bitcoin "quantum safe" by signing an EC signature. This should 
> > > > work in both Segwit V0 and Tapscript, although you have to use HASH160 
> > > > for it to fit in Segwit V0.
> > > > See my blog for the specific construction, reproduced below.
> > > > Yet another entry to the "OP_CAT can do that too" list.
> > > > Best,
> > > >
> > > > Jeremy
> > > >
> > > > ---
> > > >
> > > > I recently published a blogpost about signing up to a5 byte value using 
> > > > Bitcoin script arithmetic and Lamport signatures.
> > > > By itself, this is neat, but a little limited. What if we could sign 
> > > > longer
> > > > messages? If we can sign up to 20 bytes, we could sign a HASH160 digest 
> > > > which
> > > > is most likely quantum safe...
> > > > What would it mean if we signed the HASH160 digest of a signature? What 
> > > > the
> > > > what? Why would we do that?
> > > > Well, as it turns out, even if a quantum computer were able to crack 
> > > > ECDSA, it
> > > > would yield revealing the private key but not the ability to malleate 
> > > > the
> > > > content of what was actually signed. I asked my good friend and 
> > > > cryptographer
> > > > Madars Virza if my intuition was correct, and he
> > > > 

Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[Jeremy via bitcoin-dev]

I thought about this, but at the time of writing I couldn't come up with
something I thought was substantially better. I spent a few more cycles
thinking on it -- you can definitely do better. It's not clear how much
better Winternitz might be, or if it would be secure in this context?
Here's some exploration...

maybe you can do something like:

   || IF SWAP HASH SWAP ELSE HASH FROMALTSTACK
<2**n> TOALTSTACK ADD ENDIF CAT

you can process this (assume HASH160) into chunks of 26 bits, cat them all
together, and then stash that hash. You would need 6 gadgets, and then 1
overflow + 4 bare hashes for the final key hash (e.g. your tree looks like)
H(H(26x20) || H(26x20)...H(bit)|| H(bit) || H(bit) || H(bit)). It doesn't
make sense to have a "nice" merkle tree, just fit in as much data as
possible per call (520 bytes). If OP_SHASTREAM, this is even better since
you can ignore structuring...

This would bring your cost down by about 20 bytes per bit, for 160 bits, so
around a savings of 3200 bytes... not bad! 1/3 cheaper.

Script is about 15x160 = 2400 and change, witness is 43x160 = 6880

If you were to convert to 3-ary, you could cut this down to 101 gates with
a script like:

witnesses:
<0> 
 <1> 
  <2> 

script:
HASH SWAP
IFDUP
NOTIF# 0 passed in (0)
SWAP CAT
ELSE
<3**n> TOALT
1SUB
IF # 2 passed in (+1)
FROMALT # do nothing
ELSE # 1 passed in (T)
SWAP # Swaps H(xT) to back
FROMALT NEGATE # negate
END
FROMALT ADD TOALT # add to accumulator
ENDIF
CAT


you would end up having to publish ~64x101 data in the witness, so only
6464 total (and about 24x101 = 2424 and change for the script)

Making the script smaller also means that choice of hash160/sha256 doesn't
change script size much, just witness. And the witnesses are free to
provide their own preimages, so it would be OK to use something > 20 bytes,
< 32 for more variable security/length tradeoff.


At the cost of marginally bigger script (by about 6x101 bytes), you can
save 20x101 off the witness stack by making each key H(H(xT) || H(x0)) ||
H(x1). 43x101 + 30x101 = 7373 + change for the final grouping.

witnesses:
<0> 
  <1> 
  <2> 

script:
HASH SWAP
IFDUP
NOTIF# 0 passed in (0)
ROT SWAP CAT HASH
ELSE
<3**n> TOALT
1SUB
IF # 2 passed in (+1)
FROMALT # do nothing
ELSE # 1 passed in (T)
TOALTSTACK CAT HASH FROMALTSTACK SWAP # Swaps H(xT) to back
FROMALT NEGATE # negate
END
FROMALT ADD TOALT # add to accumulator
ENDIF
CAT


--
@JeremyRubin 



On Fri, Jul 9, 2021 at 12:03 PM Ethan Heilman  wrote:

> >Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple
> kilobytes)... blocksize increase *cough*
>
> Couldn't you significantly compress the signatures by using either
> Winternitz OTS or by using OP_CAT to build a merkle tree so that the
> full signature can be derived during script execution from a much
> shorter set of seed values?
>
> On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
>  wrote:
> >
> >
> > Good morning Jeremy,
> >
> > Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple
> kilobytes)... blocksize increase *cough*
> >
> > Since a quantum computer can derive the EC privkey from the EC pubkey
> and this scheme is resistant to that, I think you can use a single
> well-known EC privkey, you just need a unique Lamport keypair for each UTXO
> (uniqueness being mandatory due to Lamport requiring preimage revelation).
> >
> > Regards,
> > ZmnSCPxj
> >
> >
> > > Dear Bitcoin Devs,
> > >
> > > As mentioned previously, OP_CAT (or similar operation) can be used to
> make Bitcoin "quantum safe" by signing an EC signature. This should work in
> both Segwit V0 and Tapscript, although you have to use HASH160 for it to
> fit in Segwit V0.
> > >
> > > See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for
> the specific construction, reproduced below.
> > >
> > > Yet another entry to the "OP_CAT can do that too" list.
> > >
> > > Best,
> > >
> > > Jeremy
> > > -
> > >
> > > I recently published [a blog
> > > post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about
> signing up to a
> > > 5 byte value using Bitcoin script arithmetic and Lamport signatures.
> > >
> > > By itself, this is neat, but a little limited. What if we could sign
> longer
> > > messages? If we can sign up to 20 bytes, we could sign a HASH160
> digest which
> > > is most likely quantum safe...
> > >
> > > What would it mean if we signed the HASH160 digest of a signature?
> What the
> > > what? Why would we do that?
> > >
> > > Well, as it turns out, even if a quantum computer were able to crack
> ECDSA, it
> > > would yield revealing the private key but not the ability to malleate
> the
> > > content of what was actually signed.  I asked my good friend and
> cryptographer
> > > [Madars Virza](https://madars.org/) if my intuition was 

Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[ZmnSCPxj via bitcoin-dev]

Good morning Ethan,

> > Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple 
> > kilobytes)... blocksize increase cough
>
> Couldn't you significantly compress the signatures by using either
> Winternitz OTS or by using OP_CAT to build a merkle tree so that the
> full signature can be derived during script execution from a much
> shorter set of seed values?

To implement Winternitz we need some kind of limited-repeat construct, which is 
not available in SCRIPT, but may be emulatable with enough `OP_IF` and sheer 
brute force.
But what you gain in smaller signatures, you lose in a more complex and longer 
SCRIPT, and there are limits to SCRIPT size (in order to limit the processing 
done in each node).

Merkle signatures trade off shorter pubkeys for longer signatures (signatures 
need to provide the hash of the *other* preimage you are not revealing), but in 
the modern post-SegWit Bitcoin context both pubkeys and signatures are stored 
in the witness area, which have the same weight, thus it is actually a loss 
compared to Lamport.


So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy 
refers to), Merkle not so much.

Regards,
ZmnSCPxj

> On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
> bitcoin-dev@lists.linuxfoundation.org wrote:
>
> > Good morning Jeremy,
> > Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple 
> > kilobytes)... blocksize increase cough
> > Since a quantum computer can derive the EC privkey from the EC pubkey and 
> > this scheme is resistant to that, I think you can use a single well-known 
> > EC privkey, you just need a unique Lamport keypair for each UTXO 
> > (uniqueness being mandatory due to Lamport requiring preimage revelation).
> > Regards,
> > ZmnSCPxj
> >
> > > Dear Bitcoin Devs,
> > > As mentioned previously, OP_CAT (or similar operation) can be used to 
> > > make Bitcoin "quantum safe" by signing an EC signature. This should work 
> > > in both Segwit V0 and Tapscript, although you have to use HASH160 for it 
> > > to fit in Segwit V0.
> > > See my blog for the specific construction, reproduced below.
> > > Yet another entry to the "OP_CAT can do that too" list.
> > > Best,
> > >
> > > Jeremy
> > >
> > > ---
> > >
> > > I recently published a blogpost about signing up to a5 byte value using 
> > > Bitcoin script arithmetic and Lamport signatures.
> > > By itself, this is neat, but a little limited. What if we could sign 
> > > longer
> > > messages? If we can sign up to 20 bytes, we could sign a HASH160 digest 
> > > which
> > > is most likely quantum safe...
> > > What would it mean if we signed the HASH160 digest of a signature? What 
> > > the
> > > what? Why would we do that?
> > > Well, as it turns out, even if a quantum computer were able to crack 
> > > ECDSA, it
> > > would yield revealing the private key but not the ability to malleate the
> > > content of what was actually signed. I asked my good friend and 
> > > cryptographer
> > > Madars Virza if my intuition was correct, and he
> > > confirmed that it should be sufficient, but it's definitely worth closer
> > > analysis before relying on this. While the ECDSA signature can be 
> > > malleated to a
> > > different, negative form, if the signature is otherwise made immalleable 
> > > there
> > > should only be one value the commitment can be opened to.
> > > If we required the ECDSA signature be signed with a quantum proof 
> > > signature
> > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing 
> > > scheme
> > > we discussed previously is a Lamport signature, which is quantum secure.
> > > Unfortunately, we need at least 20 contiguous bytes... so we need some 
> > > sort of
> > > OP\_CAT like operation.
> > > OP\_CAT can't be directly soft forked to Segwit v0 because it modifies the
> > > stack, so instead we'll (for simplicity) also show how to use a new 
> > > opcode that
> > > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a 
> > > string
> > > for equality.
> > >
> > > ... FOR j in 0..=5
> > > <0>
> > > ... FOR i in 0..=31
> > > SWAP hash160 DUP  EQUAL IF DROP <2**i> ADD ELSE 
> > >  EQUALVERIFY ENDIF
> > > ... END FOR
> > > TOALTSTACK
> > > ... END FOR
> > >
> > > DUP HASH160
> > >
> > > ... IF CAT AVAILABLE
> > > FROMALTSTACK
> > > ... FOR j in 0..=5
> > > FROMALTSTACK
> > > CAT
> > > ... END FOR
> > > EQUALVERIFY
> > > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> > > ... FOR j in 0..=5
> > > FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP 
> > > DROP
> > > ...  END FOR
> > > DROP
> > > ... END IF
> > >
> > >  CHECKSIG
> > >
> > >
> > > That's a long script... but will it fit? We need to verify 20 bytes of 
> > > message
> > > each bit takes around 10 bytes script, an average of 3.375 bytes per 
> > > 

Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[Ethan Heilman via bitcoin-dev]

>Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple 
>kilobytes)... blocksize increase *cough*

Couldn't you significantly compress the signatures by using either
Winternitz OTS or by using OP_CAT to build a merkle tree so that the
full signature can be derived during script execution from a much
shorter set of seed values?

On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
 wrote:
>
>
> Good morning Jeremy,
>
> Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple 
> kilobytes)... blocksize increase *cough*
>
> Since a quantum computer can derive the EC privkey from the EC pubkey and 
> this scheme is resistant to that, I think you can use a single well-known EC 
> privkey, you just need a unique Lamport keypair for each UTXO (uniqueness 
> being mandatory due to Lamport requiring preimage revelation).
>
> Regards,
> ZmnSCPxj
>
>
> > Dear Bitcoin Devs,
> >
> > As mentioned previously, OP_CAT (or similar operation) can be used to make 
> > Bitcoin "quantum safe" by signing an EC signature. This should work in both 
> > Segwit V0 and Tapscript, although you have to use HASH160 for it to fit in 
> > Segwit V0.
> >
> > See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for the 
> > specific construction, reproduced below.
> >
> > Yet another entry to the "OP_CAT can do that too" list.
> >
> > Best,
> >
> > Jeremy
> > -
> >
> > I recently published [a blog
> > post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about signing up 
> > to a
> > 5 byte value using Bitcoin script arithmetic and Lamport signatures.
> >
> > By itself, this is neat, but a little limited. What if we could sign longer
> > messages? If we can sign up to 20 bytes, we could sign a HASH160 digest 
> > which
> > is most likely quantum safe...
> >
> > What would it mean if we signed the HASH160 digest of a signature? What the
> > what? Why would we do that?
> >
> > Well, as it turns out, even if a quantum computer were able to crack ECDSA, 
> > it
> > would yield revealing the private key but not the ability to malleate the
> > content of what was actually signed.  I asked my good friend and 
> > cryptographer
> > [Madars Virza](https://madars.org/) if my intuition was correct, and he
> > confirmed that it should be sufficient, but it's definitely worth closer
> > analysis before relying on this. While the ECDSA signature can be malleated 
> > to a
> > different, negative form, if the signature is otherwise made immalleable 
> > there
> > should only be one value the commitment can be opened to.
> >
> > If we required the ECDSA signature be signed with a quantum proof signature
> > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing 
> > scheme
> > we discussed previously is a Lamport signature, which is quantum secure.
> > Unfortunately, we need at least 20 contiguous bytes... so we need some sort 
> > of
> > OP\_CAT like operation.
> >
> > OP\_CAT can't be directly soft forked to Segwit v0 because it modifies the
> > stack, so instead we'll (for simplicity) also show how to use a new opcode 
> > that
> > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a 
> > string
> > for equality.
> >
> > ```
> > ... FOR j in 0..=5
> > <0>
> > ... FOR i in 0..=31
> > SWAP hash160 DUP  EQUAL IF DROP <2**i> ADD ELSE 
> >  EQUALVERIFY ENDIF
> > ... END FOR
> > TOALTSTACK
> > ... END FOR
> >
> > DUP HASH160
> >
> > ... IF CAT AVAILABLE
> > FROMALTSTACK
> > ... FOR j in 0..=5
> > FROMALTSTACK
> > CAT
> > ... END FOR
> > EQUALVERIFY
> > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> > ... FOR j in 0..=5
> > FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
> > ...  END FOR
> > DROP
> > ... END IF
> >
> >  CHECKSIG
> > ```
> >
> > That's a long script... but will it fit? We need to verify 20 bytes of 
> > message
> > each bit takes around 10 bytes script, an average of 3.375 bytes per number
> > (counting pushes), and two 21 bytes keys = 55.375 bytes of program space 
> > and 21
> > bytes of witness element per bit.
> >
> > It fits! `20*8*55.375 = 8860`, which leaves 1140 bytes less than the limit 
> > for
> > the rest of the logic, which is plenty (around 15-40 bytes required for the 
> > rest
> > of the logic, leaving 1100 free for custom signature checking). The stack 
> > size
> > is 160 elements for the hash gadget, 3360 bytes.
> >
> > This can probably be made a bit more efficient by expanding to a ternary
> > representation.
> >
> > ```
> > SWAP hash160 DUP  EQUAL  IF DROP  ELSE <3**i> SWAP DUP 
> >  EQUAL IF DROP SUB ELSE  EQUALVERIFY ADD  ENDIF 
> > ENDIF
> > ```
> >
> > This should bring it up to roughly 85 bytes per trit, and there should be 
> > 101
> > trits (`log(2**160)/log(3) == 100.94`), so about 8560 bytes... a bit 
> > cheaper!
> > But the witness stack is "only" `2121` bytes...
> >
> > As a homework exercise, maybe someone can prove 

Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[ZmnSCPxj via bitcoin-dev]

Good morning Jeremy,

Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple 
kilobytes)... blocksize increase *cough*

Since a quantum computer can derive the EC privkey from the EC pubkey and this 
scheme is resistant to that, I think you can use a single well-known EC 
privkey, you just need a unique Lamport keypair for each UTXO (uniqueness being 
mandatory due to Lamport requiring preimage revelation).

Regards,
ZmnSCPxj


> Dear Bitcoin Devs,
>
> As mentioned previously, OP_CAT (or similar operation) can be used to make 
> Bitcoin "quantum safe" by signing an EC signature. This should work in both 
> Segwit V0 and Tapscript, although you have to use HASH160 for it to fit in 
> Segwit V0.
>
> See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for the 
> specific construction, reproduced below.
>
> Yet another entry to the "OP_CAT can do that too" list.
>
> Best,
>
> Jeremy
> -
>
> I recently published [a blog
> post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about signing up to a
> 5 byte value using Bitcoin script arithmetic and Lamport signatures.
>
> By itself, this is neat, but a little limited. What if we could sign longer
> messages? If we can sign up to 20 bytes, we could sign a HASH160 digest which
> is most likely quantum safe...
>
> What would it mean if we signed the HASH160 digest of a signature? What the
> what? Why would we do that?
>
> Well, as it turns out, even if a quantum computer were able to crack ECDSA, it
> would yield revealing the private key but not the ability to malleate the
> content of what was actually signed.  I asked my good friend and cryptographer
> [Madars Virza](https://madars.org/) if my intuition was correct, and he
> confirmed that it should be sufficient, but it's definitely worth closer
> analysis before relying on this. While the ECDSA signature can be malleated 
> to a
> different, negative form, if the signature is otherwise made immalleable there
> should only be one value the commitment can be opened to.
>
> If we required the ECDSA signature be signed with a quantum proof signature
> algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing 
> scheme
> we discussed previously is a Lamport signature, which is quantum secure.
> Unfortunately, we need at least 20 contiguous bytes... so we need some sort of
> OP\_CAT like operation.
>
> OP\_CAT can't be directly soft forked to Segwit v0 because it modifies the
> stack, so instead we'll (for simplicity) also show how to use a new opcode 
> that
> uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a 
> string
> for equality.
>
> ```
> ... FOR j in 0..=5
>     <0>
>     ... FOR i in 0..=31
>         SWAP hash160 DUP  EQUAL IF DROP <2**i> ADD ELSE 
>  EQUALVERIFY ENDIF
>     ... END FOR
>     TOALTSTACK
> ... END FOR
>
> DUP HASH160
>
> ... IF CAT AVAILABLE
>     FROMALTSTACK
>     ... FOR j in 0..=5
>         FROMALTSTACK
>         CAT
>     ... END FOR
>     EQUALVERIFY
> ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
>     ... FOR j in 0..=5
>         FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
>     ...  END FOR
>     DROP
> ... END IF
>
>  CHECKSIG
> ```
>
> That's a long script... but will it fit? We need to verify 20 bytes of message
> each bit takes around 10 bytes script, an average of 3.375 bytes per number
> (counting pushes), and two 21 bytes keys = 55.375 bytes of program space and 
> 21
> bytes of witness element per bit.
>
> It fits! `20*8*55.375 = 8860`, which leaves 1140 bytes less than the limit for
> the rest of the logic, which is plenty (around 15-40 bytes required for the 
> rest
> of the logic, leaving 1100 free for custom signature checking). The stack size
> is 160 elements for the hash gadget, 3360 bytes.
>
> This can probably be made a bit more efficient by expanding to a ternary
> representation.
>
> ```
>         SWAP hash160 DUP  EQUAL  IF DROP  ELSE <3**i> SWAP DUP 
>  EQUAL IF DROP SUB ELSE  EQUALVERIFY ADD  ENDIF ENDIF
> ```
>
> This should bring it up to roughly 85 bytes per trit, and there should be 101
> trits (`log(2**160)/log(3) == 100.94`), so about 8560 bytes... a bit cheaper!
> But the witness stack is "only" `2121` bytes...
>
> As a homework exercise, maybe someone can prove the optimal choice of radix 
> for
> this protocol... My guess is that base 4 is optimal!
>
> ## Taproot?
>
> What about Taproot? As far as I'm aware the commitment scheme (`Q = pG + 
> hash(pG
> || m)G`) can be securely opened to m even with a quantum computer (finding `q`
> such that `qG = Q` might be trivial, but suppose key path was disabled, then
> finding m and p such that the taproot equation holds should be difficult 
> because
> of the hash, but I'd need to certify that claim better).  Therefore this
> script can nest inside of a Tapscript path -- Tapscript also does not impose a
> length limit, 32 byte hashes could be used as well.
>
> Further, to make keys reusable, there could be many Lamport 

[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[Jeremy via bitcoin-dev]

Dear Bitcoin Devs,

As mentioned previously, OP_CAT (or similar operation) can be used to make
Bitcoin "quantum safe" by signing an EC signature. This should work in both
Segwit V0 and Tapscript, although you have to use HASH160 for it to fit in
Segwit V0.

See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for the
specific construction, reproduced below.

Yet another entry to the "OP_CAT can do that too" list.

Best,

Jeremy
-


I recently published [a blog
post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about signing up
to a
5 byte value using Bitcoin script arithmetic and Lamport signatures.

By itself, this is neat, but a little limited. What if we could sign longer
messages? If we can sign up to 20 bytes, we could sign a HASH160 digest
which
is most likely quantum safe...

What would it mean if we signed the HASH160 digest of a signature? What the
what? Why would we do that?

Well, as it turns out, even if a quantum computer were able to crack ECDSA,
it
would yield revealing the private key but not the ability to malleate the
content of what was actually signed.  I asked my good friend and
cryptographer
[Madars Virza](https://madars.org/) if my intuition was correct, and he
confirmed that it should be sufficient, but it's definitely worth closer
analysis before relying on this. While the ECDSA signature can be malleated
to a
different, negative form, if the signature is otherwise made immalleable
there
should only be one value the commitment can be opened to.

If we required the ECDSA signature be signed with a quantum proof signature
algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing
scheme
we discussed previously is a Lamport signature, which is quantum secure.
Unfortunately, we need at least 20 contiguous bytes... so we need some sort
of
OP\_CAT like operation.

OP\_CAT can't be directly soft forked to Segwit v0 because it modifies the
stack, so instead we'll (for simplicity) also show how to use a new opcode
that
uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a
string
for equality.

```
... FOR j in 0..=5
<0>
... FOR i in 0..=31
SWAP hash160 DUP  EQUAL IF DROP <2**i> ADD ELSE
 EQUALVERIFY ENDIF
... END FOR
TOALTSTACK
... END FOR

DUP HASH160

... IF CAT AVAILABLE
FROMALTSTACK
... FOR j in 0..=5
FROMALTSTACK
CAT
... END FOR
EQUALVERIFY
... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
... FOR j in 0..=5
FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
...  END FOR
DROP
... END IF

 CHECKSIG
```

That's a long script... but will it fit? We need to verify 20 bytes of
message
each bit takes around 10 bytes script, an average of 3.375 bytes per number
(counting pushes), and two 21 bytes keys = 55.375 bytes of program space
and 21
bytes of witness element per bit.

It fits! `20*8*55.375 = 8860`, which leaves 1140 bytes less than the limit
for
the rest of the logic, which is plenty (around 15-40 bytes required for the
rest
of the logic, leaving 1100 free for custom signature checking). The stack
size
is 160 elements for the hash gadget, 3360 bytes.

This can probably be made a bit more efficient by expanding to a ternary
representation.

```
SWAP hash160 DUP  EQUAL  IF DROP  ELSE <3**i> SWAP DUP
 EQUAL IF DROP SUB ELSE  EQUALVERIFY ADD  ENDIF
ENDIF
```

This should bring it up to roughly 85 bytes per trit, and there should be
101
trits (`log(2**160)/log(3) == 100.94`), so about 8560 bytes... a bit
cheaper!
But the witness stack is "only" `2121` bytes...

As a homework exercise, maybe someone can prove the optimal choice of radix
for
this protocol... My guess is that base 4 is optimal!

## Taproot?

What about Taproot? As far as I'm aware the commitment scheme (`Q = pG +
hash(pG
|| m)G`) can be securely opened to m even with a quantum computer (finding
`q`
such that `qG = Q` might be trivial, but suppose key path was disabled, then
finding m and p such that the taproot equation holds should be difficult
because
of the hash, but I'd need to certify that claim better).  Therefore this
script can nest inside of a Tapscript path -- Tapscript also does not
impose a
length limit, 32 byte hashes could be used as well.

Further, to make keys reusable, there could be many Lamport keys comitted
inside
a taproot tree so that an address could be used for thousands of times
before
expiring. This could be used as a measure to protect accidental use rather
than
to support it.

Lastly, Schnorr actually has a stronger non-malleability property than
ECDSA,
the signatures will be binding to the approved transaction and once Lamport
signed, even a quantum computer could not steal the funds.






--
@JeremyRubin 

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev