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
1 vote
1 answer
43 views

is Client Puzzle a challenge-response variant of Proof-of-work?

is Client Puzzle a challenge-response variant of Proof-of-work? I am kind of new to crypto, sorry if the question is kind of dumb. If it's not can you give examples of algorithms that implement the ...
user avatar
2 votes
0 answers
29 views

What is the difference between Solution-Verification and Challenge-Response variants of Proof of Work;

Sorry if question is really dumb, I am new to crypto :( If the client provides the solution for the PoW Challenge-Response, in my understanding, the solution of that challenge should be verified. So I ...
user avatar
1 vote
1 answer
88 views

P256 seed problem

I'm reading up on elliptic curves and their history and it seems that people don't trust P256 seed which is defined in FIPS 186-3 on page 89 to be SEED = c49d3608 86e70493 6a6678e1 139d26b7 819f7e90 ...
user avatar
  • 11
1 vote
1 answer
54 views

Do proof of work hash function arguments have anything in common?

Some proof of work hashes have a lot of initial zeros. Do the arguments to the hash functions giving these zero containing hashes have anything in common, or are they stochastic? What I am looking ...
user avatar
1 vote
1 answer
71 views

Is this simple Proof of Work algorithm based on SHA256 susceptible to length extension attack?

Each block's contents are hashed into 32 bytes using $\operatorname{SHA-256}$ (call this string $a$). In order for the block to be accepted, there must be a 256bit nonce (call this string $b$) ...
user avatar
1 vote
1 answer
180 views

Two-way encryption algorithms similar to bcrypt

I'm in need of an algorithm that can perform a very specific task: take a short string, encrypt it using an algorithm which can be scaled to keep up with Moore's Law/has a proof-of-work factor/is ...
user avatar
10 votes
1 answer
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 ...
user avatar
1 vote
1 answer
102 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 ...
user avatar
  • 593
1 vote
2 answers
180 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 ...
user avatar
  • 11
3 votes
0 answers
117 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. ...
user avatar
  • 31
4 votes
2 answers
157 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 ...
user avatar
4 votes
2 answers
170 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 ...
user avatar
0 votes
1 answer
52 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$ ...
user avatar
3 votes
3 answers
153 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 ...
user avatar
4 votes
1 answer
502 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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 61
1 vote
1 answer
149 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 ...
user avatar
1 vote
0 answers
35 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 ...
user avatar
0 votes
0 answers
17 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 ...
user avatar
6 votes
2 answers
456 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 ...
user avatar
2 votes
1 answer
485 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 \...
user avatar
  • 153
3 votes
1 answer
73 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 ...
user avatar
2 votes
2 answers
126 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 ...
user avatar
2 votes
1 answer
804 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. ...
user avatar
2 votes
1 answer
76 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 ...
user avatar
0 votes
1 answer
196 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 ...
user avatar
  • 101
1 vote
1 answer
139 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 ...
user avatar
  • 581
3 votes
1 answer
140 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 ??
user avatar
1 vote
0 answers
114 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 ...
user avatar
5 votes
2 answers
427 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 ...
user avatar
3 votes
0 answers
114 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 ...
user avatar
1 vote
2 answers
106 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 ...
user avatar
  • 129
5 votes
1 answer
207 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 ...
user avatar
  • 201
5 votes
1 answer
496 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-...
user avatar
  • 151
3 votes
2 answers
458 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 ...
user avatar
  • 31
3 votes
2 answers
200 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 ...
user avatar
  • 131
5 votes
3 answers
751 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 ...
user avatar
  • 6,621
3 votes
2 answers
308 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 ...
user avatar
1 vote
1 answer
104 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 ...
user avatar
  • 457
1 vote
1 answer
358 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 ...
user avatar
1 vote
0 answers
295 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, ...
user avatar
  • 111
1 vote
0 answers
158 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 ...
user avatar
3 votes
0 answers
113 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 ...
user avatar
8 votes
1 answer
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 ...
user avatar
  • 1
6 votes
1 answer
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 ...
user avatar
2 votes
0 answers
132 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 ...
user avatar
  • 21
4 votes
0 answers
248 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}...
user avatar
  • 214
2 votes
0 answers
56 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 ...
user avatar
  • 636
1 vote
0 answers
1k 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 ...
user avatar
  • 353
1 vote
0 answers
105 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 ...
user avatar
  • 1,341