Date: Sat, 23 Dec 2023 00:26:07 +0000
To: "G. Andrew Stone" <g.andrew.stone@gmail.com>,
 Nagaev Boris <bnagaev@gmail.com>
From: yurisvb@pm.me
Message-ID: <nMFSEupHxGqdH2Z4kSNj-kufM4X__UexnJOqC99-KlfT84adaDfPLm66vS6V8Ogphiogz1dvzFEVjM7QO_t9PVR3VqNxZCIvD4C_SEtkDfc=@pm.me>
In-Reply-To: <jGJvlLv4UL13U6aklzwkyRE4XRQtQSK-JZzpevPzyWQhQ4rU84I5fPDSdbtW7ehFzxkLtaOEenMMQAbHslH766qj9DGfb7QlwwXqjGsNRvU=@pm.me>
References: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me>
 <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>
 <I11FZ_ZpfwpnQBh5hbBZMHsQt_cKwF9My49X4-MMRIYvaJEoIwta-GEaDNN1EtQxST4gQFAvqfOZElDvIpPrlAVknyN52IMnJKNy5kT8sUE=@pm.me>
 <CAHUwRvuyhQDN5RF0ysMAJgWS2V7vv-3yHzKcLspk_HzQY=tt2Q@mail.gmail.com>
 <jGJvlLv4UL13U6aklzwkyRE4XRQtQSK-JZzpevPzyWQhQ4rU84I5fPDSdbtW7ehFzxkLtaOEenMMQAbHslH766qj9DGfb7QlwwXqjGsNRvU=@pm.me>
Feedback-ID: 15605746:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature";
 micalg=pgp-sha256;
 boundary="------dea4fe7b6e69b5988fce1d40a8d08eaa30a617aa5122bcd6150efe1c9f173fc9";
 charset=utf-8
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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)
--------dea4fe7b6e69b5988fce1d40a8d08eaa30a617aa5122bcd6150efe1c9f173fc9
Content-Type: multipart/mixed;boundary=---------------------f4c392cefeba1a2f2d85dd1bad58f5b5

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

Dear all,

Upon second thoughts, I concluded have to issue a correction on my last co=
rrespondence. Where I wrote:

> For 2: a pre-image problem for a function
> f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format=
 of ADDRs'} X {LSIG}
> =


> (notice the nuance: {LSIG} means the singleton containing of only the sp=
ecific LSIG that was actually public, not 'in the format of LSIGs').

Please read =


"For 2: a pre-image problem for a function
f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format o=
f ADDRs'} X {s | s is 'in the format of LSIGs'}"

instead, and completely disregard the nuance below, which is wrong. I apol=
ogize for the mistake, and hope I have made myself clear. Thank you, again=
 for your interest, and I'll be back with formulas for entropy in both cas=
es soon!

YSVB

Sent with Proton Mail secure email.

On Friday, December 22nd, 2023 at 4:32 PM, yurisvb@pm.me <yurisvb@pm.me> w=
rote:


> There are three possible cryptanalysis to LAMPPRI in my scheme:
> =


> 1. From ADDR alone before T0-1 (to be precise, publishing of (TX, SIG));
> 2. From ADDR and (TX, SIG) after T0-1 (to be precise, publishing of (TX,=
 SIG));
> 3. Outmine the rest of mining community starting from a disadvantage of =
not less than (T1-T0-1) after T1 (to be precise, at time of publishing of =
LAMPRI);
> =


> ...which bring us back to my argument with Boris: There is something els=
e we missed in our considerations, which you said yourself: ironically, LA=
MPPUB is never published.
> =


> We can have LAMPPUB be 1Mb or even 1Gb long aiming at having rate of col=
lision in HL(.) be negligible (note this is perfectly adherent to the prop=
osition of memory-hard-hash, and would have the additional benefit of allo=
wing processing-storage trade-off). In this case, we really have:
> =


> For 1: a pre-image problem for a function
> f1: {k| k is a valid ECCPRI} X {l | l is a valid LAMPPRI} -> {a | a is i=
n the format of a ADDR}
> =


> having as domain the Cartesian product of set of possible ECCPRIs with s=
et of possible LAMPPRIs and counter domain, the set of possible ADDRs.
> =


> For 2: a pre-image problem for a function
> f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format=
 of ADDRs'} X {LSIG}
> =


> (notice the nuance: {LSIG} means the singleton containing of only the sp=
ecific LSIG that was actually public, not 'in the format of LSIGs').
> =


> Notice that, whatever advantage of 2 over 1 has to be compensated by the=
 perspective of having the protocol be successfully terminated before the =
attack being carried out.
> =


> For 3: Equivalente of a double-spending attack with, in the worst case, =
not less than (T1-T0-1) blocks in advantage for the rest of the community.
> =


> When I have the time, I'll do the math on what is the entropy on each ca=
se, assuming ideal hashes, but taking for granted the approximation given =
by Boris, we would have half of size of ADDR as strength, not half of LAMP=
PRI, so mission accomplished!
> =


> Another ramification of that is we can conceive a multi-use version of t=
his scheme, in which LAMPPRI is the ADDR resulting of a previous (ECCPUB, =
LAMPPUB) pair. The increased size of LAMPPRI would be compensated by one e=
ntire ADDR less in the blockchain. Namely, we'd have an extra marginal red=
uction of 12 bytes per use (possibly more, depending on how much more byte=
s we can economize given that added strength).
> =


