diff options
author | Nagaev Boris <bnagaev@gmail.com> | 2023-12-19 14:08:40 -0300 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2023-12-19 17:09:20 +0000 |
commit | 071efc7376185f98d0bde1036b1db87e6002dc8f (patch) | |
tree | 94b97d4f0633700165a1f5f0582e71e7ef4ca85f | |
parent | c08ef116a8c04c490ab04c10a567cca7c62170b2 (diff) | |
download | pi-bitcoindev-071efc7376185f98d0bde1036b1db87e6002dc8f.tar.gz pi-bitcoindev-071efc7376185f98d0bde1036b1db87e6002dc8f.zip |
Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
-rw-r--r-- | d3/867caf3e9819040f910ff6f410c2c8b5a919cb | 197 |
1 files changed, 197 insertions, 0 deletions
diff --git a/d3/867caf3e9819040f910ff6f410c2c8b5a919cb b/d3/867caf3e9819040f910ff6f410c2c8b5a919cb new file mode 100644 index 000000000..256246152 --- /dev/null +++ b/d3/867caf3e9819040f910ff6f410c2c8b5a919cb @@ -0,0 +1,197 @@ +Return-Path: <bnagaev@gmail.com> +Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) + by lists.linuxfoundation.org (Postfix) with ESMTP id D339AC0037 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 19 Dec 2023 17:09:20 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp1.osuosl.org (Postfix) with ESMTP id AEE91819BE + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 19 Dec 2023 17:09:20 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org AEE91819BE +Authentication-Results: smtp1.osuosl.org; + dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com + header.a=rsa-sha256 header.s=20230601 header.b=Jp/TIMIW +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -2.099 +X-Spam-Level: +X-Spam-Status: No, score=-2.099 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, FREEMAIL_FROM=0.001, + RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=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 7FM8GT37m1NY + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 19 Dec 2023 17:09:19 +0000 (UTC) +Received: from mail-il1-x136.google.com (mail-il1-x136.google.com + [IPv6:2607:f8b0:4864:20::136]) + by smtp1.osuosl.org (Postfix) with ESMTPS id 74EC281973 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 19 Dec 2023 17:09:19 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 74EC281973 +Received: by mail-il1-x136.google.com with SMTP id + e9e14a558f8ab-35d77fb7d94so23956675ab.0 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 19 Dec 2023 09:09:19 -0800 (PST) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=gmail.com; s=20230601; t=1703005758; x=1703610558; + darn=lists.linuxfoundation.org; + h=content-transfer-encoding:cc:to:subject:message-id:date:from + :in-reply-to:references:mime-version:from:to:cc:subject:date + :message-id:reply-to; + bh=iEvFaM/eb/VTK1j/woM7M2lZFw1erRbnvknMdn/NHLg=; + b=Jp/TIMIWoNt8XsIAfOG++tT5glZxAoabGgxT3veH8bU4NPdDZvZ5U9HuU9B8r8pPtT + rcBPm1pCTsSafpfGcwwKeORqKzlUteLVKUNqsGVMbETo3rcryNjqmtdT5SpQa0D+c3Ay + QQU0SvgtkWqIsEKxLwaImxBNcUNh9AtlDoveM2Lg9ySk5KJafLk1p/Rs5mZfmN9vrsVD + JT+NeZPQjVrhzLT6Mf4hJLNBIboKWsozCwLhK+i30kfyqLQvnK+vbKK4DRhk3AjoVrny + ILiucG8nILrBZ+WpnKhorMVT3FulJDgvY6PsxITbpot7t6vvdVE1ZiZK8euJ092lz8DB + IuXw== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20230601; t=1703005758; x=1703610558; + h=content-transfer-encoding:cc:to:subject:message-id:date:from + :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc + :subject:date:message-id:reply-to; + bh=iEvFaM/eb/VTK1j/woM7M2lZFw1erRbnvknMdn/NHLg=; + b=dfMNMdrxGRhpi5Wn8EBELYyv0XQKt6VO3nxzfiK12xx+mtmONnrjtfKFI2E3H6jpsp + 7EpH0ZpBELRGKg6SUMLp/QLv6KlwjxTNKsAu78YX7cUf8XYRl8/kPhVpRoDTYBnD5i23 + x3zxevybPoy5iETP9lGO/NbFm896/++3DKL19+wQzs9easAin/zidYZLjAw1FNvRTLEe + hDUpMc/d+O+l7P2CdsxG9eNCAzUMVrLCXKUGcQrWm0s70TkJwr9vMLXY0t/jfnlywO2Y + TVCOW1tj3I5loueUGXK1/yo5FtBKgMClIVX5MbNfGqWlhEMxYcVBCRcNVQ2OtY11l4xZ + jQMg== +X-Gm-Message-State: AOJu0Ywarz3bb//XudNiTArh7atevOy+wFfRg8A3XRideB0axsnJ+r79 + Qps6JToSbyV/5R7xAozxYYuwdUL4BBsz/3F+j19Tg4jJ2KzsLU5ZJqE= +X-Google-Smtp-Source: AGHT+IGfxc6uAQi0qY9OuDzff8ot5vmDYxrU6FbgGXE+mSe5SVFHPZKvLSoUU+YsW0gI39Uv1acLaWDtTYvPBOp3nHU= +X-Received: by 2002:a05:6e02:1cae:b0:35d:5af6:5eb4 with SMTP id + x14-20020a056e021cae00b0035d5af65eb4mr28176886ill.12.1703005758309; Tue, 19 + Dec 2023 09:09:18 -0800 (PST) +MIME-Version: 1.0 +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> +In-Reply-To: <ue8nChOuMtyW_JM-WxikLpWUSn9I99UHI5ukFVfLOEmQtCo4noetzyVKercbrwjr_EqNotDsR1QZ0oijMu11TO2jpEjlJF71OjLlNoZ-00Y=@pm.me> +From: Nagaev Boris <bnagaev@gmail.com> +Date: Tue, 19 Dec 2023 14:08:40 -0300 +Message-ID: <CAFC_Vt5PcqqcREJ67Jzcg=K+Agd02a9f5uSit8LwkYHshbvF7A@mail.gmail.com> +To: yurisvb@pm.me +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable +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 17:09:20 -0000 + +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 fingerpr= +int an ECC (Schnorr or otherwise conventional) public-key, which is not pub= +lished until first transaction. For clarity: +> +> HL(.) =3D serial-work- and memory-*hard* hash with *short* digest (ex.: A= +rgon2 with ~ 12 bytes output. "L" for "Lamport"); +> HC(.) =3D nonspecific representation of conventional, serial-work- and me= +mory-*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 Schnor= +r instead) +> LAMPPUB =3D HL(LAMPPRIi) +> LAMPPRI =3D HL(seed, tag) //Though it is (more) feasible to crack a seed = +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, cracking = +seed is still as hard as cracking a conventional seed. +> ADDR =3D H(ECCPUB, LAMPPUB) //Conventional BTC key fingerprinting with co= +nventionally used hashes and their respective brute-force-resistant digest = +lengths +> TX =3D plaintext transaction +> LSIG =3D HL(TX, LAMPPRI) +> COMMITMENT =3D Smart contract stating "This UTXO is frozen until one of t= +he following happens: A) publishing of a L such that HL(TX,L) =3D LSIG befo= +re T2 in which case TX is deemed valid and executed, or B) T2 blocks from n= +ow, when miner of LSIG has gets F1+FF1, and the miner of COMMITMENT gets FC= +, both from UTXO" +> BL =3D "Bundle of Lamport scheme" =3D (TX, LSIG) +> BC =3D "Bundle of Commitment and Conventional Signing" =3D (COMMITMENT, E= +CCPRI(COMMITMENT), ECCPUB, LAMPPUB) //LAMPPUB is added here to allow= + easy 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 ~ T0+= +1 to T0+6 blocks. This is to protect owner from dissensus (revealing LAMPPR= +I in a block and have it utilized to forge transaction in a competing block= + of same height). +> T2 =3D Block height of expiration of commitment ~ T0+24 hours to T0+ a fe= +w days to protect user from execution of commitment being triggered by inno= +cent unavailability. +> +> From ADDR alone, Miners, cannot forge a valid LSIG, nor try to ascertain = +LAMPPUB or LAMPPRI, because of pre-image-resistance of H(.) and brute-force= + resistance of ECCPUB before being published. The saving happens because, s= +afe from T2 passing without LAMPRI being broadcasted, only BL and LAMPPR, a= +nd not BC, end up in Blockchain. +> +> The proposed scheme, therefore allows for only 1 instance of Lamport sche= +med-based economic transaction, which has to be the first transaction of AD= +DR (because of publishing of ECCPUB). After this first transaction, ADDR is= + stil valid, just no longer able to issue transactions. +> +> The proposed scheme, therefore, favors the good practice of non-address r= +euse. +> +> 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. + + + +--=20 +Best regards, +Boris Nagaev + |