[ANN][XEL] Elastic Project - The Decentralized Supercomputer

[Dazza]

Well I have to thank YOU for your hard work as well.

Yeah, but I can do my hard work while out walking dogs.

I will most likely finish the basic NXT scheme today, and I will then immediately start implementing your approach in a new branch.

Which means we're now In a race.  I have to articulate my latest thinking before you write the code it's relevant to.

Re that DoS attack on the NxT scheme we were talking about.  I suggested that, once two or more blocks using the same PoS were detected, all such blocks should be regarded as invalid.  This is a minor DoS in so far as if any of these blocks have been built on, that work will have to be discarded.

A better approach might be to regard the competing blocks as valid, but to treat the stake value as zero.  Nobody honest would build on them knowingly, but it is still possible that one might be built on, if the competitor blocks are injected later.  In that case, treat it as a valid chain, albeit with a lower value that the honest builders thought at the time.  So yeah, still kind of a DoS against those honest builders, but the attacker will be DoSsing himself just as much.  The impact upon the network would be between negligible and nil.

I think I can make it work pretty quickly in a test setup when I can assume more or less synchronized clocks, but this will be a big issue I think. I know I keep talking about these clocks, but I see many scenarios where the network can split and create to parallelly existing side chains when clusters of nodes form, that do have similar clocks. So over time those which have a clock that is off +10 seconds will end up in a filter bubble, just as those with a clock -10 seconds will, none of the groups accepting blocks from the other groups and working on two entirely different sub-chains.

Did you read that link I posted earlier in the thread about timing attacks?

We need a sophisticated methodology to mitigate such timing issues, that, in the worst case, can be in the order of minutes.

My gut feeling is that this won't be too much of a problem in the end.

Gotta go now.  Be back this evening.

[Evil-Knievel]

Gotta go now.  Be back this evening.

Great, I will have responded to all open questions and commented on your thoughts by then.
See you later.

[Evil-Knievel]

Short update:

I have the PoS mining ready by now. I need some more time to test everything and remove static parameters that I have (over)written in the code for debugging reasons.
Also I need to use all addresses with positive balance in the current wallet instead of (again just for testing) a hard coded pubkey. We are almost there.

Just so that you see something, here a little screenshot showing the "time to block estimation" in action.

This is what happens here:

1. The miner wants to create a block, so he generates a "Blocktemplate" based on the current transaction pool. In this process he also creates a Coinbase transaction paying the TX fees to himself.
2. He generates a "signatureHash" H which is a hash of the previous block's signature hash combined with his public key.
3. He calculates his own target vaue T which is personalized and bases upon the users stake value.
4. If H<T then he meets the block target and finds a block immediately,
if not, then he has to wait. The own target value T increases over time, linearily. The more stake value a user has, the faster this value rises.
Eventually, T will raise so much that H<T is true again, and then the user has found the block.
5. As we exactly know how fast T is rising for each user, we can exactly determine the time a user has to wait until he finds a block.


Right now, only visible in the console, soon presented nicely in the GUI client.

[Dazza]

1. The miner wants to create a block, so he generates a "Blocktemplate" based on the current transaction pool. In this process he also creates a Coinbase transaction paying the TX fees to himself.
2. He generates a "signatureHash" H which is a hash of the previous block's signature hash combined with his public key.
3. He calculates his own target vaue T which is personalized and bases upon the users stake value.
4. If H<T then he meets the block target and finds a block immediately,
if not, then he has to wait. The own target value T increases over time, linearily. The more stake value a user has, the faster this value rises.
Eventually, T will raise so much that H<T is true again, and then the user has found the block.
5. As we exactly know how fast T is rising for each user, we can exactly determine the time a user has to wait until he finds a block.

That is clever.

Suggestion: have the miner release the block 20 seconds (or some other value determined empirically) before it is due.  Nodes receiving blocks will calculate their own "due by" time, based upon the stake-value and their own idea of network time, and hold onto the block until then.  If no valid higher-stake block is received in the meantime, the miner wins the block.

