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

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

[yurisvb]

[-- Attachment #1.1.1: Type: text/plain, Size: 1700 bytes --]

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

4.  a and b (but not c) are buried in coinbase session of a block B1 by miner M1;
5.  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;
6.  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.

[-- Attachment #1.1.2.1: Type: text/html, Size: 3309 bytes --]

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[Sergio Demian Lerner]

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

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

[Nagaev Boris]

Hey Yuri,

On Mon, Dec 18, 2023 at 6:19 AM Yuri S VB via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> down from 136 from ECC.

Schnorr signature has size 64 bytes (serialized format consists of x
coordinate of R and of s, 32 bytes each).

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

Two SHA256 hashes are 64 bytes in total, the same as one schnorr signature.

> 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

12 bytes security for spending bitcoins is not enough, is it?

-- 
Best regards,
Boris Nagaev

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 6061 bytes --]

I beg to disagree: key owner broadcasts first bundle (let's call it this way) so that it is on any miner's best interest to include said bundle on their's attempted coinbase because they know if they don't any other competing miner will in the next block.

Once more I think it's worth mentioning the principle of weakest link: if cracking this Lamport chain within the stipulated few blocks time is harder than the double-spending attack, by definition, it's (much!) more than hard enough.

Consider a 12 bytes = 96 bits Lamport hash link (Less than half a Schnorr signature). Assume a cracking power of one order of magnitude higher than the current global hash rate of say 10^21 H/s. Already our assumption is outrageously pessimistic for more that two reasons: 1) The whole premise of Bitcoin being secure is presumptive unfeasibility of that attack (weakest-link argument); 2) Memory-hard hashes, by definition, are ASIC-resistant in the first place (so, being less efficient than ASICS, the CPUs necessary to match that hashing power would be far *more* costly than today's total global mining hardware). In other words, we are giving away the hardness of the hash.

Let's assume a generous window of 1M seconds, so 10^27 hashes. Multiplying that by log2(10), we have shy of 2^89 hashes (actually it's 2^ 'shy of 89', but again: erring on the side of safety). That divided by our 2^96 possible pre-images gives a probability of approximately 2^-6 < 0.02. This doesn't sound very impressive, but an important thing to have in mind is that this attack would destroy utility only of its specific victim (owner of target UTXO), unlikely the 50%+epsilon attack, in which the adversary may block whomever they want from ever having a transaction mined. Again, we are giving away over 11 days for good measure to safeguard against loss of connection.

More importantly, the economic viability of that attack: if your UTXO has less than ~50 times the cost of that operation, which we could lower bound for, say, half of blocks rewards (again, generously assuming 100% ROI for mining). Let's be generous once again disregard mining fees, which would give us (block reward)*(seconds)/((1+ROI)*(second per block)*(prob. success)) = 6.25*10^6 / (2*600*0.02)BTC ~ 260416 BTC.

So mine is an argument of economic viability: clearly adversary's economy of scale is positive, and it doesn't make sense to consider an adversary with more scale than that necessary for double spending. Even at that unrealistically large scale, however, and even assuming your adversary would gain 1000 times more utility than what they make their victim loose, it would still be unworthy to conduct such attack to an UTXO of less than 1K BTC.

In retrospect, I'm beginning to think that 12 bytes is rather an overkill.

YSVB

Sent with Proton Mail secure email.

On Monday, December 18th, 2023 at 6:48 PM, Nagaev Boris <bnagaev@gmail.com> wrote:


> On Mon, Dec 18, 2023 at 2:22 PM yurisvb@pm.me wrote:
> 

> > Most Wallets implement BIP39 with 12 words, which corresponds to 128 bits of entropy + 4 of checksum (so really only 128 bits).
> > 

> > 2 times that would get even to one Schnorr signature, as you say.
> > Going lower than 128 per hash is, IMO admissible under the same premise of memory-hard hashes like Argon2, Scrypt, CryptoNight, Catena, Balloon Hashing, or Krypton8 (the latter of my authoring, a fully homomorphically encryptable memory-hard hash). You make hashing N times more time-costly under some conservative assumption and allow for the alleviation of log2(N) bits from your key. It's widely adopted in passwords (Argon2, for instance, being the 2015 Password Hash Competition) since human memorization of password is a critical weak link in security and UX. BIP39 itself resorts to PBKDF2 with 2048 iterations with the same goal, even though it's not memory-hard. But there is more:
> > 

> > By design, my proposed Lamport chain needs only to resist brute-force for a few blocks time, so key strength can be cheapened even further. Keep in mind that before its first transaction, the public-key of an address is not published, so the window of opportunity for brute-forcing a key with lower strength really only opens upon the broadcasting of the transaction, and closes within a few blocks time.
> 

> 

> IIRC, miner M1 is the only party who verifies the ECC signature in the
> proposed protocol. If M1 is malicious, he can crack the short hash of
> an address in advance (spending as much time as needed). He should do
> it twice to know the next two hashes. Then mines the first transaction
> (in which he steals coins from the address) with the first hash and
> then publish the second hash a few blocks later to finalize the theft.
> 

> > YSVB
> > 

> > Sent with Proton Mail secure email.
> > 

> > On Monday, December 18th, 2023 at 5:45 PM, Nagaev Boris bnagaev@gmail.com wrote:
> > 

> > > Hey Yuri,
> > 

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

> > > > down from 136 from ECC.
> > 

> > > Schnorr signature has size 64 bytes (serialized format consists of x
> > > coordinate of R and of s, 32 bytes each).
> > 

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

> > > Two SHA256 hashes are 64 bytes in total, the same as one schnorr signature.
> > 

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

> > > 12 bytes security for spending bitcoins is not enough, is it?
> > 

> > > --
> > > Best regards,
> > > Boris Nagaev
> 

> 

> 

> 

> --
> Best regards,
> Boris Nagaev

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[Nagaev Boris]

On Mon, Dec 18, 2023 at 7:44 PM <yurisvb@pm.me> wrote:
>
> I beg to disagree: key owner broadcasts first bundle (let's call it this way) so that it is on any miner's best interest to include said bundle on their's attempted coinbase because they know if they don't any other competing miner will in the next block.

What if an attacker broadcasts the first bundle? He spent a lot of
time cracking the hash which is the part of the address in the
proposed scheme. Then he cracked the second layer of hashing to have
both hashes ready. If the utxo has enough sats, the attack is
economically viable.


-- 
Best regards,
Boris Nagaev

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 3907 bytes --]

Thank you for the question, Boris. That was an easy one:

Short answer is Lamport hashes are protected by long hash of key fingerprint an ECC (Schnorr or otherwise conventional) public-key, which is not published until first transaction. For clarity:

HL(.) = serial-work- and memory-*hard* hash with *short* digest (ex.: Argon2 with ~ 12 bytes output. "L" for "Lamport");
HC(.) = nonspecific representation of conventional, serial-work- and memory-*easy* hashes with *long* (brute-force-resistant) digest length. "C" for "Conventional";
KDF(.) = conventional key deriving function
ECCPUB = public key correspondent to ECCPRI
ECCPRI = KDF(seed, tag) //conventional BTC signing key (could be Schnorr instead)
LAMPPUB = HL(LAMPPRIi)
LAMPPRI = HL(seed, tag) //Though it is (more) feasible to crack a seed S that works as pre-image to LAMPRI, such seed can only be deemed valid if the public key correspondent to KDF(s) = ECCPUB, so ultimately, cracking seed is still as hard as cracking a conventional seed.
ADDR = H(ECCPUB, LAMPPUB) //Conventional BTC key fingerprinting with conventionally used hashes and their respective brute-force-resistant digest lengths
TX = plaintext transaction
LSIG = HL(TX, LAMPPRI)
COMMITMENT = Smart contract stating "This UTXO is frozen until one of the following happens: A) publishing of a L such that HL(TX,L) = LSIG before T2 in which case TX is deemed valid and executed, or B) T2 blocks from now, when miner of LSIG has gets F1+FF1, and the miner of COMMITMENT gets FC, both from UTXO"
BL = "Bundle of Lamport scheme" = (TX, LSIG)
BC = "Bundle of Commitment and Conventional Signing" = (COMMITMENT, ECCPRI(COMMITMENT), ECCPUB, LAMPPUB)	//LAMPPUB is added here to allow easy verification that ECCPUB corresponds to ADDR
BT = "Total Bundle" = (BL, BC)
F1 = fee offered to mine BL
FF1 = fine offered to miner of BL to compensate for delay
FC = fee offered to mine BC in case of default
T0 = Block height of broadcasting of BT
T1 = Block height owner should aim at broadcasting LAMPPRI  block ~ T0+1 to T0+6 blocks. This is to protect owner from dissensus (revealing LAMPPRI in a block and have it utilized to forge transaction in a competing block of same height).
T2 = 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 ascertain LAMPPUB or LAMPPRI, because of pre-image-resistance of H(.) and brute-force resistance of ECCPUB before being published. The saving happens because, safe from T2 passing without LAMPRI being broadcasted, only BL and LAMPPR, and not BC, end up in Blockchain.

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

