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,
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
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 chains?
Who are the thought leaders that I should bring in to talk about it?
What are the major fora?
What properties should a new BTC-like system provide?
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
