> Can you let me know how you're getting 66%+? You have three chunks, which are needed: (P,R,s). You can control "P" and "R" directly and fully, by feeding it with your data. That means, you can get 66%, because it is just 2/3, if you assume, that all values have the same size. Then, to get 70% or more, grinding s-value is needed, which is doable, if you want to for example grind two or three bytes of s-value, and stop there. But let's assume, that you want to make it as fast as possible, so you don't grind anything, and then stop at 66%. > Maybe write out concretely what the data-reader would be doing? I already told you, when I said "known plaintext attack". If you want to put random data into private keys or signatures, then things are hard to break. However, if it is something useful for the reader, then usually, that kind of data are non-random. For example: some users store transactions inside OP_RETURNs, and they use ASCII hex representation. If they would use binary encoding, then they would save 50% space. But people simply don't care. And the similar case is possible here: if you want to store random data, then it is hard to use this method. However, if you want to store ASCII text, where many words can be found in a dictionary, or where the format of the data is known upfront, or can be easily guessed, then the security of the keys, is comparable to the brainwallets. Which means, that you can just put your data into the private key of the user, and a "signature nonce" (which is nothing else, but yet another private key, placed on secp256k1). And then, if you know, that your data, is for example "ASCII string", then it means, that each and every key, that you produce, simply leaks at least 32 bits per 256-bit key, if not more. And then, if the attacker can get coins from brainwallets, then decoding such data is not much harder than that. If your data contains simple words, then even dictionary attacks can be used. So, let's say that you want to encode 64 bytes in a signature: d="This is a test of storing data i"=0x5468697320697320612074657374206f662073746f72696e6720646174612069 k="n private keys inside signatures"=0x6e2070726976617465206b65797320696e73696465207369676e617475726573 P=d*G=02A2EF730B26A905A7D91940E3A512C5771D8BC8BCCA153D714E328043856CBB2B R=k*G=02E19FCA1025CFD67409309E2B1711D723BFB67EC520917D9A0AD9432414DA0D0A And then, s-value comes from SHA-256 hashing, so it is harder to control. But grinding a few bytes can give something around 70%. However, even if we stop at 66%, then still: useful data are regular. There are many patterns. If something is an ASCII string, then 1/8 bits are cleared, and it is known, which ones should be set to zero. If it is in English, then the entropy is even lower. Which means, that the private key is not directly "leaked", by being passed to the reader, but there is an assumption, that it will be easy enough to get. Also, if the key won't be leaked, then it can be used as an advantage: first, NFTs can be minted, and transferred, and then, you can pass the data directly, and say: "See? You can confirm, that they are encoded into private keys properly". And as long as the data in question is difficult enough to fully guess, the key is not revealed, even if it is quite weak. Which means, that my answer to your question is: it is a spectrum. You can make a weak signature, and have 33% encoding efficiency, and leak every private key immediately. But you can make something in a spectrum between 33% and 66%, and make something, that is "weak", but something, which won't be broken "on the spot, immediately after being broadcasted" (so you cannot really say, that the keys are "leaked", because you need to know "something" about the plaintext inside private keys, or about its format). And it is good for spammers, because then, funds can be safely confirmed, and later revealed, that "hey, I encoded that data here, by wasting 3 MB of block space, to encode 2 MB of ASCII strings, here is your NFT, that you can buy here". sob., 1 lis 2025 o 16:47 waxwing/ AdamISZ napisał(a): > 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 > > . > -- 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/CAN7kyNgyoA5rb8hYuxai6bSaPdon%3Dy%3D9Z%2BdAfqP6Mf%3DPyniJLw%40mail.gmail.com.