The proposed scheme, therefore, favors the good practice of non-address reuse.

YSVB

Sent with Proton Mail secure email.

On Tuesday, December 19th, 2023 at 1:45 AM, Nagaev Boris <bnagaev@gmail.com> wrote:


> On Mon, Dec 18, 2023 at 7:44 PM yurisvb@pm.me wrote:
> 

> > I beg to disagree: key owner broadcasts first bundle (let's call it this way) so that it is on any miner's best interest to include said bundle on their's attempted coinbase because they know if they don't any other competing miner will in the next block.
> 

> 

> What if an attacker broadcasts the first bundle? He spent a lot of
> time cracking the hash which is the part of the address in the
> proposed scheme. Then he cracked the second layer of hashing to have
> both hashes ready. If the utxo has enough sats, the attack is
> economically viable.
> 

> 

> --
> Best regards,
> Boris Nagaev

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[Nagaev Boris]

On Tue, Dec 19, 2023 at 11:07 AM <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 fingerprint an ECC (Schnorr or otherwise conventional) public-key, which is not published until first transaction. For clarity:
>
> HL(.) = serial-work- and memory-*hard* hash with *short* digest (ex.: Argon2 with ~ 12 bytes output. "L" for "Lamport");
> HC(.) = nonspecific representation of conventional, serial-work- and memory-*easy* hashes with *long* (brute-force-resistant) digest length. "C" for "Conventional";
> KDF(.) = conventional key deriving function
> ECCPUB = public key correspondent to ECCPRI
> ECCPRI = KDF(seed, tag) //conventional BTC signing key (could be Schnorr instead)
> LAMPPUB = HL(LAMPPRIi)
> LAMPPRI = HL(seed, tag) //Though it is (more) feasible to crack a seed S that works as pre-image to LAMPRI, such seed can only be deemed valid if the public key correspondent to KDF(s) = ECCPUB, so ultimately, cracking seed is still as hard as cracking a conventional seed.
> ADDR = H(ECCPUB, LAMPPUB) //Conventional BTC key fingerprinting with conventionally used hashes and their respective brute-force-resistant digest lengths
> TX = plaintext transaction
> LSIG = HL(TX, LAMPPRI)
> COMMITMENT = Smart contract stating "This UTXO is frozen until one of the following happens: A) publishing of a L such that HL(TX,L) = LSIG before T2 in which case TX is deemed valid and executed, or B) T2 blocks from now, when miner of LSIG has gets F1+FF1, and the miner of COMMITMENT gets FC, both from UTXO"
> BL = "Bundle of Lamport scheme" = (TX, LSIG)
> BC = "Bundle of Commitment and Conventional Signing" = (COMMITMENT, ECCPRI(COMMITMENT), ECCPUB, LAMPPUB)        //LAMPPUB is added here to allow easy verification that ECCPUB corresponds to ADDR
> BT = "Total Bundle" = (BL, BC)
> F1 = fee offered to mine BL
> FF1 = fine offered to miner of BL to compensate for delay
> FC = fee offered to mine BC in case of default
> T0 = Block height of broadcasting of BT
> T1 = Block height owner should aim at broadcasting LAMPPRI  block ~ T0+1 to T0+6 blocks. This is to protect owner from dissensus (revealing LAMPPRI in a block and have it utilized to forge transaction in a competing block of same height).
> T2 = 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 ascertain LAMPPUB or LAMPPRI, because of pre-image-resistance of H(.) and brute-force resistance of ECCPUB before being published. The saving happens because, safe from T2 passing without LAMPRI being broadcasted, only BL and LAMPPR, and not BC, end up in Blockchain.
>
> The proposed scheme, therefore allows for only 1 instance of Lamport schemed-based economic transaction, which has to be the first transaction of ADDR (because of publishing of ECCPUB). After this first transaction, ADDR is stil valid, just no longer able to issue transactions.
>
> The proposed scheme, therefore, favors the good practice of non-address 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 = H(ECCPUB, LAMPPUB)
 - input 1: LSIG (14 bytes)
 - input 2: ECCPUB, LAMPPRI (32+14=46). (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=80 (bytes)
Is this correct?

Taproot:
 - output: 32 bytes (schnorr public key)
 - input: 64 bytes (schnorr signature)
Total: 32+64 = 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

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 6845 bytes --]

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) = 4 bytes less.

2) Thank you for pointing out that ECCPUB is necessary. That's exactly right and I failed to realize that. To lessen the exposure, and the risk of miner 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 bits for the weakest-link-principle, since 128 bits is a nearly ubiquitous standard, employed even by the majority of seeds. Not an argument against plain Schnorr, because Schnorr keys could use it too, but, compared with current implementations, we have that would be 20-16=4 bytes less.

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

5) T0 is just the block height of burying of LSIG doesn't need to be buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on one hand, the convenience of unfreezing UTXO and having TX mining completed ASAP and, on the other, avoiding the risk of blockchain forking causing LAMPPRI 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 mining 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 mailing list has disputed how 'outrageously' conservative the 12 bytes figure is.

Any other objections?

YSVB

Sent with Proton Mail secure email.

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


> On Tue, Dec 19, 2023 at 11:07 AM 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 fingerprint an ECC (Schnorr or otherwise conventional) public-key, which is not published until first transaction. For clarity:
> > 

> > HL(.) = serial-work- and memory-hard hash with short digest (ex.: Argon2 with ~ 12 bytes output. "L" for "Lamport");
> > HC(.) = nonspecific representation of conventional, serial-work- and memory-easy hashes with long (brute-force-resistant) digest length. "C" for "Conventional";
> > KDF(.) = conventional key deriving function
> > ECCPUB = public key correspondent to ECCPRI
> > ECCPRI = KDF(seed, tag) //conventional BTC signing key (could be Schnorr instead)
> > LAMPPUB = HL(LAMPPRIi)
> > LAMPPRI = HL(seed, tag) //Though it is (more) feasible to crack a seed S that works as pre-image to LAMPRI, such seed can only be deemed valid if the public key correspondent to KDF(s) = ECCPUB, so ultimately, cracking seed is still as hard as cracking a conventional seed.
> > ADDR = H(ECCPUB, LAMPPUB) //Conventional BTC key fingerprinting with conventionally used hashes and their respective brute-force-resistant digest lengths
> > TX = plaintext transaction
> > LSIG = HL(TX, LAMPPRI)
> > COMMITMENT = Smart contract stating "This UTXO is frozen until one of the following happens: A) publishing of a L such that HL(TX,L) = LSIG before T2 in which case TX is deemed valid and executed, or B) T2 blocks from now, when miner of LSIG has gets F1+FF1, and the miner of COMMITMENT gets FC, both from UTXO"
> > BL = "Bundle of Lamport scheme" = (TX, LSIG)
> > BC = "Bundle of Commitment and Conventional Signing" = (COMMITMENT, ECCPRI(COMMITMENT), ECCPUB, LAMPPUB) //LAMPPUB is added here to allow easy verification that ECCPUB corresponds to ADDR
> > BT = "Total Bundle" = (BL, BC)
> > F1 = fee offered to mine BL
> > FF1 = fine offered to miner of BL to compensate for delay
> > FC = fee offered to mine BC in case of default
> > T0 = Block height of broadcasting of BT
> > T1 = Block height owner should aim at broadcasting LAMPPRI block ~ T0+1 to T0+6 blocks. This is to protect owner from dissensus (revealing LAMPPRI in a block and have it utilized to forge transaction in a competing block of same height).
> > T2 = 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 ascertain LAMPPUB or LAMPPRI, because of pre-image-resistance of H(.) and brute-force resistance of ECCPUB before being published. The saving happens because, safe from T2 passing without LAMPRI being broadcasted, only BL and LAMPPR, and not BC, end up in Blockchain.
> > 

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

> > The proposed scheme, therefore, favors the good practice of non-address 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 = H(ECCPUB, LAMPPUB)
> - input 1: LSIG (14 bytes)
> - input 2: ECCPUB, LAMPPRI (32+14=46). (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=80 (bytes)
> Is this correct?
> 

> Taproot:
> - output: 32 bytes (schnorr public key)
> - input: 64 bytes (schnorr signature)
> Total: 32+64 = 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

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[Nagaev Boris]

On Tue, Dec 19, 2023 at 6:22 PM <yurisvb@pm.me> wrote:
>
> 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) = 4 bytes less.

I agree. It should have been 12.

> 2) Thank you for pointing out that ECCPUB is necessary. That's exactly right and I failed to realize that. To lessen the exposure, and the risk of miner 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 bits for the weakest-link-principle, since 128 bits is a nearly ubiquitous standard, employed even by the majority of seeds. Not an argument against plain Schnorr, because Schnorr keys could use it too, but, compared with current implementations, we have that would be 20-16=4 bytes less.

