POW improvements #1227

New Issue

2018-04-28T02:57:23+02:00

Kleshni commented

2018-04-28 02:57:23 +02:00

(Migrated from github.com)

I'm going to work on some improvements to the current POW subsystem:

Continuously update expiry time while doing the work to hide your computing power from peers. Short living messages would also get advatage from this, because POW calculation can take notable part of their TTL.
Calculate several POWs in parallel in the same thread. Previous change will require to periodically interrupt calculation, so we can interleave several POWs creating something like a simple task scheduler.
Add ability to stop POW and cancel or edit a message in the UI.
Add an expected time indicator to the UI, analogous to Vanitygen's.
Make starting nonce random, solving this issue #1213.

What more?

I'm going to work on some improvements to the current POW subsystem: - Continuously update expiry time while doing the work to hide your computing power from peers. Short living messages would also get advatage from this, because POW calculation can take notable part of their TTL. - Calculate several POWs in parallel in the same thread. Previous change will require to periodically interrupt calculation, so we can interleave several POWs creating something like a simple task scheduler. - Add ability to stop POW and cancel or edit a message in the UI. - Add an expected time indicator to the UI, analogous to Vanitygen's. - Make starting nonce random, solving this issue #1213. What more?

PeterSurda commented

2018-05-03 09:35:45 +02:00

(Migrated from github.com)

Good idea

Kleshni commented

2018-05-14 06:13:08 +02:00

(Migrated from github.com)

I realised that random starting nonce can't completely hide the number of threads. It's because the first successful nonce is taken as the result, so an attacker can try all nonces before it until he finds another solution. This way he can limit the range of possible starting values making them not so random for him.

If there are two consecutive or not very distant nonces that both satisfy the POW target and a node has chosen the second of them, it reveals high probability that the node uses a multithreaded worker.

Maybe this problem is not serious, but it shows that random starting value is a bad solution and there may be more such problems. It's like using one-time pad multiple times, to encrypt all nonce trials.

I see several possible solutions:

Use strong encryption instead of this one-time pad. Encrypt a counter with a block cipher and use this value as a nonce. This must be performed for each iteration, so this would be unacceptably slow.
Choose random nonce every time. Like the prevoius option it's too slow, and a little worse because of collisions, which are impossible in case of a block cipher.
Start with a random nonce and then take the last 64 bits of the double hash as the next nonce. This is as fast as the current unencrypted counter. But these hash chains can form cycles, when a nonce collides with one of the previous. And they provide only 64-bit security: instead of decrementing a counter an attacker now needs to reverse a 64-bit hash.
Choose the first 56 bits at random and try all 256 possibilities for the last 8 bits. If two solutions are found, select one at random. This is fast and looks secure, I think it's the best option.

I realised that random starting nonce can't completely hide the number of threads. It's because the first successful nonce is taken as the result, so an attacker can try all nonces before it until he finds another solution. This way he can limit the range of possible starting values making them not so random for him. If there are two consecutive or not very distant nonces that both satisfy the POW target and a node has chosen the second of them, it reveals high probability that the node uses a multithreaded worker. Maybe this problem is not serious, but it shows that random starting value is a bad solution and there may be more such problems. It's like using one-time pad multiple times, to encrypt all nonce trials. I see several possible solutions: 1. Use strong encryption instead of this one-time pad. Encrypt a counter with a block cipher and use this value as a nonce. This must be performed for each iteration, so this would be unacceptably slow. 2. Choose random nonce every time. Like the prevoius option it's too slow, and a little worse because of collisions, which are impossible in case of a block cipher. 3. Start with a random nonce and then take the last 64 bits of the double hash as the next nonce. This is as fast as the current unencrypted counter. But these hash chains can form cycles, when a nonce collides with one of the previous. And they provide only 64-bit security: instead of decrementing a counter an attacker now needs to reverse a 64-bit hash. 4. Choose the first 56 bits at random and try all 256 possibilities for the last 8 bits. If two solutions are found, select one at random. This is fast and looks secure, I think it's the best option.

This repo is archived. You cannot comment on issues.