@poupas has mentioned this in passing, and @knoshua has referenced it a few times, so I figured i’d write up my recommendation for ‘sampling’ oDAO nodes to ensure that we can tell if they’re online.
There’s a way to monitor liveness without any contract changes.
The algorithm I favor is called Highest Random Weight or Rendezvous Hashing.
The algorithm is fairly simple.
Assume h is a hash function which returns a decimal value uniformly distributed over [0,1].
Let odao_node_ids be a list of oDAO node addresses.
ranking = map(lambda x: (h(x + block_number), x), odao_node_ids)
committee_size = ceil(0.51 * len(ranking))
committee = sorted(ranking)[0:committee_size]
This gives you a consistent committee, which is easily calculated on all oDAO instances and guaranteed to be the same for a given set of oDAO nodes and given block_number.
Conveniently, if a member of the committee fails to perform their duty, you know who the “fallbacks” are, as committee[committee_size:] is a similarly ordered list.
Contrived example:
#!/usr/bin/env python3
import hashlib
import math
def h(block_id, node_id):
out = hashlib.md5(block_id + node_id)
lowbytes = out.digest()[-2:]
score = int.from_bytes(lowbytes, "little", signed=False)
return score / 65535.0
odao_node_ids = [b"0x1111", b"0x2222", b"0x3333", b"0x4444", b"0x5555", b"0x6666"]
def get_committees(block_id, node_ids):
ranking = list(map(lambda x: (h(block_id, x), x), node_ids))
committee_size = math.ceil(0.51 * len(ranking))
ranking.sort()
return ranking[0:committee_size], ranking[committee_size:]
committee_one, fallback_one = get_committees(b'6446', odao_node_ids)
print("Committee one", ", ".join(map(lambda x: str(x[1]), committee_one)))
print("Fallback order one", ", ".join(map(lambda x:str(x[1]), fallback_one)))
committee_two, fallback_two = get_committees(b'6500', odao_node_ids)
print("Committee two", ", ".join(map(lambda x: str(x[1]), committee_two)))
print("Fallback order two", ", ".join(map(lambda x:str(x[1]), fallback_two)))
This code yields the following output:
Committee one b'0x6666', b'0x4444', b'0x5555', b'0x1111'
Fallback order one b'0x2222', b'0x3333'
Committee two b'0x6666', b'0x3333', b'0x1111', b'0x5555'
Fallback order two b'0x2222', b'0x4444'
As you can see, two deterministic but random committees were formed.
Looking at the first, nodes 1, 5, 4, and 6 are expected to submit by some deadline. If one or more fails, nodes 2 and 3 will respectively fill in (waterfalling the responsibility- ie, if node 4 fails, node 2 will fill in after X blocks have passed, and node 3 will fill in if node 2 has not after another X blocks have passed).
Given this algorithm, anyone can look at who submitted duties for a given block and determine what the committees were a posteriori, allowing us to monitor which nodes have failed their assigned duties. I wouldn’t go as far as to say that we can use this to assess penalties, given that a race condition exists: fluctuating gas prices and inconsistent gas oracles can lead a duty to not be included, even after being performed… though this will also be detectable, so maybe that’s ok.