Having everyone releasing early eliminates the advantage to be gained by unilaterally doing so.

[Dazza]

There ought to be a network-wide minimum balance in order to stake fully, otherwise we could suffer from network congestion (and could be DoSable) if there are large numbers of tiny balances trying to stake.

I disagree, the idea of Elastic is to provide supercomputing power... all these tiny balances are the computers that make up this decentralized supercomputer.

No they're not.  PoS is there to secure the blockchain, nothing else.  The distributed computing is a separate system which is not involved in blockchain security.  You don't need any stake to be part of the distributed computer, though your earnings from that might enable you to stake.  Similarly you don't need to work in order to be able to stake.

You lessen there ability to stake just like everyone else, they fall to the way side and stop contributing, soon your decentralized supercomputer is a centralized sytem controled by a few large holding stakers.

I don't think that would happen, because the big money will come from working, not staking.

network congetion? makes no sense. Any of these POS coins say keep your wallet open to stake.

Yes, but small balances, and even large balances don't get to stake every block.  They are entered into a lottery where their stake determines their chance of winning.  This is what prevents the network from being overwhelmed by a vast number of tiny PoSs

My scheme will allow every account with a balance that isn't tiny to stake every block, either collaterally, or given a little higher balance, fully.  Security comes from having as much honest stake participating each turn as possible, and I don't want to force small holdings into a lottery, in order to enable even smaller ones to participate.  It might give people the warm fuzzies if you tell them that they can stake their penny holdings, but it does nothing to enhance block security.

If some one wants to Dos the system they will...it wont  be because there are a bunch of tiny balances that leave it exposed.

With respect, I don't think you have the technical expertise to be able to judge that.

If dosing was that big of a problem all POS coins would suffer

No because of the lottery.  Only a tiny number of the sybils can win and get their PoSs accepted into the network.

[Evil-Knievel]

´
That is clever.

Suggestion: have the miner release the block 20 seconds (or some other value determined empirically) before it is due.  Nodes receiving blocks will calculate their own "due by" time, based upon the stake-value and their own idea of network time, and hold onto the block until then.  If no valid higher-stake block is received in the meantime, the miner wins the block.

Having everyone releasing early eliminates the advantage to be gained by unilaterally doing so.

Thanks ;-) Yes, releasing the block a short time before the due time is a very good idea. Thanks for that.
Still we have one issue left. Let us say, without loss of generality, the PoS hash is very bad for all active miners, i.e., a lot higher than the personal target value of each one of them. If everyone of these miners has a very low balance, e.g., 1 coin the personal target T would only rise by 1 unit per second. This may take a very long time.

Either we need an exponential increase in the target value, but that is bad because it means that people with more coins have significant advantages.

Not sure how to resolve this issue. We have to avoid such (even if they are unprovable) deadlock situations.
Would you think a hard deadline which, when passed, allows anyone to mine a block even with no balance in the account, could resolve that problem?

[Dazza]

Either we need an exponential increase in the target value, but that is bad because it means that people with more coins have significant advantages.

Surely it would reduce the advantage of people with more coins.

Assume that account A has ten times the balance of account B, and that both have approximately the same hash value.  Then with a linear increase in target value, account B would take ten times as long to be able to submit a block as account A.  With an exponential increase, account B would take log(10) more than account A, a constant difference.

Would you think a hard deadline which, when passed, allows anyone to mine a block even with no balance in the account, could resolve that problem?

With exponential growth, that would happen anyway pretty quickly, when the target exceeds 2^256.

[cryptoheadd]

When is the ICO ending?

EDIT: What's the Roadmap for the launch?

[titan20]

hi,
the website indicates today that 78,87 BTC was donated.

[Evil-Knievel]

The btc adress to sent the donations to (3Q2aKEGFTKDw3hghsBifXp39CZVMtZukxn) gives a balance of 20,50 BTC.

How come?

The addresses have changed.

[xxxgoodgirls]

hi,
the website indicates today that 78,87 BTC was donated.

The btc adress to sent the donations to (3Q2aKEGFTKDw3hghsBifXp39CZVMtZukxn) gives a balance of 20,50 BTC.

How come?

 

The address has been changed since Lannister took over the management of the project.
The original address was 3Qnj4QtdD4qtZcP82xyLq2paAEPDgfwezd

[Evil-Knievel]

Either we need an exponential increase in the target value, but that is bad because it means that people with more coins have significant advantages.

Surely it would reduce the advantage of people with more coins.

Assume that account A has ten times the balance of account B, and that both have approximately the same hash value.  Then with a linear increase in target value, account B would take ten times as long to be able to submit a block as account A.  With an exponential increase, account B would take log(10) more than account A, a constant difference.

Would you think a hard deadline which, when passed, allows anyone to mine a block even with no balance in the account, could resolve that problem?

With exponential growth, that would happen anyway pretty quickly, when the target exceeds 2^256.

You are absolutely right. Sometimes I make assumptions too quick without even thinking.
Well I have checked the NXT source code and they indeed tried to fix the problem by setting a fixed threshold of 3600 seconds when, if passed, every one can generate a block.

Code:

return hit.compareTo(target) < 0
                && (previousBlock.getHeight() < Constants.TRANSPARENT_FORGING_BLOCK_8
                || hit.compareTo(prevTarget) >= 0
                || (Constants.isTestnet ? elapsedTime > 300 : elapsedTime > 3600)
                || Constants.isOffline);

I am not a fan of this approach. I always try to look on such things from the network's perspective. A fixed time frame causes bursts of thousands of blocks being flooded in the network simultaneously once that threshold is reached.

Maybe we could do a linear target increase until the last block was mined 3600 seconds ago or more.
After that we switch to an exponential increase which quickly lets someone find a block but avoids that burst of network traffic.

[titan20]

Does Lannister have access to this old address?

hi,
the website indicates today that 78,87 BTC was donated.

The btc adress to sent the donations to (3Q2aKEGFTKDw3hghsBifXp39CZVMtZukxn) gives a balance of 20,50 BTC.

How come?

 

The address has been changed since Lannister took over the management of the project.
The original address was 3Qnj4QtdD4qtZcP82xyLq2paAEPDgfwezd

[Relaxedsense]

Hi Guys,

Could someone tell me when the crowdfunding phase will end? Also, would I be able to just donate using my multibit BTC wallet?

Many thanks.

Cheers

[Dazza]

Maybe we could do a linear target increase until the last block was mined 3600 seconds ago or more.
After that we switch to an exponential increase which quickly lets someone find a block but avoids that burst of network traffic.

3600 seconds is an hour, seems a bit long if we want a block every minutes.

Why not just have a slow exponential increase?  If the target doubles every 7 seconds, then even a target of 1 will exceed 2^256 in just under 30 minutes.

Or wait one minute with no change in the difficulty (to allow nodes with up to a minute's clock skew to submit blocks they win imediately) then start doubling every 7 seconds, guaranteeing a block in just over 30 minutes.  Nodes with greater skew than that will suffer a disadvantage, but I don't think that is much of a problem.

[Dazza]

´
That is clever.

Thanks ;-)

It's clever because it's simple, it works, and because I didn't think of it.  My solution would have been to keep rehashing using the timestamp as a nonce.[/quote]

[Evil-Knievel]

It's clever because it's simple, it works, and because I didn't think of it.  My solution would have been to keep rehashing using the timestamp as a nonce.

And with your addition of the exponential 7-second target-doubling scheme, which i personally find genius, we at the same time mitigated both the block-takes-forever and the block-submission-burst-after-duration-threshold problems.  

EDIT: I think I should take some time this weekend to write all our latest thoughts down in the white paper.

But the really hard (and interesting) part is yet to come. Computational verifiability.

[Dazza]

