Delivery-date: Wed, 01 Oct 2025 18:49:30 -0700 Received: from mail-oi1-f183.google.com ([209.85.167.183]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1v48Rl-0005Qj-PT for bitcoindev@gnusha.org; Wed, 01 Oct 2025 18:49:30 -0700 Received: by mail-oi1-f183.google.com with SMTP id 5614622812f47-43f46ed8db5sf635436b6e.0 for ; Wed, 01 Oct 2025 18:49:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1759369764; x=1759974564; 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=9QSS27BZ3x2eNTf9Xa5EvQxJ2wot8ylyFaIPqy4hUaM=; b=i52nZZY83GS5Dt3nrl62qrToLMFTHDkOmK5uXjDFBlguUPxAFE76t3mSjlOHIhUB+g MHvhZo4PrhA5I1dJk8RNhoLRvrV8C/chDXhFVi/VdrYzazQuBe/E/nB88rsh/R+Nq74C tKbnpSrezbGWEGcwBoVM3HdLjpqT+6Ek8AqH0VG2q64PtDm69K8uWHbuxXnxwJqRvKzF EqeqO4VGmDxIAuL6vuAXHN8Gxjb5N1Atx5zGFRJBBXyqyvTrp2Xuc/oAVY9xxx0HfOAK lBF67d6oAkvcE//RQ75Muvg4BK0daf0UrgdiW5c8kNwTDSgqrsG2lAiGpqkupFfSlluA XKsw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1759369764; x=1759974564; 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=9QSS27BZ3x2eNTf9Xa5EvQxJ2wot8ylyFaIPqy4hUaM=; b=NEUk1UpDQnw6Kcs1DcTg06M+D7j0eKuKEuCs9jv8a0DV0UWO16SR8Y1hdrSUBg+xw1 59zcXNIG1UspYd66D4ZfwXE8gjcvMvGu6yNVEEeAudmKfL1fJumI/tGiqlZPk/LgIIMQ metsZMTNQIu99NcZWt/jNA2VSCRsEzmSnPfmRUrxBWtmoAn2hUFz88augLJralwqIAcx IAT4Ac+/ovVMypIKbsuBDfRLzsqn3FvQ+p8Qp2Vuk3IPEDavB7yVvl9KJX8+jwGSYSEl H+QPWHmgbzixVTEx2yRtXWdgAzDTb/Lcd5YgLGoeEDLUFXFbLsRo6TJUQ+rcnfIs9dWf qxRQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1759369764; x=1759974564; 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=9QSS27BZ3x2eNTf9Xa5EvQxJ2wot8ylyFaIPqy4hUaM=; b=f976WdTma9dKv6qK+5Z4DSM+b1TpBX/cdRi+VSkkCczXbCzXzNV4B1LW43iZMmEZdY 6r6Q2YOLfhFSMNEuRNpaAuf6k/W6cKkgyEacD1WG38z3akiMlQGzIPihqqD3l2kDmp/w 0twGrI3UJ6q7iB3K3EuGW6/MPFxQnrWQ2Y+WPaBc2tdjvuKRAnqWMiQOgA2Dmp8DRA3J WnJ3V9yB/ZnBZnmvfMeMUv62kXbNxHf4LbaaqK7bBMU2IDHjCt3mmL/5IVlmyTkmhAt4 ZlFlu8ToxAl0z50Dbm3RhYgBVRFEdzmv6JC00vxx1NZg4STpQBplZHFy5PvDt8lWSp1d ArZA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCW4W2/bAsXkVgm/RGv5DdRySCqPySnQLSh9b9kT+w5JZ0FyGP9UQplOz2iaFpLJDh20tG9TX23p7AvQ@gnusha.org X-Gm-Message-State: AOJu0Yyw+0RE8OLlvDDvjkQUVdsdzgO8CoPapmPbLtiObmEdAZ/0+KNp icFlx4gZqmPuH6yAreIuvsboSGscLosg5omFfcQJf5UlIlp5kND87P1l X-Google-Smtp-Source: AGHT+IFAGw6ucZZ0EhQIClSMS5f7AD67Qevq+C9Knrmto4inLVowhySPtK0FIYXA+ZHbBmtXNVqeyg== X-Received: by 2002:a05:6808:6909:b0:43f:95b5:66e with SMTP id 5614622812f47-43fa40c00a9mr3110660b6e.14.1759369763536; Wed, 01 Oct 2025 18:49:23 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="ARHlJd5lJV/ANOfUKzy8ezjm6evXt0Y1a8F9bYk492wyu2xD1Q==" Received: by 2002:a05:6871:69b3:b0:383:97ca:d48c with SMTP id 586e51a60fabf-3abe8b6360als162492fac.0.-pod-prod-04-us; Wed, 01 Oct 2025 18:49:19 -0700 (PDT) X-Received: by 2002:a05:6808:4f28:b0:43f:71b6:79e8 with SMTP id 5614622812f47-43fa40496edmr3179855b6e.11.1759369759124; Wed, 01 Oct 2025 18:49:19 -0700 (PDT) Received: by 2002:a05:690c:62c4:b0:720:768:1935 with SMTP id 00721157ae682-77f6fbf5cc4ms7b3; Wed, 1 Oct 2025 17:25:40 -0700 (PDT) X-Received: by 2002:a53:8504:0:b0:636:1a27:6aba with SMTP id 956f58d0204a3-63b6ff07c1emr6039078d50.12.1759364739334; Wed, 01 Oct 2025 17:25:39 -0700 (PDT) Date: Wed, 1 Oct 2025 17:25:38 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <2e366b25-f789-4c9d-acf9-b87149d6a796n@googlegroups.com> In-Reply-To: References: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com> Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_136226_1627650848.1759364738949" X-Original-Sender: ekaggata@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_136226_1627650848.1759364738949 Content-Type: multipart/alternative; boundary="----=_Part_136227_1150335168.1759364738949" ------=_Part_136227_1150335168.1759364738949 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Greg, Andrew, list, Answers to Greg then Andrew: > E.g. 2 of 2 with leaked key and a secure one. That's a very good point! I was narrowly focused on the signature scheme,= =20 but Bitcoin is more than a signature scheme! > But is it even really worth the analysis when grinding gets you a 12%= =20 embedding rate in that signature at not that significant cost? (because you= =20 can independently grind the nonce and signature itself, or nonce and=20 pubkey) -- and when beyond the cost of the additional signature (making the= =20 output 3x its cost) requiring signing when forming the address completely= =20 kills public derivation, multisig with cold keys. etc? ... and then any of= =20 whatever spam concerns people have would likely be exacerbated by the=20 spammers using more resources due to the embedding rate? I certainly don't think it's worth *doing* (hence my use of the term=20 "appalling idea" :) ), as per the things you mention there. I wrote the document as a mostly academic investigation. It would be nice= =20 to be surer what the limits are, although I suspect we're all reasonably=20 confident of what is/isn't possible. > 12% embedding rate Where do you get that number from? 33% for embedding 256 bits in (P, R, s)= =20 (but as per this discussion, according to me, at the cost of key leakage).= =20 If we include the other bytes in a (taproot anyway) utxo that's not much=20 less, I guess 30% ish. I could try to guess but it'd be easier if you told= =20 me :) to Andrew: > As for waxwing's original question -- I also intuitively believe that the only way to embed data in a Schnorr signature is by grinding or revealing your key ... and I'm not convinced you can do it even by revealing your key. (R is an EC point that you can't force to be any particular value except by making a NUMS point, which you then can't use to sign; and s =3D k + ex where e is a hash of kG (among other things) so I don't think you can force that value at all.) Ah, I see what you're saying, it's a subtly different target. ECDSA allows= =20 that s be controlled, Schnorr doesn't, but I set up the game as "adversary= =20 must be able to publish a function f such that f(any published R, s, (e)) = =3D=20 data", i.e. not just f =3D identity function. That was why I wrote in the= =20 introduction (copied here for convenience:) "Data can effectively be embedded in signatures by using a publically- inferrable nonce, as was noted \href{https://groups.google.com/g/bitcoindev /c/d6ZO7gXGYbQ/m/Y8BfxMVxAAAJ}{here} and was later fleshed out in detail=20 \href{https://blog.bitmex.com/the-unstoppable-jpg-in-private-keys/}{here} ( \textbf{note}: both these sources discuss nonce-reuse but it's worse than= =20 that: any \emph{publically inferrable} nonce can achieve the same thing,=20 such as, the block hash of the parent block; this will have the same=20 embedding rate and cannot be disallowed)." It may be a different target "politically" :) but I was only thinking=20 technically, in terms of how people might end up using outputs. From a=20 technical point of view it makes no difference if f is the identity or=20 something more complex (as long as it's efficiently computable). Cheers, AdamISZ/waxwing On Wednesday, October 1, 2025 at 8:20:25=E2=80=AFPM UTC-3 Andrew Poelstra w= rote: > On Wed, Oct 01, 2025 at 10:10:16PM +0000, Greg Maxwell wrote: > > Intuitively it sounds likely, -- just in that the available values are = a > > image on the curve and a value summed with a hash dependent on everythi= ng > > else. I think it would be hard to prove. > >=20 > > But is it even really worth the analysis when grinding gets you a 12% > > embedding rate in that signature at not that significant cost? (because= =20 > you > > can independently grind the nonce and signature itself, or nonce and > > pubkey) -- and when beyond the cost of the additional signature (making= =20 > the > > output 3x its cost) requiring signing when forming the address complete= ly > > kills public derivation, multisig with cold keys. etc? ... and then any= =20 > of > > whatever spam concerns people have would likely be exacerbated by the > > spammers using more resources due to the embedding rate? > > > > Some time ago, I talked to Ethan Heilman about this in the context of PQ > signatures, and he made the interesting point that you can think of > 12% embedding rate as representing an 8x discount for real signatures vs > embedded data. And that maybe that's okay, incentive-wise. > > Needing to grind out portions of 32-byte blocks probably also reduces > the risk from people trying to embed virus signatures or other malicious > data. > > As for waxwing's original question -- I also intuitively believe that > the only way to embed data in a Schnorr signature is by grinding or > revealing your key ... and I'm not convinced you can do it even by > revealing your key. (R is an EC point that you can't force to be any > particular value except by making a NUMS point, which you then can't use > to sign; and s =3D k + ex where e is a hash of kG (among other things) > so I don't think you can force that value at all.) > > --=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 visit https://groups.google.com/d/msgid/bitcoindev/= 2e366b25-f789-4c9d-acf9-b87149d6a796n%40googlegroups.com. ------=_Part_136227_1150335168.1759364738949 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Greg, Andrew, list,

Answers to Greg then Andrew:

> E.g. 2 of 2 with leaked key and a secure= one.

That's a very good point! I was narrowly f= ocused on the signature scheme, but Bitcoin is more than a signature scheme= !

>=C2=A0=C2=A0=C2=A0But is it even really worth t= he analysis when grinding gets you a 12% embedding rate in that signature a= t not that significant cost? (because you can independently grind the nonce= and signature itself, or nonce and pubkey) -- and when beyond the cost of = the additional signature (making the output 3x its cost) requiring signing = when forming the address completely kills public derivation, multisig with = cold keys. etc?=C2=A0 ... and then any of whatever spam concerns people hav= e would likely be exacerbated by the spammers using more resources due to t= he embedding rate?

I certainly don't think it's worth = *doing* (hence my use of the term "appalling idea" :) ), as per the things = you mention there.