I think that the digest size for hash should be 2x key size for
symmetric encryption. To find a collision (= break) for a hash
function with digest size 128 bits one needs to calculate ~ 2^64
hashes because of the birthday paradox.

> 4) [Again, argument against plain, because it cuts for both sides:] To economize even further, there is also the entropy-derivation cost trade-off of N times costlier derivation for log2(N) less bits. If applied to the Address, we could shave away another byte.
>
> 5) T0 is just the block height of burying of LSIG doesn't need to be buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on one hand, the convenience of unfreezing UTXO and having TX mining completed ASAP and, on the other, avoiding the risk of blockchain forking causing LAMPPRI 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 mining 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 mailing list has disputed how 'outrageously' conservative the 12 bytes figure is.

26% reduction of block space utilization would be great, but the price
of relying on 12 bytes hashes (only need 2^48 hashes to find a
collision) is too much for that, IMHO.

Another consideration is about 12 byte hashes. Let's try to figure out
if they are resistant to rainbow table attack by a large organization.
Let's assume that the rainbow table has a chain length of 1024^3 (billion).
What storage size is needed? 2^96 * 12 / 1024^3 = 900 exabytes.
Both chain length and storage size seems prohibitively high for today,
but tomorrow the hash function can be optimized, memory can be
optimized, storage can become cheaper etc. And this attack may be
affordable for state level attackers.

> Any other objections?
>
> YSVB
>


-- 
Best regards,
Boris Nagaev

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 4803 bytes --]

You are right to point out that my proposal was lacking defense against rainbow-table, because there is a simple solution for it:
To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting LSIG, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only unknown by the builder of rainbow table while they made it, which is the case, since here we have 8*32=256 bits for LSIG, and the entropy of ECCPUB in the second.

With rainbow table out of our way, there is only brute-force analysis to mind. Honestly, Guess I should find a less 'outrageously generous' upper bound for adversary's model, than just assume they have a magic wand to convert SHA256 ASICS into CPU with the same hashrate for memory- and serial-work-hard hashes (therefore giving away hash hardness). That's because with such 'magic wand' many mining pools would, not only be capable of cracking 2^48 hashes far within the protocol's prescribed 48 hours, but also 2^64 within a block time, which would invalidate a lot of what is still in use today.

Please, allow me a few days to think that through.

YSVB

Sent with Proton Mail secure email.

On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris <bnagaev@gmail.com> wrote:


> On Tue, Dec 19, 2023 at 6:22 PM yurisvb@pm.me wrote:
>
> > 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) = 4 bytes less.
>
>
> I agree. It should have been 12.
>
> > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly right and I failed to realize that. To lessen the exposure, and the risk of miner 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 bits for the weakest-link-principle, since 128 bits is a nearly ubiquitous standard, employed even by the majority of seeds. Not an argument against plain Schnorr, because Schnorr keys could use it too, but, compared with current implementations, we have that would be 20-16=4 bytes less.
>
>
> I think that the digest size for hash should be 2x key size for
> symmetric encryption. To find a collision (= break) for a hash
> function with digest size 128 bits one needs to calculate ~ 2^64
> hashes because of the birthday paradox.
>
> > 4) [Again, argument against plain, because it cuts for both sides:] To economize even further, there is also the entropy-derivation cost trade-off of N times costlier derivation for log2(N) less bits. If applied to the Address, we could shave away another byte.
> >
> > 5) T0 is just the block height of burying of LSIG doesn't need to be buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on one hand, the convenience of unfreezing UTXO and having TX mining completed ASAP and, on the other, avoiding the risk of blockchain forking causing LAMPPRI 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 mining 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 mailing list has disputed how 'outrageously' conservative the 12 bytes figure is.
>
>
> 26% reduction of block space utilization would be great, but the price
> of relying on 12 bytes hashes (only need 2^48 hashes to find a
> collision) is too much for that, IMHO.
>
> Another consideration is about 12 byte hashes. Let's try to figure out
> if they are resistant to rainbow table attack by a large organization.
> Let's assume that the rainbow table has a chain length of 1024^3 (billion).
> What storage size is needed? 2^96 * 12 / 1024^3 = 900 exabytes.
> Both chain length and storage size seems prohibitively high for today,
> but tomorrow the hash function can be optimized, memory can be
> optimized, storage can become cheaper etc. And this attack may be
> affordable for state level attackers.
>
> > Any other objections?
> >
> > YSVB
>
>
>
> --
> Best regards,
> Boris Nagaev

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[G. Andrew Stone]

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

Does this affect the security model WRT chain reorganizations?  In the
classic doublespend attack, an attacker can only redirect UTXOs that they
spent.  With this proposal, if I understand it correctly, an attacker could
redirect all funds that have "matured" (revealed the previous preimage in
the hash chain) to themselves.  The # blocks to maturity in your proposal
becomes the classic "embargo period" and every coin spent by anyone between
the fork point and the maturity depth is available to the attacker to
doublespend?

On Thu, Dec 21, 2023, 8:05 PM Yuri S VB via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> You are right to point out that my proposal was lacking defense against
> rainbow-table, because there is a simple solution for it:
> To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting
> LSIG, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only
> unknown by the builder of rainbow table while they made it, which is the
> case, since here we have 8*32=256 bits for LSIG, and the entropy of ECCPUB
> in the second.
>
> With rainbow table out of our way, there is only brute-force analysis to
> mind. Honestly, Guess I should find a less 'outrageously generous' upper
> bound for adversary's model, than just assume they have a magic wand to
> convert SHA256 ASICS into CPU with the same hashrate for memory- and
> serial-work-hard hashes (therefore giving away hash hardness). That's
> because with such 'magic wand' many mining pools would, not only be capable
> of cracking 2^48 hashes far within the protocol's prescribed 48 hours, but
> also 2^64 within a block time, which would invalidate a lot of what is
> still in use today.
>
> Please, allow me a few days to think that through.
>
> YSVB
>
> Sent with Proton Mail secure email.
>
> On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris <
> bnagaev@gmail.com> wrote:
>
>
> > On Tue, Dec 19, 2023 at 6:22 PM yurisvb@pm.me wrote:
> >
> > > 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) = 4 bytes less.
> >
> >
> > I agree. It should have been 12.
> >
> > > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly
> right and I failed to realize that. To lessen the exposure, and the risk of
> miner 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 bits for the weakest-link-principle, since 128 bits is a nearly
> ubiquitous standard, employed even by the majority of seeds. Not an
> argument against plain Schnorr, because Schnorr keys could use it too, but,
> compared with current implementations, we have that would be 20-16=4 bytes
> less.
> >
> >
> > I think that the digest size for hash should be 2x key size for
> > symmetric encryption. To find a collision (= break) for a hash
> > function with digest size 128 bits one needs to calculate ~ 2^64
> > hashes because of the birthday paradox.
> >
> > > 4) [Again, argument against plain, because it cuts for both sides:] To
> economize even further, there is also the entropy-derivation cost trade-off
> of N times costlier derivation for log2(N) less bits. If applied to the
> Address, we could shave away another byte.
> > >
> > > 5) T0 is just the block height of burying of LSIG doesn't need to be
> buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on
> one hand, the convenience of unfreezing UTXO and having TX mining completed
> ASAP and, on the other, avoiding the risk of blockchain forking causing
> LAMPPRI 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
> mining 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 mailing list has disputed how 'outrageously' conservative the 12
> bytes figure is.
> >
> >
> > 26% reduction of block space utilization would be great, but the price
> > of relying on 12 bytes hashes (only need 2^48 hashes to find a
> > collision) is too much for that, IMHO.
> >
> > Another consideration is about 12 byte hashes. Let's try to figure out
> > if they are resistant to rainbow table attack by a large organization.
> > Let's assume that the rainbow table has a chain length of 1024^3
> (billion).
> > What storage size is needed? 2^96 * 12 / 1024^3 = 900 exabytes.
> > Both chain length and storage size seems prohibitively high for today,
> > but tomorrow the hash function can be optimized, memory can be
> > optimized, storage can become cheaper etc. And this attack may be
> > affordable for state level attackers.
> >
> > > Any other objections?
> > >
> > > YSVB
> >
> >
> >
> > --
> > Best regards,
> > Boris Nagaev_______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 8434 bytes --]

There are three possible cryptanalysis to LAMPPRI in my scheme:

1.  From ADDR alone before T0-1 (to be precise, publishing of (TX, SIG));
2.  From ADDR and (TX, SIG) after T0-1 (to be precise, publishing of (TX, SIG));
3.  Outmine the rest of mining community starting from a disadvantage of not less than (T1-T0-1) after T1 (to be precise, at time of publishing of LAMPRI);

...which bring us back to my argument with Boris: There is something else we missed in our considerations, which you said yourself: *ironically, LAMPPUB is never published*.

