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.
I haven't looked into it, but it's all linear algebra, so I have a
wild hunch some matrix magic should do the trick.
I apologize if I'm working off a misunderstanding in one or more
areas, please correct me if I'm wrong here.
> >3) Would there be any problems in allowing people to solve a problem
> > defined in advance, rather than having it vary based on the current
> > block?
>
> Yes. The amount of computing power that people have thrown at bitcoin
> mining has increased by orders of magnitude since bitcoins were
> invented, and varying the problems keeps the mining rate roughly
> constant. If you had problems of fixed difficulty, either they'd be
> too hard and mining would creak to a halt, or they'd be too easy and
> the price would crash from the flood of new bitcoin blocks, at least
> until they hit the fixed total block limit.
I mean, what if you knew the problem to solve for block 2 before block
1 was solved.
Further, what if the problems varied in difficulty but generally got
more difficult over time (as the set size of the NPC problem increased
through exhaustion of the smaller space).
> >4) Would it be useful to decouple any of the aspects of the block chain
> > from each other? Could one decouple the financial impacts from the
> > cryptographic operations from the persistent, distributed storage?
>
> There are certainly blockchains whose entries are things other than
> sort-of-money, and there's plenty of electronic money that doesn't
> use blockchains. So this question doesn't make a lot of sense.
>
> >6) Could we create markets around the various services required to
> > implement the block chain in a way that creates incentives that
> > align with the overall goals?
I mean:
1) Mining - market is obvious and already exists
2) Block chain storage
3) Block chain retrieval (for problem domains other than money)
i.e. Query blockchain for your particular NPC problem solution.
4) Submission of problems for POW (perhaps)
...given that the goal is to have this giant compute cluster solving
inherently useful problems (diamond-water paradox?) either prescribed
(solve SAT problems of increasing cardinality) or delivered to the
cluster via paid submission (i.e. generalized SETI@HOME).
--
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
