Re: [cryptography] a new blockchain POW proposal

[ianG]

On 17/01/2016 10:13 am, travis+ml-rbcryptogra...@subspacefield.org wrote:

I'm embarrassed by the long, rambling post. It was notes to myself,
which I then circulated to my friends and forwarded without editing.
I should summarize.

0) Bitcoin is amazing technology.  Truly neat.  Many related ideas,
must have taken a long time to develop.  Impressive.  Caught
me way off guard back when it was posted here.
1) Can we use SAT (or another NPC problem) as a POW?
If I'm not mistaken doing hash preimage attacks is a SAT solver.
2) Can we efficiently enumerate the aforementioned NPC problem space
and map to and from ordinals?
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?


Not in the current design because each block refers by hash to the 
previous.  Also, the design of the lottery is based on surprise to try 
and get everyone starting at the same position.



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?



It turns out that Bitcoin is incredibly well balanced in its 
interlocking assumptions.  Although it looks like a grabbag of tricks, 
it is actually carefully interconnected.


The key assumption(s) is that all are equivalently anonymous.  Therefore 
anyone can pretend to be as many as one likes.  Hence the vote on 
control is required to isolate over some unforgeable differentiating 
thing, which ends up being energy (PoW) in Bitcoin's case (proof of 
stake is also popular).


Energy costs money so it has to be paid for somehow, so we need the 
money creation to empower the mining, and we need to provide a payment 
system so as to encourate people to demand the money to incentivise the 
miners to produce otherwise worthless leading-zero hash numbers.


If you drop the "equivalently anonymous" assumption then every other 
aspect collapses.  Hence the anti-school of "private or permissioned 
blockchains," oxymoron.




5) Would it be useful to create hash lattices rather than a single
chain for some purposes?  What other structures might be useful?


So back off a bit and ask what you are trying to achieve?  Tinkering at 
the edges is fun, but pointless.


There's some thinking about sharding the blockchain because that's the 
only way to go massively scaled to say IoT levels.  Also a lot of 
thinking as to what happens when you relax the anonymity condition.




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? In other words, can the design
be a game-creating-game which serves a higher goal.  The
work product of mining can be polished and resold in jewelry,
perhaps in other markets.  This could pay for running the chain
storage.



One of the problems in markets is that it is terrifically hard to get 
specialisations up and going by planning, because you need to coordinate 
multiple groups at the same time.  In this sense, bitcoin started out as 
"everyone was a node" and then it bifurcated to miners and payments 
nodes and then again to full nodes and SPV nodes.  Evolution worked, but 
if you planned it to bootstrap like that you'd likely fail because of 
chicken & egg mechanics.




7) Can that goal include more efficient software and hardware?
Mine for great good.


The doctrinal argument is that if there is another purpose to the 
mining, then the security is weakened because it comes for less money. 
This goes back to Gresham's observation that money with multiple 
purposes has strange artifacts.  Popularly "bad money beats out the 
good" although that is only a popular saying, it's different in the 
analysis.  So in the bitcoin world of today there are multiple issues 
going on with the money source - i.e. the power costs vary which causes 
those artifacts to kick in and impact back into the ecosystem.


So ideally we would look for a more perfect distribution of the lottery, 
which would hopefully replace the PoW.  E.g., instead of using PoW to 
designate the winner, use the hash of the last block to appoint the 
decider of the next block.  If you can get the hash to be truly 
unpredictable (e.g., I can't frontrun myself by pre-predicting myself as 
the winner) then a more perfectly distributed lottery would remove the 
need for energy burning at all.




8) Other than this list, where else might I find influential
people who know more than I about this stuff, to pick their
brain?  I am in SF/BA, IRL, if that matters.


There are meetups in that area.


9) I'm sure there are problems with this idea.  If you would kindly
correct my inadequate understanding I would much appreciate.

On Sun, Jan 17, 2016 at 01:21:38AM -0800, 

Re: [cryptography] a new blockchain POW proposal

[James A. Donald]

On 2016-01-24 1:11 PM, ianG wrote:

There's some thinking about sharding the blockchain because that's the
only way to go massively scaled to say IoT levels.  Also a lot of
thinking as to what happens when you relax the anonymity condition.


Need to shard the blockchain if we are going to replace the US dollar, 
if everyone in the world starts using a cryptocurrency to buy eggs and milk.


Need to go proof of stake as it has become apparent that the interests 
of miners are not perfectly aligned with the interests of the bitcoin 
business community.


Unfortunately, these things are easier said than done.  Hard to figure 
out how to shard the blockchain and still efficiently solve the 
Byzantine Generals problem every few minutes.  I have been puzzling at 
this for some time.  Seems as if it should be doable, and indeed it is 
easy to find a seeming solution 
http://blog.sldx.com/three-challenges-for-scaling-bitcoin/, but it 
always turns out that the seeming solution makes it possible for someone 
to profit from bad behavior.  It is hard to shard the blockchain while 
having incentives aligned in every shard. To shard the blockchain we 
need global alignment of incentives with merely local knowledge.


Simple proof of stake solutions turn out to require considerably more 
work than the current proof of work solution.


I still think this is doable, but it is tricky.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] a new blockchain POW proposal

[travis+ml-rbcryptography]

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 -, 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

Re: [cryptography] a new blockchain POW proposal

[Tony Arcieri]

On Sun, Jan 17, 2016 at 2:13 AM,  wrote:

> 4) Would it be useful to decouple any of the aspects of the block
> chain from each other?


Right now Bitcoin's transaction throughput is inherently capped by the
combination of how many transactions fit in a block and how frequently new
blocks are published (hence the "Bitcoin XT" debacle).

The proof-of-work function provides what's effectively a Sybilproof leader
election system. I thought a clever idea was to decouple leader election
from authenticating transactions:

http://arxiv.org/abs/1510.02037

(This specific approach has flaws, but I'd like to see the general idea
better explored)

-- 
Tony Arcieri
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] a new blockchain POW proposal

[travis+ml-rbcryptography]

On Sun, Jan 17, 2016 at 08:31:44PM -, 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

Re: [cryptography] a new blockchain POW proposal

[John Levine]

>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.

>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.

>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? 

Depends what you think the goals are.  The current process meltdown is
an argument between people who want to make what they see as a simple
and overdue change to increase the number of transactions, and people
who for various reasons ranging from algorithmic purity to protecting
the transaction fees their racks of mining hardware is collecting.

R's,
John

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] a new blockchain POW proposal

[travis+ml-rbcryptography]

So I'm sure I'm not the first person to muse on the mining POW problem
and its lack of social value apart from being hard.  Let me lay out a
few links I've been reading in my "copious" free time and risk
sounding naive by musing a bit.  Hopefully those of you with more
knowledge can correct me and/or send me to even better references.

I'm sure those of you in the know have heard this polemic:
http://motherboard.vice.com/read/bitcoin-is-unsustainable
https://www.reddit.com/r/Bitcoin/comments/41b4zx/whiny_ragequitting/cz139ti

I'm not trying to inflame opinions on the matter, it seems they
already have been and I'm not trying to throw fuel on the fire,
and I really don't know enough about the technical details to
know why a block size matters all that much, but I am somewhat
astonished at 7 tps as an upper bound.

What I do believe is that brute forcing partial hash preimages has
virtually no useful benefit.  The fact that we have the world's
largest computing cluster solving a useless problem sounds like
something out of a Douglas Adams novel.

If we were enumerating solutions to NPC problem then the block chain
would be useful for any isomorphic NP problems, and any optimizations
would apply to all NP problems.

From what I hear, it's just local hydro, the power is basically free,
and it's currently controlled by two guys from China (a handful of
people control 95% of the mining power, IIRC). But it could be solving
useful problems. For example one day gcc could query the block chain
for register allocation solutions.

Leaving aside the technical details, waving hands at the
implementation, imagining that it exists, the first things you
brute-force optimize should, be:

1) the mining software and/or FPGA layouts, so you acquire more
   NP-complete problem solutions, faster
2) the compiler binary
3) mobile device software
4) Unix kernels

Via this method, you'd be doing computational geoarbitrage, by
precomputing solutions where energy is essentially free, memoizing
them, and creating some as-yet-undefined incentive to provide them to
other problem domains as an essentially free byproduct, and reaping
the work product n times over.

By making e.g. electric space heaters which do the work, you've also
created a sort of interesting incentive to participate in situations
where none would have existed.

IIUC, many/most compiler optimizations are NP hard problems. I would
imagine many EDA problems are, as well.

Another possibility is to create a market where people who want hard
problems solved place paid requests for solutions to search systems,
and the search systems fulfill or submit to miners pools to solve
them. That would allow for cases where the size of the specific
problem people need solved exceeds the "brute force enumeration"
system's size, and could allow for, I don't know, doing protein
folding or computational biology problems or something with tangible
existential value to the human race. If the problem isn't easily
represented as a NP complete problem, perhaps it could involve some
virtual machine language. Not really sure about the most practical
general form. And of course all the payments would be done with the
very same system for which we are implementing proof of work.

Actually we are probably solving SAT problems based on the linear
boolean equations based on whatever hash Bitcoin uses, we are just
solving them in an arbitrary order, and for an arbitrary set size (n
bit null prefix sha1 problem = solving n simultaneous random linear
equations in 160 variables?). I wonder if when viewed this way the
blockchain would be of any value for anything else.

I do have to say, the block chain (merkle tree) looks a lot like this
1998 proposal, and I direct you to the section on hash lattices, which
seem in some ways superior:

https://www.schneier.com/cryptography/archives/1998/01/cryptographic_suppor.html

I wonder if there is a case for decoupling the market for making an
entry in a global database, and the mining process itself, such that
electronic payments could be made to "commit" data to the chain, which
is widely replicated (Wait, is this USENET 2.0? No, that was cloud
storage.  This is USENET 3.0.  Or maybe this is PGP timestamping
services v2.0)

I'm still reading these:
https://en.wikipedia.org/wiki/Block_chain_(database)
https://en.wikipedia.org/wiki/Billon_standard
https://tools.ietf.org/html/draft-hallambaker-cryptomesh-00
https://tonyarcieri.com/on-the-dangers-of-a-blockchain-monoculture

Also, it appears the proud father of 20-year-old ECC says it is not
worth saving:
http://arstechnica.com/security/2015/10/nsa-advisory-sparks-concern-of-secret-advance-ushering-in-cryptoapocalypse/
https://www.reddit.com/r/crypto/comments/3qp4ta/a_riddle_wrapped_in_an_enigma_neal_koblitz_alfred/
So we'll have to consider some flexibilty in the PKC we use.
I suppose it might involve merkle signatures:
https://en.wikipedia.org/wiki/Merkle_signature_scheme

What else should I read about block 

Re: [cryptography] a new blockchain POW proposal

[travis+ml-rbcryptography]

I'm embarrassed by the long, rambling post. It was notes to myself,
which I then circulated to my friends and forwarded without editing.
I should summarize.

0) Bitcoin is amazing technology.  Truly neat.  Many related ideas,
   must have taken a long time to develop.  Impressive.  Caught
   me way off guard back when it was posted here.
1) Can we use SAT (or another NPC problem) as a POW?
   If I'm not mistaken doing hash preimage attacks is a SAT solver.
2) Can we efficiently enumerate the aforementioned NPC problem space
   and map to and from ordinals?
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?
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?
5) Would it be useful to create hash lattices rather than a single
   chain for some purposes?  What other structures might be useful?
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? In other words, can the design
   be a game-creating-game which serves a higher goal.  The
   work product of mining can be polished and resold in jewelry,
   perhaps in other markets.  This could pay for running the chain
   storage.
7) Can that goal include more efficient software and hardware?
   Mine for great good.
8) Other than this list, where else might I find influential
   people who know more than I about this stuff, to pick their
   brain?  I am in SF/BA, IRL, if that matters.
9) I'm sure there are problems with this idea.  If you would kindly
   correct my inadequate understanding I would much appreciate.

On Sun, Jan 17, 2016 at 01:21:38AM -0800, 
travis+ml-rbcryptogra...@subspacefield.org wrote:
> So I'm sure I'm not the first person to muse on the mining POW problem
> and its lack of social value apart from being hard.  Let me lay out a
> few links I've been reading in my "copious" free time and risk
> sounding naive by musing a bit.  Hopefully those of you with more
> knowledge can correct me and/or send me to even better references.
> 
> I'm sure those of you in the know have heard this polemic:
> http://motherboard.vice.com/read/bitcoin-is-unsustainable
> https://www.reddit.com/r/Bitcoin/comments/41b4zx/whiny_ragequitting/cz139ti
> 
> I'm not trying to inflame opinions on the matter, it seems they
> already have been and I'm not trying to throw fuel on the fire,
> and I really don't know enough about the technical details to
> know why a block size matters all that much, but I am somewhat
> astonished at 7 tps as an upper bound.
> 
> What I do believe is that brute forcing partial hash preimages has
> virtually no useful benefit.  The fact that we have the world's
> largest computing cluster solving a useless problem sounds like
> something out of a Douglas Adams novel.
> 
> If we were enumerating solutions to NPC problem then the block chain
> would be useful for any isomorphic NP problems, and any optimizations
> would apply to all NP problems.
> 
> From what I hear, it's just local hydro, the power is basically free,
> and it's currently controlled by two guys from China (a handful of
> people control 95% of the mining power, IIRC). But it could be solving
> useful problems. For example one day gcc could query the block chain
> for register allocation solutions.
> 
> Leaving aside the technical details, waving hands at the
> implementation, imagining that it exists, the first things you
> brute-force optimize should, be:
> 
> 1) the mining software and/or FPGA layouts, so you acquire more
>NP-complete problem solutions, faster
> 2) the compiler binary
> 3) mobile device software
> 4) Unix kernels
> 
> Via this method, you'd be doing computational geoarbitrage, by
> precomputing solutions where energy is essentially free, memoizing
> them, and creating some as-yet-undefined incentive to provide them to
> other problem domains as an essentially free byproduct, and reaping
> the work product n times over.
> 
> By making e.g. electric space heaters which do the work, you've also
> created a sort of interesting incentive to participate in situations
> where none would have existed.
> 
> IIUC, many/most compiler optimizations are NP hard problems. I would
> imagine many EDA problems are, as well.
> 
> Another possibility is to create a market where people who want hard
> problems solved place paid requests for solutions to search systems,
> and the search systems fulfill or submit to miners pools to solve
> them. That would allow for cases where the size of the specific
> problem people need solved exceeds the "brute force enumeration"
> system's size, and could allow for, I don't know, doing protein
> folding or computational biology problems or something with tangible
>