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.
89
questions
2
votes
0
answers
58
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 ...
- 143
0
votes
0
answers
36
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:
...
0
votes
1
answer
63
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 ...
- 41
1
vote
1
answer
797
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) =...
- 13
0
votes
0
answers
52
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 ...
- 343
1
vote
1
answer
62
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 ...
- 111
0
votes
2
answers
214
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 (...
- 3
1
vote
1
answer
57
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 ...
2
votes
0
answers
43
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 ...
1
vote
1
answer
244
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
...
- 11
1
vote
1
answer
122
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 ...
- 123
1
vote
1
answer
196
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$) ...
- 123
1
vote
1
answer
460
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 ...
- 11
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 ...
- 193
1
vote
1
answer
115
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 ...
- 603
1
vote
2
answers
190
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 ...
- 11
4
votes
1
answer
176
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. ...
- 41
4
votes
2
answers
208
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 ...
- 141
4
votes
2
answers
218
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 ...
- 53
0
votes
1
answer
60
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$ ...
- 101
3
votes
3
answers
184
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 ...
- 896
4
votes
1
answer
866
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 ...
- 211
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 ...
- 61
1
vote
1
answer
193
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 ...
- 153
1
vote
0
answers
40
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 ...
- 11
0
votes
0
answers
19
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 ...
- 211
7
votes
2
answers
552
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 ...
- 247
2
votes
1
answer
674
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 \...
- 153
3
votes
1
answer
78
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 ...
- 211
2
votes
2
answers
158
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 ...
- 922
2
votes
1
answer
826
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.
...
- 163
2
votes
1
answer
93
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 ...
- 420
0
votes
1
answer
201
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 ...
- 101
1
vote
1
answer
178
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 ...
- 591
3
votes
1
answer
150
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 ??
- 31
1
vote
0
answers
125
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 ...
- 993
5
votes
2
answers
458
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 ...
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 ...
1
vote
2
answers
111
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 ...
- 129
5
votes
1
answer
220
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 ...
- 201
5
votes
1
answer
532
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-...
- 151
3
votes
2
answers
468
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 ...
- 31
3
votes
2
answers
219
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 ...
- 131
5
votes
3
answers
827
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 ...
- 8,648
3
votes
2
answers
366
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
1
answer
107
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 ...
- 467
1
vote
1
answer
406
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 ...
1
vote
0
answers
314
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, ...
- 155
1
vote
0
answers
182
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 ...
- 53
3
votes
0
answers
114
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 ...
- 31