We can have LAMPPUB be 1Mb or even 1Gb long aiming at having rate of collision in HL(.) be negligible (note this is perfectly adherent to the proposition of memory-hard-hash, and would have the additional benefit of allowing processing-storage trade-off). In this case, we really have:

For 1: a pre-image problem for a function 

f1: {k| k is a valid ECCPRI} X {l | l is a valid LAMPPRI} -> {a | a is in the format of a ADDR}
having as domain the Cartesian product of set of possible ECCPRIs with set of possible LAMPPRIs and counter domain, the set of possible ADDRs.

For 2: a pre-image problem for a function 

f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {LSIG}
(notice the nuance: {LSIG} means the singleton containing of only the specific LSIG that was actually public, not 'in the format of LSIGs').

Notice that, whatever advantage of 2 over 1 has to be compensated by the perspective of having the protocol be successfully terminated before the attack being carried out.

For 3: Equivalente of a double-spending attack with, in the worst case, not less than (T1-T0-1) blocks in advantage for the rest of the community.

When I have the time, I'll do the math on what is the entropy on each case, assuming ideal hashes, but taking for granted the approximation given by Boris, we would have half of size of ADDR as strength, not half of LAMPPRI, so mission accomplished!

Another ramification of that is we can conceive a multi-use version of this scheme, in which LAMPPRI is the ADDR resulting of a previous (ECCPUB, LAMPPUB) pair. The increased size of LAMPPRI would be compensated by one entire ADDR less in the blockchain. Namely, we'd have an extra marginal reduction of 12 bytes per use (possibly more, depending on how much more bytes we can economize given that added strength).

YSVB.

On Friday, December 22nd, 2023 at 5:52 AM, G. Andrew Stone <g.andrew.stone@gmail.com> wrote:


> Does this affect the security model WRT chain reorganizations? In the classic doublespend attack, an attacker can only redirect UTXOs that they spent. With this proposal, if I understand it correctly, an attacker could redirect all funds that have "matured" (revealed the previous preimage in the hash chain) to themselves. The # blocks to maturity in your proposal becomes the classic "embargo period" and every coin spent by anyone between the fork point and the maturity depth is available to the attacker to doublespend?
> 

> On Thu, Dec 21, 2023, 8:05 PM Yuri S VB via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 

> > You are right to point out that my proposal was lacking defense against rainbow-table, because there is a simple solution for it:
> > To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting LSIG, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only unknown by the builder of rainbow table while they made it, which is the case, since here we have 8*32=256 bits for LSIG, and the entropy of ECCPUB in the second.
> > 

> > With rainbow table out of our way, there is only brute-force analysis to mind. Honestly, Guess I should find a less 'outrageously generous' upper bound for adversary's model, than just assume they have a magic wand to convert SHA256 ASICS into CPU with the same hashrate for memory- and serial-work-hard hashes (therefore giving away hash hardness). That's because with such 'magic wand' many mining pools would, not only be capable of cracking 2^48 hashes far within the protocol's prescribed 48 hours, but also 2^64 within a block time, which would invalidate a lot of what is still in use today.
> > 

> > Please, allow me a few days to think that through.
> > 

> > YSVB
> > 

> > Sent with Proton Mail secure email.
> > 

> > On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris <bnagaev@gmail.com> wrote:
> > 

> > 

> > > On Tue, Dec 19, 2023 at 6:22 PM yurisvb@pm.me wrote:
> > >
> > > > 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) = 4 bytes less.
> > >
> > >
> > > I agree. It should have been 12.
> > >
> > > > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly right and I failed to realize that. To lessen the exposure, and the risk of miner 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 bits for the weakest-link-principle, since 128 bits is a nearly ubiquitous standard, employed even by the majority of seeds. Not an argument against plain Schnorr, because Schnorr keys could use it too, but, compared with current implementations, we have that would be 20-16=4 bytes less.
> > >
> > >
> > > I think that the digest size for hash should be 2x key size for
> > > symmetric encryption. To find a collision (= break) for a hash
> > > function with digest size 128 bits one needs to calculate ~ 2^64
> > > hashes because of the birthday paradox.
> > >
> > > > 4) [Again, argument against plain, because it cuts for both sides:] To economize even further, there is also the entropy-derivation cost trade-off of N times costlier derivation for log2(N) less bits. If applied to the Address, we could shave away another byte.
> > > >
> > > > 5) T0 is just the block height of burying of LSIG doesn't need to be buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on one hand, the convenience of unfreezing UTXO and having TX mining completed ASAP and, on the other, avoiding the risk of blockchain forking causing LAMPPRI 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 mining 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 mailing list has disputed how 'outrageously' conservative the 12 bytes figure is.
> > >
> > >
> > > 26% reduction of block space utilization would be great, but the price
> > > of relying on 12 bytes hashes (only need 2^48 hashes to find a
> > > collision) is too much for that, IMHO.
> > >
> > > Another consideration is about 12 byte hashes. Let's try to figure out
> > > if they are resistant to rainbow table attack by a large organization.
> > > Let's assume that the rainbow table has a chain length of 1024^3 (billion).
> > > What storage size is needed? 2^96 * 12 / 1024^3 = 900 exabytes.
> > > Both chain length and storage size seems prohibitively high for today,
> > > but tomorrow the hash function can be optimized, memory can be
> > > optimized, storage can become cheaper etc. And this attack may be
> > > affordable for state level attackers.
> > >
> > > > Any other objections?
> > > >
> > > > YSVB
> > >
> > >
> > >
> > > --
> > > Best regards,
> > > Boris Nagaev_______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 9627 bytes --]

Dear all,

Upon second thoughts, I concluded have to issue a correction on my last correspondence. Where I wrote:

> For 2: a pre-image problem for a function
> f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {LSIG}
> 

> (notice the nuance: {LSIG} means the singleton containing of only the specific LSIG that was actually public, not 'in the format of LSIGs').

Please read 


"For 2: a pre-image problem for a function
f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {s | s is 'in the format of LSIGs'}"

instead, and completely disregard the nuance below, which is wrong. I apologize for the mistake, and hope I have made myself clear. Thank you, again for your interest, and I'll be back with formulas for entropy in both cases soon!

YSVB

Sent with Proton Mail secure email.

On Friday, December 22nd, 2023 at 4:32 PM, yurisvb@pm.me <yurisvb@pm.me> wrote:


> There are three possible cryptanalysis to LAMPPRI in my scheme:
> 

> 1. From ADDR alone before T0-1 (to be precise, publishing of (TX, SIG));
> 2. From ADDR and (TX, SIG) after T0-1 (to be precise, publishing of (TX, SIG));
> 3. Outmine the rest of mining community starting from a disadvantage of not less than (T1-T0-1) after T1 (to be precise, at time of publishing of LAMPRI);
> 

> ...which bring us back to my argument with Boris: There is something else we missed in our considerations, which you said yourself: ironically, LAMPPUB is never published.
> 

> We can have LAMPPUB be 1Mb or even 1Gb long aiming at having rate of collision in HL(.) be negligible (note this is perfectly adherent to the proposition of memory-hard-hash, and would have the additional benefit of allowing processing-storage trade-off). In this case, we really have:
> 

> For 1: a pre-image problem for a function
> f1: {k| k is a valid ECCPRI} X {l | l is a valid LAMPPRI} -> {a | a is in the format of a ADDR}
> 

> having as domain the Cartesian product of set of possible ECCPRIs with set of possible LAMPPRIs and counter domain, the set of possible ADDRs.
> 

> For 2: a pre-image problem for a function
> f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {LSIG}
> 

> (notice the nuance: {LSIG} means the singleton containing of only the specific LSIG that was actually public, not 'in the format of LSIGs').
> 

> Notice that, whatever advantage of 2 over 1 has to be compensated by the perspective of having the protocol be successfully terminated before the attack being carried out.
> 

> For 3: Equivalente of a double-spending attack with, in the worst case, not less than (T1-T0-1) blocks in advantage for the rest of the community.
> 

> When I have the time, I'll do the math on what is the entropy on each case, assuming ideal hashes, but taking for granted the approximation given by Boris, we would have half of size of ADDR as strength, not half of LAMPPRI, so mission accomplished!
> 

> Another ramification of that is we can conceive a multi-use version of this scheme, in which LAMPPRI is the ADDR resulting of a previous (ECCPUB, LAMPPUB) pair. The increased size of LAMPPRI would be compensated by one entire ADDR less in the blockchain. Namely, we'd have an extra marginal reduction of 12 bytes per use (possibly more, depending on how much more bytes we can economize given that added strength).
> 

> YSVB.
> 

> On Friday, December 22nd, 2023 at 5:52 AM, G. Andrew Stone g.andrew.stone@gmail.com wrote:
> 

> 

> 

> > Does this affect the security model WRT chain reorganizations? In the classic doublespend attack, an attacker can only redirect UTXOs that they spent. With this proposal, if I understand it correctly, an attacker could redirect all funds that have "matured" (revealed the previous preimage in the hash chain) to themselves. The # blocks to maturity in your proposal becomes the classic "embargo period" and every coin spent by anyone between the fork point and the maturity depth is available to the attacker to doublespend?
> > 

