diff options
| author | Vicky <vicky.fuyu@gmail.com> | 2024-10-24 17:20:54 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@googlegroups.com> | 2024-10-24 17:40:09 -0700 |
| commit | 63544b9afd4f4405df068e80eeb3bdea699df4bb (patch) | |
| tree | fd6e2d14e18b08020aefcd4c9201cd4bf951cee9 | |
| parent | 0f2f4a62f53cdec0e0bee5d80a6e17c2b6b4a4f0 (diff) | |
| download | pi-bitcoindev-63544b9afd4f4405df068e80eeb3bdea699df4bb.tar.gz pi-bitcoindev-63544b9afd4f4405df068e80eeb3bdea699df4bb.zip | |
Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)
| -rw-r--r-- | 4d/8783119144203a2f4058968b89371c455da25e | 870 |
1 files changed, 870 insertions, 0 deletions
diff --git a/4d/8783119144203a2f4058968b89371c455da25e b/4d/8783119144203a2f4058968b89371c455da25e new file mode 100644 index 000000000..f0d76811e --- /dev/null +++ b/4d/8783119144203a2f4058968b89371c455da25e @@ -0,0 +1,870 @@ +Delivery-date: Thu, 24 Oct 2024 17:40:09 -0700 +Received: from mail-yb1-f190.google.com ([209.85.219.190]) + by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 + (Exim 4.94.2) + (envelope-from <bitcoindev+bncBCS6PG46ZMJBBX6R5O4AMGQEMO5FGOA@googlegroups.com>) + id 1t48N5-0004sS-AM + for bitcoindev@gnusha.org; Thu, 24 Oct 2024 17:40:09 -0700 +Received: by mail-yb1-f190.google.com with SMTP id 3f1490d57ef6-e2605ce4276sf2880462276.3 + for <bitcoindev@gnusha.org>; Thu, 24 Oct 2024 17:40:07 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=googlegroups.com; s=20230601; t=1729816801; x=1730421601; darn=gnusha.org; + h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post + :list-id:mailing-list:precedence:x-original-sender:mime-version + :subject:references:in-reply-to:message-id:to:from:date:sender:from + :to:cc:subject:date:message-id:reply-to; + bh=X7H37YMUcYaqaflMZhvN5EIxJuUhoZQrd7tHIXjofRc=; + b=vsFGrrB5t4ywBeqaNd73O9xyRzJ5zck3TiDHGO2tQaoVxYHeRZlQXQoK+mdfPZyBij + EffPNGEUZC3TD3tBqeoI4xg2fw3aK99QAMAtzfI69O8IM5SR+CWJJrIX5IjJN9BXON1v + EGOj9+rh7456vfTEX5ujil8PE9cVSqi0GnbrfhcFw8KGMIaOv2HV1BZIXT+Rp7lHsoll + z6DIFe1WOpFps5S+P3f9Myetb/jUHVhX6Xt2hnH21k4qo9bhbl23dffGGbcJEWckpTem + T9r9YkZvf1pfOvpBffuApGfd8F0Yov6i+w9C1ggeqJZOQmVBj3Yyt0chrP0adwY3Ya0k + V/Cg== +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=gmail.com; s=20230601; t=1729816801; x=1730421601; darn=gnusha.org; + h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post + :list-id:mailing-list:precedence:x-original-sender:mime-version + :subject:references:in-reply-to:message-id:to:from:date:from:to:cc + :subject:date:message-id:reply-to; + bh=X7H37YMUcYaqaflMZhvN5EIxJuUhoZQrd7tHIXjofRc=; + b=BkvinDqT4Ov2TpvgVwPD6/tj5GPlV2DYKL2CpAqvsGG+HJFn1/ecNM7t8mzoMHcqFM + PUnewPflsOdTgANQM7Cyfd1eWEFTqClsFZLXtJ4XfBdVV8cAmfkjMyQARWjXxC1rRkcE + D5BrSHEz61IulN8dJ57uCMd4XfMSyy/cCaECggyoWBqAKdN9f/Fb3sTK7EGoe2A9INjY + i/SLtVIaJiuSycaTbhkrAaFsWiqfzLec9/fdxIdPbKFcoTNFSjjrYDGodXkfRx/VdjsI + jus+wLdJ44d/C0FyRYdlWHW0pt9LyksxJEqc8GEJJcx3PiD48nV9mxO1UTbn/MbUpn4D + cKug== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20230601; t=1729816801; x=1730421601; + h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post + :list-id:mailing-list:precedence:x-original-sender:mime-version + :subject:references:in-reply-to:message-id:to:from:date:x-beenthere + :x-gm-message-state:sender:from:to:cc:subject:date:message-id + :reply-to; + bh=X7H37YMUcYaqaflMZhvN5EIxJuUhoZQrd7tHIXjofRc=; + b=AP5X0i9V6Cc40CWpa/xlfL6G0pwu9301zMU+GDMb60rv5mfcxgoCLnQIVyVVANC1kC + uFHO9grd30+BRFn3RHhJVHdR2ihsgGu6+XqogTH23ekceZ1eweJ+Z7J5JkJo6JLucsQk + E6gOH5xcKHSOO1JTKvB//ciuXrU8ML2VuUapgGvxySqS9vzEZqFPUTk8Gdn9QBz4deXy + ItJZXKb4Y3KrWG6QG8Vf+1EMdSAPYsk45tzH1+8Lu+MspD7cT7ekV2E1XTGJfqFdhujk + MvV1YWc5n8nMSZSqoZs7wKSLz3RQaeOvnxuNA+U/yKKk9+lduyKW8eW/Ag4srZ+NpHs5 + nqNA== +Sender: bitcoindev@googlegroups.com +X-Forwarded-Encrypted: i=1; AJvYcCX5+riEijiyD3Y47fkIE0xKtmveBx6UcNnKS9sGLYUyPOLW7e/PARhSiStvr7/UTRYTOLyvJAD+wCs0@gnusha.org +X-Gm-Message-State: AOJu0YxgzXHS4Eb5II2VLA3ozyxVk05rhEN7lwOzszgNJxJYJwwm6rbA + 3AA5DlRWnoxzs6SMb7N8ZPhK7TYvw+/pdo9uAaA2YcMN/abKCWMX +X-Google-Smtp-Source: AGHT+IGmgEs4YLRlcmTvGSN4O+Iw4ksAXHqOQ1oIe3aQ/haTEik3BdIRpcV6uUOf6LmO1Yx/o7w6/w== +X-Received: by 2002:a05:6902:c08:b0:e28:e9ea:9784 with SMTP id 3f1490d57ef6-e2e3a6d39e7mr9288202276.49.1729816801104; + Thu, 24 Oct 2024 17:40:01 -0700 (PDT) +X-BeenThere: bitcoindev@googlegroups.com +Received: by 2002:a05:6902:1244:b0:e28:ff06:8c0b with SMTP id + 3f1490d57ef6-e2e4a5e613bls724317276.0.-pod-prod-03-us; Thu, 24 Oct 2024 + 17:39:59 -0700 (PDT) +X-Received: by 2002:a05:690c:f09:b0:6e2:1467:17b4 with SMTP id 00721157ae682-6e7f0dbbf21mr91097467b3.9.1729816799047; + Thu, 24 Oct 2024 17:39:59 -0700 (PDT) +Received: by 2002:a05:690c:640c:b0:6dd:f386:13dc with SMTP id 00721157ae682-6e7eefee159ms7b3; + Thu, 24 Oct 2024 17:20:56 -0700 (PDT) +X-Received: by 2002:a05:690c:4087:b0:6e3:1f02:407b with SMTP id 00721157ae682-6e85816739bmr31522357b3.11.1729815655236; + Thu, 24 Oct 2024 17:20:55 -0700 (PDT) +Date: Thu, 24 Oct 2024 17:20:54 -0700 (PDT) +From: Vicky <vicky.fuyu@gmail.com> +To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> +Message-Id: <864868fb-164b-4d64-8c01-f496480c26e4n@googlegroups.com> +In-Reply-To: <CAOY=fz=bcun5U75PUJJGuuB7p5dHtghrYf9gfOvj4zpiWdM_Tg@mail.gmail.com> +References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com> + <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com> + <ZjD-dMMGxoGNgzIg@camus> + <b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n@googlegroups.com> + <ZjzFtus_aBchwKz2@camus> + <9e48edb6-1909-4eee-a0c7-48123f42a198n@googlegroups.com> + <91ba7058-776d-4ff0-a179-bb2917ef03ffn@googlegroups.com> + <CAEM=y+UKgDRtaV5uveiX_Hn1dTDEF-DSHw0SjRu+j0s3fmp78Q@mail.gmail.com> + <CAOY=fzk+nKBw4kpLJLe=EngNfD5iEsWVsa5sMyPaXKp9cDAqdQ@mail.gmail.com> + <CAOY=fz=bcun5U75PUJJGuuB7p5dHtghrYf9gfOvj4zpiWdM_Tg@mail.gmail.com> +Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport + Signatures (no changes needed) +MIME-Version: 1.0 +Content-Type: multipart/mixed; + boundary="----=_Part_27804_138313945.1729815654787" +X-Original-Sender: Vicky.fuyu@gmail.com +Precedence: list +Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com +List-ID: <bitcoindev.googlegroups.com> +X-Google-Group-Id: 786775582512 +List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com> +List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com> +List-Archive: <https://groups.google.com/group/bitcoindev +List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com> +List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>, + <https://groups.google.com/group/bitcoindev/subscribe> +X-Spam-Score: 2.0 (++) + +------=_Part_27804_138313945.1729815654787 +Content-Type: multipart/alternative; + boundary="----=_Part_27805_838118986.1729815654787" + +------=_Part_27805_838118986.1729815654787 +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +Great and fascinating discussion and detailed analysis, particularly Adam,= +=20 +for the rigorous mathematical examination of the signature size=20 +distribution. + +A few observations and questions: + +1. The insight about signature size correlation when using the same z and r= +=20 +is particularly important. While using different SIGHASH flags provides=20 +some independence, the ~15 bits of security per 6-signature batch makes=20 +this construction impractical under current Bitcoin script limits. + +2. Regarding Adam's idea of PoW-locked outputs, could you elaborate more on= +=20 +how exactly you envision tuning the mining difficulty using two private=20 +keys? This interesting direction could be more practical than the full=20 +Lamport signature scheme. + +3. One additional consideration about the security model: Even if we could= +=20 +achieve higher bits of security through more signatures, wouldn't the=20 +resource requirements (script size, verification time) make this=20 +impractical for most use cases compared to existing quantum-resistant=20 +signature schemes that could be added through a soft fork? + +While perhaps not immediately practical, this exploration has helped=20 +illuminate some interesting properties of ECDSA signature size=20 +distributions and potential applications beyond Lamport signatures. +Thanks +Vicky + +On Wednesday, September 25, 2024 at 8:48:04=E2=80=AFPM UTC-4 Adam Borcany w= +rote: + +> So, some more notes on this... +> +> I figured we can use OP_CODESEPARATOR to have more variety over the *z *v= +alue,=20 +> with OP_CODESEPARATOR we can get pretty much unlimited variety (well only= +=20 +> limited by the script limit), so by requiring that 6 short signatures (a= +=20 +> signature batch) are published for every OP_CODESEPRATOR part we can forc= +e=20 +> anyone to use all the possible sighashes for the signatures. +> +> As for the security of these 6 short signatures (size<59), it seems like= +=20 +> we only get ~15bits of security for every batch of those, here is the=20 +> intuition about it from the perspective of an attacker... +> 1. Attacker starts with SIGHASH_NONE | ANYONECANPAY and grinds the=20 +> transaction locktime, version & input sequence number, such that it=20 +> produces a valid short signature under the same pubkey as original signer= +=20 +> (this has 6/256 odds) +> 2. Attacker then continues with SIGHASH_NONE by grinding the 2nd=20 +> transaction input (e.g. the sequence number of it), such that it again=20 +> produces a valid short signature under the same pubkey as the original=20 +> signer (this has 5/256 odds) +> 3. Attacker continues with SIGHASH_SINGLE | ANYONECANPAY & SIGHASH_SINGLE= +=20 +> by grinding the transaction's 1st output - these have to go together,=20 +> because there is no field that the attacker can manipulate such that it= +=20 +> changes only one of those (this has (4*3)/65536 odds) +> 4. Attacker finishes with SIGHASH_ALL | ANYONECANPAY & SIGHASH_ALL by=20 +> grinding the transaction's 2nd output - these again have to go together,= +=20 +> because there is no field that the attacker can manipulate such that it= +=20 +> changes only one of those (this has (2*1)/65536 odds) +> The reason for the numerator here not being 1 is because the attacker can= +=20 +> present the different sighash signatures in any order, so that he can=20 +> choose from 6 different public keys in the first step, 5 in the second st= +ep=20 +> and so on. +> +> So with this we can get reasonable security (90bits) by using 6 batches o= +f=20 +> these signatures (36 short signatures in total), which leads to the only= +=20 +> problem of all of this - non-push opcode limit for p2wsh redeem scripts,= +=20 +> which is just 201 non-push opcodes. Here is a simple script to just check= +=20 +> if a single signature was valid: +> # scriptSig=20 +> <pubkey index>=20 +> <short signature> +> +> # scriptPubkey +> <pubkey n> +> ... +> <pubkey 1> +> <pubkey 0> +> +> n+1 OP_ROLL OP_DUP OP_SIZE 59 OP_EQUALVERIFY #verify signature length +> n+2 OP_ROLL OP_ROLL #get the public key +> OP_CHECKSIGVERIFY #check signature matches +> +> It has 7 non-push opcodes, and doesn't include any lamport signature=20 +> checking, purely just checks if a signature is short & signed under valid= +=20 +> public key from the set of n public keys. So for 36 signatures you'd end = +up=20 +> with at least 252 non-push opcodes, already above the opcode count limit. +> +> Also important to note is that the 90bit security only applies to=20 +> pre-image resistance & second pre-image resistance. Due to the birthday= +=20 +> paradox the collision resistance is just 45bits, which is good enough if= +=20 +> you just want to use it for quantum resistant signatures, but for the use= +=20 +> case I was thinking about (double-spend protection for zero-conf=20 +> transactions) it is not enough, since malicious signer can find 2 collidi= +ng=20 +> transactions, submit the first one, and then double-spend with the second= +=20 +> one and not equivocate the lamport signature scheme. To achieve 90bit=20 +> collision resistance we would need 72 short signatures & at least 504=20 +> non-push opcodes. +> +> Another direction I was thinking about was using the public keys=20 +> themselves as kind of a lamport signature scheme. The scriptPubkey would= +=20 +> only contain *n* RIPEMD-160 commitments to the public keys & then the=20 +> signer will reveal *m* of these public keys and provide a short ECDSA=20 +> signature to them. The signer would essentially reveal *m *out of the *n = +*public=20 +> keys* (pre-images) *and that would act as a signature, the order should= +=20 +> not be important. The security of this pre-image reveal scheme is log2(*n= +*=20 +> choose *m*) bits, but it gets very tricky when then talking about the=20 +> actual short signature security, because now that order is not at all=20 +> important, the attacker can choose any of the *m *revealed public keys to= +=20 +> match the first signature (instead of 6), *m*-1 for the second (instead= +=20 +> of 5), and so on... I tried to outline that in the spreadsheet and using= +=20 +> m=3D256, n=3D30 we only get 51bits of security. +> +> Cheers, +> Adam +> +> +> +> On Wed, 25 Sept 2024 at 00:19, Adam Borcany <adamb...@gmail.com> wrote: +> +>> > Do I understand correctly that you are saying that the size of each=20 +>> signature from a set of signatures is not independently sampled as long = +as=20 +>> all the signatures use the same z and r?=20 +>> +>> Yes, correct, every private key d adds a 2^248 wide interval (actually= +=20 +>> two 2^247 wide intervals) of possible transaction hash values z, these= +=20 +>> intervals can have no overlap (meaning only one of the signature will ev= +er=20 +>> be short), or can overlap and in that case the both signatures will be= +=20 +>> short only if the transaction hash is at this overlapping region. +>> +>> > Could this scheme be saved by the fact that z need not be the same for= +=20 +>> each signature? For instance by using SIGHASH flags to re-randomize z fo= +r=20 +>> each signature. Wouldn't that restore independence? +>> +>> So there are 6 possible sighash flags, but SIGHASH_NONE | ANYONECANPAY= +=20 +>> don't provide any security as it can be re-used by the attacker (as=20 +>> attacker can just add its own output), also SIGHASH_NONE only helps with= +=20 +>> security if the transaction's 2nd input is a keyspend (p2pkh, p2wpkh, p2= +tr)=20 +>> and uses SIGHASH_ALL, otherwise attacker is able to just re-use that=20 +>> signature as well, so at best we can have 5 different sighashes that=20 +>> contribute to the security. This makes the scheme somewhat better - if= +=20 +>> you use 256 private keys (such that they collectively span the full spac= +e=20 +>> of the finite field), you can be sure that for the same z only 1 of them= +=20 +>> will ever be short, so if you require 6 of them to be short the only way= +=20 +>> for that to happen is that the 6 signatures use different SIGHASH and=20 +>> therefore use different z. I think this improves the security somewhat,= +=20 +>> signer will produce 6 short signatures with different sighashes (maybe h= +e=20 +>> needs to do a bit of grinding, but really little, like 1-5 iterations), = +the=20 +>> attacker would then have to construct a transaction such that 5 differen= +t=20 +>> signatures (under different sighash) would need to have the same positio= +n=20 +>> as when the signer generated them (only 5 because attacker can re-use th= +e SIGHASH_NONE=20 +>> | ANYONECANPAY signature), the probability of that happening is=20 +>> something around 1/2^40, so this means 2^40 more work for the attacker.= +=20 +>> This still scales with the number of public keys, such that the probabil= +ity=20 +>> of an attacker finding the valid solution is (1/{number of keys})^5. For= +=20 +>> reasonable security (e.g. 80-bit) we would need 2^16 public keys, which= +=20 +>> doesn't actually sound super crazy, but is still too much for bitcoin. +>> +>> > How much harder is this? Couldn't the locking script secretly commit t= +o=20 +>> a large number of public keys where some subset is opened by the spender= +.=20 +>> Thus, generate z to provide a signature with sufficient numbers of small= +=20 +>> size signatures to prevent brute force? That is, commit to say 1024 publ= +ic=20 +>> keys and then only reveal 64 public key commitments to give the party wh= +o=20 +>> knows preimages of the public keys an advantage?=20 +>> +>> This would only help if you could create a vector commitment of the=20 +>> public keys (e.g. merkle tree), such that you can then only reveal some = +of=20 +>> them (based on my previous paragraph, you just need to reveal 6 public k= +eys=20 +>> & signatures), and for the commitment to not blow up the script size.=20 +>> Committing to 1024 public keys by hash (or even use 1024 raw public keys= +)=20 +>> is out of the question because the p2wsh script size is limited to 10kB. +>> +>> On a different note... I also started thinking about this in the context= +=20 +>> of PoW locked outputs. It turns out you can fine-tune the mining difficu= +lty=20 +>> by just using 2 private keys, and making sure their possible transaction= +=20 +>> hash *z* intervals overlap in such a way that it creates an interval of= +=20 +>> fixed width, the PoW is then just about making sure the transaction hash= +=20 +>> lands into this interval - so actually no modular arithmetic needed, it = +is=20 +>> purely double-SHA256 hashing of the transaction and checking if the valu= +e=20 +>> is within the interval. +>> +>> Cheers, +>> Adam +>> +>> On Tue, 24 Sept 2024 at 23:08, Ethan Heilman <eth...@gmail.com> wrote: +>> +>>> Thanks for looking into this and writing this up. It is very exciting t= +o=20 +>>> see someone look into this deeper. +>>> +>>> Do I understand correctly that you are saying that the size of each=20 +>>> signature from a set of signatures is not independently sampled as long= + as=20 +>>> all the signatures use the same z and r? +>>> +>>> Could this scheme be saved by the fact that z need not be the same for= +=20 +>>> each signature? For instance by using SIGHASH flags to re-randomize z f= +or=20 +>>> each signature. Wouldn't that restore independence? +>>> +>>> > You can increase the number of private keys & let the intervals=20 +>>> overlap (and then use the intersection of any 2 adjacent private key=20 +>>> intervals by requiring 2 short signatures), but this will just make it = +much=20 +>>> harder to produce a signature (as the z value will now have to land at = +the=20 +>>> intersection of the intervals) +>>> +>>> How much harder is this? Couldn't the locking script secretly commit to= +=20 +>>> a large number of public keys where some subset is opened by the spende= +r.=20 +>>> Thus, generate z to provide a signature with sufficient numbers of smal= +l=20 +>>> size signatures to prevent brute force? That is, commit to say 1024 pub= +lic=20 +>>> keys and then only reveal 64 public key commitments to give the party w= +ho=20 +>>> knows preimages of the public keys an advantage? +>>> +>>> +>>> +>>> +>>> +>>> +>>> +>>> On Mon, Sep 23, 2024 at 5:37=E2=80=AFPM Adam Borcany <adamb...@gmail.co= +m> wrote: +>>> +>>>> Hello Ethan, +>>>> +>>>> > 3. We have modeled ECDSA s-values signatures being uniformly drawn= +=20 +>>>> from 2^256. It seems unlikely to me that the Elliptic Curve math lines= + up=20 +>>>> perfectly with a 256 bit space especially for a fixed r-value that has= +=20 +>>>> special mathematical properties.=20 +>>>> +>>>> I've been looking into this more deeply, and it would seem like it's= +=20 +>>>> not random at all, let me explain the intuition... +>>>> If we take the signing equation for the *s* value: +>>>> s =3D k^-1*(z+rd) mod n +>>>> Considering that *k* is fixed and is set to 1/2 we get: +>>>> s =3D 2*(z+rd) mod n +>>>> We can let *x *=3D *rd* being a constant, since *r* is fixed (because = +*k*=20 +>>>> is fixed) and *d* is fixed at contract creation time: +>>>> s =3D 2*(z+x) mod n +>>>> Now for the size of the signature to be 59 or less, the *s* value=20 +>>>> needs to be smaller than 2^248, but since inequality isn't defined ove= +r=20 +>>>> finite fields, we can create a set of all the integers 0..2^248 and th= +en=20 +>>>> see if the s value is contained in this set: +>>>> s =E2=88=88 {i =E2=88=88 Z | i < 2^248}=20 +>>>> 2*(z+x) =E2=88=88 {i =E2=88=88 Z | i < 2^248}=20 +>>>> We now can divide the whole condition by 2: +>>>> (z+x) =E2=88=88 {i/2 | i < 2^248} +>>>> Which we can write as (keep in mind i/2 is division in the finite=20 +>>>> field):=20 +>>>> (z+x) =E2=88=88 {i =E2=88=88 Z | i < 2^247} =E2=88=AA {i =E2=88=88 Z |= + n div 2 + 1 =E2=89=A4 i < n div 2 + 1 +=20 +>>>> 2^247}, where div is integer division +>>>> By then subtracting *x* from both sides we finally get: +>>>> z =E2=88=88 {i - x mod n | i < 2^247} =E2=88=AA {i - x mod n | n div 2= + + 1 =E2=89=A4 i < n div=20 +>>>> 2 + 1 + 2^247} +>>>> Which can be also be represented on the finite field circle & it helps= +=20 +>>>> with the intuition: +>>>> [image: ecdsa-opsize-lamport.png] +>>>> Here *x *is set to 0 for simplicity. +>>>> +>>>> What this shows is that the signature size being 59 or less depends on= +=20 +>>>> the transaction hash *z* (technically *z* is just left-most bits of=20 +>>>> the transaction hash) being in the specified intervals (depending on t= +he=20 +>>>> choice of *x*, which in turn depends on the choice of *d*), it is also= +=20 +>>>> important to note that the interval is always of the size 2^248 (or=20 +>>>> actually 2 intervals each 2^247 elements), with x offsetting the inter= +vals=20 +>>>> from *0* and *n div 2 -1* respectively. So while we can say that there= +=20 +>>>> is a 1/256 chance that a signature will be short for one private key= +=20 +>>>> (because the intervals cover 1/256 of the circle), we cannot say that = +the=20 +>>>> size of other signatures under other private keys also has the same=20 +>>>> independent chance of being short (it might have 0% chance if the inte= +rvals=20 +>>>> don't overlap). So for multiple private keys to generate short signatu= +res=20 +>>>> over the same message, they need to correspond to the overlapping inte= +rvals. +>>>> +>>>> I think this breaks the whole construction, because you can partition= +=20 +>>>> the finite field into 256 non-overlapping intervals, corresponding to = +256=20 +>>>> private keys, such that only one of these private keys will produce a = +short=20 +>>>> signature for any given message. You can increase the number of privat= +e=20 +>>>> keys & let the intervals overlap (and then use the intersection of any= + 2=20 +>>>> adjacent private key intervals by requiring 2 short signatures), but t= +his=20 +>>>> will just make it much harder to produce a signature (as the z value w= +ill=20 +>>>> now have to land at the intersection of the intervals). In the end the= + work=20 +>>>> of the attacker is just 256 times harder than the work of the signer. = +The=20 +>>>> number 256 is stemming from the fact that we use 256 private keys, and= + is=20 +>>>> purely dependent on the number of private keys, so if we use e.g. 512= +=20 +>>>> private keys the attacker will need to grind 512 times more messages t= +han=20 +>>>> the signer to find a valid one - so this is insecure for any reasonabl= +e=20 +>>>> number of private keys. +>>>> +>>>> Cheers, +>>>> Adam +>>>> +>>>> --=20 +>>>> You received this message because you are subscribed to the Google=20 +>>>> Groups "Bitcoin Development Mailing List" group. +>>>> To unsubscribe from this group and stop receiving emails from it, send= +=20 +>>>> an email to bitcoindev+...@googlegroups.com. +>>>> To view this discussion on the web visit=20 +>>>> https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-b= +b2917ef03ffn%40googlegroups.com=20 +>>>> <https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-= +bb2917ef03ffn%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter> +>>>> . +>>>> +>>> + +--=20 +You received this message because you are subscribed to the Google Groups "= +Bitcoin Development Mailing List" group. +To unsubscribe from this group and stop receiving emails from it, send an e= +mail to bitcoindev+unsubscribe@googlegroups.com. +To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= +864868fb-164b-4d64-8c01-f496480c26e4n%40googlegroups.com. + +------=_Part_27805_838118986.1729815654787 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +Great and fascinating discussion and detailed analysis, particularly Adam, = +for the rigorous mathematical examination of the signature size distributio= +n.<br /><br />A few observations and questions:<br /><br />1. The insight a= +bout signature size correlation when using the same z and r is particularly= + important. While using different SIGHASH flags provides some independence,= + the ~15 bits of security per 6-signature batch makes this construction imp= +ractical under current Bitcoin script limits.<br /><br />2. Regarding Adam'= +s idea of PoW-locked outputs, could you elaborate more on how exactly you e= +nvision tuning the mining difficulty using two private keys? This interesti= +ng direction could be more practical than the full Lamport signature scheme= +.<br /><br />3. One additional consideration about the security model: Even= + if we could achieve higher bits of security through more signatures, would= +n't the resource requirements (script size, verification time) make this im= +practical for most use cases compared to existing quantum-resistant signatu= +re schemes that could be added through a soft fork?<br /><br />While perhap= +s not immediately practical, this exploration has helped illuminate some in= +teresting properties of ECDSA signature size distributions and potential ap= +plications beyond Lamport signatures.<div>Thanks</div><div>Vicky<br /><br /= +></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">On= + Wednesday, September 25, 2024 at 8:48:04=E2=80=AFPM UTC-4 Adam Borcany wro= +te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e= +x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir= +=3D"ltr"><div>So, some more notes on this...</div><div><br></div><div>I fig= +ured we can use OP_CODESEPARATOR to have more variety over the <i>z </i>val= +ue, with OP_CODESEPARATOR we can get pretty much unlimited variety (well on= +ly limited by the script limit), so by requiring that 6 short signatures (a= + signature batch) are published for every OP_CODESEPRATOR part we can force= + anyone to use all the possible sighashes for the signatures.<br></div><div= +><br></div><div>As for the security of these 6 short signatures (size<59= +), it seems like we only get ~15bits of security for every batch of those, = +here is the intuition about it from the perspective of an attacker...</div>= +<div> +1. Attacker starts with SIGHASH_NONE | ANYONECANPAY and grinds the transact= +ion locktime, version & input sequence number, such that it produces a = +valid short signature under the same pubkey as original signer (this has 6/= +256 odds)</div><div>2. Attacker then continues with SIGHASH_NONE by grindin= +g the 2nd transaction input (e.g. the sequence number of it), such that it = +again produces a valid short signature under the same pubkey as the origina= +l signer (this has 5/256 odds)</div><div>3. Attacker continues with SIGHASH= +_SINGLE=20 +| ANYONECANPAY & SIGHASH_SINGLE by grinding the transaction's 1st o= +utput - these have to go together, because there is no field that the attac= +ker can manipulate such that it changes only one of those (this has (4*3)/6= +5536 odds)</div><div>4. Attacker finishes with SIGHASH_ALL +| ANYONECANPAY & SIGHASH_ALL by grinding the transaction's 2nd outp= +ut - these again have to go together, because there is no field that the at= +tacker can manipulate such that it changes only one of those (this has=C2= +=A0 +(2*1)/65536 odds)</div><div>The reason for the numerator here not being 1 i= +s because the attacker can present the different sighash signatures in any = +order, so that he can choose from 6 different public keys in the first step= +, 5 in the second step and so on.</div><div><br></div><div>So with this we = +can get reasonable security (90bits) by using 6 batches of these signatures= + (36 short signatures in total), which leads to the only problem of all of = +this - non-push opcode limit for p2wsh redeem scripts, which is just 201 no= +n-push opcodes. Here is a simple script to just check if a single signature= + was valid:</div><div># scriptSig +<br><pubkey index> + +<br><short signature><br><br># scriptPubkey<br><pubkey n><br>..= +.<br><pubkey 1><br><pubkey 0><br><br>n+1 OP_ROLL OP_DUP OP_SIZE= + 59 OP_EQUALVERIFY #verify signature length<br>n+2 OP_ROLL OP_ROLL #get the= + public key<br>OP_CHECKSIGVERIFY #check signature matches</div><div><br></d= +iv><div>It has 7 non-push opcodes, and doesn't include any lamport sign= +ature checking, purely just checks if a signature is short & signed und= +er valid public key from the set of n public keys. So for 36 signatures you= +'d end up with at least 252 non-push opcodes, already above the opcode = +count limit.</div><div><br></div><div>Also important to note is that the 90= +bit security only applies to=20 +pre-image resistance & second pre-image resistance. Due to the birthday= + paradox the collision resistance is just 45bits, which is good enough if y= +ou just want to use it for quantum resistant signatures, but for the use ca= +se I was thinking about (double-spend protection for zero-conf transactions= +) it is not enough, since malicious signer can find 2 colliding transaction= +s, submit the first one, and then double-spend with the second one and not = +equivocate the lamport signature scheme. To achieve 90bit collision resista= +nce we would need 72 short signatures & at least 504 non-push opcodes.<= +/div><div><br></div><div>Another direction I was thinking about was using t= +he public keys themselves as kind of a lamport signature scheme. The script= +Pubkey would only contain <i>n</i> RIPEMD-160 commitments to the public key= +s & then the signer will reveal <i>m</i> of these public keys and provi= +de a short ECDSA signature to them. The signer would essentially reveal <i>= +m </i>out of the <i>n </i>public keys<i> (pre-images) </i>and that would ac= +t as a signature, the order should not be important. The security of this p= +re-image reveal scheme is log2(<i>n</i> choose <i>m</i>) bits, but it gets = +very tricky when then talking about the actual short signature security, be= +cause now that order is not at all important, the attacker can choose any o= +f the <i>m </i>revealed public keys to match the first signature (instead o= +f 6), <i>m</i>-1 for the second (instead of 5), and so on... I tried to out= +line that in the spreadsheet and using m=3D256, n=3D30 we only get 51bits o= +f security.<br></div><div><br></div><div>Cheers,</div><div>Adam<br></div><d= +iv><br></div></div><div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div cla= +ss=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, 25 Sept 20= +24 at 00:19, Adam Borcany <<a href data-email-masked rel=3D"nofollow">ad= +amb...@gmail.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" = +style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pa= +dding-left:1ex"><div dir=3D"ltr"><div>>=20 +Do I understand correctly that you are saying that the size of each=20 +signature from a set of signatures is not independently sampled as long=20 +as all the signatures use the same z and r? <br></div><div><br></div><div>Y= +es, correct, every private key d adds a 2^248 wide interval (actually two 2= +^247 wide intervals) of possible transaction hash values z, these=20 +intervals + +can have no overlap (meaning only one of the signature will ever be short),= + or can overlap and in that case the both signatures will be short only if = +the transaction hash is at this overlapping region.</div><div><br></div><di= +v>>=20 +Could this scheme be saved by the fact that z need not be the same for=20 +each signature? For instance by using SIGHASH flags to re-randomize z=20 +for each signature. Wouldn't that restore independence?<span><br></span= +></div><div><span><br></span></div><div><span>So there are 6 possible sigha= +sh flags, but SIGHASH_NONE | ANYONECANPAY don't provide any security as= + it can be re-used by the attacker (as attacker can just add its own output= +), also SIGHASH_NONE only helps with security if the transaction's 2nd = +input is a keyspend (p2pkh, p2wpkh, p2tr) and uses SIGHASH_ALL, otherwise a= +ttacker is able to just re-use that signature as well, so at best we can ha= +ve 5 different sighashes that contribute to the security. This makes the sc= +heme somewhat better - </span>if you use 256 private keys (such that they c= +ollectively span the full space of the finite field), you can be sure that = +for the same z only 1 of them will ever be short, so if you require 6 of th= +em to be short the only way for that to happen is that the 6 signatures use= + different SIGHASH and therefore use different z. I think this improves the= + security somewhat, signer will produce 6 short signatures with different s= +ighashes (maybe he needs to do a bit of grinding, but really little, like 1= +-5 iterations), the attacker would then have to construct a transaction suc= +h that 5 different signatures (under different sighash) would need to have = +the same position as when the signer generated them (only 5 because attacke= +r can re-use the=20 +<span>SIGHASH_NONE | ANYONECANPAY signature</span>), the probability of tha= +t happening is something around 1/2^40, so this means 2^40 more work for th= +e attacker. This still scales with the number of public keys, such that the= + probability of an attacker finding the valid solution is (1/{number of key= +s})^5. For reasonable security (e.g. 80-bit) we would need 2^16 public keys= +, which doesn't actually sound super crazy, but is still too much for b= +itcoin.<br></div><div><br></div><div>>=20 +How much harder is this?=C2=A0Couldn't the locking script secretly comm= +it to a + large number of public keys where some subset is opened by the spender. + Thus, generate=C2=A0z to provide a signature with sufficient=C2=A0numbers = +of=20 +small size signatures to prevent brute force? That is, commit to say=20 +1024 public keys and then only reveal 64 public key=C2=A0commitments to giv= +e=20 +the party who knows preimages of the public keys an advantage? <br></div><d= +iv><br></div><div>This would only help if you could create a vector commitm= +ent of the public keys (e.g. merkle tree), such that you can then only reve= +al some of them (based on my previous paragraph, you just need to reveal 6 = +public keys & signatures), and for the commitment to not blow up the sc= +ript size. Committing to 1024 public keys by hash +(or even use 1024 raw public keys) + + is out of the question because the p2wsh script size is limited to 10kB.</= +div><div><br></div><div>On a different note... I also started thinking abou= +t this in the context of PoW locked outputs. It turns out you can fine-tune= + the mining difficulty by just using 2 private keys, and making sure their = +possible transaction hash <i>z</i> intervals overlap in such a way that it = +creates an interval of fixed width, the PoW is then just about making sure = +the transaction hash lands into this interval - so actually no modular arit= +hmetic needed, it is purely double-SHA256 hashing of the transaction and ch= +ecking if the value is within the interval.</div><div><br></div><div>Cheers= +,</div><div>Adam<br></div></div><br><div class=3D"gmail_quote"><div dir=3D"= +ltr" class=3D"gmail_attr">On Tue, 24 Sept 2024 at 23:08, Ethan Heilman <= +<a href data-email-masked rel=3D"nofollow">eth...@gmail.com</a>> wrote:<= +br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e= +x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"= +>Thanks=C2=A0for looking into this and writing this up. It is very exciting= + to see someone look into this deeper.<br><br>Do I understand correctly tha= +t you are saying that the size of each signature from a set of signatures i= +s not independently sampled as long as all the signatures use the same z an= +d r?<br><br>Could this scheme be saved by the fact that z need not be the s= +ame for each signature? For instance by using SIGHASH flags to re-randomize= + z for each signature. Wouldn't that restore independence?<br><br>>= +=C2=A0 + +You can increase the number of private keys & let the intervals overlap= + (and then use the intersection of any 2 adjacent private key intervals by = +requiring 2 short signatures), but this will just make it much harder to pr= +oduce a signature (as the z value will now have to land at the intersection= + of the intervals)<br><br>How much harder is this?=C2=A0Couldn't the lo= +cking script secretly commit to a large number of public keys where some su= +bset is opened by the spender. Thus, generate=C2=A0z to provide a signature= + with sufficient=C2=A0numbers of small size signatures to prevent brute for= +ce? That is, commit to say 1024 public keys and then only reveal 64 public = +key=C2=A0commitments to give the party who knows preimages of the public ke= +ys an advantage?<br><br><br><br><br><br><br></div><br><div class=3D"gmail_q= +uote"><div dir=3D"ltr" class=3D"gmail_attr">On Mon, Sep 23, 2024 at 5:37=E2= +=80=AFPM Adam Borcany <<a href data-email-masked rel=3D"nofollow">adamb.= +..@gmail.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" styl= +e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin= +g-left:1ex"><div>Hello Ethan,<br> +</div><div><br></div><div>> 3. We have modeled ECDSA s-values signatures= + being uniformly drawn from=20 +2^256. It seems unlikely to me that the Elliptic Curve math lines up=20 +perfectly with a 256 bit space especially for a fixed r-value that has=20 +special mathematical properties. + +</div><div><br></div><div>I've been looking into this more deeply, and = +it would seem like it's not random at all, let me explain the intuition= +...</div><div>If we take the signing equation for the <i>s</i> value:</div>= +<div>s =3D k^-1*(z+rd) mod n<br></div><div>Considering that <i>k</i> is fix= +ed and is set to 1/2 we get:</div><div>s =3D 2*(z+rd) mod n<br></div><div>W= +e can let <i>x </i>=3D <i>rd</i> being a constant, since <i>r</i> is fixed = +(because <i>k</i> is fixed) and <i>d</i> is fixed at contract creation time= +:</div><div>s =3D 2*(z+x) mod n<br></div><div>Now for the size of the signa= +ture to be 59 or less, the <i>s</i> value needs to be smaller than 2^248, b= +ut since inequality isn't defined over finite fields, we can create a s= +et of all the integers 0..2^248 and then see if the s value is contained in= + this set:</div><div>s<span><span> =E2=88=88</span></span> <span><span>{</s= +pan></span><span><span>i</span></span> +<span><span>=E2=88=88</span></span> Z + +<span><span> | i</span></span><span><span> < 2^248}</span></span> + +</div><div> +2*(z+x) <span><span>=E2=88=88</span></span> <span><span>{</span></span><spa= +n><span>i</span></span> +<span><span>=E2=88=88</span></span> + +Z<span><span> | i < 2^248}</span></span> + +</div><div>We now can divide the whole condition by 2:</div><div>(z+x) <spa= +n><span>=E2=88=88</span></span> <span><span>{i/2 </span></span>|<span><span= +> i < 2^248}</span></span></div><div><span><span>Which we can write as (= +keep in mind i/2 is division in the finite field):</span></span> + + + +</div><div> +(z+x) <span><span>=E2=88=88</span></span> <span><span>{i</span></span> +<span><span>=E2=88=88</span></span> + +Z<span><span></span></span> + +<span><span> | i</span></span><span><span> < 2^247}</span></span> +<span>=E2=88=AA</span> +<span><span>{i</span></span> +<span><span>=E2=88=88</span></span> + +Z<span><span></span></span> + +<span><span> | n div 2 + 1 </span></span><span><span><span><span>=E2=89=A4<= +/span></span></span></span> <span><span>i</span></span><span><span> < n = +div 2 + 1 + 2^247}, where div is integer division<br></span></span></div><d= +iv><span><span>By then subtracting <i>x</i> from both sides we finally get:= +<br>z </span></span> +<span><span>=E2=88=88</span></span> <span><span>{i - x mod n</span></span><= +span><span></span></span> + +<span><span> |=C2=A0</span></span><span><span>i</span></span><span><span> &= +lt; 2^247</span></span><span><span>}</span></span> +<span>=E2=88=AA</span> +<span><span>{i</span></span> - x mod n<span><span></span></span> + +<span><span> | n div 2 + 1 </span></span><span><span><span><span>=E2=89=A4<= +/span></span></span></span> + +<span><span> i</span></span><span><span> < n div 2 + 1 + 2^247}</span></= +span></div><div><span><span>Which can be also be represented on the finite = +field circle & it helps with the intuition:</span></span></div><div><sp= +an><span><img alt=3D"ecdsa-opsize-lamport.png" width=3D"561px" height=3D"50= +1px" src=3D"https://groups.google.com/group/bitcoindev/attach/1e951c985dad/= +ecdsa-opsize-lamport.png?part=3D0.1&view=3D1"><br></span></span></div><= +div><span><span>Here <i>x </i>is set to 0 for simplicity.<br></span></span>= +</div><div><span><span><br></span></span> </div><div>What this shows is tha= +t the signature size being 59 or less depends on the transaction hash <i>z<= +/i> (technically <i>z</i> is just left-most bits of the transaction hash) b= +eing in the specified intervals (depending on the choice of <i>x</i>, which= + in turn depends on the choice of <i>d</i>), it is also important to note t= +hat the interval is always of the size 2^248 (or actually 2 intervals each = +2^247 elements), with x offsetting the intervals from <i>0</i> and <i>n div= + 2 -1</i> respectively. So while we can say that there is a 1/256 chance th= +at a signature will be short for one private key=20 +(because the intervals cover 1/256 of the circle), we cannot say that the s= +ize of other signatures under other private keys also has the same independ= +ent chance of being short (it might have 0% chance if the intervals don'= +;t overlap). So for multiple private keys to generate short signatures over= + the same message, they need to correspond to the overlapping intervals.</d= +iv><div><br></div><div>I think this breaks the whole construction, because = +you can partition the finite field into 256 non-overlapping intervals, corr= +esponding to 256 private keys, such that only one of these private keys wil= +l produce a short signature for any given message. You can increase the num= +ber of private keys & let the intervals overlap (and then use the inter= +section of any 2 adjacent private key intervals by requiring 2 short signat= +ures), but this will just make it much harder to produce a signature (as th= +e z value will now have to land at the intersection of the intervals). In t= +he end the work of the attacker is just 256 times harder than the work of t= +he signer. The number 256 is stemming from the fact that we use 256 private= + keys, and is purely dependent on the number of private keys, so if we use = +e.g. 512 private keys the attacker will need to grind 512 times more messag= +es than the signer to find a valid one - so this is insecure for any reason= +able number of private keys.</div><div><br></div><div>Cheers,</div><div>Ada= +m<br></div> + +<p></p> + +-- <br> +You received this message because you are subscribed to the Google Groups &= +quot;Bitcoin Development Mailing List" group.<br> +To unsubscribe from this group and stop receiving emails from it, send an e= +mail to <a href data-email-masked rel=3D"nofollow">bitcoindev+...@googlegro= +ups.com</a>.<br> +To view this discussion on the web visit <a href=3D"https://groups.google.c= +om/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917ef03ffn%40googlegroups.= +com?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank" rel=3D"no= +follow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&q=3D= +https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-bb2917= +ef03ffn%2540googlegroups.com?utm_medium%3Demail%26utm_source%3Dfooter&s= +ource=3Dgmail&ust=3D1729901859852000&usg=3DAOvVaw23-EgjHD54ijIGwaqH= +uv6m">https://groups.google.com/d/msgid/bitcoindev/91ba7058-776d-4ff0-a179-= +bb2917ef03ffn%40googlegroups.com</a>.<br> +</blockquote></div> +</blockquote></div> +</blockquote></div></div> +</blockquote></div> + +<p></p> + +-- <br /> +You received this message because you are subscribed to the Google Groups &= +quot;Bitcoin Development Mailing List" group.<br /> +To unsubscribe from this group and stop receiving emails from it, send an e= +mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind= +ev+unsubscribe@googlegroups.com</a>.<br /> +To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/= +bitcoindev/864868fb-164b-4d64-8c01-f496480c26e4n%40googlegroups.com?utm_med= +ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind= +ev/864868fb-164b-4d64-8c01-f496480c26e4n%40googlegroups.com</a>.<br /> + +------=_Part_27805_838118986.1729815654787-- + +------=_Part_27804_138313945.1729815654787-- + |