Relaunched Completely

[Dazza]

Is there any consideration for protection against quantum computation? If not I suggest there should be it may not be too long from now.

Lionel's original white paper had another vulnerability which I haven't discussed in this thread because it was only theoretical - the computational resources needed to exploit it would have been enormous.  A quantum computer might possibly have bust it wide open.  The vulnerability is easier to fix than it is to explain.

The rule of thumb I use is that QC effectively halves the sizes of the crypto primitives you're using, so SHA-256 will be as strong as a 128-bit hash is now, which should be good for a long time, if not forever.  RIPEMD-160, used to turn ECDSA public keys into bitcoin addresses, looks very vulnerable.  I don't honestly know whether the ECDSA keys are big enough to resist QC.  I do know that only last year the NSA recommended moving away from elliptic curve cryptosystems which include ECDSA, or at least not migrating to them, in anticipation of QC.  Make of that what you will, this is the NSA, after all.

IMO it is a good design decision to make the keys compatible with bitcoin.  There will be plenty of time for us, and for bitcoin to move to something better later.  Moreover, there is not yet a consensus among crypto experts as to what "something better" might be.

Edited to add:  I notice EK has posted a contrary opinion.  I cannot vouch for his expertise in this field.  I can only vouch for my own lack thereof.

[Dazza]

Well, given QC is possible, you could use Shor's Algorithm (https://en.wikipedia.org/wiki/Shor%27s_algorithm) to solve the discrete logarithm problem in polynomial time.

DL is not believed to be NP-complete to my knowledge.  It is no harder than integer factorisation, for which a sub-exponential non-quantum algorithm exists.  However some NP problems (and therefore all NP-complete problems) are believed to require exponential time.

It's been a long time since I studied this, and I can't recall if NP-complete problems were proven to require exponential time (assuming P/=NP), rather than being merely assumed to do so.  If proved, then it follows that DL is provably not NP-complete.  However if it was merely a belief, then beliefs can change.

Or perhaps I'm remembering it wrong, and all that was ever said was that the only known algorithms for known NP-complete problems were exponential.  It really is a long time ago that I took that class.

[Dazza]

Honestly, I don't remember it either. For me its also around 10 years ago  
But yes, I recall that integer factorization is assumed not to be NP-complete. There is no proof, but it's generally thought to be the case.

It's closer to 30 years for me.

NFS is conjectured to be subexponential based upon a heuristic argument.  There is no proof, or if there is, it was discovered within the last couple of years, or I would certainly have heard about it, given the company I kept about that time.

The only thing I can say for certain is that DL is provably no harder than factorisation, because RSA is DL and, as everybody here surely knows, factorisation breaks RSA.

None of this is particularly relevant to matters at hand.  Nor is our different understanding of the effect of QC.

[Dazza]

Well, the verification in this scheme is a bigger problem than the confirmation (under confirmation I understand the mining of a block).

By "confirmation", I meant verification.

Imagine you have an algorithm that runs for 4 hours. Every 10 ms there is a feedback, but the block (for some reason) is mined 3 hours into the calculation.
So how should the other users (which are not miners) verify that this block is correct? They would have to perform a 3 hour calculation themselves.

Under my scheme, they would have to do a 10ms calculation.

I'm being intentionally cagey about exactly how my scheme works for two reasons.  Firstly, if you're going to use my ideas, or even if you don't, but they stimulate ideas of your own which you do use, and if the result is a hugely successful altcoin, which I think is a possibility, and if you, Lionel, or other people end up rich (or richer, in your case) because of it, then I would like to end up rich too. And right now I'm not seeing a clear path for myself to those riches. Your offer to remit to me a few BTC was kind, but it was conditioned upon you being paid yourself, which isn't certain. I could put those BTC into the public offer, or maybe scrape together the cash to buy a few BTC of my own, but I won't invest until there's a clear plan that I can believe in.  Even then, I'd consider it a gamble, and it would be one that it would hurt to lose in a way that it wouldn't hurt someone with another 860 of them.

But even if I invested, my coins would be no better than anyone else's.  In fact they'd be worse than those who came in early on a wing and a prayer. I want to be rewarded for my ideas, not (just) my money.

