Date: Tue, 19 Dec 2023 21:22:20 +0000
To: Nagaev Boris <bnagaev@gmail.com>
From: yurisvb@pm.me
Message-ID: <HG9-9VDKRd3-0v0x9QP05_Cjyk9Y3UW-94A1RHsT3xMQYmb7Y6sk9-wTUlqVZzm6ACigM7aM-B6NB-z6jVCCXhQIGEYkEcBKryzP587FlIo=@pm.me>
In-Reply-To: <CAFC_Vt5PcqqcREJ67Jzcg=K+Agd02a9f5uSit8LwkYHshbvF7A@mail.gmail.com>
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>
 <CAFC_Vt5PcqqcREJ67Jzcg=K+Agd02a9f5uSit8LwkYHshbvF7A@mail.gmail.com>
Feedback-ID: 15605746:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature";
 micalg=pgp-sha256;
 boundary="------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8";
 charset=utf-8
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
Precedence: list

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8
Content-Type: multipart/mixed;boundary=---------------------3f06cd0490d8849548ba8601b8734abf

-----------------------3f06cd0490d8849548ba8601b8734abf
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;charset=utf-8

Thank you for putting yourself through the working of carefully analyzing =
my proposition, Boris!

1) My demonstration concludes 12 bytes is still a very conservative figure=
 for the hashes. I'm not sure where did you get the 14 bytes figure. This =
is 2*(14-12) =3D 4 bytes less.

2) Thank you for pointing out that ECCPUB is necessary. That's exactly rig=
ht and I failed to realize that. To lessen the exposure, and the risk of m=
iner of LSIG, it can be left to be broadcast together with LAMPPRI.

3) I avail to advocate for economizing down the fingerprint to just 128 bi=
ts for the weakest-link-principle, since 128 bits is a nearly ubiquitous s=
tandard, employed even by the majority of seeds. Not an argument against p=
lain Schnorr, because Schnorr keys could use it too, but, compared with cu=
rrent implementations, we have that would be 20-16=3D4 bytes less.

4) [Again, argument against plain, because it cuts for both sides:] To eco=
nomize even further, there is also the entropy-derivation cost trade-off o=
f N times costlier derivation for log2(N) less bits. If applied to the Add=
ress, we could shave away another byte.

5) T0 is just the block height of burying of LSIG doesn't need to be burie=
d. T2 can perfectly be hard-coded to always be the block equivalent of T0 =
+ 48 hours (a reasonable spam to prevent innocent defaulting on commitment=
 due to network unavailability). T1 is any value such as T0 < T1 < T2, (ty=
pically T1 <=3D T0+6) of user's choosing, to compromise between, on one ha=
nd, the convenience of unfreezing UTXO and having TX mining completed ASAP=
 and, on the other, avoiding the risk of blockchain forking causing LAMPPR=
I to be accidentally leaked in the same block height as LSIG, which allows=
 for signatures to be forged. So this is 16 bytes less.

Miners would keep record of unconfirmed BL's, because of the reward of min=
ing either possible outcome of it (successful transaction or execution of =
commitment). Everything is paid for.

So, unless I'm forgetting something else, all other variables kept equal, =
we have 20 bytes lighter than Schnorr; and up to 25 bytes less the current=
 implementation of Schnorr, if items 3 and 4 are implemented too. Already =
we have a reduction of between 21% and 26%, while, so far, nobody in the m=
ailing list has disputed how 'outrageously' conservative the 12 bytes figu=
re is.

Any other objections?

YSVB

Sent with Proton Mail secure email.

On Tuesday, December 19th, 2023 at 6:08 PM, Nagaev Boris <bnagaev@gmail.co=
m> wrote:


> 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 finge=
rprint an ECC (Schnorr or otherwise conventional) public-key, which is not=
 published until first transaction. For clarity:
> > =


> > HL(.) =3D serial-work- and memory-hard hash with short digest (ex.: Ar=
gon2 with ~ 12 bytes output. "L" for "Lamport");
> > HC(.) =3D nonspecific representation of conventional, serial-work- and=
 memory-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 Sch=
norr instead)
> > LAMPPUB =3D HL(LAMPPRIi)
> > LAMPPRI =3D HL(seed, tag) //Though it is (more) feasible to crack a se=
ed 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, crac=
king seed is still as hard as cracking a conventional seed.
> > ADDR =3D H(ECCPUB, LAMPPUB) //Conventional BTC key fingerprinting with=
 conventionally used hashes and their respective brute-force-resistant dig=
