Bitcoin Forum

preamble

What is proof of work, and why should i care?

From the bitcoin wiki:

For a block to be valid it must hash to a value less than the current target; this means that each block indicates that work has been done generating it. Each block contains the hash of the preceding block, thus each block has a chain of blocks that together contain a large amount of work. Changing a block (which can only be done by making a new block containing the same predecessor) requires regenerating all successors and redoing the work they contain. This protects the block chain from tampering.

The most widely used proof-of-work scheme is SHA-256, which was introduced by Bitcoin. Some other hashing algorithms that are used for proof-of-work include scrypt, Blake-256, CryptoNight,[1] HEFTY1, Quark, SHA-3, scrypt-jane, scrypt-n, and combinations.

The reality:

the checksum method only validates that a block  is a valid sha256 hash less than or equal to  the target described in the equation. this means, that at the hashing level there are nothing to verify how a hash was produced, only that it confirms all previous work and contains valid transaction data, satisfying the "Proof of Work" concept.

What does this mean for altcoins?

Typically, altcoins rely on hashing blocks using a different algorithm, then converting the hashed block to a sha256 unsigned integer.

This means that an attacker only has to have enough Sha-256 asics to account for 51% or more of the network hashrate and a modified client designed to hash with sha256 instead of all of these algorithm's that have been piggy backed on top of sha256.

What about chained hashing?

Chained hashing provides only the illusion of security, or security through obscurity as we like to call it. this collection of algorithms:

Here's a case study:

Logicoin:

https://github.com/Logicoin/logicoin/blob/master/src/hash.h

now, lets look at bitcoin:

https://github.com/bitcoin/bitcoin/blob/master/src/hash.h


As you can see, these alternative hashing implementations are reliant on conversion back to uint256 then hashed as sha256, meaning that the entire hashing process can simply be shortcircuited back to sha256, bypassing these algorithms entirely, making the coin mineable by sha256 asics.

Additionally, the flaws with chained hashing algorithm's do not stop here. With WildKeccak derivates such as Boolberry and JackpotCoin, it is possible to short circuit the internal switch statements that chooses which hash to use in a given round. An attacker could modify his client to use the weakest, fastest hash every round, producing a clear advantage for his miners.

Additionally, this exposes a flaw in every coin other than bitcoin, and there in also reiterates the true strength of bitcoin, which relies solely on the strength of the sha256 algorithm and the proof of work concept to secure the blockchain. If you are looking for innovation in altcoins, it simply doesn't exist in a true form to date.

Conclusion

How can this issue be addressed?
Through mathematics, plain and simple. If you want to add additional hashing algorithms to bitcoin, you need to modify proof of work with additional checksum algorithms to confirm a given hash satisfies the specifications of your hashing algorithm. With chained hashing, you want to make a requirement that will show the block was hashed in a specific order. adding this data to the block defeats the purpose and a method of bypassing this will be discovered relatively easily. Instead, you might want to follow the approach of the BCRYPT hashing algorithm, which appends data to the beggining and end of a hash, offering information as to how the hash was produced.

One might be able to determine an algorithm for appending a secret to the end of the hash, and number for each round of hashing to the beginning.

say we have four rounds of hashing well to illustrate my point this is what our block hashing method might look like.

step1:

input -> 0xfe 0xdd 0xbe 0xfd //some random data
secret[0]-> //some random data computed from our input
hash-> create a hash from secret and input

result:

secret[0].hash.input  //our result hash string would

at the end of 4 rounds our hash would look like

secret[3].secret[2].secret[1].secret[0].hash / input

in this example, we can easily prove all subsequent steps in the chained hashing algorithm originated from the original input, while making it difficult to replicate without performing the entirety of the work.

Again mathematics, plain and simple.

If i am wrong, please post a reply. this is only theory based upon observation of various source codes and my approximate understanding of the concept of Proof Of Work, and the various implementations available in the altcoin scene.

shhh  :-X r3wt don't let reality get in the way of some good 'innovation' stories  ;)

lol, from where i'm sitting it looks like the innovation stories are just cover up for the Bitcoin Asic flashmining behind the scenes. I could be completely wrong though. There could be some magical code i didn't see that prevents this from happening...

