path: root/a9/8b850d974aa2a8db531978aca1f30f2a837002

Return-Path: <sergio.d.lerner@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id C8C84C0037
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Dec 2023 12:30:29 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 9E255417F9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Dec 2023 12:30:29 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 9E255417F9
Authentication-Results: smtp4.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20230601 header.b=kOT8Eaqt
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.838
X-Spam-Level: 
X-Spam-Status: No, score=-1.838 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,
 HTML_MESSAGE=0.001, HTML_OBFUSCATE_05_10=0.26,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id AX7fqlnDFs7A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Dec 2023 12:30:28 +0000 (UTC)
Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com
 [IPv6:2a00:1450:4864:20::330])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 4F127417E8
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Dec 2023 12:30:28 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 4F127417E8
Received: by mail-wm1-x330.google.com with SMTP id
 5b1f17b1804b1-40c580ba223so35987695e9.3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Dec 2023 04:30:28 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1702902626; x=1703507426;
 darn=lists.linuxfoundation.org; 
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :from:to:cc:subject:date:message-id:reply-to;
 bh=EVVQA4+Lcl94gNFSU3IFxnJb7Nhs/kSneh9izc7iy3E=;
 b=kOT8Eaqte3n55XhwTDvytYjhM7M77J3VD889sTvVwlMqDAXg2eBSlpLcq6Fpp86M1r
 xLs9Sh3l3ybs1juj2Zx1TgksrqnOxujr+NzlIz5ypSTkB+R3nuX6yMxiSFPxJjo5L5KY
 ji6uM5/eQBHvv+yh9D11MHqp9jZfa5Wd/N7g7dl6whzVwaSsmJTL8pTGLc99M/mtMgng
 fMn3rfqbdSqP4KWGRWuCuf25pfk6pyzmaGFK+fH/gw/hyVYb0acubRRISRlrQFGLFBq7
 Ts1xwRXLviNnnMkyZnLRlkhY9HcZlF3UI+fvKJHeyki/c9HTRMvlKarVc3ecfIoTLhno
 losg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1702902626; x=1703507426;
 h=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=EVVQA4+Lcl94gNFSU3IFxnJb7Nhs/kSneh9izc7iy3E=;
 b=NY5pj1SgrSshNQWD7tyKux56pYsiH+36tf4nnPuerLNJxggtmLta/zaQjmT4LXvgTd
 efoNjI4qZ3t5bZVccsvzT42aCZNiBGPBhhBMwp7/vgzviQ+dKMKzYogNFY2HR453qqlD
 Zp3i2urKcLbJJZY+zHFuyfKGlDu+lwzOWplvYCImj4h91T0WrtOxiKhGVGjROSWn3cr3
 imhevP2m1N2bmgEyMJH/zgjogxRxoNfBk1QfYiuG1chccc2lWuKHrz9oZlQlZ0s/9/GQ
 kcWl49TSwiJtRjPGa7PZRaTdmsrySMUtChwGXjvDZVUYH5GIDfsTuzwPSdm55My58iTf
 fOaA==
X-Gm-Message-State: AOJu0Yxn2KWZe0e9X8AwhbBF0E7/yHhMk1kz91BjTOaNEBJAOOoFOMnz
 cwwBQU8Hpj7297cW6ymW7r8QTf3SLF+l7F5EChTUcwt/Rik=
X-Google-Smtp-Source: AGHT+IE1bkA6kuQX+US5atl7w37pF3lyQhVTQZ0nJx6yAraPT4NrbqSTsBWl5s+xZQNqo+5k8VNinJeGBRGtoYpqC48=
X-Received: by 2002:a05:600c:2802:b0:40b:5e21:dd3c with SMTP id
 m2-20020a05600c280200b0040b5e21dd3cmr9746723wmb.106.1702902625739; Mon, 18
 Dec 2023 04:30:25 -0800 (PST)
MIME-Version: 1.0
References: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me>
In-Reply-To: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me>
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Mon, 18 Dec 2023 09:29:48 -0300
Message-ID: <CAKzdR-qaN7sO62F38tm1ppEow=Oh-3A6kwsfRyts8U+LPXvTnQ@mail.gmail.com>
To: yurisvb@pm.me, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000001859b9060cc7ea37"
X-Mailman-Approved-At: Mon, 18 Dec 2023 13:57:40 +0000
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: Mon, 18 Dec 2023 12:30:29 -0000

