From: yurisvb@pm•me
To: Nagaev Boris <bnagaev@gmail•com>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
Date: Mon, 18 Dec 2023 22:43:48 +0000 [thread overview]
Message-ID: <1aHuuO-k0Qo7Bt2-Hu5qPFHXi4RgRASpf9hWshaypHtdN-N9jkubcvmf-aUcFEA6-7L9FNXoilIyydCs41eK4v67GVflEd9WIuEF9t5rE8w=@pm.me> (raw)
In-Reply-To: <CAFC_Vt7B1oV0_uAwKe3NQLWE2jdQ_MF1W4fnVqkf8s=YHyfVyQ@mail.gmail.com>
[-- Attachment #1.1: Type: text/plain, Size: 6061 bytes --]
I beg to disagree: key owner broadcasts first bundle (let's call it this way) so that it is on any miner's best interest to include said bundle on their's attempted coinbase because they know if they don't any other competing miner will in the next block.
Once more I think it's worth mentioning the principle of weakest link: if cracking this Lamport chain within the stipulated few blocks time is harder than the double-spending attack, by definition, it's (much!) more than hard enough.
Consider a 12 bytes = 96 bits Lamport hash link (Less than half a Schnorr signature). Assume a cracking power of one order of magnitude higher than the current global hash rate of say 10^21 H/s. Already our assumption is outrageously pessimistic for more that two reasons: 1) The whole premise of Bitcoin being secure is presumptive unfeasibility of that attack (weakest-link argument); 2) Memory-hard hashes, by definition, are ASIC-resistant in the first place (so, being less efficient than ASICS, the CPUs necessary to match that hashing power would be far *more* costly than today's total global mining hardware). In other words, we are giving away the hardness of the hash.
Let's assume a generous window of 1M seconds, so 10^27 hashes. Multiplying that by log2(10), we have shy of 2^89 hashes (actually it's 2^ 'shy of 89', but again: erring on the side of safety). That divided by our 2^96 possible pre-images gives a probability of approximately 2^-6 < 0.02. This doesn't sound very impressive, but an important thing to have in mind is that this attack would destroy utility only of its specific victim (owner of target UTXO), unlikely the 50%+epsilon attack, in which the adversary may block whomever they want from ever having a transaction mined. Again, we are giving away over 11 days for good measure to safeguard against loss of connection.
More importantly, the economic viability of that attack: if your UTXO has less than ~50 times the cost of that operation, which we could lower bound for, say, half of blocks rewards (again, generously assuming 100% ROI for mining). Let's be generous once again disregard mining fees, which would give us (block reward)*(seconds)/((1+ROI)*(second per block)*(prob. success)) = 6.25*10^6 / (2*600*0.02)BTC ~ 260416 BTC.
So mine is an argument of economic viability: clearly adversary's economy of scale is positive, and it doesn't make sense to consider an adversary with more scale than that necessary for double spending. Even at that unrealistically large scale, however, and even assuming your adversary would gain 1000 times more utility than what they make their victim loose, it would still be unworthy to conduct such attack to an UTXO of less than 1K BTC.
In retrospect, I'm beginning to think that 12 bytes is rather an overkill.
YSVB
Sent with Proton Mail secure email.
On Monday, December 18th, 2023 at 6:48 PM, Nagaev Boris <bnagaev@gmail•com> wrote:
> On Mon, Dec 18, 2023 at 2:22 PM yurisvb@pm•me wrote:
>
> > Most Wallets implement BIP39 with 12 words, which corresponds to 128 bits of entropy + 4 of checksum (so really only 128 bits).
> >
> > 2 times that would get even to one Schnorr signature, as you say.
> > Going lower than 128 per hash is, IMO admissible under the same premise of memory-hard hashes like Argon2, Scrypt, CryptoNight, Catena, Balloon Hashing, or Krypton8 (the latter of my authoring, a fully homomorphically encryptable memory-hard hash). You make hashing N times more time-costly under some conservative assumption and allow for the alleviation of log2(N) bits from your key. It's widely adopted in passwords (Argon2, for instance, being the 2015 Password Hash Competition) since human memorization of password is a critical weak link in security and UX. BIP39 itself resorts to PBKDF2 with 2048 iterations with the same goal, even though it's not memory-hard. But there is more:
> >
> > By design, my proposed Lamport chain needs only to resist brute-force for a few blocks time, so key strength can be cheapened even further. Keep in mind that before its first transaction, the public-key of an address is not published, so the window of opportunity for brute-forcing a key with lower strength really only opens upon the broadcasting of the transaction, and closes within a few blocks time.
>
>
> IIRC, miner M1 is the only party who verifies the ECC signature in the
> proposed protocol. If M1 is malicious, he can crack the short hash of
> an address in advance (spending as much time as needed). He should do
> it twice to know the next two hashes. Then mines the first transaction
> (in which he steals coins from the address) with the first hash and
> then publish the second hash a few blocks later to finalize the theft.
>
> > YSVB
> >
> > Sent with Proton Mail secure email.
> >
> > On Monday, December 18th, 2023 at 5:45 PM, Nagaev Boris bnagaev@gmail•com wrote:
> >
> > > Hey Yuri,
> >
> > > On Mon, Dec 18, 2023 at 6:19 AM Yuri S VB via bitcoin-dev
> > > bitcoin-dev@lists•linuxfoundation.org wrote:
> >
> > > > down from 136 from ECC.
> >
> > > Schnorr signature has size 64 bytes (serialized format consists of x
> > > coordinate of R and of s, 32 bytes each).
> >
> > > > The whole point is that, in the typical use case in which pre-image of hash is, in fact, successfully broadcasted before maturity, commitment, the only ECC signature in this protocol is discarded, and only two Lamport hashes end up being buried at L1.
> >
> > > Two SHA256 hashes are 64 bytes in total, the same as one schnorr signature.
> >
> > > > To push economy even further, we could implement a memory-hard hash like Argon2 to do the same entropy-processing trade-off already utilized for passwords, so we could have hashes of, say 12 bytes, making it 24 in total
> >
> > > 12 bytes security for spending bitcoins is not enough, is it?
> >
> > > --
> > > Best regards,
> > > Boris Nagaev
>
>
>
>
> --
> Best regards,
> Boris Nagaev
[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]
next prev parent reply other threads:[~2023-12-18 22:44 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-12-18 1:37 yurisvb
2023-12-18 12:29 ` Sergio Demian Lerner
2023-12-18 16:45 ` Nagaev Boris
[not found] ` <-lH1AcjRwuxfuqLPFOh_oga10Qm12fb7Se9imDeS5ft6CU3y8KTQa3tBP0twJJBFSHgj7FC8EIxvEser3oZdWvkeitRwERQl_cCdgAWtbTU=@pm.me>
[not found] ` <CAFC_Vt7B1oV0_uAwKe3NQLWE2jdQ_MF1W4fnVqkf8s=YHyfVyQ@mail.gmail.com>
2023-12-18 22:43 ` yurisvb [this message]
2023-12-19 0:45 ` Nagaev Boris
2023-12-19 14:07 ` yurisvb
2023-12-19 17:08 ` Nagaev Boris
2023-12-19 21:22 ` yurisvb
2023-12-20 21:33 ` Nagaev Boris
2023-12-21 16:07 ` yurisvb
2023-12-22 4:52 ` G. Andrew Stone
2023-12-22 15:32 ` yurisvb
2023-12-23 0:26 ` yurisvb
2023-12-29 0:30 ` yurisvb
2023-12-31 17:42 ` yurisvb
2023-12-31 19:33 ` David A. Harding
2024-01-01 10:17 ` yurisvb
2024-01-01 18:57 ` David A. Harding
2024-01-05 18:02 ` yurisvb
2024-01-05 18:22 ` yurisvb
[not found] <nvbG12=5FSi7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi=5FrWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=3D@pm.me>
[not found] ` <ue8nChOuMtyW=5FJM-WxikLpWUSn9I99UHI5ukFVfLOEmQtCo4noetzyVKercbrwjr=5FEqNotDsR1QZ0oijMu11TO2jpEjlJF71OjLlNoZ-00Y=3D@pm.me>
[not found] ` <CAFC=5FVt5PcqqcREJ67Jzcg=3DK+Agd02a9f5uSit8LwkYHshbvF7A@mail.gmail.com>
[not found] ` <HG9-9VDKRd3-0v0x9QP05=5FCjyk9Y3UW-94A1RHsT3xMQYmb7Y6sk9-wTUlqVZzm6ACigM7aM-B6NB-z6jVCCXhQIGEYkEcBKryzP587FlIo=3D@pm.me>
[not found] ` <CAFC=5FVt6vqZkeenfrsqSj4T3+4+L2KMam0o0FeWJ4VzBEWE=3DHfA@mail.gmail.com>
[not found] ` <I11FZ=5FZpfwpnQBh5hbBZMHsQt=5FcKwF9My49X4-MMRIYvaJEoIwta-GEaDNN1EtQxST4gQFAvqfOZElDvIpPrlAVknyN52IMnJKNy5kT8sUE=3D@pm.me>
[not found] ` <CAHUwRvuyhQDN5RF0ysMAJgWS2V7vv-3yHzKcLspk=5FHzQY=3Dtt2Q@mail.gmail.com>
[not found] ` <jGJvlLv4UL13U6aklzwkyRE4XRQtQSK-JZzpevPzyWQhQ4rU84I5fPDSdbtW7ehFzxkLtaOEenMMQAbHslH766qj9DGfb7QlwwXqjGsNRvU=3D@pm.me>
[not found] ` <nMFSEupHxGqdH2Z4kSNj-kufM4X=5F=5FUexnJOqC99-KlfT84adaDfPLm66vS6V8Ogphiogz1dvzFEVjM7QO=5Ft9PVR3VqNxZCIvD4C=5FSEtkDfc=3D@pm.me>
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='1aHuuO-k0Qo7Bt2-Hu5qPFHXi4RgRASpf9hWshaypHtdN-N9jkubcvmf-aUcFEA6-7L9FNXoilIyydCs41eK4v67GVflEd9WIuEF9t5rE8w=@pm.me' \
--to=yurisvb@pm$(echo .)me \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=bnagaev@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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