Date: Thu, 21 Dec 2023 16:07:27 +0000
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 Nagaev Boris <bnagaev@gmail.com>
From: yurisvb@pm.me
Message-ID: <I11FZ_ZpfwpnQBh5hbBZMHsQt_cKwF9My49X4-MMRIYvaJEoIwta-GEaDNN1EtQxST4gQFAvqfOZElDvIpPrlAVknyN52IMnJKNy5kT8sUE=@pm.me>
In-Reply-To: <CAFC_Vt6vqZkeenfrsqSj4T3+4+L2KMam0o0FeWJ4VzBEWE=HfA@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>
 <1aHuuO-k0Qo7Bt2-Hu5qPFHXi4RgRASpf9hWshaypHtdN-N9jkubcvmf-aUcFEA6-7L9FNXoilIyydCs41eK4v67GVflEd9WIuEF9t5rE8w=@pm.me>
 <CAFC_Vt644Wqn7EcvoZwFscPMov8T5kO9ss_QRgNgVNir-bBA0Q@mail.gmail.com>
 <ue8nChOuMtyW_JM-WxikLpWUSn9I99UHI5ukFVfLOEmQtCo4noetzyVKercbrwjr_EqNotDsR1QZ0oijMu11TO2jpEjlJF71OjLlNoZ-00Y=@pm.me>
 <CAFC_Vt5PcqqcREJ67Jzcg=K+Agd02a9f5uSit8LwkYHshbvF7A@mail.gmail.com>
 <HG9-9VDKRd3-0v0x9QP05_Cjyk9Y3UW-94A1RHsT3xMQYmb7Y6sk9-wTUlqVZzm6ACigM7aM-B6NB-z6jVCCXhQIGEYkEcBKryzP587FlIo=@pm.me>
 <CAFC_Vt6vqZkeenfrsqSj4T3+4+L2KMam0o0FeWJ4VzBEWE=HfA@mail.gmail.com>
Feedback-ID: 15605746:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature";
 micalg=pgp-sha256;
 boundary="------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e";
 charset=utf-8
Subject: Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
Precedence: list

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e
Content-Type: multipart/mixed;boundary=---------------------988878b0db437c87187a08e65db1d5f7

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

You are right to point out that my proposal was lacking defense against ra=
inbow-table, because there is a simple solution for it:
To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting LSIG=
, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only unknown =
by the builder of rainbow table while they made it, which is the case, sin=
ce here we have 8*32=3D256 bits for LSIG, and the entropy of ECCPUB in the=
 second.

With rainbow table out of our way, there is only brute-force analysis to m=
ind. Honestly, Guess I should find a less 'outrageously generous' upper bo=
und for adversary's model, than just assume they have a magic wand to conv=
ert SHA256 ASICS into CPU with the same hashrate for memory- and serial-wo=
rk-hard hashes (therefore giving away hash hardness). That's because with =
such 'magic wand' many mining pools would, not only be capable of cracking=
 2^48 hashes far within the protocol's prescribed 48 hours, but also 2^64 =
within a block time, which would invalidate a lot of what is still in use =
today.

Please, allow me a few days to think that through.

YSVB

Sent with Proton Mail secure email.

On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris <bnagaev@gmail=
.com> wrote:


> On Tue, Dec 19, 2023 at 6:22=E2=80=AFPM yurisvb@pm.me wrote:
>
> > Thank you for putting yourself through the working of carefully analyz=
ing my proposition, Boris!
> >
> > 1) My demonstration concludes 12 bytes is still a very conservative fi=
gure for the hashes. I'm not sure where did you get the 14 bytes figure. T=
his is 2*(14-12) =3D 4 bytes less.
>
>
> I agree. It should have been 12.
>
> > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly=
 right and I failed to realize that. To lessen the exposure, and the risk =