--0000000000001859b9060cc7ea37
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Yuri,
While not exactly the same, the idea of using Lamport chains was analyzed
circa 2012 in the context of cryptocurrencies.
I proposed a new signature scheme called MAVE [1], and then a
cryptocurrency scheme called MAVEPAY [2] to reduce the size of signatures
to a minimum of 3 hash verifications per signature, assuming a blockchain
or time-stamping service.

Later there was a similar proposal by A. Miller called FawkesCoin [3]
(using "Guy Fawkes Protocol" [4] or fawkes signatures, for short).

regards

[1] https://bitslog.files.wordpress.com/2012/04/mave1.pdf
[2] https://bitslog.files.wordpress.com/2012/04/mavepay1.pdf
[3] https://link.springer.com/chapter/10.1007/978-3-319-12400-1_36
[4] R. J. Anderson, F. Bergadano, B. Crispo, J.-H. Lee, C. Manifavas, and
R. M. Needham. A new family of authentication protocols. Operating Systems
Review, 32(4):9=E2=80=9320, 1998.


On Mon, Dec 18, 2023 at 6:19=E2=80=AFAM Yuri S VB via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Dear colleagues,
>
> After having mentioned it in a Twitter Space
> <https://twitter.com/i/spaces/1vOxwjWWOqdJB> a few moments ago, I felt
> the need to share the idea with you even just as a draft. Utilizing Lampo=
rt
> Scheme <https://en.wikipedia.org/wiki/S/KEY> (not signature
> <https://en.wikipedia.org/wiki/Lamport_signature>) for better
> byte-efficiency in L1:
>
>
>    1. Have signing keys consist of the current ECC key AND a Lamport
>    chain;
>    2. For signing of a transaction, broadcast a tuple consisting of
>       1. the plain transaction,
>       2. hash of the previous Lamport chain concatenated to the
>       transaction
>       3. commitment signed by ECC freezing its UTXO and promising that in
>       a few blocks time the pre image of hash will be published.
>    3. a and b (but not c) are buried in coinbase session of a block B1 by
>    miner M1;
>    4. If upon maturity, such pre-image is not broadcasted, signed
>    commitment is buried in the next block and executed. As a consequence,
>    frozen UTXO pays B1 for a and b being buried at M1's coinbase *and* mi=
ner
>    M2 for burying it [the commitment] in a block B2 subsequent to maturit=
y;
>    5. If pre-image is broadcasted before maturity, it is buried in
>    another block B2', pays for itself, pays M1 for burying a adn b at B1 =
and
>    pays whatever else was determined in the plain transaction of item 2.a=
.
>
>
> The whole point is that, in the typical use case in which pre-image of
> hash is, in fact, successfully broadcasted before maturity, commitment, t=
he
> only ECC signature in this protocol is discarded, and only two Lamport
> hashes end up being buried at L1.
>
> To push economy even further, we could implement a memory-hard hash like
> Argon2 to do the same entropy-processing trade-off already utilized for
> passwords, so we could have hashes of, say 12 bytes, making it 24 in tota=
l,
> down from 136 from ECC.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--0000000000001859b9060cc7ea37
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Yuri,<br>While not exactly the same, the idea of using =
Lamport chains was analyzed circa 2012 in the context of cryptocurrencies.=
=C2=A0<div>I proposed a new=C2=A0signature scheme called MAVE [1], and then=
 a cryptocurrency scheme called MAVEPAY [2] to reduce the size of signature=
s to a minimum of 3 hash verifications per signature, assuming a blockchain=
 or time-stamping service.</div><div><br></div><div>Later there was a simil=
ar proposal by A. Miller called FawkesCoin [3] (using &quot;Guy Fawkes Prot=
ocol&quot; [4] or fawkes signatures, for short).<br><br></div><div>regards<=
/div><div><br></div><div>[1] <a href=3D"https://bitslog.files.wordpress.com=
/2012/04/mave1.pdf">https://bitslog.files.wordpress.com/2012/04/mave1.pdf</=
a></div><div>[2]=C2=A0<a href=3D"https://bitslog.files.wordpress.com/2012/0=
4/mavepay1.pdf">https://bitslog.files.wordpress.com/2012/04/mavepay1.pdf</a=
></div><div>[3]=C2=A0<a href=3D"https://link.springer.com/chapter/10.1007/9=
78-3-319-12400-1_36">https://link.springer.com/chapter/10.1007/978-3-319-12=
400-1_36</a><br>[4] R. J. Anderson, F. Bergadano, B. Crispo, J.-H. Lee, C. =
Manifavas, and R. M. Needham. A new family of authentication protocols. Ope=
rating Systems Review, 32(4):9=E2=80=9320, 1998.<br></div><div><br></div></=
div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On=
 Mon, Dec 18, 2023 at 6:19=E2=80=AFAM Yuri S VB via bitcoin-dev &lt;<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfo=
