From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: In-Reply-To: References: 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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
I think it is possible to get past the 201 op code limit doing it in t= apscript. 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= ted. 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.

Best,
benthecarman
=
On Tuesday, April 30, 2024 at 9:22:54=E2=80=AFAM UTC-5 Andrew Poelstra w= rote:
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 o= f 2^72
> computations, it would provide the attacker some advantage.
>=20
> If we are assuming discrete log is still hard, why do we need Lamp= ort
> 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 o= n
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 yo= u 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.wpsoftwar= e.net/andrew

The sun is always shining in space
-Justin Lewis-Webster

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msg= id/bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com.=
------=_Part_85990_406851706.1715214678205-- ------=_Part_85989_269653429.1715214678205--