summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNagaev Boris <bnagaev@gmail.com>2023-12-19 14:08:40 -0300
committerbitcoindev <bitcoindev@gnusha.org>2023-12-19 17:09:20 +0000
commit071efc7376185f98d0bde1036b1db87e6002dc8f (patch)
tree94b97d4f0633700165a1f5f0582e71e7ef4ca85f
parentc08ef116a8c04c490ab04c10a567cca7c62170b2 (diff)
downloadpi-bitcoindev-071efc7376185f98d0bde1036b1db87e6002dc8f.tar.gz
pi-bitcoindev-071efc7376185f98d0bde1036b1db87e6002dc8f.zip
Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
-rw-r--r--d3/867caf3e9819040f910ff6f410c2c8b5a919cb197
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
+