Questions tagged [proof-of-work]

This tag should be used for questions regarding the function and use of proof-of-work systems and proof-of-work algorithms. Proof of work describes a decentralized consensus system based on an arbitrary mathematical problem that is moderately hard to solve but easy to verify.

Filter by
Sorted by
Tagged with
2
votes
1answer
129 views

Prove that certain amount of data was stored

I'm looking for a way to prove that a certain amount of data was stored, through some easily verifiable piece of information. Similarly to how proof-of-work can prove through a hash that a certain ...
3
votes
0answers
53 views

Can you elaborate on pBFT for dBFT in relation to PoW and PoS consensus algorithms in layman's terms?

I've read all other related answers and googled this extensively. My intention and background in asking this question is that I am delving into cryptocurrency and blockchain technology in general. ...
1
vote
1answer
113 views

Is the proof-of-work algorithm "Quark" insecure?

I recently found out about Quark here. Apparently it is a proof-of-work algorithm used by several cryptocurrencies and is based on a single-level hash function, which consists of 9 different levels of ...
10
votes
1answer
2k views

Proof of work designed for CPUs?

My naive understanding of proof-of-work algorithms is that they are essentially a p=np type problem where it's easy to check a solution, but difficult to produce a solution. I have recently read that ...
1
vote
1answer
77 views

Complexity of Hash mining/signing

While reading about mining in crypto currency, I found that it requires some leading bits of a hash function output to be 0. This boils down to preimage resistance of the hash function, hence done ...
4
votes
2answers
137 views

Why aren't public-private keys sufficient to build a block chain? Why do we need proof of work/stake?

Taking the simple case of Bitcoin here: If all nodes can validate published transactions by checking the signature (created using the private key of the sender) of the transaction against the public ...
1
vote
2answers
128 views

What are alternatives to Proof of Work for consensus of a blockchain that doesn't contain anything of value?

For example, a distributed blockchain that would keep track of the weather. Anyone could add a weather reading, and several of these would be stored in each block, just like transactions in a ...
4
votes
2answers
142 views

Single-block hash construction based on a block cipher with two fixed keys

Let k1, k2 be two arbitrary fixed keys (nothing-up-my-sleeve values like "foo" and "bar") and ...
0
votes
1answer
49 views

Partial proof of work: an hash function that validates parts of input, insensitive to the rest

In typical proof of work, there is a one-way hash-function that takes binary inputs and generates an output $h(x,y)$ where $x,y\in\{0,1\}^M$ are binary inputs, so that finding $x$ for a certain $y$ ...
2
votes
3answers
115 views

Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)

I'm working at understanding the Wesolowski and Pietrzak RSA group based VDFs (verifiable delay functions). These basically work by requiring the prover to do a bunch of repeated squaring within a ...
0
votes
0answers
22 views

Universal Computation “measurement” using SNARKs?

If SNARKs are able to prove computations of arbitrary complexity and difficulty were executed correctly, would it be possible to use them to create a Proof of Work consensus system where ANY ...
4
votes
1answer
396 views

"Memory-Hard" vs. "Memory-Bound" Functions?

One of the approaches in order to prevent Sybil or DoS attacks is CPU-bound PoW. However, because of the influence of Moore’s law, the memory-based approaches are suggested. As actually there are two ...
0
votes
0answers
24 views

Identify the value of the plaintext from a noised expression

Having the following instructions: Using Paillier encryption to encrypt $m$. So, we get $Enc(m)$ Multiply $Enc(m)$ and $A$ to Get $C$. So, $C = Enc(m).A $ Decrypt $C$ using Paillier Decryption ...
1
vote
0answers
32 views

Asymmetric non-interactive proof of work scheme

I'm looking for a non-interactive proof of work scheme. I want for it to (1) be faster to find solutions to if you're in the possession of an arbitrary secret, like a private key, and (2) for the ...
0
votes
0answers
16 views

Scrypt cipher - known vulnerabilities and cryptanalysis? [duplicate]

there is a Scrypt cipher which is used for exmaple by some cryptos like LItecoin for their mining algorithm. I never heared of scrypt. I know eg SHA256 which is well analyzed and considered as secure ...
5
votes
2answers
378 views

Why not use random world events instead of a proof-of-work algorithm?

