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

From: waxwing/ AdamISZ <[email-masked]>
Date: Tue, 7 Oct 2025 05:05:24 -0700 (PDT)

Hi aj,

Interesting points! Answers inline.

On Tuesday, October 7, 2025 at 6:38:40 AM UTC-3 Anthony Towns wrote:

On Wed, Oct 01, 2025 at 07:24:50AM -0700, waxwing/ AdamISZ wrote: 
> 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. 

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 structure. 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 variant of taproot, and I agree, that is a very Bad 
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 
leakage 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 delay, 
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 signing, 
encourage key reuse. 

> (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*). 

That seems right to me. 

I think if the signature scheme supported pubkey recovery (ie, s*G = R + 
H(R,m)*P, and our "m" didn't commit to P as well), you could get around 
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 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.

> However 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 seem 
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.

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 sha256 
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) = 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 output 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=k*G as the public 
nonce). 

Recover the data using the following process: 

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

2) Recover ri from each signature; ri = si - H(Ri, P, mi)*p. Recover 
the data ai as ai = 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 = p, p(i+1) = p + H(k*G, p(i)), or similar. That would allow you 
to use an n-of-n multisig to get multiple blocks in a single transaction 
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 transaction 
that reveals k*G, and detecting the relationship between k*G and the 
spending conditions of the transaction that created the coin being spent. 
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 is 
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 needed 
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 single 
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 than 
OP_RETURN, and significantly less detectable than either. I think Knots 
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 haven't 
provided any security proofs...

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.

My analysis was narrower: output-side embedding (in a theoretical future of 
P,R,s outputs). But that's a little confusing because (P, R, s) is still 
there whether some of it is put in witness 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 consensus scripting system, that 
doesn't quite mean what it seems! And the embedding 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 you mention (and I did 
upthread), it's per *transaction* which is a much lower rate.

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.

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