Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1

From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
To: yurisvb@pm.me,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
Date: Mon, 18 Dec 2023 09:29:48 -0300	[thread overview]
Message-ID: <CAKzdR-qaN7sO62F38tm1ppEow=Oh-3A6kwsfRyts8U+LPXvTnQ@mail.gmail.com> (raw)
In-Reply-To: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me>

[-- Attachment #1: Type: text/plain, Size: 3165 bytes --]

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–20, 1998.

On Mon, Dec 18, 2023 at 6:19 AM 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 Lamport
> 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* miner
>    M2 for burying it [the commitment] in a block B2 subsequent to maturity;
>    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, the
> 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 total,
> down from 136 from ECC.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5033 bytes --]