Taking a combination of world events-- thunder, astronomical imagery, vote outcomes, stock index value-- and deriving the ID of the source of truth from a hashed combination of them could be used ...
6
votes
2answers
384 views

Verifiable delay functions vs Proof of Sequential Work

I've read recent papers about verifiable delay functions (Boneh et al 2018) and proof of sequential works (Cohen et al. 2018). I understand that the core difference between the definitions is that a ...
2
votes
1answer
378 views

Bit-strength of discrete logarithm for a group of integers modulo a safe prime

Preliminaries Let $p$ be a safe prime number. Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$. We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ . Let $g \...
3
votes
1answer
63 views

Estimating difficulty of "Memory-Hard Proof-of-Work" based on "size of memory"?

In Bitcoin proof-of-work, the difficulty of Proof-of-Work is estimated and calculated based on total hashing power of the participants. If total hashing power of the participants is higher, then PoW ...
21
votes
4answers
5k views

What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

Ron Rivest posed a puzzle in 1999. MIT LCS35 Time Capsule Crypto-Puzzle. The problem is to compute $2^{2^t} \pmod n$ for specified values of $t$ and $n$. Here $n$ is the product of two large ...
1
vote
2answers
102 views

Is there confirmation blocks in Proof-of-Stake Blockchain?

When I'm reading literature about proof-of-stake blockchain, I found that it seems there is no concept about confirmation blocks (which is used to confirm a posted transaction is indeed honestly ...
2
votes
1answer
772 views

Proof of work - 51% attack

In the 51% attack on the Proof Of Work Consensus Mechanism, it's often said that you need more hashing power than the rest of the network combined. Though I can't understand why you need that much. ...
3
votes
1answer
132 views

POW with Linear time to solve it?

Any suggestions for A Proof-of-Work algorithm in literature so that the time required for solving it is linear with the puzzle difficulty ??
2
votes
1answer
75 views

Embedding POW in an EC public key

I have an application where it would be advantageous for an attacker to have to spend a long time generating public keys. To do this, I require that the hash of the public key be less than a certain ...
3
votes
2answers
440 views

Can the proof of elasped time (PoET) consensus algorithm be exploited by multiple nodes?

i recently learned about the Hyperledger Blockchain Project and the specific frameworks. In case of the Sawtooth framework, consensus is reached not by PoW but by PoET (Proof of elapsed Time). When ...
0
votes
1answer
187 views

What Proof of Work does IOTA use? [closed]

I have some trouble finding valid information about IOTA. Actually I would be nice if there would be a good source. So my question is: Bitcoin uses the SHA-256 twice and some "target bits" for ...
3
votes
2answers
181 views

Why does the prover in an interactive proof run in exponential time with the space of the computation?

I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches. In particular, I've been watching the following YouTube video which talks ...
5
votes
1answer
487 views

Time-locked Puzzles & Dead Man's Switch Intervention

I have been researching time-based puzzles. Specifically, computationally expensive algorithms for the purpose of a time-lock. This has lead me to sequential squaring, firstly, as well as some memory-...
1
vote
1answer
115 views

Hashing with (some sort of) Public and Private keys/salt/nonce

I'm trying to design a protocol where hashing can involve some public and private components. The idea is that Alice hashes a value with minimal computation and sends the hash to Bob. For Bob it ...
1
vote
0answers
106 views

Scrypt with weak parameters, for proof of work?

I need a proof of work/memory that takes about 100ms to complete, and as short time as possible to validate. Hashing random values and a nounce to get enough leading zeroes is my current approach, and ...
1
vote
2answers
95 views

Are there Guaranteed Proof-of-work Systems?

Proof-of-Work systems such as hashcash, it seems to me, do not actually prove that a certain amount of work has been performed. For example, in the case of hashcan, could not the first random hash ...
3
votes
0answers
113 views

Proof of knowledge of exponentiations

I am reading a paper of Furukawa and Sako, "An efficient scheme for proving a shuffle" from 2001. This paper writes a protocol for verifiable shuffling in mixnets. Their protocol make use of ...
1
vote
1answer
323 views

Security proof of mix net

I am writing an exercise in cryptography about anonymous communication. One of the systems I have looked into is the mix net protocol. I want to prove that this is secure. I have seen many different ...
5
votes
3answers
706 views

Anti-spamming hash-based proof-of-work?

