Table of Contents
Abstract

The Keep Network requires a trusted source of randomness for the process of trustless group election. While the network requires that randomness to function correctly, the source of randomness is itself broadly applicable. This trusted source of randomness takes the form of a BLS Threshold Relay. We discuss implementation of this random beacon, including assumptions and mitigations for bad actors and poor network connectivity.

Overview

The threshold relay described herein is a way of generating verifiable randomness that is resistant to bad actors both in the relay network and on the anchoring blockchain, assumed here to be Ethereum. The basic functioning of the relay (further details are in the section on System Details) is:

  • Some number of groups exist in the relay.

  • An arbitrary seed value vs counts as the first entry in the relay.[1]

  • A request ri is dispatched to the chain for a new entry.

  • The previous entry vs is used to choose a group to produce the response to the request.

  • vs is signed by at least a subset of the chosen group members, and the resulting signature is the entry generated in response to the request. It is published to the anchoring blockchain as the entry vi.

  • The new entry vi may trigger the formation of a new group from the set of all members in the relay.

  • A group expires after a certain amount of time.

The following sections will detail how this basic function is implemented in practice, including notes on Prior Work that motivated this design, the [Incentive Structures] used to economically incentivize good behavior by network participants, [Core Technologies] used in the network, and finally the System Details that outline the implementation itself. [Upgrade Management] is also discussed.

Prior Work

Dfinity has described their implementation of a random beacon backed by a threshold relay in their consensus whitepaper [2]. The relay described in this paper is heavily based on the one devised by the Dfinity team, with certain adjustments for implementation on an existing blockchain. The key distinction between the Dfinity implementation and the Keep implementation is that Keep has to contend with blockchains that do not implement the same primitives as the in-house Dfinity chain targeted in their paper. Concerns such as transaction costs and payment for beacon entries are therefore a core part of the incentive system built around the Keep random beacon.

As described in the above paper, at the heart of the relay beacon is the signature scheme described by Dan Boneh, Ben Lynn, and Hovav Shacham in [3], termed BLS. Three properties of the scheme are of particular use in this case: BLS signatures can be used in threshold mode, where k of n participants are sufficient to produce a combined signature; BLS threshold signatures produce the same final signature irrespective of the participants; and BLS signatures are typically shorter than those of many other threshold signature schemes.

Finally, underpinning the process of generating new groups for BLS threshold signatures in the system is a distributed key generation algorithm based on work by Gennaro, Jarecki, Krawczyk, and Rabin [4], as also described in the Dfinity paper above. The Keep Random Beacon publishes group public keys to the anchoring blockchain and does member selection on-chain, but key generation occurs between nodes with only the final result vote occurring on-chain.

Incentive Structure

The system generates verifiable random numbers using threshold signatures. BLS threshold signatures are deterministic, so a given signing group can only produce one valid signature for any given input. A party that knows the private key of a signing group can calculate signatures in advance, and generated entries can be influenced by preventing the selected group from producing a signature and thus forcing the beacon to select a different group.

To incentivize participants, every member of a group that produces a valid entry is rewarded. Participants that perform costly but necessary actions are reimbursed for the costs and further rewarded.

Each participant is required to stake a number of tokens that are held as collateral against misbehavior. Participants staking a greater number of tokens have a correspondingly greater opportunity to earn rewards. In the event that a group fails to produce a signature when requested or its private key is provably abused, each member of the group is punished by slashing their stake; taking away some or all of their staked tokens.

In some cases, misbehavior is proven with the help of a third party "tattletale" who notifies the beacon of the misbehavior, and if necessary, provides the required proof. If the misbehavior occurred as claimed, the tattletale is rewarded with a fraction of the slashed tokens.

System Details

The system has two high-level modes of operation, discussed in detail in their individual sections:

  • Group formation, consisting of group member selection and distributed key generation.

  • Threshold signing, triggered by a beacon request and producing a new entry in the relay (which in turn also triggers the formation of a new group). signing also involves selecting the appropriate price for a new relay entry.

Additionally, the beacon makes money by charging for beacon requests. An early draft of the pricing mechanism is described in its own section.

Group formation

Random Beacon Group Selection

The group selection protocol is intended to be an interactive method of selecting candidate group P from the set of all stakers S given a pseudorandom seed value Vi.

Functional interface:

inputs: S, Vi

output: P

The protocol should:

  1. produce a representative result, where each staker’s profit is proportional to the number of tokens they have staked

  2. produce a group P of constant size N

  3. not require an excessive amount of on-chain operations to perform

  4. not be feasible for an adversary to manipulate

Table 1. Some terms
Term Meaning

Trenchcoating

Several actors pooling up their stakes under one staker identity to take advantage of rich-get-richer effects. Thus what seems to be a large staker is actually "a hundred small stakers in a trenchcoat".

Blitzpantsing

The inverse of trenchcoating; a single token holder dividing their stake under multiple identities to avoid rich-get-poorer effects or to increase their representation in groups. This can increase profits above what is designed, or make certain attacks easier to perform by making one actor more likely to control a group. Thus what seems to be a large number of small stakers is actually a single whale in an "inverse trenchcoat", or "blitzpants".

Non-interactive

A protocol is non-interactive if it can be performed without stakers providing additional information. Specifically, Si can determine whether they are in P without input from other stakers in S.

Interactive

An interactive protocol requires stakers to provide additional information over what is available on-chain, and then performs a deterministic algorithm to select a group based on the information provided by the stakers. In an interactive protocol Si cannot know for sure whether they are in P before they receive the other stakers' input.

Actual staker

An actor holding and staking at least MINIMUM_STAKE tokens, represented as Si. Each actual staker corresponds to one or more virtual stakers. An actual staker can be represented multiple times in a candidate group, through multiple virtual stakers. The surplus tokens above n * MINIMUM_STAKE (for an integer n) do not impact the actual staker’s ability to create virtual stakers.

Virtual staker

A construct used to simplify the mathematical requirements of the group selection protocol and ensure blitzpantsing provides no advantage.

Each virtual staker represents exactly MINIMUM_STAKE tokens staked by some actual staker who may or may not be anonymous. A virtual staker may only ever be included once in a candidate group, and N properly denotes the number of virtual stakers in P.

Ticket

A message containing a pseudorandomly generated value Wk which is used to determine whether a given virtual staker is eligible for the group P (the lowest N tickets will be chosen) and a proof of the validity of the value

Threshold

The value of the highest-valued ticket in P

Spacetickets

Is a space consisting of all possible tickets. It is strongly related with a pseudorandom function that is used for ticket generation. Currently the Spacetickets is equal to 264- 1, which is due to selection of the first 8 bytes of keccak256 as our pseudorandom function.

Supplytokens

Is the total number of tokens which are going to be supplied during the project lifetime and is set to 10^9.

Natural threshold

Thresholdnat = floor(N * Spacetickets / (Supplytokens / MINIMUM_STAKE))

In other words, the natural threshold is the value N virtual stakers' tickets would be expected to fall below if the tokens were optimally staked, and the tickets' values were evenly distributed in the domain of the pseudorandom function.

Usually ThresholdP > Thresholdnat as not all tokens will be staked and the distribution of stakes will not be optimal.

Setup

When a staker Sj is created, the following values are determined:

  • Stakej: the amount of tokens staked by Sj and thus locked up until the staker is destroyed

  • Weightj= floor(Stakej / MINIMUM_STAKE): the staking weight of Sj; how many virtual stakers can represent Sj

  • Addressj: the operator address of Sj

Protocol

A new output Vi is generated by the random beacon. This triggers the selection of a new candidate group.

Phase 1: ticket calculation

Sj calculates Ticketk = (valuek, vs, Addressj) where:

  • the ticket value is calculated as valuek = prf(Vi, Addressj, vs)

  • the virtual staker number vs is within the range 1 ⇐ vs ⇐ Weightj

  • the staker weight Weightj is correct for the operator address Addressj

Phase 2: ticket submission
Phase 2a: initial ticket submission

Each staker whose valuek < Thresholdnat on one or more Ticketk publishes the ticket/s.

The operator contract checks the validity of each submitted ticket by querying the staking contract for the stake available to the operator in the ticket, calculating the corresponding staker weight, checking that the virtual staker index vs is within the allowed bounds, and verifying that valuek is correct. Invalid tickets are rejected.

Phase 2a ends when TICKET_INITIAL_TIMEOUT is reached.

Phase 2b: reactive ticket submission

If the number of tickets received in phase 2a is less than N, the stakers whose tickets did not fall below the natural threshold will publish theirs.

Tickets should ideally be published in order, to reduce the costs of ticket submission on the stakers. For this, it is recommended that tickets where Wk = x * Thresholdnat be submitted at time x * TICKET_INITIAL_TIMEOUT, IFF the number of tickets below Wk is less than N.

When tickets are published in order, the number of unnecessary transactions can be minimized, which benefits the stakers. Thus it would be in each staker’s interests to follow the regular order. This, however, is only a recommendation and tickets submitted at different times should not be rejected.

Phase 2b ends when TICKET_SUBMISSION_TIMEOUT is reached.

Phase 3: threshold determination

After all potentially eligible tickets have been submitted, the N tickets with the lowest values for valuek will be selected into the group P. The corresponding virtual stakers will be automatically assigned to form the group and no further interaction is necessary. DKG will be performed.

Notes and rationale:
Virtual stakers

Due to the use of virtual stakers, the stakers will be expected to be represented in P with a probability proportional to their Weightj; a staker staking at least 2 * MINIMUM_STAKE may also be selected multiple times for the same group.

This makes the result representative and ensures that neither blitzpantsing nor trenchcoating will provide the staker greater profits than they could acquire otherwise (requirement 1), with the exception that pooling token amounts below MINIMUM_STAKE and sharing the risk and profits would enable the utilization of smaller holders' tokens or surplus tokens from regular stakers. This form of trenchcoating is arguably either neutral or beneficial, and in any case it does not violate proportionality of rewards.

Interactive protocol

There would be two simple non-interactive options but neither is able to satisfy all of the requirements:

  1. One method would be to have each Sj calculate a pseudorandom value Seedj, and then everybody whose Seedj < Thresholdi is in P. Thresholdi would be calculated using public information, eg. by Thresholdi = floor(N * Spacetickets / |S|) for a 256-bit Seedj. However, this means that due to random chance, most of the time |P| != N. This violates requirement 2.

  2. Alternatively each staker could present some kind of a hashed value Hashj so that whether Sj is in P can be determined publicly by f(Vi, Hashj, S, N) → Bool. This cannot work, because then anybody could calculate f(Vm, Hashj, S, N) for a large number of different values Vm and see how often Sj ends up eligible for the candidate group. Due to requirement 1 this necessarily reveals how much Sj has staked to an arbitrary degree of precision, violating requirement 5.

These constraints seem inherent in the problem, and thus an interactive protocol appears necessary. The aforementioned issues can be avoided by having Sj calculate a value Wj, so that Sj will be in P if ThresholdP > Wj.