est lengths
> > TX =3D plaintext transaction
> > LSIG =3D HL(TX, LAMPPRI)
> > COMMITMENT =3D Smart contract stating "This UTXO is frozen until one o=
f the following happens: A) publishing of a L such that HL(TX,L) =3D LSIG =
before T2 in which case TX is deemed valid and executed, or B) T2 blocks f=
rom now, when miner of LSIG has gets F1+FF1, and the miner of COMMITMENT g=
ets FC, both from UTXO"
> > BL =3D "Bundle of Lamport scheme" =3D (TX, LSIG)
> > BC =3D "Bundle of Commitment and Conventional Signing" =3D (COMMITMENT=
, ECCPRI(COMMITMENT), ECCPUB, LAMPPUB) //LAMPPUB is added here to allow ea=
sy 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 ~ T=
0+1 to T0+6 blocks. This is to protect owner from dissensus (revealing LAM=
PPRI in a block and have it utilized to forge transaction in a competing b=
lock of same height).
> > T2 =3D Block height of expiration of commitment ~ T0+24 hours to T0+ a=
 few days to protect user from execution of commitment being triggered by =
innocent unavailability.
> > =


> > From ADDR alone, Miners, cannot forge a valid LSIG, nor try to ascerta=
in LAMPPUB or LAMPPRI, because of pre-image-resistance of H(.) and brute-f=
orce resistance of ECCPUB before being published. The saving happens becau=
se, safe from T2 passing without LAMPRI being broadcasted, only BL and LAM=
PPR, and not BC, end up in Blockchain.
> > =


> > The proposed scheme, therefore allows for only 1 instance of Lamport s=
chemed-based economic transaction, which has to be the first transaction o=
f ADDR (because of publishing of ECCPUB). After this first transaction, AD=
DR is stil valid, just no longer able to issue transactions.
> > =


> > The proposed scheme, therefore, favors the good practice of non-addres=
s reuse.
> > =


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


> =


> =


> --
> Best regards,
> Boris Nagaev
-----------------------3f06cd0490d8849548ba8601b8734abf
Content-Type: application/pgp-keys; filename="publickey - yurisvb@pm.me - 0x535F445D.asc"; name="publickey - yurisvb@pm.me - 0x535F445D.asc"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="publickey - yurisvb@pm.me - 0x535F445D.asc"; name="publickey - yurisvb@pm.me - 0x535F445D.asc"

LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4c0JOQkYySmpSWUJDQUM1MXlo
K0s0MmF0c0V5MGdCTmgvaklXR1hzQnRFLzdJOGFuUmZkZTcvcWdHeXkKbEx4TXFZRE1OelUwN3c5
Z3VINllKRDdWdzNaUmxTVGVqNU9Hc2laOFJ2OUp4YXBYc0MxeDMrdHhOQkFQClYyVml1MVpsMnhK
Y29sTDkrem9SUmhmU25lVDVaZm1IQlpBSklKbmhOdU80ajhrRi9iNDRFaEZ3NkwvTgpGbE9rK1VC
SkVvS0FFQWttd09aWWpVTDd6MStRdzJBZkJIVGVwNFMzYmY4SmZMNDFOUVJsRnBSa3MrSkMKTjNa
c0ozZmZhNURjWjVqTGgyK2k5Mlg2eE8yVW5nM0hLYXhJYTVtbzB3cGVvQ1JQdUxNRjE2cjVQelJ4
CjJmNldzZVlUbWVmZWVYUGUzZEhyTTR4ai9ndHpBRGNxaFd6VVZLM21ZNTdPTXhVYjJ4MWdqZ1Z6
QUJFQgpBQUhOSFhsMWNtbHpkbUpBY0cwdWJXVWdQSGwxY21semRtSkFjRzB1YldVK3dzQjFCQkFC
Q0FBZkJRSmQKaVkwV0Jnc0pCd2dEQWdRVkNBb0NBeFlDQVFJWkFRSWJBd0llQVFBS0NSQXYzelY4
UzhOTVZkTkRCLzlRCnZRRlpZNkRzR3FMOTlkKzI2QjdHYmRCb0VjenUxL2NqTVpNdE9QeW9nSElF
eXllalR3R1RVN3ZYNEpWZQozRHZnbnd4U2xIYjQ2dDU2VGV3OU5rZ2V4MmFIb0hGRnJBd3MraTVa
ajdZN2lhL2l2RVozZE1KR3dNSUoKeVlQS08rdG1ockxNYWlSSFdnUnhtSG5mRnhUY1dFQ1dSZEk3
dDRJWFp3Rm9QN2Z3TVVVVXQrV3NTbzJSCnJhUVZEL3NTL2F2TlF5T2h6YTlLcVBQNjBZY3B2RUtj
UXArL2hyTjRRcFhVSkxiaDFZMVlqeUhlbDhnQgpRa3p2QzUwUjVxTzRlY2xxSy9FMEhESnlDWmZN
TThkV2o0REJrTWN2SzlsYjB5b3ZRMDFFTXp1NkU1NEcKYjZ0VFp1bktQTVpVd1J1SW5FY0hHMjV0
azdWUEM4clJTU0hqeDhTT3pzQk5CRjJKalJZQkNBQ3RiUWdNCldRSnMvTVdZbDR2THRLSlhYbFlS
T2h1YkVWbjRjTFdZSmVFWHpzSllCQWRlNWh0QlEzc212UjJ2NnVJegptejJpaXFsSkVVdmYwY2xM
WS9QVExoSGVTbWE5VTRodzRaRDNZKzV6WWxINURza2l1N3lLZTdIVmpEVmkKd1FJN25acWRvanJs
dDhCZENiOVNMaXRNaFRvR1crS2E1VCtUOWNmbWthMk1qa3pRSFBNTEJtdVJ6a2V2ClBkZFF6M0xB
MjMzZDNHREVTZklCYy91OC9YelBUNkZTZ3MzSEh4OEFJbFdQbEJaYmh6WmpQNlRLclRNRQpOSEtK
cmxTRlZKclErL25QU28ya0VSL0VDczF0aUJEY0JkamVPYWx6LzdRVWN0Rnp3NGdjS0RtMGpUeEkK
cVhWVlV3a2tuRkM4NDZMTjNBT2p0UWRyOVV3czVsTzhkeXBGQUJFQkFBSEN3RjhFR0FFSUFBa0ZB
bDJKCmpSWUNHd3dBQ2drUUw5ODFmRXZEVEZXS2VBZ0FxRXN1QXJMZFprYXBvZDI3K2hpcHZZNUcr
eVRLQW1NMApIVlhmQzJiMVdtNXQwQXhOVXVkMlJ1OTE1MHA3V09CRXpXYkxnNXdzOTc1M296dlZi
cFpIQU9uVGZOeXoKUUR5QWhmZ1hNQjIvdzRERXEwT2tlQVBRNXhsQWtISDZpUW1hSkZiYy9FRjRX
ZWZWeE92MnNRNDlRNks5Ci9Bb1FROG54RVh1RzRidXVrclEwTGVlTVAzNEdMWUhYK2JvWENHQmxI
MGhiZm5kc3VQbEdqYnBnWVErdQplclJGTlB4N1JtSWtnQjJ0WmhwZkZ3VGtid1c2TVFmWDM5Z3F1
SitwVEVKUnA5UmpJVjFZU2txSjZJUkgKQkc4eFBocGgzT3huaWJyWkdlbGdtakpNM2QwM1k5OSs3
OXBvdTRlY09BeWYyTHMrMVVTY2NDTzA2YnI4CldlcjJ3cmI0WXc9PQo9aHJheAotLS0tLUVORCBQ
R1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCg==
-----------------------3f06cd0490d8849548ba8601b8734abf--

--------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: ProtonMail

wsBzBAEBCAAnBYJlggl5CZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL
w0xVAACU+gf+KpdrCimgxN9BpYm33VRwkp0Z7lRMZLaXjPU0L04saeDwedyN
xUKJQn+e0v8bhLjcTduGS2GFdnTatw/PsIMWTnV4zH2207St0nZM+7I/+9uY
w+YvvvjvQV2Go2E3AJNjqA5Wz/nJlppY9rQHMFP+23VOVuEzP9cu7pdQNttq
KxIap36rz7i+ShJcbqua7s+DkNeW1fBG6ikoM8LvYaZ/MKGjuIHpmOBUjLdx
xDt221xj03DSeIIJNNOR1RSF/VO1DGoUNqYZMNv2lmm15EvfR+Uzwq8THkRC
wy0oJjm4JI8vbd4qYCbr+zLkF7HfTjYzwE9ihnX3ehGqJd8g4YjXXA==
=YX0X
-----END PGP SIGNATURE-----


--------92a542ae0e51e7c7edc271876fb1e019e442ebc8ca96f04b032950b376d0d2a8--