> > On Thu, Dec 21, 2023, 8:05 PM Yuri S VB via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
> > 

> > > You are right to point out that my proposal was lacking defense against rainbow-table, because there is a simple solution for it:
> > > To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting LSIG, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only unknown by the builder of rainbow table while they made it, which is the case, since here we have 8*32=256 bits for LSIG, and the entropy of ECCPUB in the second.
> > > 

> > > With rainbow table out of our way, there is only brute-force analysis to mind. Honestly, Guess I should find a less 'outrageously generous' upper bound for adversary's model, than just assume they have a magic wand to convert SHA256 ASICS into CPU with the same hashrate for memory- and serial-work-hard hashes (therefore giving away hash hardness). That's because with such 'magic wand' many mining pools would, not only be capable of cracking 2^48 hashes far within the protocol's prescribed 48 hours, but also 2^64 within a block time, which would invalidate a lot of what is still in use today.
> > > 

> > > Please, allow me a few days to think that through.
> > > 

> > > YSVB
> > > 

> > > Sent with Proton Mail secure email.
> > > 

> > > On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris bnagaev@gmail.com wrote:
> > > 

> > > > On Tue, Dec 19, 2023 at 6:22 PM yurisvb@pm.me wrote:
> > > > 

> > > > > 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) = 4 bytes less.
> > > > 

> > > > I agree. It should have been 12.
> > > > 

> > > > > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly right and I failed to realize that. To lessen the exposure, and the risk of miner 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 bits for the weakest-link-principle, since 128 bits is a nearly ubiquitous standard, employed even by the majority of seeds. Not an argument against plain Schnorr, because Schnorr keys could use it too, but, compared with current implementations, we have that would be 20-16=4 bytes less.
> > > > 

> > > > I think that the digest size for hash should be 2x key size for
> > > > symmetric encryption. To find a collision (= break) for a hash
> > > > function with digest size 128 bits one needs to calculate ~ 2^64
> > > > hashes because of the birthday paradox.
> > > > 

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

> > > > > 5) T0 is just the block height of burying of LSIG doesn't need to be buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on one hand, the convenience of unfreezing UTXO and having TX mining completed ASAP and, on the other, avoiding the risk of blockchain forking causing LAMPPRI 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 mining 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 mailing list has disputed how 'outrageously' conservative the 12 bytes figure is.
> > > > 

> > > > 26% reduction of block space utilization would be great, but the price
> > > > of relying on 12 bytes hashes (only need 2^48 hashes to find a
> > > > collision) is too much for that, IMHO.
> > > > 

> > > > Another consideration is about 12 byte hashes. Let's try to figure out
> > > > if they are resistant to rainbow table attack by a large organization.
> > > > Let's assume that the rainbow table has a chain length of 1024^3 (billion).
> > > > What storage size is needed? 2^96 * 12 / 1024^3 = 900 exabytes.
> > > > Both chain length and storage size seems prohibitively high for today,
> > > > but tomorrow the hash function can be optimized, memory can be
> > > > optimized, storage can become cheaper etc. And this attack may be
> > > > affordable for state level attackers.
> > > > 

> > > > > Any other objections?
> > > > > 

> > > > > YSVB
> > > > 

> > > > --
> > > > Best regards,
> > > > Boris Nagaev_______________________________________________
> > > > bitcoin-dev mailing list
> > > > bitcoin-dev@lists.linuxfoundation.org
> > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 10573 bytes --]

Dear all,

Upon a few more days working on my proposed protocol, I've found a way to waive the need for:
1) mining the conventional public key;
2) user broadcasting 2 distinct payloads a few blocks apart;

Up to 66% footprint reduction.

I'll be publishing and submitting it as BIP soon. Those who got interested are more than welcome to get in touch directly.

It's based on my proposed cryptosystem based on the conjectured hardness of factorization of polynomials in finite fields:
https://github.com/Yuri-SVB/FFM-cryptography/

YSVB

Sent with Proton Mail secure email.

On Saturday, December 23rd, 2023 at 1:26 AM, yurisvb@pm.me <yurisvb@pm.me> wrote:


> Dear all,
> 

> Upon second thoughts, I concluded have to issue a correction on my last correspondence. Where I wrote:
> 

> > For 2: a pre-image problem for a function
> > f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {LSIG}
> > 

> > (notice the nuance: {LSIG} means the singleton containing of only the specific LSIG that was actually public, not 'in the format of LSIGs').
> 

> 

> Please read
> 

> "For 2: a pre-image problem for a function
> f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {s | s is 'in the format of LSIGs'}"
> 

> 

> instead, and completely disregard the nuance below, which is wrong. I apologize for the mistake, and hope I have made myself clear. Thank you, again for your interest, and I'll be back with formulas for entropy in both cases soon!
> 

> YSVB
> 

> Sent with Proton Mail secure email.
> 

> 

> On Friday, December 22nd, 2023 at 4:32 PM, yurisvb@pm.me yurisvb@pm.me wrote:
> 

> 

> 

> > There are three possible cryptanalysis to LAMPPRI in my scheme:
> > 

> > 1. From ADDR alone before T0-1 (to be precise, publishing of (TX, SIG));
> > 2. From ADDR and (TX, SIG) after T0-1 (to be precise, publishing of (TX, SIG));
> > 3. Outmine the rest of mining community starting from a disadvantage of not less than (T1-T0-1) after T1 (to be precise, at time of publishing of LAMPRI);
> > 

> > ...which bring us back to my argument with Boris: There is something else we missed in our considerations, which you said yourself: ironically, LAMPPUB is never published.
> > 

> > We can have LAMPPUB be 1Mb or even 1Gb long aiming at having rate of collision in HL(.) be negligible (note this is perfectly adherent to the proposition of memory-hard-hash, and would have the additional benefit of allowing processing-storage trade-off). In this case, we really have:
> > 

> > For 1: a pre-image problem for a function
> > f1: {k| k is a valid ECCPRI} X {l | l is a valid LAMPPRI} -> {a | a is in the format of a ADDR}
> > 

> > having as domain the Cartesian product of set of possible ECCPRIs with set of possible LAMPPRIs and counter domain, the set of possible ADDRs.
> > 

> > For 2: a pre-image problem for a function
> > f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {LSIG}
> > 

> > (notice the nuance: {LSIG} means the singleton containing of only the specific LSIG that was actually public, not 'in the format of LSIGs').
> > 

> > Notice that, whatever advantage of 2 over 1 has to be compensated by the perspective of having the protocol be successfully terminated before the attack being carried out.
> > 

> > For 3: Equivalente of a double-spending attack with, in the worst case, not less than (T1-T0-1) blocks in advantage for the rest of the community.
> > 

> > When I have the time, I'll do the math on what is the entropy on each case, assuming ideal hashes, but taking for granted the approximation given by Boris, we would have half of size of ADDR as strength, not half of LAMPPRI, so mission accomplished!
> > 

> > Another ramification of that is we can conceive a multi-use version of this scheme, in which LAMPPRI is the ADDR resulting of a previous (ECCPUB, LAMPPUB) pair. The increased size of LAMPPRI would be compensated by one entire ADDR less in the blockchain. Namely, we'd have an extra marginal reduction of 12 bytes per use (possibly more, depending on how much more bytes we can economize given that added strength).
> > 

> > YSVB.
> > 

> > On Friday, December 22nd, 2023 at 5:52 AM, G. Andrew Stone g.andrew.stone@gmail.com wrote:
> > 

> > > Does this affect the security model WRT chain reorganizations? In the classic doublespend attack, an attacker can only redirect UTXOs that they spent. With this proposal, if I understand it correctly, an attacker could redirect all funds that have "matured" (revealed the previous preimage in the hash chain) to themselves. The # blocks to maturity in your proposal becomes the classic "embargo period" and every coin spent by anyone between the fork point and the maturity depth is available to the attacker to doublespend?
> > > 

> > > On Thu, Dec 21, 2023, 8:05 PM Yuri S VB via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
> > > 

> > > > You are right to point out that my proposal was lacking defense against rainbow-table, because there is a simple solution for it:
> > > > To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting LSIG, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only unknown by the builder of rainbow table while they made it, which is the case, since here we have 8*32=256 bits for LSIG, and the entropy of ECCPUB in the second.
> > > > 

> > > > With rainbow table out of our way, there is only brute-force analysis to mind. Honestly, Guess I should find a less 'outrageously generous' upper bound for adversary's model, than just assume they have a magic wand to convert SHA256 ASICS into CPU with the same hashrate for memory- and serial-work-hard hashes (therefore giving away hash hardness). That's because with such 'magic wand' many mining pools would, not only be capable of cracking 2^48 hashes far within the protocol's prescribed 48 hours, but also 2^64 within a block time, which would invalidate a lot of what is still in use today.
> > > > 

