bitcoin-dev

Lamport scheme (not signature) to economize on L1

Lamport scheme (not signature) to economize on L1

Original Postby yurisvb at pm.me

Posted on: December 22, 2023 15:32 UTC

The email discusses potential vulnerabilities in a cryptographic scheme related to LAMPPRI, addressing the technicalities of cryptanalysis under different conditions.

It outlines three scenarios of concern: the first involves an ADDR before T0-1 without (TX, SIG), the second encompasses both ADDR and (TX, SIG) after T0-1, and the third scenario is about outmining the rest of the mining community after T1 with a significant time disadvantage.

The correspondence highlights a critical aspect that LAMPPUB, despite being a fundamental component of the system, is ironically never published. This leads to the suggestion that LAMPPUB could be significantly large, such as 1Mb or 1Gb, to ensure the collision rate in the hash function HL(.) remains negligible. This approach aligns with the concept of a memory-hard hash function and would allow for a processing-storage trade-off.

In the first scenario, there is an emphasis on the pre-image problem associated with a function f1, which maps a valid ECCPRI and a valid LAMPPRI to an ADDR format. The second scenario details a similar pre-image problem with function f2_(TX,ECCPUB), which takes a valid LAMPPRI to an ADDR format paired with a specific LSIG, instead of any LSIG format. This nuance indicates that any advantage gained in the second scenario over the first must be offset by the ability to complete the protocol successfully before an attack takes place.

The third scenario equates to a double-spending attack where the adversary is at a disadvantage of not less than (T1-T0-1) blocks compared to the rest of the community.

Further in the email, there is an acknowledgment of the need to calculate the entropy for each case, assuming ideal hashes. However, based on an approximation provided by Boris, it's noted that the strength of security would be derived from half the size of ADDR rather than half of LAMPPRI, thus achieving the intended security goal.

A notable proposition towards the end of the email is the potential for a multi-use version of the scheme. In this variation, LAMPPRI would be generated from the ADDR resulting from a previous pair of (ECCPUB, LAMPPUB). This adjustment would reduce blockchain bloat by effectively removing one whole ADDR from the chain and further reducing it by an additional marginal 12 bytes per use, potentially more depending on the added strength.