* [bitcoindev] On (in)ability to embed data into Schnorr
@ 2025-10-01 14:24 waxwing/ AdamISZ
2025-10-01 22:10 ` Greg Maxwell
2025-10-03 13:24 ` Peter Todd
0 siblings, 2 replies; 7+ messages in thread
From: waxwing/ AdamISZ @ 2025-10-01 14:24 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 1548 bytes --]
Hi all,
https://github.com/AdamISZ/schnorr-unembeddability/
Here I'm analyzing whether the following statement is true: "if you can
embed data into a (P, R, s) tuple (Schnorr pubkey and signature, BIP340
style), without grinding or using a sidechannel to "inform" the reader, you
must be leaking your private key".
See the abstract for a slightly more fleshed out context.
I'm curious about the case of P, R, s published in utxos to prevent 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) immediately fall
out of the utxo set.
(To emphasize, this is different to the earlier observations (including 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*).
However I still am probably in the large majority that thinks it's
appalling to imagine a sig attached to every pubkey onchain.
Either way, I found it very interesting! Perhaps others will find the
analysis valuable.
Feedback (especially of the "that's wrong/that's not meaningful" variety)
appreciated.
Regards,
AdamISZ/waxwing
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/0f6c92cc-e922-4d9f-9fdf-69384dcc4086n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 2061 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoindev] On (in)ability to embed data into Schnorr
2025-10-01 14:24 [bitcoindev] On (in)ability to embed data into Schnorr waxwing/ AdamISZ
@ 2025-10-01 22:10 ` Greg Maxwell
2025-10-01 23:11 ` Andrew Poelstra
2025-10-03 13:24 ` Peter Todd
1 sibling, 1 reply; 7+ messages in thread
From: Greg Maxwell @ 2025-10-01 22:10 UTC (permalink / raw)
To: waxwing/ AdamISZ; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 3193 bytes --]
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 everything
else. I think it would be hard to prove.
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 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? ... and then any of
whatever spam concerns people have would likely be exacerbated by the
spammers using more resources due to the embedding rate?
Also re private key leaking an utxo set, well not so if it's part of an
explicit multisig. E.g. 2 of 2 with leaked key and a secure one.
On Wed, Oct 1, 2025 at 7:50 PM waxwing/ AdamISZ <ekaggata@gmail•com> wrote:
> Hi all,
>
> https://github.com/AdamISZ/schnorr-unembeddability/
>
> Here I'm analyzing whether the following statement is true: "if you can
> embed data into a (P, R, s) tuple (Schnorr pubkey and signature, BIP340
> style), without grinding or using a sidechannel to "inform" the reader, you
> must be leaking your private key".
>
> See the abstract for a slightly more fleshed out context.
>
> I'm curious about the case of P, R, s published in utxos to prevent 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) immediately fall
> out of the utxo set.
>
> (To emphasize, this is different to the earlier observations (including 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*).
>
> However I still am probably in the large majority that thinks it's
> appalling to imagine a sig attached to every pubkey onchain.
>
> Either way, I found it very interesting! Perhaps others will find the
> analysis valuable.
>
> Feedback (especially of the "that's wrong/that's not meaningful" variety)
> appreciated.
>
> Regards,
> AdamISZ/waxwing
>
> --
> 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
> email to bitcoindev+unsubscribe@googlegroups•com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/0f6c92cc-e922-4d9f-9fdf-69384dcc4086n%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/0f6c92cc-e922-4d9f-9fdf-69384dcc4086n%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAAS2fgQRz%3DEJ%2BNm2rxrB_SEpqroFbcc%2BhUhmghJJ1jrJc-WUDA%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 4267 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoindev] On (in)ability to embed data into Schnorr
2025-10-01 22:10 ` Greg Maxwell
@ 2025-10-01 23:11 ` Andrew Poelstra
2025-10-02 0:25 ` waxwing/ AdamISZ
0 siblings, 1 reply; 7+ messages in thread
From: Andrew Poelstra @ 2025-10-01 23:11 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 2288 bytes --]
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 everything
> else. I think it would be hard to prove.
>
> 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 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? ... and then 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 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 = k + ex where e is a hash of kG (among other things)
so I don't think you can force that value at all.)
--
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
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/aN21KbXTORgXAVH0%40mail.wpsoftware.net.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoindev] On (in)ability to embed data into Schnorr
2025-10-01 23:11 ` Andrew Poelstra
@ 2025-10-02 0:25 ` waxwing/ AdamISZ
2025-10-02 15:56 ` waxwing/ AdamISZ
0 siblings, 1 reply; 7+ messages in thread
From: waxwing/ AdamISZ @ 2025-10-02 0:25 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 5725 bytes --]
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,
but Bitcoin is more than a signature scheme!
> 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 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? ... and then any of
whatever spam concerns people have would likely be exacerbated by the
spammers using more resources due to the 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 mostly academic investigation. It would be nice
to be surer what the limits are, although I suspect we're all reasonably
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)
(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 but 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 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 = 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 as "adversary
must be able to publish a function f such that f(any published R, s, (e)) =
data", i.e. not just f = identity function. That was why I wrote in the
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
\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 will 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, 2025 at 8:20:25 PM UTC-3 Andrew Poelstra wrote:
> 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 everything
> > else. I think it would be hard to prove.
> >
> > 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
> 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? ... and then 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 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 = k + ex where e is a hash of kG (among other things)
> so I don't think you can force that value at all.)
>
> --
> 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
>
>
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/2e366b25-f789-4c9d-acf9-b87149d6a796n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 10070 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoindev] On (in)ability to embed data into Schnorr
2025-10-02 0:25 ` waxwing/ AdamISZ
@ 2025-10-02 15:56 ` waxwing/ AdamISZ
2025-10-02 19:49 ` Greg Maxwell
0 siblings, 1 reply; 7+ messages in thread
From: waxwing/ AdamISZ @ 2025-10-02 15:56 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 2892 bytes --]
> > 12% 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 but it'd be easier if
you told me :)
Thinking about it again: to publish data, you have to publish a
transaction! I guess the most economical, paying taproot to taproot, is
about 192 bytes with script path plus the posited extra 64 for the (R,s) in
the output, so yeah that'd be 32 out of 256, 12.5%. Isn't the figure a bit
different for key path though, because no control block? Well it hardly
matters, it's some small fraction in that range.
An interesting mechanical detail in this near-absurd scenario is that if
you wanted to repeatedly publish off the same (presumably a few multiples
of dust level) output, you couldn't also do the leak single key thing,
since you'd lose control to re-spend. So that'd place us in the "explicit
multisig" scenario that Greg mentioned, which I think would only make sense
with legacy script? Kind of a different scenario, also it would be really
weird to update legacy script to take into account a new "you must sign the
pubkeys" rule. Though I guess in this fictional scenario, it might happen
like that. If you did do it with legacy, you'd be publishing bare 2 of 2
multisig. If you did it with taproot due to how that works, the script is
not published until the output is spent, so I think that's outside what I
was considering ("data in utxo set"). (I guess you could also use something
like a hash lock which might be more efficient). So anyway if you wanted to
do this repeatedly and minimize cost, for whatever strange reason, you'd be
adding another 50-100 bytes each time bringing that % down to like 10% or
less.
But that all became way too hypothetical to even analyze properly :)
Anyway just to reemphasize I certainly wasn't advocating this sig-attaching
system, but it seems important to know what the result of it would be: we
would still not have changed the obvious reality that embedding data in
witness gives more space for data, and is more economical, and we would
only reduce by a big factor how much can be embedded in outputs (anything
from 8% to 15% embedding rate seems possible depending on the hypothetical
details), while having to screw up much of Bitcoin's functionality in the
process.
Cheers,
AdamISZ/waxwing
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/cf15c24e-18d0-4221-a3d4-4177c82a6381n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 3303 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoindev] On (in)ability to embed data into Schnorr
2025-10-02 15:56 ` waxwing/ AdamISZ
@ 2025-10-02 19:49 ` Greg Maxwell
0 siblings, 0 replies; 7+ messages in thread
From: Greg Maxwell @ 2025-10-02 19:49 UTC (permalink / raw)
To: waxwing/ AdamISZ; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 3950 bytes --]
I just meant in the purely grinding non-key leaking case you could get 4
bytes into the nonce pretty easily and 4 bytes into either the pubkey or
signature out of a 64 byte signature. Obviously the delivered embedding
rate in a whole txn will be lower, but maybe not that much thanks to
multisig outputs.
On Thu, Oct 2, 2025 at 4:17 PM waxwing/ AdamISZ <ekaggata@gmail•com> wrote:
> > > 12% 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 but it'd be easier if
> you told me :)
>
> Thinking about it again: to publish data, you have to publish a
> transaction! I guess the most economical, paying taproot to taproot, is
> about 192 bytes with script path plus the posited extra 64 for the (R,s) in
> the output, so yeah that'd be 32 out of 256, 12.5%. Isn't the figure a bit
> different for key path though, because no control block? Well it hardly
> matters, it's some small fraction in that range.
>
> An interesting mechanical detail in this near-absurd scenario is that if
> you wanted to repeatedly publish off the same (presumably a few multiples
> of dust level) output, you couldn't also do the leak single key thing,
> since you'd lose control to re-spend. So that'd place us in the "explicit
> multisig" scenario that Greg mentioned, which I think would only make sense
> with legacy script? Kind of a different scenario, also it would be really
> weird to update legacy script to take into account a new "you must sign the
> pubkeys" rule. Though I guess in this fictional scenario, it might happen
> like that. If you did do it with legacy, you'd be publishing bare 2 of 2
> multisig. If you did it with taproot due to how that works, the script is
> not published until the output is spent, so I think that's outside what I
> was considering ("data in utxo set"). (I guess you could also use something
> like a hash lock which might be more efficient). So anyway if you wanted to
> do this repeatedly and minimize cost, for whatever strange reason, you'd be
> adding another 50-100 bytes each time bringing that % down to like 10% or
> less.
>
> But that all became way too hypothetical to even analyze properly :)
>
> Anyway just to reemphasize I certainly wasn't advocating this
> sig-attaching system, but it seems important to know what the result of it
> would be: we would still not have changed the obvious reality that
> embedding data in witness gives more space for data, and is more
> economical, and we would only reduce by a big factor how much can be
> embedded in outputs (anything from 8% to 15% embedding rate seems possible
> depending on the hypothetical details), while having to screw up much of
> Bitcoin's functionality in the process.
>
> Cheers,
> AdamISZ/waxwing
>
> --
> 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
> email to bitcoindev+unsubscribe@googlegroups•com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/cf15c24e-18d0-4221-a3d4-4177c82a6381n%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/cf15c24e-18d0-4221-a3d4-4177c82a6381n%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAAS2fgQtx_FnecKxpKryTq9o5HJfirY_Vyih6FXzHGHG2itmQQ%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 4778 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoindev] On (in)ability to embed data into Schnorr
2025-10-01 14:24 [bitcoindev] On (in)ability to embed data into Schnorr waxwing/ AdamISZ
2025-10-01 22:10 ` Greg Maxwell
@ 2025-10-03 13:24 ` Peter Todd
1 sibling, 0 replies; 7+ messages in thread
From: Peter Todd @ 2025-10-03 13:24 UTC (permalink / raw)
To: waxwing/ AdamISZ; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 1531 bytes --]
On Wed, Oct 01, 2025 at 07:24:50AM -0700, waxwing/ AdamISZ wrote:
> Hi all,
>
> https://github.com/AdamISZ/schnorr-unembeddability/
>
> Here I'm analyzing whether the following statement is true: "if you can
> embed data into a (P, R, s) tuple (Schnorr pubkey and signature, BIP340
> style), without grinding or using a sidechannel to "inform" the reader, you
> must be leaking your private key".
>
> See the abstract for a slightly more fleshed out context.
>
> I'm curious about the case of P, R, s published in utxos to prevent 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) immediately fall
> out of the utxo set.
>
> (To emphasize, this is different to the earlier observations (including 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*).
You can probably use timelock encryption to ensure that the leak of the private
key only happens in the future, after the funds are recovered by the owner in a
subsequent transaction.
--
https://petertodd.org 'peter'[:-1]@petertodd.org
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/aN_OlgvB-Co1BL19%40petertodd.org.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2025-10-03 15:51 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-10-01 14:24 [bitcoindev] On (in)ability to embed data into Schnorr waxwing/ AdamISZ
2025-10-01 22:10 ` Greg Maxwell
2025-10-01 23:11 ` Andrew Poelstra
2025-10-02 0:25 ` waxwing/ AdamISZ
2025-10-02 15:56 ` waxwing/ AdamISZ
2025-10-02 19:49 ` Greg Maxwell
2025-10-03 13:24 ` Peter Todd
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox