People who code: we want your input. Take the Survey
26

2) Has anyone claimed to make any progress with this challenge? Ah that question I can answer now... I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of April. Another team shall have the answer by the 11th or 12th of May (they used a FPGA). I noticed around the end of 2015 that if I used GMP I could find the ...


13

NO, you can't ! I will only consider initial_vector_0 and next_block_0. What you have found is this: +---+ | | | | IV0 ---->+ f +----> state | | | | | +---+ | xor +---------> 1111111111...1 0000000000 +---+ | | | ...


11

A true source of randomness or a Common Reference String (CRS) as it's referred to in cryptography, could potentially be used in some cases in the place of Proof-of-Work, although as forest pointed out it isn't immediately clear how to achieve this or whether it is possible, especially in settings such as blockchains where something closer to a Random Oracle ...


10

Uniformity is a tricky one. SHA-256 (as well as SHA-3 for that matter) follows a heuristic approach. That is, the design is not based on a hardness assumption (for example, the factoring or discrete-log assumption) but on criteria that have only been verified empirically. As such, also the study of uniformity is an empirical study. The development of SHA-1/...


8

What prevents an attacker from building a custom ASIC and buying off-the-shelf DRAM chips, and building systems that pair each ASIC with a DRAM chip? DRAM memory is already pretty optimized for random memory accesses per second per dollar. Since a memory bound PoW spends more time waiting for memory than doing computation, there's little point in using an ...


8

Bitcoin ASIC miners are specialized hardware, which is capable of computing SHA-256 only. If you change almost any parameter in the Bitcoin proof-of-work, the existing miners will be useless. For instance, you could just change SHA-256 to SHA-1 or SHA-3. To be more efficient against spammers equipped with GPU, you might want to employ a hash function that ...


7

Yes, the argument is largely correct. A good memory-hard proof-of-work scheme can be fairly resistant to speedup using ASIC, if designed around a good primitive like Argon2 and parametrized appropriately; in particular, having a large fraction of its cost spent in un-cacheable accesses to enough memory that DRAM is the only economical choice for that. The ...


7

Memory-hard proof-of-work: are they ASIC-resistant? Theoretically, the answer is a clear “no”. Given enough resources (read: invested time and money) and the appropriate knowledge (ASICs don’t grow on trees, they have to be designed) all currently known and/or published “memory-hard PoW” solutions could be rendered into futile efforts. But theory ends ...


6

There has been a huge amount of work on related questions in the past years. As Thomas Prest mention, this problem was considered for memory-hard function, which provably (in some idealized models) require some amount of space to be evaluated. However, MHF alone are only the weakest primitive of this kind; many primitives have been designed that enhance ...


6

A typical thing which you cannot do with a proof of sequential work is achieving time-lock encryption. In time lock encryption, you want the user to be able to retrieve the hidden message only after some time (i.e., you want to "send a message to the future", as its inventors initially put it). With a VDF, you can use the unique secret to mask the secret ...


5

The paper "Proofs of Space: When Space is of the Essence" proposes a scheme that allows a client to prove that it has read/write access to at least $B$ bytes of memory. Basically, the server gives the client a function $f$ that requires at least $B$ bytes to compute, and the client proves it can compute $f$. The method is complicated and I haven't absorbed ...


5

TL;DR: No, this is not memory-hard and may not even be as computationally intense as you would have thought. Suppose we have a hash function $H:\{0,1\}^*\to\{0,1\}^n$, for example SHA-256. Now we can construct $H':\{0,1\}^*\to\{0,1\}^n:m\mapsto H(M\parallel m)$ for some fixed, pre-defined message $M$ and where $\parallel$ denotes concatenation. Note how $H'$...


5

You are misunderstanding what a proof-of-work algorithm is designed to accomplish. It's designed to provide an economic disincentive to repeating the process many times (e.g. sending an email or visiting a website). Real-world values on the other hand have the distinct property of being difficult to predict in advance, making it useful for proving that a ...


4

We know that traditional mathematical proofs can contain mistakes, and that these mistakes can remain undiscovered for years. Sometimes, the scheme is secure even if the proof is incorrect, e.g. RSA-OAEP. Sometimes, the scheme is mildly flawed, the flaws undiscovered because of mistakes in the proof, e.g. HMQV. And sometimes a scheme is simply insecure. We ...


4

Currently, it is probably safe. There are preimage attacks on MD5 but they are only slightly better than brute force. With a proof of work that only requires the initial bits of the hash to match it would likely be easier to use brute force than try to apply any attacks on it. However, I cannot see a good reason you would do that instead of using a more ...


