From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 07 Oct 2025 06:52:55 -0700 Received: from mail-oa1-f58.google.com ([209.85.160.58]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1v687a-0006nc-0L for bitcoindev@gnusha.org; Tue, 07 Oct 2025 06:52:55 -0700 Received: by mail-oa1-f58.google.com with SMTP id 586e51a60fabf-369f44847f0sf851509fac.3 for ; Tue, 07 Oct 2025 06:52:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1759845168; x=1760449968; 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=nLNNgpvjerhJVjDsIxPzXPqH0r8TtK1cFrppdJl0h7s=; b=kLpTgVpcO8b//fH9nwvdB8qmnxYbsbW2Co/ama9n9bVJBsG2CCPD+5NQloJkc9Me2H 7M4iLhUGY86aXH4bmNj9OZP0iJuCzdv4K4nlQ7HKkjI3LNLEZiJPTeQ8XIIG8ofO2pWM fyItxTcCunvcS5CRKbWuV8qL9ebTWQrWVrLBAqgNko0Ho8j6tgffOVcwyCjjU+eeTrPv f4M46gppeuOXOr0vPaLqgINTKvACpU8jywiFSRrtZjrJPUyR+vtCdXnHPkYQOXNGXUe1 8c/mY9PhWnzok53uaNaAn8t4Mi2WlQ36ovj9oQ5VnVi/CTWuPkI11qu90oIglTNRauiL HXKg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1759845168; x=1760449968; 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=nLNNgpvjerhJVjDsIxPzXPqH0r8TtK1cFrppdJl0h7s=; b=jK49qAq9xzcHz7HqAsakvZ/VatkzNumMNlwb/oC0+jEV1QfQaSzGAbl72zVWPD4l8i gJI4Y7Q+XjDMl6iSpA7bLoI7M9lYoyUfFEtpxlO2rlrQrJsyyGoOmwSuxqDeDItxTCEb rXsa1e+KgFB7BaXPBgyELhDeOdz7J9W0WdrcQfUSnzS5jr/j7vq5K7JnbdwADtlsdQpX aFfyLO1rz2nIW1u7wAas/oabERz3A3Nl3MWTB1CYKLhD1fBnldeLWgb3GnRUsNWqS12s hjnWCBvIcpR9MTtDFDqb+uKqR0MxIKj87F7YggLhais1nlCy/QERaQluctvyqS1J5iHI ahMg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1759845168; x=1760449968; 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=nLNNgpvjerhJVjDsIxPzXPqH0r8TtK1cFrppdJl0h7s=; b=wn26gG5HY1mYvZyTF6MWFuy08huSVFKI5UiNSXRt8W0kD+oXbBzRtX6PFAviYnJj4L nwhMGt8a/AvJiHp7JpW7TLIehoiXC4lu318j8XYxfy/EacEwzMu3L6AsIw9KE+XBV9pS IKNpIES70mVe88jOOC4WZLwZmRPYEz4nb2MP0OsYEVCENPSUXKaKpz7NIvGw/uHUybFk eu7VYntBVZOnS71JNF03rmpH9Pv1WrHL1GmLQvtbT+rQZNfcDnN9R4Jnze0IDjRQ/mEb HNmfvYkfqMv5IK4Q8YlsSpI9QUgIpOaJm9i+YYV/hIqkzIWMG+QHylAMhNgQfO9E0bRT olZQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCVMwBEtLFtp6qLuJ8GdjaDc/j88guJoOB8zCyYD75cltkgw81j/+y8AOBTWtXrmTHFPXW760KpntWx3@gnusha.org X-Gm-Message-State: AOJu0Yzxx5kE06yS5qatZXpKaVW0SnOG6ka1mQ1vKyglBKtxmRnoH7i5 rE9agW84pdAeaaldwfDa8l4ZQFuI9Id6IiTkzUQHIUzsaX5QY61CHESj X-Google-Smtp-Source: AGHT+IH9iL4S6qVvY8V1G71ldUpECMAnhFiNoGNZ/EIrl9frZFXt/wknlxdy2luwssx4BUPOrJRQ+A== X-Received: by 2002:a05:6870:88a6:b0:35c:2b51:3e0d with SMTP id 586e51a60fabf-3b0f3d2757fmr4133456fac.1.1759845167510; Tue, 07 Oct 2025 06:52:47 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="ARHlJd54lcrG13RTWzOEyzcozZ5c5lcl52fpNIBI/LMjlA3MBQ==" Received: by 2002:a05:6870:264:b0:344:f218:403d with SMTP id 586e51a60fabf-3abe79b33c2ls3983895fac.0.-pod-prod-03-us; Tue, 07 Oct 2025 06:52:42 -0700 (PDT) X-Received: by 2002:a05:6808:f15:b0:43f:3d56:4dca with SMTP id 5614622812f47-43fc18c1e30mr7444309b6e.50.1759845162558; Tue, 07 Oct 2025 06:52:42 -0700 (PDT) Received: by 2002:a05:690c:f0f:b0:741:b7fe:46f4 with SMTP id 00721157ae682-77f94127abcms7b3; Tue, 7 Oct 2025 05:05:25 -0700 (PDT) X-Received: by 2002:a05:690c:fcd:b0:76f:715a:3d1d with SMTP id 00721157ae682-77f946a1b5amr199325907b3.43.1759838724407; Tue, 07 Oct 2025 05:05:24 -0700 (PDT) Date: Tue, 7 Oct 2025 05:05:24 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: 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_289212_1826414132.1759838724050" 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_289212_1826414132.1759838724050 Content-Type: multipart/alternative; boundary="----=_Part_289213_1092278003.1759838724050" ------=_Part_289213_1092278003.1759838724050 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi aj, Interesting points! Answers inline. On Tuesday, October 7, 2025 at 6:38:40=E2=80=AFAM UTC-3 Anthony Towns wrote= : On Wed, Oct 01, 2025 at 07:24:50AM -0700, waxwing/ AdamISZ wrote:=20 > I'm curious about the case of P, R, s published in utxos to prevent usage= =20 > of utxos as data. I think this answers in the half-affirmative: you can= =20 > only embed data by leaking the privkey so that it (can) immediately fall= =20 > out of the utxo set.=20 I think you can attack the setup here.=20 If you allow scriptPubKeys in the utxo set whose spending conditions=20 are HTLC/atomic-swap-like:=20 (pubkey A and preimage reveal of X)=20 OR (pubkey B and block height > H)=20 then you either set H to be arbitrarily far in the future and reveal=20 B's privkey, or choose an NUMS X with no known preimage, and reveal=20 A's privkey. Yes. In the paper (and my OP email) I'm trying to narrow it down completely= =20 to a P, R, s structure. I guess if we try to be realistic about this=20 "publish a signature in the output always" horrible scenario, it would have= =20 to just ditch the NUMS variant of taproot, and I agree, that is a very Bad= =20 Thing (TM). (uh sorry you discuss this in the next paragraph but, w/e). Alternative examples like multisig or hash lock in script to get the data= =20 leakage without losing control of the output (necessarily) have been=20 mentioned but I like your 2-branch setup as a good flexible example. If you don't allow those things (eg, by requiring such constructions=20 also have a (pubkey musig(A,B)) path) then I think you rule out NUMS-IPK=20 constructions, and end up making things like vaults ("hotkey with delay,=20 coldkey anytime") difficult to send to ("I have to sign with my cold=20 key to request funds?"), or, depending on what the utxo R,s is signing,=20 encourage key reuse.=20 > (To emphasize, this is different to the earlier observations (including= =20 by=20 > me!) that just say it is *possible* to leak data by leaking the private= =20 > key; here I'm trying to prove that there is *no other way*).=20 That seems right to me.=20 I think if the signature scheme supported pubkey recovery (ie, s*G =3D R += =20 H(R,m)*P, and our "m" didn't commit to P as well), you could get around=20 this by just having P be the data, with no one, including the "signer"=20 able to recover the private key.=20 Yes, basically. I discuss this in the paper w.r.t. ECDSA. Your description= =20 of the relevance of pubkey recovery is good, but there are some nuances.=20 You can't quite (with ECDSA) get P to be the data and have a valid sig, but= =20 you can get 's' to be the data simply by backsolving for the private key x.= =20 Lack of "pubkey prefixing" in the very funky 'commitment to the nonce' in= =20 ECDSA causes that. And the second nuance, you did actually mention: you get= =20 "not leaking the key" for free, here. But it's still only a 32/96 bytes=20 embedding rate though, the way I count it. =20 > However I still am probably in the large majority that thinks it's=20 > appalling to imagine a sig attached to every pubkey onchain.=20 I think the only thing achieved by embedding data in the utxo set (vs=20 an OP_RETURN output or witness data) is to bloat the utxo set; and if=20 that's the goal, it can equally easily be done with spendable outputs=20 that the attacker simply chooses not to ever spend. So that doesn't seem=20 like a terribly interesting solution to anything. I think the logic of that is not quite right. Suppose I want to embed=20 pictures into the unpruneable utxo set specifically (and not only 'in=20 transactions'). The starting point here was me trying to write out how you= =20 can't embed data in known-privkey (Schnorr) P, R, s tuples. And not only pictures; as Andrew pointed out above, there's always the=20 concern of some kind of virus-y "naughty" data. =20 As far as embedding data in signatures goes, I think the following=20 scheme would allow you to publish data in a cryptographically-secure way,= =20 with minimal lost funds:=20 0) Setup secret keys p and q, and a 32-byte secret k. H(a,b,..) is sha256= =20 of a,b,.. concatenated.=20 1) Split your data into N 31 byte blocks, a1, a2, .., aN.=20 2) Calculate r0 as H(k*G). Calculate r1, .., rN as:=20 r(i+1) =3D H(p, r(i)) + a(i)=20 3) Sign N+1 transactions in a chain spending pubkey p*G, using rN, r(N-1),= =20 .., r1, r0 as nonces. All but the final tx should pay to a p*G output to=20 continue the chain; the final output should pay to q*G instead.=20 4) Once all transactions are sufficiently confirmed, spend the final=20 output with k as the secret nonce (and hence R=3Dk*G as the public=20 nonce).=20 Recover the data using the following process:=20 1) From the final transaction, recover R=3Dk*G, and calculate r0 as H(R).= =20 Recover p from the previous transaction, p =3D (s0-r0)/H(r0*G, P,mi).=20 2) Recover ri from each signature; ri =3D si - H(Ri, P, mi)*p. Recover=20 the data ai as ai =3D ri - H(p,r(i-1)).=20 Dealing with the points being 32-bytes might require carrying over a=20 sign-bit; but that should be possible in the spare ~7 bits since each=20 block was only 31 bytes not 32 bytes. Left as an exercise for the=20 reader, etc.=20 I believe that the privkey p is secure prior to k*G being revealed,=20 since all the nonces are distinct hashes seeded by that privkey; and q=20 remains secure because k is never revealed.=20 If you wanted to not reuse the pubkey p*G repeatedly, you could tweak it=20 to be p0 =3D p, p(i+1) =3D p + H(k*G, p(i)), or similar. That would allow y= ou=20 to use an n-of-n multisig to get multiple blocks in a single transaction=20 without seeming weird, eg.=20 I believe the only way to distinguish this from a normal transaction=20 pattern where a wallet has a change output, is via the final transaction=20 that reveals k*G, and detecting the relationship between k*G and the=20 spending conditions of the transaction that created the coin being spent.= =20 That's already somewhat expensive to check for every spend, but could=20 be made more so by publishing k*G on some other medium (ie the data is=20 in the blockchain, but you obtain the txid and key to find the data=20 from elsewhere), or by revealing (k+x)*G where x is a random 20-bit=20 (?) number, and a significant but tractable amount of grinding is needed=20 to recover the desired k*G and decode the data -- the idea being that=20 that is tractable for someone who knows there is data at that txid,=20 but not tractable when performed on every signature in the blockchain=20 in order to filter data publication.=20 I think if you did 20 such transactions per block, each spending a single= =20 20-of-20 tapscript multisig, you'd get 12400 bytes of data per block=20 (without violating standardness constraints), at a cost of ~11800vb, so=20 much less efficient than inscriptions, but slightly more efficient than=20 OP_RETURN, and significantly less detectable than either. I think Knots=20 default policy currently allows up to 50-of-50 multisig in tapscript,=20 which would give you 31kB of data in ~26.6kvB of tx weight in a block.=20 If you're regularly making payments from a particular wallet, I think=20 that procedure would allow you to encode data in your change outputs at=20 the rate of 32B/tx for no additional cost. Though the data would only be=20 recoverable once complete, and it's probably worth noting that I haven't=20 provided any security proofs... Very nice example. I am glad you took the trouble to write it out, because= =20 I agree that examples like that are worth working through because as you=20 say they lean closer to being properly indistinguishable from ordinary=20 transaction patterns. My analysis was narrower: output-side embedding (in a theoretical future of= =20 P,R,s outputs). But that's a little confusing because (P, R, s) is still=20 there whether some of it is put in witness or not. So everyone seems to=20 agree that privkey reveal is necessary for that, but everyone is also=20 pointing out that with Bitcoin's actual consensus scripting system, that=20 doesn't quite mean what it seems! And the embedding rate is not very good.= =20 In this framing, not much has changed in your "chained" example: once the= =20 privkey p is revealed, you get the k value per chain link, so it's still=20 roughly a 1/3 ratio, or more realistically, as you mention (and I did=20 upthread), it's per *transaction* which is a much lower rate. Your points about limits, standardness constraints are well taken; those=20 are the kinds of things that do actually matter today, but I was not=20 thinking about. --=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/= e4d271ad-9ea3-41e5-96e2-6cb0118943e4n%40googlegroups.com. ------=_Part_289213_1092278003.1759838724050 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi aj,

Interesting points! Answers inline.
<= br />


On Tuesday, Octobe= r 7, 2025 at 6:38:40=E2=80=AFAM UTC-3 Anthony Towns wrote:
On Wed, Oct 01, 2025 at 07:24:50AM -0700, wa= xwing/ AdamISZ wrote:
> I'm curious about the case of P, R, s published in utxos to prev= ent usage
> of utxos as data. I think this answers in the half-affirmative: = you can
> only embed data by leaking the privkey so that it (can) immediat= ely fall
> out of the utxo set.

I think you can attack the setup here.

If you allow scriptPubKeys in the utxo set whose spending conditions
are HTLC/atomic-swap-like:

(pubkey A and preimage reveal of X)
OR (pubkey B and block height > H)

then you either set H to be arbitrarily far in the future and reveal
B's privkey, or choose an NUMS X with no known preimage, and reveal
A's privkey.

Yes. In the paper (and= my OP email) I'm trying to narrow it down completely to a P, R, s structur= e. I guess if we try to be realistic about this "publish a signature in the= output always" horrible scenario, it would have to just ditch the NUMS var= iant of taproot, and I agree, that is a very Bad Thing (TM). (uh sorry you = discuss this in the next paragraph but, w/e).

Al= ternative examples like multisig or hash lock in script to get the data lea= kage without losing control of the output (necessarily) have been mentioned= but I like your 2-branch setup as a good flexible example.

If you don't allow those things (eg, by requiring such constructions
also have a (pubkey musig(A,B)) path) then I think you rule out NUMS-= IPK
constructions, and end up making things like vaults ("hotkey with del= ay,
coldkey anytime") difficult to send to ("I have to sign with my cold
key to request funds?"), or, depending on what the utxo R,s is signin= g,
encourage key reuse.

> (To emphasize, this is different to the earlier observations (in= cluding by
> me!) that just say it is *possible* to leak data by leaking the = private
> key; here I'm trying to prove that there is *no other way*).

That seems right to me.

I think if the signature scheme supported pubkey recovery (ie, s*G = =3D R +
H(R,m)*P, and our "m" didn't commit to P as well), you could get arou= nd
this by just having P be the data, with no one, including the "signer= "
able to recover the private key.


Yes, basically. I discuss this in = the paper w.r.t. ECDSA. Your description of the relevance of pubkey recover= y is good, but there are some nuances. You can't quite (with ECDSA) get P t= o be the data and have a valid sig, but you can get 's' to be the data simp= ly by backsolving for the private key x. Lack of "pubkey prefixing" in the = very funky 'commitment to the nonce' in ECDSA causes that. And the second n= uance, you did actually mention: you get "not leaking the key" for free, he= re. But it's still only a 32/96 bytes embedding rate though, the way I coun= t it.
=C2=A0
> Howeve= r I still am probably in the large majority that thinks it's
> appalling to imagine a sig attached to every pubkey onchain.

I think the only thing achieved by embedding data in the utxo set (vs
an OP_RETURN output or witness data) is to bloat the utxo set; and if
that's the goal, it can equally easily be done with spendable outputs
that the attacker simply chooses not to ever spend. So that doesn't s= eem
like a terribly interesting solution to anything.
I think the logic of that is not quite right. Suppose I want= to embed pictures into the unpruneable utxo set specifically (and not only= 'in transactions'). The starting point here was me trying to write out how= you can't embed data in known-privkey (Schnorr) P, R, s tuples.
=
And not only pictures; as Andrew pointed out above, there'= s always the concern of some kind of virus-y "naughty" data.
=C2= =A0


As far as embedding data in signatures goes, I think the following
scheme would allow you to publish data in a cryptographically-secure = way,
with minimal lost funds:

0) Setup secret keys p and q, and a 32-byte secret k. H(a,b,..) is s= ha256
of a,b,.. concatenated.

1) Split your data into N 31 byte blocks, a1, a2, .., aN.

2) Calculate r0 as H(k*G). Calculate r1, .., rN as:

r(i+1) =3D H(p, r(i)) + a(i)

3) Sign N+1 transactions in a chain spending pubkey p*G, using rN, r= (N-1),
.., r1, r0 as nonces. All but the final tx should pay to a p*G ou= tput to
continue the chain; the final output should pay to q*G instead.

4) Once all transactions are sufficiently confirmed, spend the final
output with k as the secret nonce (and hence R=3Dk*G as the publi= c
nonce).

Recover the data using the following process:

1) From the final transaction, recover R=3Dk*G, and calculate r0 as = H(R).
Recover p from the previous transaction, p =3D (s0-r0)/H(r0*G, P,= mi).

2) Recover ri from each signature; ri =3D si - H(Ri, P, mi)*p. Recov= er
the data ai as ai =3D ri - H(p,r(i-1)).

Dealing with the points being 32-bytes might require carrying over a
sign-bit; but that should be possible in the spare ~7 bits since each
block was only 31 bytes not 32 bytes. Left as an exercise for the
reader, etc.

I believe that the privkey p is secure prior to k*G being revealed,
since all the nonces are distinct hashes seeded by that privkey; and = q
remains secure because k is never revealed.

If you wanted to not reuse the pubkey p*G repeatedly, you could tweak= it
to be p0 =3D p, p(i+1) =3D p + H(k*G, p(i)), or similar. That would a= llow you
to use an n-of-n multisig to get multiple blocks in a single transact= ion
without seeming weird, eg.

