Date: Fri, 29 Dec 2023 00:30:30 +0000
To: "G. Andrew Stone" <g.andrew.stone@gmail.com>,
 Nagaev Boris <bnagaev@gmail.com>
From: yurisvb@pm.me
Message-ID: <EKvQwk6gu1g35fnG_QC8zeX6QR9Vr6u3vXqRsbBS1imvt8GgfMP-9lOqFjNG6gWFSVJdmbsFyZ2vL8PhwxRc94EXSNZMEWRDt429S_uWuOE=@pm.me>
In-Reply-To: <nMFSEupHxGqdH2Z4kSNj-kufM4X__UexnJOqC99-KlfT84adaDfPLm66vS6V8Ogphiogz1dvzFEVjM7QO_t9PVR3VqNxZCIvD4C_SEtkDfc=@pm.me>
References: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me>
 <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>
 <nMFSEupHxGqdH2Z4kSNj-kufM4X__UexnJOqC99-KlfT84adaDfPLm66vS6V8Ogphiogz1dvzFEVjM7QO_t9PVR3VqNxZCIvD4C_SEtkDfc=@pm.me>
Feedback-ID: 15605746:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature";
 micalg=pgp-sha256;
 boundary="------ea1b607a5cc3d2ab353323555d1516fc6ebfb9382d45f75a29cc028550013ca1";
 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)
--------ea1b607a5cc3d2ab353323555d1516fc6ebfb9382d45f75a29cc028550013ca1
Content-Type: multipart/mixed;boundary=---------------------2963eaee4de145cb6fc148607ada0475

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

Dear all,

Upon a few more days working on my proposed protocol, I've found a way to =
waive the need for:
1) mining the conventional public key;
2) user broadcasting 2 distinct payloads a few blocks apart;

Up to 66% footprint reduction.

I'll be publishing and submitting it as BIP soon. Those who got interested=
 are more than welcome to get in touch directly.

It's based on my proposed cryptosystem based on the conjectured hardness o=
f factorization of polynomials in finite fields:
https://github.com/Yuri-SVB/FFM-cryptography/

YSVB

Sent with Proton Mail secure email.

On Saturday, December 23rd, 2023 at 1:26 AM, yurisvb@pm.me <yurisvb@pm.me>=
 wrote:


> Dear all,
> =


> Upon second thoughts, I concluded have to issue a correction on my last =
correspondence. 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 form=
at of ADDRs'} X {LSIG}
> > =


> > (notice the nuance: {LSIG} means the singleton containing of only the =
specific 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=
 of ADDRs'} X {s | s is 'in the format of LSIGs'}"
> =


> =


> instead, and completely disregard the nuance below, which is wrong. I ap=
ologize for the mistake, and hope I have made myself clear. Thank you, aga=
in for your interest, and I'll be back with formulas for entropy in both c=
ases 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 (T=
X, SIG));
> > 3. Outmine the rest of mining community starting from a disadvantage o=
f not less than (T1-T0-1) after T1 (to be precise, at time of publishing o=
f LAMPRI);
> > =


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


> > We can have LAMPPUB be 1Mb or even 1Gb long aiming at having rate of c=
ollision in HL(.) be negligible (note this is perfectly adherent to the pr=
oposition of memory-hard-hash, and would have the additional benefit of al=
lowing 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=
 in the format of a ADDR}
> > =


> > having as domain the Cartesian product of set of possible ECCPRIs with=
 set 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 form=
at of ADDRs'} X {LSIG}
> > =


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


> > Notice that, whatever advantage of 2 over 1 has to be compensated by t=
he perspective of having the protocol be successfully terminated before th=
e 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 communit=
y.
> > =


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


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


> > YSVB.
> > =


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


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


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


> > > > You are right to point out that my proposal was lacking defense ag=
ainst rainbow-table, because there is a simple solution for it:
> > > > To take nonces from recent blocks, say, T0-6, ..., T0-13, for salt=
ing 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 c=
ase, since here we have 8*32=3D256 bits for LSIG, and the entropy of ECCPU=
B in the second.
> > > > =