> YSVB.
> =


> On Friday, December 22nd, 2023 at 5:52 AM, G. Andrew Stone g.andrew.ston=
e@gmail.com wrote:
> =


> =


> =


> > Does this affect the security model WRT chain reorganizations? In the =
classic doublespend attack, an attacker can only redirect UTXOs that they =
spent. With this proposal, if I understand it correctly, an attacker could=
 redirect all funds that have "matured" (revealed the previous preimage in=
 the hash chain) to themselves. The # blocks to maturity in your proposal =
becomes the classic "embargo period" and every coin spent by anyone betwee=
n the fork point and the maturity depth is available to the attacker to do=
ublespend?
> > =


> > On Thu, Dec 21, 2023, 8:05=E2=80=AFPM Yuri S VB via bitcoin-dev bitcoi=
n-dev@lists.linuxfoundation.org wrote:
> > =


> > > You are right to point out that my proposal was lacking defense agai=
nst rainbow-table, because there is a simple solution for it:
> > > To take nonces from recent blocks, say, T0-6, ..., T0-13, for saltin=
g LSIG, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only un=
known by the builder of rainbow table while they made it, which is the cas=
e, since 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 analysi=
s to mind. Honestly, Guess I should find a less 'outrageously generous' up=
per bound for adversary's model, than just assume they have a magic wand t=
o convert SHA256 ASICS into CPU with the same hashrate for memory- and ser=
ial-work-hard hashes (therefore giving away hash hardness). That's because=
 with such 'magic wand' many mining pools would, not only be capable of cr=
acking 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 i=
n 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 =
analyzing my proposition, Boris!
> > > > > =


> > > > > 1) My demonstration concludes 12 bytes is still a very conservat=
ive figure for the hashes. I'm not sure where did you get the 14 bytes fig=
ure. This 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 e=
xactly 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 LAMPP=
RI.
> > > > > =


> > > > > 3) I avail to advocate for economizing down the fingerprint to j=
ust 128 bits for the weakest-link-principle, since 128 bits is a nearly ub=
iquitous standard, employed even by the majority of seeds. Not an argument=
 against plain Schnorr, because Schnorr keys could use it too, but, compar=
ed with current implementations, we have that would be 20-16=3D4 bytes les=
s.
> > > > =


> > > > 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 side=
s:] To economize even further, there is also the entropy-derivation cost t=
rade-off 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 t=
o be buried. T2 can perfectly be hard-coded to always be the block equival=
ent of T0 + 48 hours (a reasonable spam to prevent innocent defaulting on =
commitment 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 one hand, the convenience of unfreezing UTXO and having TX mining comp=
leted ASAP and, on the other, avoiding the risk of blockchain forking caus=
ing LAMPPRI to be accidentally leaked in the same block height as LSIG, wh=
ich allows for signatures to be forged. So this is 16 bytes less.
> > > > > =


> > > > > Miners would keep record of unconfirmed BL's, because of the rew=
ard of mining either possible outcome of it (successful transaction or exe=
cution of commitment). Everything is paid for.
> > > > > =


> > > > > So, unless I'm forgetting something else, all other variables ke=
pt equal, we have 20 bytes lighter than Schnorr; and up to 25 bytes less t=
he current implementation of Schnorr, if items 3 and 4 are implemented too=
. Already we have a reduction of between 21% and 26%, while, so far, nobod=
y in the mailing list has disputed how 'outrageously' conservative the 12 =
bytes figure is.
> > > > =


> > > > 26% reduction of block space utilization would be great, but the p=
rice
> > > > 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 organizat=
ion.
> > > > Let's assume that the rainbow table has a chain length of 1024^3 (=
billion).
> > > > What storage size is needed? 2^96 * 12 / 1024^3 =3D 900 exabytes.
> > > > Both chain length and storage size seems prohibitively high for to=
day,
> > > > 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_______________________________________________
> > > > bitcoin-dev mailing list
> > > > bitcoin-dev@lists.linuxfoundation.org
> > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
-----------------------f4c392cefeba1a2f2d85dd1bad58f5b5
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==
-----------------------f4c392cefeba1a2f2d85dd1bad58f5b5--

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

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

wsBzBAEBCAAnBYJlhikRCZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL
w0xVAADyngf/e02qdToCDTIxaD4OUcPGJ7e0RU1x//VjE+hXxR/V6v1bScnU
Qco5nQsTDHxDEIAPPemwuiKPcL9NL8hN+0X37CGuhi4TSbcyXEd4JAl5T37s
Pjve8IaJ0zJfUWA3SQmfIZPxEKUf/W1Dlaga7qV8T5WG7KZy1Rf6be/8XaCB
rpxQtwKj6eM254sv4MFenFDDFd4x36NDyVjQDoUp57qqDzCNxr/u922b0Zj1
DW+vR4ZflaIj1Bkre0hBvNcTUZFYy+GdslZfmjomwerVGpGQp28H1LdCL+dR
vJg3WOJNfC9Yw3T06FZLyfIqGILETPXGFrsWaI0FtnvLqXgMYR3oQA==
=o3zQ
-----END PGP SIGNATURE-----


--------dea4fe7b6e69b5988fce1d40a8d08eaa30a617aa5122bcd6150efe1c9f173fc9--