Wouldn't it be easier to "make the point" by moding a mining program and raping non-sha altcoins?

Why expend energy in trying to convince others about the theory, instead of actually doing it and showing it? What is the obstacle?

I'm seeking someone with a fairly large amount of Sha 256 asics to help me test the theory.

Some altcoin algos run at like 3-5 Mhs at some GPUs while SHA256 runs at like 500 MHs. It's already 100x+. Why do you need asics? Mod a client and have fun.

In the case of cryptonight which runs at like a few hashes per sec, you are orders of magnitude faster with 500 MHs of a GPU running sha256.

There is a check for the correct PoW hash in CheckBlock():

    // Check proof of work matches claimed amount
    if (!CheckProofOfWork(GetPoWHash(), nBits))
        return DoS(50, error("CheckBlock() : proof of work failed"));

I don't see how you can get around this check.

You don't understand the premise at all. The hashes are always converted back to sha256, meaning theoretically you could short circuit the entire algorithms of these coins with bitcoin's sha 256 algorithm and still produce valid blocks on the network.

No I understand what you are saying. I do not understand why you "require" sha256 asics for "testing it". You can test it even with a cpu (or gpu).

Well yes, thats the basics of proof of work. however the problem is, its only verifying a sha 256 hash. not the hashes that produced that hash, so my premise is that you can shortcircuit the entire process and just mine any of these coins with sha 256 ASIC.

Yea, in theory one of the slow chained scrypts should be vulnerable, how about Franko? Mod a client and hit that shit hard, lets see if it will break.

The premise here is that this flaw could allow 51% attacks on alternate-algorithm coins with bitcoin hardware.

If I understand this correctly and it's a fesible scenario it wouldn't affect multi-pows like myriad because submitting a sha256 generated block directly will be assigned to the sha256 part of the chain and will not affect the other 4 algorithms even though their final hash is done via sha hashing.

You have a wrong premise. The main vulnerability is NOT bitcoin hardware, but the speed differential between sha256 and other hashes. If cryptonight hashes at a few hashes per second and you use a sha256 800 mhash GPU (7970), why would you need an ASIC hardware? You will already have 99.9% of the network.

you're both not understanding each other. your arguments have nothing to do with his and vice versa.

Excuse me:

He writes


Why would the short-circuiting of the hash only work in ASICs and not in CPUs or GPUs (with SHA256 mining software)? Please explain this to me because I'm an idiot.

Hmmm so you're saying get a modified client, rip out the part where the hash is verified on it's respective algo and just leave the part where the hash is verified after the sha256 final hashing thus if the submitted block was created using sha256 correctly the final check will pass it as good ... it's a very good question but I'm in no position to respond to it. I've messaged a trained coin dev with your thread as it seems very very interesting.

Yeah he didn't get that, your point is valid, you don't need asics to mine sha256, you can generate sha256 blocks with any mining hardware :)

Exactly. And GPU sha256 is orders of magnitude faster than many other algos (so bypassing the other algos ensures a tremendous speed advantage). Hence the "requirement" for ASIC sha256 to "test it" is bogus. So why doesn't he make a software mining client for cpu or gpu so that we can see it?

Quoting this, so it doesn't get edited and I can come back later for a story.


He says his client can get around this CheckBlock

it's not the mining client that needs to be modified, it's the actual coin source from what I understand so that you skip the primary hash verification and go directly to the sha256 one. The network should see it as a valid hash since it's ultimately a sha256 hash.

Yes, that's what I actually meant (wrote it wrong). Even the wallet can mine with a cpu sha256 - and be quite fast at it (compared to slow algos running on GPUs).

ahmed_bodi just made a good point, even if you mod your client and submit a buttload of directly generated sha blocks, the other nodes on the network will still verify using the usual method and thus will reject your blocks and ultimately mark you as a doser.

and it wouldn't make for a valid 51% attack because since your blocks will be rejected from the start your hashrate won't even register on the network thus you will not be able to attack anything.

Each block is checked using the client source, you can make one client do anything, even mint 10000000000 of whatever coin, but the block will be rejected by all the other conforming clients because the block is invalid.

