From: waxwing/ AdamISZ <ekaggata@gmail•com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr
Date: Wed, 1 Oct 2025 17:25:38 -0700 (PDT) [thread overview]
Message-ID: <2e366b25-f789-4c9d-acf9-b87149d6a796n@googlegroups.com> (raw)
In-Reply-To: <aN21KbXTORgXAVH0@mail.wpsoftware.net>
[-- 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 --]
prev parent reply other threads:[~2025-10-02 1:49 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-10-01 14:24 waxwing/ AdamISZ
2025-10-01 22:10 ` Greg Maxwell
2025-10-01 23:11 ` Andrew Poelstra
2025-10-02 0:25 ` waxwing/ AdamISZ [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=2e366b25-f789-4c9d-acf9-b87149d6a796n@googlegroups.com \
--to=ekaggata@gmail$(echo .)com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox