path: root/4d/8783119144203a2f4058968b89371c455da25e

Delivery-date: Thu, 24 Oct 2024 17:40:09 -0700
Received: from mail-yb1-f190.google.com ([209.85.219.190])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBCS6PG46ZMJBBX6R5O4AMGQEMO5FGOA@googlegroups.com>)
	id 1t48N5-0004sS-AM
	for bitcoindev@gnusha.org; Thu, 24 Oct 2024 17:40:09 -0700
Received: by mail-yb1-f190.google.com with SMTP id 3f1490d57ef6-e2605ce4276sf2880462276.3
        for <bitcoindev@gnusha.org>; Thu, 24 Oct 2024 17:40:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1729816801; x=1730421601; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:sender:from
         :to:cc:subject:date:message-id:reply-to;
        bh=X7H37YMUcYaqaflMZhvN5EIxJuUhoZQrd7tHIXjofRc=;
        b=vsFGrrB5t4ywBeqaNd73O9xyRzJ5zck3TiDHGO2tQaoVxYHeRZlQXQoK+mdfPZyBij
         EffPNGEUZC3TD3tBqeoI4xg2fw3aK99QAMAtzfI69O8IM5SR+CWJJrIX5IjJN9BXON1v
         EGOj9+rh7456vfTEX5ujil8PE9cVSqi0GnbrfhcFw8KGMIaOv2HV1BZIXT+Rp7lHsoll
         z6DIFe1WOpFps5S+P3f9Myetb/jUHVhX6Xt2hnH21k4qo9bhbl23dffGGbcJEWckpTem
         T9r9YkZvf1pfOvpBffuApGfd8F0Yov6i+w9C1ggeqJZOQmVBj3Yyt0chrP0adwY3Ya0k
         V/Cg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1729816801; x=1730421601; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:from:to:cc
         :subject:date:message-id:reply-to;
        bh=X7H37YMUcYaqaflMZhvN5EIxJuUhoZQrd7tHIXjofRc=;
        b=BkvinDqT4Ov2TpvgVwPD6/tj5GPlV2DYKL2CpAqvsGG+HJFn1/ecNM7t8mzoMHcqFM
         PUnewPflsOdTgANQM7Cyfd1eWEFTqClsFZLXtJ4XfBdVV8cAmfkjMyQARWjXxC1rRkcE
         D5BrSHEz61IulN8dJ57uCMd4XfMSyy/cCaECggyoWBqAKdN9f/Fb3sTK7EGoe2A9INjY
         i/SLtVIaJiuSycaTbhkrAaFsWiqfzLec9/fdxIdPbKFcoTNFSjjrYDGodXkfRx/VdjsI
         jus+wLdJ44d/C0FyRYdlWHW0pt9LyksxJEqc8GEJJcx3PiD48nV9mxO1UTbn/MbUpn4D
         cKug==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1729816801; x=1730421601;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=X7H37YMUcYaqaflMZhvN5EIxJuUhoZQrd7tHIXjofRc=;
        b=AP5X0i9V6Cc40CWpa/xlfL6G0pwu9301zMU+GDMb60rv5mfcxgoCLnQIVyVVANC1kC
         uFHO9grd30+BRFn3RHhJVHdR2ihsgGu6+XqogTH23ekceZ1eweJ+Z7J5JkJo6JLucsQk
         E6gOH5xcKHSOO1JTKvB//ciuXrU8ML2VuUapgGvxySqS9vzEZqFPUTk8Gdn9QBz4deXy
         ItJZXKb4Y3KrWG6QG8Vf+1EMdSAPYsk45tzH1+8Lu+MspD7cT7ekV2E1XTGJfqFdhujk
         MvV1YWc5n8nMSZSqoZs7wKSLz3RQaeOvnxuNA+U/yKKk9+lduyKW8eW/Ag4srZ+NpHs5
         nqNA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCX5+riEijiyD3Y47fkIE0xKtmveBx6UcNnKS9sGLYUyPOLW7e/PARhSiStvr7/UTRYTOLyvJAD+wCs0@gnusha.org
