[bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Ethan Heilman]

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

One day having lunch at the MIT DCI and discussing OP_CAT and lamport
signatures we came up with a scheme to do lamport signatures on Bitcoin
transactions without OP_CAT.

This scheme has the following properties:
1. Should work with today's Bitcoin (no OP_CAT required).
2. Unlike other lamport signatures in Bitcoin script, this scheme signs the
spending transaction.

Disclaimer: This is very preliminary work and the security of these
signatures rests on a number of simplifying assumptions about ECDSA
signatures that may not be true. Do not use this signature scheme in a
Bitcoin output unless your intent is for that output to be a fun crypto
bounty. I have not tested this in Bitcoin script.

This idea of using signature length shares a lot in common with sigPOW
(signature POW) proposed by Robin Linus [3,4] and implemented by VzxPLnHqr
[5] which uses signature length grinding as a transaction level POW
mechanism and earlier work by Anthony Towns and Greg Maxwell using ECDSA
signature length constraints to force revealing signing key [6].

Our approach differs from the Jeremy Rubin's approach in [7] as we do not
require OP_CAT and we use P2SH not tapscript and from Jeremy Rubin's
approach in [8] as our goal is to verify a Lamport signature on the
spending transaction rather than a Lamport signature on arbitrary data.
When compared with [7,8] our scheme is far less practical as it requires
very large numbers of signatures (below we discuss 1000 signatures).

## Signing a Bitcoin Transaction with Lamport Signatures

An ECDSA signature (r,s) is calculated as r = (k*G)_x, s= (z+r*dA)/k
- k is randomly chosen nonce
- dA is the signing key,
- z is derived from the hash of the signed message, i.e., transaction hash.

Our Lamport scheme is based on the following observation. ECDSA signatures
in bitcoin are variable in length and that the length of an s-value in an
ECDSA signature for a fixed nonce, k, and fixed signing key has its length
determined by the transaction hash. We can use OP_SIZE to get the size of a
signature and we can use Lamport signatures to sign this size. We explain
Lamport signatures below.

The security of our scheme rests on a way to fix the nonce k. Madars Virza
and Andrew Poelstra both pointed out to me when discussing this scheme that
setting k=1/2, that is setting k to the multiplicative inverse of 2,
results in a k with a very short r
(r=0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63) [0].
This means that the first 11 bytes (88-bits of the r value are zero and
truncated) so the r-value is only 21 bytes long! A publicly known k leaks
the signing key, but that doesn't matter for our purposes.

Using this k, we can ensure that the r values on two signatures are the
same by inspecting their length using `OP_SIZE(sig) < (21+32+6)`. Grinding
r to find a smaller value requires 2^96 (12 bytes of zeros) computations
assuming no mathematical shortcut such as the one used to find k=1/2.


To explain how to use the above observative to sign Bitcoin transactions
with Lamport signatures, let's remind ourselves how Lamport signatures [1]
 work. To sign 1-bit with a Lamport signature you first use a hash function
H, to compute: x0 = H(y0), x1 = H(y1). Next, you publish x0,x1 as your
public key. Then, to sign the bit 0, you release the value y0. Anyone can
use y0 to verify that x0 == H(y0). To sign the bit 1, you release y1.

We use Lamport signatures to sign the length of a bitcoin signature. The
length of the signature serves as a proxy for the transaction hash of the
spending transaction. Repeating this many times provides cryptographic
levels of security. Let's look at an example:

Alice computes her Lamport public keys and signing keys
x00 = Hash(y00)
x01 = Hash(y01)
x10 = Hash(y10)
x11 = Hash(y11)
x20 = Hash(y20)
x21 = Hash(y21)

In pseudocode Alice's redeem script looks like:
```
PUSH ecdsaPubkey0
OP_CHECKSIG (ecdsaSig0)
// Verify lamport signature on ecdsaSig0
PUSH x00, x01
if OP_SIZE (ecdsaSig0) == 59:
  if OP_HASH(y00) != x00: OP_RETURN
else if OP_SIZE (ecdsaSig0) < 59:
  if OP_HASH(y01) != x01: OP_RETURN

PUSH ecdsaPubkey1
OP_CHECKSIG (ecdsaSig1)
// Verify lamport signature on ecdsaSig1
PUSH x10, x11
if OP_SIZE (ecdsaSig1) == 59:
  if OP_HASH(y10) != x10: OP_RETURN
else if OP_SIZE (ecdsaSig1) < 59:
  if OP_HASH(y11) != x11: OP_RETURN

// Verify lamport signature on ecdsaSig2
PUSH ecdsaPubkey2
OP_CHECKSIG (ecdsaSig2)
// Verify lamport signature on ecdsaSig1
PUSH x20, x21
if OP_SIZE (ecdsaSig2) == 59:
  if OP_HASH(y20) != x10: OP_RETURN
else if OP_SIZE (ecdsaSig2) < 59:
  if OP_HASH(y21) != x21: OP_RETURN
```

Alice computes the ECDSA signatures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For
example let’s say OP_SIZE(ecdsaSig0)=59, OP_SIZE(ecdsaSig1)=58,
OP_SIZE(ecdsaSig2)=59. Thus, to spend she generates a Lamport signature
over those lengths by releasing the preimages: y00, y11, y20.

The spend script pseudocode:
```
PUSH ecdsaSig0
PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 59
PUSH ecdsaSig1
PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be less than 59
PUSH ecdsaSig2
PUSH y20 // Signs that OP_SIZE(ecdsaSig2) should be 59
```

The advantage Alice has over an attacker attempting to steal her funds is
that all Alice has to do is release the preimages for the lengths of all of
her ECDSA signatures, but an attacker has  to construct a transaction hash
that matches the size of her signatures for each different ECDSA signature.
The probability an attacker manages this for three random ECDSA signatures
given the lengths above (59,58,59) is 255/256 * 1/256 * 255/256 ~= 0.3%.
Alice can arbitrarily amplify her security by adding additional ECDSA
signatures.

It was pointed out to me by Andrew Poelstra that the probability that a
random signature is shorter by one byte is 1/256 because OP_SIZE only
measures the byte length of a value, not the bit length. This means most of
the time if Alice just used three ECDSA signatures, they would all be
length 59. In such a case the attacker would have (255/256)^3 = 98%
probability of generating a transaction that can be spent using Alice's
signature on the attacker's very first try!

For this reason Alice really needs a lot of ECDSA signatures and probably
also needs to grind for safer values to sign (safer = high diversity in
length).

Assuming a simplistic model of ECDSA signatures length Prob(1-1/256) for
length 59 and Prob(1/256) for length <59, the probability that Alice will
generate exactly m <59-length signatures and n-m 59 length signatures is:
`(255/256)^(n-m)*(1/256)^m*(n choose m)`.

An attacker would need to not only generate m <59-length signatures and n-m
59 length signatures, but generate them in the same position as Alice
generated them. The probability an attacker will generate exactly m
<59-length signatures and n-m 59 length signatures in the same position as
Alice is: (255/256)^(n-m)*(1/256)^m

On average Alice would need 1000 attempts to sign with n=800,m=10. Whereas
an attacker would need to make 2^84 attempts to brute force the output
after seeing alice attempt to spend that output using a n=800,m=10
signature.

## Known weaknesses

1. *The Tuning Attack:* The attacker can use different SIG_HASH flags per
signature to attack each signature individually. For instance ecdsaSig1
doesn't have the right length, the attacker can try SIGHASH_NONE to try
again without changing any of the other signature lengths. This provides
the attacker some advantage but with sufficient numbers of signatures it
does not break the scheme. Alice can also use this approach to increase the
security of her signatures by increasing length diversity. Unclear if this
helps or hurts security more.

2. *Mix and Match Attack:* Even if an attacker can not grind a shorter
r-value, an r-value of roughly 21-23 bytes would allow an attacker to make
a few more individual attempts on a particular signature length. This is
because we only measure the total length of the ECDSA signature, so a
23-byte r-value combined with a 29-byte s-value would be 23+29+6 = 58
bytes. 29-byte s-value are rare and occur with ~1/2^24 probability, but if
an attacker managed to grind a 23-byte r-value at a cost of 2^72
computations, it would provide the attacker some advantage.

## Known Improvements

1. Rather than only signing if the length is 59 or less. We could extend
the scheme to sign multiple ECDSA signature length values, 59, 58, 57,
56... This could enable Alice to greatly increase her security as say 56
would only occur 1 out of every 2^32 signatures. Winternitz One Time
signatures (WOTs) [2] could be used here to compress signature length.

1. Jeremy Rubun suggested the following optimization: rather than directly
signing the ECDSA signatures lengths, you construct a 32-bit bit vector of
the signature lengths using OP_MUL, OP_ADD.

bit vector = OP_SIZE(ecdsaSig0)==59 + 2*(OP_SIZE(ecdsaSig1)==59) +
4*(OP_SIZE(ecdsaSig2)==59) ...

Then you compute a Winternitz One Time signature over this bit vector. This
would require also computing a WInternitz or Lamport signature over a
checksum of the bit vector. This would substantially reduce the number of
lamport public keys and signing keys and likely reduce the size of redeem
script and spend script by half.

3. Since 59 is the default length, Alice does not in fact need to sign 59.
It could be inferred that if no preimage is given or say the preimage 0 is
given, the length that Alice intends is 59. This would save space on the
spend script and redeem script.


## Open Questions

1. Could OP_CODESEPARATOR be used by Alice or the attacker to either
strengthen or weaken the security of this scheme. Alice using
OP_CODESEPARATOR to strengthen the security of this scheme by increasing
signature length diversity was suggested by Jeremy Rubin. After some
discussion, the fact that the redeem script is part of the P2SH address
means that the data in OP_CODESEPARATOR would still influence all the other
ECDSA signatures. That said, perhaps there is some way it can be exploited
to either help Alice or help the attacker.

2. If a nonce value k was discovered such that k*G = r = 1, we could remove
the assumption that no could find a smaller r. It is unknown how to find
r=1 as it requires finding the discrete log. It is possible to create
transaction signatures that have r=1 without knowing k, through the use of
ECDSA pubkey recovery. This does not work for our scheme as we must commit
to the ECDSA  public key in the spent transaction. Are there any known
smaller r values than r=1/2*G?

3. How many bits of security does each ECDSA signature contribute in this
scheme given the SIGHASH mix and match attack above? How many ECDSA
signatures are needed? We have modeled ECDSA s-values signatures being
uniformly drawn from 2^256. It seems unlikely to me that the Elliptic Curve
math lines up perfectly with a 256 bit space especially for a fixed r-value
that has special mathematical properties. Non-uniformity here could end up
helping (increasing length diversity) or hurting (a pattern an attacker
could exploit to match the length faster than brute force) the security.

4. An attacker could trade off brute forcing the transaction hash lengths
by computing a small r-value. What does the time-memory trade look like
here?

5. Is there any use for this beyond a fun party trick?

Thanks to Madars Virza, Dan Gould, Armin Sabouri, Neha Narula, Jeremy
Rubin, Andrew Poelstra, Robin Linus for discussing this with me and giving
me feedback. This initial discuss was fueled by the MIT DCI espresso
machine. I've attempted to credit all ideas contributed to the contributor,
if I got this wrong or missed a contribution shoot me an email. Any
mistakes are my own as I wrote this up.

[0]: "Bitcoin Wallet Recovery via ECDSA Short Signatures"
https://github.com/demining/Bitcoin-Wallet-Recovery?tab=readme-ov-file

[1]: "Constructing Digital Signatures from a One Way Function", Leslie
Lamport (1979),
https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/

[2]: "A Certified Digital Signature", Ralph C. Merkle (1979),
https://www.ralphmerkle.com/papers/Certified1979.pdf

[3]: "Timelocked Proof of Work via signature length",  Robin Linus (2021),
https://gist.github.com/RobinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md

[4]: "Proof of Work in Bitcoin Script", Robin Linus (2020),
https://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md

[5]: "sig-pow - work-locked outputs", VzxPLnHqr (2022),
https://github.com/VzxPLnHqr/sig-pow/

[6]: "[Lightning-dev] Better privacy with SNARKs", Anthony Towns (2015),
https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html

[7]: "Quantum Proofing Bitcoin with a CAT", Jeremy Rubin (2021),
https://rubin.io/blog/2021/07/06/quantum-bitcoin/

[8]: "CheckSigFromStack for 5 Byte Values", Jeremy Rubin (2021),
https://rubin.io/blog/2021/07/02/signing-5-bytes/

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com.

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

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Matthew Zipkin]

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

We discussed this scheme at NY BitDevs last night and one participant made
a great point:

> if an attacker managed to grind a 23-byte r-value at a cost of 2^72
computations, it would provide the attacker some advantage.

If we are assuming discrete log is still hard, why do we need Lamport
signatures at all? In a post-quantum world, finding k such that r is 21
bytes or less is efficient for the attacker.


On Sun, Apr 28, 2024 at 8:50 PM Ethan Heilman <eth3rs@gmail.com> wrote:

