:toc: macro

= Random Beacon Distributed Key Generation

:toclevels: 4

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.

ifndef::yellowpaper[toc::[]]

:leveloffset: +1

include::terms.adoc[]

include::concepts.adoc[]

:leveloffset: -1


== Overview

Input: _V~i~, 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 _V~j~_
should _P_ be chosen as the group to produce
the __j__th 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 _P~i~_

After phase _p_, the nodes that failed to broadcast a required message
will be added to _IA~p~_.
Nodes that broadcast a malformed message may be added to _IA~p~_ or _DQ~p~_.

[#phase-1,reftext="Phase 1"]
=== Phase 1. Ephemeral key generation

To ensure integrity in later parts of the DKG protocol,
we will require every _P~i~_ to generate
an ephemeral ECDH keypair _(x~ij~, y~ij~)_ for every other member _P~j~_ 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
[source, python]
----
include::dkg.py[tags=phase-1]
----

[#phase-2,reftext="Phase 2"]
=== Phase 2. Ephemeral ECDH

Every node in _P_ has now published a valid list of ephemeral ECDH pubkeys.
_P~i~_ will perform ECDH with every _P~j~_ in _P_ to create _k~ij~_.

.Phase 2
[source, python]
----
include::dkg.py[tags=phase-2]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-2]
----

[#phase-3,reftext="Phase 3"]
=== Phase 3. Polynomial generation

Every node in _G~3~_ has, for every other node in _G~3~_, 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 _f~i~(z)_ and _g~i~(z)_ of degree _M_ and calculate
other players' shares as points on these polynomials. Additionally, calculate
Pedersen commitments to the coefficients of _f~i~(z)_ using the coefficients
of _g~i~(z)_.

Shares to _P~j~_ are encrypted with the symmetric key _K~ij~ = K~ji~_
shared by _P~i~_ and _P~j~_.
Commitments and encrypted shares are broadcast to other players.

.Phase 3
[source, python]
----
include::dkg.py[tags=phase-3]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-3]
----

[#phase-4,reftext="Phase 4"]
=== 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
[source, python]
----
include::dkg.py[tags=phase-4]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-4]
----

[#phase-5,reftext="Phase 5"]
=== 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
[source, python]
----
include::dkg.py[tags=phase-5]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-5]
----

[#phase-6,reftext="Phase 6"]
=== Phase 6: Share calculation

Each player sets their share _x~i~_ of the secret _X_ to equal the sum of all
shares _s~ji~_ as per GJKR. _X_ equals the sum of shares _s~j0~_.

.Phase 6
[source, python]
----
include::dkg.py[tags=phase-6]
----

[#phase-7,reftext="Phase 7"]
=== Phase 7: Public key share points

Each player broadcasts their _A~ik~_ values.

.Phase 7
[source, python]
----
include::dkg.py[tags=phase-7]
----

[#phase-8,reftext="Phase 8"]
=== Phase 8: Public key share validation

Each player validates the values received in <<phase-7>>.

.Phase 8
[source, python]
----
include::dkg.py[tags=phase-8]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-8]
----

[#phase-9,reftext="Phase 9"]
=== 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 _E~jm~_ and not just _E~mj~_. 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 _M~nofail~ = M/2_ the impact of this is reduced to a
manageable level.

.Phase 9
[source, python]
----
include::dkg.py[tags=phase-9]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-9]
----

[#phase-10,reftext="Phase 10"]
=== Phase 10: Disqualified share opening

All active players in _G~10~_ broadcast the keys they share with
players in _DQ~9~_, so the reconstruction of Pedersen-VSS can be done
offline.

.Phase 10
[source, python]
----
include::dkg.py[tags=phase-10]
----

[#phase-11,reftext="Phase 11"]
=== Phase 11: Disqualified share reconstruction

Decrypt and reconstruct _z~m~_ for every participant _P~m~_ that presented
valid shares in <<phase-3>> but whose public key shares in <<phase-7>> were invalid.
Calculate _y~m~ = z~m~ * P1_ for each reconstructed _z~m~_.

.Phase 11
[source, python]
----
include::dkg.py[tags=phase-11]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-11]
----

[#phase-12,reftext="Phase 12"]
=== Phase 12: Public key reconstruction

Let _G~12~ = G~11~_

Combine _y~j~_ for all participants in _G~6~_ 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
[source, python]
----
include::dkg.py[tags=phase-12]
----

.Utility functions
[source, python]
----
include::dkg_util.py[tags=phase-12]
----

[#phase-13,reftext="Phase 13"]
=== Phase 13: Result establishment

Let _IA = IA~1~ + IA~2~ + ... + IA~10~_

Let _DQ = DQ~1~ + DQ~2~ + ... + DQ~10~_

[source, python]
----
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,reftext="Phase 14"]
=== 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.

[source, python]
----
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.

[bibliography]
== 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
