From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 50A48C0037 for ; Tue, 19 Dec 2023 21:22:46 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 1953960EA1 for ; Tue, 19 Dec 2023 21:22:46 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 1953960EA1 Authentication-Results: smtp3.osuosl.org; dkim=pass (2048-bit key) header.d=pm.me header.i=@pm.me header.a=rsa-sha256 header.s=protonmail3 header.b=ix3XUtYe 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 smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id m4Qr8sjrHgqt for ; Tue, 19 Dec 2023 21:22:45 +0000 (UTC) Received: from mail-4316.protonmail.ch (mail-4316.protonmail.ch [185.70.43.16]) by smtp3.osuosl.org (Postfix) with ESMTPS id A211160EDE for ; Tue, 19 Dec 2023 21:22:44 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org A211160EDE DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pm.me; s=protonmail3; t=1703020962; x=1703280162; bh=7+Ds7qtkTRCSF9Vi707SSLcLvf4Ftf8F1hT9hvjIL1c=; 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=ix3XUtYeATToe3ZiNnB2tmavqegQOtWpXh4MpIjWDhUASk1DTU0am/qGkd8ndDmSA 7LE7nokPLe4mrPKVmg6L+xpLLnfNK9FPaIkoMGSpjM30l6sVoXS1RB/YRB59HuiWQJ Wo4SD5EHbT5IhdBAh7SEhFMSltCDYI7QZQIkZYciZAoiMHFlu+qkkzQkHhzSGsaVO/ 0Ri/S4phlzqtjeipZiVB7pbcvQCPzKDZHZEPoTS7t3MOqnIUejUUW3hIjKaBdW35C0 SAW6U6CwbYs2Bjai2LAi7XKxEd/xlSntEFO+Wf9cQRbeu2xtZt6Tv1/DOrGY+5X33H 1Af218uihymew== Date: Tue, 19 Dec 2023 21:22:20 +0000 To: 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="------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8"; charset=utf-8 X-Mailman-Approved-At: Tue, 19 Dec 2023 21:45:43 +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: Tue, 19 Dec 2023 21:22:46 -0000 This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8 Content-Type: multipart/mixed;boundary=---------------------3f06cd0490d8849548ba8601b8734abf -----------------------3f06cd0490d8849548ba8601b8734abf Content-Transfer-Encoding: quoted-printable Content-Type: text/plain;charset=utf-8 Thank you for putting yourself through the working of carefully analyzing = my proposition, Boris! 1) My demonstration concludes 12 bytes is still a very conservative figure= for the hashes. I'm not sure where did you get the 14 bytes figure. This = is 2*(14-12) =3D 4 bytes less. 2) Thank you for pointing out that ECCPUB is necessary. That's exactly rig= ht and I failed to realize that. To lessen the exposure, and the risk of m= iner of LSIG, it can be left to be broadcast together with LAMPPRI. 3) I avail to advocate for economizing down the fingerprint to just 128 bi= ts for the weakest-link-principle, since 128 bits is a nearly ubiquitous s= tandard, employed even by the majority of seeds. Not an argument against p= lain Schnorr, because Schnorr keys could use it too, but, compared with cu= rrent implementations, we have that would be 20-16=3D4 bytes less. 4) [Again, argument against plain, because it cuts for both sides:] To eco= nomize even further, there is also the entropy-derivation cost trade-off o= f N times costlier derivation for log2(N) less bits. If applied to the Add= ress, we could shave away another byte. 5) T0 is just the block height of burying of LSIG doesn't need to be burie= d. T2 can perfectly be hard-coded to always be the block equivalent 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, (ty= pically T1 <=3D T0+6) of user's choosing, to compromise between, on one ha= nd, the convenience of unfreezing UTXO and having TX mining completed ASAP= and, on the other, avoiding the risk of blockchain forking causing LAMPPR= I 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 reward of min= ing 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 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 m= ailing list has disputed how 'outrageously' conservative the 12 bytes figu= re is. Any other objections? YSVB Sent with Proton Mail secure email. On Tuesday, December 19th, 2023 at 6:08 PM, Nagaev Boris wrote: > On Tue, Dec 19, 2023 at 11:07=E2=80=AFAM yurisvb@pm.me wrote: > = > > Thank you for the question, Boris. That was an easy one: > > = > > Short answer is Lamport hashes are protected by long hash of key finge= rprint an ECC (Schnorr or otherwise conventional) public-key, which is not= published until first transaction. For clarity: > > = > > HL(.) =3D serial-work- and memory-hard hash with short digest (ex.: Ar= gon2 with ~ 12 bytes output. "L" for "Lamport"); > > HC(.) =3D nonspecific representation of conventional, serial-work- and= memory-easy hashes with long (brute-force-resistant) digest length. "C" f= or "Conventional"; > > KDF(.) =3D conventional key deriving function > > ECCPUB =3D public key correspondent to ECCPRI > > ECCPRI =3D KDF(seed, tag) //conventional BTC signing key (could be Sch= norr instead) > > LAMPPUB =3D HL(LAMPPRIi) > > LAMPPRI =3D HL(seed, tag) //Though it is (more) feasible to crack a se= ed S that works as pre-image to LAMPRI, such seed can only be deemed valid= if the public key correspondent to KDF(s) =3D ECCPUB, so ultimately, crac= king seed is still as hard as cracking a conventional seed. > > ADDR =3D H(ECCPUB, LAMPPUB) //Conventional BTC key fingerprinting with= conventionally used hashes and their respective brute-force-resistant dig= est lengths > > TX =3D plaintext transaction > > LSIG =3D HL(TX, LAMPPRI) > > COMMITMENT =3D Smart contract stating "This UTXO is frozen until one o= f the following happens: A) publishing of a L such that HL(TX,L) =3D LSIG = before T2 in which case TX is deemed valid and executed, or B) T2 blocks f= rom now, when miner of LSIG has gets F1+FF1, and the miner of COMMITMENT g= ets FC, both from UTXO" > > BL =3D "Bundle of Lamport scheme" =3D (TX, LSIG) > > BC =3D "Bundle of Commitment and Conventional Signing" =3D (COMMITMENT= , ECCPRI(COMMITMENT), ECCPUB, LAMPPUB) //LAMPPUB is added here to allow ea= sy verification that ECCPUB corresponds to ADDR > > BT =3D "Total Bundle" =3D (BL, BC) > > F1 =3D fee offered to mine BL > > FF1 =3D fine offered to miner of BL to compensate for delay > > FC =3D fee offered to mine BC in case of default > > T0 =3D Block height of broadcasting of BT > > T1 =3D Block height owner should aim at broadcasting LAMPPRI block ~ T= 0+1 to T0+6 blocks. This is to protect owner from dissensus (revealing LAM= PPRI in a block and have it utilized to forge transaction in a competing b= lock of same height). > > T2 =3D Block height of expiration of commitment ~ T0+24 hours to T0+ a= few days to protect user from execution of commitment being triggered by = innocent unavailability. > > = > > From ADDR alone, Miners, cannot forge a valid LSIG, nor try to ascerta= in LAMPPUB or LAMPPRI, because of pre-image-resistance of H(.) and brute-f= orce resistance of ECCPUB before being published. The saving happens becau= se, safe from T2 passing without LAMPRI being broadcasted, only BL and LAM= PPR, and not BC, end up in Blockchain. > > = > > The proposed scheme, therefore allows for only 1 instance of Lamport s= chemed-based economic transaction, which has to be the first transaction o= f ADDR (because of publishing of ECCPUB). After this first transaction, AD= DR is stil valid, just no longer able to issue transactions. > > = > > The proposed scheme, therefore, favors the good practice of non-addres= s reuse. > > = > > YSVB > = > = > Thank you for the great explanation, Yuri! > = > Let's make sure we are on the same page. > = > I calculated the on-chain footprint of signatures of the proposed > scheme and compared it with schnorr keys as are used in taproot. > = > Lamport scheme, the case no ECC signature is published: > - output: 20 bytes. ADDR =3D H(ECCPUB, LAMPPUB) > - input 1: LSIG (14 bytes) > - input 2: ECCPUB, LAMPPRI (32+14=3D46). (ECCPUB is needed to verify > hashing to ADDR; LAMPPUB is not needed onchain, because it is a hash > of LAMPPRI.) > Total onchain footprint: 20+14+46=3D80 (bytes) > Is this correct? > = > Taproot: > - output: 32 bytes (schnorr public key) > - input: 64 bytes (schnorr signature) > Total: 32+64 =3D 96 (bytes) > = > Some additional space is needed in the lamport scheme case to address > T0 from T1 and to have T1 in the first place. Tx overhead is around 10 > bytes and say 6 bytes for the reference. It looks, the footprint will > be the same. > = > = > = > -- > Best regards, > Boris Nagaev -----------------------3f06cd0490d8849548ba8601b8734abf 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== -----------------------3f06cd0490d8849548ba8601b8734abf-- --------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wsBzBAEBCAAnBYJlggl5CZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL w0xVAACU+gf+KpdrCimgxN9BpYm33VRwkp0Z7lRMZLaXjPU0L04saeDwedyN xUKJQn+e0v8bhLjcTduGS2GFdnTatw/PsIMWTnV4zH2207St0nZM+7I/+9uY w+YvvvjvQV2Go2E3AJNjqA5Wz/nJlppY9rQHMFP+23VOVuEzP9cu7pdQNttq KxIap36rz7i+ShJcbqua7s+DkNeW1fBG6ikoM8LvYaZ/MKGjuIHpmOBUjLdx xDt221xj03DSeIIJNNOR1RSF/VO1DGoUNqYZMNv2lmm15EvfR+Uzwq8THkRC wy0oJjm4JI8vbd4qYCbr+zLkF7HfTjYzwE9ihnX3ehGqJd8g4YjXXA== =YX0X -----END PGP SIGNATURE----- --------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8--