[ANN][XEL] Elastic Project - The Decentralized Supercomputer - page 248.

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

Quote from: HunterMinerCrafter on September 24, 2016, 07:31:43 AM

I think that including the workId (this is derived from the block hash wher the work is published iirc?) probably closes at least one other attack on my list. Prior to this change, a job publisher could also precompute PoW certificates for the work to return those funds to himself immediately after publishing...

Actually, the workId is derived from the transaction (not the block) in which it was published so I guess yes .. your attack would work.
While not interesting for the PoW certificates (you can very well charge back using the work cancellation button) it might become interesting when precalculating bounties, submitting them prior to the closure of a work to get most of the bounty fund payout for one-self (remember, the fund is always distributed among all bounty submissions after the work has been closed).

I am starting to fix that right away!

Quote from: HunterMinerCrafter on September 24, 2016, 07:31:43 AM

This does seem to prevent the basic work stealing problem. If you actually fill the entire memory space it would also mitigate (but not entirely prevent) another attack still on my list.

Actually, I am right now filling the entire 12 integers of "possible input entropy" but not the entire memory space. If required to do so, we could go this way, even though this would increase the overhead noticably. Right now it's pretty handy to have large parts of the memory "nulled".

I am really eager to hear about this attack Wink

Quote from: HunterMinerCrafter on September 24, 2016, 07:31:43 AM

The laundry list is still growing. I'm finding a few new attacks each day, and with the weekend now here I'll have some time to *really* focus again.

I hope (and I really believe) that with your help we can get rid of most (all?) these problems Wink

Also, I am really excited to hear about your next discoveries and start brainstorming about ways to conquer them.
After all, you have my sincere appreciation for your help!!

Lannister

full member

Activity: 140

Merit: 500

I'm blocking all private messages. Use Bitmessage!

Quote from: HunterMinerCrafter on September 24, 2016, 07:29:19 AM

P.S.

BTC address: 1EVnmWVjTWWEbHrWenoyJ3k7wroyAD1K1r

I have just sent you 4 BTC. At this point I have to mention that you are solely responsible for ensuring that your federal income taxes are paid at the right time.

https://blockchain.info/tx/d6694f56b875f517d7aa8c1c58a7ec42d0c7169ed94a5645b1f6f6bc82bf3de5

HunterMinerCrafter

sr. member

Activity: 434

Merit: 250

Quote from: Evil-Knievel on September 24, 2016, 03:53:13 AM

I have thought about FHE operations, but do they really need a native support? Or is the support already there implicitly because you can apply the regular *, /, +, -, % operations on "encrypted values"?

If you think of a Palier cryptosystem,

Paillier is only partial homomorphism.

Quote

Also, I think in the first place it might become complicated using "encrypted values" in the verify routine.

This is no problem for FHE, there are several approaches. This is commonly applied with "searchable encryption" schemes. (Basically publisher gives an index of acceptable values and a trapdoor to check if a value is in the index.)

Other option is to use bit circuits instead of word-width operations. Then you reduce size of the output value until it crosses a probability threshold. (This approach will produce some error (more error the less you reduce size of output) so you might miss some solution or pay for some solution which is not actually valid.) Downside is that this makes for significantly larger programs.

These are all forms of "conditional disclosure of secrets" schemes, there are many and they are well studied, particularly in the past 5-10 years.

(Such "conditionals" are also possible with partial HE as in "cryptoleq" but they necessarily weaken security as they must do partial decryptions with obfuscation, so they necessarily reveal more than at most one bit of information.)

HunterMinerCrafter

sr. member

Activity: 434

Merit: 250

Quote from: Evil-Knievel on September 23, 2016, 08:00:08 AM

Fixed this (and that m[(1>0)]=1)! Thanks!

I'll make another pass over the parser first thing and let you know if I find any of these remaining.

Quote

Also fixed, the WCET tricking bug,

There is definitely at least one problem remaining in the RuntimeEstimator, but I'm still working out some details.

HunterMinerCrafter

sr. member

Activity: 434

Merit: 250

Quote from: Evil-Knievel on September 23, 2016, 06:23:22 AM

I'm impressed!!!

Thanks!

Quote

1. Miners have to provide a <=32byte long "seed" called the "multiplicator" instead of the direct integer arguments.
2. Then a random number stream is derived from the public key of the sender, the workId and the 32 byte long seed by hashing those values using sha256.

I think that including the workId (this is derived from the block hash wher the work is published iirc?) probably closes at least one other attack on my list. Prior to this change, a job publisher could also precompute PoW certificates for the work to return those funds to himself immediately after publishing...

Quote