> One day having lunch at the MIT DCI and discussing OP_CAT and lamport
> signatures we came up with a scheme to do lamport signatures on Bitcoin
> transactions without OP_CAT.
>
> This scheme has the following properties:
> 1. Should work with today's Bitcoin (no OP_CAT required).
> 2. Unlike other lamport signatures in Bitcoin script, this scheme signs
> the spending transaction.
>
> Disclaimer: This is very preliminary work and the security of these
> signatures rests on a number of simplifying assumptions about ECDSA
> signatures that may not be true. Do not use this signature scheme in a
> Bitcoin output unless your intent is for that output to be a fun crypto
> bounty. I have not tested this in Bitcoin script.
>
> This idea of using signature length shares a lot in common with sigPOW
> (signature POW) proposed by Robin Linus [3,4] and implemented by VzxPLnHqr
> [5] which uses signature length grinding as a transaction level POW
> mechanism and earlier work by Anthony Towns and Greg Maxwell using ECDSA
> signature length constraints to force revealing signing key [6].
>
> Our approach differs from the Jeremy Rubin's approach in [7] as we do not
> require OP_CAT and we use P2SH not tapscript and from Jeremy Rubin's
> approach in [8] as our goal is to verify a Lamport signature on the
> spending transaction rather than a Lamport signature on arbitrary data.
> When compared with [7,8] our scheme is far less practical as it requires
> very large numbers of signatures (below we discuss 1000 signatures).
>
> ## Signing a Bitcoin Transaction with Lamport Signatures
>
> An ECDSA signature (r,s) is calculated as r = (k*G)_x, s= (z+r*dA)/k
> - k is randomly chosen nonce
> - dA is the signing key,
> - z is derived from the hash of the signed message, i.e., transaction hash.
>
> Our Lamport scheme is based on the following observation. ECDSA signatures
> in bitcoin are variable in length and that the length of an s-value in an
> ECDSA signature for a fixed nonce, k, and fixed signing key has its length
> determined by the transaction hash. We can use OP_SIZE to get the size of a
> signature and we can use Lamport signatures to sign this size. We explain
> Lamport signatures below.
>
> The security of our scheme rests on a way to fix the nonce k. Madars Virza
> and Andrew Poelstra both pointed out to me when discussing this scheme that
> setting k=1/2, that is setting k to the multiplicative inverse of 2,
> results in a k with a very short r
> (r=0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63) [0].
> This means that the first 11 bytes (88-bits of the r value are zero and
> truncated) so the r-value is only 21 bytes long! A publicly known k leaks
> the signing key, but that doesn't matter for our purposes.
>
> Using this k, we can ensure that the r values on two signatures are the
> same by inspecting their length using `OP_SIZE(sig) < (21+32+6)`. Grinding
> r to find a smaller value requires 2^96 (12 bytes of zeros) computations
> assuming no mathematical shortcut such as the one used to find k=1/2.
>
>
> To explain how to use the above observative to sign Bitcoin transactions
> with Lamport signatures, let's remind ourselves how Lamport signatures [1]
>  work. To sign 1-bit with a Lamport signature you first use a hash function
> H, to compute: x0 = H(y0), x1 = H(y1). Next, you publish x0,x1 as your
> public key. Then, to sign the bit 0, you release the value y0. Anyone can
> use y0 to verify that x0 == H(y0). To sign the bit 1, you release y1.
>
> We use Lamport signatures to sign the length of a bitcoin signature. The
> length of the signature serves as a proxy for the transaction hash of the
> spending transaction. Repeating this many times provides cryptographic
> levels of security. Let's look at an example:
>
> Alice computes her Lamport public keys and signing keys
> x00 = Hash(y00)
> x01 = Hash(y01)
> x10 = Hash(y10)
> x11 = Hash(y11)
> x20 = Hash(y20)
> x21 = Hash(y21)
>
> In pseudocode Alice's redeem script looks like:
> ```
> PUSH ecdsaPubkey0
> OP_CHECKSIG (ecdsaSig0)
> // Verify lamport signature on ecdsaSig0
> PUSH x00, x01
> if OP_SIZE (ecdsaSig0) == 59:
>   if OP_HASH(y00) != x00: OP_RETURN
> else if OP_SIZE (ecdsaSig0) < 59:
>   if OP_HASH(y01) != x01: OP_RETURN
>
> PUSH ecdsaPubkey1
> OP_CHECKSIG (ecdsaSig1)
> // Verify lamport signature on ecdsaSig1
> PUSH x10, x11
> if OP_SIZE (ecdsaSig1) == 59:
>   if OP_HASH(y10) != x10: OP_RETURN
> else if OP_SIZE (ecdsaSig1) < 59:
>   if OP_HASH(y11) != x11: OP_RETURN
>
> // Verify lamport signature on ecdsaSig2
> PUSH ecdsaPubkey2
> OP_CHECKSIG (ecdsaSig2)
> // Verify lamport signature on ecdsaSig1
> PUSH x20, x21
> if OP_SIZE (ecdsaSig2) == 59:
>   if OP_HASH(y20) != x10: OP_RETURN
> else if OP_SIZE (ecdsaSig2) < 59:
>   if OP_HASH(y21) != x21: OP_RETURN
> ```
>
> Alice computes the ECDSA signatures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For
> example let’s say OP_SIZE(ecdsaSig0)=59, OP_SIZE(ecdsaSig1)=58,
> OP_SIZE(ecdsaSig2)=59. Thus, to spend she generates a Lamport signature
> over those lengths by releasing the preimages: y00, y11, y20.
>
> The spend script pseudocode:
> ```
> PUSH ecdsaSig0
> PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 59
> PUSH ecdsaSig1
> PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be less than 59
> PUSH ecdsaSig2
> PUSH y20 // Signs that OP_SIZE(ecdsaSig2) should be 59
> ```
>
> The advantage Alice has over an attacker attempting to steal her funds is
> that all Alice has to do is release the preimages for the lengths of all of
> her ECDSA signatures, but an attacker has  to construct a transaction hash
> that matches the size of her signatures for each different ECDSA signature.
> The probability an attacker manages this for three random ECDSA signatures
> given the lengths above (59,58,59) is 255/256 * 1/256 * 255/256 ~= 0.3%.
> Alice can arbitrarily amplify her security by adding additional ECDSA
> signatures.
>
> It was pointed out to me by Andrew Poelstra that the probability that a
> random signature is shorter by one byte is 1/256 because OP_SIZE only
> measures the byte length of a value, not the bit length. This means most of
> the time if Alice just used three ECDSA signatures, they would all be
> length 59. In such a case the attacker would have (255/256)^3 = 98%
> probability of generating a transaction that can be spent using Alice's
> signature on the attacker's very first try!
>
> For this reason Alice really needs a lot of ECDSA signatures and probably
> also needs to grind for safer values to sign (safer = high diversity in
> length).
>
> Assuming a simplistic model of ECDSA signatures length Prob(1-1/256) for
> length 59 and Prob(1/256) for length <59, the probability that Alice will
> generate exactly m <59-length signatures and n-m 59 length signatures is:
> `(255/256)^(n-m)*(1/256)^m*(n choose m)`.
>
> An attacker would need to not only generate m <59-length signatures and
> n-m 59 length signatures, but generate them in the same position as Alice
> generated them. The probability an attacker will generate exactly m
> <59-length signatures and n-m 59 length signatures in the same position as
> Alice is: (255/256)^(n-m)*(1/256)^m
>
> On average Alice would need 1000 attempts to sign with n=800,m=10. Whereas
> an attacker would need to make 2^84 attempts to brute force the output
> after seeing alice attempt to spend that output using a n=800,m=10
> signature.
>
> ## Known weaknesses
>
> 1. *The Tuning Attack:* The attacker can use different SIG_HASH flags per
> signature to attack each signature individually. For instance ecdsaSig1
> doesn't have the right length, the attacker can try SIGHASH_NONE to try
> again without changing any of the other signature lengths. This provides
> the attacker some advantage but with sufficient numbers of signatures it
> does not break the scheme. Alice can also use this approach to increase the
> security of her signatures by increasing length diversity. Unclear if this
> helps or hurts security more.
>
> 2. *Mix and Match Attack:* Even if an attacker can not grind a shorter
> r-value, an r-value of roughly 21-23 bytes would allow an attacker to make
> a few more individual attempts on a particular signature length. This is
> because we only measure the total length of the ECDSA signature, so a
> 23-byte r-value combined with a 29-byte s-value would be 23+29+6 = 58
> bytes. 29-byte s-value are rare and occur with ~1/2^24 probability, but if
> an attacker managed to grind a 23-byte r-value at a cost of 2^72
> computations, it would provide the attacker some advantage.
>
> ## Known Improvements
>
> 1. Rather than only signing if the length is 59 or less. We could extend
> the scheme to sign multiple ECDSA signature length values, 59, 58, 57,
> 56... This could enable Alice to greatly increase her security as say 56
> would only occur 1 out of every 2^32 signatures. Winternitz One Time
> signatures (WOTs) [2] could be used here to compress signature length.
>
> 1. Jeremy Rubun suggested the following optimization: rather than directly
> signing the ECDSA signatures lengths, you construct a 32-bit bit vector of
> the signature lengths using OP_MUL, OP_ADD.
>
> bit vector = OP_SIZE(ecdsaSig0)==59 + 2*(OP_SIZE(ecdsaSig1)==59) +
> 4*(OP_SIZE(ecdsaSig2)==59) ...
>
> Then you compute a Winternitz One Time signature over this bit vector.
> This would require also computing a WInternitz or Lamport signature over a
> checksum of the bit vector. This would substantially reduce the number of
> lamport public keys and signing keys and likely reduce the size of redeem
> script and spend script by half.
>
> 3. Since 59 is the default length, Alice does not in fact need to sign 59.
> It could be inferred that if no preimage is given or say the preimage 0 is
> given, the length that Alice intends is 59. This would save space on the
> spend script and redeem script.
>
>
> ## Open Questions
>
> 1. Could OP_CODESEPARATOR be used by Alice or the attacker to either
> strengthen or weaken the security of this scheme. Alice using
> OP_CODESEPARATOR to strengthen the security of this scheme by increasing
> signature length diversity was suggested by Jeremy Rubin. After some
> discussion, the fact that the redeem script is part of the P2SH address
> means that the data in OP_CODESEPARATOR would still influence all the other
> ECDSA signatures. That said, perhaps there is some way it can be exploited
> to either help Alice or help the attacker.
>
> 2. If a nonce value k was discovered such that k*G = r = 1, we could
> remove the assumption that no could find a smaller r. It is unknown how to
> find r=1 as it requires finding the discrete log. It is possible to create
> transaction signatures that have r=1 without knowing k, through the use of
> ECDSA pubkey recovery. This does not work for our scheme as we must commit
> to the ECDSA  public key in the spent transaction. Are there any known
> smaller r values than r=1/2*G?
>
> 3. How many bits of security does each ECDSA signature contribute in this
> scheme given the SIGHASH mix and match attack above? How many ECDSA
> signatures are needed? We have modeled ECDSA s-values signatures being
> uniformly drawn from 2^256. It seems unlikely to me that the Elliptic Curve
> math lines up perfectly with a 256 bit space especially for a fixed r-value
> that has special mathematical properties. Non-uniformity here could end up
> helping (increasing length diversity) or hurting (a pattern an attacker
> could exploit to match the length faster than brute force) the security.
>
> 4. An attacker could trade off brute forcing the transaction hash lengths
> by computing a small r-value. What does the time-memory trade look like
> here?
>
> 5. Is there any use for this beyond a fun party trick?
>
> Thanks to Madars Virza, Dan Gould, Armin Sabouri, Neha Narula, Jeremy
> Rubin, Andrew Poelstra, Robin Linus for discussing this with me and giving
> me feedback. This initial discuss was fueled by the MIT DCI espresso
> machine. I've attempted to credit all ideas contributed to the contributor,
> if I got this wrong or missed a contribution shoot me an email. Any
> mistakes are my own as I wrote this up.
>
> [0]: "Bitcoin Wallet Recovery via ECDSA Short Signatures"
> https://github.com/demining/Bitcoin-Wallet-Recovery?tab=readme-ov-file
>
> [1]: "Constructing Digital Signatures from a One Way Function", Leslie
> Lamport (1979),
> https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/
>
> [2]: "A Certified Digital Signature", Ralph C. Merkle (1979),
> https://www.ralphmerkle.com/papers/Certified1979.pdf
>
> [3]: "Timelocked Proof of Work via signature length",  Robin Linus (2021),
> https://gist.github.com/RobinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md
>
> [4]: "Proof of Work in Bitcoin Script", Robin Linus (2020),
> https://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md
>
> [5]: "sig-pow - work-locked outputs", VzxPLnHqr (2022),
> https://github.com/VzxPLnHqr/sig-pow/
>
> [6]: "[Lightning-dev] Better privacy with SNARKs", Anthony Towns (2015),
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html
>
> [7]: "Quantum Proofing Bitcoin with a CAT", Jeremy Rubin (2021),
> https://rubin.io/blog/2021/07/06/quantum-bitcoin/
>
> [8]: "CheckSigFromStack for 5 Byte Values", Jeremy Rubin (2021),
> https://rubin.io/blog/2021/07/02/signing-5-bytes/
>
> --
> You received this message because you are subscribed to the Google Groups
> "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com
> <https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CA%2Bx5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw%40mail.gmail.com.

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

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Ethan Heilman]

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

> If we are assuming discrete log is still hard, why do we need Lamport
signatures at all? In a post-quantum world, finding k such that r is 21
bytes or less is efficient for the attacker.

This is true, however there is a fix. Someone at the DCI, I think Madars,
pointed out that if you had a quantum computer you could find r=1 and then
everyone could use r=1 in the scheme and not have to worry about grinding
attacks. So the ability to compute discrete logs would strengthen this
scheme.

Interestingly, you can generate valid ecdsa signatures where (r=1,s=1)
using ecdsa pubkey recovery because "An ECDSA signature itself does not
prove knowledge of a discrete log."
<https://bitcointalk.org/index.php?topic=1729534.msg17309060#msg17309060>

I am not aware of any technique, even if we had OP_LAMPORT, to make Bitcoin
outputs quantum resistant without a softfork to add the ability to disable
key-spend paths in a taproot output. I'd love to be proven wrong on this
point.

On Tue, Apr 30, 2024 at 8:32 AM Matthew Zipkin <pinheadmz@gmail.com> wrote:

> We discussed this scheme at NY BitDevs last night and one participant made
> a great point:
>
> > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
> computations, it would provide the attacker some advantage.
>
> If we are assuming discrete log is still hard, why do we need Lamport
> signatures at all? In a post-quantum world, finding k such that r is 21
> bytes or less is efficient for the attacker.
>
>
> On Sun, Apr 28, 2024 at 8:50 PM Ethan Heilman <eth3rs@gmail.com> wrote:
>
>> One day having lunch at the MIT DCI and discussing OP_CAT and lamport
>> signatures we came up with a scheme to do lamport signatures on Bitcoin
>> transactions without OP_CAT.
>>
>> This scheme has the following properties:
>> 1. Should work with today's Bitcoin (no OP_CAT required).
>> 2. Unlike other lamport signatures in Bitcoin script, this scheme signs
>> the spending transaction.
>>
>> Disclaimer: This is very preliminary work and the security of these
>> signatures rests on a number of simplifying assumptions about ECDSA
>> signatures that may not be true. Do not use this signature scheme in a
>> Bitcoin output unless your intent is for that output to be a fun crypto
>> bounty. I have not tested this in Bitcoin script.
>>
>> This idea of using signature length shares a lot in common with sigPOW
>> (signature POW) proposed by Robin Linus [3,4] and implemented by VzxPLnHqr
>> [5] which uses signature length grinding as a transaction level POW
>> mechanism and earlier work by Anthony Towns and Greg Maxwell using ECDSA
>> signature length constraints to force revealing signing key [6].
>>
>> Our approach differs from the Jeremy Rubin's approach in [7] as we do not
>> require OP_CAT and we use P2SH not tapscript and from Jeremy Rubin's
>> approach in [8] as our goal is to verify a Lamport signature on the
>> spending transaction rather than a Lamport signature on arbitrary data.
>> When compared with [7,8] our scheme is far less practical as it requires
>> very large numbers of signatures (below we discuss 1000 signatures).
>>
>> ## Signing a Bitcoin Transaction with Lamport Signatures
>>
>> An ECDSA signature (r,s) is calculated as r = (k*G)_x, s= (z+r*dA)/k
>> - k is randomly chosen nonce
>> - dA is the signing key,
>> - z is derived from the hash of the signed message, i.e., transaction
>> hash.
>>
>> Our Lamport scheme is based on the following observation. ECDSA
>> signatures in bitcoin are variable in length and that the length of an
>> s-value in an ECDSA signature for a fixed nonce, k, and fixed signing key
>> has its length determined by the transaction hash. We can use OP_SIZE to
>> get the size of a signature and we can use Lamport signatures to sign this
>> size. We explain Lamport signatures below.
>>
>> The security of our scheme rests on a way to fix the nonce k. Madars
>> Virza and Andrew Poelstra both pointed out to me when discussing this
>> scheme that setting k=1/2, that is setting k to the multiplicative inverse
>> of 2, results in a k with a very short r
>> (r=0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63) [0].
>> This means that the first 11 bytes (88-bits of the r value are zero and
>> truncated) so the r-value is only 21 bytes long! A publicly known k leaks
>> the signing key, but that doesn't matter for our purposes.
>>
>> Using this k, we can ensure that the r values on two signatures are the
>> same by inspecting their length using `OP_SIZE(sig) < (21+32+6)`. Grinding
>> r to find a smaller value requires 2^96 (12 bytes of zeros) computations
>> assuming no mathematical shortcut such as the one used to find k=1/2.
>>
>>
>> To explain how to use the above observative to sign Bitcoin transactions
>> with Lamport signatures, let's remind ourselves how Lamport signatures [1]
>>  work. To sign 1-bit with a Lamport signature you first use a hash function
>> H, to compute: x0 = H(y0), x1 = H(y1). Next, you publish x0,x1 as your
>> public key. Then, to sign the bit 0, you release the value y0. Anyone can
>> use y0 to verify that x0 == H(y0). To sign the bit 1, you release y1.
>>
>> We use Lamport signatures to sign the length of a bitcoin signature. The
>> length of the signature serves as a proxy for the transaction hash of the
>> spending transaction. Repeating this many times provides cryptographic
>> levels of security. Let's look at an example:
>>
>> Alice computes her Lamport public keys and signing keys
>> x00 = Hash(y00)
>> x01 = Hash(y01)
>> x10 = Hash(y10)
>> x11 = Hash(y11)
>> x20 = Hash(y20)
>> x21 = Hash(y21)
>>
>> In pseudocode Alice's redeem script looks like:
>> ```
>> PUSH ecdsaPubkey0
>> OP_CHECKSIG (ecdsaSig0)
>> // Verify lamport signature on ecdsaSig0
>> PUSH x00, x01
>> if OP_SIZE (ecdsaSig0) == 59:
>>   if OP_HASH(y00) != x00: OP_RETURN
>> else if OP_SIZE (ecdsaSig0) < 59:
>>   if OP_HASH(y01) != x01: OP_RETURN
>>
>> PUSH ecdsaPubkey1
>> OP_CHECKSIG (ecdsaSig1)
>> // Verify lamport signature on ecdsaSig1
>> PUSH x10, x11
>> if OP_SIZE (ecdsaSig1) == 59:
>>   if OP_HASH(y10) != x10: OP_RETURN
>> else if OP_SIZE (ecdsaSig1) < 59:
>>   if OP_HASH(y11) != x11: OP_RETURN
>>
>> // Verify lamport signature on ecdsaSig2
>> PUSH ecdsaPubkey2
>> OP_CHECKSIG (ecdsaSig2)
>> // Verify lamport signature on ecdsaSig1
>> PUSH x20, x21
>> if OP_SIZE (ecdsaSig2) == 59:
>>   if OP_HASH(y20) != x10: OP_RETURN
>> else if OP_SIZE (ecdsaSig2) < 59:
>>   if OP_HASH(y21) != x21: OP_RETURN
>> ```
>>
>> Alice computes the ECDSA signatures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For
>> example let’s say OP_SIZE(ecdsaSig0)=59, OP_SIZE(ecdsaSig1)=58,
>> OP_SIZE(ecdsaSig2)=59. Thus, to spend she generates a Lamport signature
>> over those lengths by releasing the preimages: y00, y11, y20.
>>
>> The spend script pseudocode:
>> ```
>> PUSH ecdsaSig0
>> PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 59
>> PUSH ecdsaSig1
>> PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be less than 59
>> PUSH ecdsaSig2
>> PUSH y20 // Signs that OP_SIZE(ecdsaSig2) should be 59
>> ```
>>
>> The advantage Alice has over an attacker attempting to steal her funds is
>> that all Alice has to do is release the preimages for the lengths of all of
>> her ECDSA signatures, but an attacker has  to construct a transaction hash
>> that matches the size of her signatures for each different ECDSA signature.
>> The probability an attacker manages this for three random ECDSA signatures
>> given the lengths above (59,58,59) is 255/256 * 1/256 * 255/256 ~= 0.3%.
>> Alice can arbitrarily amplify her security by adding additional ECDSA
>> signatures.
>>
>> It was pointed out to me by Andrew Poelstra that the probability that a
>> random signature is shorter by one byte is 1/256 because OP_SIZE only
>> measures the byte length of a value, not the bit length. This means most of
>> the time if Alice just used three ECDSA signatures, they would all be
>> length 59. In such a case the attacker would have (255/256)^3 = 98%
>> probability of generating a transaction that can be spent using Alice's
>> signature on the attacker's very first try!
>>
>> For this reason Alice really needs a lot of ECDSA signatures and probably
>> also needs to grind for safer values to sign (safer = high diversity in
>> length).
>>
>> Assuming a simplistic model of ECDSA signatures length Prob(1-1/256) for
>> length 59 and Prob(1/256) for length <59, the probability that Alice will
>> generate exactly m <59-length signatures and n-m 59 length signatures is:
>> `(255/256)^(n-m)*(1/256)^m*(n choose m)`.
>>
>> An attacker would need to not only generate m <59-length signatures and
>> n-m 59 length signatures, but generate them in the same position as Alice
>> generated them. The probability an attacker will generate exactly m
>> <59-length signatures and n-m 59 length signatures in the same position as
>> Alice is: (255/256)^(n-m)*(1/256)^m
>>
>> On average Alice would need 1000 attempts to sign with n=800,m=10.
>> Whereas an attacker would need to make 2^84 attempts to brute force the
>> output after seeing alice attempt to spend that output using a n=800,m=10
>> signature.
>>
>> ## Known weaknesses
>>
>> 1. *The Tuning Attack:* The attacker can use different SIG_HASH flags per
>> signature to attack each signature individually. For instance ecdsaSig1
>> doesn't have the right length, the attacker can try SIGHASH_NONE to try
>> again without changing any of the other signature lengths. This provides
>> the attacker some advantage but with sufficient numbers of signatures it
>> does not break the scheme. Alice can also use this approach to increase the
>> security of her signatures by increasing length diversity. Unclear if this
>> helps or hurts security more.
>>
>> 2. *Mix and Match Attack:* Even if an attacker can not grind a shorter
>> r-value, an r-value of roughly 21-23 bytes would allow an attacker to make
>> a few more individual attempts on a particular signature length. This is
>> because we only measure the total length of the ECDSA signature, so a
>> 23-byte r-value combined with a 29-byte s-value would be 23+29+6 = 58
>> bytes. 29-byte s-value are rare and occur with ~1/2^24 probability, but if
>> an attacker managed to grind a 23-byte r-value at a cost of 2^72
>> computations, it would provide the attacker some advantage.
>>
>> ## Known Improvements
>>
>> 1. Rather than only signing if the length is 59 or less. We could extend
>> the scheme to sign multiple ECDSA signature length values, 59, 58, 57,
>> 56... This could enable Alice to greatly increase her security as say 56
>> would only occur 1 out of every 2^32 signatures. Winternitz One Time
>> signatures (WOTs) [2] could be used here to compress signature length.
>>
>> 1. Jeremy Rubun suggested the following optimization: rather than
>> directly signing the ECDSA signatures lengths, you construct a 32-bit bit
>> vector of the signature lengths using OP_MUL, OP_ADD.
>>
>> bit vector = OP_SIZE(ecdsaSig0)==59 + 2*(OP_SIZE(ecdsaSig1)==59) +
>> 4*(OP_SIZE(ecdsaSig2)==59) ...
>>
>> Then you compute a Winternitz One Time signature over this bit vector.
>> This would require also computing a WInternitz or Lamport signature over a
>> checksum of the bit vector. This would substantially reduce the number of
>> lamport public keys and signing keys and likely reduce the size of redeem
>> script and spend script by half.
>>
>> 3. Since 59 is the default length, Alice does not in fact need to sign
>> 59. It could be inferred that if no preimage is given or say the preimage 0
>> is given, the length that Alice intends is 59. This would save space on the
>> spend script and redeem script.
>>
>>
>> ## Open Questions
>>
>> 1. Could OP_CODESEPARATOR be used by Alice or the attacker to either
>> strengthen or weaken the security of this scheme. Alice using
>> OP_CODESEPARATOR to strengthen the security of this scheme by increasing
>> signature length diversity was suggested by Jeremy Rubin. After some
>> discussion, the fact that the redeem script is part of the P2SH address
>> means that the data in OP_CODESEPARATOR would still influence all the other
>> ECDSA signatures. That said, perhaps there is some way it can be exploited
>> to either help Alice or help the attacker.
>>
>> 2. If a nonce value k was discovered such that k*G = r = 1, we could
>> remove the assumption that no could find a smaller r. It is unknown how to
>> find r=1 as it requires finding the discrete log. It is possible to create
>> transaction signatures that have r=1 without knowing k, through the use of
>> ECDSA pubkey recovery. This does not work for our scheme as we must commit
>> to the ECDSA  public key in the spent transaction. Are there any known
>> smaller r values than r=1/2*G?
>>
>> 3. How many bits of security does each ECDSA signature contribute in this
>> scheme given the SIGHASH mix and match attack above? How many ECDSA
>> signatures are needed? We have modeled ECDSA s-values signatures being
>> uniformly drawn from 2^256. It seems unlikely to me that the Elliptic Curve
>> math lines up perfectly with a 256 bit space especially for a fixed r-value
>> that has special mathematical properties. Non-uniformity here could end up
>> helping (increasing length diversity) or hurting (a pattern an attacker
>> could exploit to match the length faster than brute force) the security.
>>
>> 4. An attacker could trade off brute forcing the transaction hash lengths
>> by computing a small r-value. What does the time-memory trade look like
>> here?
>>
>> 5. Is there any use for this beyond a fun party trick?
>>
>> Thanks to Madars Virza, Dan Gould, Armin Sabouri, Neha Narula, Jeremy
>> Rubin, Andrew Poelstra, Robin Linus for discussing this with me and giving
>> me feedback. This initial discuss was fueled by the MIT DCI espresso
>> machine. I've attempted to credit all ideas contributed to the contributor,
>> if I got this wrong or missed a contribution shoot me an email. Any
>> mistakes are my own as I wrote this up.
>>
>> [0]: "Bitcoin Wallet Recovery via ECDSA Short Signatures"
>> https://github.com/demining/Bitcoin-Wallet-Recovery?tab=readme-ov-file
>>
>> [1]: "Constructing Digital Signatures from a One Way Function", Leslie
>> Lamport (1979),
>> https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/
>>
>> [2]: "A Certified Digital Signature", Ralph C. Merkle (1979),
>> https://www.ralphmerkle.com/papers/Certified1979.pdf
>>
>> [3]: "Timelocked Proof of Work via signature length",  Robin Linus
>> (2021),
>> https://gist.github.com/RobinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md
>>
>> [4]: "Proof of Work in Bitcoin Script", Robin Linus (2020),
>> https://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md
>>
>> [5]: "sig-pow - work-locked outputs", VzxPLnHqr (2022),
>> https://github.com/VzxPLnHqr/sig-pow/
>>
>> [6]: "[Lightning-dev] Better privacy with SNARKs", Anthony Towns (2015),
>> https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html
>>
>> [7]: "Quantum Proofing Bitcoin with a CAT", Jeremy Rubin (2021),
>> https://rubin.io/blog/2021/07/06/quantum-bitcoin/
>>
>> [8]: "CheckSigFromStack for 5 Byte Values", Jeremy Rubin (2021),
>> https://rubin.io/blog/2021/07/02/signing-5-bytes/
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Bitcoin Development Mailing List" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to bitcoindev+unsubscribe@googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com
>> <https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .
>>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BW9x70K-nSW1FvKyK%2BjYn2LnzPR8cRGxPJ4tpKsBzT8fA%40mail.gmail.com.

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

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Andrew Poelstra]

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

On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
> > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
> computations, it would provide the attacker some advantage.
> 
> If we are assuming discrete log is still hard, why do we need Lamport
> signatures at all? In a post-quantum world, finding k such that r is 21
> bytes or less is efficient for the attacker.
>

Aside from Ethan's point that a variant of this technique is still
secure in the case that discrete log is totally broken (or even
partially broken...all we need is that _somebody_ is able to find the
discrete log of the x=1 point and for them to publish this).

Another reason this is useful is that if you have a Lamport signature on
the stack which is composed of SIZE values, all of which are small
enough to be manipulated with the numeric script opcodes, then you can
do covenants in Script.

(Sadly(?), I think none of this works in the context of the 201-opcode
limit...and absent BitVM challenge-response tricks it's unlikely you can
do much in the context of the 4MWu block size limit..), but IMO it's a
pretty big deal that size limits are now the only reason that Bitcoin
doesn't have covenants.)

-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ZjD-dMMGxoGNgzIg%40camus.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Ethan Heilman]

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

One could redesign this scheme to minimize the number of opcodes.

Back of the napkin scheme follows:

Alice, rather than Lamport signing the length of each ECDSA signature,
instead Lamport (or WOTS) signs a vector of the positions of the low-length
ECDSA signatures (low length here means length=58 rather than length=59).
Then the redeem script would only check the length of those particular
signatures and could drop the other other public keys. This saves
significantly on the number of opcodes because we only need to check the
Lamport signature on the vector, no one each signature length and we can
drop unused checked signatures without evaluating them.

Alice's advantage over the attacker is that she gets to fix the positions
of the low length ECDSA signatures after she generates them. This means if
the total number of signatures is N and the number of low length signatures
is M, her advantage over the attacker is (N choose M). For instance if
N=M=10, to generate 10 59-length signatures, Alice needs to perform
2^(8*10) work. This is because we assume the probability of generating a
58-byte ECDSA signature is 1/256 (1/2^8). However if N=40, M=10 she only
needs to perform 2^(8*10)/(40 choose 10) work.

If we assume that we want 80 bits of security, this means we need M=10 low
length ECDCSA signatures (2^(8*10)). The next parameter is how cheap we
want this to be for Alice to compute, we can boost Alice's signing time by
increasing N and remove log2(N choose 10) from the work she needs to
compute the signature. If we want to ensure Alice has to do no more than
2^32 work to sign, then we need N=46 or 46 ecdsa signatures.

On Tue, Apr 30, 2024 at 10:21 AM Andrew Poelstra <apoelstra@wpsoftware.net>
wrote:

> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
> > > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
> > computations, it would provide the attacker some advantage.
> >
> > If we are assuming discrete log is still hard, why do we need Lamport
> > signatures at all? In a post-quantum world, finding k such that r is 21
> > bytes or less is efficient for the attacker.
> >
>
> Aside from Ethan's point that a variant of this technique is still
> secure in the case that discrete log is totally broken (or even
> partially broken...all we need is that _somebody_ is able to find the
> discrete log of the x=1 point and for them to publish this).
>
> Another reason this is useful is that if you have a Lamport signature on
> the stack which is composed of SIZE values, all of which are small
> enough to be manipulated with the numeric script opcodes, then you can
> do covenants in Script.
>
> (Sadly(?), I think none of this works in the context of the 201-opcode
> limit...and absent BitVM challenge-response tricks it's unlikely you can
> do much in the context of the 4MWu block size limit..), but IMO it's a
> pretty big deal that size limits are now the only reason that Bitcoin
> doesn't have covenants.)
>
> --
> Andrew Poelstra
> Director, Blockstream Research
> Email: apoelstra at wpsoftware.net
> Web:   https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
>     -Justin Lewis-Webster
>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BUnxB2vKQpJAa-z-qGZQfpR1ZeW3UyuFFZ6_WTWFYGfjw%40mail.gmail.com.

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

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Antoine Riard]

[-- Attachment #1.1: Type: text/plain, Size: 6527 bytes --]

Hi Ethan,

From my understanding, you're proposing to emulate Lamport signature 
verification / generation
scheme by leveraging the implicit signature digest of the OP_CHECKSIG 
operation, which has been
a valid Bitcoin Script opcode since genesis block. Signature digests is a 
commitment to a bitcoin
transaction fields, and this is verified by the interpreter both for ECDSA 
and Schnorr schemes.

Here you're proposing to use the ECDSA's `k` nonce as a fixed public value 
by committing the
ECDSA-signature length as a parameter of an OP_SIZE and the cleartext `r,s` 
signature itself as
the verification parameter of a OP_SHA256, emulating the h(x) = y for 
Lamport signature range of
bits, all in a redeem script (i.e P2SH).

I don't know if your proposed scheme is secure against message forgery 
attacks or invalid curve
domain parameters, e.g using the point at infinity as your point R, and if 
from them you could play
tricks with coordinates.

On the usage of such emulated Lamport signature scheme in a public 
transaction-relay network,
there is one fundamental security property of Lamport signature to be aware 
off, mainly the one-time
usage. So this is very unclear if as soon you're broadcasting the 
transaction, miners coalition could
withhold the transaction inclusion to trigger the initial signer to reveal 
more a lot of pre-committed
fixed-nonce ECDSA signatures.

Apart of concerns of this scheme in a blockchain and assuming it's not 
utterly broken due to
message forgery attacks, I'm skeptical on the robustness of the scheme as 
the number of on-chain
pre-committed signatures is a parameter of the preimage-resistance of the 
Lamport signature scheme
itself. Sounds a classic time-space tradeoff, by increasing the lot of 
fixed-nonce signatures we're making
it harder to break, even for observers with significant computational 
ressources.

Beyond, 2^64 bit of security doesn't seem a lot in considerations of 
state-of-the-art collision attacks
on hash functions from recent academic literature. And one have to consider 
how you can take the
short-cut by pre-computing rainbow tables for ECDSA r-value of a given 
signature size.

I think a more interesting open question of this post is if we have already 
hash-chain-based covenant
"today" in Bitcoin. If by fixing the integer `z` of the s-value of ECDSA 
signature in redeem script, and
computing backward the chain of chids redeem scripts to avoid hash-chain 
dependencies. This is unclear
what would be the security guarantees and average btc units cost for 
scriptSig / witness under current block
size limit of 4MWU.

Best,
Antoine
Le mardi 30 avril 2024 à 22:18:36 UTC+1, Ethan Heilman a écrit :

> One could redesign this scheme to minimize the number of opcodes.
>
> Back of the napkin scheme follows:
>
> Alice, rather than Lamport signing the length of each ECDSA signature, 
> instead Lamport (or WOTS) signs a vector of the positions of the low-length 
> ECDSA signatures (low length here means length=58 rather than length=59). 
> Then the redeem script would only check the length of those particular 
> signatures and could drop the other other public keys. This saves 
> significantly on the number of opcodes because we only need to check the 
> Lamport signature on the vector, no one each signature length and we can 
> drop unused checked signatures without evaluating them.
>
> Alice's advantage over the attacker is that she gets to fix the positions 
> of the low length ECDSA signatures after she generates them. This means if 
> the total number of signatures is N and the number of low length signatures 
> is M, her advantage over the attacker is (N choose M). For instance if 
> N=M=10, to generate 10 59-length signatures, Alice needs to perform 
> 2^(8*10) work. This is because we assume the probability of generating a 
> 58-byte ECDSA signature is 1/256 (1/2^8). However if N=40, M=10 she only 
> needs to perform 2^(8*10)/(40 choose 10) work.
>
> If we assume that we want 80 bits of security, this means we need M=10 low 
> length ECDCSA signatures (2^(8*10)). The next parameter is how cheap we 
> want this to be for Alice to compute, we can boost Alice's signing time by 
> increasing N and remove log2(N choose 10) from the work she needs to 
> compute the signature. If we want to ensure Alice has to do no more than 
> 2^32 work to sign, then we need N=46 or 46 ecdsa signatures.
>
> On Tue, Apr 30, 2024 at 10:21 AM Andrew Poelstra <apoe...@wpsoftware.net> 
> wrote:
>
>> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
>> > > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
>> > computations, it would provide the attacker some advantage.
>> > 
>> > If we are assuming discrete log is still hard, why do we need Lamport
>> > signatures at all? In a post-quantum world, finding k such that r is 21
>> > bytes or less is efficient for the attacker.
>> >
>>
>> Aside from Ethan's point that a variant of this technique is still
>> secure in the case that discrete log is totally broken (or even
>> partially broken...all we need is that _somebody_ is able to find the
>> discrete log of the x=1 point and for them to publish this).
>>
>> Another reason this is useful is that if you have a Lamport signature on
>> the stack which is composed of SIZE values, all of which are small
>> enough to be manipulated with the numeric script opcodes, then you can
>> do covenants in Script.
>>
>> (Sadly(?), I think none of this works in the context of the 201-opcode
>> limit...and absent BitVM challenge-response tricks it's unlikely you can
>> do much in the context of the 4MWu block size limit..), but IMO it's a
>> pretty big deal that size limits are now the only reason that Bitcoin
>> doesn't have covenants.)
>>
>> -- 
>> Andrew Poelstra
>> Director, Blockstream Research
>> Email: apoelstra at wpsoftware.net
>> Web:   https://www.wpsoftware.net/andrew
>>
>> The sun is always shining in space
>>     -Justin Lewis-Webster
>>
>>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/2775e9e8-4f1a-4f03-a8f0-4a4c2f6e93a9n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 8140 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Ethan Heilman]

Hi Antoine,

> On the usage of such emulated Lamport signature scheme in a public transaction-relay network, there is one fundamental security property of Lamport signature to be aware off, mainly the one-time usage. So this is very unclear if as soon you're broadcasting the transaction, miners coalition could withhold the transaction inclusion to trigger the initial signer to reveal more a lot of pre-committed fixed-nonce ECDSA signatures.

I'm not sure I understand what you are saying here. I agree that once
Alice broadcasts a transaction spending such an output, she can not
double spend that output without losing security. You'd want to define
the unforgeability property to be EU-CMA with only a single signature.
Why would Alice simply just not rebroadcast her original transaction?
If she wants the capability to bump the fees without changing the sig
hash, she can use the SIGHASH flag anyone can pay or CPFP.

> using the point at infinity as your point R, and if from them you could play tricks with coordinates.

What do you mean by this? k=0? I do agree that this scheme is making
some very odd assumptions about ecdsa signatures and they may not
hold. Certainly no one should expect this scheme to be secure without
a proof of security or at the least some sort of justification for why
anyone expects these assumptions to hold.

> Beyond, 2^64 bit of security doesn't seem a lot in considerations of state-of-the-art collision attacks on hash functions from recent academic literature.

I agree that 64 bits of security is nowhere near safe. I used 80 bits
of security in the example because that is the collision resistance of
P2SH. 80-bits is still probably too low.

> And one have to consider how you can take the short-cut by pre-computing rainbow tables for ECDSA r-value of a given signature size.

It's worse than that! Storage and lookup would not require anything so
fancy as rainbow tables. Once you have precomputed a 20 byte r-value
you can use it everywhere. Grinding such an r-value would cost 2^96
queries for 50% success rate, but would let you trivially break any of
these signatures which used a 21 byte r-value with a pen and some
paper. Still, if you could do 2^96 ecdsa queries, it would be
computationally expensive as mining 1,125,899,906,842,620 bitcoin
blocks. You'd probably be better off mining those blocks than grinding
the r-value.

On Wed, May 1, 2024 at 4:57 AM Antoine Riard <antoine.riard@gmail.com> wrote:
>
> Hi Ethan,
>
> From my understanding, you're proposing to emulate Lamport signature verification / generation
> scheme by leveraging the implicit signature digest of the OP_CHECKSIG operation, which has been
> a valid Bitcoin Script opcode since genesis block. Signature digests is a commitment to a bitcoin
> transaction fields, and this is verified by the interpreter both for ECDSA and Schnorr schemes.
>
> Here you're proposing to use the ECDSA's `k` nonce as a fixed public value by committing the
> ECDSA-signature length as a parameter of an OP_SIZE and the cleartext `r,s` signature itself as
> the verification parameter of a OP_SHA256, emulating the h(x) = y for Lamport signature range of
> bits, all in a redeem script (i.e P2SH).
>
> I don't know if your proposed scheme is secure against message forgery attacks or invalid curve
> domain parameters, e.g using the point at infinity as your point R, and if from them you could play
> tricks with coordinates.
>
> On the usage of such emulated Lamport signature scheme in a public transaction-relay network,
> there is one fundamental security property of Lamport signature to be aware off, mainly the one-time
> usage. So this is very unclear if as soon you're broadcasting the transaction, miners coalition could
> withhold the transaction inclusion to trigger the initial signer to reveal more a lot of pre-committed
> fixed-nonce ECDSA signatures.
>
> Apart of concerns of this scheme in a blockchain and assuming it's not utterly broken due to
> message forgery attacks, I'm skeptical on the robustness of the scheme as the number of on-chain
> pre-committed signatures is a parameter of the preimage-resistance of the Lamport signature scheme
> itself. Sounds a classic time-space tradeoff, by increasing the lot of fixed-nonce signatures we're making
> it harder to break, even for observers with significant computational ressources.
>
> Beyond, 2^64 bit of security doesn't seem a lot in considerations of state-of-the-art collision attacks
> on hash functions from recent academic literature. And one have to consider how you can take the
> short-cut by pre-computing rainbow tables for ECDSA r-value of a given signature size.
>
> I think a more interesting open question of this post is if we have already hash-chain-based covenant
> "today" in Bitcoin. If by fixing the integer `z` of the s-value of ECDSA signature in redeem script, and
> computing backward the chain of chids redeem scripts to avoid hash-chain dependencies. This is unclear
> what would be the security guarantees and average btc units cost for scriptSig / witness under current block
> size limit of 4MWU.
>
> Best,
> Antoine
> Le mardi 30 avril 2024 à 22:18:36 UTC+1, Ethan Heilman a écrit :
>>
>> One could redesign this scheme to minimize the number of opcodes.
>>
>> Back of the napkin scheme follows:
>>
>> Alice, rather than Lamport signing the length of each ECDSA signature, instead Lamport (or WOTS) signs a vector of the positions of the low-length ECDSA signatures (low length here means length=58 rather than length=59). Then the redeem script would only check the length of those particular signatures and could drop the other other public keys. This saves significantly on the number of opcodes because we only need to check the Lamport signature on the vector, no one each signature length and we can drop unused checked signatures without evaluating them.
>>
>> Alice's advantage over the attacker is that she gets to fix the positions of the low length ECDSA signatures after she generates them. This means if the total number of signatures is N and the number of low length signatures is M, her advantage over the attacker is (N choose M). For instance if N=M=10, to generate 10 59-length signatures, Alice needs to perform 2^(8*10) work. This is because we assume the probability of generating a 58-byte ECDSA signature is 1/256 (1/2^8). However if N=40, M=10 she only needs to perform 2^(8*10)/(40 choose 10) work.
>>
>> If we assume that we want 80 bits of security, this means we need M=10 low length ECDCSA signatures (2^(8*10)). The next parameter is how cheap we want this to be for Alice to compute, we can boost Alice's signing time by increasing N and remove log2(N choose 10) from the work she needs to compute the signature. If we want to ensure Alice has to do no more than 2^32 work to sign, then we need N=46 or 46 ecdsa signatures.
>>
>> On Tue, Apr 30, 2024 at 10:21 AM Andrew Poelstra <apoe...@wpsoftware.net> wrote:
>>>
>>> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
>>> > > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
>>> > computations, it would provide the attacker some advantage.
>>> >
>>> > If we are assuming discrete log is still hard, why do we need Lamport
>>> > signatures at all? In a post-quantum world, finding k such that r is 21
>>> > bytes or less is efficient for the attacker.
>>> >
>>>
>>> Aside from Ethan's point that a variant of this technique is still
>>> secure in the case that discrete log is totally broken (or even
>>> partially broken...all we need is that _somebody_ is able to find the
>>> discrete log of the x=1 point and for them to publish this).
>>>
>>> Another reason this is useful is that if you have a Lamport signature on
>>> the stack which is composed of SIZE values, all of which are small
>>> enough to be manipulated with the numeric script opcodes, then you can
>>> do covenants in Script.
>>>
>>> (Sadly(?), I think none of this works in the context of the 201-opcode
>>> limit...and absent BitVM challenge-response tricks it's unlikely you can
>>> do much in the context of the 4MWu block size limit..), but IMO it's a
>>> pretty big deal that size limits are now the only reason that Bitcoin
>>> doesn't have covenants.)
>>>
>>> --
>>> Andrew Poelstra
>>> Director, Blockstream Research
>>> Email: apoelstra at wpsoftware.net
>>> Web:   https://www.wpsoftware.net/andrew
>>>
>>> The sun is always shining in space
>>>     -Justin Lewis-Webster
>>>
> --
> You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/2775e9e8-4f1a-4f03-a8f0-4a4c2f6e93a9n%40googlegroups.com.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXjPwsst%3DrU5KS%3D%3DF8VfXaLtcfgoWt2CuY%2BhBMmLXhCsA%40mail.gmail.com.

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[David A. Harding]