> > > > Please, allow me a few days to think that through.
> > > > 

> > > > YSVB
> > > > 

> > > > Sent with Proton Mail secure email.
> > > > 

> > > > On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris bnagaev@gmail.com wrote:
> > > > 

> > > > > On Tue, Dec 19, 2023 at 6:22 PM yurisvb@pm.me wrote:
> > > > > 

> > > > > > 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) = 4 bytes less.
> > > > > 

> > > > > I agree. It should have been 12.
> > > > > 

> > > > > > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly right and I failed to realize that. To lessen the exposure, and the risk of miner 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 bits for the weakest-link-principle, since 128 bits is a nearly ubiquitous standard, employed even by the majority of seeds. Not an argument against plain Schnorr, because Schnorr keys could use it too, but, compared with current implementations, we have that would be 20-16=4 bytes less.
> > > > > 

> > > > > I think that the digest size for hash should be 2x key size for
> > > > > symmetric encryption. To find a collision (= break) for a hash
> > > > > function with digest size 128 bits one needs to calculate ~ 2^64
> > > > > hashes because of the birthday paradox.
> > > > > 

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

> > > > > > 5) T0 is just the block height of burying of LSIG doesn't need to be buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on one hand, the convenience of unfreezing UTXO and having TX mining completed ASAP and, on the other, avoiding the risk of blockchain forking causing LAMPPRI 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 mining 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 mailing list has disputed how 'outrageously' conservative the 12 bytes figure is.
> > > > > 

> > > > > 26% reduction of block space utilization would be great, but the price
> > > > > of relying on 12 bytes hashes (only need 2^48 hashes to find a
> > > > > collision) is too much for that, IMHO.
> > > > > 

> > > > > Another consideration is about 12 byte hashes. Let's try to figure out
> > > > > if they are resistant to rainbow table attack by a large organization.
> > > > > Let's assume that the rainbow table has a chain length of 1024^3 (billion).
> > > > > What storage size is needed? 2^96 * 12 / 1024^3 = 900 exabytes.
> > > > > Both chain length and storage size seems prohibitively high for today,
> > > > > but tomorrow the hash function can be optimized, memory can be
> > > > > optimized, storage can become cheaper etc. And this attack may be
> > > > > affordable for state level attackers.
> > > > > 

> > > > > > Any other objections?
> > > > > > 

> > > > > > YSVB
> > > > > 

> > > > > --
> > > > > Best regards,
> > > > > Boris Nagaev_______________________________________________
> > > > > bitcoin-dev mailing list
> > > > > bitcoin-dev@lists.linuxfoundation.org
> > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 13607 bytes --]

Dear all,

Below goes reference to diagram of key derivation of current (hopefully final) version of my proposed protocol, which, now, doesn't rely on FFM cryptosystem.

https://github.com/Yuri-SVB/LVBsig/blob/main/docs/keys_diagram.jpg

Here, you have one-way function derivations happening from left to right, and the final BPMN states representing objects that are eventually published.

h are generic representations of hashes;
H refer to a serial-work- and memory-hard-hash requiring hours to be computed;
FHE stands for Fully Homomorphic Encryption;

The long hash makes it so that ADDR_(i-1) the Lamport pre-image is attainable, but only after the transaction and its hashing are buried a few blocks deep, and that solves any concern about honest loss of access to the internet causing sender be punished by execution of commitment.

Neither PRI_i and PUB_i or commitment need to be buried in the ordinary, expected, seamless execution of protocol because all are easily attainable from ADDR_(i-1), once it's published.

In a few sentences:

1) Sender broadcasts Lamport-schemed-signed TX, which, by itself, is not verifiable;

2) Together with it, sender broadcasts a conventionally signed commitment promising that Lamport-scheme pre-image will be broadcast before T2. This commitment freezes UTXO until either fulfillment of promise, expiration of T2, or attempted breaking of promise by double-spending (broadcasting of another bundle). Fines are established as warranty for all involved miners;

3) Together with it, sender broadcasts Lamport pre-image ADDR_(i-1) encrypted with a symmetric key derived through very long hash from a seed also attached in the bundle. This makes miners able to easily attain ADDR(i-1) safely after Lamport-schemed-signed TX is mined a few blocks deep, but also safely before T2. That also solves concerns of sender innocently losing access to internet (possibly due to an attack) after initial broadcasting, therefore being unfairly punished by execution of COMMITMENT_i.;

4) Upon ADDR_(i-1) being either decrypted by miners or broadcast by sender, Lamport-schemed-signed TX will already be a few blocks deep, ADDR_(i-1) will be mined and validate TX, releasing fees for all miners involved. (PRI_i, PUB_i) are revoked, and ADDR_i becomes an alias for ADDR_(i-1), that can, now, work as an address, having ADDR_(i-2) as Lamport pre-image. If i=1, the Lamport chain is exhausted.

If we have the ADDR's and Lamport-scheme-signatures be 16 bytes long, we reach the promised 32 bytes of on-chain footprint.

Belated Merry Christmas and Happy New Year!

YSVB.

Sent with Proton Mail secure email.

On Friday, December 29th, 2023 at 1:30 AM, yurisvb@pm.me <yurisvb@pm.me> wrote:


> Dear all,
> 

> Upon a few more days working on my proposed protocol, I've found a way to waive the need for:
> 1) mining the conventional public key;
> 2) user broadcasting 2 distinct payloads a few blocks apart;
> 

> Up to 66% footprint reduction.
> 

> I'll be publishing and submitting it as BIP soon. Those who got interested are more than welcome to get in touch directly.
> 

> It's based on my proposed cryptosystem based on the conjectured hardness of factorization of polynomials in finite fields:
> https://github.com/Yuri-SVB/FFM-cryptography/
> 

> YSVB
> 

> Sent with Proton Mail secure email.
> 

> 

> On Saturday, December 23rd, 2023 at 1:26 AM, yurisvb@pm.me yurisvb@pm.me wrote:
> 

> 

> 

> > Dear all,
> > 

> > Upon second thoughts, I concluded have to issue a correction on my last correspondence. Where I wrote:
> > 

> > > For 2: a pre-image problem for a function
> > > f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {LSIG}
> > > 

> > > (notice the nuance: {LSIG} means the singleton containing of only the specific LSIG that was actually public, not 'in the format of LSIGs').
> > 

> > Please read
> > 

> > "For 2: a pre-image problem for a function
> > f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {s | s is 'in the format of LSIGs'}"
> > 

> > instead, and completely disregard the nuance below, which is wrong. I apologize for the mistake, and hope I have made myself clear. Thank you, again for your interest, and I'll be back with formulas for entropy in both cases soon!
> > 

> > YSVB
> > 

> > Sent with Proton Mail secure email.
> > 

> > On Friday, December 22nd, 2023 at 4:32 PM, yurisvb@pm.me yurisvb@pm.me wrote:
> > 

> > > There are three possible cryptanalysis to LAMPPRI in my scheme:
> > > 

> > > 1. From ADDR alone before T0-1 (to be precise, publishing of (TX, SIG));
> > > 2. From ADDR and (TX, SIG) after T0-1 (to be precise, publishing of (TX, SIG));
> > > 3. Outmine the rest of mining community starting from a disadvantage of not less than (T1-T0-1) after T1 (to be precise, at time of publishing of LAMPRI);
> > > 

> > > ...which bring us back to my argument with Boris: There is something else we missed in our considerations, which you said yourself: ironically, LAMPPUB is never published.
> > > 

> > > We can have LAMPPUB be 1Mb or even 1Gb long aiming at having rate of collision in HL(.) be negligible (note this is perfectly adherent to the proposition of memory-hard-hash, and would have the additional benefit of allowing processing-storage trade-off). In this case, we really have:
> > > 

> > > For 1: a pre-image problem for a function
> > > f1: {k| k is a valid ECCPRI} X {l | l is a valid LAMPPRI} -> {a | a is in the format of a ADDR}
> > > 

> > > having as domain the Cartesian product of set of possible ECCPRIs with set of possible LAMPPRIs and counter domain, the set of possible ADDRs.
> > > 

> > > For 2: a pre-image problem for a function
> > > f2_(TX,ECCPUB): {l | l is 'a valid LAMPPRI'} -> {a | a is 'in the format of ADDRs'} X {LSIG}
> > > 

> > > (notice the nuance: {LSIG} means the singleton containing of only the specific LSIG that was actually public, not 'in the format of LSIGs').
> > > 

> > > Notice that, whatever advantage of 2 over 1 has to be compensated by the perspective of having the protocol be successfully terminated before the attack being carried out.
> > > 

> > > For 3: Equivalente of a double-spending attack with, in the worst case, not less than (T1-T0-1) blocks in advantage for the rest of the community.
> > > 

> > > When I have the time, I'll do the math on what is the entropy on each case, assuming ideal hashes, but taking for granted the approximation given by Boris, we would have half of size of ADDR as strength, not half of LAMPPRI, so mission accomplished!
> > > 