I'm planning to implement a public mailbox for receiving feedback, and I'd like to use hash-based proof-of-work to frustrate spammers. First, we want to use 320-bit capacity Gimli permutation as the ...
5
votes
1answer
179 views

Making attacks on password hashes less economical

Perhaps an abstract question on complexity given the trade offs between memory vs runtime, I was wondering if it's possible to constrain only either extremes approaches to be optimally efficient, thus ...
2
votes
2answers
239 views

how much trust can we place in protocol verifiers?

I read many papers on authenticated key exchange protocols, and most security proofs are done by the authors. In this method, you can imagine that the efficiency is low. Moreover, even if you have ...
3
votes
2answers
259 views

Can/Which encryption algorithms be daisy chained to create a cryptographic computational puzzle?

Goal Create a computational puzzle that is fast to generate, takes an average computer minutes to solve, doesn't have any exploitable weaknesses, makes use of existing/tested encryption algorithms ...
1
vote
1answer
99 views

how to efficiently prove the query result is empty?

Consider a simplified scenario. Suppose an untrusted server holds a set of data $A=\{ a_1,a_2,\cdots,a_n\}$. A client issues a query $b$ to the server and wants to decide if $b\in A$. The server ...
1
vote
0answers
279 views

Can Bitcoin mining solve Graph Isomorphism-related problems?

Given a cryptographic hash $H:\{0,1\}^*\mapsto\{0,1\}^N$ and data $D\in\{0,1\}^*$, the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $x$ such that $H(x\Vert D)$ begins with $d$ leading zeros, ...
1
vote
0answers
150 views

Difficulty of finding partially matching ciphertexts for a given plaintext when encrypted with two different keys

I'm trying to find a simple, practical proof-of-work scheme based purely on encryption (due to wide availability of optimized, hardware accelerated AES execution on most platforms, including modern ...
8
votes
1answer
1k views

Free Start Collision In SHA-3

Given that the five sub-functions that comprise SHA-3 are reversible an individual can produce specific outputs of their choosing. The following is to my knowledge an example of a free start collision ...
3
votes
0answers
112 views

Can a stream cipher with a big S-box create ASIC-resistance?

For a proof of work system a hash algorithm generates one pseudorandom index each round, in the same manner as RC4 and Spritz do. And it uses a bigger S-box, e.g. 2^20 numbers. The actual hash would ...
6
votes
1answer
1k views

Is this simple memory-hard function good?

I'm trying to come up with a simple memory-hard function for a proof-of-work system to protect against spam. Is the one below secure? For a message M, append a random number R. Repeat until you find ...
2
votes
0answers
128 views

Why does the DBDH simulator have half the advantage of an adversary?

Literature that includes the DBDH assumption such as this paper or this paper has a formal security proof that states: Suppose an adversary with non-negligible advantage $\varepsilon = Adv$. A ...
4
votes
0answers
223 views

Complexity: Taylor series and security proofs [closed]

Taylor Series For some functions entered into Wolfram, a Taylor series expansion is represented in Big-O notation. E.g. $\sin x, x = \frac \pi4$ produces: $\frac {1} {\sqrt[]{2}} +\frac{x-\frac{\pi}...
1
vote
2answers
150 views

Stateless proof-of-work system with 0-roundtrip time

I'm designing an API. To avoid abuse, I need to rate limit the requests somehow, but I don't want to do it per user as it's very easy to create new accounts automatically. I think a proof of work ...
2
votes
0answers
55 views

Is there a proof-of-work scheme vulnerable to length extension attack?

I wonder is there an example of proof of work scheme that uses a hash function and requires the hash function to be immune to length extension attack? I mean the scheme, that becomes easy to solve if ...
1
vote
0answers
883 views

how to prove by reduction correctly?

some times when see a problem like : if some G is a PRG then G' is also a PRG. we prove this by reduction in the following way: we assume there is a Distinguisher A for G' and we construct ...
12
votes
2answers
282 views

Prove that you have $K$ bytes of memory

Alice has bought a brand new hard disk, $K$ (with $K \sim 10^{12}$) bytes in size. She is very happy about her purchase, and tells Bob about it. Bob claims he also bought a $K$ bytes hard disk. Alice ...
1
vote
0answers
101 views

Fill-and-question as a proof of space

This question follows from my previous one on proofs of space. Proof of space mechanisms rely on the computation of some proof that is easy to verify and requires from the prover an arbitrary amount ...