From: Vicky <vicky.fuyu@gmail•com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)
Date: Thu, 24 Oct 2024 17:20:54 -0700 (PDT) [thread overview]
Message-ID: <864868fb-164b-4d64-8c01-f496480c26e4n@googlegroups.com> (raw)
In-Reply-To: <CAOY=fz=bcun5U75PUJJGuuB7p5dHtghrYf9gfOvj4zpiWdM_Tg@mail.gmail.com>
[-- 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 --]
next prev parent reply other threads:[~2024-10-25 0:40 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-29 0:30 Ethan Heilman
2024-04-30 12:32 ` Matthew Zipkin
2024-04-30 13:25 ` Ethan Heilman
2024-04-30 14:21 ` Andrew Poelstra
2024-04-30 20:43 ` Ethan Heilman
2024-05-01 3:46 ` Antoine Riard
2024-05-01 20:02 ` Ethan Heilman
2024-05-06 7:39 ` David A. Harding
2024-05-06 16:48 ` Andrew Poelstra
2024-05-06 18:56 ` David A. Harding
2024-05-06 19:06 ` Andrew Poelstra
2024-05-07 0:55 ` Antoine Riard
2024-05-07 16:05 ` Ethan Heilman
2024-05-07 4:11 ` David A. Harding
2024-05-07 14:34 ` Andrew Poelstra
2024-05-09 0:31 ` Ben Carman
2024-05-09 12:46 ` Andrew Poelstra
2024-05-11 2:53 ` Antoine Riard
[not found] ` <91ba7058-776d-4ff0-a179-bb2917ef03ffn@googlegroups.com>
[not found] ` <CAEM=y+UKgDRtaV5uveiX_Hn1dTDEF-DSHw0SjRu+j0s3fmp78Q@mail.gmail.com>
[not found] ` <CAOY=fzk+nKBw4kpLJLe=EngNfD5iEsWVsa5sMyPaXKp9cDAqdQ@mail.gmail.com>
[not found] ` <CAOY=fz=bcun5U75PUJJGuuB7p5dHtghrYf9gfOvj4zpiWdM_Tg@mail.gmail.com>
2024-10-25 0:20 ` Vicky [this message]
2024-10-25 9:58 ` Garlo Nicon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=864868fb-164b-4d64-8c01-f496480c26e4n@googlegroups.com \
--to=vicky.fuyu@gmail$(echo .)com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox