Skip to main content

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
0 votes
1 answer
49 views

Is discrete logarithm good approach for a time-bounded proof of work?

I'm writing a system where a client needs to show via proof of work that it's really intending to consume CPU resources on the server, and not just bombing the server with denial of service queries. ...
juhist's user avatar
  • 1,383
1 vote
0 answers
47 views

Are saltless PoW's ok?

So, I'm building a system loosely based on the S/Kademlia principles and I have a question. I generate IDs from hashing a public key such that $ID = H(PK)$. Further, I say that for an ID to be valid ...
Lullen's user avatar
  • 11
1 vote
1 answer
44 views

A doubt on Proofs-of-Sequential-Work protocols

Proofs-of-Sequential-Work ($\mathsf{PoSW}$) are cryptographic protocols that engage two parties, a prover with $\mathtt{poly}(N)$-parallel processors and a deterministic verifier such that the ...
Somudro Gupto's user avatar
0 votes
0 answers
20 views

Reduction For MAC systems

I am not too knowledgeable regarding reductions for message authentication code encryption. Here is an example I found: There is a MAC' based on a preliminary existing MAC as such: MAC'(k, m) = MAC(k,...
sangaCat's user avatar
0 votes
1 answer
41 views

Proof of work for large amount of data

I'm new to cryptography, sorry if this question is dumb. I've just read the paper of Dwork and Naor Pricing via Processing or Combatting Junk Mail and understand the example of squaring on $\mathbb{Z}/...
Ta Thanh Dinh's user avatar
3 votes
1 answer
198 views

Fischlin vs. Fiat-Shamir Performance

Using Fiat-Shamir, an interactive 3-round sigma protocol can be compiled into a non-interactive zero-knowledge proof in the random oracle model. A NIZK through Fiat-Shamir is not UC-Secure due to ...
Atonal's user avatar
  • 155
0 votes
0 answers
40 views

The specific nature of a 51% attack - in relation to a multiple choice question that I was marked as incorrect on

In a course I'm taking the following question came up: ...
phoenixestant's user avatar
0 votes
1 answer
68 views

Why can't crypto currencies have every node verify blocks independently instead of proof of work/stake?

For verifying transactions, normally nodes do proof of work and agree with the majority of workers, but why can't they just do the computation themselves and agree with any other node that has the ...
Alex Breeze's user avatar
1 vote
1 answer
873 views

Why is $\operatorname{Hash}(x \oplus y)$ not a secure proof-of-work algorithm?

$x$ is challenging string, $y$ is proof string. $\operatorname{H}$ is the proof-of-work (pow) function, to find a $y$ such that $H(x,y)<2^{256}/D$ $x ,y = \{ 0, 1 \}^{512}$ $\operatorname{H}(x,y) =...
user2383960's user avatar
0 votes
0 answers
60 views

How can we construct stationary and non-stationary time locks?

Time locks enables us to encrypt data for a period of time, up to a certain deadline, such that even a computationally powerful adversary is not able to learn any substantial information about the ...
Gokul Alex's user avatar
1 vote
1 answer
68 views

Are RSA keypairs proof of work?

My computer generates a 65536-bit RSA keypair in 106 minutes. Is there a way to generate them faster by some trade-off? Can they be created in bulk, so long as they're able to encrypt and decrypt? Is ...
Brent's user avatar
  • 111
0 votes
2 answers
336 views

I need an encryption algorithm that doesn't require keys and computationally easy to encrypt, hard to decrypt

I need an encryption algorithm that doesn't require keys and computationally easy to encrypt, hard to decrypt. Decrypting can involve brute force. If the algorithm can be applied again and again (...
Aerbil's user avatar
  • 3
1 vote
1 answer
74 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 ...
Van Altercolt's user avatar
2 votes
0 answers
50 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 ...
Van Altercolt's user avatar
1 vote
1 answer
424 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 ...
Ukneshi's user avatar
  • 11
1 vote
1 answer
143 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 ...
David Jonsson's user avatar
1 vote
1 answer
246 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$) ...
user491880's user avatar
1 vote
1 answer
616 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 ...
Aurell1an's user avatar
9 votes
1 answer
3k 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 ...
user6916458's user avatar
1 vote
1 answer
123 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 ...
hola's user avatar
  • 603
1 vote
2 answers
202 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 ...
Njord's user avatar
  • 11
4 votes
1 answer
200 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. ...
josh's user avatar
  • 41
4 votes
2 answers
214 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 ...
SpaceMonkey's user avatar
4 votes
2 answers
226 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 ...
yellowlive's user avatar
0 votes
1 answer
62 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$ ...
Ameer Jewdaki's user avatar
3 votes
3 answers
208 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 ...
Adam Ierymenko's user avatar
4 votes
1 answer
1k 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 ...
Questioner's user avatar
0 votes
0 answers
26 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 ...
sof's user avatar
  • 61
1 vote
1 answer
210 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 ...
Biology nerd's user avatar
1 vote
0 answers
41 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 ...
H. L. Seger's user avatar
0 votes
0 answers
20 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 ...
johnsmiththelird's user avatar
7 votes
2 answers
607 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 ...
Bartolinio's user avatar
2 votes
1 answer
802 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 \...
RalphS's user avatar
  • 153
3 votes
1 answer
82 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 ...
Questioner's user avatar
2 votes
2 answers
175 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 ...
CryptoLover's user avatar
2 votes
1 answer
839 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. ...
Benjamin Larsen's user avatar
2 votes
1 answer
99 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 ...
Erik Aronesty's user avatar
0 votes
1 answer
208 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 ...
garondal's user avatar
  • 101
1 vote
1 answer
208 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 ...
zetaprime's user avatar
  • 591
3 votes
1 answer
151 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 ??
David Nicola's user avatar
1 vote
0 answers
143 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 ...
Drathier's user avatar
  • 1,043
5 votes
2 answers
473 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 ...
Matthias Danetzky's user avatar
3 votes
0 answers
120 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 ...
Meghann Jones's user avatar
1 vote
2 answers
112 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 ...
jkj yuio's user avatar
  • 129
5 votes
1 answer
227 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 ...
ruffsl's user avatar
  • 201
5 votes
1 answer
572 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-...
xendi's user avatar
  • 151
3 votes
2 answers
473 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 ...
pekayde's user avatar
  • 31
3 votes
2 answers
232 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 ...
kw3rti's user avatar
  • 131
5 votes
3 answers
869 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 ...
DannyNiu's user avatar
  • 9,519
3 votes
2 answers
400 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 ...
Conathan Rypt's user avatar