Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id C8C84C0037 for ; 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 ; 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 ; 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 ; 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 ; 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: In-Reply-To: From: Sergio Demian Lerner Date: Mon, 18 Dec 2023 09:29:48 -0300 Message-ID: To: yurisvb@pm.me, Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 > a few moments ago, I felt > the need to share the idea with you even just as a draft. Utilizing Lampo= rt > Scheme (not 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
Hi Yuri,
While not exactly the same, the idea of using = Lamport chains was analyzed circa 2012 in the context of cryptocurrencies.= =C2=A0
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.

Later there was a simil= ar proposal by A. Miller called FawkesCoin [3] (using "Guy Fawkes Prot= ocol" [4] or fawkes signatures, for short).

regards<= /div>

[3]=C2=A0https://link.springer.com/chapter/10.1007/978-3-319-12= 400-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. Ope= rating 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.linuxfo= undation.org> wrote:
Dear col= leagues,

After having mentioned it in=C2=A0a Twitter Space=C2=A0a few moments ago, I felt= the need to share the idea with you even just as a draft. Utilizing= =C2=A0Lamport Scheme=C2=A0(not=C2=A0<= 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) for better byte-efficiency in L1:
  • Have signing keys consist of the= current ECC key AND a Lamport chain;
  • For signing of a transaction, broadcast a tup= le consisting of=C2=A0
    1. the plain transaction,= =C2=A0
    2. hash of the previous Lamport chain concatenated= to the transaction
    3. 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.
  • a and b (bu= t not c) are buried in coinbase session of a block B1 by miner M1;
  • 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=C2=A0and=C2=A0miner M2 for b= urying it [the commitment] in a block B2 subsequent to maturity;
  • If pre-image is broadcasted before = maturity, it is buried in another block B2', 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.

    • 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>
    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.
    _______________________________________________
    bitcoin-dev mailing list
    = bitcoin-dev@lists.linuxfoundation.org
    https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
    --0000000000001859b9060cc7ea37--