Date: Mon, 18 Dec 2023 22:43:48 +0000
To: Nagaev Boris <bnagaev@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: yurisvb@pm.me
Message-ID: <1aHuuO-k0Qo7Bt2-Hu5qPFHXi4RgRASpf9hWshaypHtdN-N9jkubcvmf-aUcFEA6-7L9FNXoilIyydCs41eK4v67GVflEd9WIuEF9t5rE8w=@pm.me>
In-Reply-To: <CAFC_Vt7B1oV0_uAwKe3NQLWE2jdQ_MF1W4fnVqkf8s=YHyfVyQ@mail.gmail.com>
References: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me>
 <CAFC_Vt5xqhuXjNVeSGE2Pn=0N0MuB6pOnREzGhSQSpk+hTUUSg@mail.gmail.com>
 <-lH1AcjRwuxfuqLPFOh_oga10Qm12fb7Se9imDeS5ft6CU3y8KTQa3tBP0twJJBFSHgj7FC8EIxvEser3oZdWvkeitRwERQl_cCdgAWtbTU=@pm.me>
 <CAFC_Vt7B1oV0_uAwKe3NQLWE2jdQ_MF1W4fnVqkf8s=YHyfVyQ@mail.gmail.com>
Feedback-ID: 15605746:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature";
 micalg=pgp-sha256;
 boundary="------b701f3bdd13ced714986bd6f94bf3f4db2563dbd8f4cb2758725eeef8fecdd6d";
 charset=utf-8
Subject: [bitcoin-dev]  Lamport scheme (not signature) to economize on L1
Precedence: list

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------b701f3bdd13ced714986bd6f94bf3f4db2563dbd8f4cb2758725eeef8fecdd6d
Content-Type: multipart/mixed;boundary=---------------------621ec6e465cff0467f1a4463ed593878

-----------------------621ec6e465cff0467f1a4463ed593878
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;charset=utf-8

I beg to disagree: key owner broadcasts first bundle (let's call it this w=
ay) so that it is on any miner's best interest to include said bundle on t=
heir's attempted coinbase because they know if they don't any other compet=
ing 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 harde=
r than the double-spending attack, by definition, it's (much!) more than h=
ard enough.

Consider a 12 bytes =3D 96 bits Lamport hash link (Less than half a Schnor=
r signature). Assume a cracking power of one order of magnitude higher tha=
n 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 (weake=
st-link argument); 2) Memory-hard hashes, by definition, are ASIC-resistan=
t in the first place (so, being less efficient than ASICS, the CPUs necess=
ary to match that hashing power would be far *more* costly than today's to=
tal global mining hardware). In other words, we are giving away the hardne=
ss 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 poss=
ible pre-images gives a probability of approximately 2^-6 < 0.02. This doe=
sn'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 t=
arget UTXO), unlikely the 50%+epsilon attack, in which the adversary may b=
lock whomever they want from ever having a transaction mined. Again, we ar=
e giving away over 11 days for good measure to safeguard against loss of c=
onnection.

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. succes=
s)) =3D 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 w=
ith more scale than that necessary for double spending. Even at that unrea=
listically large scale, however, and even assuming your adversary would ga=
in 1000 times more utility than what they make their victim loose, it woul=
d 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=E2=80=AFPM yurisvb@pm.me wrote:
> =


> > Most Wallets implement BIP39 with 12 words, which corresponds to 128 b=
its 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 premis=
e 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 u=
nder some conservative assumption and allow for the alleviation of log2(N)=
 bits from your key. It's widely adopted in passwords (Argon2, for instanc=
e, being the 2015 Password Hash Competition) since human memorization of p=
assword is a critical weak link in security and UX. BIP39 itself resorts t=
o PBKDF2 with 2048 iterations with the same goal, even though it's not mem=
ory-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 i=
s 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=E2=80=AFAM 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-imag=
e of hash is, in fact, successfully broadcasted before maturity, commitmen=
t, the only ECC signature in this protocol is discarded, and only two Lamp=
ort hashes end up being buried at L1.
> > =


> > > Two SHA256 hashes are 64 bytes in total, the same as one schnorr sig=
nature.
> > =


> > > > To push economy even further, we could implement a memory-hard has=
h 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
-----------------------621ec6e465cff0467f1a4463ed593878
Content-Type: application/pgp-keys; filename="publickey - yurisvb@pm.me - 0x535F445D.asc"; name="publickey - yurisvb@pm.me - 0x535F445D.asc"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="publickey - yurisvb@pm.me - 0x535F445D.asc"; name="publickey - yurisvb@pm.me - 0x535F445D.asc"

LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4c0JOQkYySmpSWUJDQUM1MXlo
K0s0MmF0c0V5MGdCTmgvaklXR1hzQnRFLzdJOGFuUmZkZTcvcWdHeXkKbEx4TXFZRE1OelUwN3c5
Z3VINllKRDdWdzNaUmxTVGVqNU9Hc2laOFJ2OUp4YXBYc0MxeDMrdHhOQkFQClYyVml1MVpsMnhK
Y29sTDkrem9SUmhmU25lVDVaZm1IQlpBSklKbmhOdU80ajhrRi9iNDRFaEZ3NkwvTgpGbE9rK1VC
SkVvS0FFQWttd09aWWpVTDd6MStRdzJBZkJIVGVwNFMzYmY4SmZMNDFOUVJsRnBSa3MrSkMKTjNa
c0ozZmZhNURjWjVqTGgyK2k5Mlg2eE8yVW5nM0hLYXhJYTVtbzB3cGVvQ1JQdUxNRjE2cjVQelJ4
CjJmNldzZVlUbWVmZWVYUGUzZEhyTTR4ai9ndHpBRGNxaFd6VVZLM21ZNTdPTXhVYjJ4MWdqZ1Z6
QUJFQgpBQUhOSFhsMWNtbHpkbUpBY0cwdWJXVWdQSGwxY21semRtSkFjRzB1YldVK3dzQjFCQkFC
Q0FBZkJRSmQKaVkwV0Jnc0pCd2dEQWdRVkNBb0NBeFlDQVFJWkFRSWJBd0llQVFBS0NSQXYzelY4
UzhOTVZkTkRCLzlRCnZRRlpZNkRzR3FMOTlkKzI2QjdHYmRCb0VjenUxL2NqTVpNdE9QeW9nSElF
eXllalR3R1RVN3ZYNEpWZQozRHZnbnd4U2xIYjQ2dDU2VGV3OU5rZ2V4MmFIb0hGRnJBd3MraTVa
ajdZN2lhL2l2RVozZE1KR3dNSUoKeVlQS08rdG1ockxNYWlSSFdnUnhtSG5mRnhUY1dFQ1dSZEk3
dDRJWFp3Rm9QN2Z3TVVVVXQrV3NTbzJSCnJhUVZEL3NTL2F2TlF5T2h6YTlLcVBQNjBZY3B2RUtj
UXArL2hyTjRRcFhVSkxiaDFZMVlqeUhlbDhnQgpRa3p2QzUwUjVxTzRlY2xxSy9FMEhESnlDWmZN
TThkV2o0REJrTWN2SzlsYjB5b3ZRMDFFTXp1NkU1NEcKYjZ0VFp1bktQTVpVd1J1SW5FY0hHMjV0
azdWUEM4clJTU0hqeDhTT3pzQk5CRjJKalJZQkNBQ3RiUWdNCldRSnMvTVdZbDR2THRLSlhYbFlS
T2h1YkVWbjRjTFdZSmVFWHpzSllCQWRlNWh0QlEzc212UjJ2NnVJegptejJpaXFsSkVVdmYwY2xM
WS9QVExoSGVTbWE5VTRodzRaRDNZKzV6WWxINURza2l1N3lLZTdIVmpEVmkKd1FJN25acWRvanJs
dDhCZENiOVNMaXRNaFRvR1crS2E1VCtUOWNmbWthMk1qa3pRSFBNTEJtdVJ6a2V2ClBkZFF6M0xB
MjMzZDNHREVTZklCYy91OC9YelBUNkZTZ3MzSEh4OEFJbFdQbEJaYmh6WmpQNlRLclRNRQpOSEtK
cmxTRlZKclErL25QU28ya0VSL0VDczF0aUJEY0JkamVPYWx6LzdRVWN0Rnp3NGdjS0RtMGpUeEkK
cVhWVlV3a2tuRkM4NDZMTjNBT2p0UWRyOVV3czVsTzhkeXBGQUJFQkFBSEN3RjhFR0FFSUFBa0ZB
bDJKCmpSWUNHd3dBQ2drUUw5ODFmRXZEVEZXS2VBZ0FxRXN1QXJMZFprYXBvZDI3K2hpcHZZNUcr
eVRLQW1NMApIVlhmQzJiMVdtNXQwQXhOVXVkMlJ1OTE1MHA3V09CRXpXYkxnNXdzOTc1M296dlZi
cFpIQU9uVGZOeXoKUUR5QWhmZ1hNQjIvdzRERXEwT2tlQVBRNXhsQWtISDZpUW1hSkZiYy9FRjRX
ZWZWeE92MnNRNDlRNks5Ci9Bb1FROG54RVh1RzRidXVrclEwTGVlTVAzNEdMWUhYK2JvWENHQmxI
MGhiZm5kc3VQbEdqYnBnWVErdQplclJGTlB4N1JtSWtnQjJ0WmhwZkZ3VGtid1c2TVFmWDM5Z3F1
SitwVEVKUnA5UmpJVjFZU2txSjZJUkgKQkc4eFBocGgzT3huaWJyWkdlbGdtakpNM2QwM1k5OSs3
OXBvdTRlY09BeWYyTHMrMVVTY2NDTzA2YnI4CldlcjJ3cmI0WXc9PQo9aHJheAotLS0tLUVORCBQ
R1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCg==
-----------------------621ec6e465cff0467f1a4463ed593878--

--------b701f3bdd13ced714986bd6f94bf3f4db2563dbd8f4cb2758725eeef8fecdd6d
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: ProtonMail

wsBzBAEBCAAnBYJlgMsQCZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL
w0xVAAD/TAf+LEBLLfUxDy5yiw7jSBCLxNfrCXzyqUVs820hV0u6m7hGAGpN
1zWRVKWRqn81dzmv8xj0qcY/P8P3t2GlRb36jZSG9CzG5Au+Kt8zhZIdI5xf
6AtxlIFLMC8bCk5JIekfkwcjDQvwb7QrCQtdtB7Y5JGKkV89zbEfBih+Me0m
wXUe/FE9zaZyQvy0C+/C8DJm2MwCB4uUci9szv0ab+lsF6m9vHLWQPcuJ8xH
be51xA94Q5YN/UhDEAbQz0GkFiWij+mheWb8YyHcCVghN5JwK4JxOYNgfyJb
iaTFhjxaHxL91aER7zwRYzyJznOeoXAab7/WlPkfxPewHUHTwnQyBA==
=YBXU
-----END PGP SIGNATURE-----


--------b701f3bdd13ced714986bd6f94bf3f4db2563dbd8f4cb2758725eeef8fecdd6d--