X-Gm-Message-State: AOJu0YxgzXHS4Eb5II2VLA3ozyxVk05rhEN7lwOzszgNJxJYJwwm6rbA
	3AA5DlRWnoxzs6SMb7N8ZPhK7TYvw+/pdo9uAaA2YcMN/abKCWMX
X-Google-Smtp-Source: AGHT+IGmgEs4YLRlcmTvGSN4O+Iw4ksAXHqOQ1oIe3aQ/haTEik3BdIRpcV6uUOf6LmO1Yx/o7w6/w==
X-Received: by 2002:a05:6902:c08:b0:e28:e9ea:9784 with SMTP id 3f1490d57ef6-e2e3a6d39e7mr9288202276.49.1729816801104;
        Thu, 24 Oct 2024 17:40:01 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6902:1244:b0:e28:ff06:8c0b with SMTP id
 3f1490d57ef6-e2e4a5e613bls724317276.0.-pod-prod-03-us; Thu, 24 Oct 2024
 17:39:59 -0700 (PDT)
X-Received: by 2002:a05:690c:f09:b0:6e2:1467:17b4 with SMTP id 00721157ae682-6e7f0dbbf21mr91097467b3.9.1729816799047;
        Thu, 24 Oct 2024 17:39:59 -0700 (PDT)
Received: by 2002:a05:690c:640c:b0:6dd:f386:13dc with SMTP id 00721157ae682-6e7eefee159ms7b3;
        Thu, 24 Oct 2024 17:20:56 -0700 (PDT)
X-Received: by 2002:a05:690c:4087:b0:6e3:1f02:407b with SMTP id 00721157ae682-6e85816739bmr31522357b3.11.1729815655236;
        Thu, 24 Oct 2024 17:20:55 -0700 (PDT)
Date: Thu, 24 Oct 2024 17:20:54 -0700 (PDT)
From: Vicky <vicky.fuyu@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <864868fb-164b-4d64-8c01-f496480c26e4n@googlegroups.com>
In-Reply-To: <CAOY=fz=bcun5U75PUJJGuuB7p5dHtghrYf9gfOvj4zpiWdM_Tg@mail.gmail.com>
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
 <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
 <ZjD-dMMGxoGNgzIg@camus>
 <b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n@googlegroups.com>
 <ZjzFtus_aBchwKz2@camus>
 <9e48edb6-1909-4eee-a0c7-48123f42a198n@googlegroups.com>
 <91ba7058-776d-4ff0-a179-bb2917ef03ffn@googlegroups.com>
 <CAEM=y+UKgDRtaV5uveiX_Hn1dTDEF-DSHw0SjRu+j0s3fmp78Q@mail.gmail.com>
 <CAOY=fzk+nKBw4kpLJLe=EngNfD5iEsWVsa5sMyPaXKp9cDAqdQ@mail.gmail.com>
 <CAOY=fz=bcun5U75PUJJGuuB7p5dHtghrYf9gfOvj4zpiWdM_Tg@mail.gmail.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
 Signatures (no changes needed)
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_27804_138313945.1729815654787"
X-Original-Sender: Vicky.fuyu@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: 2.0 (++)

------=_Part_27804_138313945.1729815654787
Content-Type: multipart/alternative; 
	boundary="----=_Part_27805_838118986.1729815654787"

------=_Part_27805_838118986.1729815654787
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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

A few observations and questions:

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

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

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

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

On Wednesday, September 25, 2024 at 8:48:04=E2=80=AFPM UTC-4 Adam Borcany w=
rote:

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

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
864868fb-164b-4d64-8c01-f496480c26e4n%40googlegroups.com.

------=_Part_27805_838118986.1729815654787
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Great and fascinating discussion and detailed analysis, particularly Adam, =
for the rigorous mathematical examination of the signature size distributio=
n.<br /><br />A few observations and questions:<br /><br />1. The insight a=
bout 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 imp=
ractical under current Bitcoin script limits.<br /><br />2. Regarding Adam'=
s idea of PoW-locked outputs, could you elaborate more on how exactly you e=
nvision tuning the mining difficulty using two private keys? This interesti=
ng direction could be more practical than the full Lamport signature scheme=
.<br /><br />3. One additional consideration about the security model: Even=
 if we could achieve higher bits of security through more signatures, would=