On 2024-04-30 04:21, Andrew Poelstra wrote:
> Another reason this is useful is that if you have a Lamport signature 
> on
> the stack which is composed of SIZE values, all of which are small
> enough to be manipulated with the numeric script opcodes, then you can
> do covenants in Script.

Hi Andrew,

I don't understand the above.  I think of a covenant as a script that is 
able to restrict the scriptPubKey of the transaction that spends it.  As 
I understand Heilman's description, a lamport signature commits to the 
size of an ECDSA signature (which can naturally vary) and the ECDSA 
signature commits to the spending transaction.  Performing the lamport 
verification on the stack is practically equivalent to 
OP_CHECKSIGFROMSTACK, which is half of what you need for a covenant.  As 
you've previously described[1], the other half is some method for 
introspection.  How do lamport signatures offer introspection when 
they're restricted to committing to ECDSA signatures that can't be known 
at the time a script is created due to circular dependency in hashing 
(i.e., the ECDSA signature commits to the spending transaction, which 
commits to the previous transaction's txid, which commits to the 
script)?

Thanks!,

-Dave

[1] https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/47711dc4ffe9d661e8321b05b6adab4e%40dtrt.org.

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Andrew Poelstra]

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

On Sun, May 05, 2024 at 09:39:51PM -1000, David A. Harding wrote:
> 
> Hi Andrew,
> 
> I don't understand the above.  I think of a covenant as a script that is
> able to restrict the scriptPubKey of the transaction that spends it.  As I
> understand Heilman's description, a lamport signature commits to the size of
> an ECDSA signature (which can naturally vary) and the ECDSA signature
> commits to the spending transaction.  Performing the lamport verification on
> the stack is practically equivalent to OP_CHECKSIGFROMSTACK, which is half
> of what you need for a covenant.  As you've previously described[1], the
> other half is some method for introspection.  How do lamport signatures
> offer introspection when they're restricted to committing to ECDSA
> signatures that can't be known at the time a script is created due to
> circular dependency in hashing (i.e., the ECDSA signature commits to the
> spending transaction, which commits to the previous transaction's txid,
> which commits to the script)?
>

Aside from limits on transaction size, post-Taproot script can verify a
trace of any program execution, as long as the individual elements it is
operating on fit into 4-byte CScriptNums. You can therefore implement
SHA2, ECDSA, etc., and reconstruct the pattern of SIZE elements by
feeding in transaction data. Which of course can then be arbitrarily
constrained.

Probably actually doing this would take more than 4 megs of script and
you would need to use some sort of BitVM tricks and the whole thing
might not work. But this was my point in saying that "only the script
limits are stopping us from having covenants".

And pre-Taproot we have only 201 opcodes so of course this is all
totally out of the question :) but plausibly we could make a copy of the
Lamport signature in a Taproot output and then use non-equivocation
slashing conditions to somehow make things work.


-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ZjkJ0fPyzuAPTLWS%40camus.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[David A. Harding]

On 2024-05-06 06:48, Andrew Poelstra wrote:
> [...] post-Taproot script can verify a
> trace of any program execution, as long as the individual elements it 
> is
> operating on fit into 4-byte CScriptNums. You can therefore implement
> SHA2, ECDSA, etc., and reconstruct the pattern of SIZE elements by
> feeding in transaction data. Which of course can then be arbitrarily
> constrained.

Thanks for your answer!  I think I understand.  However, we don't have 
ECDSA in tapscript; all signatures in tapscript are 64 bytes plus an 
optional sighash byte, so there's no natural variation in signature 
size.

-Dave

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/a5a86fcd50e2cdbdf40a12ac9463a828%40dtrt.org.

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Andrew Poelstra]

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

On Mon, May 06, 2024 at 08:56:21AM -1000, David A. Harding wrote:
> On 2024-05-06 06:48, Andrew Poelstra wrote:
> > [...] post-Taproot script can verify a
> > trace of any program execution, as long as the individual elements it is
> > operating on fit into 4-byte CScriptNums. You can therefore implement
> > SHA2, ECDSA, etc., and reconstruct the pattern of SIZE elements by
> > feeding in transaction data. Which of course can then be arbitrarily
> > constrained.
> 
> Thanks for your answer!  I think I understand.  However, we don't have ECDSA
> in tapscript; all signatures in tapscript are 64 bytes plus an optional
> sighash byte, so there's no natural variation in signature size.
>

You can implement ECDSA. It will just take a *lot* of opcodes.

-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ZjkqIzPSFLc0GJJ1%40camus.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Antoine Riard]

[-- Attachment #1.1: Type: text/plain, Size: 6410 bytes --]

Hi Ethan,

> I'm not sure I understand what you are saying here. I agree that once
> Alice broadcasts a transaction spending such an output, she can not
> double spend that output without losing security. You'd want to define
> the unforgeability property to be EU-CMA with only a single signature.
> Why would Alice simply just not rebroadcast her original transaction?
> If she wants the capability to bump the fees without changing the sig
> hash, she can use the SIGHASH flag anyone can pay or CPFP.

If my understanding of your scheme is correct, the Lamport public key
(e.g x00 == Hash(y00) is committed in the redeem script of a said UTXO.
scriptpubkey.

I think this opens the following denial-of-service attack by adversaries
with hashrate capabilities:
- Alice Lamport-emulated signs and broadcast her transaction X
- Coalition of Miners (e.g 30% of network) refuse to include Alice's 
transaction X
- Alice can:
        - a) wait for the 70% honest network to mine her transaction
        - b) increase her feerate to bump incentives to mine transaction X
- If Alice picks up option b)
        - Alice Lamport-emulated signs and broadcast her transaction X by 
using ACP flag / CPFP
        - This assumes the consumption of a "fresh" fee-bumping UTXO
        - This fee-bumping UTXO can be locked under a Lamport 
emulated-pubkey

I think this scheme with a one-time usage property is more exposed to 
denial-of-service
attacks (or wallet UTXO deanonymization) than ECDSA / Schnorr scheme.

I believe you might even have a worst-case scenario of this DoS where a 
coalition
of mining attackers force you to one-time sig all your Lamport pubkeys 
committed
in UTXOs (original UTXO + fee-bumping UTXOs), in a way that the orignal 
UTXO cannot
be moved because its feerate is perpetually under mempool min fee, or the 
marginal
ancestor feerate unit of miners block templates.

I don't know if this vector of attack is correct, however one can note it 
could arise
in alternative spontaneous scenarios, such as second-layers scarce 
liquidity allocation
(e.g dual-funding), where many UTXOs concurrent spends might compete to 
confirm first.

> What do you mean by this? k=0? I do agree that this scheme is making
> some very odd assumptions about ecdsa signatures and they may not
> hold. Certainly no one should expect this scheme to be secure without
> a proof of security or at the least some sort of justification for why
> anyone expects these assumptions to hold.

I think the ECDSA signature verification algorithm forbids the usage
of the point at infinity for the curve point resulting from the modular
arithmetic on your r-value and s-value, not k=0 where k is the nonce.

I don't know if you could play with the transaction hash to produce
a curve point which is equals to the point at infinity, especially in
context where the transaction hash is including inputs from multiple
non-trusted counterparties (e.g if you're using SIGHASH flags).

> It's worse than that! Storage and lookup would not require anything so
> fancy as rainbow tables. Once you have precomputed a 20 byte r-value
> you can use it everywhere. Grinding such an r-value would cost 2^96
> queries for 50% success rate, but would let you trivially break any of
> these signatures which used a 21 byte r-value with a pen and some
> paper. Still, if you could do 2^96 ecdsa queries, it would be
> computationally expensive as mining 1,125,899,906,842,620 bitcoin
> blocks. You'd probably be better off mining those blocks than grinding
> the r-value.

Well, we're not comparing "apple-to-apple" here as on one side you have
modular arithmetic operations, on the other side bitwise rotations. I'm
thinking you might have an advantage in your ecdsa queries as a finite field
is, as the name say so, "finite" so you could theoretically pre-compute all
entries in your storage. On the other hand, with block mining (even assuming
a functional implementation of Grover's algorithm) you have lookup and
propagation latency under 10 min in average. Sounds you can parellize both
problems resolution (re-use hash round states or point addition), so it 
might
be just a classicla time-space trade-off here.

> I think a more interesting open question of this post is if we have 
already hash-chain-based covenant
> "today" in Bitcoin. If by fixing the integer `z` of the s-value of ECDSA 
signature in redeem script, and
> computing backward the chain of chids redeem scripts to avoid hash-chain 
dependencies. 

Correcting myself on my initial email, the design bottleneck here is 
obviously
that spent outpoints are committed in a child signature digest in a no-APO 
world.
This is still an interesting question if you can remove spent outpoints 
commitment
by leveraging OP_SIZE or fixing other ECDSA signature components.

Best,
Antoine

Le lundi 6 mai 2024 à 20:25:33 UTC+1, Andrew Poelstra a écrit :

> On Mon, May 06, 2024 at 08:56:21AM -1000, David A. Harding wrote:
> > On 2024-05-06 06:48, Andrew Poelstra wrote:
> > > [...] post-Taproot script can verify a
> > > trace of any program execution, as long as the individual elements it 
> is
> > > operating on fit into 4-byte CScriptNums. You can therefore implement
> > > SHA2, ECDSA, etc., and reconstruct the pattern of SIZE elements by
> > > feeding in transaction data. Which of course can then be arbitrarily
> > > constrained.
> > 
> > Thanks for your answer! I think I understand. However, we don't have 
> ECDSA
> > in tapscript; all signatures in tapscript are 64 bytes plus an optional
> > sighash byte, so there's no natural variation in signature size.
> >
>
> You can implement ECDSA. It will just take a *lot* of opcodes.
>
> -- 
> Andrew Poelstra
> Director, Blockstream Research
> Email: apoelstra at wpsoftware.net
> Web: https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
> -Justin Lewis-Webster
>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/bd37a9f1-7fb9-4111-a069-31c3665073d2n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 7876 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[David A. Harding]

On 2024-05-06 09:06, Andrew Poelstra wrote:
> You can implement ECDSA. It will just take a *lot* of opcodes.

I'll accept that as a given, but how do you know that a given ECDSA 
signature actually commits to the transaction that contains it if 
OP_CHECKSIG only operates on fixed-size schnorr signatures?

Is this what you're describing: if the controlling signature is a 
lamport signature that commits to an ECDSA signature, it's safe to 
disclose the private key for the ECDSA signature; when you don't have to 
worry about private key disclosure, it's safe to construct a schnorr 
signature that uses the same private key, nonce, and message commitment 
as the ECDSA signature; if that schnorr signature makes OP_CHECKSIG 
return true, then you know the message is the current transaction?

That still leaves me confused.  If ECDSA can be implemented within 
tapscript, then I would expect that schnorr could also be implemented 
within tapscript; that gives you an OP_CSFS equivalent.  If being able 
to implement ECDSA in tapscript allows introspection, then I would 
expect implementing schnorr in tapscript would allow introspection; that 
gives you an OP_CAT equivalent.  If you have OP_CSFS and OP_CAT, you 
have covenants and there's no need for lamport signatures or ECDSA.

Apologies for my remaining confused in the face of something that's 
probably obvious,

-Dave





-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/93b8ed39b0aa3955eb9cb99f9fc5aae9%40dtrt.org.

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Andrew Poelstra]

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

On Mon, May 06, 2024 at 06:11:48PM -1000, David A. Harding wrote:
> On 2024-05-06 09:06, Andrew Poelstra wrote:
> > You can implement ECDSA. It will just take a *lot* of opcodes.
> 
> I'll accept that as a given, but how do you know that a given ECDSA
> signature actually commits to the transaction that contains it if
> OP_CHECKSIG only operates on fixed-size schnorr signatures?
> 

You need to connect your Lamport signature to an ECDSA CHECKSIG (in a
pre-Taproot output). So what I'm depending on here is that it's possible
to "copy the signature" from a pre-Taproot spend to a post-Taproot spend
by using Lamport signatures and some anti-equivocation scheme.

In pre-Taproot we confirm that the signature matches the pattern of
OP_SIZE outputs. In post-Taproot we reconstruct the signature and
constrain the transaction, checking that it spends *both* the
pre-Taproot and the post-Taproot output.

> Is this what you're describing: if the controlling signature is a lamport
> signature that commits to an ECDSA signature, it's safe to disclose the
> private key for the ECDSA signature; when you don't have to worry about
> private key disclosure, it's safe to construct a schnorr signature that uses
> the same private key, nonce, and message commitment as the ECDSA signature;
> if that schnorr signature makes OP_CHECKSIG return true, then you know the
> message is the current transaction?
> 

Nope, in this scheme we are avoiding Schnorr signatures entirely.

> That still leaves me confused.  If ECDSA can be implemented within
> tapscript, then I would expect that schnorr could also be implemented within
> tapscript; that gives you an OP_CSFS equivalent.  If being able to implement
> ECDSA in tapscript allows introspection, then I would expect implementing
> schnorr in tapscript would allow introspection; that gives you an OP_CAT
> equivalent.  If you have OP_CSFS and OP_CAT, you have covenants and there's
> no need for lamport signatures or ECDSA.
>

Implementing ECDSA in Tapscript *only* allows introspection in
conjunction with the ability to force a user to spend a Tapscript output
alongside a pre-Tapscript output containing the same ECDSA signature.
And I am waving my hands and saying that I think you can force this by
using covenant tricks.

> Apologies for my remaining confused in the face of something that's probably
> obvious,
> 

Lol. This whole thing is kinda insane.

-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/Zjo72iTDYjwwsXW3%40camus.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Ethan Heilman]

