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

From: "G. Andrew Stone" <[email-masked]>
Date: Thu, 21 Dec 2023 23:52:08 -0500

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 <
[email-masked]> 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 <
> [email-masked]> wrote:
>
>
> > On Tue, Dec 19, 2023 at 6:22 PM [email-masked] 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
> [email-masked]
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>