3. This random number stream is then used to obtain exactly 12 random integers which are then passed to the ElasticPL program.

This does seem to prevent the basic work stealing problem. If you actually fill the entire memory space it would also mitigate (but not entirely prevent) another attack still on my list.

Quote

THANKS FOR SHARING!!! I HOPE TO GET MORE HINTS ON HOW TO "DECONSTRUCT" XEL SOON ;-)!!

The laundry list is still growing. I'm finding a few new attacks each day, and with the weekend now here I'll have some time to *really* focus again.

HunterMinerCrafter

sr. member

Activity: 434

Merit: 250

P.S.

BTC address: 1EVnmWVjTWWEbHrWenoyJ3k7wroyAD1K1r

HunterMinerCrafter

sr. member

Activity: 434

Merit: 250

Quote from: Lannister on September 23, 2016, 04:05:24 AM

Considering your knowledge I hope you would be able to stick around and shed some more light on the flawed parts of the project.Your help is much appreciated.

Thanks! I'll stick around until I run out of interesting and/or fun ways to (ab)use the network. If there's still a meaningfully "useful" network left when I'm done, maybe I'll even stick around longer. Wink

HunterMinerCrafter

sr. member

Activity: 434

Merit: 250

Quote from: coralreefer on September 22, 2016, 08:35:41 PM

Edit: I think I understand now....you are saying that the hash wont get propegated so unless the inputs are unique to me anyone can steal it....that sux :-)

Right, there is a subtle variant of Sybil attack here. Cathy is racing Bob to propagate their work certificates. Even if we told the story with 2 users acting as single peer nodes (not Sybil) on acoustic couple or home broadband Cathy basically still has a 50/50 shot at stealing any given work solution that she sees. At that point it would likely just come down to network routing topology.

With even a small out-resourcing (obv my story was over the top, by today's standards) Cathy could pretty much trivially ruin Bob's day the vast majority of the time.

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

Quote from: HunterMinerCrafter on September 22, 2016, 12:24:03 PM

Quote from: Evil-Knievel on September 22, 2016, 07:49:30 AM

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.

I have thought about FHE operations, but do they really need a native support? Or is the support already there implicitly because you can apply the regular *, /, +, -, % operations on "encrypted values"?

If you think of a Palier cryptosystem, and let D() be the decryption routine and E() the encryption routines.
Now let's assume someone wants to calculate something arbitrary, to keep it simple let's say (x * y) % n.
Wouldn't it be sufficient, for a work author, to provide E(x) and E(y), and let the program calculate (E(x)*E(y) % n^2) using it's native methods since D(E(x)*E(y) % n^2) = (x + y) % n?

Also, I think in the first place it might become complicated using "encrypted values" in the verify routine.

EDIT: Following elliptic curves are now supported natively in ElasticPL:

Code:

("secp192k1","secp192r1","secp224k1","secp224r1","secp256k1","secp256r1","secp384r1","prime192v1","prime192v2","prime192v3","prime256v1")

yosir

sr. member

Activity: 260

Merit: 250

Hi,

Great job guys. I see dedication and skill that can't be found in most of projects.
If I may ask, is there a way to buy more XEL now, after ICO? Is there some kind of mechanism (not platform but a safe process) for sell/buy between participants of ICO?

Thanks,
Yossi

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

Quote from: atomicgroup on September 23, 2016, 11:25:52 PM

hi, i have partecipate at the ICO but i dont receive my XEL... can you help me?

We are still in the testnet phase.

atomicgroup

full member

Activity: 370

Merit: 100

hi, i have partecipate at the ICO but i dont receive my XEL... can you help me?

beyinsi

hero member

Activity: 742

Merit: 501

ek, when will be ready elastic? can u tell us a roadmap,

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

Also fixed, the WCET tricking bug, where you could use an overflow in the WCET counting mechanism to trick the program in thinking your program has WCET 0.
This overflow should be catched here now: https://github.com/OrdinaryDude/elastic-pl/commit/92ce4c4e10941b8c3fe7269849a3c13ae3e5abb3

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

Quote from: HunterMinerCrafter on September 22, 2016, 12:20:56 PM

Quote from: Evil-Knievel on September 22, 2016, 06:36:21 AM

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

Fixed this (and that m[(1>0)]=1)! Thanks!

EDIT: Elliptic curve point operations now added to ElasticPL for SECP256k1 for both compressed and uncompressed representations.

Example script:

Code:

input 12;
m[0] = 0;
m[1] = 0;
m[2] = 0;
m[3] = 0;
m[4] = 0;
m[5] = 0;
m[6] = 0;
m[7] = 1;
m[10] = 0;
m[11] = 0;
m[12] = 0;
m[13] = 0;
m[14] = 0;
m[15] = 0;
m[16] = 0;
m[17] = 1;
m[999] = 4;
SECP256K1PrivToPub 0 true;
SECP256K1PrivToPub 10 true;
SECP256K1PointAdd 0 true 10 true true;
SECP256K1PointScalarMult 10 true 999 4 true;
verify (1==1);

Specification:

Code:

SECP256K1PrivToPub  
SECP256K1PointAdd     
SECP256K1PointSub    
SECP256K1PointScalarMult    
-- all outputs are written to the memory beginning at startinteger_state

Testoutput of example script:

Code:

Elastic Programming Language Interpreter Version 0.1:  Reading from file ec.spl . . .
[!] Worst case execution time: 12017
[!] Random integers specified: 12
m[0]: 46531711
m[1]: -1807618691
m[2]: 1831880000
m[3]: 1855307900
m[4]: -665028722
m[5]: 1267527484
m[6]: -1481921527
m[7]: -1185124194
m[8]: -452984832
m[9]: 319628733
m[10]: 48534491
m[11]: -239006336
m[12]: -212328887
m[13]: 76745492
m[14]: 80505875
m[15]: -1878073227
m[16]: -2072708460
m[17]: -1410808627
m[18]: 318767104
m[999]: 4
[!] Bounty requirement met: true

Converting the integers to hex, you will find out that the two calculated EC points are correct!!!
2*G = 02C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
4*G = 02E493DBF1C10D80F3581E4904930B1404CC6C13900EE0758474FA94ABE8C4CD13

Evil-Knievel

legendary

Activity: 1260

Merit: 1168

Quote from: HunterMinerCrafter on September 22, 2016, 02:14:41 PM

Quote from: HunterMinerCrafter on September 21, 2016, 01:12:50 PM

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!)
[...]

