Delivery-date: Wed, 01 Oct 2025 16:20:31 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.127 as permitted sender) client-ip=66.183.0.127;
Date: Wed, 1 Oct 2025 23:11:37 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr
Message-ID: <aN21KbXTORgXAVH0@mail.wpsoftware.net>
References: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com>
 <CAAS2fgQRz=EJ+Nm2rxrB_SEpqroFbcc+hUhmghJJ1jrJc-WUDA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="W3fq7Rcg/H7ctoXC"
Content-Disposition: inline
In-Reply-To: <CAAS2fgQRz=EJ+Nm2rxrB_SEpqroFbcc+hUhmghJJ1jrJc-WUDA@mail.gmail.com>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com


--W3fq7Rcg/H7ctoXC
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline

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.

--W3fq7Rcg/H7ctoXC
Content-Type: application/pgp-signature; name=signature.asc

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCgAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmjdtScACgkQxYjWPOQb
l8EuqQf/a9nqRL84KJ5GvIuDol33hP4duxj5I3HF/I9wzFn20AjZDvStJnbt6PPk
azDXivhnniNodlEXcD5DqCrTVL+YAMfDi0Q7bfm5hrUPEiTNSJCphQ2zCkEhnWc3
NO4ipsPt1ps2sWbD0z2BzOHmwVACpcnevHQ988x95nbfVICzPhLrqsubc9aXfPgB
zWd8qXtezxleZ+lOUZo96aLpTDRd9hcpehOmlZaYMBb3sNDW60STM5ymE60G58U8
06qacCWfFNSyn0XBY/MFOXUWu1qtR7hZ8M52ej6B+n6vVi1w9gSPAhGFl6asen2Z
n8lX331UHt84m+XZdIZ1iUMKZDisLg==
=EEBV
-----END PGP SIGNATURE-----

--W3fq7Rcg/H7ctoXC--