Author

Topic: [ANN][XEL] Elastic Project - The Decentralized Supercomputer - page 249. (Read 450524 times)

sr. member
Activity: 434
Merit: 250
Right now, testnet tokens are just "free" anyway, you can basically mine proof shares without actually doing the job's work... so if I need some coins I'll just "take" them from the network!  Wink

(But that is another bug, for another day...)

So I guess that today is as good a day as any....

Let's look at an (only slightly more) interesting and fun bug, which we'll call "HMC bug #6" but which is more generally known as "basic work stealing."  (Note that XEL is not the first design to encounter this problem!)

Consider a cast of characters:

Altruistic Alice, the "wealthy peer" - She is a big XEL donor, holds lots of XEL, and uses it to stake-forge blocks on the network.  Being altruistic she selects transactions indiscriminately, simply prioritizing those she receives first.

Basic Bob, the "normal miner" - He doesn't have much XEL, but he has a big farm of small CPUs and GPUs left over from other coin mining, so he mines PoW/PoB hoping to one day strike it XEL-rich by getting lucky on some big work order.  He's a bit of a loner because his small apartment is always noisy and hot, and his few friends give him funny looks when he runs out in the middle of dinner because "the damn rig is on a fork again" whatever that means...

Crafty Cathy, the "hax0r" - She's an attacker on the network, looking to heist some coins to sell in order to add to her BTC hoardings.  Maybe we should call her Cracker Cybil, because she keeps excessively well-connected nodes using a heavily modified client on her ill-gotten botnet nodes around the world.

Developer Dave, the "code monkey" - He's a bioinformatics software engineer at a scientific research institution, tasked with solving for a new crispr sequence to adjust dermal elasticity in primates, with the hopes of addressing the epidemic plight of crows feet on aging people's faces.  (Or something like that.  He's got work to request, that's the only important aspect, here, about Dave.)

Now consider the scenario:

1. Dave codes up some big, complex job to do some gene sequencing search, which he knows can have only a single possible bounty solution.
2. After some local testing, he's so confident with the job construction that he submits it to the network backed by his entire 2 million XEL budget offered up. (It's a well-funded research institute.)
3. Alice sees his work order TX and forges it into a block.
4. Bob sees the job, says to himself "this is the one!" and points all of his cpu resource at it, raising the temperature in his hot apartment another 5 degrees.
5. Let's say that Bob gets really lucky, and finds 2 PoW certificates and then stumbles upon the 1 PoB certificate.
6. Excitedly, Bob pushes these 3 transactions out to his peers.  (Over half of which are actually just Cathy.)
7. Cathy's modified, well connected nodes don't relay the TXs.  Instead, they quickly create new transactions with the same input values, but signed by her, and relay these instead.
8. Alice sees Cathy's TXs before Bob's TXs, since Cathy is both well connected and happens to have botnet C&C nodes in a datacenter on an OC-12 uplink geographically near Alice. Alice starts forging them into the next block.
9. Alice then sees Bob's TXs, but rejects them as duplicate, forging Cathy's into a block instead.
10. Bob sees the block with *his* solution values, but signed by Cathy and, being none the wiser, assumes he's been improbably out-lucked.  He gives up on life and jumps out of the nearby window.
11. Dave goes about his life, being none the wiser, happy to have received his solution so quickly.
12. Alice goes about her life, being none the wiser, happy to have contributed to the network.
13. Cathy immediately cashes out the free 2 million XEL on the open XEL/BTC markets, crashing the spot price - but hey what does she care?  She goes about her life, happy to have increased her BTC position.

Woops.

The original Satoshi PoW designs (as well as sound derivatives, like MotoCoin ) are not subject to this sort of problem, because the block contents being hashed over in the work function are always unique to each miner as they contain a signature in the coin-base transaction.  Changing this signature invalidates the solution.  This might suggest a "simple" solution of including some PoW-submitter-specific identifier directly in the hashing, but the same sort of solution can't be used to prevent PoB stealing.

In order to prevent both certificates from being subject to stealing the "allowed" input values for a miner would need to be made somehow specific to that miner, perhaps derived as a deterministic stream from their public identifier.  However, since miners need to be able to iterate a *lot*  of (effectively unbounded) input values, this is only a partial mitigation - jobs with a low number of inputs (96 bits is not all that much entropy these days) could still be subject to a variant of the attack where after seeing Bob's solution, Alice just "grinds" her input value stream generator on her botnet in hopes to quickly find a stream position which produces the same inputs. (On average this would still be lower cost to her than actually doing the work, ofc.) To prevent this, the amount of input values would need to be forced to always be sufficiently large such that there is no reasonable probability of grinding the inputs to find a corresponding "position" in their own stream which creates the same inputs.

In other words, XEL should probably always fill *all* input memory with random values, taken from a deterministic generated sequence derived from something miner-specific, and work/bounty solution certificates should include the position in the stream which gives the corresponding inputs, for validation.

Questions?
hero member
Activity: 535
Merit: 500
@HunterMinerCrafter thanks for stopping by. Hope you'll stay with us longer and I hope you'll get some BTC for your help.

I've actually been lurking on the thread(s) for quite some time.

I also hope that I'll get some BTC for help.  I'm still waiting for that BTC from Ethereum developers to be donated to Tau.  (Even though I am (apparently) no longer "on" the Tau project.)  Eth never paid out on even the *first* consensus-breaking bug that we reported to them.  (After that, I never bothered to report any additional bugs/design-flaw to them, some of which are still latent in their implementation(s) just waiting to turn into the next DAO hack debacle, HEH.)

(I just hope that you don't all come to resent me by the time that I've finished deconstructing XEL entirely.... Wink  I have something of a touch-of-death for these alts, yknow...)

Well, this should be an interesting time, in any case!

Please send me your BTC address PM. (or if you want place it in your signature). I guarantee you that I'll send you 1BTC from my personal stack if you stay with us for at least 5 pages of this thread (with hot discussion).

(I donated to XEL much below 1BTC but I'm trying to help as much as I can because when I heard of it I thought that it can happen and can be some kind of very new thing in crypto world.)

Anyway I think that @Lannister will reward you more for your contribution, before mainnet will be live.
legendary
Activity: 1148
Merit: 1000
@HunterMinerCrafter thanks for stopping by. Hope you'll stay with us longer and I hope you'll get some BTC for your help.

I've actually been lurking on the thread(s) for quite some time.

I also hope that I'll get some BTC for help.  I'm still waiting for that BTC from Ethereum developers to be donated to Tau.  (Even though I am (apparently) no longer "on" the Tau project.)  Eth never paid out on even the *first* consensus-breaking bug that we reported to them.  (After that, I never bothered to report any additional bugs/design-flaw to them, some of which are still latent in their implementation(s) just waiting to turn into the next DAO hack debacle, HEH.)

(I just hope that you don't all come to resent me by the time that I've finished deconstructing XEL entirely.... Wink  I have something of a touch-of-death for these alts, yknow...)

Well, this should be an interesting time, in any case!

maybe Evil-Knievel can post a public XEL address for donation, would like to donate 2% of my XEL coin to support XEL long term development.

 Smiley
sr. member
Activity: 434
Merit: 250
@HunterMinerCrafter thanks for stopping by. Hope you'll stay with us longer and I hope you'll get some BTC for your help.

I've actually been lurking on the thread(s) for quite some time.

I also hope that I'll get some BTC for help.  I'm still waiting for that BTC from Ethereum developers to be donated to Tau.  (Even though I am (apparently) no longer "on" the Tau project.)  Eth never paid out on even the *first* consensus-breaking bug that we reported to them.  (After that, I never bothered to report any additional bugs/design-flaw to them, some of which are still latent in their implementation(s) just waiting to turn into the next DAO hack debacle, HEH.)

(I just hope that you don't all come to resent me by the time that I've finished deconstructing XEL entirely.... Wink  I have something of a touch-of-death for these alts, yknow...)

Well, this should be an interesting time, in any case!
sr. member
Activity: 434
Merit: 250
EDIT: Do we want elliptic curve arithmetics supported natively?

That would be interesting, but IMO what would be very interesting would be to include native "FHE" (homomorphic) operations.  I could imagine many users would be willing to trade performance of their job evaluations for protection of information related to their work algorithm.
sr. member
Activity: 434
Merit: 250
Currently, most of HunterMinerCrafter's bugs are fixed in this version! Cleaning out the remaining few parts.

It does seem improved, but still some related problems. For example:
Code:
m[0] = (1 && 2) + 3;
still causes a cast exception.  (There are other cases...)

Perhaps this fix could be simplified by doing away with a distinct boolean type, and making the entire language operate only on word-width (int) values.  There really isn't any particular reason that I can see for distinguishing bools.

Quote
@HunterMinerCrafter's: Grammar is there as well (ElasticPL.jjt)! Rebuild compiler and parser with "./rebuild.sh"

Great, this will certainly make some things a bit easier!
sr. member
Activity: 434
Merit: 250
HunterMinerCrafter, I am right now reworking the entire interpreter / VM.
I think I will be finished today, and then we should launch a bug bounty program. I would suggest 1 BTC per each crash in the new scripting engine! What do you think?

I think that not all bugs have the same "value" - a minor parser problem is not "worth" the same as a way to "trick" the WCET, for example.

Quote
The goal is to have a interpreter that never crashes, even if people write syntactically correct (but semantically wrong) programs.

Any program which can crash/hang the VM can be used to attack the network.  Any program which can "trick" the WCET can be used to get "free work" done, at best, or to attack the network as well, at worst.

Quote
The only issue that we cannot "ignore" or rather disable by grammar or semantics is a stack overflow error, where people make huge nested clauses which exceed the stack space! I have to think a moment about how we should handle such cases. Since it should occur during parsing already, when building the AST tree, I think that we can detect such things before they get embedded into the block chain. (See an poc example here: https://github.com/OrdinaryDude/elastic-pl/blob/master/stack_overflow_error.spl)

Yes, I had this on my list as well, but I am not sure, yet, how much of a problem it really is.  A simple, linear loop over the source string to count nesting depth of blocks and parens before parse could probably catch it without excepting at the jvm level.

Quote
EDIT: I will ask Lannister to consider giving you some BTC for your work so far! Just as an appetizer to look for more issues.

Great, let me know what you decide.  I'd be happy to continue trading problem reports for BTC for as long as problematic issues and BTC remain, ofc.  Wink
hero member
Activity: 994
Merit: 513
But we really need to think about the POW difficulty scaling.

Maybe we should organize a contest or so! The current scheme (inspired by the Dark Gravity Wave) obviously "sucks".
When you look at the past blocks, we are *faaaaar* from having a steady #10 tx per block, its more kind of oscillating, even though a miner is working constantly without much fluctuation in its computation power.

pls refer to AntiGravityWave (every block), that may inspire you.
https://github.com/viacoin/viacoin/tree/master/src

The biggest problem is that we may have many many miners but no POW for several blocks when there is no work online. When then a new work package is submitted, the difficulty is low again causing many POW submissions to be broadcasted in bursts until the difficulty adapts again.

Ok, I'm just brainstorming here, but couldn't you just create work by mining other currencies over the XEL network? Someone proposed this as a use case anyway, plus, it is scaleable, so maybe, that would be a way to keep the difficulty at a certain level: if there is no work to be done on the network, miners create their own work by mining other coins. They are rewarded in form of those coins. You might have to implement a system, where smaller miners don't lose the XEL they invest to bigger miners (essentially, they would pay the XEL invested back to themselves). Or maybe it levels out anyway, if they pay for a Job that fits their size… A relatively crude way would be to create a special job, where the miner can decide to mine this job only on their own…
legendary
Activity: 1260
Merit: 1168
There is still a flaw in the grammer that I would like to level out.

For now, we are distinguishing between "^" and "xor" depending if it connects two UnaryExpressions or two ConditionalExpressions.
Using the same token for both resulted in the requirement to use Lookahead=2.
The reason is because ConditionalExpressions may effectively be UnaryExpressions themselves and in
Code:
if(1 ^ 3)
its not clear if it's two Unary- or two ConditionalExpressions). I like to avoid that.
Let's see if I can fix that today! I appreciate any pointer to the right direction.
hero member
Activity: 1039
Merit: 510
I propose to implement Woodcoin's logarithmic supply curve, ensuring longevity and stability of the coin:

http://woodcoin.org/woodcoin.pdf/
legendary
Activity: 1148
Merit: 1000
UPDATE: SHA512, SHA256, RIPEMD160, RIPEMD128, Tiger, MD5 and Whirlpool-T added to Elastic PL language!
More to come!


EDIT: Do we want elliptic curve arithmetics supported natively?

seems zcash need a lot of memory, but do we have a way to parallel the zcash mining to some small nodes?

then elastic will become the biggest zcash network.

also zcash will have a billions marketcap in few years.

hero member
Activity: 535
Merit: 500
Lot of awesome work.

@HunterMinerCrafter thanks for stopping by. Hope you'll stay with us longer and I hope you'll get some BTC for your help.
legendary
Activity: 1260
Merit: 1168
UPDATE: SHA512, SHA256, RIPEMD160, RIPEMD128, Tiger, MD5 and Whirlpool-T added to Elastic PL language!
More to come!


EDIT: Do we want elliptic curve arithmetics supported natively?
legendary
Activity: 1260
Merit: 1168
This is pending work, but for those who want to try out hacking with the new Elastic PL language, do this:


Currently, most of HunterMinerCrafter's bugs are fixed in this version! Cleaning out the remaining few parts.


@HunterMinerCrafter's: Grammar is there as well (ElasticPL.jjt)! Rebuild compiler and parser with "./rebuild.sh"


1. Checkout from git

Code:
git clone https://github.com/OrdinaryDude/elastic-pl

2. Edit your Elastic PL program. One example is in a file named sqrt.spl

Code:
input 3;
m[10]=5;
m[11]=10;
m[m[10]+m[11]+100]=m[10]+m[11];
m[9]=6+m[8];
m[1000]=4^7;
if((3<1)^(3>2)){
m[1001]=1000;
}
if(1^((3>1)+1)>2){
m[123]=~7;
}
if(~(1<2)){
m[20]=2;
}
Whirlpool 0 0;
m[100]=m[11]+(m[11]>0);
repeat(6){
m[9]=9;
}
if(3 != (3<0)){
m[999]=9;
}
m[918]=(!(22==!(!0-1)));
verify m[918]==1;

3. Execute the Elastic Test Compiler with this file as the input

Code:
java -jar test_compiler.jar sqrt.spl

4. You will see some input like the WCET and the current state of the memory

Code:
127 beavis@methusalem ~/Development/elastic-pl (git)-[master] % java -jar test_compiler.jar sqrt.spl                                                                              :(
Elastic Programming Language Interpreter Version 0.1:  Reading from file sqrt.spl . . .
[!] Worst case execution time: 173
[!] Random integers specified: 3
m[0]: 1192166409
m[1]: -1414904722
m[2]: 1231453518
m[3]: -1106075325
m[4]: -2016486447
m[5]: 231832450
m[6]: 1137366352
m[7]: -1601577969
m[8]: -291001792
m[9]: 9
m[10]: 1908861904
m[11]: 1994669180
m[12]: -56578766
m[13]: 1450743772
m[14]: -1248421791
m[15]: 77205338
m[20]: 2
m[100]: 1994669181
m[115]: 15
m[123]: -8
m[918]: 1
m[999]: 9
m[1000]: 3
m[1001]: 1000
[!] Bounty requirement met: true
5.75s user 0.19s system 320% cpu 1.855 total

legendary
Activity: 1260
Merit: 1168
HunterMinerCrafter, I am right now reworking the entire interpreter / VM.
I think I will be finished today, and then we should launch a bug bounty program. I would suggest 1 BTC per each crash in the new scripting engine! What do you think?

The goal is to have a interpreter that never crashes, even if people write syntactically correct (but semantically wrong) programs.
The only issue that we cannot "ignore" or rather disable by grammar or semantics is a stack overflow error, where people make huge nested clauses which exceed the stack space! I have to think a moment about how we should handle such cases. Since it should occur during parsing already, when building the AST tree, I think that we can detect such things before they get embedded into the block chain. (See an poc example here: https://github.com/OrdinaryDude/elastic-pl/blob/master/stack_overflow_error.spl)

EDIT: I will ask Lannister to consider giving you some BTC for your work so far! Just as an appetizer to look for more issues.
newbie
Activity: 24
Merit: 0
Steadily moving forward. Keep up the good work guys.  Cool

yeah, should be very closed to launch.
hero member
Activity: 840
Merit: 500
Risk taker & Black Swan farmer.
Steadily moving forward. Keep up the good work guys.  Cool
sr. member
Activity: 434
Merit: 250
The other issue I see with this disparity between slow & fast work is that it seems very likely that the fast work will end up paying out all their POW rewards, but the slow difficult work may only pay out a small fraction of it due to this disparity between slow and fast work.  It would be great if we could figure out a way that the POW rewards get paid if there are miners working on that work id.

More fundamentally, the Satoshi proof-of-work is predicated on an assumption that "cost per hash" is relatively comparable, and that solutions are distributed uniformly relative to hashing effort applied.  Neither of these are the case, here, which means difficulty can not be "correct" as originally defined.  This puts the jobs mechanism at risk in several ways.  (Also other bugs for other days, there...)
sr. member
Activity: 434
Merit: 250
post your xel and I'll send some testnet tokens - or use the EK's public node to take some.

Regards

If I come to need some, I can let you know.

Right now, testnet tokens are just "free" anyway, you can basically mine proof shares without actually doing the job's work... so if I need some coins I'll just "take" them from the network!  Wink

(But that is another bug, for another day...)
sr. member
Activity: 464
Merit: 260
One thing which I can say for sure is that the difficulty calculation will need to be made entirely per work order job, as some programs will execute at 200k evals/sec/cpu and some will be 2k evals/sec/cpu and (as things stand right now) some might be 0.0002 evals/sec/cpu.

I tend agree with this assessment that the POW should be per work id.

My understanding is that the owner of the slow eval/sec work is supposed to provide larger POW payouts to entice miners to mine their work; however, I could see this having the opposite affect because of what HunterMinerCrafter wrote.  Regardless of how much the POW payout is of an extremely slow eval/sec work item is, with only 10 POW payouts per block (for all work ids combined) there would be a good chance that even if you found a POW result for the slow eval/sec work you wouldn't get paid as the fast eval/sec work is going to get evaluated 10x, 100x, etc times more often than this slow work and would likely consume most of the 10 POW payouts.

The other issue I see with this disparity between slow & fast work is that it seems very likely that the fast work will end up paying out all their POW rewards, but the slow difficult work may only pay out a small fraction of it due to this disparity between slow and fast work.  It would be great if we could figure out a way that the POW rewards get paid if there are miners working on that work id.
Jump to: