On Sun, Jan 17, 2016 at 11:49:20PM -0800,
travis+ml-rbcryptogra...@subspacefield.org wrote:
> On Sun, Jan 17, 2016 at 08:31:44PM -0000, John Levine wrote:
> > >1) Can we use SAT (or another NPC problem) as a POW?
> >
> > Meybe. Remember that a POW has to be hard to compute but easy
> > to verify and each instance should be roughly the same difficulty.
> > My impression is that some SAT problems are a lot harder than others,
> > and you can't tell in advance which is which.
>
> IIUC, making sure the first N bits of a hash are zero, is basically
> the SAT problem (make these equations equal one), with random
> equations/functions ("random oracle model" of ideal hashes).
>
> A SAT solution would provide input variables that made all the
> equations 1 (or equivalently, zero) and should probably be much
> more efficient than computing a hash, although perhaps the general
> solution is not as efficient as the specific form solution defined
> by a given hash.
On the solution side, you could take the ordinal number in this set
size, and use it to generate the coefficients in the maximal
conjunctive normal form; for each input variable apearance, it might
be (+) present, (-) inverted, or (0) absent from that spot.
Assuming the maximal conjunctive normal form is:
y_n = (c_n1 x1 v c_n2 x2) ^ (c_n3 x1 v c_n4 x2)
Then for c_1 = { 1 -1 0 1 }
y1 = (x1 v -x2) ^ (x2)
Actually, that's not fully general, as it fails to give enough
opporunities for variables and their negations to play in every
possible way; it would, for example, make it impossible to
represent y = (x1) ^ (-x1 v -x2) ^ (x2) ^ (-x1 v x2)
I'm pretty sure there's some fancy work you could do to get this all
straightened out and make it such that a certain size bitstring
enumerates all possible NPC SAT problems in a certain number of
variables, possibly by treating a variable and its negation as two
input variables, for the purposes of generating equations, and
supressing them with zero coefficients.
In this case, the block chain simply iterates that bitstring
(representing vector c), lets people submit a solution, and then
iterates again, until it rolls over.
The brute force miners could continue to iterate solutions the way
they still have; by trying all possible input bits drawn by random
selection - and see if the equations evaluate to true. Anyone who
wants to check their work, takes their vector for x and plugs them in
with vector c to evaluate y. If y comes up all 1s, it's legit.
These guys set the ceiling of how much work it should take.
The SAT solving miners, might see some pattern in c that allows them
to compute the answer quicker. Bully for them.
Other miners might use humans a la the Verigames game Paradox:
http://paradox.centerforgamescience.org/paradox/Paradox.html
--
http://www.subspacefield.org/~travis/ | if spammer then j...@subspacefield.org
"Computer crime, the glamor crime of the 1970s, will become in the
1980s one of the greatest sources of preventable business loss."
John M. Carroll, "Computer Security", first edition cover flap, 1977
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