n't the resource requirements (script size, verification time) make this im=
practical for most use cases compared to existing quantum-resistant signatu=
re schemes that could be added through a soft fork?<br /><br />While perhap=
s not immediately practical, this exploration has helped illuminate some in=
teresting properties of ECDSA signature size distributions and potential ap=
plications beyond Lamport signatures.<div>Thanks</div><div>Vicky<br /><br /=
></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">On=
 Wednesday, September 25, 2024 at 8:48:04=E2=80=AFPM UTC-4 Adam Borcany wro=
te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e=
x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir=
=3D"ltr"><div>So, some more notes on this...</div><div><br></div><div>I fig=
ured we can use OP_CODESEPARATOR to have more variety over the <i>z </i>val=
ue, with OP_CODESEPARATOR we can get pretty much unlimited variety (well on=
ly 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.<br></div><div=
><br></div><div>As for the security of these 6 short signatures (size&lt;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...</div>=
<div>
1. Attacker starts with SIGHASH_NONE | ANYONECANPAY and grinds the transact=
ion locktime, version &amp; input sequence number, such that it produces a =
valid short signature under the same pubkey as original signer (this has 6/=
256 odds)</div><div>2. Attacker then continues with SIGHASH_NONE by grindin=
g 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 origina=
l signer (this has 5/256 odds)</div><div>3. Attacker continues with SIGHASH=
_SINGLE=20
| ANYONECANPAY &amp; SIGHASH_SINGLE by grinding the transaction&#39;s 1st o=
utput - these have to go together, because there is no field that the attac=
ker can manipulate such that it changes only one of those (this has (4*3)/6=
5536 odds)</div><div>4. Attacker finishes with SIGHASH_ALL
| ANYONECANPAY &amp; SIGHASH_ALL by grinding the transaction&#39;s 2nd outp=
ut - these again have to go together, because there is no field that the at=
tacker can manipulate such that it changes only one of those (this has=C2=
=A0
(2*1)/65536 odds)</div><div>The reason for the numerator here not being 1 i=
s 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.</div><div><br></div><div>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 no=
n-push opcodes. Here is a simple script to just check if a single signature=
 was valid:</div><div># scriptSig
<br>&lt;pubkey index&gt;

<br>&lt;short signature&gt;<br><br># scriptPubkey<br>&lt;pubkey n&gt;<br>..=
.<br>&lt;pubkey 1&gt;<br>&lt;pubkey 0&gt;<br><br>n+1 OP_ROLL OP_DUP OP_SIZE=
 59 OP_EQUALVERIFY #verify signature length<br>n+2 OP_ROLL OP_ROLL #get the=
 public key<br>OP_CHECKSIGVERIFY #check signature matches</div><div><br></d=
iv><div>It has 7 non-push opcodes, and doesn&#39;t include any lamport sign=
ature checking, purely just checks if a signature is short &amp; signed und=
er valid public key from the set of n public keys. So for 36 signatures you=
&#39;d end up with at least 252 non-push opcodes, already above the opcode =
count limit.</div><div><br></div><div>Also important to note is that the 90=
bit security only applies to=20
pre-image resistance &amp; second pre-image resistance. Due to the birthday=
 paradox the collision resistance is just 45bits, which is good enough if y=
ou just want to use it for quantum resistant signatures, but for the use ca=
se I was thinking about (double-spend protection for zero-conf transactions=
) it is not enough, since malicious signer can find 2 colliding transaction=
s, submit the first one, and then double-spend with the second one and not =
equivocate the lamport signature scheme. To achieve 90bit collision resista=
nce we would need 72 short signatures &amp; at least 504 non-push opcodes.<=
/div><div><br></div><div>Another direction I was thinking about was using t=
he public keys themselves as kind of a lamport signature scheme. The script=
Pubkey would only contain <i>n</i> RIPEMD-160 commitments to the public key=
s &amp; then the signer will reveal <i>m</i> of these public keys and provi=
de a short ECDSA signature to them. The signer would essentially reveal <i>=
m </i>out of the <i>n </i>public keys<i> (pre-images) </i>and that would ac=
t as a signature, the order should not be important. The security of this p=
re-image reveal scheme is log2(<i>n</i> choose <i>m</i>) bits, but it gets =
very tricky when then talking about the actual short signature security, be=
cause now that order is not at all important, the attacker can choose any o=
f the <i>m </i>revealed public keys to match the first signature (instead o=
f 6), <i>m</i>-1 for the second (instead of 5), and so on... I tried to out=
line that in the spreadsheet and using m=3D256, n=3D30 we only get 51bits o=
f security.<br></div><div><br></div><div>Cheers,</div><div>Adam<br></div><d=
iv><br></div></div><div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div cla=
ss=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, 25 Sept 20=
24 at 00:19, Adam Borcany &lt;<a href data-email-masked rel=3D"nofollow">ad=
amb...@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" =
style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pa=
dding-left:1ex"><div dir=3D"ltr"><div>&gt;=20
Do I understand correctly that you are saying that the size of each=20
signature from a set of signatures is not independently sampled as long=20
as all the signatures use the same z and r? <br></div><div><br></div><div>Y=
es, correct, every private key d adds a 2^248 wide interval (actually two 2=
^247 wide intervals) of possible transaction hash values z, these=20
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.</div><div><br></div><di=
v>&gt;=20
Could this scheme be saved by the fact that z need not be the same for=20
each signature? For instance by using SIGHASH flags to re-randomize z=20
for each signature. Wouldn&#39;t that restore independence?<span><br></span=
></div><div><span><br></span></div><div><span>So there are 6 possible sigha=
sh flags, but SIGHASH_NONE | ANYONECANPAY don&#39;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&#39;s 2nd =
input is a keyspend (p2pkh, p2wpkh, p2tr) and uses SIGHASH_ALL, otherwise a=
ttacker is able to just re-use that signature as well, so at best we can ha=
ve 5 different sighashes that contribute to the security. This makes the sc=
heme somewhat better - </span>if you use 256 private keys (such that they c=
ollectively 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 th=
em 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 s=
ighashes (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 suc=
h that 5 different signatures (under different sighash) would need to have =
the same position as when the signer generated them (only 5 because attacke=
r can re-use the=20
<span>SIGHASH_NONE | ANYONECANPAY signature</span>), the probability of tha=
t happening is something around 1/2^40, so this means 2^40 more work for th=
e 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 key=
s})^5. For reasonable security (e.g. 80-bit) we would need 2^16 public keys=
, which doesn&#39;t actually sound super crazy, but is still too much for b=
itcoin.<br></div><div><br></div><div>&gt;=20
How much harder is this?=C2=A0Couldn&#39;t the locking script secretly comm=
it to a
 large number of public keys where some subset is opened by the spender.
 Thus, generate=C2=A0z to provide a signature with sufficient=C2=A0numbers =
of=20
small size signatures to prevent brute force? That is, commit to say=20
1024 public keys and then only reveal 64 public key=C2=A0commitments to giv=
e=20
the party who knows preimages of the public keys an advantage? <br></div><d=
iv><br></div><div>This would only help if you could create a vector commitm=
ent of the public keys (e.g. merkle tree), such that you can then only reve=
al some of them (based on my previous paragraph, you just need to reveal 6 =
public keys &amp; signatures), and for the commitment to not blow up the sc=
ript 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.</=
div><div><br></div><div>On a different note... I also started thinking abou=
t 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 <i>z</i> 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 arit=
hmetic needed, it is purely double-SHA256 hashing of the transaction and ch=
ecking if the value is within the interval.</div><div><br></div><div>Cheers=
,</div><div>Adam<br></div></div><br><div class=3D"gmail_quote"><div dir=3D"=
ltr" class=3D"gmail_attr">On Tue, 24 Sept 2024 at 23:08, Ethan Heilman &lt;=
<a href data-email-masked rel=3D"nofollow">eth...@gmail.com</a>&gt; wrote:<=
br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"=
>Thanks=C2=A0for looking into this and writing this up. It is very exciting=
 to see someone look into this deeper.<br><br>Do I understand correctly tha=
t you are saying that the size of each signature from a set of signatures i=
s not independently sampled as long as all the signatures use the same z an=
d r?<br><br>Could this scheme be saved by the fact that z need not be the s=
ame for each signature? For instance by using SIGHASH flags to re-randomize=
 z for each signature. Wouldn&#39;t that restore independence?<br><br>&gt;=
=C2=A0

You can increase the number of private keys &amp; 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 pr=
oduce a signature (as the z value will now have to land at the intersection=
 of the intervals)<br><br>How much harder is this?=C2=A0Couldn&#39;t the lo=
cking script secretly commit to a large number of public keys where some su=
bset is opened by the spender. Thus, generate=C2=A0z to provide a signature=
 with sufficient=C2=A0numbers of small size signatures to prevent brute for=
ce? That is, commit to say 1024 public keys and then only reveal 64 public =
key=C2=A0commitments to give the party who knows preimages of the public ke=
ys an advantage?<br><br><br><br><br><br><br></div><br><div class=3D"gmail_q=
uote"><div dir=3D"ltr" class=3D"gmail_attr">On Mon, Sep 23, 2024 at 5:37=E2=
=80=AFPM Adam Borcany &lt;<a href data-email-masked rel=3D"nofollow">adamb.=
..@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin=
g-left:1ex"><div>Hello Ethan,<br>
</div><div><br></div><div>&gt; 3. We have modeled ECDSA s-values signatures=
 being uniformly drawn from=20
2^256. It seems unlikely to me that the Elliptic Curve math lines up=20
perfectly with a 256 bit space especially for a fixed r-value that has=20
special mathematical properties.

</div><div><br></div><div>I&#39;ve been looking into this more deeply, and =
it would seem like it&#39;s not random at all, let me explain the intuition=
...</div><div>If we take the signing equation for the <i>s</i> value:</div>=
<div>s =3D k^-1*(z+rd) mod n<br></div><div>Considering that <i>k</i> is fix=
ed and is set to 1/2 we get:</div><div>s =3D 2*(z+rd) mod n<br></div><div>W=
e can let <i>x </i>=3D <i>rd</i> being a constant, since <i>r</i> is fixed =
(because <i>k</i> is fixed) and <i>d</i> is fixed at contract creation time=
:</div><div>s =3D 2*(z+x) mod n<br></div><div>Now for the size of the signa=
ture to be 59 or less, the <i>s</i> value needs to be smaller than 2^248, b=
ut since inequality isn&#39;t defined over finite fields, we can create a s=
et of all the integers 0..2^248 and then see if the s value is contained in=
 this set:</div><div>s<span><span> =E2=88=88</span></span> <span><span>{</s=
pan></span><span><span>i</span></span>
<span><span>=E2=88=88</span></span> Z

<span><span> | i</span></span><span><span> &lt; 2^248}</span></span>

</div><div>
2*(z+x) <span><span>=E2=88=88</span></span> <span><span>{</span></span><spa=
n><span>i</span></span>
<span><span>=E2=88=88</span></span>

Z<span><span> | i &lt; 2^248}</span></span>

</div><div>We now can divide the whole condition by 2:</div><div>(z+x) <spa=
n><span>=E2=88=88</span></span> <span><span>{i/2 </span></span>|<span><span=
> i &lt; 2^248}</span></span></div><div><span><span>Which we can write as (=
keep in mind i/2 is division in the finite field):</span></span>



</div><div>
(z+x) <span><span>=E2=88=88</span></span> <span><span>{i</span></span>
<span><span>=E2=88=88</span></span>

Z<span><span></span></span>

<span><span> | i</span></span><span><span> &lt; 2^247}</span></span>
<span>=E2=88=AA</span>
<span><span>{i</span></span>
<span><span>=E2=88=88</span></span>

Z<span><span></span></span>

<span><span> | n div 2 + 1 </span></span><span><span><span><span>=E2=89=A4<=
/span></span></span></span> <span><span>i</span></span><span><span> &lt; n =
div 2 + 1 + 2^247}, where div is integer division<br></span></span></div><d=
iv><span><span>By then subtracting <i>x</i> from both sides we finally get:=
<br>z </span></span>
<span><span>=E2=88=88</span></span> <span><span>{i - x mod n</span></span><=
span><span></span></span>

<span><span> |=C2=A0</span></span><span><span>i</span></span><span><span> &=
lt; 2^247</span></span><span><span>}</span></span>
<span>=E2=88=AA</span>
<span><span>{i</span></span> - x mod n<span><span></span></span>

<span><span> | n div 2 + 1 </span></span><span><span><span><span>=E2=89=A4<=
/span></span></span></span>

<span><span> i</span></span><span><span> &lt; n div 2 + 1 + 2^247}</span></=
span></div><div><span><span>Which can be also be represented on the finite =
field circle &amp; it helps with the intuition:</span></span></div><div><sp=
an><span><img alt=3D"ecdsa-opsize-lamport.png" width=3D"561px" height=3D"50=
1px" src=3D"https://groups.google.com/group/bitcoindev/attach/1e951c985dad/=
ecdsa-opsize-lamport.png?part=3D0.1&amp;view=3D1"><br></span></span></div><=
div><span><span>Here <i>x </i>is set to 0 for simplicity.<br></span></span>=
</div><div><span><span><br></span></span> </div><div>What this shows is tha=
t the signature size being 59 or less depends on the transaction hash <i>z<=
/i> (technically <i>z</i> is just left-most bits of the transaction hash) b=
eing in the specified intervals (depending on the choice of <i>x</i>, which=
 in turn depends on the choice of <i>d</i>), it is also important to note t=
hat the interval is always of the size 2^248 (or actually 2 intervals each =
2^247 elements), with x offsetting the intervals from <i>0</i> and <i>n div=
 2 -1</i> respectively. So while we can say that there is a 1/256 chance th=
at a signature will be short for one private key=20
(because the intervals cover 1/256 of the circle), we cannot say that the s=
ize of other signatures under other private keys also has the same independ=
ent chance of being short (it might have 0% chance if the intervals don&#39=
;t overlap). So for multiple private keys to generate short signatures over=
 the same message, they need to correspond to the overlapping intervals.</d=
iv><div><br></div><div>I think this breaks the whole construction, because =
you can partition the finite field into 256 non-overlapping intervals, corr=
esponding to 256 private keys, such that only one of these private keys wil=
l produce a short signature for any given message. You can increase the num=
ber of private keys &amp; let the intervals overlap (and then use the inter=
section of any 2 adjacent private key intervals by requiring 2 short signat=
ures), but this will just make it much harder to produce a signature (as th=
e z value will now have to land at the intersection of the intervals). In t=
he end the work of the attacker is just 256 times harder than the work of t=
he 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 messag=
es than the signer to find a valid one - so this is insecure for any reason=
able number of private keys.</div><div><br></div><div>Cheers,</div><div>Ada=
m<br></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href data-email-masked rel=3D"nofollow">bitcoindev+...@googlegro=
ups.com</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917ef03ffn%40googlegroups.=
com?utm_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank" rel=3D"no=
follow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=3D=
https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917=
ef03ffn%2540googlegroups.com?utm_medium%3Demail%26utm_source%3Dfooter&amp;s=
ource=3Dgmail&amp;ust=3D1729901859852000&amp;usg=3DAOvVaw23-EgjHD54ijIGwaqH=
uv6m">https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-=
bb2917ef03ffn%40googlegroups.com</a>.<br>
</blockquote></div>
</blockquote></div>
</blockquote></div></div>
</blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/864868fb-164b-4d64-8c01-f496480c26e4n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/864868fb-164b-4d64-8c01-f496480c26e4n%40googlegroups.com</a>.<br />

------=_Part_27805_838118986.1729815654787--

------=_Part_27804_138313945.1729815654787--