I wrote the document as a mos= tly academic investigation. It would be nice to be surer what the limits ar= e, although I suspect we're all reasonably confident of what is/isn't possi= ble.

>=C2=A0=C2=A012% embedding rate
Where do you get that number from? 33% for embedding 256 bits in (P, R, s= ) (but as per this discussion, according to me, at the cost of key leakage)= . If we include the other bytes in a (taproot anyway) utxo that's not much = less, I guess 30% ish. I could try to guess=C2=A0but it'd be easier if you = told me :)

to Andrew:

> As for waxwing's original question -- I also intuitively believe that=
the only way to embed data in a Schnorr signature is by grinding orrevealing your key ... and I'm not convinced you can do it even by
revealing your key. (R is an EC point that you can't force to be any
= particular value except by making a NUMS point, which you then can't useto sign; and s =3D k + ex where e is a hash of kG (among other things)so I don't think you can force that value at all.)

Ah, I see what you're saying, it's a subtly different target. = ECDSA allows that s be controlled, Schnorr doesn't, but I set up the game a= s "adversary must be able to publish a function f such that f(any published= R, s, (e)) =3D data", i.e. not just f =3D identity function. That was why = I wrote in the introduction (copied here for convenience:)

=
"Data can effectively be em= bedded in signatures by using a pu= blically-inferrable n= once, as was noted \href{https://groups.google.com/g/bitcoindev<= /span>/c/d6ZO7gXGYbQ/m/Y8BfxMVxAAAJ}{here} and was later fleshed out in detail \href{https://blog.bitmex.com/the-= unstoppable-jpg-in-private-keys/}{here} (\textbf{= note}: both these sources discuss nonce-reuse but it's worse than that: any= \emph{publically inferrable} nonce can = achieve the same thing, such as, the block hash of the parent block; this w= ill have the same embedding rate and cannot be disallowed)."