But that's not my only, or even my main reason for being cagey.  I also have issues with Lionel and the whole way he's managed/ing this thing.  Before I open up fully about mine, I would like to see a clear explanation of exactly what his original idea was, and I don't want him, or you for that matter, to take my ideas and claim that this was what he intended all along.

As things stand at the moment, I don't believe he ever had a viable plan.  I don't believe his system could have worked at all.  Even if it could have, I don't believe it was secure.  I don't believe his claims that he had security proofs, or if he did, that those proofs established the real-world security of his system.  I'm not calling him a liar.  I think it's quite possible that he believed in what he was doing, but if so, then I think he was mistaken.

[Dazza]

There is a vulnerability, which I think is unavoidable under my scheme, which is that a malicious miner could open up the program in a debugger mid-execution, and change a few variables.  So long as he doesn't do this within the 10ms interval for which he claims a block win, and as long as he doesn't claim a bounty, then his mischief will go undetected.  This doesn't compromise block security; he will still have proven that he's worked, just not in the way the buyer wanted.  The only person harmed is the buyer who doesn't get what he's paid for.  The miner has no financial incentive to do this, so as long as it's documented and buyers know that this is a risk they're taking, then I think it's OK.

[Cryptorials]

You don't need to know in advance how long it will run.

The buyer commits a number of ELC, and specifies how much he will pay the winning miner for each block solved while running his program, and what bounties he will pay for what results.  This is written into the blockchain.  Once committed, the network won't let him spend those coins in any other way, until the offer terminates or is withdrawn (Edit: by which I mean the buyer withdraws the offer.  There should be a short time before the withdrawal becomes effective, in order to allow the miners to notice the withdrawal and stop work).  It is then up to each miner to decide for himself if he accepts the deal or not.  There's no need for him to notify the buyer of his acceptance (Edit: or anyone else, until he actually solves a block). He just starts running the program.  The network confirms each block in the usual way and pays the winning miner out of the committed funds.  Similarly the network confirms the bounties, and pays the solving miners.  When the funds are exhausted, or when the offer terminates or is withdrawn, then the miners will abandon work on that program and run another.  Any ELC left over are returned to the buyer.

If each miner decides whether to take a particular piece of work does that mean you could have miners who only take a certain kind of work?

Forgive me if I'm being ignorant, but one thing that concerned me was the idea of people doing both bitcoin PoW and other assorted work on the same machine - wouldn't that mean doing bitcoin PoW on a regular CPU/GPU, which is obviously a lot less efficient that the ASICs it would be competing against? In this scheme, for example, could you have a form of merged mining where a bitcoin miner with an ASIC took only bitcoin PoW? If there were transactions providing fees then perhaps it would even pay for the miner to submit work so there is always bitcoin PoW for him to do, so he can earn ELC transaction fees on top of the regular mining. Also then perhaps a CPU could take different work to a GPU, meaning everyone could take the jobs best suited to his mining rig?

[Cryptorials]

Well I think it is perfectly fine if miners chose the work they want to do. This way we will have different types of miners specialized for different types of computations.
I think in the long term we will have Bitcoin ASICs, GPUs, FPGAs, CPUs ... each of them being good at a certain subset of problems. So no matter if you want a double SHA256 hash for the bitcoin blockchain to be found (ASIC) or if you want to calculate something highly parallelizable (GPU, FPGA) or if you calculate something memory intensive (CPU), you will always have someone who is willing to work off your task as quickly as possible.

Restricting the mining process to only one type of devices would have significant impacts on the efficiency of the entire cluster.

So yes, in my eyes miners must be able to chose the PoW function they work on freely.

Awesome! In addition to making sure that the cluster is efficient for solving any problem, I think this could also increase the number of people who are able to participate in mining which will probably help with adoption and getting people involved with development and stuff.

[poornamelessme]

But that's not my only, or even my main reason for being cagey.  I also have issues with Lionel and the whole way he's managed/ing this thing.  Before I open up fully about mine, I would like to see a clear explanation of exactly what his original idea was, and I don't want him, or you for that matter, to take my ideas and claim that this was what he intended all along.

As things stand at the moment, I don't believe he ever had a viable plan.  I don't believe his system could have worked at all.  Even if it could have, I don't believe it was secure.  I don't believe his claims that he had security proofs, or if he did, that those proofs established the real-world security of his system.  I'm not calling him a liar.  I think it's quite possible that he believed in what he was doing, but if so, then I think he was mistaken.

