Signature Proofs


#1

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

#2

Nice one @mav Just a quick note though. With node ageing and the secure name implementation this starts to kick in a litle. In those cases the new group will ask a node to create a key between two existing nodes (the nodes with the greatest distance between them in the group). It’s not intended to be a proof of work, but just fyi


#3