There is no "getting around" the CheckBlock function. The PoW hash is calculated and if it does not match the block is rejected by the network.

Emulating the right PoW hash with sha256 hashes is likely a much more complicated problem than simply solving the PoW hash.

good ideas but it doesnt check out. (i explained it to foodies)

You might be faster hashing sha256, but the problem at hand is also matching the correct PoW hash. This seems to be a much more demanding problem than calculating the PoW hash itself.

This is a outrageous claim without something more than some theoretical development in the way the underlining math works.  Celebrate the "discovery" of this idea when you have successfully broken a few shitcoins. 

is the claim so outrageous. what does checkProofOfWork do exactly?

i'll comment it for you so you understand.

https://github.com/Logicoin/logicoin/blob/master/src/main.cpp  line 1420


now, for CheckWork:


The hashings itself may occur in other algorithms, but the checks are only ran on sha256 hashes, which was my point all along. if the sha256 hash satisfies the target it doesn't matter whether the extra hashing ever occured.

I'm having trouble understanding what the argument against my theory is? is it that short circuiting can't possibly produce a valid hash without all the extra hashing? i don't believe that to be true.

checkProofOfWork is called with a PoW hash, i.e. GetPoWHash(), and not a sha256 hash.

GetPoWHash() executes the hashing algo on the client

https://github.com/Logicoin/logicoin/blob/0bfec6b1e2a63c0a60a77fb38dfb95d666293ed9/src/main.h#L1320
https://github.com/Logicoin/logicoin/blob/0bfec6b1e2a63c0a60a77fb38dfb95d666293ed9/src/hashblock.h#L62

block getpowhash calls header gethash calls a hash function.

In the above it does the hash9.

In litecoins case it's scrypt: https://github.com/litecoin-project/litecoin/blob/master-0.8/src/main.h#L1376

https://github.com/Logicoin/logicoin/blob/0bfec6b1e2a63c0a60a77fb38dfb95d666293ed9/src/main.h


so the argument is that a short circuited hash would be seen as invalid on the unmodified clients? i don't think thats true at all.

without the technical side.

your theory is based on the assumption that the hash is accepted as is and checked if it meets the difficulty.

instead the values you send are run through the client, a hash is produced using the algo of the coin, and if that production matches up the block is valid.

so a sha256 hash matching isn't enough, it'll be invalid.

snipped code:


(you were looking at the gethash function from transactions, not blocks in your above snip)

How will it be invalid? the target and all underlying block data are the same. when the hash is converted to sha256, how would the hash be accepted but rejected if it is short circuited with sha256?

So far, much of my theory has been proven wrong, but i still think i'm on to something here. there is a flaw, i can feel it

Quick question. I noticed in your OP there is no mention of x11. There is a reference of Logicoin and you posted this only in Darkcoin thread.



I guess I am unclear if if you are claiming x11 has this flaw? And why post that snarky comment in Darkcoin thread?

r3wt, the nonce is the PoW not the hash. It's the former, nonce, time merkle which is checked, not the hash.

flaw's in what you thought was being checked.

very glad somebody is checking this stuff though, always question and check, thanks!

no you took it the wrong way. I wanted to get the attention of
 eduffield, the dark coin dev's opinion. With so many ahitcoins darkcoin seems to be one of few with a dev who would care to investigate it.

:D still gettin love I see <3

Wouldnt it be easier to just open a testnet?

No intention of editing it.
awaiting said story :D (I know a story or 10 myself).

Because sha256d(blockheader) produces a different result to sha256d(other_hashing_algo(blockheader)).

If you assert that it can produce the same, that'd be a sha256 collission and every crypto program which uses sha256 is screwed.

As I said earlier, the checks you are looking at all assume the hash you send is the one being used, when the hash is reproduced by each client when a block is broadcast. The client will come to a totally different hash that doesn't match the one you specified and just reject the block.

you're right I was totally ignoring the difference in the output after x rounds. I didnt thinkit would mean a collision but you are right in the end. Bitcoin doesn't use prngs so the hashes have a certain precision in which they are predictable. If I know correctly understand, its the constant nnonce that makes it all work to produce independently verifiable hashes