Hi Antoine,

Responding in line:


> - Alice can:
>         - a) wait for the 70% honest network to mine her transaction
>         - b) increase her feerate to bump incentives to mine transaction X
> - If Alice picks up option b)
>         - Alice Lamport-emulated signs and broadcast her transaction X by using ACP flag / CPFP
>         - This assumes the consumption of a "fresh" fee-bumping UTXO
>         - This fee-bumping UTXO can be locked under a Lamport emulated-pubkey
>
> I think this scheme with a one-time usage property is more exposed to denial-of-service
> attacks (or wallet UTXO deanonymization) than ECDSA / Schnorr scheme.

It sounded like originally you were saying she can't bump her fee
without double signing, but as you point out ANYONECANPAY or CPFP
let's you do fee bumping without double signing. This doesn't seem
different from say a pre-signed bitcoin transaction that you can't
change transaction hash of.

> I think the ECDSA signature verification algorithm forbids the usage
> of the point at infinity for the curve point resulting from the modular
> arithmetic on your r-value and s-value, not k=0 where k is the nonce.
>
> I don't know if you could play with the transaction hash to produce
> a curve point which is equals to the point at infinity, especially in
> context where the transaction hash is including inputs from multiple
> non-trusted counterparties (e.g if you're using SIGHASH flags).

I don't see the attack. If the point at infinity is forbidden, how is
this exploited? Wouldn't the attacker's signature just be rejected by
the network?

> Well, we're not comparing "apple-to-apple" here as on one side you have
> modular arithmetic operations, on the other side bitwise rotations. I'm
> thinking you might have an advantage in your ecdsa queries as a finite field
> is, as the name say so, "finite" so you could theoretically pre-compute all
> entries in your storage. On the other hand, with block mining (even assuming
> a functional implementation of Grover's algorithm) you have lookup and
> propagation latency under 10 min in average. Sounds you can parellize both
> problems resolution (re-use hash round states or point addition), so it might
> be just a classicla time-space trade-off here.

If someone discovers a smaller r than used in the signatures, they
would break the existing signatures I agree. Grover's might break P2SH
in general so Bitcoin might be in real trouble at that point.

> Correcting myself on my initial email, the design bottleneck here is obviously
> that spent outpoints are committed in a child signature digest in a no-APO world.
> This is still an interesting question if you can remove spent outpoints commitment
> by leveraging OP_SIZE or fixing other ECDSA signature components.

No APO?

Thanks,
Ethan

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BX-bhUuDxyYQ-MJGA49BgvnHW9-7L3zvBLPyJux%3DkqYbA%40mail.gmail.com.

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Ben Carman]

[-- Attachment #1.1: Type: text/plain, Size: 2743 bytes --]

I think it is possible to get past the 201 op code limit doing it in 
tapscript. I don't think it would have the same quantum security but could 
maybe be a path to covenants. My understanding is that you're using the 
OP_SIZE of the sig to basically decide to verify if the bit is a 0 or a 1, 
then do that verification. You could do the same trick with schnorr sigs, 
just for 0 bits don't include the sighash_all flag, and for 1 bits include 
it. This would allow you to get around all the resource limits that taproot 
lifted. This still should be safe since the the signature commits to if it 
is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable very 
complex things or just let you do it on 1 bit of information in tapscript.

Best,
benthecarman

On Tuesday, April 30, 2024 at 9:22:54 AM UTC-5 Andrew Poelstra wrote:

> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
> > > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
> > computations, it would provide the attacker some advantage.
> > 
> > If we are assuming discrete log is still hard, why do we need Lamport
> > signatures at all? In a post-quantum world, finding k such that r is 21
> > bytes or less is efficient for the attacker.
> >
>
> Aside from Ethan's point that a variant of this technique is still
> secure in the case that discrete log is totally broken (or even
> partially broken...all we need is that _somebody_ is able to find the
> discrete log of the x=1 point and for them to publish this).
>
> Another reason this is useful is that if you have a Lamport signature on
> the stack which is composed of SIZE values, all of which are small
> enough to be manipulated with the numeric script opcodes, then you can
> do covenants in Script.
>
> (Sadly(?), I think none of this works in the context of the 201-opcode
> limit...and absent BitVM challenge-response tricks it's unlikely you can
> do much in the context of the 4MWu block size limit..), but IMO it's a
> pretty big deal that size limits are now the only reason that Bitcoin
> doesn't have covenants.)
>
> -- 
> Andrew Poelstra
> Director, Blockstream Research
> Email: apoelstra at wpsoftware.net
> Web: https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
> -Justin Lewis-Webster
>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 3904 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Andrew Poelstra]

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

On Wed, May 08, 2024 at 05:31:18PM -0700, Ben Carman wrote:
> I think it is possible to get past the 201 op code limit doing it in 
> tapscript. I don't think it would have the same quantum security but could 
> maybe be a path to covenants. My understanding is that you're using the 
> OP_SIZE of the sig to basically decide to verify if the bit is a 0 or a 1, 
> then do that verification. You could do the same trick with schnorr sigs, 
> just for 0 bits don't include the sighash_all flag, and for 1 bits include 
> it. This would allow you to get around all the resource limits that taproot 
> lifted. This still should be safe since the the signature commits to if it 
> is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable very 
> complex things or just let you do it on 1 bit of information in tapscript.
>

If I'm understanding you right, then what you're signing is your choice
of sighash flags, rather than anything inherent to the transaction. So I
don't think this works.

-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ZjzFtus_aBchwKz2%40camus.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Antoine Riard]

[-- Attachment #1.1: Type: text/plain, Size: 4221 bytes --]

Hi Ethan,

> It sounded like originally you were saying she can't bump her fee
> without double signing, but as you point out ANYONECANPAY or CPFP
> let's you do fee bumping without double signing. This doesn't seem
> different from say a pre-signed bitcoin transaction that you can't
> change transaction hash of.

With lamport signature, the public key is committed in the coin. Once
you're spending the coin, the secret key must be revealed to commit to
the transaction hash. The secret key cannot be re-used to commit to
another transaction hash and the spend *in its current state* must be
included in the chain.

With pre-signed bitcoin transaction under ecdsa / schnorr, the signer
group can change the transaction hash (e.g adjust destination or feerate),
assuming "off-chain" interactivity.

> I don't see the attack. If the point at infinity is forbidden, how is
> this exploited? Wouldn't the attacker's signature just be rejected by
> the network?

Yes, a pair of ecdsa (r, s) integers verifying as a point at infinity
would be rejected by the network. Assume short r-value that can be guessed
by the attacker, the k nonce is fixed and the attacker can contribute to
the transaction hash. Can the attacker contributes to the transaction hash
in way the pair of ecdsa (r, s) verifies as a point at infinity ?

I don't think the attack works as the private key d is still assume to
be secret here, and the computational space to find short-r and hash 
contribution inputs to provoke a point at infinity collision sounds to be 
huge.
Though I cannot convince myself without a more fleshed scheme.

> If someone discovers a smaller r than used in the signatures, they
> would break the existing signatures I agree. Grover's might break P2SH
> in general so Bitcoin might be in real trouble at that point.

I still wonder if you could have tree of such lamport pubkeys, to have more
sounds true lamport signature with a 1-to-1 bit mapping between transaction
bit and lamport secret key bit ? Sounds you will hit consensus limits. And 
yeah
note Grover's algo could also be used to break proof-of-work mining races,
so trouble.

> No APO?

There is a "faux-ctv" variant I think known by a lot of people, where with
bip118 anyprevout you can have no-input signature committed in the redeem 
script.
A way to have ensure any spending child is a valid pre-image of the 
signature digest.

Best,
Antoine

Le jeudi 9 mai 2024 à 13:49:04 UTC+1, Andrew Poelstra a écrit :

> On Wed, May 08, 2024 at 05:31:18PM -0700, Ben Carman wrote:
> > I think it is possible to get past the 201 op code limit doing it in 
> > tapscript. I don't think it would have the same quantum security but 
> could 
> > maybe be a path to covenants. My understanding is that you're using the 
> > OP_SIZE of the sig to basically decide to verify if the bit is a 0 or a 
> 1, 
> > then do that verification. You could do the same trick with schnorr 
> sigs, 
> > just for 0 bits don't include the sighash_all flag, and for 1 bits 
> include 
> > it. This would allow you to get around all the resource limits that 
> taproot 
> > lifted. This still should be safe since the the signature commits to if 
> it 
> > is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable 
> very 
> > complex things or just let you do it on 1 bit of information in 
> tapscript.
> >
>
> If I'm understanding you right, then what you're signing is your choice
> of sighash flags, rather than anything inherent to the transaction. So I
> don't think this works.
>
> -- 
> Andrew Poelstra
> Director, Blockstream Research
> Email: apoelstra at wpsoftware.net
> Web: https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
> -Justin Lewis-Webster
>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/9e48edb6-1909-4eee-a0c7-48123f42a198n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 5530 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Vicky]