> > > > With rainbow table out of our way, there is only brute-force analy=
sis to mind. Honestly, Guess I should find a less 'outrageously generous' =
upper bound for adversary's model, than just assume they have a magic wand=
 to convert SHA256 ASICS into CPU with the same hashrate for memory- and s=
erial-work-hard hashes (therefore giving away hash hardness). That's becau=
se 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 al=
so 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 bnagae=
v@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 carefull=
y analyzing my proposition, Boris!
> > > > > > =


> > > > > > 1) My demonstration concludes 12 bytes is still a very conserv=
ative figure for the hashes. I'm not sure where did you get the 14 bytes f=
igure. 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=
 exactly right and I failed to realize that. To lessen the exposure, and t=
he risk of miner of LSIG, it can be left to be broadcast together with LAM=
PPRI.
> > > > > > =


> > > > > > 3) I avail to advocate for economizing down the fingerprint to=
 just 128 bits for the weakest-link-principle, since 128 bits is a nearly =
ubiquitous standard, employed even by the majority of seeds. Not an argume=
nt against plain Schnorr, because Schnorr keys could use it too, but, comp=
ared with current implementations, we have that would be 20-16=3D4 bytes l=
ess.
> > > > > =


> > > > > 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 si=
des:] To economize even further, there is also the entropy-derivation cost=
 trade-off of N times costlier derivation for log2(N) less bits. If applie=
d 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 buried. T2 can perfectly be hard-coded to always be the block equiv=
alent of T0 + 48 hours (a reasonable spam to prevent innocent defaulting o=
n 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 betwee=
n, on one hand, the convenience of unfreezing UTXO and having TX mining co=
mpleted ASAP and, on the other, avoiding the risk of blockchain forking ca=
using LAMPPRI to be accidentally leaked in the same block height as LSIG, =
which allows for signatures to be forged. So this is 16 bytes less.
> > > > > > =


> > > > > > Miners would keep record of unconfirmed BL's, because of the r=
eward of mining either possible outcome of it (successful transaction or e=
xecution of commitment). Everything is paid for.
> > > > > > =


> > > > > > So, unless I'm forgetting something else, all other variables =
kept equal, we have 20 bytes lighter than Schnorr; and up to 25 bytes less=
 the current implementation of Schnorr, if items 3 and 4 are implemented t=
oo. Already we have a reduction of between 21% and 26%, while, so far, nob=
ody in the mailing list has disputed how 'outrageously' conservative the 1=
2 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 figu=
re out
> > > > > if they are resistant to rainbow table attack by a large organiz=
ation.
> > > > > 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 =
today,
> > > > > but tomorrow the hash function can be optimized, memory can be
> > > > > optimized, storage can become cheaper etc. And this attack may b=
e
> > > > > 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
-----------------------2963eaee4de145cb6fc148607ada0475
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==
-----------------------2963eaee4de145cb6fc148607ada0475--

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

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

wsBzBAEBCAAnBYJljhMLCZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL
w0xVAACDRwf+KGNJAQH5ZKqINazUYBLNJ1Ay2/v9tVST/Klu5FxG4vOtoyrs
cPGFUPfBWjfpET5IvIyRFmSj5cjrHSGwH+15zU6sjRiMEHvwwC/SUemGbNm3
JRD8h7EKQ10zcNAQmNuje2GB5bQcb9zUxoV72JfVhgQalgcsdQPf3b2//h70
v5FBFuTHQQAhAjS4iJfBV7emGrF1r/ATQnYNU7tRYf2EThwFlMtUpIAFoaK4
A/dOWTbEjtatZevRLBeO9jtiK11A6N8V1DryVWj+Cbf1v2EuqZ3IhaSr36Aj
WoAv3XsvcxGvJop5YvF63n5uhn6DVhdC1ykozFo6JVZa0sRcAMCyvg==
=2u06
-----END PGP SIGNATURE-----


--------ea1b607a5cc3d2ab353323555d1516fc6ebfb9382d45f75a29cc028550013ca1--