diff options
| author | Ben Carman <benthecarman1@gmail.com> | 2024-05-08 17:31:18 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@googlegroups.com> | 2024-05-08 17:37:26 -0700 |
| commit | fd1a585d27ba0676f9adf89007ed56fc52b1f637 (patch) | |
| tree | c83897e6c69fdc91707b3ac48c579ca6193089e7 | |
| parent | bd7081fe762a03c594d648e6043d658176f7bd19 (diff) | |
| download | pi-bitcoindev-fd1a585d27ba0676f9adf89007ed56fc52b1f637.tar.gz pi-bitcoindev-fd1a585d27ba0676f9adf89007ed56fc52b1f637.zip | |
Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)
| -rw-r--r-- | 33/b7fae9f77b7dca9318b6c094dfe56d9ab4b4e4 | 255 |
1 files changed, 255 insertions, 0 deletions
diff --git a/33/b7fae9f77b7dca9318b6c094dfe56d9ab4b4e4 b/33/b7fae9f77b7dca9318b6c094dfe56d9ab4b4e4 new file mode 100644 index 000000000..c03e76a28 --- /dev/null +++ b/33/b7fae9f77b7dca9318b6c094dfe56d9ab4b4e4 @@ -0,0 +1,255 @@ +Delivery-date: Wed, 08 May 2024 17:37:26 -0700 +Received: from mail-yb1-f185.google.com ([209.85.219.185]) + by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 + (Exim 4.94.2) + (envelope-from <bitcoindev+bncBDAOTO4QXEFBBPVV6CYQMGQESI5DXTA@googlegroups.com>) + id 1s4rmo-0001d3-2R + for bitcoindev@gnusha.org; Wed, 08 May 2024 17:37:26 -0700 +Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-de468af2b73sf622041276.0 + for <bitcoindev@gnusha.org>; Wed, 08 May 2024 17:37:25 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=googlegroups.com; s=20230601; t=1715215039; x=1715819839; 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=kti8PQ1sH0PD5vZh1UeacUZlgebA3UoNsfs3+kVOvFI=; + b=SOmARHTKYXkIHJ8sQbcED9bvmO1LExQfXWOfN+wKBktE7FqXu9v+Og2Bhs+t1bXPB/ + 9JYyi/1Ts5V8sAD0Mq2c+sD3/bz5qtsrhwR550yGjft8ANC1EZNYdBFToMOZr57A4UUA + 9Y/+9Pk6ZvQCe5wXBd3GQ7PzBU3tfz72kDRAdvbFSNO4zbv0mtewiLY6ifY7iHUXjnQv + sJ8ZO8A9f3UZBtBi+JZrISxR9BbO00YKwOQDUTRY2PhJxMBuz8sPN0EixAwBT0wxZhqK + yRd8BHVemJHyORZf5O6qddS0Q0XEgfGjJoDe7CkLnx1911AMw4jCw92QhvROu/f4pLJh + g81A== +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=gmail.com; s=20230601; t=1715215039; x=1715819839; 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=kti8PQ1sH0PD5vZh1UeacUZlgebA3UoNsfs3+kVOvFI=; + b=JKYzj3J+sMMwuAAkaY/jHyQZ6RqlXBoKBZCBHDShqylLxRgw+GAHW23Y4/GiDeETW4 + MZlknjng67tajJiCKI8SQMrfov+AqtAhwMLfinIGjIypMnObrC54viR7x1fDI+5+bhpF + I7XRToGknWLDERYoCDu0orgiyBX67Fp3/fdTJ8ow3dmKMjNIJWEq9tZc8bpLFTk+N7TB + EQw1aX4L6ZR6HxIKlA17WxuUP9QJYKwcoMQkeaZOaosQDBqIBZDo6//oCClXgpmcgiVw + jftoERy38suYUnfxM5qZX83igdbFaHEzdFZI8L4z7o5+RHzqh901YexVHA6ZuwGDaLAh + WgJg== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20230601; t=1715215039; x=1715819839; + 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=kti8PQ1sH0PD5vZh1UeacUZlgebA3UoNsfs3+kVOvFI=; + b=Z0rGERyOg4L5s7y8tC666fj091jyh2MSfUweDYgnabfeUu3fbePVh/a6G1O1/q6mAQ + SgT78ATmsum3OtmCsimhyOw43BSTSmQdySDBd655IOfwnJbNKdZYLvCPLd/qYEgS1rOF + 9MS23jerAt3z3Pk6C+Sni35d3wdxM5oszJY+yAEjJVa2BNX1RIOuVZQE0mFXYT94IRyw + 0mLpMNAz3bsIHAAep4J4fYBMd2JS7H6l8BdbyYOVaI/40eEjHIyDafekfeFWg/8ZW6jO + BIQEN7iVYf7A6bGwet33V65C34C2BuVBGbaCyWh/qFm6SIj2GpSH4hqxAUBsRc+HiXwu + Uw+g== +Sender: bitcoindev@googlegroups.com +X-Forwarded-Encrypted: i=1; AJvYcCV0ooCdMO392dCNVvXlU4tqR/vDiSzzYnRp10PhjLXJwiahY2mKw7JEE6UKyrDaMo9EBgtHjP7Yep6sMbfSdd/PYZKN8qU= +X-Gm-Message-State: AOJu0Yz+6nxs2gYDvEF3kscreLXZtNZY++CyBF1n2jNOjRzl4h4cx0zU + Ztf0nMJ5f2ujQzvHigxA1IuPqrryVyIBKzndw93CJZa7bf3A8oV/ +X-Google-Smtp-Source: AGHT+IGk6e3Oh9eIZ57wWxvcEdrXmn3hAMx9WsiH6RrmCzEbXDhQs6xr9Q8sddToq65Ztkds4hxZMw== +X-Received: by 2002:a25:cec7:0:b0:de6:17aa:e711 with SMTP id 3f1490d57ef6-debb9cde0d6mr5572260276.7.1715215039552; + Wed, 08 May 2024 17:37:19 -0700 (PDT) +X-BeenThere: bitcoindev@googlegroups.com +Received: by 2002:a25:ad45:0:b0:de5:a88f:94bd with SMTP id 3f1490d57ef6-debd087c4afls530768276.1.-pod-prod-08-us; + Wed, 08 May 2024 17:37:17 -0700 (PDT) +X-Received: by 2002:a25:9e11:0:b0:de5:1b63:9ee5 with SMTP id 3f1490d57ef6-debb9da66d2mr1211632276.7.1715215037830; + Wed, 08 May 2024 17:37:17 -0700 (PDT) +Received: by 2002:a05:690c:dcf:b0:620:26bb:319f with SMTP id 00721157ae682-62086722468ms7b3; + Wed, 8 May 2024 17:31:19 -0700 (PDT) +X-Received: by 2002:a0d:e2cb:0:b0:61a:f3ea:3994 with SMTP id 00721157ae682-620993b8121mr3099657b3.3.1715214678624; + Wed, 08 May 2024 17:31:18 -0700 (PDT) +Date: Wed, 8 May 2024 17:31:18 -0700 (PDT) +From: Ben Carman <benthecarman1@gmail.com> +To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> +Message-Id: <b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n@googlegroups.com> +In-Reply-To: <ZjD-dMMGxoGNgzIg@camus> +References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com> + <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com> + <ZjD-dMMGxoGNgzIg@camus> +Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport + Signatures (no changes needed) +MIME-Version: 1.0 +Content-Type: multipart/mixed; + boundary="----=_Part_85989_269653429.1715214678205" +X-Original-Sender: benthecarman1@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: -0.5 (/) + +------=_Part_85989_269653429.1715214678205 +Content-Type: multipart/alternative; + boundary="----=_Part_85990_406851706.1715214678205" + +------=_Part_85990_406851706.1715214678205 +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +I think it is possible to get past the 201 op code limit doing it in=20 +tapscript. I don't think it would have the same quantum security but could= +=20 +maybe be a path to covenants. My understanding is that you're using the=20 +OP_SIZE of the sig to basically decide to verify if the bit is a 0 or a 1,= +=20 +then do that verification. You could do the same trick with schnorr sigs,= +=20 +just for 0 bits don't include the sighash_all flag, and for 1 bits include= +=20 +it. This would allow you to get around all the resource limits that taproot= +=20 +lifted. This still should be safe since the the signature commits to if it= +=20 +is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable very= +=20 +complex things or just let you do it on 1 bit of information in tapscript. + +Best, +benthecarman + +On Tuesday, April 30, 2024 at 9:22:54=E2=80=AFAM UTC-5 Andrew Poelstra wrot= +e: + +> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote: +> > > if an attacker managed to grind a 23-byte r-value at a cost of 2^72 +> > computations, it would provide the attacker some advantage. +> >=20 +> > If we are assuming discrete log is still hard, why do we need Lamport +> > signatures at all? In a post-quantum world, finding k such that r is 21 +> > bytes or less is efficient for the attacker. +> > +> +> Aside from Ethan's point that a variant of this technique is still +> secure in the case that discrete log is totally broken (or even +> partially broken...all we need is that _somebody_ is able to find the +> discrete log of the x=3D1 point and for them to publish this). +> +> Another reason this is useful is that if you have a Lamport signature on +> the stack which is composed of SIZE values, all of which are small +> enough to be manipulated with the numeric script opcodes, then you can +> do covenants in Script. +> +> (Sadly(?), I think none of this works in the context of the 201-opcode +> limit...and absent BitVM challenge-response tricks it's unlikely you can +> do much in the context of the 4MWu block size limit..), but IMO it's a +> pretty big deal that size limits are now the only reason that Bitcoin +> doesn't have covenants.) +> +> --=20 +> Andrew Poelstra +> Director, Blockstream Research +> Email: apoelstra at wpsoftware.net +> Web: https://www.wpsoftware.net/andrew +> +> The sun is always shining in space +> -Justin Lewis-Webster +> +> + +--=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 on the web visit https://groups.google.com/d/msgid/= +bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com. + +------=_Part_85990_406851706.1715214678205 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div>I think it is possible to get past the 201 op code limit doing it in t= +apscript. <span style=3D"text-overflow: unset;">I don't think it would have= + the same quantum security but could maybe be a path to covenants. My unde= +rstanding is that you're using the OP_SIZE of the sig to basically decide t= +o verify if the bit is a 0 or a 1, then do that verification. You could do = +the same trick with schnorr sigs, just for 0 bits don't include the sighash= +_all flag, and for 1 bits include it. + +This would allow you to get around all the resource limits that taproot lif= +te</span>d. This still should be safe since the the signature commits to if= + it is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable ve= +ry complex things or just let you do it on 1 bit of information in tapscrip= +t.</div><div><br /></div><div>Best,</div><div>benthecarman<br /></div><div>= +<br /></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_att= +r">On Tuesday, April 30, 2024 at 9:22:54=E2=80=AFAM UTC-5 Andrew Poelstra w= +rote:<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;">On Tue,= + Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote: +<br>> > if an attacker managed to grind a 23-byte r-value at a cost o= +f 2^72 +<br>> computations, it would provide the attacker some advantage. +<br>>=20 +<br>> If we are assuming discrete log is still hard, why do we need Lamp= +ort +<br>> signatures at all? In a post-quantum world, finding k such that r = +is 21 +<br>> bytes or less is efficient for the attacker. +<br>> +<br> +<br>Aside from Ethan's point that a variant of this technique is still +<br>secure in the case that discrete log is totally broken (or even +<br>partially broken...all we need is that _somebody_ is able to find the +<br>discrete log of the x=3D1 point and for them to publish this). +<br> +<br>Another reason this is useful is that if you have a Lamport signature o= +n +<br>the stack which is composed of SIZE values, all of which are small +<br>enough to be manipulated with the numeric script opcodes, then you can +<br>do covenants in Script. +<br> +<br>(Sadly(?), I think none of this works in the context of the 201-opcode +<br>limit...and absent BitVM challenge-response tricks it's unlikely yo= +u can +<br>do much in the context of the 4MWu block size limit..), but IMO it'= +s a +<br>pretty big deal that size limits are now the only reason that Bitcoin +<br>doesn't have covenants.) +<br> +<br>--=20 +<br>Andrew Poelstra +<br>Director, Blockstream Research +<br>Email: apoelstra at <a href=3D"http://wpsoftware.net" target=3D"_blank"= + rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3De= +n&q=3Dhttp://wpsoftware.net&source=3Dgmail&ust=3D17153008146390= +00&usg=3DAOvVaw3wIDzlUj1wqXmVV4RyaQhz">wpsoftware.net</a> +<br>Web: <a href=3D"https://www.wpsoftware.net/andrew" target=3D"_blank" = +rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den= +&q=3Dhttps://www.wpsoftware.net/andrew&source=3Dgmail&ust=3D171= +5300814639000&usg=3DAOvVaw1ZlDWyULQOphaSgTZFgrBT">https://www.wpsoftwar= +e.net/andrew</a> +<br> +<br>The sun is always shining in space +<br> -Justin Lewis-Webster +<br> +<br></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 on the web visit <a href=3D"https://groups.google.c= +om/d/msgid/bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.= +com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg= +id/bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com</a>.= +<br /> + +------=_Part_85990_406851706.1715214678205-- + +------=_Part_85989_269653429.1715214678205-- + |