Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr

From: waxwing/ AdamISZ <[email-masked]>
Date: Wed, 8 Oct 2025 05:55:36 -0700 (PDT)

Answers inline.

On Wednesday, October 8, 2025 at 5:45:06 AM UTC-3 Anthony Towns wrote:

On Tue, Oct 07, 2025 at 05:05:24AM -0700, waxwing/ AdamISZ wrote: 
> Yes, basically. I discuss this in the paper w.r.t. ECDSA. Your 
description 
> of the relevance of pubkey recovery is good, but there are some nuances. 
> You can't quite (with ECDSA) get P to be the data and have a valid sig, 
but 
> you can get 's' to be the data simply 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 nuance, you did actually mention: you 
get 
> "not leaking the key" for free, here. But it's still only a 32/96 bytes 
> embedding rate though, the way I count it. 

You've got 4x 32-byte values to play with: s, r, p and m. The verification 
equation determines one of these, reducing it to 3x. m isn't able to be 
freely chosen, reducing it to 2x. And being able to reverse the equation 
in order to calculate anything requires the receiver to know one of the 
secrets, which reduces it to 1x. (Grinding can bump that back up to a 
factor of 1.something) So that's the 32. On the other side, you need to 
transmit everything but m which is otherwise determined by the setup, 
so that's the 96. 

Yeah I think so, roughly. It's not 100% watertight deductions but it seems 
correct from where I'm sitting.
(I would only nit that 'm' isn't in consideration as it's implicit, not 
published, in current signature usage; in a proposed signature-in-output, m 
would obviously be constrained to something with no wiggle room (and 
including P if we used ECDSA, but we wouldn't).

> 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'). 

Sure, but then I'll also suppose your goal is to harm Bitcoin by bloating 
the utxo set. If that weren't one of your fundamental goals, you'd use 
other, cheaper and easier, ways of encoding the data.

But the goal can be simply this: my data is more marketable if I can 
plausibly claim that it's embedded into bitcoin nodes for eternity (whether 
true or not, it's marketable). AFAIK this is indeed a thing, in the real 
world.

> Very nice example. I am glad you took the trouble to write it out, 
because 
> I agree that examples like that are worth working through because as you 
> say they lean closer to being properly indistinguishable from ordinary 
> transaction patterns. 

I think the (P,R,s) outputs could be an interesting design for a 
non-programmable system that was intended purely for payments -- a 
FEDwire/SWIFT replacement without the possibility of vaults, lightning, 
etc. Presumably more mimblewimble friendly etc too. Presumably the "R,s" 
values could also be a signature of P by the operator's well known pubkey, 
giving you a KYC/CBDC-like system too. 

You could get programmability back in this scenario by allow P to sign 
a script, which you then satisfy, rather than signing a payment directly 
(ie, the graftroot approach). 

I like this line of thought, and indeed I'd forgotten about graftroot and 
the whole delegation angle.
(and just to repeat the point made earlier: we'd only need to sign over a 
message including P for ecdsa, but we wouldn't use that.)
I guess if you're discussing a hypothetical permissioned system though it's 
a whole different world, so I'm going to sidestep that one.

But it does sound interesting to do delegation and then ZkPOK outputs even 
in a Bitcoin world. Albeit it's a long way from where we are today.

Of course we're firmly pie in the sky again here, but I think it helps 
inform thinking about Bitcoin as it is concretely today.

Anyway, once you make the system programmable in interesting ways, I 
think you get data embeddability pretty much immediately,

My main motivation in discussing this was indeed the extent to which you 
get embeddability even without any programmability; as we've established, 
it's not zero, and it's not restricted to grinding (exponential work). But 
in *pure* unprogrammable, ZkPOK outputs of form P, R,s and nothing else 
allowed, it *is*, I'm claiming, restricted to key leakage and doesn't 
surpass 33%.

and then it's 
just a matter of trading off the optimal encoding rate versus how easily 
identifiable your transactions can be. Forcing data to be hidden at a 
cost of making it less efficient just leaves less resources available 
to other users of the system, though, which doesn't seem like a win in 
any way to me. 

> Your points about limits, standardness constraints are well taken; those 
> are the kinds of things that do actually matter today, but I was not 
> thinking about. 

Note that I mentioned the standardness constraints not because they're 
limits today, but rather because they reflect the form existing txs take, 
so mimicing that form would allow txs embedding data via this scheme to 
be difficult to distinguish from other txs, and hence equally difficult 
to censor/filter. 

I see. Good point.

-- 
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 [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/323c2d13-e90f-49c5-bfe0-f161b8b8dbb4n%40googlegroups.com.