Delivery-date: Sat, 26 Oct 2024 02:06:17 -0700 Received: from mail-yw1-f187.google.com ([209.85.128.187]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1t4ckR-0005ca-FZ for bitcoindev@gnusha.org; Sat, 26 Oct 2024 02:06:17 -0700 Received: by mail-yw1-f187.google.com with SMTP id 00721157ae682-6e35bdb6a31sf56053157b3.1 for ; Sat, 26 Oct 2024 02:06:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1729933569; x=1730538369; 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=uSxsduxeRk0DErvCMMJe2weHoS7og5qwINtzWqXLgv0=; b=ABo9K5tKtrWOOO89ykYAkRl8l3nfHZHW0V3a99CP6DRSHlj5FZPKc0eHgSIzGzEizl pZsPrxBahpTAVHevx48RFbJo57hOUzuoBe28gqrUd52xfl98OjZJzISj+AaN9oyNe6/y zBbqN/MF0H3HjQU3tAxgCgQwqpW1X+rUzt4Xg6BuwtJTfzG0iDgGiW4V0SUbljyO0t7D CIwB2Vt38Kj7eZRbLG/OC+i8L8FP71tG8I3Ui+K3DtG+CUMAg6+KAlM/qGM2q5xbVOfv JtR5x3rnu6lpGFjYHMP449DaWzn2Q3C+3oLHJIBxUPxcGGF42ssqBDqEHzDzKJ4maTkH v+kQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729933569; x=1730538369; 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=uSxsduxeRk0DErvCMMJe2weHoS7og5qwINtzWqXLgv0=; b=lR6oPoE47rhqiBNZAy3MvM5Fgz3XJflrL9dVtUqGKZ6QgE64YbIpbTgJ1y4VOInNcG vq0GvObUXZHmCLjvCaW+XMHwYdMbvNHer5nucp7S8ykFiP74J8ZrL9cUm6LV1PjIpZwl 4G9DZCwEPfyuAql2Z7meIq7AP0BofOEn8pmh0Q8spO4MTYJ8x5rsZ52tvwF94jbgwn45 dWr6xjfgwIt+rryKhR0VxKBxXfy57VJp4sVS1E7K6rGtu6WijOP0Cfee5XdwXCqHTlnw f7RwpD6EIWn6ClN0m9JtEOwMoAFM0bqQhj1Q2yYELkgVZ+2pNO+U6F2AImxa2Wa/YiDC 6OCg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729933569; x=1730538369; 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=uSxsduxeRk0DErvCMMJe2weHoS7og5qwINtzWqXLgv0=; b=Q/0Oh1VWk2BOKOdT3/HrMQ+b1G1o5KPa3Amt+lKuP41sNjOA0j3Y3JjxVAmLBn0P+D u7Ec9HNeEuQje7Tplb4SZchuTfIXecr/d9QQFt2mATjNgNE4Ag6KHqcv3+Ivketg2foL w7bQTmQtCYOQ2AxcQf9/Riz/OFulMCiJh3lle2Ol6ABlwzDZqCrnXVFuXb+XgtjhE6Ia GbKvrzhc/sMJFrFcOWVpWdf03WFPmXokxWBBP+7+0G8yaJrJX3wvBGP4hTYwf7r70e/a G04ty1CYNIscuS2pe2ysFr6/jZtUjaYDGK0WO8C9j9zj8b2xdpFiRqEFttIp99XFZnq1 eHCg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCVE05BsTN0R2zkfXjETUp1O1YIyok5sqFHQwAiJgPfO54HPzyjto17PWLL0zoPCR+JDg2ymaeKFxS2R@gnusha.org X-Gm-Message-State: AOJu0YwkQWwCjPKDTR+cSyV3w1ldXZ84+unxidVXkiV8XUg8meB5s3jI yo5oxJsyNhzjTfNp99Lr6cDPnS7WELSx/zwZScCrHDZeqaKsK/g3 X-Google-Smtp-Source: AGHT+IFr79TxEXzJqCwxoCNc4pOaID3uMAwnW8vf9KMx89kuQxNhy31Jb0+yYQ4R0gUUrrYIMgxWMQ== X-Received: by 2002:a25:8287:0:b0:e2b:d3da:46d7 with SMTP id 3f1490d57ef6-e3087bfca8dmr1506892276.40.1729933569275; Sat, 26 Oct 2024 02:06:09 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:709:b0:e2b:d93a:e562 with SMTP id 3f1490d57ef6-e2e4a7c56c2ls87680276.1.-pod-prod-09-us; Sat, 26 Oct 2024 02:06:07 -0700 (PDT) X-Received: by 2002:a05:690c:f8e:b0:6e3:22ee:bfd3 with SMTP id 00721157ae682-6e9d898212dmr21266927b3.20.1729933566990; Sat, 26 Oct 2024 02:06:06 -0700 (PDT) Received: by 2002:a05:690c:640c:b0:6dd:f386:13dc with SMTP id 00721157ae682-6e7eefee159ms7b3; Fri, 25 Oct 2024 02:58:49 -0700 (PDT) X-Received: by 2002:a05:690c:f92:b0:6e3:116c:ec0c with SMTP id 00721157ae682-6e86630a038mr47485397b3.30.1729850328171; Fri, 25 Oct 2024 02:58:48 -0700 (PDT) Date: Fri, 25 Oct 2024 02:58:47 -0700 (PDT) From: Garlo Nicon To: Bitcoin Development Mailing List Message-Id: In-Reply-To: <864868fb-164b-4d64-8c01-f496480c26e4n@googlegroups.com> References: <9e48edb6-1909-4eee-a0c7-48123f42a198n@googlegroups.com> <91ba7058-776d-4ff0-a179-bb2917ef03ffn@googlegroups.com> <864868fb-164b-4d64-8c01-f496480c26e4n@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_57582_1336580663.1729850327845" X-Original-Sender: garlonicon@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_57582_1336580663.1729850327845 Content-Type: multipart/alternative; boundary="----=_Part_57583_703281779.1729850327845" ------=_Part_57583_703281779.1729850327845 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > could you elaborate more on how exactly you envision tuning the mining=20 difficulty using two private keys? For example: this address requires grinding a single byte:=20 https://mempool.space/testnet4/address/tb1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensa= ncqmv2l2n82p0q5f5tls758l9d And this one requires grinding two bytes:=20 https://mempool.space/testnet4/address/tb1qk3endeq6x0xj4pjt4zwag8wf3a629rzq= r8jxd7jnmlac902wa5ysqxm9wt So, in the first case, if your difficulty is 1, then in the second case, it= =20 is 256. If you require both, then your real difficulty is equal to 257. Which means, that by requiring N different signature sizes, and forming a= =20 multisig, you can pick a difficulty somewhere in between. pi=C4=85tek, 25 pa=C5=BAdziernika 2024 o 02:40:01 UTC+2 Vicky napisa=C5=82(= a): > 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= =20 > r 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= =20 > on how exactly you envision tuning the mining difficulty using two privat= e=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 coul= d=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= wrote: > >> So, some more notes on this... >> >> I figured we can use OP_CODESEPARATOR to have more variety over the *z *= value,=20 >> with OP_CODESEPARATOR we can get pretty much unlimited variety (well onl= y=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 for= ce=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 signe= r=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_SINGL= E=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 ca= n=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 s= tep=20 >> and so on. >> >> So with this we can get reasonable security (90bits) by using 6 batches= =20 >> of these signatures (36 short signatures in total), which leads to the o= nly=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 chec= k=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 vali= d=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 us= e=20 >> case I was thinking about (double-spend protection for zero-conf=20 >> transactions) it is not enough, since malicious signer can find 2 collid= ing=20 >> transactions, submit the first one, and then double-spend with the secon= d=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= =20 >> *public keys* (pre-images) *and that would act as a signature, the order= =20 >> should not be important. The security of this pre-image reveal scheme is= =20 >> log2(*n* choose *m*) bits, but it gets very tricky when then talking=20 >> about the actual short signature security, because now that order is not= at=20 >> all important, the attacker can choose any of the *m *revealed public=20 >> keys to match the first signature (instead of 6), *m*-1 for the second= =20 >> (instead of 5), and so on... I tried to outline that in the spreadsheet = and=20 >> using 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 e= ver=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 fo= r=20 >>> each signature? For instance by using SIGHASH flags to re-randomize z f= or=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 wit= h=20 >>> security if the transaction's 2nd input is a keyspend (p2pkh, p2wpkh, p= 2tr)=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 spa= ce=20 >>> of the finite field), you can be sure that for the same z only 1 of the= m=20 >>> will ever be short, so if you require 6 of them to be short the only wa= y=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 = he=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 differe= nt=20 >>> signatures (under different sighash) would need to have the same positi= on=20 >>> as when the signer generated them (only 5 because attacker can re-use t= he 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 probabi= lity=20 >>> of an attacker finding the valid solution is (1/{number of keys})^5. Fo= r=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= =20 >>> to a large number of public keys where some subset is opened by the=20 >>> spender. Thus, generate z to provide a signature with sufficient number= s of=20 >>> small size signatures to prevent brute force? That is, commit to say 10= 24=20 >>> public keys and then only reveal 64 public key commitments to give the= =20 >>> party who 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 = keys=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 key= s)=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 contex= t=20 >>> of PoW locked outputs. It turns out you can fine-tune the mining diffic= ulty=20 >>> by just using 2 private keys, and making sure their possible transactio= n=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 has= h=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 val= ue=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= =20 >>>> to 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 lon= g 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 = for=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 t= o=20 >>>> a large number of public keys where some subset is opened by the spend= er.=20 >>>> Thus, generate z to provide a signature with sufficient numbers of sma= ll=20 >>>> size signatures to prevent brute force? That is, commit to say 1024 pu= blic=20 >>>> keys and then only reveal 64 public key commitments to give the party = who=20 >>>> knows preimages of the public keys an advantage? >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> On Mon, Sep 23, 2024 at 5:37=E2=80=AFPM Adam Borcany =20 >>>> 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 line= s up=20 >>>>> perfectly with a 256 bit space especially for a fixed r-value that ha= s=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= =20 >>>>> *k* 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 ov= er=20 >>>>> finite fields, we can create a set of all the integers 0..2^248 and t= hen=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=20 >>>>> div 2 + 1 + 2^247} >>>>> Which can be also be represented on the finite field circle & it help= s=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 o= n=20 >>>>> the transaction hash *z* (technically *z* is just left-most bits of= =20 >>>>> the transaction hash) being in the specified intervals (depending on = the=20 >>>>> choice of *x*, which in turn depends on the choice of *d*), it is=20 >>>>> also 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 inte= rvals=20 >>>>> from *0* and *n div 2 -1* respectively. So while we can say that=20 >>>>> there is a 1/256 chance that a signature will be short for one privat= e 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 int= ervals=20 >>>>> don't overlap). So for multiple private keys to generate short signat= ures=20 >>>>> over the same message, they need to correspond to the overlapping int= ervals. >>>>> >>>>> 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 priva= te=20 >>>>> keys & let the intervals overlap (and then use the intersection of an= y 2=20 >>>>> adjacent private key intervals by requiring 2 short signatures), but = this=20 >>>>> will just make it much harder to produce a signature (as the z value = will=20 >>>>> now have to land at the intersection of the intervals). In the end th= e 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, an= d 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 = than=20 >>>>> the signer to find a valid one - so this is insecure for any reasonab= le=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, sen= d=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-= bb2917ef03ffn%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/= e7c5645a-1ac2-458b-a85d-0aecc768392en%40googlegroups.com. ------=_Part_57583_703281779.1729850327845 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > could you elaborate more on how exactly you envision tuning the mining= difficulty using two private keys?

For example: this address re= quires grinding a single byte: https://mempool.space/testnet4/address/tb1qz= sjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tls758l9d
And this one= requires grinding two bytes: https://mempool.space/testnet4/address/tb1qk3= endeq6x0xj4pjt4zwag8wf3a629rzqr8jxd7jnmlac902wa5ysqxm9wt

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

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

pi=C4=85tek, 2= 5 pa=C5=BAdziernika 2024 o=C2=A002:40:01 UTC+2 Vicky napisa=C5=82(a):
<= /div>
Great and fascinat= ing discussion and detailed analysis, particularly Adam, for the rigorous m= athematical examination of the signature size distribution.

A few ob= servations and questions:

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

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

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

While perhaps not immediately practical, t= his exploration has helped illuminate some interesting properties of ECDSA = signature size distributions and potential applications beyond Lamport sign= atures.
Thanks
Vicky

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

I figured we can use OP_CODESEPARATOR to have mor= e variety over the z value, with OP_CODESEPARATOR we can get pretty = much unlimited variety (well only limited by the script limit), so by requi= ring that 6 short signatures (a signature batch) are published for every OP= _CODESEPRATOR part we can force anyone to use all the possible sighashes fo= r the signatures.

As for the security of these= 6 short signatures (size<59), it seems like we only get ~15bits of secu= rity for every batch of those, here is the intuition about it from the pers= pective 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 <adamb...@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:
Thanks=C2=A0for lookin= g into this and writing this up. It is very exciting to see someone look in= to this deeper.

Do I understand correctly that you are saying that t= he size of each signature from a set of signatures is not independently sam= pled as long as all the signatures use the same z and r?

Could this = scheme be saved by the fact that z need not be the same for each signature?= For instance by using SIGHASH flags to re-randomize z for each signature. = Wouldn't that restore independence?

>=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> wr= ote:
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+...@googlegroups.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/e7c5645a-1ac2-458b-a85d-0aecc768392en%40googlegroups.com.
------=_Part_57583_703281779.1729850327845-- ------=_Part_57582_1336580663.1729850327845--