undation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin=
g-left:1ex"><div style=3D"font-family:Arial,sans-serif;font-size:14px"></di=
v><div style=3D"line-height:1.5;background-color:rgb(255,255,255)">Dear col=
leagues,<br><br>After having mentioned it in<span>=C2=A0</span><a title=3D"=
a Twitter Space" href=3D"https://twitter.com/i/spaces/1vOxwjWWOqdJB" rel=3D=
"noreferrer nofollow noopener" style=3D"text-decoration:underline" target=
=3D"_blank">a Twitter Space</a><span>=C2=A0</span>a few moments ago, I felt=
 the need to share the idea with you even just as a draft. Utilizing<span>=
=C2=A0</span><a title=3D"Lamport Scheme" href=3D"https://en.wikipedia.org/w=
iki/S/KEY" rel=3D"noreferrer nofollow noopener" style=3D"text-decoration:un=
derline" target=3D"_blank">Lamport Scheme</a>=C2=A0(not<span>=C2=A0</span><=
a title=3D"signature" href=3D"https://en.wikipedia.org/wiki/Lamport_signatu=
re" rel=3D"noreferrer nofollow noopener" style=3D"text-decoration:underline=
" target=3D"_blank">signature</a>) for better byte-efficiency in L1:<br><br=
></div><div style=3D"line-height:1.5;background-color:rgb(255,255,255)"><ol=
 style=3D"margin:0px;padding:0px 0px 0px 2.85714em;font-size:1em"><li style=
=3D"list-style-type:&quot;1. &quot;"><span>Have signing keys consist of the=
 current ECC key AND a Lamport chain;<br></span></li><li style=3D"list-styl=
e-type:&quot;2. &quot;"><span>For signing of a transaction, broadcast a tup=
le consisting of=C2=A0</span></li><ol style=3D"margin:0px;padding:0px 0px 0=
px 2.85714em;list-style-type:lower-alpha"><li><span>the plain transaction,=
=C2=A0</span></li><li><span>hash of the previous Lamport chain concatenated=
 to the transaction</span></li><li>commitment signed by ECC freezing its UT=
XO and promising that in a few blocks time the pre image of hash will be pu=
blished.</li></ol><li style=3D"list-style-type:&quot;3. &quot;">a and b (bu=
t not c) are buried in coinbase session of a block B1 by miner M1;</li><li =
style=3D"list-style-type:&quot;4. &quot;">If upon maturity, such pre-image =
is not broadcasted, signed commitment is buried in the next block and execu=
ted. As a consequence, frozen UTXO pays B1 for a and b being buried at M1&#=
39;s coinbase<span>=C2=A0</span><b>and</b><span>=C2=A0</span>miner M2 for b=
urying it [the commitment] in a block B2 subsequent to maturity;</li><li st=
yle=3D"list-style-type:&quot;5. &quot;">If pre-image is broadcasted before =
maturity, it is buried in another block B2&#39;, pays for itself, pays M1 f=
or burying a adn b at B1 and pays whatever else was determined in the plain=
 transaction of item 2.a.<br></li></ol><div><br>The whole point is that, in=
 the typical use case in which pre-image of hash is, in fact, successfully =
broadcasted before maturity, commitment, the only ECC signature in this pro=
tocol is discarded, and only two Lamport hashes end up being buried at L1.<=
br><br>To push economy even further, we could implement a memory-hard hash =
like Argon2 to do the same entropy-processing trade-off already utilized fo=
r passwords, so we could have hashes of, say 12 bytes, making it 24 in tota=
l, down from 136 from ECC.</div></div><div style=3D"font-family:Arial,sans-=
serif;font-size:14px"><div>
    </div>
</div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000001859b9060cc7ea37--