[-- Attachment #1.1: Type: text/plain, Size: 16654 bytes --]

Great and fascinating discussion and detailed analysis, particularly Adam, 
for the rigorous mathematical examination of the signature size 
distribution.

A few observations and questions:

1. The insight about signature size correlation when using the same z and r 
is particularly important. While using different SIGHASH flags provides 
some independence, the ~15 bits of security per 6-signature batch makes 
this construction impractical under current Bitcoin script limits.

2. Regarding Adam's idea of PoW-locked outputs, could you elaborate more on 
how exactly you envision tuning the mining difficulty using two private 
keys? This interesting direction could be more practical than the full 
Lamport signature scheme.

3. One additional consideration about the security model: Even if we could 
achieve higher bits of security through more signatures, wouldn't the 
resource requirements (script size, verification time) make this 
impractical for most use cases compared to existing quantum-resistant 
signature schemes that could be added through a soft fork?

While perhaps not immediately practical, this exploration has helped 
illuminate some interesting properties of ECDSA signature size 
distributions and potential applications beyond Lamport signatures.
Thanks
Vicky

On Wednesday, September 25, 2024 at 8:48:04 PM UTC-4 Adam Borcany wrote:

> So, some more notes on this...
>
> I figured we can use OP_CODESEPARATOR to have more variety over the *z *value, 
> with OP_CODESEPARATOR we can get pretty much unlimited variety (well only 
> limited by the script limit), so by requiring that 6 short signatures (a 
> signature batch) are published for every OP_CODESEPRATOR part we can force 
> anyone to use all the possible sighashes for the signatures.
>
> As for the security of these 6 short signatures (size<59), it seems like 
> we only get ~15bits of security for every batch of those, here is the 
> intuition about it from the perspective of an attacker...
> 1. Attacker starts with SIGHASH_NONE | ANYONECANPAY and grinds the 
> transaction locktime, version & input sequence number, such that it 
> produces a valid short signature under the same pubkey as original signer 
> (this has 6/256 odds)
> 2. Attacker then continues with SIGHASH_NONE by grinding the 2nd 
> transaction input (e.g. the sequence number of it), such that it again 
> produces a valid short signature under the same pubkey as the original 
> signer (this has 5/256 odds)
> 3. Attacker continues with SIGHASH_SINGLE | ANYONECANPAY & SIGHASH_SINGLE 
> by grinding the transaction's 1st output - these have to go together, 
> because there is no field that the attacker can manipulate such that it 
> changes only one of those (this has (4*3)/65536 odds)
> 4. Attacker finishes with SIGHASH_ALL | ANYONECANPAY & SIGHASH_ALL by 
> grinding the transaction's 2nd output - these again have to go together, 
> because there is no field that the attacker can manipulate such that it 
> changes only one of those (this has  (2*1)/65536 odds)
> The reason for the numerator here not being 1 is because the attacker can 
> present the different sighash signatures in any order, so that he can 
> choose from 6 different public keys in the first step, 5 in the second step 
> and so on.
>
> So with this we can get reasonable security (90bits) by using 6 batches of 
> these signatures (36 short signatures in total), which leads to the only 
> problem of all of this - non-push opcode limit for p2wsh redeem scripts, 
> which is just 201 non-push opcodes. Here is a simple script to just check 
> if a single signature was valid:
> # scriptSig 
> <pubkey index> 
> <short signature>
>
> # scriptPubkey
> <pubkey n>
> ...
> <pubkey 1>
> <pubkey 0>
>
> n+1 OP_ROLL OP_DUP OP_SIZE 59 OP_EQUALVERIFY #verify signature length
> n+2 OP_ROLL OP_ROLL #get the public key
> OP_CHECKSIGVERIFY #check signature matches
>
> It has 7 non-push opcodes, and doesn't include any lamport signature 
> checking, purely just checks if a signature is short & signed under valid 
> public key from the set of n public keys. So for 36 signatures you'd end up 
> with at least 252 non-push opcodes, already above the opcode count limit.
>
> Also important to note is that the 90bit security only applies to 
> pre-image resistance & second pre-image resistance. Due to the birthday 
> paradox the collision resistance is just 45bits, which is good enough if 
> you just want to use it for quantum resistant signatures, but for the use 
> case I was thinking about (double-spend protection for zero-conf 
> transactions) it is not enough, since malicious signer can find 2 colliding 
> transactions, submit the first one, and then double-spend with the second 
> one and not equivocate the lamport signature scheme. To achieve 90bit 
> collision resistance we would need 72 short signatures & at least 504 
> non-push opcodes.
>
> Another direction I was thinking about was using the public keys 
> themselves as kind of a lamport signature scheme. The scriptPubkey would 
> only contain *n* RIPEMD-160 commitments to the public keys & then the 
> signer will reveal *m* of these public keys and provide a short ECDSA 
> signature to them. The signer would essentially reveal *m *out of the *n *public 
> keys* (pre-images) *and that would act as a signature, the order should 
> not be important. The security of this pre-image reveal scheme is log2(*n* 
> choose *m*) bits, but it gets very tricky when then talking about the 
> actual short signature security, because now that order is not at all 
> important, the attacker can choose any of the *m *revealed public keys to 
> match the first signature (instead of 6), *m*-1 for the second (instead 
> of 5), and so on... I tried to outline that in the spreadsheet and using 
> m=256, n=30 we only get 51bits of security.
>
> Cheers,
> Adam
>
>
>
> On Wed, 25 Sept 2024 at 00:19, Adam Borcany <adamb...@gmail.com> wrote:
>
>> > Do I understand correctly that you are saying that the size of each 
>> signature from a set of signatures is not independently sampled as long as 
>> all the signatures use the same z and r? 
>>
>> Yes, correct, every private key d adds a 2^248 wide interval (actually 
>> two 2^247 wide intervals) of possible transaction hash values z, these 
>> intervals can have no overlap (meaning only one of the signature will ever 
>> be short), or can overlap and in that case the both signatures will be 
>> short only if the transaction hash is at this overlapping region.
>>
>> > Could this scheme be saved by the fact that z need not be the same for 
>> each signature? For instance by using SIGHASH flags to re-randomize z for 
>> each signature. Wouldn't that restore independence?
>>
>> So there are 6 possible sighash flags, but SIGHASH_NONE | ANYONECANPAY 
>> don't provide any security as it can be re-used by the attacker (as 
>> attacker can just add its own output), also SIGHASH_NONE only helps with 
>> security if the transaction's 2nd input is a keyspend (p2pkh, p2wpkh, p2tr) 
>> and uses SIGHASH_ALL, otherwise attacker is able to just re-use that 
>> signature as well, so at best we can have 5 different sighashes that 
>> contribute to the security. This makes the scheme somewhat better - if 
>> you use 256 private keys (such that they collectively span the full space 
>> of the finite field), you can be sure that for the same z only 1 of them 
>> will ever be short, so if you require 6 of them to be short the only way 
>> for that to happen is that the 6 signatures use different SIGHASH and 
>> therefore use different z. I think this improves the security somewhat, 
>> signer will produce 6 short signatures with different sighashes (maybe he 
>> needs to do a bit of grinding, but really little, like 1-5 iterations), the 
>> attacker would then have to construct a transaction such that 5 different 
>> signatures (under different sighash) would need to have the same position 
>> as when the signer generated them (only 5 because attacker can re-use the SIGHASH_NONE 
>> | ANYONECANPAY signature), the probability of that happening is 
>> something around 1/2^40, so this means 2^40 more work for the attacker. 
>> This still scales with the number of public keys, such that the probability 
>> of an attacker finding the valid solution is (1/{number of keys})^5. For 
>> reasonable security (e.g. 80-bit) we would need 2^16 public keys, which 
>> doesn't actually sound super crazy, but is still too much for bitcoin.
>>
>> > How much harder is this? Couldn't the locking script secretly commit to 
>> a large number of public keys where some subset is opened by the spender. 
>> Thus, generate z to provide a signature with sufficient numbers of small 
>> size signatures to prevent brute force? That is, commit to say 1024 public 
>> keys and then only reveal 64 public key commitments to give the party who 
>> knows preimages of the public keys an advantage? 
>>
>> This would only help if you could create a vector commitment of the 
>> public keys (e.g. merkle tree), such that you can then only reveal some of 
>> them (based on my previous paragraph, you just need to reveal 6 public keys 
>> & signatures), and for the commitment to not blow up the script size. 
>> Committing to 1024 public keys by hash (or even use 1024 raw public keys) 
>> is out of the question because the p2wsh script size is limited to 10kB.
>>
>> On a different note... I also started thinking about this in the context 
>> of PoW locked outputs. It turns out you can fine-tune the mining difficulty 
>> by just using 2 private keys, and making sure their possible transaction 
>> hash *z* intervals overlap in such a way that it creates an interval of 
>> fixed width, the PoW is then just about making sure the transaction hash 
>> lands into this interval - so actually no modular arithmetic needed, it is 
>> purely double-SHA256 hashing of the transaction and checking if the value 
>> is within the interval.
>>
>> Cheers,
>> Adam
>>
>> On Tue, 24 Sept 2024 at 23:08, Ethan Heilman <eth...@gmail.com> wrote:
>>
>>> Thanks for looking into this and writing this up. It is very exciting to 
>>> see someone look into this deeper.
>>>
>>> Do I understand correctly that you are saying that the size of each 
>>> signature from a set of signatures is not independently sampled as long as 
>>> all the signatures use the same z and r?
>>>
>>> Could this scheme be saved by the fact that z need not be the same for 
>>> each signature? For instance by using SIGHASH flags to re-randomize z for 
>>> each signature. Wouldn't that restore independence?
>>>
>>> >  You can increase the number of private keys & let the intervals 
>>> overlap (and then use the intersection of any 2 adjacent private key 
>>> intervals by requiring 2 short signatures), but this will just make it much 
>>> harder to produce a signature (as the z value will now have to land at the 
>>> intersection of the intervals)
>>>
>>> How much harder is this? Couldn't the locking script secretly commit to 
>>> a large number of public keys where some subset is opened by the spender. 
>>> Thus, generate z to provide a signature with sufficient numbers of small 
>>> size signatures to prevent brute force? That is, commit to say 1024 public 
>>> keys and then only reveal 64 public key commitments to give the party who 
>>> knows preimages of the public keys an advantage?
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Mon, Sep 23, 2024 at 5:37 PM Adam Borcany <adamb...@gmail.com> wrote:
>>>
>>>> Hello Ethan,
>>>>
>>>> > 3. We have modeled ECDSA s-values signatures being uniformly drawn 
>>>> from 2^256. It seems unlikely to me that the Elliptic Curve math lines up 
>>>> perfectly with a 256 bit space especially for a fixed r-value that has 
>>>> special mathematical properties. 
>>>>
>>>> I've been looking into this more deeply, and it would seem like it's 
>>>> not random at all, let me explain the intuition...
>>>> If we take the signing equation for the *s* value:
>>>> s = k^-1*(z+rd) mod n
>>>> Considering that *k* is fixed and is set to 1/2 we get:
>>>> s = 2*(z+rd) mod n
>>>> We can let *x *= *rd* being a constant, since *r* is fixed (because *k* 
>>>> is fixed) and *d* is fixed at contract creation time:
>>>> s = 2*(z+x) mod n
>>>> Now for the size of the signature to be 59 or less, the *s* value 
>>>> needs to be smaller than 2^248, but since inequality isn't defined over 
>>>> finite fields, we can create a set of all the integers 0..2^248 and then 
>>>> see if the s value is contained in this set:
>>>> s ∈ {i ∈ Z | i < 2^248} 
>>>> 2*(z+x) ∈ {i ∈ Z | i < 2^248} 
>>>> We now can divide the whole condition by 2:
>>>> (z+x) ∈ {i/2 | i < 2^248}
>>>> Which we can write as (keep in mind i/2 is division in the finite 
>>>> field): 
>>>> (z+x) ∈ {i ∈ Z | i < 2^247} ∪ {i ∈ Z | n div 2 + 1 ≤ i < n div 2 + 1 + 
>>>> 2^247}, where div is integer division
>>>> By then subtracting *x* from both sides we finally get:
>>>> z ∈ {i - x mod n | i < 2^247} ∪ {i - x mod n | n div 2 + 1 ≤ i < n div 
>>>> 2 + 1 + 2^247}
>>>> Which can be also be represented on the finite field circle & it helps 
>>>> with the intuition:
>>>> [image: ecdsa-opsize-lamport.png]
>>>> Here *x *is set to 0 for simplicity.
>>>>
>>>> What this shows is that the signature size being 59 or less depends on 
>>>> the transaction hash *z* (technically *z* is just left-most bits of 
>>>> the transaction hash) being in the specified intervals (depending on the 
>>>> choice of *x*, which in turn depends on the choice of *d*), it is also 
>>>> important to note that the interval is always of the size 2^248 (or 
>>>> actually 2 intervals each 2^247 elements), with x offsetting the intervals 
>>>> from *0* and *n div 2 -1* respectively. So while we can say that there 
>>>> is a 1/256 chance that a signature will be short for one private key 
>>>> (because the intervals cover 1/256 of the circle), we cannot say that the 
>>>> size of other signatures under other private keys also has the same 
>>>> independent chance of being short (it might have 0% chance if the intervals 
>>>> don't overlap). So for multiple private keys to generate short signatures 
>>>> over the same message, they need to correspond to the overlapping intervals.
>>>>
>>>> I think this breaks the whole construction, because you can partition 
>>>> the finite field into 256 non-overlapping intervals, corresponding to 256 
>>>> private keys, such that only one of these private keys will produce a short 
>>>> signature for any given message. You can increase the number of private 
>>>> keys & let the intervals overlap (and then use the intersection of any 2 
>>>> adjacent private key intervals by requiring 2 short signatures), but this 
>>>> will just make it much harder to produce a signature (as the z value will 
>>>> now have to land at the intersection of the intervals). In the end the work 
>>>> of the attacker is just 256 times harder than the work of the signer. The 
>>>> number 256 is stemming from the fact that we use 256 private keys, and is 
>>>> purely dependent on the number of private keys, so if we use e.g. 512 
>>>> private keys the attacker will need to grind 512 times more messages than 
>>>> the signer to find a valid one - so this is insecure for any reasonable 
>>>> number of private keys.
>>>>
>>>> Cheers,
>>>> Adam
>>>>
>>>> -- 
>>>> You received this message because you are subscribed to the Google 
>>>> Groups "Bitcoin Development Mailing List" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send 
>>>> an email to bitcoindev+...@googlegroups.com.
>>>> To view this discussion on the web visit 
>>>> https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917ef03ffn%40googlegroups.com 
>>>> <https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917ef03ffn%40googlegroups.com?utm_medium=email&utm_source=footer>
>>>> .
>>>>
>>>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/864868fb-164b-4d64-8c01-f496480c26e4n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 20031 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Garlo Nicon]

