diff options
| author | yurisvb <yurisvb@pm.me> | 2023-12-19 21:22:20 +0000 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2023-12-19 21:22:46 +0000 |
| commit | 7d5dcbaf9464837581180f2424e8d9792eb08947 (patch) | |
| tree | be64d9a15a4b81ddc3382b538cbbdec74b41931f | |
| parent | 071efc7376185f98d0bde1036b1db87e6002dc8f (diff) | |
| download | pi-bitcoindev-7d5dcbaf9464837581180f2424e8d9792eb08947.tar.gz pi-bitcoindev-7d5dcbaf9464837581180f2424e8d9792eb08947.zip | |
Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
| -rw-r--r-- | 83/b36d1a07fd04cb724876169d0ff5638c538096 | 330 |
1 files changed, 330 insertions, 0 deletions
diff --git a/83/b36d1a07fd04cb724876169d0ff5638c538096 b/83/b36d1a07fd04cb724876169d0ff5638c538096 new file mode 100644 index 000000000..e9c47bd5c --- /dev/null +++ b/83/b36d1a07fd04cb724876169d0ff5638c538096 @@ -0,0 +1,330 @@ +Return-Path: <yurisvb@pm.me> +Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 50A48C0037 + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bnagaev@gmail.com> +From: yurisvb@pm.me +Message-ID: <HG9-9VDKRd3-0v0x9QP05_Cjyk9Y3UW-94A1RHsT3xMQYmb7Y6sk9-wTUlqVZzm6ACigM7aM-B6NB-z6jVCCXhQIGEYkEcBKryzP587FlIo=@pm.me> +In-Reply-To: <CAFC_Vt5PcqqcREJ67Jzcg=K+Agd02a9f5uSit8LwkYHshbvF7A@mail.gmail.com> +References: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me> + <CAFC_Vt5xqhuXjNVeSGE2Pn=0N0MuB6pOnREzGhSQSpk+hTUUSg@mail.gmail.com> + <-lH1AcjRwuxfuqLPFOh_oga10Qm12fb7Se9imDeS5ft6CU3y8KTQa3tBP0twJJBFSHgj7FC8EIxvEser3oZdWvkeitRwERQl_cCdgAWtbTU=@pm.me> + <CAFC_Vt7B1oV0_uAwKe3NQLWE2jdQ_MF1W4fnVqkf8s=YHyfVyQ@mail.gmail.com> + <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> +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 <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: 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 <bnagaev@gmail.co= +m> 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-- + + |