It may be a different target "politically" :) but= I was only thinking technically, in terms of how people might end up using= outputs. From a technical point of view it makes no difference if f is the= identity or something more complex (as long as it's efficiently computable= ).

Cheers,
AdamISZ/waxwing
On Wednesday, October 1, 2= 025 at 8:20:25=E2=80=AFPM UTC-3 Andrew Poelstra wrote:
On Wed, Oct 01, 2025 at 10:10:16P= M +0000, Greg Maxwell wrote:
> Intuitively it sounds likely, -- just in that the available values= are a
> image on the curve and a value summed with a hash dependent on eve= rything
> else. I think it would be hard to prove.
>=20
> But is it even really worth the analysis when grinding gets you a = 12%
> embedding rate in that signature at not that significant cost? (be= cause you
> can independently grind the nonce and signature itself, or nonce a= nd
> pubkey) -- and when beyond the cost of the additional signature (m= aking the
> output 3x its cost) requiring signing when forming the address com= pletely
> kills public derivation, multisig with cold keys. etc? ... and th= en any of
> whatever spam concerns people have would likely be exacerbated by = the
> spammers using more resources due to the embedding rate?
>

Some time ago, I talked to Ethan Heilman about this in the context of P= Q
signatures, and he made the interesting point that you can think of
12% embedding rate as representing an 8x discount for real signatures v= s
embedded data. And that maybe that's okay, incentive-wise.

Needing to grind out portions of 32-byte blocks probably also reduces
the risk from people trying to embed virus signatures or other maliciou= s
data.

As for waxwing's original question -- I also intuitively believe th= at
the only way to embed data in a Schnorr signature is by grinding or
revealing your key ... and I'm not convinced you can do it even by
revealing your key. (R is an EC point that you can't force to be an= y
particular value except by making a NUMS point, which you then can'= t use
to sign; and s =3D k + ex where e is a hash of kG (among other things)
so I don't think you can force that value at all.)

--=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 visit https://groups.google.com/d/msgid/bitcoind= ev/2e366b25-f789-4c9d-acf9-b87149d6a796n%40googlegroups.com.
------=_Part_136227_1150335168.1759364738949-- ------=_Part_136226_1627650848.1759364738949--