[-- Attachment #1.1: Type: text/plain, Size: 17765 bytes --]

> could you elaborate more on how exactly you envision tuning the mining 
difficulty using two private keys?

For example: this address requires grinding a single byte: 
https://mempool.space/testnet4/address/tb1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tls758l9d
And this one requires grinding two bytes: 
https://mempool.space/testnet4/address/tb1qk3endeq6x0xj4pjt4zwag8wf3a629rzqr8jxd7jnmlac902wa5ysqxm9wt

So, in the first case, if your difficulty is 1, then in the second case, it 
is 256. If you require both, then your real difficulty is equal to 257.

Which means, that by requiring N different signature sizes, and forming a 
multisig, you can pick a difficulty somewhere in between.

piątek, 25 października 2024 o 02:40:01 UTC+2 Vicky napisał(a):

> Great and fascinating discussion and detailed analysis, particularly Adam, 
> for the rigorous mathematical examination of the signature size 
> distribution.
>
> A few observations and questions:
>
> 1. The insight about signature size correlation when using the same z and 
> r is particularly important. While using different SIGHASH flags provides 
> some independence, the ~15 bits of security per 6-signature batch makes 
> this construction impractical under current Bitcoin script limits.
>
> 2. Regarding Adam's idea of PoW-locked outputs, could you elaborate more 
> on how exactly you envision tuning the mining difficulty using two private 
> keys? This interesting direction could be more practical than the full 
> Lamport signature scheme.
>
> 3. One additional consideration about the security model: Even if we could 
> achieve higher bits of security through more signatures, wouldn't the 
> resource requirements (script size, verification time) make this 
> impractical for most use cases compared to existing quantum-resistant 
> signature schemes that could be added through a soft fork?
>
> While perhaps not immediately practical, this exploration has helped 
> illuminate some interesting properties of ECDSA signature size 
> distributions and potential applications beyond Lamport signatures.
> Thanks
> Vicky
>
> On Wednesday, September 25, 2024 at 8:48:04 PM UTC-4 Adam Borcany wrote:
>
>> So, some more notes on this...
>>
>> I figured we can use OP_CODESEPARATOR to have more variety over the *z *value, 
>> with OP_CODESEPARATOR we can get pretty much unlimited variety (well only 
>> limited by the script limit), so by requiring that 6 short signatures (a 
>> signature batch) are published for every OP_CODESEPRATOR part we can force 
>> anyone to use all the possible sighashes for the signatures.
>>
>> As for the security of these 6 short signatures (size<59), it seems like 
>> we only get ~15bits of security for every batch of those, here is the 
>> intuition about it from the perspective of an attacker...
>> 1. Attacker starts with SIGHASH_NONE | ANYONECANPAY and grinds the 
>> transaction locktime, version & input sequence number, such that it 
>> produces a valid short signature under the same pubkey as original signer 
>> (this has 6/256 odds)
>> 2. Attacker then continues with SIGHASH_NONE by grinding the 2nd 
>> transaction input (e.g. the sequence number of it), such that it again 
>> produces a valid short signature under the same pubkey as the original 
>> signer (this has 5/256 odds)
>> 3. Attacker continues with SIGHASH_SINGLE | ANYONECANPAY & SIGHASH_SINGLE 
>> by grinding the transaction's 1st output - these have to go together, 
>> because there is no field that the attacker can manipulate such that it 
>> changes only one of those (this has (4*3)/65536 odds)
>> 4. Attacker finishes with SIGHASH_ALL | ANYONECANPAY & SIGHASH_ALL by 
>> grinding the transaction's 2nd output - these again have to go together, 
>> because there is no field that the attacker can manipulate such that it 
>> changes only one of those (this has  (2*1)/65536 odds)
>> The reason for the numerator here not being 1 is because the attacker can 
>> present the different sighash signatures in any order, so that he can 
>> choose from 6 different public keys in the first step, 5 in the second step 
>> and so on.
>>
>> So with this we can get reasonable security (90bits) by using 6 batches 
>> of these signatures (36 short signatures in total), which leads to the only 
>> problem of all of this - non-push opcode limit for p2wsh redeem scripts, 
>> which is just 201 non-push opcodes. Here is a simple script to just check 
>> if a single signature was valid:
>> # scriptSig 
>> <pubkey index> 
>> <short signature>
>>
>> # scriptPubkey
>> <pubkey n>
>> ...
>> <pubkey 1>
>> <pubkey 0>
>>
>> n+1 OP_ROLL OP_DUP OP_SIZE 59 OP_EQUALVERIFY #verify signature length
>> n+2 OP_ROLL OP_ROLL #get the public key
>> OP_CHECKSIGVERIFY #check signature matches
>>
>> It has 7 non-push opcodes, and doesn't include any lamport signature 
>> checking, purely just checks if a signature is short & signed under valid 
>> public key from the set of n public keys. So for 36 signatures you'd end up 
>> with at least 252 non-push opcodes, already above the opcode count limit.
>>
>> Also important to note is that the 90bit security only applies to 
>> pre-image resistance & second pre-image resistance. Due to the birthday 
>> paradox the collision resistance is just 45bits, which is good enough if 
>> you just want to use it for quantum resistant signatures, but for the use 
>> case I was thinking about (double-spend protection for zero-conf 
>> transactions) it is not enough, since malicious signer can find 2 colliding 
>> transactions, submit the first one, and then double-spend with the second 
>> one and not equivocate the lamport signature scheme. To achieve 90bit 
>> collision resistance we would need 72 short signatures & at least 504 
>> non-push opcodes.
>>
>> Another direction I was thinking about was using the public keys 
>> themselves as kind of a lamport signature scheme. The scriptPubkey would 
>> only contain *n* RIPEMD-160 commitments to the public keys & then the 
>> signer will reveal *m* of these public keys and provide a short ECDSA 
>> signature to them. The signer would essentially reveal *m *out of the *n 
>> *public keys* (pre-images) *and that would act as a signature, the order 
>> should not be important. The security of this pre-image reveal scheme is 
>> log2(*n* choose *m*) bits, but it gets very tricky when then talking 
>> about the actual short signature security, because now that order is not at 
>> all important, the attacker can choose any of the *m *revealed public 
>> keys to match the first signature (instead of 6), *m*-1 for the second 
>> (instead of 5), and so on... I tried to outline that in the spreadsheet and 
>> using m=256, n=30 we only get 51bits of security.
>>
>> Cheers,
>> Adam
>>
>>
>>
>> On Wed, 25 Sept 2024 at 00:19, Adam Borcany <adamb...@gmail.com> wrote:
>>
>>> > Do I understand correctly that you are saying that the size of each 
>>> signature from a set of signatures is not independently sampled as long as 
>>> all the signatures use the same z and r? 
>>>
>>> Yes, correct, every private key d adds a 2^248 wide interval (actually 
>>> two 2^247 wide intervals) of possible transaction hash values z, these 
>>> intervals can have no overlap (meaning only one of the signature will ever 
>>> be short), or can overlap and in that case the both signatures will be 
>>> short only if the transaction hash is at this overlapping region.
>>>
>>> > Could this scheme be saved by the fact that z need not be the same for 
>>> each signature? For instance by using SIGHASH flags to re-randomize z for 
>>> each signature. Wouldn't that restore independence?
>>>
>>> So there are 6 possible sighash flags, but SIGHASH_NONE | ANYONECANPAY 
>>> don't provide any security as it can be re-used by the attacker (as 
>>> attacker can just add its own output), also SIGHASH_NONE only helps with 
>>> security if the transaction's 2nd input is a keyspend (p2pkh, p2wpkh, p2tr) 
>>> and uses SIGHASH_ALL, otherwise attacker is able to just re-use that 
>>> signature as well, so at best we can have 5 different sighashes that 
>>> contribute to the security. This makes the scheme somewhat better - if 
>>> you use 256 private keys (such that they collectively span the full space 
>>> of the finite field), you can be sure that for the same z only 1 of them 
>>> will ever be short, so if you require 6 of them to be short the only way 
>>> for that to happen is that the 6 signatures use different SIGHASH and 
>>> therefore use different z. I think this improves the security somewhat, 
>>> signer will produce 6 short signatures with different sighashes (maybe he 
>>> needs to do a bit of grinding, but really little, like 1-5 iterations), the 
>>> attacker would then have to construct a transaction such that 5 different 
>>> signatures (under different sighash) would need to have the same position 
>>> as when the signer generated them (only 5 because attacker can re-use the SIGHASH_NONE 
>>> | ANYONECANPAY signature), the probability of that happening is 
>>> something around 1/2^40, so this means 2^40 more work for the attacker. 
>>> This still scales with the number of public keys, such that the probability 
>>> of an attacker finding the valid solution is (1/{number of keys})^5. For 
>>> reasonable security (e.g. 80-bit) we would need 2^16 public keys, which 
>>> doesn't actually sound super crazy, but is still too much for bitcoin.
>>>
>>> > How much harder is this? Couldn't the locking script secretly commit 
>>> to a large number of public keys where some subset is opened by the 
>>> spender. Thus, generate z to provide a signature with sufficient numbers of 
>>> small size signatures to prevent brute force? That is, commit to say 1024 
>>> public keys and then only reveal 64 public key commitments to give the 
>>> party who knows preimages of the public keys an advantage? 
>>>
>>> This would only help if you could create a vector commitment of the 
>>> public keys (e.g. merkle tree), such that you can then only reveal some of 
>>> them (based on my previous paragraph, you just need to reveal 6 public keys 
>>> & signatures), and for the commitment to not blow up the script size. 
>>> Committing to 1024 public keys by hash (or even use 1024 raw public keys) 
>>> is out of the question because the p2wsh script size is limited to 10kB.
>>>
>>> On a different note... I also started thinking about this in the context 
>>> of PoW locked outputs. It turns out you can fine-tune the mining difficulty 
>>> by just using 2 private keys, and making sure their possible transaction 
>>> hash *z* intervals overlap in such a way that it creates an interval of 
>>> fixed width, the PoW is then just about making sure the transaction hash 
>>> lands into this interval - so actually no modular arithmetic needed, it is 
>>> purely double-SHA256 hashing of the transaction and checking if the value 
>>> is within the interval.
>>>
>>> Cheers,
>>> Adam
>>>
>>> On Tue, 24 Sept 2024 at 23:08, Ethan Heilman <eth...@gmail.com> wrote:
>>>
>>>> Thanks for looking into this and writing this up. It is very exciting 
>>>> to see someone look into this deeper.
>>>>
>>>> Do I understand correctly that you are saying that the size of each 
>>>> signature from a set of signatures is not independently sampled as long as 
>>>> all the signatures use the same z and r?
>>>>
>>>> Could this scheme be saved by the fact that z need not be the same for 
>>>> each signature? For instance by using SIGHASH flags to re-randomize z for 
>>>> each signature. Wouldn't that restore independence?
>>>>
>>>> >  You can increase the number of private keys & let the intervals 
>>>> overlap (and then use the intersection of any 2 adjacent private key 
>>>> intervals by requiring 2 short signatures), but this will just make it much 
>>>> harder to produce a signature (as the z value will now have to land at the 
>>>> intersection of the intervals)
>>>>
>>>> How much harder is this? Couldn't the locking script secretly commit to 
>>>> a large number of public keys where some subset is opened by the spender. 
>>>> Thus, generate z to provide a signature with sufficient numbers of small 
>>>> size signatures to prevent brute force? That is, commit to say 1024 public 
>>>> keys and then only reveal 64 public key commitments to give the party who 
>>>> knows preimages of the public keys an advantage?
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Mon, Sep 23, 2024 at 5:37 PM Adam Borcany <adamb...@gmail.com> 
>>>> wrote:
>>>>
>>>>> Hello Ethan,
>>>>>
>>>>> > 3. We have modeled ECDSA s-values signatures being uniformly drawn 
>>>>> from 2^256. It seems unlikely to me that the Elliptic Curve math lines up 
>>>>> perfectly with a 256 bit space especially for a fixed r-value that has 
>>>>> special mathematical properties. 
>>>>>
>>>>> I've been looking into this more deeply, and it would seem like it's 
>>>>> not random at all, let me explain the intuition...
>>>>> If we take the signing equation for the *s* value:
>>>>> s = k^-1*(z+rd) mod n
>>>>> Considering that *k* is fixed and is set to 1/2 we get:
>>>>> s = 2*(z+rd) mod n
>>>>> We can let *x *= *rd* being a constant, since *r* is fixed (because 
>>>>> *k* is fixed) and *d* is fixed at contract creation time:
>>>>> s = 2*(z+x) mod n
>>>>> Now for the size of the signature to be 59 or less, the *s* value 
>>>>> needs to be smaller than 2^248, but since inequality isn't defined over 
>>>>> finite fields, we can create a set of all the integers 0..2^248 and then 
>>>>> see if the s value is contained in this set:
>>>>> s ∈ {i ∈ Z | i < 2^248} 
>>>>> 2*(z+x) ∈ {i ∈ Z | i < 2^248} 
>>>>> We now can divide the whole condition by 2:
>>>>> (z+x) ∈ {i/2 | i < 2^248}
>>>>> Which we can write as (keep in mind i/2 is division in the finite 
>>>>> field): 
>>>>> (z+x) ∈ {i ∈ Z | i < 2^247} ∪ {i ∈ Z | n div 2 + 1 ≤ i < n div 2 + 1 
>>>>> + 2^247}, where div is integer division
>>>>> By then subtracting *x* from both sides we finally get:
>>>>> z ∈ {i - x mod n | i < 2^247} ∪ {i - x mod n | n div 2 + 1 ≤ i < n 
>>>>> div 2 + 1 + 2^247}
>>>>> Which can be also be represented on the finite field circle & it helps 
>>>>> with the intuition:
>>>>> [image: ecdsa-opsize-lamport.png]
>>>>> Here *x *is set to 0 for simplicity.
>>>>>
>>>>> What this shows is that the signature size being 59 or less depends on 
>>>>> the transaction hash *z* (technically *z* is just left-most bits of 
>>>>> the transaction hash) being in the specified intervals (depending on the 
>>>>> choice of *x*, which in turn depends on the choice of *d*), it is 
>>>>> also important to note that the interval is always of the size 2^248 (or 
>>>>> actually 2 intervals each 2^247 elements), with x offsetting the intervals 
>>>>> from *0* and *n div 2 -1* respectively. So while we can say that 
>>>>> there is a 1/256 chance that a signature will be short for one private key 
>>>>> (because the intervals cover 1/256 of the circle), we cannot say that the 
>>>>> size of other signatures under other private keys also has the same 
>>>>> independent chance of being short (it might have 0% chance if the intervals 
>>>>> don't overlap). So for multiple private keys to generate short signatures 
>>>>> over the same message, they need to correspond to the overlapping intervals.
>>>>>
>>>>> I think this breaks the whole construction, because you can partition 
>>>>> the finite field into 256 non-overlapping intervals, corresponding to 256 
>>>>> private keys, such that only one of these private keys will produce a short 
>>>>> signature for any given message. You can increase the number of private 
>>>>> keys & let the intervals overlap (and then use the intersection of any 2 
>>>>> adjacent private key intervals by requiring 2 short signatures), but this 
>>>>> will just make it much harder to produce a signature (as the z value will 
>>>>> now have to land at the intersection of the intervals). In the end the work 
>>>>> of the attacker is just 256 times harder than the work of the signer. The 
>>>>> number 256 is stemming from the fact that we use 256 private keys, and is 
>>>>> purely dependent on the number of private keys, so if we use e.g. 512 
>>>>> private keys the attacker will need to grind 512 times more messages than 
>>>>> the signer to find a valid one - so this is insecure for any reasonable 
>>>>> number of private keys.
>>>>>
>>>>> Cheers,
>>>>> Adam
>>>>>
>>>>> -- 
>>>>> You received this message because you are subscribed to the Google 
>>>>> Groups "Bitcoin Development Mailing List" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send 
>>>>> an email to bitcoindev+...@googlegroups.com.
>>>>> To view this discussion on the web visit 
>>>>> https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917ef03ffn%40googlegroups.com 
>>>>> <https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917ef03ffn%40googlegroups.com?utm_medium=email&utm_source=footer>
>>>>> .
>>>>>
>>>>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/e7c5645a-1ac2-458b-a85d-0aecc768392en%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 20939 bytes --]

Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

[Xiaohui Liu]

[-- Attachment #1.1: Type: text/plain, Size: 2155 bytes --]

Hi,

How does covenant work without OP_CAT here, assuming no size limit? Don't 
you still need OP_CAT to parse/introspect fields (e.g., input/output) of 
the spending transaction?

Regards,
sCrypt

On Tuesday, April 30, 2024 at 7:22:54 AM UTC-7 Andrew Poelstra wrote:

> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
> > > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
> > computations, it would provide the attacker some advantage.
> > 
> > If we are assuming discrete log is still hard, why do we need Lamport
> > signatures at all? In a post-quantum world, finding k such that r is 21
> > bytes or less is efficient for the attacker.
> >
>
> Aside from Ethan's point that a variant of this technique is still
> secure in the case that discrete log is totally broken (or even
> partially broken...all we need is that _somebody_ is able to find the
> discrete log of the x=1 point and for them to publish this).
>
> Another reason this is useful is that if you have a Lamport signature on
> the stack which is composed of SIZE values, all of which are small
> enough to be manipulated with the numeric script opcodes, then you can
> do covenants in Script.
>
> (Sadly(?), I think none of this works in the context of the 201-opcode
> limit...and absent BitVM challenge-response tricks it's unlikely you can
> do much in the context of the 4MWu block size limit..), but IMO it's a
> pretty big deal that size limits are now the only reason that Bitcoin
> doesn't have covenants.)
>
> -- 
> Andrew Poelstra
> Director, Blockstream Research
> Email: apoelstra at wpsoftware.net
> Web: https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
> -Justin Lewis-Webster
>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/129a9605-7a91-42a7-a9ef-07de6662ca7en%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 3290 bytes --]