all_tickets = []
for S_j in S:
    for vs in [1..Weight_j]:
        W_k = prf(V_i, Q_j, vs)
        all_tickets.append(Ticket(W_k, proof(W_k))

Threshold_P = max(all_tickets.map(fn(t): t.W_k).sort().take(N)

Assuming once again 256-bit values for Wk and ThresholdP, Sj can predict their expected probability of being in P by calculating how likely it would be that ThresholdP > Wk. Then Sj can broadcast their input only if there seems to be a realistic chance that they could be selected. If it seems likely that ThresholdP < Wk, Sj can refrain from broadcasting Wk and only monitor the situation, reacting if it seems that few stakers' ticket values are falling under the estimated threshold.

Alternative off-chain protocol

This protocol was not chosen but is included in the yellowpaper to illustrate reasoning and what alternatives were considered

Protocol

Each staker calculates their tickets

Each staker who has one or more ticket/s that may be eligible for the group broadcasts the ticket, including proof of its validity

Other stakers check broadcasted tickets for validity; if an invalid ticket is broadcast, the ticket is rejected

After Tselection has elapsed, stakers following the broadcast channel select N tickets with the lowest value to form the candidate group

Each member of the candidate group BLS-signs a message containing all the tickets of the group and the threshold

This is the Group Formation Message, signed by [P1..PN] to ensure the integrity of the group selection process. Because all participants are required to sign the Group Formation Message, the group composition cannot be manipulated later.

The members of P perform DKG; at the end of DKG the final message contains:

  • DKG output, similarly BLS signed

  • group formation message

  • aggregate BLS signature of the above

On-chain receives DKG conclusion message, and:

  • checks that all stakers in the group formation message are valid

  • checks the proofs supplied in the tickets

  • checks that all tickets are below the threshold

  • checks that the group formation message is signed by everyone in P and that the DKG output is signed by at least H members of P

If two or more valid group formations are presented, the one with the lowest threshold wins

Any virtual staker is only permitted to sign a group formation message for one group (any given ticket may only be used for one group); if a ticket is used for two or more different groups, the staker should be penalized

Submitting only a group formation message without DKG conclusion is also valid and signifies that the group was formed, but DKG did not reach quorum (H participants would not agree on any given result)

However, if a group formation message is published it may be superseded by a valid DKG conclusion message for the same group

If a member of group P with ThresholdP publishes a valid group formation message, and a member of group P' with ThresholdP' publishes a valid group formation and DKG conclusion message:

  • if P ∩ P' != {}, the stakers who signed both group formation messages should be penalized, but the groups P and P' may still be valid (this is to prevent an attack where one member of an unfavorable group prevents the group creation by signing and publishing a different, unrelated group creation message)

  • if ThresholdP > ThresholdP', group P' is to be considered the correct group and the group selection is to be deemed a success.

  • if ThresholdP < ThresholdP', group P is to be considered the correct group and the group selection is to be deemed a failure.

  • if ThresholdP = ThresholdP', group P' is to be considered the correct group

Notes

The off-chain protocol is much more complex to secure effectively, and a variety of attacks on the group composition need to be addressed.

Random Beacon Distributed Key Generation

This proposal for Distributed Key Generation for the threshold relay is based on a protocol by Gennaro, Jarecki, Krawczyk and Rabin [GJKR]. GJKR is further based on Pedersen-VSS (verifiable secret sharing) [Ped]. For this implementation, GJKR has been modified to make protocol violations objectively attributable and remove the need for one-to-one messaging channels.

The protocol uses ephemeral ECDH keys to encrypt one-to-one communication on the broadcast channel. This ensures that participants can neither make baseless complaints nor cause a minor nuisance with subtle misbehavior.

Additionally, the threshold relay public key submission protocol is defined.

Terms used in distributed key generation (DKG)
Time limits
Tp

Time limit for phase p of the key generation; after Tp has elapsed every non-inactive participant is assumed to have broadcast its own message for phase p and received others' messages

TDKG

Time limit for the distributed key generation to finish and P1 to submit the result

TSTEP

Time limit after which the next participant in queue becomes eligible to submit the result

TVOTING

Time limit after which any disputes over the correct result are assumed to be resolved, with the plurality being honest

TRESPONSE

Extension to the time limit after a new vote has been submitted, to ensure honest members are able to react to last-minute votes.

Rewards and punishments
RDKG_SUBMIT

Reward for the member submitting the finally accepted result

DDKG_MISSED_SUBMISSION

Penalty for all members P1 .. Pi-1 who failed to submit the result before Pi, if i > 1

DDKG_DQ

Penalty for members on the disqualified list

Values at the time of group creation
Vi

ith output of the random beacon

S

The set of all stakers at the time of Vi

P

The candidate group of players selected from S with Vi, who will try to perform the key generation to create signing group G

Pj

j-th node in P based on the group candidate selection algorithm

Values in the DKG protocol
IAp

The set of nodes in P that first failed to broadcast a required message within a specified time limit in phase p and were thus added to the set of inactive nodes after that phase

IA

IA1 + IA2 + …​

The set of inactive nodes in P (nodes that failed to broadcast a required message within a specified time limit during the DKG)

DQp

The set of nodes in P that were disqualified in phase p for provably and attributably violating the protocol

DQ

DQ1 + DQ2 + …​

The set of all disqualified nodes in P

Gp

Gp-1 - IAp-1 - DQp-1

The set of nodes in P that were active and well-behaved at the beginning of phase p (G1= P)

G

P - IA - DQ

The successfully created group after removal of inactive and misbehaving nodes

Keys
Xi

Long-term ECDSA private key of Pi

Yi

Long-term ECDSA public key of Pi

xij

Ephemeral ECDH private key of Pi for the purpose of encrypted communication with Pj

yij

Ephemeral ECDH public key of Pi for the purpose of encrypted communication with Pj

kij = kji

ECDH(xij, yij)

Symmetric key generated by Pi for encrypting and decrypting communications with Pj

X

X = Σ zi

The (virtual) private key corresponding to the group G'

Y

Y = X * P1

The public key corresponding to the group G'

zi

zi = ai0

Piece of the group private key X generated by Pi

yi

yi = zi * P1 = Ai0

Piece of Pi of the group public key Y

xi

xi = Σ sji

The individual private key of Pi corresponding to a share of X at i

gxi

gxi = xi * P1 = Σ (sji * P1)

The individual public key of Pi corresponding to a share of Y at i

Details+Rationale
Message delivery
Broadcast channel

Every group member in phase p can safely assume every non-inactive group member has seen all messages broadcast within Tp after the beginning of phase p.

All messages broadcast by Pi are assumed to be signed with Xi.

A message is malformed if it cannot be parsed and validated as the message required in a particular phase of the protocol.

The implementation details of the broadcast channel are currently out of scope for this document.

Assumptions and implications

The broadcast channel is assumed to give all participants the same view of the world, and deliver all messages from non-inactive participants within a time that is less than the applicable time limit for each phase.

If these assumptions don’t hold, certain attacks become possible. For example, if a message from Pi reaches honest participant Pj but not Pk, their sets of inactive participants IAPj and IAPk will differ. This will make them vote for different results, which will prevent quorum from being reached on full signing, while on escalating votes a coordinating adversary could make its preferred incorrect result win the vote. To protect against the latter, escalating votes assumes a null result when any single result is opposed by fmax + 1 participants as it means that the honest votes are split.

Result format

The result of the DKG protocol can be either a success or a failure.

Success means the DKG protocol finished with at most Mfail participants misbehaving or dropping offline during the execution of the protocol, and the group of the remaining honest participants G should be added to the signing groups for the threshold relay.

Failure means that the group creation could not finish, due to either the number of (inactive + disqualified) participants exceeding Mfail, or the presented results being disputed in a way where the correct outcome cannot be ascertained.

Overview

Input: Vi, S

Output: one of

  • Successfully generated group P including

    • public key Y of P

    • lists of absent and disqualified nodes IA and DQ

  • Failure to generate a valid group including

    • list of disqualified nodes DQ

The group generation protocol selects a new candidate group P from S and runs a distributed key generation (DKG) protocol to create a threshold signature public key Y for the group, to be used in the random beacon.

After a successful execution of the protocol, P will be the group of nodes that may participate in the random beacon signing, having been neither inactive or misbehaving during the DKG.

Inactive nodes will be removed from P and not be eligible for the rewards from participating in the random beacon by contributing to the signature Vj should P be chosen as the group to produce the jth random number from the beacon.

Disqualified nodes will be removed from P and their stake will be slashed in punishment for provably and attributably acting in breach of the DKG protocol.

Protocol

Phases are seen from the perspective of Pi

After phase p, the nodes that failed to broadcast a required message will be added to IAp. Nodes that broadcast a malformed message may be added to IAp or DQp.

Phase 1. Ephemeral key generation

To ensure integrity in later parts of the DKG protocol, we will require every Pi to generate an ephemeral ECDH keypair (xij, yij) for every other member Pj in P. These will be broadcast in phase 1.

Registering the ephemeral keys on-chain is not required if the broadcast channel assumption holds, and all honest participants agree on the keys published by each participant in phase 1.

Phase 1
# Because G1 and G2 in alt_bn128 are cyclic groups of prime order, this number
# can also be used as the size of the secret sharing finite field
q = G1.curveOrder

# Receive the DKG parameters from on-chain
dkgSetup = getDkgSetup()

# Presented from the perspective of P_i
i = dkgSetup.members.index(self.pubkey)

# Keep track of other qualified participants
#
# `goodParticipants[P]` denotes the qualified participants in phase `P`
#
goodParticipants[1] = [1..N]

# Record the blockheight at the start of the DKG
#
# Used later for calculating timeouts
#
T_dkgInit = getCurrentBlockHeight()

ephemeralPubkeys = []

for j in goodParticipants[1], j != i:
    x_ij = genEcdhKeypair()

    self.ephemeralKey[j] = x_ij

    y_ij = x_ij.pubkey

    ephemeralPubkeys[j] = y_ij

broadcast(messagePhase1(ephemeralPubkeys))
Phase 2. Ephemeral ECDH

Every node in P has now published a valid list of ephemeral ECDH pubkeys. Pi will perform ECDH with every Pj in P to create kij.

Phase 2
# Receive messages from phase 1:
# - ephemeral public keys of other participants
#     IA if message not received
#
# Validate:
# - message from P_j must contain a public key for all P_k, k != j
#     DQ if public key absent
# - all public keys must be valid curve points of the ECDH curve
#     DQ if invalid
#
messages.receive(1)

for j in goodParticipants[2], j != i:
    privkey_ij = self.ephemeralKey[j]
    pubkey_ji = ephemeralPubkey(j, i)

    k_ij = ecdh(privkey_ij, pubkey_ji)
    self.symkey[j] = k_ij
Utility functions
# Fetch the correct ephemeral pubkey from messages broadcast in phase 1
#
# The format for the message of `P_j` in phase `P` is: `messages[P][j]`
#
def ephemeralPubkey(senderIndex, recipientIndex):
    return messages[1][senderIndex].pubkey[recipientIndex]
Phase 3. Polynomial generation

Every node in G3 has, for every other node in G3, a symmetric key that can be used for encrypted and attributable communications over the broadcast channel. The Pedersen-VSS phase of the GJKR DKG algorithm can commence.

Create two polynomials fi(z) and gi(z) of degree M and calculate other players' shares as points on these polynomials. Additionally, calculate Pedersen commitments to the coefficients of fi(z) using the coefficients of gi(z).

Shares to Pj are encrypted with the symmetric key Kij = Kji shared by Pi and Pj. Commitments and encrypted shares are broadcast to other players.

Phase 3
# GJKR 1.(a):
#  f_i(z) = a_i0 + a_i1 * z + ... + a_it * z^t
#  f'_i(z) = b_i0 + b_i1 * z + ... + b_it * z^t
#
# a_ij = sharePolyCoeffs[j]
# b_ij = blindingFactors[j]
#
# G1.randomScalar = integer from range(0, q)
#
self.sharePolyCoeffs = [0..M].map(G1.randomScalar)
self.blindingFactors = [0..M].map(G1.randomScalar)


def f_i(z):
    return evaluateAt(z, self.sharePolyCoeffs) % q


def g_i(z):
    return evaluateAt(z, self.blindingFactors) % q


z_i = self.sharePolyCoeffs[0]
# assert(z_i == f_i(0))


self.commitments = map(ecCommit, self.sharePolyCoeffs, self.blindingFactors)

encryptedShares = []

for j in goodParticipants[3]:
    s_ij = f_i(j)
    t_ij = g_i(j)

    if i != j:
        pointsBytes = marshalPoints(s_ij, t_ij)
        payload_ij = encrypt(self.symkey[j], pointsBytes)

        encryptedShares[j] = payload_ij
    else:
        self.shares[i] = (s_ij, t_ij)

broadcast(messagePhase3(encryptedShares, self.commitments))
Utility functions
# Evaluate a polynomial given by `coeffs` at point `z`
#
# `coeffs` is little-endian; `ax^2 + bx + c` is expressed as `[c, b, a]`
#
# `evaluateAt(2, [6, 3, 4]) = 6 + (3 * 2^1) + (4 * 2^2) = 28`
#
def evaluateAt(z, coeffs):
    return sum(
        [ coeffs[k] * z^k for k in [0..M] ]
    )


# Pedersen commitment to secret value `s` and blinding factor `t`
# `G = P1` is the standard generator of the elliptic curve
# `H = G*a` is a custom generator where `a` is unknown
#
# C(s, t) = G*s + H*t
#
def ecCommit(s, t):
    Gs = P1.scalarMult(s)
    Ht = H.scalarMult(t)
    return ecAdd(Gs, Ht)
Phase 4: Share verification

Receive, decrypt and validate shares from other participants. If any share proves inconsistent with the sender’s published commitments, broadcast a complaint by publishing the identity of the misbehaving party along with the corresponding ephemeral private key so others can check the result.

Phase 4
# Receive messages from phase 3:
# - commitments to the secret sharing polynomials
# - encrypted share payloads
#     IA if message not present
#
# Validate:
# - the expected number of commitments (M + 1) is present
#     DQ if n of commitments incorrect
# - commitments must be valid curve points of G1
#     DQ if a commitment is not valid curve point
# - message from P_j must contain encrypted payloads for all other participants
#     DQ if payload absent
# - the length of each payload must be: 2 * G1_SCALAR_LENGTH + MAC_LENGTH
#     DQ if a payload has incorrect length
#
messages.receive(3)

shareComplaints = []

for j in goodParticipants[4], j != i:
    k_ij = self.symkey[j]

    validShares = decryptAndValidateShares(
        senderIndex = j,
        recipientIndex = i,
        symkey = k_ij
     )

    if not validShares:
        X_ij = self.ephemeralKey[j]
        shareComplaints.append(shareComplaint(j, X_ij))
    else:
        (s_ji, t_ji) = validShares
        self.shares[j] = (s_ji, t_ji)

broadcast(messagePhase4(shareComplaints))
Utility functions
# Calculate the sum of a list of elliptic curve points
def ecSum(points):
    return reduce(ecAdd, points)


# Fetch the correct encrypted shares from messages broadcast in phase 3
def encryptedShares(senderIndex, recipientIndex):
    return messages[3][senderIndex].encryptedShares[recipientIndex]


# Fetch a specific participant's commitments from messages broadcast in phase 3
def commitments(senderIndex):
    return messages[3][senderIndex].commitments


# Fetch the correct shares and try to decrypt them with the provided key
def decryptShares(
    senderIndex,
    recipientIndex,
    symkey
):
    payload = encryptedShares(senderIndex, recipientIndex)

    return decrypt(payload, symkey)


# Fetch the shares and validate them
#
# Check that shares decrypt correctly and are consistent with the sender's
# published commitments
#
def decryptAndValidateShares(
    senderIndex,
    recipientIndex,
    symkey
):
    plaintext = decryptShares(
        senderIndex,
        recipientIndex,
        symkey
    )

    if not plaintext:
        return False
    else:
        (share_S, share_T) = unmarshalPoints(plaintext)

        sharesValid = checkShareConsistency(
            senderIndex,
            recipientIndex,
            share_S,
            share_T
        )

        if sharesValid:
            return (share_S, share_T)
        else:
            return False


# Check that equation 2 from GJKR holds for `share_S, share_T`
#
# P_i is the player whose shares are validated
# P_j is the perspective player performing the validation
#
# GJKR 1.(b):
#
#   g^s_ij * h^t_ij == product([ C_ik ^ (j^k) for k in [0..T] ]) % p
#
def checkShareConsistency(
    recipientIndex,
    senderIndex,
    share_S,
    share_T
):
    i = senderIndex
    j = recipientIndex

    C_i = commitments(i)

    C_ecSum = ecSum(
        [ C_i[k].scalarMult(j^k) for k in [0..M] ]
    )

    sharesValid = ecCommit(share_S, share_T) == C_ecSum
    return sharesValid
Phase 5: Share complaint resolution

If anyone has complaints about another player, use the published private keys to decrypt transmitted messages and determine fault.

As every message in the broadcast channel is signed, decrypting previous messages makes misbehavior attributable. For every complaint, one party will be disqualified: either the accused sent invalid shares, or the accuser made a false complaint.

Phase 5
# Receive messages from phase 4:
# - complaints about inconsistent shares, or "no complaints"
#     IA if not present
#
# Validate:
# - each revealed private key must be a valid scalar for ECDH
#     DQ if invalid
# - each revealed private key must correspond to the public key
#     DQ if does not match
#     (explicit in pseudocode)
#
messages.receive(4)

for complaint in messages[4]:
    j = complaint.senderIndex
    m = complaint.accusedIndex
    privkey_jm = complaint.privkey

    # Presented private key does not correspond to the published public key
    #
    # Disqualify accuser
    #
    if not validatePrivkey(
        senderIndex = j,
        recipientIndex = m,
        privkey = privkey_jm
    ):
        disqualify(5, j)
    else:
        pubkey_mj = ephemeralPubkey(m, j)

        k_jm = ecdh(privkey_jm, pubkey_mj)

        # Check whether the shares are consistent with the accused's commitments
        sharesValid = decryptAndValidateShares(
            senderIndex = m,
            recipientIndex = j,
            symkey = k_jm
        )

        # Shares inconsistent, disqualify accused
        if not sharesValid:
            disqualify(5, m)
        # Shares consistent, disqualify accuser
        else:
            disqualify(5, j)
Utility functions
# Check that a revealed private key matches previously broadcast public key
def validatePrivkey(senderIndex, recipientIndex, privkey):
    expectedPubkey = ephemeralPubkey(senderIndex, recipientIndex)
    return derivePubkey(privkey) == expectedPubkey
Phase 6: Share calculation

Each player sets their share xi of the secret X to equal the sum of all shares sji as per GJKR. X equals the sum of shares sj0.

Phase 6
# GJKR 2:
#
QUAL = goodParticipants[6]

# GJKR 3:
#
#   x_i = sum([ s_ji for j in QUAL ]) % q
#   x'_i = sum([ t_ji for j in QUAL ]) % q
#
# This is safe to calculate here as the consistency of the shares has been
# ascertained. If a participant gets disqualified later their public key piece
# will be reconstructed to match the honest participants' shares.
#
x_i = sum(
    [ self.shares[j].share_S for j in QUAL ]
) % q

xprime_i = sum(
    [ self.shares[j].share_T for j in QUAL ]
) % q
Phase 7: Public key share points

Each player broadcasts their Aik values.

Phase 7
# GJKR 4.(a):
#
#   A_ik = g^a_ik % p
#
self.pubkeyCoeffs = [
    P1.scalarMult(A_ik) for A_ik in self.sharePolyCoeffs
]

broadcast(messagePhase7(self.pubkeyCoeffs))
Phase 8: Public key share validation

Each player validates the values received in Phase 7.

Phase 8
# Receive messages from phase 7:
# - public key coefficients
#     IA if message not present
#
# Validate:
# - the expected number (M + 1) of pubkey coefficients must be present
#     DQ if incorrect number of coeffs
# - public key coefficients must be valid curve points for G1
#     DQ if a coefficient is not a valid curve point
#
messages.receive(7)

pubkeyComplaints = []

for j in goodParticipants[8]:
    pubkeyShareValid = validatePubkeyCoeffs(
        senderIndex = j,
        recipientIndex = i,
        share_S = self.shares[j].share_S
    )

    if not pubkeyShareValid:
        pubkeyComplaints.append(pubkeyComplaint(j))

broadcast(messagePhase8(pubkeyComplaints))
Utility functions
# Fetch the sender's public key coeffs `A_ik` from messages broadcast in phase 7
def pubkeyCoeffs(senderIndex):
    return messages[7][senderIndex].pubkeyCoeffs


# P_i is the player whose public key share is calculated
# P_j is the perspective player
#
def pubkeyShare(senderIndex, recipientIndex):
    i = senderIndex
    j = recipientIndex

    A_i = pubkeyCoeffs(i)

    pubkeyShare = ecSum(
        [ A_i[k].scalarMult(j^k) for k in [0..M] ]
    )
    return pubkeyShare


# Check that equation 3 holds for `share_S`
#
# GJKR 4.(b):
#
#   g^s_ij == product([ A_ik ^ (j^k) for k in [0..T] ]) % p
#
def validatePubkeyCoeffs(
        senderIndex,
        recipientIndex,
        share_S
):
    return P1.scalarMult(share_S) == pubkeyShare(senderIndex, recipientIndex)
Phase 9: Second complaint resolution

As in Phase 5, but with the validation formula from Phase 8.

It should be noted that the symmetric nature of the encryption allows the parties to also decrypt Ejm and not just Emj. However, this is not very significant as even the publication of only the misbehaving participants' shares would reduce the security margin excessively if a large fraction of P were to misbehave.

By aborting group creation if the number of inactive and disqualified participants exceeds Mnofail = M/2 the impact of this is reduced to a manageable level.

Phase 9
# Receive messages from phase 8:
# - complaints about invalid public key coefficients, or "no complaints"
#     IA if no message sent
#
# Validate:
# - each revealed private key must be a valid scalar for ECDH
#     DQ if invalid
# - each revealed private key must correspond to the public key
#     DQ if does not match pubkey from phase 1
#     (explicit in pseudocode)
#
messages.receive(8)

for complaint in messages[8]:
    j = complaint.senderIndex
    m = complaint.accusedIndex
    privkey_jm = complaint.privkey

    if not validatePrivkey(
            senderIndex = j,
            recipientIndex = m,
            privkey = privkey_jm
    ):
        disqualify(9, j)
    else:
        pubkey_mj = ephemeralPubkey(m, j)

        symkey = ecdh(privkey_jm, pubkey_mj)

        badActor = resolvePubkeyComplaint(
            senderIndex = m,
            recipientIndex = j,
            symkey = symkey
        )

        if badActor == "accused" or badActor == "both":
            disqualify(9, m)
        if badActor == "complainer" or badActor == "both":
            disqualify(9, j)
Utility functions
# Check which party is at fault when a complaint is presented in phase 8
#
# Decrypt the shares the accused sent to the complainer in phase 3 and check
# the validity of the accused's `A_ik` values
#
def resolvePubkeyComplaint(
        senderIndex,
        recipientIndex,
        symkey
):
    plaintext = decryptShares(
        senderIndex,
        recipientIndex,
        symkey
    )

    if not plaintext:
        # only happens if the complainer failed to complain earlier
        # and thus both violated protocol
        return "both"
    else:
        (share_S, _) = unmarshalPoints(plaintext)

        pubkeyValid = validatePubkeyCoeffs(
            senderIndex,
            recipientIndex,
            share_S
        )

        if pubkeyValid:
            return "complainer"
        else:
            return "accused"
Phase 10: Disqualified share opening

All active players in G10 broadcast the keys they share with players in DQ9, so the reconstruction of Pedersen-VSS can be done offline.

Phase 10
disqualifiedKeys = []

for m in disqualifiedInPhase[9]:
    keyPackage = (m, self.ephemeralKey[m])
    disqualifiedKeys.append(keyPackage)

broadcast(messagePhase10(disqualifiedKeys))
Phase 11: Disqualified share reconstruction

Decrypt and reconstruct zm for every participant Pm that presented valid shares in Phase 3 but whose public key shares in Phase 7 were invalid. Calculate ym = zm * P1 for each reconstructed zm.

Phase 11
# Receive messages from phase 10:
# - good participants' ephemeral private keys for each disqualified participant
#     IA if no message sent
#
# Validate:
# - all expected private keys are revealed
#     DQ if number of keys is incorrect
# - each revealed private key must be a valid scalar for ECDH
#     DQ if a private key is invalid
# - each revealed private key must correspond to the public key
#     DQ if private key does not match public key from phase 1
#     (explicit in pseudocode)
#
messages.receive(10)

for keys_j in messages[10]:
    j = keys_j.sender
    for keyPackage in keys_j.keyPackages:
        m = keyPackage.index
        privkey_jm = keyPackage.ephemeralKey

        if not disqualifiedInPhase[9].contains(m):
            # P_j broadcast the wrong keys
            disqualify(11, j)

        if not validatePrivkey(
            senderIndex = j,
            recipientIndex = m,
            privkey = privkey_jm
        ):
            # P_j broadcast invalid keys
            disqualify(11, j)
        else:
            pubkey_mj = ephemeralPubkey(m, j)
            symkey_jm = ecdh(privkey_jm, pubkey_mj)

            validShares = decryptAndValidateShares(
                senderIndex = m,
                recipientIndex = j,
                symkey = symkey_jm
            )

            if not validShares:
                # P_j failed to complain earlier
                disqualify(11, j)
            else:
                (s_mj, t_mj) = validShares
                self.revealedShares[m][j] = (s_mj, t_mj)

for m in disqualifiedInPhase[9]:
    shares_m = self.revealedShares[m].values
    indices_m = self.revealedShares[m].indices

    z_m = reconstruct(shares_m, indices_m)
    y_m = P1.scalarMult(z_m)
    self.reconstructed_Y_[m] = y_m
Utility functions
def reconstruct(shares, indices):
    secret = sum(
        [ share_k * lagrange(k, indices) for share_k in shares, k in indices ]
    )
    return secret % q
Phase 12: Public key reconstruction

Let G12 = G11

Combine yj for all participants in G6 to reconstruct the public key for the group. Additionally, calculate and store each qualified participant’s individual public key for validating signature shares.

Phase 12
# GJKR 4.(c):
#
#   Y = product([ A_i0 for i in QUAL ]) % p
#
def A_(i):
    if not disqualifiedInPhase[9].contains(i):
        return pubkeyCoeffs(i)
    else:
        return [self.reconstructed_Y_[i]]

Y = ecSum(
    [ A_(i)[0] for i in QUAL ]
)

for j in goodParticipants[12]:
    self.peerPublicKeys[j] = individualPublicKey(j, QUAL)
Utility functions
# Calculate the individual public key of a specific participant
#
# P_i is each qualified participant in turn
#
# GJKR (C1'):
#
#   g^x_j
#     = g^( sum([ s_ij for i in QUAL ]) ) % p
#     = product([ g^s_ij for i in QUAL ]) % p
#     = product([ product([ A_ik ^ (j^k) for k in [0..T] ]) for i in QUAL ]) % p
#
def individualPublicKey(memberIndex, QUAL):
    pubkeyShares = [ pubkeyShare(i, memberIndex) for i in QUAL ]
    return ecSum(pubkeyShares)
Phase 13: Result establishment

Let IA = IA1 + IA2 + …​ + IA10

Let DQ = DQ1 + DQ2 + …​ + DQ10

if nPlayers(IA + DQ) {lt}= M_nofail:
  correctResult = Result.success(pubkey = Y, inactive = IA, disqualified = DQ)

resultHash = hash(correctResult)

Once the result has been determined, all participants evaluate the hash of their preferred result, sign the hash and broadcast the hash and a signature over it in the group broadcast channel. Each participant collects the signatures matching their preferred result, stores them along with the signers' member indices.

  • If the signature of hash broadcasted off-chain is invalid, it will be rejected and not published to the chain in the next phase.

  • If multiple signatures from the same member on the same result are found, they will all be filtered-out so that none of them is published to the chain in the next phase.

If multiple signatures from the same member on different results are found, they should all be filtered-out so that none of them is published to the chain in the next phase.

If the result for the DKG is a failure due to too many members being inactive or disqualified, no result is submitted on-chain; instead, the DKG is allowed to simply time out.

Phase 14: Result submission
Off-chain

When a participant becomes eligible to submit the result (with supporting signatures) on-chain they submit if they have at least the honest majority (marked as H - constant for the given group size) of signatures for that result (including their own).

First player is always eligible to submit the result.

Second player becomes eligible after initial timeout (time necessary to perform DKG protocol plus step time T_dkg + T_step) and remains eligible until the result is accepted by the chain.

In other words, Nth player becomes eligible to submit the result after T_dkg + (N-1) * T_step and remains eligible until the result is accepted by the chain.

If first player is late and second player tries to submit, whichever gets mined first wins and subsequent submissions are disregarded immediately to avoid burdening the loser with excess gas fees.

alreadySubmitted = False
resultPublished = False
finished = False

while not resultPublished:
  T_now = getCurrentBlockHeight()

  # using T_init from phase 1
  T_elapsed = T_now - T_init

  # determine highest index j eligible to submit
  if T_elapsed <= T_dkg:
    j = 1
  else:
    T_over = T_elapsed - T_dkg
    j = 1 + ceiling(T_over / T_step)

  if j >= i:
    broadcast(correctResult)
    resultPublished = True
    alreadySubmitted = True
  else:
    resultPublished = checkChainForResult()
On-chain

When the result is submitted on-chain along with the signatures, the contract checks that there are at least H signatures or more, and that each signature is valid for the submitted result and the corresponding member ID. Submissions containing multiple signatures on the same result from the same member are rejected.

If the above checks pass, the result is considered canonical for the group. All other group members should abort publishing their results and no new result submissions will be accepted by the chain.

If the above checks do not pass, the result is rejected.

If no canonical result has been published until T_dkg + N * T_step, where N is the group size, DKG operation is marked as failed.

References
  • [GJKR] Gennaro R., Jarecki S., Krawczyk H., Rabin T. (1999) Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In: Stern J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg

  • [Ped] Pedersen T.P. (1992) Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum J. (eds) Advances in Cryptology — CRYPTO ’91. CRYPTO 1991. Lecture Notes in Computer Science, vol 576. Springer, Berlin, Heidelberg

  • [EIP-197] EIP 197: Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128

Random Beacon Signing

Terminology

P1

The generator point for the BLS elliptic curve

X_k

The group private key of Group_k

Y_k

The group public key: Y_k = P1 * X_k

Entry_e

The entry matching the entry identifier e

Input_e

The input for generating the new entry: Entry_e = Input_e * X

x_i

The individual private key of P_i

y_i

The individual public key of P_i: y_i = P1 * x_i

Share_i

The signature share by P_i: Share_i = Input_e * x_i

N

The number of members in a group

H

The number of members required for a honest majority

Signing group selection

When a valid request has been received, the beacon begins the relay entry generation.

The current block is recorded as the start block of the entry generation:

currentRequestStartBlock = block.number

The previous entry is hashed to produce the signing group selection seed.

seed = keccak256(previousEntry)

The signing group is selected by taking the value of the seed modulo the number of currently active groups, and selecting the corresponding active group:

selectedGroup = seed % numberOfGroups()

Signature generation

The selected group now has relayEntryTimeout blocks to submit the signature to previousEntry.

Generating signature shares

Each member P_i in selectedGroup calculates their signature share: Share_i = previousEntry * x_i.

The generated shares are broadcast to the other members. The broadcast message contains the Share_i and the member index i of the sender P_i.

Message = (Share_i, i)

Verifying signature shares

When P_i receives a signature share Share_j broadcast by P_j, the share can be verified by blsVerify(Share_j, y_j, previousEntry). If Share_j is valid, P_i can use it for reconstructing the threshold signature. If Share_j is invalid, P_i must not use it for reconstructing the entry.

Reconstructing the signature

Once P_i has received at least blsThreshold valid shares, the entry can be reconstructed using Lagrange interpolation.

shares = validMessages.map(share)

indices = validMessages.map(index)

newEntry = lagrangeInterpolate(0, indices, shares)

Output submission

Member Psubmitter of Groupi submits newEntry = blsSign(previousEntry, X_i)

The beacon verifies that the submitted entry is a valid signature of the previous entry for the selected group’s public key:

blsVerify(newEntry, previousEntry, Y_i)

If the submitted entry is valid, it is accepted as the current beacon entry Entryi = newEntry. Reward Psubmitter and other members of Groupi according to the reward formula.

If the submitted entry is invalid, it is rejected.

Entry timeout

If a valid output is not submitted before block timeoutBlock = currentRequestStartBlock + relayEntryTimeout + 1, the entry generation for the selected group times out. From timeoutBlock onwards, no submissions by Groupi are accepted, and anyone can report the timeout by calling reportRelayEntryTimeout().

When the beacon receives a valid timeout report the previously selected group is terminated, with each member penalized for their (lack of) contribution to the failure. The beacon returns to the signing group selection with the failed group being removed from the group pool.

Pricing

Background

The beacon needs to capture enough value to make it self-sufficient. It uses a simple method for pricing beacon entries that doesn’t present easy exploitation opportunities. The pricing method avoids the known downfalls of previously considered, more complex, schemes, such as price discrimination being defeated by callback pooling.

Implementation

Making requests

A request begins with the query entry_fee_estimate = estimate_fee(callback_gas_amount) , which provides the customer with an estimated fee to use in the request. The fee estimate is only valid for the transaction it is called in, so the customer must make the request immediately after obtaining the estimate. Insufficient payment will lead to the request being rejected and the transaction reverted.

To make a request after determining the applicable fee the customer must call the request method on the beacon, transferring enough currency to cover the fee: request_entry.value(entry_fee_estimate)().

If the customer wishes to receive the generated random number in a callback, they should also specify the callback address, callback function, and callback gas amount: request_entry.value(entry_fee_estimate)(callback_address, callback_function, callback_gas).

No new requests should be made while the beacon is already processing another request. Requests made while the beacon is busy will be rejected and the transaction reverted.

Receiving a request

A request sent to a non-busy beacon is checked for request fee >= entry fee estimate + callback gas amount from the request. If the beacon is already serving an earlier request, it rejects any new requests and refunds the fee.

A sufficiently funded request triggers the beacon to select the new signing group. The selected group is tasked with producing the new entry.

The request is then set as the pending request with the following information:

  • the requester address

  • the callback address, callback function, and callback gas amount, if applicable

  • the assigned signing group[5]

  • the submission delay base time which equals the number of the block the request was received in, plus 1[6]

  • the request fee paid

Serving a request
Receiving submissions

A valid entry created by a signing group is submitted by a member of the group called the submitter, before the Submission deadline. Submissions that fail verification are ignored. Repeat submissions for a request that has already been served are dropped immediately to minimize gas expenditure.

If no valid entry has been received by the submission deadline a submission timeout can be called by anyone, as a result of which:

  • the failing group is terminated and its members slashed

  • a new signing group is assigned from the remaining active groups

  • the submission delay calculation is reset by setting the submission delay base time to the previous submission deadline.

When a valid entry submission is received on-chain:

  • it is emitted in an event

  • the requester’s callback is called if applicable

  • and fees, rewards and refunds are paid out

Callback processing

A callback is called using the callback gas amount as the maximum gas. If the callback gas amount is insufficient, callback execution is skipped and the rest of the relay entry submission code is processed as usual.

callback expenditure is calculated as, gas spent on call * minimum(gas price ceiling, actual gas price during transaction).

The minimum of the gas price is included to protect the beacon and requester against malicious miner-submitters.

Malicious miner-submitter attacks:

  • a miner-submitter can steal the surplus pool subsidy by placing an arbitrary gas price on the transaction that is higher than quoted. This will cause the requester refund to go negative. If the negative requester refund is added to the 1% surplus pool subsidy it can permit the miner-submitter to steal the subsidy.

  • a miner-submitter can steal the requesters refund by setting the gas price to the provided maximum. The requester is billed for the entire gas budget even if they really only spent a small fraction of it.

A callback execution that uses more gas than specified in the request will run out of gas. A callback execution can cost more than was quoted and paid for only when the gas cost of the transaction exceeds the gas price ceiling. The submitter is intended to take the hit for submitting with a gas price that exceeds the gas price ceiling.

Requester refund

requester refund = actual entry price - requester fee + 1% of request subsidy pool

actual entry price = callback expenditure + entry base price

entry base price = estimated gas price + profit margin + DKG contribution amortized over multiple entries + entry verification fee

Group & Submitter reward = F (submission delay, submission delay base time)

If the sum of rewards paid out is < profit margin + entry verification fee, the difference is added to the request subsidy pool.

The DKG contribution is added to the DKG fee pool, and the state of the pool is checked.

If the amount in the DKG fee pool equals or exceeds the DKG cost estimate, group creation and a new DKG may be triggered.

Rewards

A base reward for each member of a signing group that produces an entry is specified in the system constants in the service contract and:

profit margin = base reward * group size

The exact rewards paid out to operators are based on the base reward but vary according to submission delay and submitter position.

To incentivize customers to request entries, any amount in excess of the profit margin is added to the beacons request subsidy pool

Submitter reward

Submitter reward = F (submission delay, submission delay base time)

If the sum of rewards paid out is < profit margin + entry verification fee, the difference is added to the request subsidy pool.

Group reward

The group reward is paid to every member of the signing group, including the submitter, upon submission of a valid entry.

The group reward equals the base reward multiplied by a delay factor equaling the fraction of time left by the submission deadline, squared: group reward = base reward * delay factor; delay factor = (Tremaining / (Tdeadline - Tbegin))2; Tremaining = Tdeadline - Treceived.

The delay factor is counted from 1 in the first block a submission could be published in, to 0 in the deadline block which doesn’t accept any more submissions.

For example, assume the maximum time to submit is 20 blocks, the off-chain entry generation protocol takes 5 blocks and a request is made on block 1000.

Block 1005 is the earliest block the submission could be published in: if published in this block the delay factor is 1. Block 1025 is the deadline block: no submissions are accepted and the delay factor is 0.

If the entry is submitted in block 1009, the delay factor is:

((1025 - 1009) / (1025 - 1005))^2 = 0.8^2 = 0.64

Thus the group reward = base reward * 0.64, with the difference being the delay penalty = base reward * (1 - 0.64).

If the submission deadline is reached and the delay factor reaches 0, the entry submission fails and all group members are penalized.

Submitter reward

In addition to the group reward, the submitter is reimbursed for gas fees and receives an extra reward.

The submitter reward consists of: - callback expenditure to cover the exact cost of the callback

  • the entry verification fee to cover the cost of verifying the submission

  • 5% of the delay penalties of the entire group

Unlike the callback allowance, the entire entry verification fee is paid to the submitter regardless of their gas expenditure. The submitter is free to spend less or more, keeping the surplus or paying the difference. This is to incentivize optimizing gas fees.

To incentivize a race for the submitter position, the submitter receives:

_delay penalty * group size * 0.05_ as an extra reward

With realistic group sizes this is significant, but not high enough to render certain attacks profitable. If the group size is 100 and the delay factor is 0.64, the submitter receives an extra reward of:

base reward * 0.36 * 100 * 0.05 = base reward * 1.8

In this scenario the full submitter reward would be:

base reward * (1.8 + 0.64) + callback expenditure + entry verification fee

DKG submitter reimbursement

How is the DKG submitter compensated?

Getting to participate in a formed group is already valuable so there is no additional reward for a DKG result submitter. The only thing necessary is a gas cost reimbursement for the submitter.

After the DKG result is submitted:

DKG result submission expenditure = minimum(gas price ceiling, actual gas price during transaction) * gas spent on call

The entire DKG result submission expenditure is returned to the submitter from the DKG fee pool of the operator contract.

The minimum of the gas price protects the beacon against malicious miner-submitters. If the submitter is also a miner, they can place any arbitrary gas price on the transaction. Without taking the minimum, miner-submitter would be able to steal from DKG fee pool of the operator contract.

Any surplus between the DKG fee pool of the operator contract and the actual cost of DKG result submission is returned back to the service contract. In the case when the entire DKG fails, the unspent fee will be transferred back to the service contract upon the next DKG triggered by the service contract.

The on-chain DKG result submission code needs to have all deterministic and time-bounded run paths that are independent of miner-controlled inputs. If the miner-submitter pays the gas price as set in the gas price ceiling, but tricks the contract into consuming twice the gas as normal, they will be able to get twice the reimbursement as well.

Cost estimates
Gas price ceiling

A gas price ceiling is required to estimate the gas cost components.

The critical feature of the gas price ceiling is that the ceiling price should be sufficient for getting beacon entries processed within the deadline under all circumstances.

If actual gas prices rise to a level where gas price ceiling is insufficient for getting a transaction to be mined, and stays there for the duration of the entry submission window, the basic profit margin for the operators cannot be guaranteed.

However, this does not imply that high gas prices would render the beacon inoperable. The submitter’s extra reward incentivizes submitting even when the entry verification fee cannot cover the gas costs. In the extreme, avoiding the severe penalty for failure to produce an entry will incentivize group members to pay the gas prices up to the (theoretical) limit where gas for the entry submission transaction costs as much as the KEEP tokens at stake.

DKG cost estimate

The gas required for DKG should be calculated. DKG gas cost should include only DKG result submission. Ticket submission costs are covered by the expected return from getting into a signing group. Multiply DKG gas by gas price ceiling to get DKG cost estimate. Use a DKG frequency divider d to set the group creation rate; once every d entries on average. Divide DKG cost estimate by d to get DKG contribution for each entry.

The maximum DKG gas cost should be hardcoded in the operator contract. The service contract takes the highest applicable gas cost from all operator contracts being used and multiplies it by the gas price ceiling.

As long as the gas price ceiling is sufficient to cover the immediate rise in gas fees during DKG execution the beacon is capable of generating new groups without requiring DKG result submitter to take a hit for submitting the result with a higher gas price.

Entry verification fee

Calculate gas required for verifying entry and associated support operations. The maximum entry verification gas cost are hardcoded in the operator contract. The service contract takes the highest applicable gas cost from all operator contracts being used and multiplies it by the gas price ceiling to get entry verification fee.

Staking

The Keep network uses staking of tokens to enforce correct behavior.

Basic description

Anyone with tokens can stake them, setting them aside as collateral for network operations. Staked tokens are delegated to an operator address who performs work for operator contracts. Operators can earn rewards from contributing to the network, but if they misbehave their collateral can be taken away (stake slashing) as punishment.

Stakers and roles

A token owner may wish to stake in a variety of different ways, for security or efficiency reasons. To support different ways of staking, the network uses a single abstraction of a staker comprised of multiple separate roles:

owner

Provides the tokens for the staker

operator

Handles the day-to-day participation in the network operations

beneficiary

Collects any rewards earned by the staker

authorizer

Authorizes contracts to protect against buggy or compromised upgrades

The different roles can all be performed by the same address; they may be divided between different addresses controlled by the same person; or they may be different parties entirely, executing a sophisticated scheme of cold storage and third-party delegation. As far as the network is concerned, any of these arrangements simply forms a staker.

staker

An abstraction representing the owner, operator, beneficiary and authorizer each performing their respective roles.

Stakers are identified by their operator address.

Initiating staking

Staking is initiated by the owner choosing the amount of tokens to stake, and the operator, beneficiary and authorizer addresses. The owner then authorizes the staking contract to claim a number of tokens, and calls the staking contract to stake the tokens. The staking contract processes the call, claims the tokens to itself, and records the information. The addresses of the roles cannot be changed after delegation.

Contract authorization

Before the staker can participate in the network, the authorizer must authorize each operator contract the staker wishes to use. It is necessary to introduce new functionality and to upgrade old contracts, but buggy or malicious operator contracts could be used to steal or destroy tokens by slashing well-behaved stakers. The requirement for authorization ensures that the owner’s tokens are safe even if a contract upgrade is compromised, as long as the authorizer denies authorization to such contracts.

Once a contract has been authorized, the authorization cannot be revoked.

Operation

The operator provides services in the network by following the protocols of authorized operator contracts.

Any number of operations may be active at once regardless of the staked amount.

Rewards

Stakers that provide services in the network will be rewarded at certain points. Rewards may be either tokens or the currency used to pay for network services. Rewards earned by a staker will be sent to the staker’s beneficiary address.

Slashing

If a staker violates the protocol of an operation in a way which can be proven on-chain, they will be penalized by having their stakes slashed.

If a staker has joined multiple operations at once, they may accrue more punishments than their stake can cover. If a staker’s remaining stake falls to zero, the staker is terminated and may not continue any operations. Any remaining penalties are nullified.

Tattletales

Some misbehavior cannot be caught by a contract alone and requires the cooperation of a third party tattletale. If a tattletale presents proof of misbehavior by a staker, a part of the penalty will be awarded to the tattletale as a tattletale reward.

Unstaking

When staking, the tokens used as collateral are locked until the staker announces their intention to stop staking, and for a period of time afterwards. The purpose of this unstaking period is to give operations time to finish before the collateral can be moved away. No new operations can be started or joined within the unstaking period but the staker is required to continue participating in any unfinished operations.

Details

Roles

The staker is an abstraction comprising of four different roles, each with a clear scope of responsibility. The initial design included only the roles of the owner, operator and beneficiary; the authorizer was added to take full advantage of the upgrade security plan.

Owner

The owner makes the decision to stake, provides the tokens for the staker, and chooses the addresses for the other roles. The owner can initiate unstaking and reclaim tokens, but these can also be performed by the operator.

The role of the owner is designed to facilitate cold storage by minimizing the interaction necessary for staking. Initiating staking is the only operation where the owner’s keys are absolutely required.

Operator

The operator address is tasked with participation in network operations, and represents the staker in most circumstances.

Rewards and punishments are based solely on the operator’s actions, and the operator can not only cause opportunity costs but can also lose the entire stake and possibly steal a fraction of it using only contracts functioning as intended. If the operator is a different party from the owner, a high level of trust is necessary.

In addition to participating in the network via the authorized operator contracts, the operator can also initiate undelegation.

Beneficiary

The beneficiary is an entirely passive role. Rewards of tokens or currency are simply sent to the beneficiary address by the staking contract.

The beneficiary role is separate from the owner and operator to provide flexibility in how to receive and use rewards without interfering with the owner’s cold storage or the possible contractual relationship between the owner and operator.

Authorizer

Because slashing stakes requires arbitrary access to stakers' accounts, explicit authorization is required for each operator contract before it may penalize stakers.

The upgrade security plan is designed to limit the impact of upgrade key compromise and to provide a graceful recovery route while minimizing the impact to the rest of the network. The explicit authorization requirement prevents a compromised contract from stealing stakers' funds by exploiting the punishment interface. Instead, compromise of both the authorizer and the contract is required.

As a further security measure, the authorizer can only authorize pre-approved contracts from a list maintained by the governance structure of the network. This ensures that the authorizer cannot do damage in the absence of further compromise, except by withholding desired authorizations.

The authorizer role is separated from the owner and operator to facilitate cold storage for the former and to reduce the necessary privileges of the latter.

If the owner were required to authorize each new contract and upgrade, it would present an unnecessary hindrance to effective cold storage schemes. Due to the two-factor nature of the authorizer keys, the same level of protection is not necessarily required.

On the other hand, separating the authorizer from the operator reduces the latter’s ability to profit from damaging the owner’s interests. While even the operator has the ability to lose or steal the owner’s tokens, it is restricted by the opportunities provided by the authorized contracts. Using the tattletale mechanism to transfer tokens is inefficient, but a compromised contract would not be subject to the same restrictions and could be used to transfer all of the staker’s tokens to the attacker.

Third party delegation

The role of the authorizer can be delegated to a third party, and it is expected that many would do so.

Most owners and operators are unlikely to scrutinize each contract, or even to have the ability to do so effectively. Providing a convenient way to express one’s choice to trust a third party would make centralization of such trust visible.

A downside of convenient delegation is that requiring individual authorizations provides another source of friction and human judgment between compromise of single points of failure and actual loss of staker funds. An owner can avoid this fate by not assigning a third party as the authorizer address.

Staking contract

The staking contract records two time (blockheight) fields for each operator: the block the operator was created, and the block undelegating began.

Operators can be:

  • non-existent

  • not ready for work selection because they were created too recently

  • active and eligible for work selection

  • winding down and ineligible for work selection but finishing earlier work

  • finished undelegation so the owner can recover their tokens

Using the systemwide constant undelegation period, the operator’s status can be determined from the creation and undelegation blocks.

Operators are uniquely identified by their address and operator addresses cannot be reused, even after returning the tokens to the owner.

To reduce the impact of transaction reordering, both delegating and undelegating take effect on the next block after the block the transaction is processed in.

Parameters
Operator initialization period

E.g. 50,000 (roughly 6 days)

To avoid certain attacks on work selection, recently created operators must wait for a specific period of time before being eligible for work selection. This waiting period must be greater than the highest permissible time between the making of a beacon entry request and the request being served. In the ideal case, multiple entries would be requested and generated within the initialization period.

If the initialization period is insufficiently long, the pseudorandom work selection process can be subverted by creating operators whose identifiers (addresses) are calculated to yield advantageous outputs in the selection function. This can let the adversary control the majority in the new signing group.

If the new group is in line to sign the next entry, the adversary could choose the group’s private key so that the following entry also gets signed by a group controlled by the same adversary. With sufficient calculation capability, this can be repeated n times at the cost of roughly O(kn) calculations where k equals the number of active groups divided by the number of active adversary-controlled groups. If another signing group is created within this time, it can be similarly controlled. This can eventually lead to the adversary controlling the entire network.

With the initialization period, the adversary has to create the operators in advance long before they become eligible for work selection. Thus the adversary has to be able to predict each entry generated during the initialization period. With an unreasonably powerful adversary that can arbitrarily frontrun 50% of all entries, generating n entries within the initialization period provides 2n security against this attack.

Undelegation period

E.g. 200,000 ~ 800,000 (roughly 1 to 3 months)

The staking contract guarantees that an undelegated operator’s stakes will stay locked for a number of blocks after undelegation, and thus available as collateral for any work the operator is engaged in.

Operator data
mapping(address => Operator) operators;

struct Operator {
  uint128 stakedAmount;
  uint64  createdAt;
  uint64  undelegatedAt;
  address owner;
  address beneficiary;
  address authorizer;
}

Each operator stores the addresses of its owner, beneficiary and authorizer, the amount of tokens delegated to the operator, the block it was created at, and the block it was undelegated at if applicable.

Operator status
enum Status { NonExistent, NotReady, Active, WindingDown, Finished }

operatorStatus(address operator) -> Status

An operator’s status determines what actions are available for the operator and the owner the delegated tokens.

Non-existent

The operator doesn’t exist.

operators[operator] == nil

Not ready

The operator has been created in the same block the query was performed in. The operator is ineligible for work selection.

An operator is NotReady if the current block is equal or less than the creation block plus the initialization period.

block.number =< operator.createdAt + initializationPeriod

Active

The owner has delegated staked tokens to the operator, and the operator is eligible for work selection.

An operator is Active if the current block is greater than the creation block plus initialization period, and the undelegation block is either 0 or equal or greater than the current block.

block.number > operator.createdAt + initializationPeriod && (block.number =< operator.undelegatedAt || operator.undelegatedAt == 0)

Winding down

The operator has been undelegated and is not eligible for work selection, and the operator is finishing any work they were selected for earlier. The operator’s backing tokens continue to be locked as collateral.

An operator is WindingDown if the current block is greater than the undelegation block, but at most the undelegation block plus the undelegation period.

operator.undelegatedAt < block.number =< (operator.undelegatedAt + undelegationPeriod)

Finished

Undelegating the operator has finished. The backing tokens are unlocked and can be returned to the owner.

An operator is Finished if the current block is greater than the undelegation block plus the undelegation period.

block.number > operator.undelegatedAt + undelegationPeriod

Work selection eligibility

eligibleStake(address operator, uint block) → uint

Operators are eligible for work selection based on their status in the block the work selection started in. In some situations an operator’s status may have changed after work selection started, but before the operator contract queries it. For these cases the staking contract must provide a way to determine the operator’s eligibility for work selection that started in an earlier block.

It is the responsibility of each operator contract to query operator eligibility with the correct block number. Failure to use the correct block leads to minor manipulation opportunities. For example, querying an operator’s eligibility on the current block when they submit a ticket means that an ineligible operator whose initialization period is almost over could wait to submit their ticket until they become eligible for work selection.

To make determining an operator’s eligibility for work selection simpler and cheaper, the staking contract must provide the eligibleStake() function which returns the number of KEEP tokens available for use as collateral.

When calling eligibleStake(), the staking contract assumes msg.sender is an operator contract. eligibleStake() does not return meaningful results when called by an address that doesn’t correspond to an operator contract. If the operator is ineligible for work selection on msg.sender, eligibleStake() returns 0. Otherwise eligibleStake() returns operator.stakedAmount.

operatorExists = operators[operator] != nil

senderAuthorized = authorized[operator.authorizer][msg.sender] == True

operatorReady = block > operator.createdAt + initializationPeriod

notUndelegated = block =< operator.undelegatedAt || operator.undelegatedAt == 0

if operatorExists && senderAuthorized && operatorReady && notUndelegated:
  return operator.stakedAmount
else:
  return 0
Actions
Staking

stake(uint amount, address operator, address beneficiary, address authorizer)

Staking tokens delegates them to the operator, who can then use them as collateral for performing work. Staking is performed by the owner of the tokens, who must have authorized the staking contract to transfer amount KEEP to itself (e.g. via approveAndCall()).

token.allowance(msg.sender, stakingContract) >= amount

The nominated operator must not already exist.

operators[operator] == nil

The staking contract transfers amount KEEP from msg.sender to itself, and creates a stake delegation relationship, with the operator becoming Active in the next block.

operators[operator] = Operator {
  stakedAmount = amount;
  createdAt = block.number;
  undelegatedAt = 0;
  owner = msg.sender;
  beneficiary = beneficiary;
  authorizer = authorizer;
}
Cancelling staking

cancelStake(address operator)

The owner can cancel staking within the operator initialization period without being subjected to the token lockup for the undelegation period. This can be used to undo mistaken delegation to the wrong operator address.

msg.sender == operator.owner

block.number =< operator.createdAt + initializationPeriod

If staking is cancelled, the staked tokens are immediately returned to the owner, and the undelegation time is set to the present.

operator.stakedAmount = 0

operator.undelegatedAt = block.number

Undelegating

undelegate(address operator)

Undelegating sets the operator to WindingDown status so that the backing tokens can later be recovered by the owner. Undelegating can be performed by either the owner or the operator.

msg.sender == (operator || operator.owner)

Undelegating can only be performed on a currently active operator.

operatorStatus(operator) == Active

The staking contract sets the undelegation block of the operator to equal the current block, making the operator ineligible for any work selection in the future. Work selection performed earlier in the same block shall proceed as normal.

operator.undelegatedAt = block.number

Recovering tokens

recoverStake(address operator) → uint

Recovering staked tokens transfers them back to the owner. Recovering tokens can only be performed by the owner, when the operator is finished undelegating.

msg.sender == operator.owner

operatorStatus(operator) == Finished

The staking contract sets the staked amount of the operator to zero, and transfers the previously delegated tokens (or however much was remaining) back to the owner.

operator.stakedAmount = 0

The staking contract may additionally clean up the owner, beneficiary and authorizer addresses for the gas refund. However, the staking contract must not delete the creation and undelegation times, as this would enable reuse of the same operator address.

Misbehavior and punishments

To incentivize correct behavior in the Keep network, misbehaving participants will be punished. In some situations, proving misbehavior requires cooperation from another participant, a tattletale. This coordination is incentivized by rewarding the tattletale by granting them a fraction of the tokens taken from the misbehaving participant.

Authorization

Operator contracts are authorized to impose penalties by stakers' authorizers. All stakers using the same authorizer share the set of authorized operator contracts. Once given, this authorization cannot be revoked by the authorizer.

When an operator wishes to join a signing group the operator contract creating the group must be authorized by the operator’s authorizer. Authorization is checked when an operator submits a ticket for validation. The operator contract queries the staking contract for the amount of stake available for it. If the operator contract is not authorized or the operator is otherwise ineligible for work selection, the staking contract will return that the operator has no available stake, leading to any submitted tickets being rejected.

Penalties

When an operator’s misbehavior is proven on-chain the operator contract calls the staking contract to punish the operator, specifying the type and magnitude of the punishment. The staking contract checks that the operator contract is authorized to punish the operator, and if true, applies the penalty according to its own rules.

A penalty can be applied to one or more operators simultaneously. Each affected operator is penalized in the same way by the same amount. If the same address is listed multiple times among the operators to be punished, the punishment will be applied multiple times.

Pure slashing

When misbehavior is detected without third-party input, a pure slashing penalty is applied. Pure slashing means that the staking contract subtracts the applicable penalty from the operator’s stake and burns tokens equal to the penalty amount. If the operator doesn’t have enough stake for the punishment (e.g. because it has been punished earlier), the punishment is equal to the remaining stake.

Seizing

When a tattletale proves another operator’s misbehavior, a fraction of the penalty amount is seized and transferred to the tattletale, while the rest is burned.

If the full amount is transferred to the tattletale, it can be exploited to transfer staked tokens without the normal constraints. To reduce the effectiveness of this "tattletale transfer", the seized amount is limited to a maximum of 5% of the entire penalty. The tattletale reward can be set to any value between 0 and the maximum of 5% of the penalty.

To apply a seizing penalty, the operator contract includes the tattletale operator’s address in the call. The staking contract subtracts the applicable penalty from the operator’s stake and transfers the reward to the tattletale’s beneficiary address. The remainder is burned.

Penalty amounts

In later versions, penalties for misbehavior can be adjusted to match the severity of the misbehavior. However, initially the penalty for misbehaving in the random beacon will equal the minimum stake required to join a signing group.

Interfaces

Staking contract: slashing
slash(tokens amount, address[] misbehavers)

Slash each operator in the list misbehavers by the specified amount (or their remaining stake, whichever is lower).

For each misbehaver in misbehavers, perform the following:

  1. Check that the caller is authorized to slash the operator: isAuthorized(msg.sender, misbehaver.authorizer) == true.

  2. Determine the applicable punishment for the operator: thisPenalty = min(amount, misbehaver.stake).

  3. Subtract the punishment from the operator’s stake and add it to the total to be burned: misbehaver.stake -= thisPenalty; totalPenalty += thisPenalty.

    Finally, burn an amount of tokens equal to the slashed total: tokenContract.burn(totalPenalty).

seize(tokens amount, float rewardMultiplier, address tattletale, address[] misbehavers)

Punish each operator in the list misbehavers by the specified amount or their remaining stake. Reward the tattletale by an amount between 0 and the maximum reward, determined by the rewardMultiplier argument: if rewardMultiplier is greater than 0 and at most 1, multiply the highest allowed tattletale reward by rewardMultiplier. Otherwise reject the call for an invalid reward multiplier.

For each misbehaver in misbehavers, calculate and apply the appropriate penalty and track the total as in slash().

Finally, determine the tattletale reward: reward = totalPenalty * 0.05 * rewardMultiplier. Transfer the reward to the tattletale’s Beneficiary and burn the rest of the penalty: tokenContract.burn(totalPenalty - reward).

Staking contract: authorizations
authorize(address op_contract)

Authorize op_contract. Operators using msg.sender as their authorizer may now join operations on op_contract and op_contract may slash their stakes.

isAuthorized(address op_contract, address authorizer) → bool

Check if the authorizer authorizer has authorized op_contract to apply punishments on operators using authorizer as their authorizer.

eligibleStake(address operator) → uint

Return the number of staked tokens available for the calling contract. Includes an authorization check isAuthorized(msg.sender, operator.authorizer) and other checks on the operator’s eligibility for work selection.

Token contract
burn(amount sum)

Any address that holds tokens can call burn(amount sum) to burn sum tokens, limited by tokens held by the address.

Punishable misbehavior

Failure to sign an entry

If a signing group is tasked with producing a beacon entry, but fails to submit a valid entry within the allotted deadline, each member in the group is punished by seizing and the group itself will be terminated.

The punishment is triggered by calling reportRelayEntryTimeout() once the deadline has been reached. The submitter of the trigger transaction will be treated as the tattletale, but the tattletale reward will be limited to min(1, 20 / group_size) of the maximum, or effectively the minimum stake of a single member. This is to prevent actors in a lynchpin position from profitably stealing other stakers' funds.

Unauthorized use of group signing key

If the group signing key of a signing group has been leaked, it can be proven by using the key to sign the address of the group and calling reportUnauthorizedSigning().

If the signature is valid for the public key of the signing group, it proves that the key has been used without authorization. Each member of the signing group is punished by seizing and the group is terminated. The submitter of the trigger transaction receives the maximum tattletale reward.

Upgrade management

The system has been designed to facilitate upgrades without exposing stakers to vulnerabilities commonly found in upgradeable smart contracts. For this purpose, smart contracts in the system are divided into different categories based on their purpose and functionality, and strict security boundaries are maintained in the design.

Furthermore, the authority to take various actions in the system has been divided into a number of roles where each role has a specific purpose and domain. The roles and their authorizations are designed to limit the impact of single key compromise. Severely harmful actions such as stealing participants' stakes should require the compromise of multiple independent actors wherever feasible.

Contract structure

Overview

Token contract

KEEP is an ERC20 token defined by the token contract. The token contract is hard-coded in the operator and staking contracts, but the design of the overall system makes it possible to later migrate to a new version of the token contract without disrupting customer experience.

Staking contract

Owners of KEEP tokens can use a staking contract to stake them and use them as collateral for operators who perform useful work in the Keep Network. Staked tokens are transferred to the staking contract and delegated to an operator address. The staking contract makes the tokens available to operator contracts that have been authorized to punish the operator in case of misbehavior, while protecting them from unauthorized operator contracts.

Operator contracts

Operators interact with operator contracts to perform useful work for customers. Operator contracts handle operations that are critical for the proper incentives of individual operators. They reward operators for correct behavior, and are authorized to punish misbehavior.

Service contracts

Service contracts provide higher-level services to the public using work performed by one or more operator contracts. Service contracts do not interact directly with operators nor do they need to be aware of the KEEP tokens or the staking contract. Operator contracts can be upgraded without disrupting customer experience by deploying a new version and adding it to the service contract.

Registry

The addresses of contracts approved by Keep Org are kept in the registry. Token contracts, staking contracts, operator contracts and service contracts are all tracked separately in the registry. The addresses and statuses of various contracts can be queried from the registry.

Operator contracts

Operator contracts coordinate the work performed by network operators, and provide services to other "customer" contracts. Operator contracts handle all operations that may have an impact on staked tokens. Conversely, operators performing work for the network only need to interact with operator contracts.

The customer contract is treated as untrusted and the operator contract must maintain correctness and the safety of the operators' stakes regardless of the customer contract’s input. Each operator contract is an independent "microservice", keeping its own state on security-critical data.

When a customer contract requests an operator contract to perform a service, it must pay the operator contract for the service provided. The payment is distributed to contributing operators according to the operator contract’s own rules. An operator contract can either provide services to any contract that makes a valid request and pays the correct fee, or it can be owned by a specific contract and only serve its owner. In the random beacon the service contract is the only "customer" of the operator contracts, and operator contracts only provide services to the random beacon. Future operator contracts may provide services directly to the public.

If one or more participant operators misbehave or fail to perform promised work, the operator contract tells the staking contract to punish the guilty parties and optionally reward a tattletale that proved the misbehavior. To punish misbehaving operators, an operator contract must be authorized by the operator’s authorizer. Once an operator contract has been authorized by some address, it can never be deauthorized by that address.

Service contracts

Service contracts use the basic functionality performed by operator contracts, to provide useful services to the public. In contrast to operator contracts, service contracts don’t interact directly with operators and a failure in a service contract cannot risk operators' stakes.

Service contracts receive requests for their services from customers, and provide the requested services. Elements that are critical for operators' security and incentives are delegated to an operator contract, while other parts of the work are performed in the service contract. The service contract keeps shared state which is not security-critical.

Service contracts can use multiple different versions of operator contracts to perform the operator contract functions. To permit system upgrades, the list of used operator contracts can be updated with proper authorization.

Roles and authorizations

Roles

Governance

Governance is the final arbiter of authority in the Keep Network. The role of Governance is to enable recovery from key compromise by rekeying other roles. Governance has the authority to change the addresses of the Registry Keeper, Panic Button, and the service contracts' Operator Contract Upgraders The rekeying process is currently unspecified.

Registry Keeper

The Registry Keeper maintains the global registry of approved contracts. Each operator contract must be approved by the Registry Keeper before it can be authorized to punish operators or used by a service contract. The Registry Keeper can be rekeyed by Governance.

Panic Button

The Panic Button can disable malicious or malfunctioning contracts that have been previously approved by the Registry Keeper. When a contract is disabled by the Panic Button, its status on the registry changes to reflect this, and it becomes ineligible to penalize operators. Contracts disabled by the Panic Button can not be reactivated. The Panic Button can be rekeyed by Governance.

Operator Contract Upgrader

Each service contract has an Operator Contract Upgrader whose purpose is to manage operator contracts for that service contract. The Operator Contract Upgrader can add new operator contracts to the service contract, and deprecate old ones. The Operator Contract Upgraders can be rekeyed by Governance.

Authorizer

Each operator has an Authorizer whose purpose is to determine which operator contracts may punish the operator for misbehavior. The operator can only perform work for authorized operator contracts. The Authorizer cannot be rekeyed except by undelegating and redelegating.

Authorizations

The Registry and Panic Button

The registry tracks all Keep Org -approved contracts. Operator contracts have a special status on the registry, reflecting the ability of the Panic Button to disable them.

Each operator contract’s status may be NULL, APPROVED or DISABLED.

A status of NULL is the default and means that the operator contract has not been approved by the Registry Keeper.

When the Registry Keeper approves a operator contract, its status switches to APPROVED in the registry. Approved operator contracts can be authorized to punish operators, and service contracts may utilize them.

The Panic Button can be used to set the status of an APPROVED contract to DISABLED. Operator Contracts disabled with the Panic Button cannot be re-enabled, and disabled contracts may not punish operators nor be selected by service contracts to perform work.

Staking contracts: authorized operator contracts

Staking contracts hold staked tokens, enforce staking rules, and punish misbehaving operators on behalf of authorized operator contracts. For this purpose, each staking contract tracks which operator contracts have been authorized by which addresses.

The authorized operator contracts are a mapping of (address authorizer, address operator_contract) → status.

The status of a contract may be either NULL or AUTHORIZED. A status of NULL is the default and means the operator contract is not authorized. A status of AUTHORIZED means that the operator contract may impose punishments on those operators who have assigned that authorizer as their Authorizer.

To authorize an operator contract on a staking contract, the operator contract must have been APPROVED on the registry. Once a operator contract has been authorized, authorization cannot be withdrawn by the authorizer. However, a operator contract that has been DISABLED by the Panic Button may not punish stakers.

Service contracts: used operator contracts

Service contracts use the basic functionality performed by operator contracts, to provide useful services to the public. Service contracts can use multiple different versions of operator contracts to perform the operator contract functions. To permit system upgrades, the list of used operator contracts can be updated with proper authorization.

A service contract is deployed with zero operator contracts, rendering the service contract inactive until at least one operator contract is activated.

Each service contract has its own Operator Contract Upgrader who can add used operator contracts. To add a used operator contract, the operator contract must have been APPROVED on the registry, and the interface it claims to implement must match what the service contract expects.

If an operator contract has been DISABLED by the Panic Button, the service contract must not use its functionality. This must be checked when the service contract selects an operator contract.

Impact of compromised keys

Individual keys
Registry Keeper

A compromised Registry Keeper can approve arbitrary operator contracts. However, using those operator contracts for a service contract requires the service contract’s Operator Contract Upgrader as well. Thus, a compromised Registry Keeper cannot endanger customers alone. Similarly, stakers' funds are safe from being slashed by malicious contracts unless their Authorizers are also compromised.

Panic Button

A compromised Panic Button can disable arbitrary operator contracts and halt all network services. Recovery is impossible until Governance has rekeyed the Panic Button.

This is inevitable due to the functionality of the Panic Button, but the impact could be mitigated by setting a cap on how many times the Panic Button can be invoked within a particular timeframe. However, if a compromised Registry Keeper approves a large number of malicious contracts, a rate-limited Panic Button would be overwhelmed and unable to disable them all. This could be further mitigated by rate-limiting the Registry Keeper similarly.

Operator Contract Upgrader

A compromised Operator Contract Upgrader can activate operator contracts on the affected service contract within the strict constraints of the upgrade process. It is unlikely that an uncompromised Registry Keeper would have approved an operator contract that would satisfy the constraints yet cause a significant impact on the service contract.

Authorizer

If only the Authorizer of some staker is compromised, the attacker can authorize operator contracts that have been approved by the Registry Keeper, and that use the same staking contract as the staker.

This has a very limited negative impact unless the Registry Keeper has approved a faulty or malicious operator contract.

Key combinations
Registry Keeper + Operator Contract Upgrader

If a malicious operator contract can get globally approved, the impacted service contract can be completely subverted by switching all work to the malicious operator contract.

While already existing operations should finish normally, the service contract can be rendered effectively useless for new requests.

Registry Keeper + Authorizer

If the Registry Keeper approves a malicious operator contract, and a staker’s Authorizer authorizes it, the malicious contract can be used to steal staked funds within the constraints of tattletale rewards: seizing up to 5% to the attacker and burning the rest.

Upgrade processes

Operator contract upgrade

Operator contracts are immutable, and are upgraded by deploying a new version in a separate contract. The Registry Keeper then approves the new contract on the registry, and operators are able to authorize it. Once authorized by a sufficient number of stakers, the contract can be added into the used operator contracts of a service contract.

Operator contracts can be upgraded without losing service contract state, but critical state is held within the operator contract and cannot be migrated.

  1. Deploy the new operator contract

  2. Approve the operator contract on the registry

  3. Wait for stakers to authorize the operator contract

  4. Activate the operator contract on the relevant service contract/s

Service contract upgrade

Because service contracts don’t impact the security of staked tokens, they can be upgraded in-place without migrating to a new address.

New service contract

A new service contract is deployed on-chain and listed on the registry.

If the service contract doesn’t rely on an operator contract exclusive to itself, it can be deployed after the operator contracts it uses are in place.

Otherwise the service contract must be deployed first, inactive because it has no operator contracts it uses. Once the address of the service contract is determined, the operator contract is deployed, approved on the registry, and authorized by stakers. The operator contract can now be activated on the service contract, making it ready to provide services.

  1. Deploy the new service contract

  2. Deploy a new operator contract serving the new service contract

  3. Approve the operator contract on the registry

  4. Wait for stakers to authorize the operator contract

  5. Activate the operator contract on the service contract

Staking contract upgrades

Staking contracts can be upgraded by deploying a new version, and waiting for stakers to migrate by withdrawing their stakes on the old contract and staking them again on the new contract. While stakers are migrating, new operator contracts using the new staking contract should be deployed. Once stakers have migrated and approved the new operator contracts, the contracts can be activated on service contracts.

  1. Deploy the new staking contract

  2. Deploy new operator contracts recognizing the new staking contract

  3. Approve the operator contracts on the registry

  4. Wait for stakers to migrate to the new staking contract

  5. Wait for stakers to authorize the new operator contracts

  6. Activate the operator contracts on the service contracts

Token upgrade

The upgrade process makes it possible to even hard-fork the token without disrupting service contract user experience:

  1. Deploy the new token contract

  2. Deploy a migration contract that lets holders convert old tokens to new tokens

  3. Deploy a new staking contract for the new tokens

  4. Deploy new operator contracts recognizing the new token and staking contract

  5. Approve the operator contracts on the registry

  6. Wait for stakers to convert their tokens, stake on the new contract and authorize the new operator contracts

  7. Activate the operator contracts on the service contracts

Glossary

Stake

An amount of KEEP that is bonded in order to participate in the threshold relay and, optionally, the Keep network. Part or all of this can be removed from escrow as penalties for misbehavior, while part or all of it can be refunded if and when a participant chooses to withdraw in orderly fashion from the network and relay.

Staker

A staking client that has a stake, but may not yet be in a signing group.

Minimum Stake Amount

The minimum stake amount that will make a staking client a staker, as required by the staking smart contract.

Stake Amount

Total KEEP deposited for a single stake.

Signing Member

One member of one complete signing group in the threshold relay.

Signing Group

One complete signing group in the threshold relay.

Lead Signing Group

The signing group that will produce the next relay entry candidate (due to being the result of $E_i mod N$ with $E_i$ being the current entry and $N$ being the number of groups). If this group fails to respond to the request in time, the lead responsibility may shift to another group.

Relay Entry Candidate

A random number generated by the threshold relay that has not yet been finalized on the blockchain; may be invalid.

Relay Entry

A relay entry candidate that has been finalized on the blockchain; may be invalid.

Keep Client

The entire application running on a user’s system, which contains multiple subclients for the various pieces of the Keep system.

Staking Client

The part of the Keep Client that stakes and participates in the threshold relay.

Verifying Client

Verifies entries on-chain and reports invalid entries. Optional, does not require a stake. Reward for identifying an invalid random number on the chain.

Provider Client

The Keep Provider piece of the application, which can in turn have workers for various Keep types.

Keep Type

The functionality that the given Keep relies on for providing security. e.g. an SHM (Secure Hardware Module) Keep, SMPC (Secure Multi-Party Computation) Keep, Proxy Reencryption Keep, etc.

Provider Worker

One worker that runs the code to allow a provider client to participate in a given Keep Type.

Keep Provider

One economic entity in the Keep network; has a stake, must participate in a signing group as a single member.

Keep

Up to 1MB of encrypted storage across one or more Keep Providers.

KEEP

Token used to stake. Can be represented as a K with a vertical bar through it.

Keep Owner, Delegate, Requester are described in the whitepaper.


1. The importance, from a security perspective, of the seed value goes away almost immediately in a functioning network.
2. https://dfinity.org/pdf-viewer/library/dfinity-consensus.pdf
3. D. Boneh, B. Lynn and H. Shacham, “Short signatures from the Weil pairing”, Advances in Cryptology – ASIACRYPT 2001, Lecture Notes in Computer Science, 2248 (2001), 514–532. Full version: Journal of Cryptology, 17 (2004), 297–319.
4. R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Advances in Cryptology — EUROCRYPT ’99: International Conference on the Theory and Application of Cryptographic Techniques Prague, Czech Republic, May 2–6, 1999 Proceedings, chapter Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, pages 295–310. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999 ; http://groups.csail.mit.edu/cis/pubs/stasio/vss.ps.gz
5. This is needed if changes to the active groups can be made while waiting for an entry.
6. The way of calculating rewards is inevitably prone to off-by-one errors somewhere and doing the incrementing at request time seems the simplest.