path: root/d3/867caf3e9819040f910ff6f410c2c8b5a919cb

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