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: Sat, 1 Nov 2025 07:49:05 -0700 (PDT) [thread overview]
Message-ID: <781840dd-b633-4d87-b05d-d389c6374d63n@googlegroups.com> (raw)
In-Reply-To: <CAN7kyNhE39gJyV7xCRNpZAu-jkP7bu2DvkhZ7FdLsGxa-QLjQw@mail.gmail.com>
[-- Attachment #1.1: Type: text/plain, Size: 5975 bytes --]
Hi Garlo Nicon,
Before I answer your point I want to mention (to readers): probably some
things remained tacit in this thread but are worth emphasizing:
1. It's always trivial to get a 100% embedding rate if it's OK to assume
the embedder is choosing to share data off-blockchain with others (just xor
the real signature with their chosen data and call that the key). This is
of course is a bit silly (though not entirely silly); if the purpose is to
*communicate* then they can use the communication channel for the data,
instead of the xor value, and forget about the blockchain. On the other
hand if their purpose is to publish data, and rely on the immutability and
persistence of the blockchain, then there is the problem that the xor key
can be lost; it's that offchain data that represents the actual semantics
of what they published, and so they're in rather the same position as they
would have been without the blockchain existing at all. (insert
finesses/caveats but, basically).
2. All of the above theoretical analysis doesn't work for ECDSA *as an
algorithm outside of Bitcoin*. You get 32 bytes of embedding without
leaking the private key, there. (the s-value can literally be made to say
"hello world" 3 times or whatever). this is the non-pubkey-committing
nature of standard ECDSA. I *think* you can make it behave the same as
Schnorr in terms of pubkey-unembeddability-without-key-leakage by putting
the pubkey in the message, but it's even harder to analyze than Schnorr
(which is already hard).
3. In contrast to 2., the pubkey is in fact embedded in the message
(indirectly), at least usually, in Bitcoin (except sighash_noinput type
stuff which isn't live), so you can't put hello world in the signatures for
now, at least AFAIK. Still even then you're stuck at a 33% rate if we
include all of P, R, s, which seems reasonable (in fact, that's a generous
measure). Again, I am ignoring grinding which always adds a bit more.
Anyway, you say:
> So, I guess it is a spectrum: something like 70% efficiency means, that
you need "known plaintext attack" to get the data. And then, you can use
less and less bits per public key, to make it arbitrarily weaker. Then,
instead of relying on a timelock, you can rely on computation difficulty
for the reader, for example: "how many bits I need to leak, to make it
breakable by lattice attack".
I think it's an interesting idea to use lattice attacks but I can't find a
way to agree with 66 or 70%. Here's why:
We assume a "few" signatures are all on the same private key. If there are
N such signatures, then once LLL or similar lattice method is successful,
you retrieve the 1 private key (32 bytes) and the N * 27 bytes (or so;
imagining 5 bytes are biased; it *can* go lower, requiring more signatures;
doesn't change the situation).
So you embedded successfully 27N+32 (all the nonces and the private key)
into 64N + 32N [1] for a ratio that is a bit less than 33%. Compare with
just using a repeated nonce in 2 equations, where you get 64 bytes (nonce,
privkey) from 2*P + 2*(R,s) or so a total of 196, i.e. 33% exactly.
Basically, at least in a bitcoin context, there is no gain in doing a
partial exposure of the nonce; you may as well just reveal all of it,
either by repetition or as noted in the pdf, by using something public like
a block hash. Notice that if my note [1] did not apply, then all the above
isn't correct, the ratios work differently.
Can you let me know how you're getting 66%+? I'm guessing you're just
saying "the k and the d values" but as per above I don't see it. Maybe
write out concretely what the data-reader would be doing?
[1] It's easy to slip up here - I know I did - when considering publication
*on bitcoin* compared with just publishing signatures. In the latter case,
I can publish 100 signatures with the tacit assumption that they all refer
to the same key (or, you can verify, to check). In bitcoin the pubkey is
never tacit, it's always published in the scriptPubKey or scriptSig or
whatever, so you can't gain efficiency from repeated uses of the same key
(i.e. you can't write 64N + 32, it must be 64N + 32N for (P, R, s) tuples).
Cheers,
Adam
On Friday, October 31, 2025 at 10:25:30 AM UTC-3 Garlo Nicon wrote:
> 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
You can embed data into a valid signature. For example:
R=k*G
P=d*G
k=first_chunk_of_data
d=second_chunk_of_data
And then, keys are "weak", because people can use "known plaintext attack",
to get them. However, if you want to push random data, that is unknown to
the reader, then it is known only by the holder of the data.
Which means, that the efficiency of this encoding is somewhere around 66%,
by grinding SHA-256 hashes, it could probably reach around 70% in practice.
Only s-value is something, that needs any grinding, for k-value and
d-value, you need only the data, and nothing else.
So, I guess it is a spectrum: something like 70% efficiency means, that you
need "known plaintext attack" to get the data. And then, you can use less
and less bits per public key, to make it arbitrarily weaker. Then, instead
of relying on a timelock, you can rely on computation difficulty for the
reader, for example: "how many bits I need to leak, to make it breakable by
lattice attack".
--
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/781840dd-b633-4d87-b05d-d389c6374d63n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 6721 bytes --]
next prev parent reply other threads:[~2025-11-01 15:47 UTC|newest]
Thread overview: 19+ 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
2025-10-02 15:56 ` waxwing/ AdamISZ
2025-10-02 19:49 ` Greg Maxwell
2025-10-06 13:04 ` waxwing/ AdamISZ
2025-10-03 13:24 ` Peter Todd
2025-10-04 2:39 ` waxwing/ AdamISZ
2025-10-07 8:22 ` Anthony Towns
2025-10-07 12:05 ` waxwing/ AdamISZ
2025-10-08 5:12 ` Anthony Towns
2025-10-08 12:55 ` waxwing/ AdamISZ
2025-10-31 9:10 ` Tim Ruffing
2025-10-31 13:09 ` waxwing/ AdamISZ
2025-10-31 13:19 ` Garlo Nicon
2025-11-01 14:49 ` waxwing/ AdamISZ [this message]
2025-11-02 9:11 ` Garlo Nicon
2025-11-02 13:30 ` waxwing/ AdamISZ
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=781840dd-b633-4d87-b05d-d389c6374d63n@googlegroups.com \
--to=ekaggata@gmail.com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
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