From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sun, 02 Nov 2025 02:11:43 -0800 Received: from mail-oa1-f60.google.com ([209.85.160.60]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vFV3l-0002Zm-Ev for bitcoindev@gnusha.org; Sun, 02 Nov 2025 02:11:42 -0800 Received: by mail-oa1-f60.google.com with SMTP id 586e51a60fabf-3c97be590afsf1529447fac.1 for ; Sun, 02 Nov 2025 02:11:40 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1762078295; cv=pass; d=google.com; s=arc-20240605; b=e1TujcYF9G53gjT4hdKDJb+0j012/g9wclttJKpkhuBICjI0ptIgYwpZ4438JGqQK4 EQJGGgFjSlAhtSSFdXX+F/hPK+JAHIOsaCI1oXUSv8W5HuA4usMZe4ak6Keg+yC5Z8qh iEQpPCnYNCrhbyiVddt+cduJlqPt5J37/5AkO22YpK2YYS4alXwLEh0Tuneyzrnexg8m Okt4/hcD/ZdXzWyQevDXVRVJWR+tlXBD/ue4p7MZMEeUBxEqe1K4f9ndImU4dclg0R5K aoAy+sh8Ot+X0nRIvv6yCLudBOnSCyVbjWi1mh0F9J05wyd4fPoF2InWTPeXWX+YEjna R4PQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=pz+wEmKfTrOTMZOdD8+HrqOt1hT/x80CpuSlxMlQTc0=; fh=o+6czXb7r08IBDSPrZqFxZjLm4kuc+XydHDn5DJ0zQI=; b=D/qpkfuhlnYi1U6JPwwAM5OrG9nNNVzTmy0El8OdKzFmNT44g5xzLUccHAm+uQbenY YQraxP7YljffbgA5JhNSDGm5nyh5uj9Qwu9vJFjPpyZBfI/WFzwGDLNZ7LQGeHN0YgH0 t93V0oZUsoFx80ffU66tugiNrCnccVJ01I+jN7gPz2LYwsSzqQr8BP1pbEPVyQDBc1Lk 7//ywH/i3ouguOxzX9jwDqJkxX4F+OV+wZZ+GwwdXRLEA932OqOAyDv+efXuZvEGNGs4 E3frui3/kzh2wWs0Q3miZQ6cHD9nfk58pIC3120qPsWTXI+5cQyFL7YyJtOV3H3a0ilA UU/Q==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=bW5BMrg4; spf=pass (google.com: domain of garlonicon@gmail.com designates 2a00:1450:4864:20::52a as permitted sender) smtp.mailfrom=garlonicon@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1762078295; x=1762683095; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=pz+wEmKfTrOTMZOdD8+HrqOt1hT/x80CpuSlxMlQTc0=; b=X7psa+/w4lR/Ftj/bGpLtPCCnOZtWnz84N3KAm9s8QF+Kgi39DZ5DH2/CvOD/IQQkA Xmb6JjmnvvrdN5ADzn0JGxE/qeYTp50l+hb5KnNmowM7DtXe7YQTHq77OJVWHsrfJEIO QxOk5sAqDS+XcbI7dfgi9LFB+ezFr0XR4sYLZ5/nfIaku/JqtYUeqSReWXYTU4leG16M NdHAKhpSmNSUenAQubCKy0+d/XhCQVmwh7sh9xC7t6mZscsHtaEzR5MNhJ+TT2/E+IWW Iy3fC1giiwXDkTC7885U5wgmBAKnF4q0VjdoBB22iKQBCry1XaYYSCXdv0BoyXj81u0W zctA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762078295; x=1762683095; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=pz+wEmKfTrOTMZOdD8+HrqOt1hT/x80CpuSlxMlQTc0=; b=LUfCDpGWrjI7YO8H3+i2x04SjVYgqZ6nxwXBAHnrqQM06JsKS6nrkpWg8bvRys72ZL VjmsZeyky4VlXp6kQP6PYXnn0RlMSzEGYIOY4oRFxMO/7Z26dTQj9/KuFpVzZ3NuK2/a B39AGF3BGvy67IFaeiNn4VS2fHeJVqXjMPXAOemLU7n4MH71gj7Fbavv6q7BcZwmrk+5 NduzErC/RrAAGQD4OAMgfVJ6XtkgHL3SDcV0a7H21LFs6lbQSQuUWKQYTZEzz0IdBUJQ oCA1m4Gjv6EcTZhV4OY/sROMqzDfO4GGnFrxF84Ex1LJvFC7mXfZ49ZqBmnzC5X+fVmM jXSw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762078295; x=1762683095; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:x-beenthere:x-gm-message-state:sender:from :to:cc:subject:date:message-id:reply-to; bh=pz+wEmKfTrOTMZOdD8+HrqOt1hT/x80CpuSlxMlQTc0=; b=f4FyB3pZwQjYQssGq2WYXxVOEol6QYEKZcAOAjUBOlmLeK6iV1eQDcLE3xK/GDIQ2O y2uIt1oTZZAWFjl6Gxk/TH89NKmnk8zW8weBFjEJEDgcw736jfXAqx0//35p/jAQcvBq P7dofaBusqI35H+7kM2aj/LK8BTsCEZJQkn7WplboALUCUvcBXLlyNlEeGWcVuY7mIFh eKd4tS+RIO0u0oqKX14+O7dwRGS1QIx77CCG3l8Xnu9zWBp6VopXoTr/hkn18bpzRD72 7AfBEUzVEi20yBaXsyAIjFcTZHzc+I3Fet5SQtK4foGjt8+BZtcsILl+5zGILgIBpAtH byow== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCU78ly3r3NxhgfQNkyfzSVfZD4J8eaUFg/LkWj+zLmfLuvjx2wKaZC5rLG2GFEZKxNXit0UjibTKDrp@gnusha.org X-Gm-Message-State: AOJu0YywoR6zTvfttSIlhaaH8t0P+j+e6UErrsMBaMlg8AhdqqvuJpfX VqLKuoiarsmXquUq1p7SnIJOsvQxwP4ZhDYKuLRDoHQeO1X4EknttWtA X-Google-Smtp-Source: AGHT+IGCWdjjaQT2PC/dkJXGiYQshpGqNHdZ5AOREI9s1ydFZq6num/6/t5DmVNv91RitEZzqg6jwA== X-Received: by 2002:a05:6871:4e42:b0:315:c0bc:4bb8 with SMTP id 586e51a60fabf-3daca006117mr4980772fac.2.1762078294909; Sun, 02 Nov 2025 02:11:34 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+YlpSl9QIrjVMdYvG5cnL2Vxz3q7vCQYPTChUkCHJYCBA==" Received: by 2002:a05:6870:f10e:b0:31d:8f7d:c062 with SMTP id 586e51a60fabf-3d8b5fb9705ls1499368fac.0.-pod-prod-06-us; Sun, 02 Nov 2025 02:11:30 -0800 (PST) X-Received: by 2002:a05:6808:80b4:b0:43f:2ab7:345a with SMTP id 5614622812f47-44f95f7ce58mr4352898b6e.37.1762078290303; Sun, 02 Nov 2025 02:11:30 -0800 (PST) Received: by 2002:ab3:61b6:0:b0:2cb:c6e3:5608 with SMTP id a1c4a302cd1d6-2d0b7fd0598msc7a; Sun, 2 Nov 2025 01:12:10 -0800 (PST) X-Received: by 2002:a2e:a555:0:b0:376:45a3:27c9 with SMTP id 38308e7fff4ca-37a18d9f61emr26633001fa.10.1762074727463; Sun, 02 Nov 2025 01:12:07 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1762074727; cv=none; d=google.com; s=arc-20240605; b=cYBg2jJjfwolo8OyENbKbO5h/E3xBoozF0hlkLGMu2aijq2iAcVg/wwlJy/dYW4fFg 9sspFNYX4e2LThLW+XC3NCorVw0AqmEcnBacDuTJEK2AvjqmaYCBsQoVH2+pwIBQ1L+x Rw0XZ5DyTGZtyrvE2/iIUzPUO0y9mbd8G58s2R7bJh/Q3HYz87yv3+hsKREBrn3FDPSc nCgLfb/TY6x1T4ybWFjoP26+GShdMGp9IyJPF8zEfAK9Ly7BloPLYCawtIZKK+RGga+E /XytXTOzGEYUZV7S6rYqBvPwmQe5ATcwYW6GBjXqgQ1h8gQsveFyRn/ATmKY2DQJ+SzF CKtw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=8G+O9sXeivT8GJk/GxCOxQIOqG4iIlqAawRMPamaJB0=; fh=zfrgopOiIZUyW/QOQMW3tlf+B0T0p2fpIoXRbxgb3Y8=; b=HgNO4DICXAPm8j/8VT6X8VcVOMWiyU3IChL0lQLT2g9aCv4jREPVWR8HY+nopCucdd mtvZZFLvjW1Rxj2s8d/nml8leQSxmH4fHKPUlV0SDO7/rstjgQFCKA8q3H/hQBH8uacD A7CYt7dZwCzkV9sbeY/6t46CDUeIL9GO/U+YeRTCyUlLEsZirOhcJlkjAcztaZa7F/r7 qliQUcY5DOE42uD2ZNwPpQvZzGK33mzhQUQ4tuxyuEUOpUGAwG3bwx1jJbq+tWp/qrH4 y2un4cFt/TwbGAjBp0UNuzQhDkjYRQGzlbVo1/6USWdLePIi5qSQCu0jppeHNBPRJx6O PMbw==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=bW5BMrg4; spf=pass (google.com: domain of garlonicon@gmail.com designates 2a00:1450:4864:20::52a as permitted sender) smtp.mailfrom=garlonicon@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com. [2a00:1450:4864:20::52a]) by gmr-mx.google.com with ESMTPS id 38308e7fff4ca-37a1c019dbasi1802491fa.3.2025.11.02.01.12.07 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 02 Nov 2025 01:12:07 -0800 (PST) Received-SPF: pass (google.com: domain of garlonicon@gmail.com designates 2a00:1450:4864:20::52a as permitted sender) client-ip=2a00:1450:4864:20::52a; Received: by mail-ed1-x52a.google.com with SMTP id 4fb4d7f45d1cf-6407e617ad4so3787562a12.0 for ; Sun, 02 Nov 2025 01:12:07 -0800 (PST) X-Gm-Gg: ASbGnctgjEe8qmGmFAcYN26g4Ou+6OE91m9bFcg4d9rXL94XaAZgF/8hiqLP/ybFaQU +PjYqmCm6S7BgkdxzV9Sd0JaNSu5+0xyhcYaT6/TwT6jODPIxED1/DqIfHNdJv0DdtkyBk+q1mI ILNN2ILeizzbvY6trHksjO6eEQ7yYP4Nn5mYhiKCEBmkM3cZboGgMYr8PRYOvp5PuBHWV7lSU5t h86iE9qOlwAHcI8j+wytadr2HEkAvKWqAerbPthlKFiA1RVhslNRj2qCQ3S7nOBBbLmcKs= X-Received: by 2002:a05:6402:1012:b0:640:9611:99d3 with SMTP id 4fb4d7f45d1cf-64096119e76mr2972206a12.18.1762074726336; Sun, 02 Nov 2025 01:12:06 -0800 (PST) MIME-Version: 1.0 References: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com> <781840dd-b633-4d87-b05d-d389c6374d63n@googlegroups.com> In-Reply-To: <781840dd-b633-4d87-b05d-d389c6374d63n@googlegroups.com> From: Garlo Nicon Date: Sun, 2 Nov 2025 10:11:55 +0100 X-Gm-Features: AWmQ_bmUXEEy_1Qif2N6IZNu2Mb4kRR8YYJUhmV7GpblSrvp7KwbcjqBUvmfcV4 Message-ID: Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr To: "waxwing/ AdamISZ" Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000218c3e064298fe89" X-Original-Sender: garlonicon@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=bW5BMrg4; spf=pass (google.com: domain of garlonicon@gmail.com designates 2a00:1450:4864:20::52a as permitted sender) smtp.mailfrom=garlonicon@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) --000000000000218c3e064298fe89 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > 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=3D"This is a test of storing data i"=3D0x5468697320697320612074657374206f662073746f72696e6720646174612069 k=3D"n private keys inside signatures"=3D0x6e2070726976617465206b65797320696e73696465207369676e6174757= 26573 P=3Dd*G=3D02A2EF730B26A905A7D91940E3A512C5771D8BC8BCCA153D714E328043856CBB2= B R=3Dk*G=3D02E19FCA1025CFD67409309E2B1711D723BFB67EC520917D9A0AD9432414DA0D0= A 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=C5=82= (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 x= or > 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 t= o > *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 an= d > 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 the= y > 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 f= or > 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 generou= s > 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 ar= e > 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 signature= s; > 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 li= ke > a block hash. Notice that if my note [1] did not apply, then all the abov= e > 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=E2=80=AFAM UTC-3 Garlo Nicon wrot= e: > > > 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=3Dk*G > P=3Dd*G > k=3Dfirst_chunk_of_data > d=3Dsecond_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 practic= e. > 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-d389= c6374d63n%40googlegroups.com > > . > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= CAN7kyNgyoA5rb8hYuxai6bSaPdon%3Dy%3D9Z%2BdAfqP6Mf%3DPyniJLw%40mail.gmail.co= m. --000000000000218c3e064298fe89 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
> Can you let me know how you're getting 66%+?
<= br>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 a= ll values have the same size.

Then, to get 70% or more, grinding s-v= alue is needed, which is doable, if you want to for example grind two or th= ree bytes of s-value, and stop there. But let's assume, that you want t= o make it as fast as possible, so you don't grind anything, and then st= op at 66%.

> Maybe write out concretely what the data-reader woul= d be doing?

I already told you, when I said "known plaintext at= tack". 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 u= sers store transactions inside OP_RETURNs, and they use ASCII hex represent= ation. If they would use binary encoding, then they would save 50% space. B= ut people simply don't care.

And the similar case is possible he= re: if you want to store random data, then it is hard to use this method. H= owever, 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 ea= sily guessed, then the security of the keys, is comparable to the brainwall= ets.

Which means, that you can just put your data into the private k= ey of the user, and a "signature nonce" (which is nothing else, b= ut yet another private key, placed on secp256k1). And then, if you know, th= at 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.
<= br>So, let's say that you want to encode 64 bytes in a signature:

d=3D"This is a test of storing= data i"=3D0x5468697320697320612074657374206f662073746f72696e672064617= 4612069
k=3D"n private keys inside signatures"=3D0x6e207072697= 6617465206b65797320696e73696465207369676e617475726573
P=3Dd*G=3D02A2EF73= 0B26A905A7D91940E3A512C5771D8BC8BCCA153D714E328043856CBB2B
R=3Dk*G=3D02E= 19FCA1025CFD67409309E2B1711D723BFB67EC520917D9A0AD9432414DA0D0A
<= br>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 pattern= s. If something is an ASCII string, then 1/8 bits are cleared, and it is kn= own, which ones should be set to zero. If it is in English, then the entrop= y is even lower. Which means, that the private key is not directly "le= aked", 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 trans= ferred, and then, you can pass the data directly, and say: "See? You c= an 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 y= ou 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 reall= y say, that the keys are "leaked", because you need to know "= ;something" about the plaintext inside private keys, or about its form= at). And it is good for spammers, because then, funds can be safely confirm= ed, and later revealed, that "hey, I encoded that data here, by wastin= g 3 MB of block space, to encode 2 MB of ASCII strings, here is your NFT, t= hat you can buy here".

sob., 1 lis 2025 o 16:47= =C2=A0waxwing/ AdamISZ <ekaggata@g= mail.com> napisa=C5=82(a):
Hi Garlo Nicon,

Before I answer y= our point I want to mention (to readers): probably some things remained tac= it 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 xo= r 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, in= stead 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 persi= stence 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/c= aveats but, basically).