Is Lionel even following this thread, on his own coin?

I see a lot of technical discussions, which is fine and all, but none of it from the original developer of the coin.

Basically to an outsider, it looks like some guy wrote a flawed whitepaper, with no devs aboard, asked for money without escrow, and now a couple of guys in this forum (you and Knievel) have ideas on how to fix the whitepaper. Only problem is, they aren't the ones doing the ICO.

Still waiting for Lionel's CV, info on his other devs + coders, and so on. That assumes any other devs even exist, and Lionel is really Lionel.

[Dazza]

That, judging from my short brainstorming on that, would only work if you do not use the input of the proof of work function as the solution to the block.
You would rather have to submit the state (yet to be defined, but sth. like the content of the stack) at a certain point in time (like on one of these 10ms marks).
Then, the state after applying the next x operations (preferably until the next 10ms mark) is checked to meet some arbitrary target value.

Assuming that by "10ms" we actually mean some yet-to-be-decided deterministic metric, which proxies for that or some other interval of time.  Your idea now is to use SHA-256(StartState,EndState) over the 10ms interval as your proof of work function.  Correct?

This however opens up new attack vectors in my opinion.

Nope, just the old one.

It is for example hard to verify that the "state" one submits can actually be reached by executing the present proof of work function.
Verifying this would essentially mean to run the entire function from the beginning.

Agreed, but we can't do that.  Nor do we need to, from a block security point of view.  Think of the 10ms segment as an entire user supplied program.  StartState is random input.  EndState is the corresponding output.

And it suffers from the same flaw.  An attacker might know a faster algorithm to compute EndState from StartState.

You're on the right tracks, though.  Try again.  Here's a hint, or perhaps a puzzle.  Order matters.  SHA-256(This,That) might work, while SHA-256(That, This) is trivially exploitable.

[Dazza]

Basically to an outsider, it looks like some guy wrote a flawed whitepaper, with no devs aboard, asked for money without escrow, and now a couple of guys in this forum (you and Knievel) have ideas on how to fix the whitepaper. Only problem is, they aren't the ones doing the ICO.

I don't know if I qualify as an outsider any more, but that's exactly what it looks like to me too.  Added to that is the tight timescale that I doubt is achievable.

I think Lionel should hand the whole project over to EK, website and funds and all.  I think he's by far the most credible person involved.  Also EK should offer to refund everyone who wants their money back, and to those who stay in, make it clear that nothing is decided, that everything is open to brainstorming.

[Cryptorials]

I've actually found the way the ICO was set up quite exciting and inspiring. It seems like Lionel set out the bare bones of a great idea that may or may not be possible, and set the sliding price scale so that if you think its possible - place your bets now. If you, like EK and Dazza, have the means to make it possible, then you can make your bet come good. If you're on the fence, then you can wait and see how the ideas unfold, but you'll get a lot less for your money.

Amazingly it seems to have drawn people perfectly placed to solve the problems, if they are indeed solvable.

[kbhutto]

Where is Lionel?

[Cryptorials]

I've actually found the way the ICO was set up quite exciting and inspiring. It seems like Lionel set out the bare bones of a great idea that may or may not be possible, and set the sliding price scale so that if you think its possible - place your bets now. If you, like EK and Dazza, have the means to make it possible, then you can make your bet come good. If you're on the fence, then you can wait and see how the ideas unfold, but you'll get a lot less for your money.

Amazingly it seems to have drawn people perfectly placed to solve the problems, if they are indeed solvable.

I personally think, should we solve it (and I have the feeling that we can make it, in fact that we are really close to it) such that the scheme is rock solid,
this coin will change high performance computing once for all. Imagine a few ELC coins can give you as much computational power as a cluster that you have to pay thousands of dollars for ... per hour.
Either the currently present clusters become WAY cheaper, or the price of an ELC explodes. Just my personal view, and my no means meant to influence anyone in making a decision.

But it has to be rock solid, that is why we do all this brainstorming stuff.

Good to hear. I'm definitely going to buy into this, but I think I'll wait till block 399990 to decide how much 

[xxxgoodgirls]

@EK are you actually in contact with Lionel? I am unsure about investing in this coin or not.
He is still the guy who will handle the ICO funds and it looks like he's not giving his contribute anymore to the discussion you and dazza brought in.

