Looking for some feedback possibly to feed into an RFC
Signature Proofs
I’m proposing an alternative proof of work from the existing hash-based proof.
This is because the majority of computation work on the safe network is signature based. Proving a node can do fast hashing isn’t proving it’s able to contribue useful computation to the network.
I believe if proof of resource (or at least, the computational part of it) is based on hashing, it will incentivize the wrong developments from farmers looking to optimize their throughput with custom hardware. This could have significant implications for the future performance and security of the network.
The basic idea is to replace the hash function in the proof with the signature function.
Similarities
- The node performing the proof must supply a valid response to be accepted on the network.
- The difficulty of the proof can be set arbitrarily by the network.
- The network supplies some challenge data.
- The node must find some extra data that satisfies the challenge conditions and return it to the network.
The node must find some response data that when combined with some presupplied challenge data will create a signature value below a threshold target. A valid signature value cannot be precomputed by the node, so forms an effective proof of signature capability.
Basic Design
The new node is set a challenge by the network
NETWORK:
send_challenge_to_node -> random_challenge_data, difficulty_threshold
The node uses this data to prove their signature capability
NODE:
message = challenge_data + my_random_data
signature = sign ( message )
while signature > difficulty_threshold
message = challenge_data + new_random_value
signature = sign ( message )
send_to_network -> message, signature
The network assesses the signature capability of the node using the time taken to respond with a valid answer (less time means more capable).
NETWORK:
verify signature challenge has been passed
assess time taken to complete challenge
The test is easy to administer, keeping load on the network low:
- the node to be tested is given some random challenge data to sign, and a difficulty threshold
The test is easy to verify, keeping load on the network low:
- check the signature is below the difficulty threshold
- check the signed message contains the original challenge
- check the signature is valid for the given public key and message
The test is difficult to pass, ensuring the node can support high loads:
- the node cannot know which value combines with the presupplied data in a way that results in a signature below the target difficulty, so must try using brute force to find a valid value.
Risks
- luck is a factor - the node may find a valid response in a short time. However, like hash-based proof, the challenge is statistically reliable over many samples (an exponential distribution as with bitcoin mining). This implies the test should be administered periodically, and is not particularly useful as a one-time proof (see below).
- the response should be restricted in length, since verifying the signature of large messages can consume resources that should be used to perform other network functions.
- the signing cipher must not use a mode of operation that enables preimaging. A change to any single bit of the message should result in all bits of the signature having equal probability of being updated.
Reducing The Impact Of Luck
Instead of accepting the first answer to pass the difficulty threshold, allocate the node a specific amount of time to perform as many signatures as possible. The node submits a selection of their best signatures from that period. The network can judge the signature capability of this node by using the median of the results, and can judge the luck using the standard deviation of the results. This requires some (minor) extra computation for the judges, but at the benefit of a more reliable measure of signature capability.
Implementation
I tested the function maidsafe/rust_sodium/sign_detached, and the technique described above works reliably.
In the table, difficulty is the number of leading zeros in the binary representation of the signature value. To pass the test, the binary signature value must have at least that many leading zeros.
Difficulty Iterations To Pass | Median
2 2 3 2 2 3 | 2
3 21 8 11 15 3 | 11
4 22 18 17 67 25 | 22
5 72 40 42 82 34 | 42
6 80 54 145 100 45 | 80
7 121 221 183 178 157 | 178
8 175 311 430 208 178 | 208
9 472 723 980 669 1797 | 723
10 544 3096 1019 1312 1918 | 1312
11 663 4293 3221 1993 4680 | 3221
12 3973 5868 10799 13643 9797 | 9797
13 13117 10803 29997 40337 11552 | 13117
14 20430 20980 34774 42612 14627 | 20980