patternMinor
Can proofs-of-work be probabilistically checkable?
Viewed 0 times
cancheckableworkprobabilisticallyproofs
Problem
I have been lurking for a while; this is my first post here. I’m sorry if my question is ill-formed or formatted poorly. This question came out of some ideas in another question from a sister site.
Question
Because of the nature of a blockchain, a large number of publicly agreeable coin flips may be generated - namely, the hashes of previous blocks may be agreed by the network to be randomly drawn from $\{0,1\}$.
Accordingly, has anyone attempted to create a solution to the Byzantine Generals' Problem for a blockchain, where a proof-of-work is a decision problem in $NEXP$ or $PSPACE$, and the proof is checked probabilistically, using hashes of previous blocks as public coin flips?
Motivation
I’ve seen discussions online attempting to make a proof-of-work for cryptocurrencies "better," by, for example, finding witnesses to $NP$ problems.
A prover who finds a witness to an $NP$ problem may publicly announce the witness to prove that she did the work.
If there were a common, static pool of $NP$ problems, say $TSPs$ of subsets of the $n$ largest cities on Earth, then announcing the witness to secure block $i$ means that anyone can take that same witness and attach the work to another chain, which does not secure the chain.
If the verification were a zero-knowledge proof, the world (apart from the prover) may never need to know what the witness actually was.
However, as noted by others, because cryptocurrencies are trustless peer-to-peer systems, attempting to keep such a witness zero-knowledge may be difficult in a trustless peer-to-peer system.
For example, if a prover finds a solution to one of the $TSP$ problems from a static pool, and announces a $ZKP$ proof, she may still be tempted to sell her witness to fraudster if the price was right. That fraudster may attach the work to another fraudulent chain.
The witness to an $NP$ problem may not secure a blockchain, which is one of the purposes of a proof-of-work.
Similar Proposals
Converting the
Question
Because of the nature of a blockchain, a large number of publicly agreeable coin flips may be generated - namely, the hashes of previous blocks may be agreed by the network to be randomly drawn from $\{0,1\}$.
Accordingly, has anyone attempted to create a solution to the Byzantine Generals' Problem for a blockchain, where a proof-of-work is a decision problem in $NEXP$ or $PSPACE$, and the proof is checked probabilistically, using hashes of previous blocks as public coin flips?
Motivation
I’ve seen discussions online attempting to make a proof-of-work for cryptocurrencies "better," by, for example, finding witnesses to $NP$ problems.
A prover who finds a witness to an $NP$ problem may publicly announce the witness to prove that she did the work.
If there were a common, static pool of $NP$ problems, say $TSPs$ of subsets of the $n$ largest cities on Earth, then announcing the witness to secure block $i$ means that anyone can take that same witness and attach the work to another chain, which does not secure the chain.
If the verification were a zero-knowledge proof, the world (apart from the prover) may never need to know what the witness actually was.
However, as noted by others, because cryptocurrencies are trustless peer-to-peer systems, attempting to keep such a witness zero-knowledge may be difficult in a trustless peer-to-peer system.
For example, if a prover finds a solution to one of the $TSP$ problems from a static pool, and announces a $ZKP$ proof, she may still be tempted to sell her witness to fraudster if the price was right. That fraudster may attach the work to another fraudulent chain.
The witness to an $NP$ problem may not secure a blockchain, which is one of the purposes of a proof-of-work.
Similar Proposals
Converting the
Solution
I believe the answer to the question is, for all intents and purposes, "yes, this idea is being explored in [BRSV17] (link)."
For example, given two sets $S$ and $T$ of $d$-dimensional vectors with $|S|=|T|=n$, the $2$ Orthogonal Vectors $\text{(2OV)}$ problem is to find a vector $\sigma\in S$ and $\tau\in T$ such that $\langle\sigma,\tau\rangle=0$. This can be extended to a $\text{kOV}$ problem.
In [BRSV17], the authors show how to convert the $\text{2-OV}$ problem into an Merlin-Arthur protocol that can be extended to a Proof of Useful Work, and extend the problem to a $k$-round Interactive Proof.
The authors do this by converting the problem into a Sum Check protocol to determine the value of a polynomial $\text{GOV}$ over a field $\mathbb{F}$ at a random point $x\in\mathbb{F}$. The Sum Check protocol is a predecessor of the [Sha92], [BFL91] and [BFLS91] protocols.
The authors further disclose a blockchain including the Proof of Useful Work, wherein posers add $\text{kOV}$ problems to a common pool, and miners follow the Fiat-Shamir heuristic to construct a transcript of the interactive proof. Miners determine the random point $x$ by salting the hash of the previous block with the coefficients of the Sum Check protocol.
The authors go on to describe that the $\text{kOV}$ problem is related to the $\text{APSP}$ problem and the $\text{3SUM}$ problem.
I suspect this work may be a spring-board to other ideas?
Reference
[BRSV17] M. Ball, A. Rosen, M. Sabin, and P. N. Vasedevan. Proofs of Useful Work. 2017
P.S. I'm not sure if my LaTeX is right for KOV, APSP, 3SUM etc.
For example, given two sets $S$ and $T$ of $d$-dimensional vectors with $|S|=|T|=n$, the $2$ Orthogonal Vectors $\text{(2OV)}$ problem is to find a vector $\sigma\in S$ and $\tau\in T$ such that $\langle\sigma,\tau\rangle=0$. This can be extended to a $\text{kOV}$ problem.
In [BRSV17], the authors show how to convert the $\text{2-OV}$ problem into an Merlin-Arthur protocol that can be extended to a Proof of Useful Work, and extend the problem to a $k$-round Interactive Proof.
The authors do this by converting the problem into a Sum Check protocol to determine the value of a polynomial $\text{GOV}$ over a field $\mathbb{F}$ at a random point $x\in\mathbb{F}$. The Sum Check protocol is a predecessor of the [Sha92], [BFL91] and [BFLS91] protocols.
The authors further disclose a blockchain including the Proof of Useful Work, wherein posers add $\text{kOV}$ problems to a common pool, and miners follow the Fiat-Shamir heuristic to construct a transcript of the interactive proof. Miners determine the random point $x$ by salting the hash of the previous block with the coefficients of the Sum Check protocol.
The authors go on to describe that the $\text{kOV}$ problem is related to the $\text{APSP}$ problem and the $\text{3SUM}$ problem.
I suspect this work may be a spring-board to other ideas?
Reference
[BRSV17] M. Ball, A. Rosen, M. Sabin, and P. N. Vasedevan. Proofs of Useful Work. 2017
P.S. I'm not sure if my LaTeX is right for KOV, APSP, 3SUM etc.
Context
StackExchange Computer Science Q#76833, answer score: 2
Revisions (0)
No revisions yet.