Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7F6C9C0037 for ; Thu, 21 Dec 2023 16:07:52 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 5353D40A50 for ; Thu, 21 Dec 2023 16:07:52 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 5353D40A50 Authentication-Results: smtp2.osuosl.org; dkim=pass (2048-bit key) header.d=pm.me header.i=@pm.me header.a=rsa-sha256 header.s=protonmail3 header.b=gWAcyuzP 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 smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HUOvgvNoysfv for ; Thu, 21 Dec 2023 16:07:49 +0000 (UTC) X-Greylist: delayed 172540 seconds by postgrey-1.37 at util1.osuosl.org; Thu, 21 Dec 2023 16:07:48 UTC DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org C37A840645 Received: from mail-40131.protonmail.ch (mail-40131.protonmail.ch [185.70.40.131]) by smtp2.osuosl.org (Postfix) with ESMTPS id C37A840645 for ; Thu, 21 Dec 2023 16:07:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pm.me; s=protonmail3; t=1703174865; x=1703434065; bh=y3HuS8/fz37dllTU2DW6pwf+buc41/MpIpEkjvAeuJc=; h=Date:To:From:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=gWAcyuzPEDK18LPORy39WyOHhPjX2FneRReRaOFXOXA1WdQQ0e9zz00SwY70ErHlX eHLW8vvNdZTswe1m2GARYAc4zPfgFkHdr5oqqNZR5Tp1YtgV25XMJ+ewEoubqDXMFo 1KSOnvKchFm0dBH1E9rEenBNJmtjPa+J6Rk5XatT0fpXwLpSOB5qO+/EtNUsZ/ny4B TIe1/mZ0r9isUp+GPd10xawu1uwjRira00gl2+0x7rkF7GzcRaPIPeE2tdksaEbLi1 cJQ0aJ8DbX5vEep6XDVZ3IEgRYSVPJHLI96+3DFUT3aDWXqJIAa53Vhn/kN4H0MtNa ycVKdjEFO23gQ== Date: Thu, 21 Dec 2023 16:07:27 +0000 To: Bitcoin Protocol Discussion , Nagaev Boris From: yurisvb@pm.me Message-ID: In-Reply-To: References: <-lH1AcjRwuxfuqLPFOh_oga10Qm12fb7Se9imDeS5ft6CU3y8KTQa3tBP0twJJBFSHgj7FC8EIxvEser3oZdWvkeitRwERQl_cCdgAWtbTU=@pm.me> <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="------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e"; charset=utf-8 X-Mailman-Approved-At: Fri, 22 Dec 2023 01:02:16 +0000 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: Thu, 21 Dec 2023 16:07:52 -0000 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 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--