I believe the only way to distinguish this from a normal transaction
pattern where a wallet has a change output, is via the final transact= ion
that reveals k*G, and detecting the relationship between k*G and the
spending conditions of the transaction that created the coin being sp= ent.
That's already somewhat expensive to check for every spend, but could
be made more so by publishing k*G on some other medium (ie the data i= s
in the blockchain, but you obtain the txid and key to find the data
from elsewhere), or by revealing (k+x)*G where x is a random 20-bit
(?) number, and a significant but tractable amount of grinding is nee= ded
to recover the desired k*G and decode the data -- the idea being that
that is tractable for someone who knows there is data at that txid,
but not tractable when performed on every signature in the blockchain
in order to filter data publication.

I think if you did 20 such transactions per block, each spending a si= ngle
20-of-20 tapscript multisig, you'd get 12400 bytes of data per block
(without violating standardness constraints), at a cost of ~11800vb, = so
much less efficient than inscriptions, but slightly more efficient th= an
OP_RETURN, and significantly less detectable than either. I think Kno= ts
default policy currently allows up to 50-of-50 multisig in tapscript,
which would give you 31kB of data in ~26.6kvB of tx weight in a block= .

If you're regularly making payments from a particular wallet, I think
that procedure would allow you to encode data in your change outputs = at
the rate of 32B/tx for no additional cost. Though the data would only= be
recoverable once complete, and it's probably worth noting that I have= n't
provided any security proofs...

Ver= y nice example. I am glad you took the trouble to write it out, because I a= gree that examples like that are worth working through because as you say t= hey lean closer to being properly indistinguishable from ordinary transacti= on patterns.

My analysis was narrower: output-si= de embedding (in a theoretical future of P,R,s outputs). But that's a littl= e confusing because (P, R, s) is still there whether some of it is put in w= itness or not. So everyone seems to agree that privkey reveal is necessary = for that, but everyone is also pointing out that with Bitcoin's actual cons= ensus scripting system, that doesn't quite mean what it seems! And the embe= dding rate is not very good. In this framing, not much has changed in your = "chained" example: once the privkey p is revealed, you get the k value per = chain link, so it's still roughly a 1/3 ratio, or more realistically, as yo= u mention (and I did upthread), it's per *transaction* which is a much lowe= r rate.

Your points about limits, standardness c= onstraints are well taken; those are the kinds of things that do actually m= atter today, but I was not thinking about.


--
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/e4d271ad-9ea3-41e5-96e2-6cb0118943e4n%40googlegroups.com.
------=_Part_289213_1092278003.1759838724050-- ------=_Part_289212_1826414132.1759838724050--