I'm impressed!!! Thank you so much for sharing your thoughts with us!

I have implemented a fix in the development branch! The most interesting part happens here:
https://github.com/OrdinaryDude/elastic-core/blob/development/src/java/nxt/Attachment.java#L274-L429

1. Miners have to provide a <=32byte long "seed" called the "multiplicator" instead of the direct integer arguments.
2. Then a random number stream is derived from the public key of the sender, the workId and the 32 byte long seed by hashing those values using sha256.
3. This random number stream is then used to obtain exactly 12 random integers which are then passed to the ElasticPL program.

Hijacking other people's proof of work therefore should be no longer possible. All that comes at the cost of an additional effort to compute the sha256 hashes for the random number inputs at the miner's side.

THANKS FOR SHARING!!! I HOPE TO GET MORE HINTS ON HOW TO "DECONSTRUCT" XEL SOON ;-)!!

EDIT: Miner has also been updated on the development branch!

e1ghtSpace

legendary

Activity: 1540

Merit: 1001

Crypto since 2014

http://www.elastic.pro/

The website seems to be down...
For me it "took too long to respond."

Is anyone else having trouble accessing the site or is it just me?

Lannister

full member

Activity: 140

Merit: 500

I'm blocking all private messages. Use Bitmessage!

Quote from: HunterMinerCrafter on September 22, 2016, 02:14:41 PM

Questions?

I'm sorry for the absence. My schedule has been swamped this year and things have been a little hectic lately with little room for spending time at the computer. I do have a question indeed: could you share your BTC address so I can throw a few thousand pounds worth of BTC your way for what you have so far disclosed? That's what I've got for now in my mobile wallet, plenty more to come after I finished downloading the blockchain.

Considering your knowledge I hope you would be able to stick around and shed some more light on the flawed parts of the project.Your help is much appreciated.

coralreefer

sr. member

Activity: 464

Merit: 260

Quote from: HunterMinerCrafter on September 22, 2016, 02:14:41 PM

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?

Great overview...This clarified some of my questions. However, you mentioned that the adding a signature wont help POB. My understanding is that POB also included a hash of the inputs, so if this hash was simply extended to include both a miner specific signature along with the inputs would that solve this issue without changing the current logic around the use of inputs?

Edit: I think I understand now....you are saying that the hash wont get propegated so unless the inputs are unique to me anyone can steal it....that sux :-)

ImI

legendary

Activity: 1946

Merit: 1019

Quote from: HunterMinerCrafter on September 22, 2016, 12:41:17 PM

Quote from: unvoid on September 22, 2016, 09:32:26 AM

@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!

This Input is very much appreciated! Eventually some of the donated funds go your way, other wise i am pretty sure we will come up with some BTCs or XEL.

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