Nice suggestion, I support it! Although I wouldn't call them workers but I'd rather refer to their computational tasks.

What would you call them, then?

[Dazza]

And with your addition of the exponential 7-second target-doubling scheme, which i personally find genius...

That's enough backslapping.  Back to work.

But the really hard (and interesting) part is yet to come. Computational verifiability.

Yep.

[Dazza]

Before I post my revisions, let's touch base on the NXT scheme.  My understanding is that, regardless of stake, the first valid PoS block received by a node which meets the target is the winner.  It's just that the target is harder, and in general will be met later for small stakes than large ones.  If a node receives a valid block, before it has launched its own, then it won't launch.  I would imagine that in such a scheme, relatively few blocks launch, but if two are launched near simultaneously (or which become valid near simultaniously) in distant parts of the network, then the likelihood of a fork with both branches being built on is high.  How do you propose to eliminate side-chains?

With my scheme, a lot more PoS blocks will be launched, and even more PoS without a block, so the level of network chatter will be higher, but the voting will ensure that side-chains will very quickly become moribund, and will die when the recent stake value of the main chain gets high enough.

When reading the following be careful to distinguish between the Stake Value (SV) of an account (ASV), the SV of a block (BSV), and the SV of a chain (CSV).  These will all have different definitions.  There will be two kinds of PoS, those that come with an associated block (PoS+B) and those that don't (PoS-B).  I'm also not going to consider timing issues as my goal here is just to get the idea across.

The timing can be solved by having nodes not care about the hours or minutes, only the seconds, and by having nodes periodically poll their peers for the latters' view of Elastic Network Time (ENT) and taking the average (appropriately defined.  If one peer is 01 and another is 57 then their average is 59).  Over time the nodes should converge.

Assume that we want to regard as confirmed any block once it is N blocks deep into the blockchain.

My new idea is similar to my old one, in that for each block, there is a refectory period followed by a bidding period.

I suggest a change in terminology.  Call this the voting period rather than the bidding period.  I think this more clearly reflects what is going on.

As before, each node discards any invalid PoS (i.e., those that violate the protocol, or those that do not extend a live chain) on sight, along with its block if it has one, and for each live chain, if it receives more than one valid PoS+B extending that chain, it regards the block with the highest ASV as the (local) winner.

If a PoS+B is ineligable to extend the chain due to that account already having won too recently, then it will not win, but could still participate collaterally.

It also keeps track of every other (valid) PoS - with or without block - it receives.  (It could discard the blocks of losing PoS+B, so long as it has a way to recover them from other nodes, if necessary.)  Nodes should discard or reject a PoS-B whenever it has decided to retain at least the PoS of a PoS+B from the same account.

At the start of the bidding period, a node should launch a PoS+B, for any account it controls with ASV greater than x% of the ASV of the account it regards as having won the last block.  Because ASVs are likely to obey Zipf's law, x could probably be set quite low without causing flooding.  Other nodes may have a different view of the winner of the last block, so a PoS+B might legitimately be launched, but rejected by other nodes who do not think its ASV is high enough.  (Nevertheless, a node should retain an otherwise valid PoS+B from an account it judges to have insufficient ASV for as long as it is the highest ASV PoS+B it has seen.  As soon as it sees another with a higher value, it can discard the lower one.)

In addition, the node should try to create a PoS-B for every account it controls with ASV > 0,

Or ASV > some threshold.

including accounts for which it has launched PoS+B.  (The duplication is necessary because, as stated above legitimately submitted PoS+B may be rejected by other nodes due to insufficient ASV.) Unlike PoS+B, PoS-B will have to pass a hash value test which depends upon the account's ASV as with NXT. If successful, these are also launched at the start of bidding.  Valid PoS-B are never rejected on grounds of insufficient ASV.

I would abandon this hash value test. for reasons given in my earlier reply to Dink.  Also the last sentence would no longer apply though the stake threshold for a PoS-B would be less than for a PoS+B.

Finally, as a last resort, if a node has neither launched a block nor received a (valid) one (including otherwise valid blocks from accounts with insufficient SV) then it should launch a PoS+B for its highest SV account according to the delay schedule described in my previous suggestion.

All launched PoS (both PoS+B and PoS-B) should extend the chain with the greatest CSV, according to the launching node.

The end result of all of this, is that so long as a node controls at least one account with ASV > 0, there will be at least one chain extended by a PoS+B.  Any chain not so extended dies.  Also a chain dies if it's CSV is less than y% of the CSV of the winning chain.

Sidechains should be allowed to develop a few blocks, to test the network's view on them, before killing them off.

Apart from the addition of PoS-B, The new scheme differs from the previous in that an account's ASV is no longer the time integral of its balance.  Instead it is equal to the lowest balance that the account has had during the last N blocks.  An account that was created or which has won a block fewer than N blocks ago has an ASV of zero.

The block extending a chain has a BSV equal to it's own ASV plus the ASV of all other PoS+B and PoS-B extending the same chain. Call these other contributors of ASV to the BSV "collateral support".  No account's ASV is counted more than once in the past N blocks, so if any of the PoS, including the winning PoS+B has already contributed collaterally to the BSV of an earlier block in the chain, then it is not counted again.  Nor, if a block is added to a collateral supporter, does the new block add to the collateral support.  In other words, collateral support is given to sisters, not aunts.  The CSV is the sum of the last N blocks' BSVs.

The idea behind collateral support is that the main chain will benefit from honest PoS more than any side-chain, including a side-chain being built by an attacker.  (If the attacker's chain benefits more, then it is the main chain by definition.)  Moreover an attacker can gain nothing by diverting his resources into his own collateral sybils, since this will just take away ASV from his winning blocks.  This is a zero-sum game for him.  PoS-B allows every account-holder with any ASV at all a chance to contribute collaterally to blockchain security, though they can never win a block unless their ASV is enough to allow them to launch a PoS+B.  Every PoS, with or without block, will need to has all the PoW supporting it's predecessor.

To summarise:  PoS+B need to meet an ASV threshold, but not a hash threshold.  BoS-B need to meet a hash threshold, but no ASV threshold. Note that the attack I describe above is defeated.  A PoS miner cannot PoW his PoS+B because there is no hash target to meet.  Neither can he PoW his PoS-B because there is no block to diddle.

This is slick, but again I think the whole hash target thing in these scheme would result in tiny accounts getting to stake, while larger accounts can't.

If a fork persists longer than N blocks, then we increase N by 1 per block so that it always covers at least as far back as the fork point.

For clarity, leave N fixed, and let M be the number of blocks back to the earliest live fork point, or M=N if larger.

To maintain the fork, an attacker will have to bring ever more resources to bear.  Or increase his chain's CSV past that of the main chain, at which point it takes over as the main chain. To do this, he will need to own N account each with a higher balance than anyone else.  If we ever see the same N accounts winning over and over, we could increase N even if we don't see a fork.

I have a different way to prevent the same N accounts winning over and over again.  For any given chain, order the PoS+B trying to extend it by ASV.  Then the one with the Highest ASV wins straight away so long as it hasn't already won in the last M blocks.  Else if it won n blocks ago with n<=M, multiply its ASV by n/N, and move on to the next.  If the PoS+B with the next highest ASV hasn't won in the last M or 2N blocks (whichever is greater), then it wins straight away.  Else if it won n<max(M,2N) blocks ago, multiply its ASV by n/2N and move onto the next.  For the PoS+B with the third highest ASV, repeat the procedure using M and 3N and so on.

If no block wins straight away choose a block which has won the least number of times during the last M blocks.  Usually this number will be zero.  If there are several blocks tying on this metric, use the modified ASV as the tie-breaker.

With this scheme, larger stakes will win the block more often, but, so long as there is an alternative, never more than once since transaction confirmation or the oldest live fork point.  Smaller stakes get to win occasionally.