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"
Subject: Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
Precedence: list

--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--