[Dink]

I would skip the "rushing" part and just come up with something rock- solid, it seems the whitepaper was rushed and now look at all the discussion that needs to take place .  Thank you Dazza and Ek.

[Cryptorials]

I would skip the "rushing" part and just come up with something rock- solid, it seems the whitepaper was rushed and now look at all the discussion that needs to take place .  Thank you Dazza and Ek.

You're welcome. Well, getting it rock-solid has the highest priority now. I am still thinking about the part that I have written a few hours before. I more and more get the feeling that this idea still needs a few more iterations. But I also think it might serve as a good starting point. I am right now summarizing all possible attacks that come to my mind so I can discuss them with Dazza.

Yeah, no point in rushing and I don't think anybody expects you to come in and then get everything planned out in a few days. In any case, it would ruin the whole nature of the ICO if we know that's its going to work before the reward starts to go down. I like the idea of it being a bit of a gamble with out-sized potential returns, and then gradually becoming a safer bet (hopefully) but with lower returns over the course of the long ICO sale.

[Dazza]

I am right now summarizing all possible attacks that come to my mind so I can discuss them with Dazza.

Please don't large me up, even in your own mind, as some kind of crypto guru.  I'm not.  I'm not a crypto virtuoso.  I'm not a crypto expert, (unless your definition of "expert" is "an ex is a has-been and a spurt is a drip under pressure".)  I'm just some guy on the internet who's a little smarter than the average bear, and who's done a little reading on the subject.  What I know about it might fill a book.  What I don't know would fill a library.

And please don't let anyone assume that if we come up with something that we can't see how to attack, this is evidence that it is secure.

[Cryptorials]

The faster algorithm attack is driving me nuts  
I more and more get the feeling that we must move away from the blockchain idea as proposed by bitcoin.
We have to ensure that no-one would have any positive effect from solving his own blocks quicker than the rest.

If we cannot prevent people to write shortcut-algorithms we have to ensure that they would have no reason to do so.

Means the transaction ledger (user payments) is separated from the POW ledger (keeping track of bounty payments and fee collections).
Also the latter must be designed in a way that malicious miners cannot roll-back the chains by using the 51% attack to charge back bounty payments they had paid before ... or at least have no real benefit from doing so. Furthermore, block generation on one ledger must verify transactions in the other ledger in a way that it cannot be reverted.

Maybe it's also worth to think into this direction. I, however, find the faster-algorithm attack really interesting from the scientific point of view. I wish we solve it.

Are you suggesting that there should be two ledgers so that the person solving his own blocks only gets his own payment, not control of consensus or transaction fees?

If so then doesn't this mean that you need some other pow or pos or something to secure the payment ledger? I that case you might as well just build a distributed cloud computing system and take bitcoin as payment, but you get rid of the big benefit - one set of work, meaning one set of costs, producing two valuable results (securing the network and whatever the purpose of the work has for whoever submitted it).

[Dazza]

The faster algorithm attack is driving me nuts  

Pernicious, isn't it.

I more and more get the feeling that we must move away from the blockchain idea as proposed by bitcoin.
We have to ensure that no-one would have any positive effect from solving his own blocks quicker than the rest.

I keep vacillating on that one.  If the workers aren't securing the blockchain, for example, if we move to a pure proof-of-stake system, we still need a way to prove to the buyer (or at least provide him with some assurance) that the workers are working

Maybe it's also worth to think into this direction. I, however, find the faster-algorithm attack really interesting from the scientific point of view. I wish we solve it.

I still think I've solved it.  I could be wrong about that.

[Dazza]

About five minutes ago, I wrote.

I still think I've solved it.  I could be wrong about that.

I haven't solved it, at least not in the strong form I thought I had.  Damn faster algorithm attack.

I still think I've solved it in the weaker from that I've alluded to earlier.  Specifically I believe, but cannot prove that an attacker can achieve at best a linear speedup.  The problem is, how much he can speed it up is proportional to the efficiency of the proof of work system.  If the system is split 50-50 between useful work and overhead, then the attacker can double the speed, by dispensing with running the program, and just suffering the overhead.  If it's split 67-33, he can tripple the speed.

I can force him to suffer the overhead.  I can't force him to run the program.  Damn, damn, damn, damn, damn, damn.