Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id B633FC0037 for ; 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 ; 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 ; 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 ; 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" , Nagaev Boris From: yurisvb@pm.me Message-ID: In-Reply-To: References: <1aHuuO-k0Qo7Bt2-Hu5qPFHXi4RgRASpf9hWshaypHtdN-N9jkubcvmf-aUcFEA6-7L9FNXoilIyydCs41eK4v67GVflEd9WIuEF9t5rE8w=@pm.me> 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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 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 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--