which memory hard hashing algorithm can equalize low-computational and high-computational power devices to utilize blockchain in the IoT?

Question

Recently IBM and Microsoft showed their interest (IBM post, Microsoft post) in utilizing bitcoin's blockchain for internet of things (IoT) development. Let's assume that in close future the blockchain technique to be implemented in smart cars overlaying road conditions or traffic data to each other. Bitcoin's Blockchain is based on a SHA256 Proof-of-Work or finding a proof which when is hashed is more than a target. This helps to tackle double-spending attack.

In the example of future smart cars described above the majority of honest nodes will be low-computational power devices (maybe like raspberry pi) therefore, it will be easy for adversary to perform a double-spending attack if implemented mining algorithm will not be able to bottleneck mining capabilities of devices.

In the question "How can I make sure password hashing is secure on computers while not being prohibitively slow on mobile devices?" Mr.nsl is looking for a password hashing algorithm that can give balance between security and speed for fast-CPU and slow mobile devices. I am looking for an algorithm that can resist fast CPU/GPU to use their computational power for overtaking advantage over the network of low-computational device. Therefore I have two assumptions how to tackle this issue:

1. Utilize a hashing function that can provide a fairness/balance to a certain extent between low-computing and faster-computing devices (e.g., between laptop and raspberry PI).
2. While connecting to peers in a network nodes send each other versions and if versions are the same, nodes proceed with exchanging verack (a connection ackknowledgement) messages. Hence maybe these devices should along with a version of installed client should send their computational abilities. Therefore if a requesting peer possesses too much of computational power no other nodes will connecto to him.

Therefore questions,

1. Even though I understand that solving proof-of-work is directly influenced on one's computational speed, can a crypto person suggest me a memory hard hashing algorithm that can satisfy assumption #1, i.e. be good for the raspberry pi (which currently has max of 512 MB RAM) and not let an average computer with 8GB to overtake a network and perform double-spending attacks?

2. Also, is it physically possible to send your real computational power during a handshake with a node?

Thanks

Answer 1

While memory-limited algorithms are discussed in the altcoin community ("alternative" cryptographic coins based on ideas similar to bitcoins), they do not primarily solve the disparity between a "low-end" general purpose computer (e.g. the RasPi) and a high-end general purpose computer, but they are used to prevent special-purpose hardware that exceed computational power (also computational power per Watt) by multiple orders of magnitude. The idea is that hashing does not need much chip space, and you build a chip that calculates many hashes in parallel by just copy/pasting it many times into one case. On the other hand, memory does need space, and megabytes of memory need lots of space (take a look at current processor die pictures. The vast amount of die space is occupied by caches, not by the calculation engine). For bitcoins, special-purpose bitcoin mining chips (FPGA miners and later ASIC miners) "took over the world" around 2 years ago, because they outperform general-purpose machines. That's the reason coins like DogeCoin use the Scrypt algorithm already mentioned by sukosevato.

The ration between RasPi memory (0.5GB) and an enthusiast's PC (32GB) is likely even greater than the difference in CPU power between those devices, so going memory-limited doesn't help the RasPi to catch up. In fact, if you can not prevent a device that has n times the computational power and n times the memory of a smaller device, to just behave like n of the smaller devices.

So in summary: I don't think you can find a hashing algorithm based on CPU and memory operations that does not give fast (gaming) PCs a big advantage over the Pi (which still has a lot of computing power).

Addressing your second question, sukosevato is right again: There is no way to prevent a device claiming to have a lower computational power than it really has. A fast device pretending to be a slow device can be caught if it systematically takes advantage - if you know the hashing speed of a device, you know how many coins it sucessfully mine in a certain time interval. If it takes advantage of getting "small devices bonus" by needing to solve less difficult hashes, and submitting more solutions than you can realistically find with the small device, the network could try to ban you.

The only reasonable way I see to prevent devices claiming too low computing power is to make showing the increased computing power more advantageous than hiding it. Alas, this directly translates to: The faster device must be able to convert the full speed advantage to profit, otherwise it could try to play slightly unfair and exploit the "slow device bonus".

Answer 2

I'm not too familiar with bitcoin and have no idea how it is relevant to IoT. The best example of a memory hard hashing function that I know of is Scrypt.

I can answer your second question to some extent. You could easily send some random string of bytes to a node and tell it hash it as often as it can within a certain time frame. This way you could establish a lower bound for the performance of a node. The more often they managed to hash it, the faster it is. However, nothing is stopping a very fast node from simply hashing it 100.000 times and then doing nothing for the rest of the time period to act like it is a slower node. So a lower bound for real computational power is possible, an upper bound is not since a faster computer can always fake being slow.