> > > Another ramification of that is we can conceive a multi-use version of this scheme, in which LAMPPRI is the ADDR resulting of a previous (ECCPUB, LAMPPUB) pair. The increased size of LAMPPRI would be compensated by one entire ADDR less in the blockchain. Namely, we'd have an extra marginal reduction of 12 bytes per use (possibly more, depending on how much more bytes we can economize given that added strength).
> > > 

> > > YSVB.
> > > 

> > > On Friday, December 22nd, 2023 at 5:52 AM, G. Andrew Stone g.andrew.stone@gmail.com wrote:
> > > 

> > > > Does this affect the security model WRT chain reorganizations? In the classic doublespend attack, an attacker can only redirect UTXOs that they spent. With this proposal, if I understand it correctly, an attacker could redirect all funds that have "matured" (revealed the previous preimage in the hash chain) to themselves. The # blocks to maturity in your proposal becomes the classic "embargo period" and every coin spent by anyone between the fork point and the maturity depth is available to the attacker to doublespend?
> > > > 

> > > > On Thu, Dec 21, 2023, 8:05 PM Yuri S VB via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
> > > > 

> > > > > You are right to point out that my proposal was lacking defense against rainbow-table, because there is a simple solution for it:
> > > > > To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting LSIG, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only unknown by the builder of rainbow table while they made it, which is the case, since here we have 8*32=256 bits for LSIG, and the entropy of ECCPUB in the second.
> > > > > 

> > > > > With rainbow table out of our way, there is only brute-force analysis to mind. Honestly, Guess I should find a less 'outrageously generous' upper bound for adversary's model, than just assume they have a magic wand to convert SHA256 ASICS into CPU with the same hashrate for memory- and serial-work-hard hashes (therefore giving away hash hardness). That's because with such 'magic wand' many mining pools would, not only be capable of cracking 2^48 hashes far within the protocol's prescribed 48 hours, but also 2^64 within a block time, which would invalidate a lot of what is still in use today.
> > > > > 

> > > > > Please, allow me a few days to think that through.
> > > > > 

> > > > > YSVB
> > > > > 

> > > > > Sent with Proton Mail secure email.
> > > > > 

> > > > > On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris bnagaev@gmail.com wrote:
> > > > > 

> > > > > > On Tue, Dec 19, 2023 at 6:22 PM yurisvb@pm.me wrote:
> > > > > > 

> > > > > > > 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) = 4 bytes less.
> > > > > > 

> > > > > > I agree. It should have been 12.
> > > > > > 

> > > > > > > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly right and I failed to realize that. To lessen the exposure, and the risk of miner 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 bits for the weakest-link-principle, since 128 bits is a nearly ubiquitous standard, employed even by the majority of seeds. Not an argument against plain Schnorr, because Schnorr keys could use it too, but, compared with current implementations, we have that would be 20-16=4 bytes less.
> > > > > > 

> > > > > > I think that the digest size for hash should be 2x key size for
> > > > > > symmetric encryption. To find a collision (= break) for a hash
> > > > > > function with digest size 128 bits one needs to calculate ~ 2^64
> > > > > > hashes because of the birthday paradox.
> > > > > > 

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

> > > > > > > 5) T0 is just the block height of burying of LSIG doesn't need to be buried. 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, (typically T1 <= T0+6) of user's choosing, to compromise between, on one hand, the convenience of unfreezing UTXO and having TX mining completed ASAP and, on the other, avoiding the risk of blockchain forking causing LAMPPRI 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 mining 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 mailing list has disputed how 'outrageously' conservative the 12 bytes figure is.
> > > > > > 

> > > > > > 26% reduction of block space utilization would be great, but the price
> > > > > > of relying on 12 bytes hashes (only need 2^48 hashes to find a
> > > > > > collision) is too much for that, IMHO.
> > > > > > 

> > > > > > Another consideration is about 12 byte hashes. Let's try to figure out
> > > > > > if they are resistant to rainbow table attack by a large organization.
> > > > > > Let's assume that the rainbow table has a chain length of 1024^3 (billion).
> > > > > > What storage size is needed? 2^96 * 12 / 1024^3 = 900 exabytes.
> > > > > > Both chain length and storage size seems prohibitively high for today,
> > > > > > but tomorrow the hash function can be optimized, memory can be
> > > > > > optimized, storage can become cheaper etc. And this attack may be
> > > > > > affordable for state level attackers.
> > > > > > 

> > > > > > > Any other objections?
> > > > > > > 

> > > > > > > YSVB
> > > > > > 

> > > > > > --
> > > > > > Best regards,
> > > > > > Boris Nagaev_______________________________________________
> > > > > > bitcoin-dev mailing list
> > > > > > bitcoin-dev@lists.linuxfoundation.org
> > > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[David A. Harding]

Hi Yuri,

I think it's worth noting that for transactions with an equal number of 
P2TR keypath spends (inputs) and P2TR outputs, the amount of space used 
in a transaction by the serialization of the signature itself (16 vbytes 
per input) ranges from a bit over 14% of transaction size (1-input, 
1-output) to a bit less than 16% (10,000-in, 10,000-out; a ~1 MvB tx).  
I infer that to mean that the absolute best a signature replacement 
scheme can do is free up 16% of block space.

An extra 16% of block space is significant, but the advantage of that 
savings needs to be compared to the challenge of creating a highly peer 
reviewed implementation of the new signature scheme and then convincing 
a very large number of Bitcoin users to accept it.  A soft fork proposal 
that introduces new-to-Bitcoin cryptography (such as a different hash 
function) will likely need to be studied for a prolonged period by many 
experts before Bitcoin users become confident enough in it to trust 
their bitcoins to it.  A hard fork proposal has the same challenges as a 
soft fork, plus likely a large delay before it can go into effect, and 
it also needs to be weighed against the much easier process it would be 
for experts and users to review a hard fork that increased block 
capacity by 16% directly.

I haven't fully studied your proposal (as I understand you're working on 
an improved version), but I wanted to put my gut feeling about it into 
words to offer feedback (hopefully of the constructive kind): I think 
the savings in block space might not be worth the cost in expert review 
and user consensus building.

That said, I love innovative ideas about Bitcoin and this is one I will 
remember.  If you continue working on it, I very much look forward to 
seeing what you come up with.  If you don't continue working on it, I 
believe you're likely to think of something else that will be just as 
exciting, if not more so.

Thanks for innovating!,

-Dave

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 3132 bytes --]

Hello, Dave,

I'm afraid I didn't understand your objection. It would be great to have a direct, real-time conversation with you, if you have the availability. Be my guest to DM me for that.

Though this is to be confirmed, I suspect my proposed scheme can be implemented with available, existing Bitcoin infrastructure. As far as my limited knowledge goes, the trickiest part would be to have miners agree that pre-image of hash of a transaction, in a subsequent block is acceptable authentication. As for the commitment, it could be implemented as ordinary smart contracts are, and its size doesn't matter because in the normal use case, it is not mined.

To be clear: The only component that is mined other than addresses and the plaintext transactions would be one hash, between 16 and 20 bytes. From the No-Free-Lunch Principle, the cost for it is that transaction takes a few blocks, instead of just one to be validated.

YSVB

Sent with Proton Mail secure email.

On Sunday, December 31st, 2023 at 8:33 PM, David A. Harding <dave@dtrt.org> wrote:


> Hi Yuri,
> 

> I think it's worth noting that for transactions with an equal number of
> P2TR keypath spends (inputs) and P2TR outputs, the amount of space used
> in a transaction by the serialization of the signature itself (16 vbytes
> per input) ranges from a bit over 14% of transaction size (1-input,
> 1-output) to a bit less than 16% (10,000-in, 10,000-out; a ~1 MvB tx).
> I infer that to mean that the absolute best a signature replacement
> scheme can do is free up 16% of block space.
> 

> An extra 16% of block space is significant, but the advantage of that
> savings needs to be compared to the challenge of creating a highly peer
> reviewed implementation of the new signature scheme and then convincing
> a very large number of Bitcoin users to accept it. A soft fork proposal
> that introduces new-to-Bitcoin cryptography (such as a different hash
> function) will likely need to be studied for a prolonged period by many
> experts before Bitcoin users become confident enough in it to trust
> their bitcoins to it. A hard fork proposal has the same challenges as a
> soft fork, plus likely a large delay before it can go into effect, and
> it also needs to be weighed against the much easier process it would be
> for experts and users to review a hard fork that increased block
> capacity by 16% directly.
> 

> I haven't fully studied your proposal (as I understand you're working on
> an improved version), but I wanted to put my gut feeling about it into
> words to offer feedback (hopefully of the constructive kind): I think
> the savings in block space might not be worth the cost in expert review
> and user consensus building.
> 

