From mboxrd@z Thu Jan 1 00:00:00 1970 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<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 & 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 & SIGHASH_SINGLE by grinding the transaction'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 & SIGHASH_ALL by grinding the transaction'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><pubkey index> <br><short signature><br><br># scriptPubkey<br><pubkey n><br>..= .<br><pubkey 1><br><pubkey 0><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't include any lamport sign= ature checking, purely just checks if a signature is short & signed und= er 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.</div><div><br></div><div>Also important to note is that the 90= bit security only applies to=20 pre-image resistance & 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 & 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 & 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 <<a href data-email-masked rel=3D"nofollow">ad= amb...@gmail.com</a>> 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>>=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>>=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'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'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 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't actually sound super crazy, but is still too much for b= itcoin.<br></div><div><br></div><div>>=20 How much harder is this?=C2=A0Couldn'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 & 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 <= <a href data-email-masked rel=3D"nofollow">eth...@gmail.com</a>> 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't that restore independence?<br><br>>= =C2=A0 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 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'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 <<a href data-email-masked rel=3D"nofollow">adamb.= ..@gmail.com</a>> 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>> 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've been looking into this more deeply, and = it would seem like it'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'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> < 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 < 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 < 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> < 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> < 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> < n div 2 + 1 + 2^247}</span></= span></div><div><span><span>Which can be also be represented on the finite = field circle & 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&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'= ;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 & 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" 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&utm_source=3Dfooter" target=3D"_blank" rel=3D"no= follow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&q=3D= https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917= ef03ffn%2540googlegroups.com?utm_medium%3Demail%26utm_source%3Dfooter&s= ource=3Dgmail&ust=3D1729901859852000&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" 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--