path: root/34/7ec2c0c1553e57bf6cf2e45b96d0717e1733cb

Return-Path: <yurisvb@pm.me>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id B633FC0037
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 22 Dec 2023 15:32:56 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id 836B983F0D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 22 Dec 2023 15:32:56 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 836B983F0D
Authentication-Results: smtp1.osuosl.org;
 dkim=pass (2048-bit key) header.d=pm.me header.i=@pm.me header.a=rsa-sha256
 header.s=protonmail3 header.b=j5gU/T2Y
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level: 
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H5=0.001,
 RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Received: from smtp1.osuosl.org ([127.0.0.1])
 by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id eAc8uI7VH9lN
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 22 Dec 2023 15:32:54 +0000 (UTC)
Received: from mail-4316.protonmail.ch (mail-4316.protonmail.ch [185.70.43.16])
 by smtp1.osuosl.org (Postfix) with ESMTPS id ED37883EFA
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 22 Dec 2023 15:32:53 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org ED37883EFA
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pm.me;
 s=protonmail3; t=1703259170; x=1703518370;
 bh=S1VrMmalOOH1jAkyvZ6OUMnATPkDPhdkf1/PHbsWx1U=;
 h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References:
 Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID:
 Message-ID:BIMI-Selector;
 b=j5gU/T2YQ8Pete7a7wbX7mBLqxWeYGF8WIi54p8axNgfMa799M1/JMLJ2FgkUW/72
 Ci5XrG6sQ7hJghQCiQ891Ja9cjyv0QTZf4uy5+k3ZCeXp9VmrHDgl4SOCE6pvuj1Px
 ZTJX/i5I/qff92ffiE/UaNeZL9R7tJxcqu03hWmA2cRCFCr7g9RH73lJbV281SDb8E
 07agmT4X6nvzkYw6jOAa7vY1y9EsL1T5d7QRhClVcd9BvJTqrMyC4nQAxlD/JKm/Uw
 e8o8C4r3FYcKVrsXcS+SOjcVBvrQzjiLY5DQ2k7kcV4MukUmK1ggO6t9GlWlHY4ouj
 vJKcDSrSSD3tA==
Date: Fri, 22 Dec 2023 15:32:38 +0000
To: "G. Andrew Stone" <g.andrew.stone@gmail.com>,
 Nagaev Boris <bnagaev@gmail.com>
From: yurisvb@pm.me
Message-ID: <jGJvlLv4UL13U6aklzwkyRE4XRQtQSK-JZzpevPzyWQhQ4rU84I5fPDSdbtW7ehFzxkLtaOEenMMQAbHslH766qj9DGfb7QlwwXqjGsNRvU=@pm.me>
In-Reply-To: <CAHUwRvuyhQDN5RF0ysMAJgWS2V7vv-3yHzKcLspk_HzQY=tt2Q@mail.gmail.com>
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>
Feedback-ID: 15605746:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature";
 micalg=pgp-sha256;
 boundary="------36fbc994a4da26dd2df80e91de2326347e37c4df886d9272037986f645335de4";
 charset=utf-8
X-Mailman-Approved-At: Fri, 22 Dec 2023 15:53:25 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 22 Dec 2023 15:32:56 -0000

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------36fbc994a4da26dd2df80e91de2326347e37c4df886d9272037986f645335de4
Content-Type: multipart/mixed;boundary=---------------------ee4c42fee14100a3ca4d794ff39bc5a9

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

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 n=
ot less than (T1-T0-1) after T1 (to be precise, at time of publishing of L=
AMPRI);

...which bring us back to my argument with Boris: There is something else =
we missed in our considerations, which you said yourself: *ironically, LAM=
PPUB is never published*.

We can have LAMPPUB be 1Mb or even 1Gb long aiming at having rate of colli=
sion in HL(.) be negligible (note this is perfectly adherent to the propos=
ition of memory-hard-hash, and would have the additional benefit of allowi=
ng 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 format o=
f ADDRs'} X {LSIG}
(notice the nuance: {LSIG} means the singleton containing of only the spec=
ific 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 p=
erspective of having the protocol be successfully terminated before the at=
tack being carried out.

For 3: Equivalente of a double-spending attack with, in the worst case, no=
t 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 case=
, 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 LAMPPR=
I, so mission accomplished!

Another ramification of that is we can conceive a multi-use version of thi=
s scheme, in which LAMPPRI is the ADDR resulting of a previous (ECCPUB, LA=
MPPUB) pair. The increased size of LAMPPRI would be compensated by one ent=
ire ADDR less in the blockchain. Namely, we'd have an extra marginal reduc=
tion of 12 bytes per use (possibly more, depending on how much more bytes =
we can economize given that added strength).

YSVB.

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


> Does this affect the security model WRT chain reorganizations? In the cl=
assic doublespend attack, an attacker can only redirect UTXOs that they sp=
ent. With this proposal, if I understand it correctly, an attacker could r=
edirect all funds that have "matured" (revealed the previous preimage in t=
he hash chain) to themselves. The # blocks to maturity in your proposal be=
comes the classic "embargo period" and every coin spent by anyone between =
the fork point and the maturity depth is available to the attacker to doub=
lespend?
> =


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


> > You are right to point out that my proposal was lacking defense agains=
t rainbow-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 unkn=
own by the builder of rainbow table while they made it, which is the case,=
 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 analysis =
to mind. Honestly, Guess I should find a less 'outrageously generous' uppe=
r 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 seria=
l-work-hard hashes (therefore giving away hash hardness). That's because w=
ith such 'magic wand' many mining pools would, not only be capable of crac=
king 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@g=
mail.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 an=
alyzing my proposition, Boris!
> > > >
> > > > 1) My demonstration concludes 12 bytes is still a very conservativ=
e figure for the hashes. I'm not sure where did you get the 14 bytes figur=
e. 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 exa=
ctly right and I failed to realize that. To lessen the exposure, and the r=
isk 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 jus=
t 128 bits for the weakest-link-principle, since 128 bits is a nearly ubiq=
uitous standard, employed even by the majority of seeds. Not an argument a=
gainst plain Schnorr, because Schnorr keys could use it too, but, compared=
 with 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 tra=
de-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 to =
be buried. T2 can perfectly be hard-coded to always be the block equivalen=
t of T0 + 48 hours (a reasonable spam to prevent innocent defaulting on co=
mmitment 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, o=
n one hand, the convenience of unfreezing UTXO and having TX mining comple=
ted ASAP and, on the other, avoiding the risk of blockchain forking causin=
g LAMPPRI to be accidentally leaked in the same block height as LSIG, whic=
h allows for signatures to be forged. So this is 16 bytes less.
> > > >
> > > > Miners would keep record of unconfirmed BL's, because of the rewar=
d of mining either possible outcome of it (successful transaction or execu=
tion 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 too. =
Already we have a reduction of between 21% and 26%, while, so far, nobody =
in the mailing list has disputed how 'outrageously' conservative the 12 by=
tes figure is.
> > >
> > >
> > > 26% reduction of block space utilization would be great, but the pri=
ce
> > > 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 o=
ut
> > > if they are resistant to rainbow table attack by a large organizatio=
n.
> > > Let's assume that the rainbow table has a chain length of 1024^3 (bi=
llion).
> > > What storage size is needed? 2^96 * 12 / 1024^3 =3D 900 exabytes.
> > > Both chain length and storage size seems prohibitively high for toda=
y,
> > > 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
-----------------------ee4c42fee14100a3ca4d794ff39bc5a9
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==
-----------------------ee4c42fee14100a3ca4d794ff39bc5a9--

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

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

wsBzBAEBCAAnBYJlhav0CZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL
w0xVAAAC3Af/eSPZtS80kRK/UnE/ygEdC1wTXYR1va7y8nrlhhmHKm3p35BS
NDL+d3DcyV17hMY2tAmFbgmp9EuDYGOCoFDWXdI8b5e8/cd1TC1CLWO9A31k
AwtS9hgaGyU1hrD4U6O/OfgAAzUnTqhKdulCU/4wOnhR+NuCCSYX2auVeKAH
F+NCvFSqg0O0xUWumuja2lAvCmPz3VzhTCVJCNzR+ULlzj0XZMrRMOQOMS1s
N9+KxLnc/CHLMpeSzGWz37VTHRwcKbwywRYsinpEs3DCqy70wPmtEwKh2kEB
xkIJpmAA8oBex7mUPWhFmJC9mb/acoRLyWb8BzZy1CczHTt45GvKmg==
=64f9
-----END PGP SIGNATURE-----


--------36fbc994a4da26dd2df80e91de2326347e37c4df886d9272037986f645335de4--