From mboxrd@z Thu Jan 1 00:00:00 1970 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 <bitcoindev+bncBCY3VBMZVAMRB77B6K4AMGQEFRRUHPI@googlegroups.com>) 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 <bitcoindev@gnusha.org>; 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 <garlonicon@gmail.com> To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> Message-Id: <e7c5645a-1ac2-458b-a85d-0aecc768392en@googlegroups.com> In-Reply-To: <864868fb-164b-4d64-8c01-f496480c26e4n@googlegroups.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> <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: <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_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 >> <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 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 <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 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 <eth...@gmail.com> 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 <adamb...@gmail.c= om>=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 >>>>> <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/= 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?<br /><br />For example: this address re= quires grinding a single byte: https://mempool.space/testnet4/address/tb1qz= sjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tls758l9d<br />And this one= requires grinding two bytes: https://mempool.space/testnet4/address/tb1qk3= endeq6x0xj4pjt4zwag8wf3a629rzqr8jxd7jnmlac902wa5ysqxm9wt<br /><br />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.<br /><br = />Which means, that by requiring N different signature sizes, and forming a= multisig, you can pick a difficulty somewhere in between.<br /><br /><div = class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">pi=C4=85tek, 2= 5 pa=C5=BAdziernika 2024 o=C2=A002:40:01 UTC+2 Vicky napisa=C5=82(a):<br/><= /div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border= -left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Great and fascinat= ing discussion and detailed analysis, particularly Adam, for the rigorous m= athematical examination of the signature size distribution.<br><br>A few ob= servations and questions:<br><br>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.<br><br>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.<br><br>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?<br><br>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.<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 wrote:<br></div><blockquote class=3D"= gmail_quote" style=3D"margin:0 0 0 0.8ex;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 figured we can use OP_CODESEPARATOR to have mor= e variety over the <i>z </i>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.<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 secu= rity for every batch of those, here is the intuition about it from the pers= pective 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 rel=3D"nofollow">adamb...@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);padding-left:1ex"><div di= r=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 rel=3D"nofollow">eth...@gmail.com</a>> wrote:<br></div><blockquote cl= ass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid= rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">Thanks=C2=A0for lookin= g into this and writing this up. It is very exciting to see someone look in= to this deeper.<br><br>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?<br><br>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?<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 rel=3D"nofollow">adamb...@gmail.com</a>> wr= ote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px= 0.8ex;border-left:1px solid rgb(204,204,204);padding-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 rel=3D"nofollow">bitcoindev+...@googlegroups.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" rel=3D"nofollow" target=3D"= _blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Dpl&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=3D1729936693553000&usg=3DAOvVaw1hlektGArZZ4_VOXv7= qS_U">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></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/e7c5645a-1ac2-458b-a85d-0aecc768392en%40googlegroups.com?utm_med= ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind= ev/e7c5645a-1ac2-458b-a85d-0aecc768392en%40googlegroups.com</a>.<br /> ------=_Part_57583_703281779.1729850327845-- ------=_Part_57582_1336580663.1729850327845--