> That said, I love innovative ideas about Bitcoin and this is one I will
> remember. If you continue working on it, I very much look forward to
> seeing what you come up with. If you don't continue working on it, I
> believe you're likely to think of something else that will be just as
> exciting, if not more so.
> 

> Thanks for innovating!,
> 

> -Dave

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[David A. Harding]

On 2024-01-01 00:17, yurisvb@pm.me wrote:
> I'm afraid I didn't understand your objection. [...]
> I suspect my proposed scheme can be
> implemented with available, existing Bitcoin infrastructure.

Is a soft fork or a hard fork required?  If so, the proposal will need a 
lot of peer review and user acceptance.

What are the benefits of your proposal?  As I understand it, the benefit 
is smaller transactions.  How much smaller will they be in terms of 
vbytes?  For example, a transaction today with one input performing a 
taproot keypath spend and one taproot-paying output is 111 vbytes[1].  
What will be the total onchain size of an equivalent one-input, 
one-output transaction using your scheme?

My comment (not objection) is that modest decreases in onchain data size 
may not provide a significant enough benefit to attract reviewers and 
interested users, especially if a proposal is complicated by a 
dependencies on many things that have not previously been included in 
Bitcoin (such as new hash functions).

If I'm deeply misunderstanding your proposal and my questions don't make 
sense, I'd very much appreciate a clarification about what your proposal 
does.

Thanks,

-Dave

[1] https://bitcoinops.org/en/tools/calc-size/

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 3865 bytes --]

Dear friends and colleagues,

I believe this current version of the protocol and its documentation, now including a diagram answers the questions raised so far:

https://github.com/Yuri-SVB/LVBsig/blob/main/docs/white_paper.md

All in all, in addition to the plain transaction TXi, only 36 bytes are needed to authenticate it. The number falls to 16 in case of address (address chain) is reused, because change address coincides with Lamport-scheme pre-image.

YSVB.

Sent with Proton Mail secure email.

On Monday, January 1st, 2024 at 11:17 AM, yurisvb@pm.me <yurisvb@pm.me> wrote:


> Hello, Dave,
> 

> I'm afraid I didn't understand your objection. It would be great to have a direct, real-time conversation with you, if you have the availability. Be my guest to DM me for that.
> 

> Though this is to be confirmed, I suspect my proposed scheme can be implemented with available, existing Bitcoin infrastructure. As far as my limited knowledge goes, the trickiest part would be to have miners agree that pre-image of hash of a transaction, in a subsequent block is acceptable authentication. As for the commitment, it could be implemented as ordinary smart contracts are, and its size doesn't matter because in the normal use case, it is not mined.
> 

> To be clear: The only component that is mined other than addresses and the plaintext transactions would be one hash, between 16 and 20 bytes. From the No-Free-Lunch Principle, the cost for it is that transaction takes a few blocks, instead of just one to be validated.
> 

> YSVB
> 

> Sent with Proton Mail secure email.
> 

> 

> On Sunday, December 31st, 2023 at 8:33 PM, David A. Harding dave@dtrt.org wrote:
> 

> 

> 

> > Hi Yuri,
> > 

> > I think it's worth noting that for transactions with an equal number of
> > P2TR keypath spends (inputs) and P2TR outputs, the amount of space used
> > in a transaction by the serialization of the signature itself (16 vbytes
> > per input) ranges from a bit over 14% of transaction size (1-input,
> > 1-output) to a bit less than 16% (10,000-in, 10,000-out; a ~1 MvB tx).
> > I infer that to mean that the absolute best a signature replacement
> > scheme can do is free up 16% of block space.
> > 

> > An extra 16% of block space is significant, but the advantage of that
> > savings needs to be compared to the challenge of creating a highly peer
> > reviewed implementation of the new signature scheme and then convincing
> > a very large number of Bitcoin users to accept it. A soft fork proposal
> > that introduces new-to-Bitcoin cryptography (such as a different hash
> > function) will likely need to be studied for a prolonged period by many
> > experts before Bitcoin users become confident enough in it to trust
> > their bitcoins to it. A hard fork proposal has the same challenges as a
> > soft fork, plus likely a large delay before it can go into effect, and
> > it also needs to be weighed against the much easier process it would be
> > for experts and users to review a hard fork that increased block
> > capacity by 16% directly.
> > 

> > I haven't fully studied your proposal (as I understand you're working on
> > an improved version), but I wanted to put my gut feeling about it into
> > words to offer feedback (hopefully of the constructive kind): I think
> > the savings in block space might not be worth the cost in expert review
> > and user consensus building.
> > 

> > That said, I love innovative ideas about Bitcoin and this is one I will
> > remember. If you continue working on it, I very much look forward to
> > seeing what you come up with. If you don't continue working on it, I
> > believe you're likely to think of something else that will be just as
> > exciting, if not more so.
> > 

> > Thanks for innovating!,
> > 

> > -Dave

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]

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

[yurisvb]

[-- Attachment #1.1: Type: text/plain, Size: 4297 bytes --]

Addendum:

Tomorrow I'll host a Twitter Spaces on this topic:
https://twitter.com/yurivillasboas/status/1743305920937963696
You are all welcome to join!

YSVB

Sent with Proton Mail secure email.

On Friday, January 5th, 2024 at 7:02 PM, yurisvb@pm.me <yurisvb@pm.me> wrote:


> Dear friends and colleagues,
> 

> I believe this current version of the protocol and its documentation, now including a diagram answers the questions raised so far:
> 

> https://github.com/Yuri-SVB/LVBsig/blob/main/docs/white_paper.md
> 

> All in all, in addition to the plain transaction TXi, only 36 bytes are needed to authenticate it. The number falls to 16 in case of address (address chain) is reused, because change address coincides with Lamport-scheme pre-image.
> 

> YSVB.
> 

> Sent with Proton Mail secure email.
> 

> 

> On Monday, January 1st, 2024 at 11:17 AM, yurisvb@pm.me yurisvb@pm.me wrote:
> 

> 

> 

> > Hello, Dave,
> > 

> > I'm afraid I didn't understand your objection. It would be great to have a direct, real-time conversation with you, if you have the availability. Be my guest to DM me for that.
> > 

> > Though this is to be confirmed, I suspect my proposed scheme can be implemented with available, existing Bitcoin infrastructure. As far as my limited knowledge goes, the trickiest part would be to have miners agree that pre-image of hash of a transaction, in a subsequent block is acceptable authentication. As for the commitment, it could be implemented as ordinary smart contracts are, and its size doesn't matter because in the normal use case, it is not mined.
> > 

> > To be clear: The only component that is mined other than addresses and the plaintext transactions would be one hash, between 16 and 20 bytes. From the No-Free-Lunch Principle, the cost for it is that transaction takes a few blocks, instead of just one to be validated.
> > 

> > YSVB
> > 

> > Sent with Proton Mail secure email.
> > 

> > On Sunday, December 31st, 2023 at 8:33 PM, David A. Harding dave@dtrt.org wrote:
> > 

> > > Hi Yuri,
> > > 

> > > I think it's worth noting that for transactions with an equal number of
> > > P2TR keypath spends (inputs) and P2TR outputs, the amount of space used
> > > in a transaction by the serialization of the signature itself (16 vbytes
> > > per input) ranges from a bit over 14% of transaction size (1-input,
> > > 1-output) to a bit less than 16% (10,000-in, 10,000-out; a ~1 MvB tx).
> > > I infer that to mean that the absolute best a signature replacement
> > > scheme can do is free up 16% of block space.
> > > 

> > > An extra 16% of block space is significant, but the advantage of that
> > > savings needs to be compared to the challenge of creating a highly peer
> > > reviewed implementation of the new signature scheme and then convincing
> > > a very large number of Bitcoin users to accept it. A soft fork proposal
> > > that introduces new-to-Bitcoin cryptography (such as a different hash
> > > function) will likely need to be studied for a prolonged period by many
> > > experts before Bitcoin users become confident enough in it to trust
> > > their bitcoins to it. A hard fork proposal has the same challenges as a
> > > soft fork, plus likely a large delay before it can go into effect, and
> > > it also needs to be weighed against the much easier process it would be
> > > for experts and users to review a hard fork that increased block
> > > capacity by 16% directly.
> > > 

> > > I haven't fully studied your proposal (as I understand you're working on
> > > an improved version), but I wanted to put my gut feeling about it into
> > > words to offer feedback (hopefully of the constructive kind): I think
> > > the savings in block space might not be worth the cost in expert review
> > > and user consensus building.
> > > 

> > > That said, I love innovative ideas about Bitcoin and this is one I will
> > > remember. If you continue working on it, I very much look forward to
> > > seeing what you come up with. If you don't continue working on it, I
> > > believe you're likely to think of something else that will be just as
> > > exciting, if not more so.
> > > 

> > > Thanks for innovating!,
> > > 

> > > -Dave

[-- Attachment #1.2: publickey - yurisvb@pm.me - 0x535F445D.asc --]
[-- Type: application/pgp-keys, Size: 1678 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 509 bytes --]