[Cryptography] Looking for sequential-memory-hard hashing

[Zooko Wilcox-OHearn]

Hi Bear:

Nice to correspond with you again. I've been reading your posts on
mailing lists for a long time now. ☺

I don't have an opinion about your proposed algorithm, but I wanted to
point out some related work: the candidates from the Password Hashing
Competition. Many of them, e.g. Catena
(https://password-hashing.net/submissions/specs/Catena-v3.pdf ), are
explicitly designed to be usable as proofs of work, and I kind of
suspect that *any* of them *could* serve as a proof-of-work, because
the Password Hashing Problem seems to be almost the same thing as the
Proof Of Work Problem. Many of them (again, including Catena) are
memory-oriented.

Another piece of related work is John Tromp's Cuckoo Hashing Proof Of
Work: https://raw.githubusercontent.com/tromp/cuckoo/master/cuckoo.pdf

I think there is a pretty close relationship between your proposal of
partially-colliding triplets which have a relationship between the
three pre-images and Cuckoo. To see what I mean, read the part of the
cuckoo PDF about "Momentum", which is a lot like your proposal and
which Cuckoo is a generalization of.

Regards,

Zooko