3 ms·

In late 2013 I came up with the first memory hard Proof-of-Work puzzle, Cuckoo Cycle [1], based on finding fixed-length cycles in random graphs. Recently, custo

by tromp 4y ago

In late 2013 I came up with the first memory hard Proof-of-Work puzzle, Cuckoo Cycle [1], based on finding fixed-length cycles in random graphs. Recently, custom chips were developed to solve it more efficiently than GPUs can. That probably had more impact than the Binary Lambda Calculus language I designed [2] or the logical rules of Go I co-formulated [3]. Computing the number of Go positions [4] or approximating the number of Chess positions [5] had little impact beyond satisfying my intellectual curiosity. [1] https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo [2] https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html [3] https://tromp.github.io/go.html https://tromp.github.io/go.html [4] https://tromp.github.io/go/legal.html https://tromp.github.io/go/legal.html [5] https://github.com/tromp/ChessPositionRanking#readme https://github.com/tromp/ChessPositionRanking#readme

lucb1e 4y ago
> the first memory hard Proof-of-Work puzzle Scrypt is from 2009, per Wikipedia. That's memory hard, and using hashes with some zeroed out bits is a thing done for a long time (Bitcoin 2009; some old meaning of "cryptographic pepper" (fallen out of use) that iirc dates back to the 90s). Am I misunderstanding what you built?
- adastra22 4y ago
  SCrypt was thought to be memory hard. It was not, and making asics for it ended up being pretty trivial.
  - tromp 4y ago
    Scrypt is memory hard. The reason ASICs were easy to make was the small memory requirement chosen to make PoW verification not too slow.
- tromp 4y ago
  Scrypt [1] is a password based key derivation function (PBKDF), which can be used as a hash function that takes a configurable amount of memory to compute. The reason it makes a very poor PoW (as choice of hash function in the Hashcash Proof-of-Work) is that the PoW verifier needs as much memory as the PoW prover, whereas a good PoW should be instantly verifiable. This is why blockchains using scrypt as hash function severely limit the amount of memory used (usually to 128KB). So that verification, while slow, is not horribly slow. Cuckoo Cycle also requires a configurable amount of memory to solve (subject to certain tradeoffs), but crucially, can be instantly verified with no memory use at all. And thus makes for a good PoW. In the form of the Cuckatoo32 variant that most mining takes place with, it requires 0.5 GB of SRAM and 0.5 GB of DRAM to solve most efficiently. [1] https://en.wikipedia.org/wiki/Scrypt https://en.wikipedia.org/wiki/Scrypt
  - lucb1e 4y ago
    > the PoW verifier needs as much memory as the PoW prover, whereas a good PoW should be instantly verifiable Ooh, yes I see, that is a big difference. Cool work!

by tromp 4y ago

lucb1e 4y ago

> the first memory hard Proof-of-Work puzzle Scrypt is from 2009, per Wikipedia. That's memory hard, and using hashes with some zeroed out bits is a thing done for a long time (Bitcoin 2009; some old meaning of "cryptographic pepper" (fallen out of use) that iirc dates back to the 90s). Am I misunderstanding what you built?

adastra22 4y ago
SCrypt was thought to be memory hard. It was not, and making asics for it ended up being pretty trivial.
- tromp 4y ago
  Scrypt is memory hard. The reason ASICs were easy to make was the small memory requirement chosen to make PoW verification not too slow.
tromp 4y ago
Scrypt [1] is a password based key derivation function (PBKDF), which can be used as a hash function that takes a configurable amount of memory to compute. The reason it makes a very poor PoW (as choice of hash function in the Hashcash Proof-of-Work) is that the PoW verifier needs as much memory as the PoW prover, whereas a good PoW should be instantly verifiable. This is why blockchains using scrypt as hash function severely limit the amount of memory used (usually to 128KB). So that verification, while slow, is not horribly slow. Cuckoo Cycle also requires a configurable amount of memory to solve (subject to certain tradeoffs), but crucially, can be instantly verified with no memory use at all. And thus makes for a good PoW. In the form of the Cuckatoo32 variant that most mining takes place with, it requires 0.5 GB of SRAM and 0.5 GB of DRAM to solve most efficiently. [1] https://en.wikipedia.org/wiki/Scrypt https://en.wikipedia.org/wiki/Scrypt
- lucb1e 4y ago
  > the PoW verifier needs as much memory as the PoW prover, whereas a good PoW should be instantly verifiable Ooh, yes I see, that is a big difference. Cool work!