Proposal for oDAO duty 'committees'

@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))
    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.


Proposal 2 inspired by @Valdorff and pseudo coded up after a lot of consternation about how to deal with dynamic sizes of both the odao and duties vectors.

Since we need ceii(len(odao_nodes) / 2) or len(odao_nodes) / 2 + 1 if the number of odao nodes is odd and even respectively, we can form committees by bucketing odao nodes into 2 groups, and selecting 1-2 nodes that simply perform both duties.

That would look something like this:

#!/usr/bin/env python3

def left_of(array, idx, count):
    c = 0
    while abs(c) < count:
        c -= 1
        yield array[idx + c]

def right_of(array, idx, count):
    c = 0
    while abs(c) < count:
        c += 1
        yield array[idx + c]

def get_groups(node_ids, block):
    # Assume duties occure every 1024 blocks
    duty_index = block // 1024
    n_nodes = len(node_ids)

    idx = duty_index % n_nodes
    extra_duty_nodes = None
    group_a = None
    group_b = None
    if n_nodes % 2 == 1:
        # When an odd number of nodes exist, One node will always do each duty.
        # Round-robin to select it.
        extra_duty_nodes = set(node_ids[idx:idx+1])
        # Treat the node_ids list as a ring buffer.
        # Add nodes from the left side of the extra duty node until the set has half
        group_a = set(left_of(node_ids, idx, n_nodes // 2))
        # and group a is the other half (from the right)
        group_b = set(right_of(node_ids, idx, n_nodes // 2))
        # When an even number of nodes exist, form two even groups
        # and round-robin each group for cross-duty performance
        group_a, group_b = node_ids[::2], node_ids[1::2]
        extra_duty_nodes = set([group_a[idx % (n_nodes // 2)], group_b[idx % (n_nodes // 2)]])
        group_a, group_b = set(group_a), set(group_b)

    # Make sure the unlucky extra duty node(s) appear(s) in both groups
    group_a = group_a.union(extra_duty_nodes)
    group_b = group_b.union(extra_duty_nodes)

    # Finally, we flip the order depending on the parity of the duty index,
    # so all nodes perform all duties over time
    if duty_index % 2 == 0:
        group_a, group_b = group_b, group_a
    return sorted(list(group_a)), sorted(list(group_b))

# Order must be preserved across watchtower processes, so make it alphabetic
duties = sorted(["submit_balances", "submit_prices", "i_am_a_teapot"])

def get_committees(node_ids, block):

    group_0, group_1 = get_groups(node_ids, block)

    out = {}
    for i in range(0, len(duties)):
        if i % 2 == 0:
            out[duties[i]] = group_0
            out[duties[i]] = group_1
    return out

# Odd number of odao nodes exists
odao_node_ids = sorted([b"0x1111", b"0x2222", b"0x3333", b"0x4444", b"0x5555", b"0x6666", b"0x7777"])
print(get_committees(odao_node_ids, 0))
print(get_committees(odao_node_ids, 1024))
print(get_committees(odao_node_ids, 1024*2))
print(get_committees(odao_node_ids, 1024*3))

# Even number of odao nodes exists
odao_node_ids = sorted([b"0x1111", b"0x2222", b"0x3333", b"0x4444", b"0x5555", b"0x6666", b"0x7777", b"0x8888"])
print(get_committees(odao_node_ids, 0))
print(get_committees(odao_node_ids, 1024))
print(get_committees(odao_node_ids, 1024*2))
print(get_committees(odao_node_ids, 1024*3))

Which produces the following output for odd number of odao instances:

{'i_am_a_teapot': [b'0x1111', b'0x2222', b'0x3333', b'0x4444'], 'submit_balances': [b'0x1111', b'0x5555', b'0x6666', b'0x7777'], 'submit_prices': [b'0x1111', b'0x2222', b'0x3333', b'0x4444']}
{'i_am_a_teapot': [b'0x1111', b'0x2222', b'0x6666', b'0x7777'], 'submit_balances': [b'0x2222', b'0x3333', b'0x4444', b'0x5555'], 'submit_prices': [b'0x1111', b'0x2222', b'0x6666', b'0x7777']}
{'i_am_a_teapot': [b'0x3333', b'0x4444', b'0x5555', b'0x6666'], 'submit_balances': [b'0x1111', b'0x2222', b'0x3333', b'0x7777'], 'submit_prices': [b'0x3333', b'0x4444', b'0x5555', b'0x6666']}
{'i_am_a_teapot': [b'0x1111', b'0x2222', b'0x3333', b'0x4444'], 'submit_balances': [b'0x4444', b'0x5555', b'0x6666', b'0x7777'], 'submit_prices': [b'0x1111', b'0x2222', b'0x3333', b'0x4444']}

As you can see, for the first set of duties, node 0x1111 performs everything; for the second, node 0x2222 performs everything; and so on.
Additionally, for the first set of duties, the 3 nodes immediately following 0x1111 perform the first and last duties, and the 3 nodes immediately before 0x1111 perform the second duty.
For the second set of duties, the same holds true, but for the nodes before and after 0x2222, however, now the first and third set of duties fall to the 3 nodes immediately before 0x2222, and so on.

For an even number of nodes, this is simpler:

{'i_am_a_teapot': [b'0x1111', b'0x2222', b'0x4444', b'0x6666', b'0x8888'], 'submit_balances': [b'0x1111', b'0x2222', b'0x3333', b'0x5555', b'0x7777'], 'submit_prices': [b'0x1111', b'0x2222', b'0x4444', b'0x6666', b'0x8888']}
{'i_am_a_teapot': [b'0x1111', b'0x3333', b'0x4444', b'0x5555', b'0x7777'], 'submit_balances': [b'0x2222', b'0x3333', b'0x4444', b'0x6666', b'0x8888'], 'submit_prices': [b'0x1111', b'0x3333', b'0x4444', b'0x5555', b'0x7777']}
{'i_am_a_teapot': [b'0x2222', b'0x4444', b'0x5555', b'0x6666', b'0x8888'], 'submit_balances': [b'0x1111', b'0x3333', b'0x5555', b'0x6666', b'0x7777'], 'submit_prices': [b'0x2222', b'0x4444', b'0x5555', b'0x6666', b'0x8888']}
{'i_am_a_teapot': [b'0x1111', b'0x3333', b'0x5555', b'0x7777', b'0x8888'], 'submit_balances': [b'0x2222', b'0x4444', b'0x6666', b'0x7777', b'0x8888'], 'submit_prices': [b'0x1111', b'0x3333', b'0x5555', b'0x7777', b'0x8888']}

The nodes are split into two groups. One node is selected from each group to also appear in the other group.

The split here is parity, so the first group is all evens, and the second group is all odds, aside from the nodes selected to form a majority by joining all groups.

Again, each duty interval, the duties flip flop, so all nodes perform all duties.

The advantage to this approach over the last approach is that all odao nodes perform at least 1 duty every N blocks, while maintaining fairness.

In the case of a node not performing its duty, all the nodes who haven’t already performed that duty would race to step in.


I, and by extension CryptoManufaktur, support this idea. This is a helpful sanity check on node liveness, and also creates a form of community oversight of oDAO nodes being able to perform their duties.

1 Like

I support this and other measures to improve oDAO accountability.


I, and therefore Sigma Prime, also support this initiative.

It’s important to maintain liveness and any steps to ensure this is the case for the ODAO membership, we support.