2. All of the above theore= tical analysis doesn't work for ECDSA *as an algorithm outside of Bitco= in*. 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 o= r 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-unemb= eddability-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 t= he message (indirectly), at least usually, in Bitcoin (except sighash_noinp= ut type stuff which isn't live), so you can't put hello world in th= e 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, th= at's a generous measure). Again, I am ignoring grinding which always ad= ds a bit more.

Anyway, you say:

> So, I guess it is a spectrum: something like 70% efficiency mean= s, that you need "known plaintext attack" to get the data. And th= en, you can use less and less bits per public key, to make it arbitrarily w= eaker. 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 t= hink it's an interesting idea to use lattice attacks but I can't fi= nd 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 suc= cessful, 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 signat= ures; doesn't change the situation).

So you em= bedded 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 n= once; you may as well just reveal all of it, either by repetition or as not= ed 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 t= he d values" but as per above I don't see it. Maybe write out conc= retely 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 t= o the same key (or, you can verify, to check). In bitcoin the pubkey is nev= er tacit, it's always published in the scriptPubKey or scriptSig or wha= tever, 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) tupl= es).

Cheers,
Adam

On Friday, October 31, 2025 at 10:25:30=E2=80=AFAM UTC-3 Garl= o Nicon wrote:
> i= f 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=3Dk*G
P=3Dd*G
k=3Dfirst_chunk_of_da= ta
d=3Dsecond_chunk_of_data

And then, keys are "weak&= quot;, because people can use "known plaintext attack", to get th= em. 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-2= 56 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 m= any bits I need to leak, to make it breakable by lattice attack".

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.googl= e.com/d/msgid/bitcoindev/781840dd-b633-4d87-b05d-d389c6374d63n%40googlegrou= ps.com.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.= com/d/msgid/bitcoindev/CAN7kyNgyoA5rb8hYuxai6bSaPdon%3Dy%3D9Z%2BdAfqP6Mf%3D= PyniJLw%40mail.gmail.com.
--000000000000218c3e064298fe89--