4

In short: the question does not explain well the notion of asymmetry in ECC; and the exposition is not how Elliptic Curve Cryptography works. A reasoning sidestepping the notion of Discrete Logarithm Problem over a finite group can not really explain asymmetry as meant in ECC. Asymmetry is in the knowledge Alice and Bob have about the key, not asymmetry of ...


4

What is the probability that both [Hu] = [Hmu] and [He] = [Hme]. In english, what is the chance that two different files can have identical hashes in both an unencrypted and encrypted form? Depends on whether they are "random" files or attacker controlled. MD5 is a 128-bit hash, so for two random files that differ the probability that they have the same ...


4

I like the features of the second, except for some drawbacks: I don't believe the drawbacks are as bad as you think. 1.This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys. It doesn't help the attacker; if the attacker sees the public key, the ...


4

The Wikipedia definitions are clear; memory-bound functions; Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of memory required to hold data. This is proposed for using against spams, first CPU-bound then memory bound. This algorithms requires to access memory in an ...


3

I see at least one way of doing what you want to do: memory-hard functions. Alice just needs to store a value $m$ and its hash $H(m)$, where $H$ is a memory-hard function and where the parameters are scaled so that you cannot compute $H(m)$ unless you are above a certain memory threshold. See e.g. this article which provides a provably memory-hard hash ...


3

The probability of finding an acceptable number is $$Pr(\mbox{accept})=2^{-20}.$$ Thus the probability not to find an acceptable number is $$Pr(\mbox{reject})=1-Pr(\mbox{accept})=1-2^{-20}.$$ Assuming independent events, the probability not to find an acceptable number in $k$ attempts is given by $$Pr(\mbox{$k$ rejects})=(1-2^{-20})^k.$$ Thus, the ...


3

Updated answer: No, this is not possible with cryptography. You have the ciphertext and you have the key. For all anyone knows, you could have made a copy of those to some other computer and decrypted the ciphertext without telling anyone. There's no way (with cryptography) to prove you haven't done that. One approach would be to implement a secure service ...


3

Can encryption algorithms be used daisy chained like this to create a simple computational puzzle… It can be done, but remember encryption algos are built to be (among other things) fast/speedy while hash algos generally tend to be slower (which is the main reason why — as an example — Bitcoin uses SHA256d for its POW). This is one of a few reasons I would ...


3

Taking away the worries Would the provided "Prefix: " provide a weakness that can be exploited? No, any secure cipher should be protected against plaintext attacks. To be precise, the ciphertext should be indistinguishable (not leak any info) for Chosen Plaintext Attacks. This is abreviated to IND_CPA. This is a stronger notion than just a known ...


3

Since they're all competing, the hash-power used to create a block in 10 minutes, is 1/4 of the total hashing power. That's not correct. If the work effort is set to $n$, that is, it takes an expected $2^n$ hashes before someone finds a valid preimage. If Alice, Bob, Charlie and Eve are all working equally hard, then we would expect that each one would ...


3

If you give me enough information to evaluate $h$ on inputs of my choice, then I can easily check whether $h$ is sensitive to the $i$th bit of input --- just evaluate it on two strings that differ only in their $i$th bit and see if the outputs are the same. So it is not possible to hide this property in the description of a public function.


3

Blockchain is a decentralized system, and PoW secures it with a large computational cost, such as RandomX developed by the Monero development team. If there are no PoW, an attacker would easily acquire enough computer power which can prevent the other nodes from verifying properly. PoW, therefore, makes acquiring such power difficult, or economically ...


2

Amazingly enough, the puzzle was solved a few weeks after @TacticalCoder got an answer, on May 10, as described at https://www.cryptophage.com. Their solution worked in 2 months, rather than nearly 4 years, since they used FPGA hardware optimized for this task. And I think they declared to the LCS that they expected to solve it, just hours after @...


2

I designed Cuckoo Cycle at https://github.com/tromp/cuckoo as the first trivially verifiable, scalable and time-memory-trade-off-hard proof-of-work system. It parallellizes reasonably well up to at least 12 CPU-threads, but is expected to saturate the memory due to random access latencies for some small multiple of that. A GPU has memory with tons of ...


2

Answers surely will be somewhat opinion-based, as no one can really say if manual checks are more or less convincing than automated checks. After all, both can be convincing if communicated/sold successfully to third parties. From my personal point of view, the best approach would be to manually verify the results of automatic verifications. So, first ...


Only top voted, non community-wiki answers of a minimum length are eligible