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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: <864868fb-164b-4d64-8c01-f496480c26e4n@googlegroups.com> In-Reply-To: References: <9e48edb6-1909-4eee-a0c7-48123f42a198n@googlegroups.com> <91ba7058-776d-4ff0-a179-bb2917ef03ffn@googlegroups.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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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 > =20 > > > # scriptPubkey > > ... > > > > 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 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 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 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 >>>> >>>> . >>>> >>> --=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.

A few observations and questions:

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.

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= .

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?

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.
Thanks
Vicky

On= Wednesday, September 25, 2024 at 8:48:04=E2=80=AFPM UTC-4 Adam Borcany wro= te:
So, some more notes on this...

I fig= ured we can use OP_CODESEPARATOR to have more variety over the z 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.

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 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)
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)
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)
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)
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.

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:
# 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 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.

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>

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 n RIPEMD-160 commitments to the public key= s & then the signer will reveal m of these public keys and provi= de a short ECDSA signature to them. The signer would essentially reveal = m out of the n public keys (pre-images) 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(n choose m) 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 m revealed public keys to match the first signature (instead o= f 6), m-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.

Cheers,
Adam



On Wed, 25 Sept 20= 24 at 00:19, Adam Borcany <ad= amb...@gmail.com> wrote:
>=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?

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.

>=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?

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 - 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 SIGHASH_NONE | ANYONECANPAY signature), 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.

>=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?

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.

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 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 arit= hmetic needed, it is purely double-SHA256 hashing of the transaction and ch= ecking if the value is within the interval.

Cheers= ,
Adam

On Tue, 24 Sept 2024 at 23:08, Ethan Heilman <= eth...@gmail.com> wrote:<= br>
Thanks=C2=A0for looking into this and writing this up. It is very exciting= to see someone look into this deeper.

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?

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?

>= =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)

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?







On Mon, Sep 23, 2024 at 5:37=E2= =80=AFPM Adam Borcany <adamb.= ..@gmail.com> wrote:
Hello Ethan,

> 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.

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 =3D k^-1*(z+rd) mod n
Considering that k is fix= ed and is set to 1/2 we get:
s =3D 2*(z+rd) mod n
W= e can let x =3D rd being a constant, since r is fixed = (because k is fixed) and d is fixed at contract creation time= :
s =3D 2*(z+x) mod n
Now for the size of the signa= ture to be 59 or less, the s 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:
s =E2=88=88 {i =E2=88=88 Z | i < 2^248}
2*(z+x) =E2=88=88 {i =E2=88=88 Z | i < 2^248}
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 field):
(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<= /span> i < n = div 2 + 1 + 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<= span> |=C2=A0i &= lt; 2^247} =E2=88=AA {i - x mod n | n div 2 + 1 =E2=89=A4<= /span> i < n div 2 + 1 + 2^247}
Which can be also be represented on the finite = field circle & it helps with the intuition:
3D"ecdsa-opsize-lamport.png"
<= div>Here x is set to 0 for simplicity.
=

What this shows is tha= t the signature size being 59 or less depends on the transaction hash z<= /i> (technically z is just left-most bits of the transaction hash) b= eing 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 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 0 and n div= 2 -1 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.

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.

Cheers,
Ada= m

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+...@googlegro= ups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-= bb2917ef03ffn%40googlegroups.com.

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