of miner of LSIG, it can be left to be broadcast together with LAMPPRI.
> >
> > 3) I avail to advocate for economizing down the fingerprint to just 12=
8 bits for the weakest-link-principle, since 128 bits is a nearly ubiquito=
us standard, employed even by the majority of seeds. Not an argument again=
st plain Schnorr, because Schnorr keys could use it too, but, compared wit=
h current implementations, we have that would be 20-16=3D4 bytes less.
>
>
> I think that the digest size for hash should be 2x key size for
> symmetric encryption. To find a collision (=3D break) for a hash
> function with digest size 128 bits one needs to calculate ~ 2^64
> hashes because of the birthday paradox.
>
> > 4) [Again, argument against plain, because it cuts for both sides:] To=
 economize even further, there is also the entropy-derivation cost trade-o=
ff of N times costlier derivation for log2(N) less bits. If applied to the=
 Address, we could shave away another byte.
> >
> > 5) T0 is just the block height of burying of LSIG doesn't need to be b=
uried. T2 can perfectly be hard-coded to always be the block equivalent of=
 T0 + 48 hours (a reasonable spam to prevent innocent defaulting on commit=
ment due to network unavailability). T1 is any value such as T0 < T1 < T2,=
 (typically T1 <=3D T0+6) of user's choosing, to compromise between, on on=
e hand, the convenience of unfreezing UTXO and having TX mining completed =
ASAP and, on the other, avoiding the risk of blockchain forking causing LA=
MPPRI to be accidentally leaked in the same block height as LSIG, which al=
lows for signatures to be forged. So this is 16 bytes less.
> >
> > Miners would keep record of unconfirmed BL's, because of the reward of=
 mining either possible outcome of it (successful transaction or execution=
 of commitment). Everything is paid for.
> >
> > So, unless I'm forgetting something else, all other variables kept equ=
al, we have 20 bytes lighter than Schnorr; and up to 25 bytes less the cur=
rent implementation of Schnorr, if items 3 and 4 are implemented too. Alre=
ady we have a reduction of between 21% and 26%, while, so far, nobody in t=
he mailing list has disputed how 'outrageously' conservative the 12 bytes =
figure is.
>
>
> 26% reduction of block space utilization would be great, but the price
> of relying on 12 bytes hashes (only need 2^48 hashes to find a
> collision) is too much for that, IMHO.
>
> Another consideration is about 12 byte hashes. Let's try to figure out
> if they are resistant to rainbow table attack by a large organization.
> Let's assume that the rainbow table has a chain length of 1024^3 (billio=
n).
> What storage size is needed? 2^96 * 12 / 1024^3 =3D 900 exabytes.
> Both chain length and storage size seems prohibitively high for today,
> but tomorrow the hash function can be optimized, memory can be
> optimized, storage can become cheaper etc. And this attack may be
> affordable for state level attackers.
>
> > Any other objections?
> >
> > YSVB
>
>
>
> --
> Best regards,
> Boris Nagaev
-----------------------988878b0db437c87187a08e65db1d5f7
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==
-----------------------988878b0db437c87187a08e65db1d5f7--

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

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

wsBzBAEBCAAnBYJlhGKeCZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL
w0xVAADHBQf/ftQ7PWwKqJh1C5E5RA0Xcpd7G5mHyn/tMV1RDyU2fm+pIdUM
9HDJISW7HZ2JMNd5EBvSLGERGY7707ArFm/+IQgYtkaXrXX4hPQ0awa8lKAz
3nKwWkpfXtQd0NJarqB4R9+ks6/VoxoTLwYoI6aKP6pTMNo5KdsUxDuxWdvu
ijo1HvZmsidbB47vpUx12Nck1NOjivi60E9LHy4xKE9Tbj6uQiMovR2c324i
cY2+bwZA0H5CzK3Qvp9U24C+0P2ZP53MX1289CD4gMTTVI7+jkN5iu9F5AgB
Qnfs4rhBusXFd14MEZePaxgQ4JtwzQWaVkW/iZHI9hvdu51eusmCGw==
=7+Rr
-----END PGP SIGNATURE-----


--------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e--