Semi-Trusted-Party (STP) threshold-OPRF key-update Protocol

[[[ note this is a draft, which matches the current implementation, changes are still expected ]]]

This document specifies a proposal for a semi-robust threshold-OPRF
key- update protocol that can work for small deployments with a small
number of parties and infrequent executions. Semi-robust means that
the protocol can fail in the DKG phase if any party aborts, but can
still succeed later if some parties are detected cheating or
aborting. If someone aborts in the first DKG phase then the protocol
needs to run again, possibly after kicking out misbehaving
parties. This protocol does support maximum 127 peers. This is
probably way too much for a generic threshold protocol, but it
might work in very special circumstances.

Broadcast is implemented by the semi-trusted party (STP) opening a
channel to each peer secured by the peers long-term encryption
key. Every message is routed through the STP.

Peer long-term encryption keys can be either TLS-based, or
Noise_XK-based (https://noiseexplorer.com/patterns/XK/). In the latter
case the long-term public keys must be known and validated in advance
by the STP.

The long-term signing keys of peers MUST be known by all parties
before the start of the protocol.

This protocol is based on the threshold updatable OPRF as described in
section 6.2 of [JKR19].

The basic building blocks for this protocol are the FT-Joint-DL-VSS
protocol for the DKGs as specified in Appendix H figure 7 of [GRR98],
and the Multi-party Multiplication protocol which given the sharings
of secret `a` and secret `b` generates a sharing of the product `a·b`
without learning anything about either secret. The multi-party
multiplication is based on the FT-Mult protocol shown in Fig. 6 from
[GRR98].

The update protocol from old key kc to new key kc' works as follows
(quote from the JKR paper):

The distributed update protocol assumes that n servers S1,...,Sn have
a sharing (k1,..., kn) of a key k. To produce a new key k′ the servers
jointly generate a sharing ρ1,...,ρn of a random secret ρ ∈Zq and run
distributed multiplication FT-Mult(kc,ρ) to generate shares
k′1,...,k′n of the new key defined as k′ = ρ · k. Finally, each server
Si sends to clients its share ρi from which the recipient reconstructs
ρ and sets ∆:= ρ [= k′/k].

------<=[ Roles                                         ]=>-----------

There is three roles in this protocol:

 - semi-trusted party (STP) orchestrating the communication between
   all other participants.
 - dealers: exactly 2t+1 participants (having shares of both kc and p)
   are acting as dealers
 - all participants (peers and STP)

------<=[ Prototocol Phases                             ]=>-----------

Some of the following phases are optional and only executed if the
previous step revealed a misbehaving party, these phases make the
protocol robust to also successfully complete in the presence of
misbehaving parties. Phases 3, 5, 7, and 9 are these optional
corrective phases.

0. pre-condition: all parties know the long-term signing keys of each
   other. STP ensures that n >= 2t+1 and at least 2t+1 of them hold
   shares of the old key kc, otherwise abort.

1. Initialization, sharing of basic parameters, setup of p2p noise
   channels.

2. execute STP-DKG for all peers that hold a share of kc, calculating
   sharing of ρ, if a fast-track VSPS check fails disqualify the
   cheaters. Abort if some other hard-fail occurs during the DKG.

3. DKG dealers defend against complaints by revealing contested
   shares. Based on this peers disqualify any misbehaving peers from
   contributing to the result of the DKG.

4. execute the FT-Mult protocol, to calculate FT-Mult(kc, ρ),
   generating sharings of kc'.

5. Verify the commitments matching the shares of step 2, if there is
   failures to verify run a recovery procedure to correct the failing
   shares/commitments.

6. Dealers run ZK proofs on the correctness of their 𝓒_i0
   commitment. If any of these fails, run a recovery procedure to
   correct the commitment.

7. Recover from failed ZK proofs, reconstructing the failing dealer
   P_i secret λ_iα_iβ_i and recalculating the correct 𝓒_i0 commitment.

8. Aggregate the final shares and commitments. Run a Fast-track VSPS
   check on the final commitments for the shares of the
   multiplications. If any of these fails, run a recovery procedure.

9. Recovery of λ_iα_iβ_i for any dealer who fails the VSPS check and
   deterministically re-share the recovered secret.

10. Finalization of computation: parties send their ρ_i shares to the
   STP which reconstructs ρ and computes ∆=1/p.Parties replace their
   kc share with their kc` share.

------<=[ Simplified API                                ]=>-----------

Since the protocol consists of many steps, it is recommended to
abstract the API to the following schema:

0. Initialize
While not done and not error:
  1. Allocate input buffers
  2. input = receive()
  3. allocate output buffer
  4. run next step of protocol
  5. if there is output: send(output)
6. Post-processing

This simple schema simplifies the load of an implementer using this
protocol, reducing opportunities for errors and provides strict
security. It also allows full abstraction of the underlying
communication media.

The reference implementation in toprf-update.c follows this schema for
both the STP and the peers.

------<=[ Protocol transcript                           ]=>-----------

Transcript - all broadcast messages are accumulated into a transcript
by each peer and the semi-trusted party, at the end of the protocol
all parties publish their signed transcripts and only if all
signatures are correct and the transcripts match, is the protocol
successful.

The transcript is a hash, that is initialized with the string:
   "stp update session transcript"

in pseudo-code:

```
   transcript_state = hash_init()
   transcript_state = hash_update("stp update session transcript")
```

Updating the transcript first updates the hash with the canonical
32bit size of the message to be added to the transcript, then the
message itself is added to the hash.

```
    transcript_state = hash_update(transcript_state, I2OSP(len(msg))
    transcript_state = hash_update(transcript_state, msg)
```

A function `update_ts` can be used as a high-level interface to
updating the transcript with messages:

```
update_ts(state,msg)
    state = hash_update(state, I2OSP(len(msg))
    state = hash_update(state, msg)
    return state
```

------<=[ Session id                                    ]=>-----------

Every execution of the protocol starts by the participants
establishing a unique and fresh session id, this is to ensure that no
messages can be replayed. The session id is a 256 bit (32B) random
value of cryptographic quality.

Every message sent MUST contain a valid session id.

The session id is established in the very first steps of the protocol,
where each peer generates a 32B nonce, and broadcasts this, and - upon
reception of all peers - hashes the STP session id nonce together with
the concatenation of the peers nonces (in order of the peers) to
establish the final session id.

------<=[ Message header                                ]=>-----------

All messages have a message header:

  uint8  signature[32]
  uint0  sign_here[0]
  uint8  type = 0x81
  uint8  version = 0
  uint8  messageno
  uint32 len
  uint8  from
  uint8  to
  uint64 timestamp
  uint8  sessionid[32]

The header begins with the signature of the sender over the rest of
the header and all of the data.

The field sign_here is a zero-bit field, only used for addressing the
start of the data to be signed or verified.

The next field is the protocol type identifier. STP Update has an
identifier value of 129 (0x81). And currently a version number of 0.

The following field in the header is really a state identifier. A
recipient MUST verify that the messageno is matching with the expected
number related to the state of the protocol.

The len field MUST be equal to the size of the packet received on the
network including the packet header.

The `from` field is simply the index of the peer, since peers are
indexed starting from 1, the value 0 is used for the semi-trusted
party. Any value greater than 128 is invalid. The state defines from
whom to receive messages, and thus the from field MUST be validated
against these expectations.

The `to` field is similar to the `from` field, with the difference
that the value 0xff is reserved for broadcast messages. The peer (or
STP) MUST validate that it is indeed the recipient of a given message.

The timestamp field is just a 64bit timestamp as seconds elapsed since
1970/01/01, for peers that have no accurate clock themselves but do
have an RTC, the first initiating message from the STP SHOULD be used
as a reference for synchronizing during the protocol.


------<=[ Message signatures                            ]=>-----------

Every message MUST be signed using the sender peers long-term signing
key. The signature is made over the complete message.


------<=[ Verifying messages                            ]=>-----------

Whenever a message is received by any participant, they first MUST
check the correctness of the signature:

```
   msg = recv()
   sign_pk = sign_keys[expected_sender_id]
   assert(verify(sign_pk, msg))
```

The recipient MUST also assert the correctness of all the other header
fields:

```
   assert(msg.type == 0x81)
   assert(msg.version == 0)
   assert(msg.sessionid == sessionid)
   assert(msg.messageno == expected_messageno)
   assert(msg.from == expected_sender_id)
   assert(msg.to == (own_peer_id or 0xff))
   assert(ref_ts <= msg.ts < ref_ts + timeout))
   ref_ts = msg.ts
```

The value `timeout` should be configurable and be set to the smallest
value that doesn't cause protocol aborts due to slow responses.

If at any step of the protocol any participant receives one or more
messages that fail these checks, the participant MUST abort the
protocol and log all violations and if possible alert the user.

------<=[ Message transmission                          ]=>-----------

A higher level message transmission interface can be provided, for
sending:

```
msg = send_msg(msgno, from, to, sign_sk, session_id, data)
    ts = timestamp()
    msg = type: 0x81, version: 0, messageno: msgno, len: len(header) + len(data) + len(sig), from: from, to: to, ts: ts, data
    sig = sign(sign_sk, msg)
    return msg
```

And for validating incoming messages:

```

data = recv_msg(msgno, from, to, ref_ts, sign_pk, session_id, msg)
    assert(verify(sign_pk, msg)
    assert(msg.type == 0x81)
    assert(msg.version == 0)
    assert(msg.messageno == msgno)
    assert(msg.len == len(msg))
    assert(msg.from == from)
    assert(msg.to == to)
    assert(ref_ts < msg.ts < ref_ts + timeout))

    if msg.to == 0xff:
        update_ts(state,msg)
```

The parameters `msgno`, `from`, `to`, `session_id` should be the
values expected according to the current protocol state.

------<=[ Cheater detection                             ]=>-----------

All participants MUST report to the user all errors that can identify
cheating peers in any given step. For each detected cheating peer the
participants MUST record and log the following information:

 - the current protocol step,
 - the violating peer,
 - the other peer involved, and
 - the type of violation

In order to detect other misbehaving peers in the current step,
processing for the rest of the SHOULD peers continue until the end of
the current step. Any further violations should be recorded as above.

Before the next message to the peers is sent, the STP must
check if there are no noted violations, if so the STP aborts and
reports all violators with their parameters to the user.

Abort conditions include any errors detected by recv_msg(), or when
the number of complaints is more than t for one peer, or more than t^2
in total.

Participants should log all broadcast interactions, so that any
post-mortem investigation can identify cheaters.

------<=[ Second generator point                        ]=>-----------

FT-Mult and the FT-Joint-DL_VSS DKG require a second generator on the
group. We generate it in the following manner:

  h = voprf_hash_to_group(blake2b(hash,"nothing up my sleeve number"))

Where voprf_hash_to_groups is according to [RFC9497].

------<=[ The FT-MULT sub-protocol                      ]=>-----------

FT-MULT, calculates the product of two values α,β both shared in the
same (n,t) threshold sharing setup.

The FT-MULT sub-protocol is based on the "Fast-track multiplication"
as in fig. 6 of [GRR98], page 19. It goes as follows:

------<=[ FT-MULT pre-conditions                        ]=>-----------

1. All Peers use TLS or the STP knows long-term encryption keys for all
   peers.

2. STP and peers MUST know long-term signing keys of everyone in the
   protocol.

3. There is at least 2t+1 peers holding shares of both operands
   participating in the protocol, 2t+1 of them will be acting as
   dealers, the rest of the participants act as passive receivers.

4. Each dealer P_i has
   - a share of α: α_i = 𝑓_α(i), one of the values to multiply
   - a share of β: β_i = 𝑓_β(i), the other value to multiply
   - a share of 𝑟: ρ_i = 𝑟(i), a blinding factor for the homomorphic commitment of α
   - a share of 𝑠: σ_i = 𝑠(i), blinding factor for the homomorphic commitment of β

public inputs, for i:=0..n
   𝓐_i = 𝓗(α_i,ρ_i) = g^(α_i)*h^(ρ_i)
   𝓑_i = 𝓗(β_i,σ_i) = g^(β_i)*h^(σ_i)

These conditions MUST be guaranteed by the initialization and DKG
phases of this protocol.

------<=[ FT-MULT VSPS check                            ]=>-----------

A VSPS check on a vector of homomorphic commitments verifies that
these correspond to a polynomial of degree t. The protocol relies on
this check heavily.

VSPS Check on 𝓒_i, i:=1..n,

    t+1                   t+1
     Π  𝓒_i^Δ_i     =      Π  𝓒_(i+t+1)^Δ_i
    i=0                   i=0

                 t
    where Δ'_i = Σ λ_(j,i)*δ^j
                j=0

where λ is an inverted Vandermonde matrix over 0..t for the lhs, and
t+1..2t+1 for the rhs.

------<=[ Phase 1 - Initialization                      ]=>-----------

In this phase the protocol establishes a joint session id, and
Noise_XK protected channels between all peers.

Until the joint session id is established, the session id of shared in
the very first message of the STP is used.

This phase starts by the STP executing the `toprf_update_start_stp()`
function, which receives the parameters to the protocol, such as the
values N and T, the keyid of the record do update, the long-term
signatures keys of the peers. The result of this function is a initial
message to be sent to the peers, notifying them of the initiation of
the protocol, and all the essential parameters.

This initial message contains:
 - the public long-term signature key of the STP,
 - a hash of the DST,
 - a keyid of the key to be updated,
 - and an initial session_id.

The peers receive this message, and check if the public key of the STP
is authorized to operate on this key, they abort if the STP is
unauthorized.

------<=[ 1. Peer shares sid nonce                      ]=>-----------

The peers all receive the initial message from the STP.

This message contains a keyid, so that the client can check and load
the corresponding kc key share and corresponding long-term signature
keys of the peers, information stored in an internal state.

Finally the peers each start their own protocol loop, in which they
generate their own session id nonce and share the commitment to their
share of kc. This nonce and commitment is broadcast via the STP.

------<=[ 2. STP sets sessionid and forwards keys       ]=>-----------

STP receives all messages from the peers, then
  - verifies each of them,
  - extracts the session id nonce and the commitment for their kc
    share from each,
  - hashes its own and the peers nonces in order
  - sets the final session id to the result
  - wraps all peer messages in a STP broadcast envelope message using
    the new session id.
  - adds the broadcast envelope message to the global transcript, and
  - sends this message to all peers.

session_id = hash(stp_session_id  |
                  peer1_sid_nonce |
                  peer2_sid_nonce |
                  ...             |
                  peerN_sid_nonce)

the stp_session_id is distributed to all peers in the first message of
the protocol.

------<=[ 3. peers set sessionid & noise keys           ]=>-----------

After verifying, adding it to the transcript and unwrapping the
broadcast message envelope from the STP, the peers calculate the
session id like the STP did in the previous step. Furthermore they
verify that the sessionid they calculated is the same as the session
id used in the broadcast envelope header.

Finally the peers each initiate a Noise XK handshake message to all
peers.

------<=[ 4. STP routes handshakes between peers        ]=>-----------

The TP receives all 1st handshake messages from all peers and routes
them correctly to their destination. These messages are not broadcast,
each of them is a P2P message. The benefit of the STP forming a star
topology here is, that the peers can be on very different physical
networks (wifi, lora, uart, nfc, usb, bluetooth, etc) and only the TP
needs to be able to connect to all of them.

------<=[ 5. each peer responds to each handshake       ]=>-----------

Peer receives noise handshake1 from each peer and responds with
handshake2 answer to each peer.

------<=[ 6. STP routes handshakes between peers        ]=>-----------

STP just like in step 4. routes all P2P messages from all peers to the
correct recipients of the messages.

------<=[ 7. Peers conclude handshakes, start p DKG     ]=>-----------

This step concludes the Initialization phase and starts the DKG phase.

The peers receive the 3rd and final message of the Noise handshakes,
completing the setup of these Noise-protected peer-to-peer channels.

------<=[ Phase 2 - STP DKG of p                        ]=>-----------

The peers then start the DKG phase during which they collectively
generate the shared delta p factor. The underlying algorithm is
FT-Joint-DL-VSS from fig 7 in Appendix H of [GRR98].

1. Player P_i chooses a random value r_i and shares it using the DL-VSS
   protocol, Denote by α_i,j ,ρ_i,j the share player P_i gives to player P_j. The
   value 𝓐_i,j = g^(α_i,j)*h^(ρ_i,j) is public.

Since we might be forced to disclose the shares in case the peer gets
accused with cheating, but we don't want to reveal more information
than necessary we derive a dedicated key for the shares of the p value
to be shared/generated. The key for each of these shares is generated
in the following way:

We extract the shared key from the noise session. And run it through a

```
share_key = HKDF-expand("key for encryption of p share for []", noise_key)
```

Here the [] is replaced by the index of the peer who is the recipient
of this share.

Encryption of the shares is a simple XSalsa20 stream cipher with the
share_key, and for this step an all-zero nonce. Instead of the usual
poly1305 MAC, which is not key-committing (and thus would allow a peer
to cheat) we calculate an HMAC over the ciphertext with the share_key.

The shares α_i,j ,ρ_i,j for the p DKG are encrypted using the above
specified procedure.

The encrypted shares and their commitments 𝓐_i,j are stored by the
peer for later distribution.

The HMAC for each encrypted share is broadcast together with
the hash of the concatenation of all 𝓐_i,j commitments:

      C_i = hash(𝓐_i0 | 𝓐_i1 | .. | 𝓐_in)

```
encrypted_shares = []
hmacs = []
for i in 1..N
   encrypted_shares[i] = encrypt_share(send_session[i], share[i])
   hmacs[i] = hmac(send_session[i].key, encrypted_shares[i])

C_i = hash(commitments)
msg_6 = send_msg(6, peerid, 0xff, peer_sign_sk, session_id, {C_i, hmacs})
```

------<=[ 8. STP collects and broadcasts all C_i commitments ]=>-------

STP standard broadcast procedure expanded here, referred to later:

  1. receives the messages from each peer
  2. validates the message using recv_msg()
  3. concatenates all received messages into a new message
  4. signs the message of messages
  5. adds this the message of messages and its signature to the transcript
  6. sends it to all peers

In this case the STP keeps a copy for later of the broadcast
commitment hashes and of the MACs of the encrypted shares.

```
p_C_hashes = []
p_hmacs = []
msgs = []
for i in 1..N
   msg_6 = recv(i)
   data = recv_msg(6, i, 0xff, ref_ts, peer_sign_pks[i], session_id, msg_6)
   p_C_hashes[i], p_hmacs[i] = data
   msgs = msgs | msg_6

msg_7 = send_msg(7, 0, 0xff, stp_sign_sk, session_id, msgs)

state = update_ts(state, msg_7)

broadcast(msg_7)
```

------<=[ 9. Peers receive commitment hashes & HMACs    ]=>-------

The peers receive all C_i commitment hashes and share-HMACs and for
the p DKGs and broadcast their respective 𝓐 commitment vectors:

```
msg_7 = recv()
msgs = recv_msg(7, 0, 0xff, ref_ts, stp_sign_pk, session_id, msg_7)
state = update_ts(state, msg_7)

p_C_hashes = []
p_share_macs = []
for i in 1..N
   msg_6 = msgs[i]
   data = = recv_msg(6, i, 0xff, ref_ts, peer_sign_pks[i], session_id, msg_6)
   p_C_hashes[i], p_share_macs[i] = data
   msgs = msgs | msg_6

msg_8 = send_msg(8, peerid, 0xff, peer_sign_sk, session_id, p_A)
```

------<=[ 12. STP broadcasts all commitments            ]=>-------

This is a regular STP broadcast step. Besides keeping a copy of all
commitments, the STP does also verify the commitment hashes and does
an FT-VSPS check on the commitments.

The STP verifies the VSPS property of the sum of the shared secrets by
running VSPS-Check on 𝓐_i,..,𝓐_n where

           𝓐_j = Π 𝓐_i,j
                 i

If this check fails the STP runs VSPS-Checks on each individual
sharing. These checks are informational, and should guide the operator
in detecting and deterring cheaters.

```
p_commitments[][]
msgs = []
for i in 1..N
   msg_8 = recv(i)
   data = recv_msg(8, i, 0xff, ref_ts, peer_sign_pks[i], session_id, msg_8)
   p_commitments[i] = data
   msgs = msgs | msg_6
   if p_C_hashes != hash(p_commitments[i])
      report(i)

C = []
for i in 1..n
   C[i] = sum(p_commitments[j][i] for j in 1..n)

if vsps(C) fails:
   for i..n
      if vsps(p_commitments[i]) fails report(i)

msg_9 = send_msg(9, 0, 0xff, stp_sign_sk, session_id, msgs)

state = update_ts(state, msg_9)

broadcast(msg_9)
```

------<=[ 11. Peers receive commitments, send shares    ]=>-------

The peers receive the broadcast commitments of all dealers for the
DKG, they check the commitment hashes and abort if they don't match,
otherwise they store the commitments for the next step.

Peers privately send the encrypted shares to each recipient.

```
msg_9 = recv()
msgs = recv_msg(9, 0, 0xff, ref_ts, stp_sign_pk, session_id, msg_9)
state = update_ts(state, msg_9)

p_commitments = [][]
for i in 1..N
   msg_8 = msgs[i]
   data = recv_msg(8, i, 0xff, ref_ts, peer_sign_pks[i], session_id, msg_8)
   p_commitments[i] = data
   assert p_C_hashes[i] == hash(p_commitments[i])

msg_10s = []
for i in 1..N
   msg = send_msg(9, peerid, i, peer_sign_sk, session_id, p_encrypted_shares[i])
   send(msg)
```

------<=[ 12. STP routes shares to recipients           ]=>-------

STP just routes all P2P messages from all peers to the correct
recipients of the messages.

```
for i in 1..N
   msgs = recv(i)
   for j in 1..N
       send(j, msgs[j])
```

------<=[ 13. each peer receives shares & check commitments   ]=>-------

The peers receive the private messages containing their shares. The
peers verify the shares against the previously broadcast commitment
vectors. For each
    𝓐_i,j == g^(α_i,j) * h^(ρ_i,j)
pair that fails, a complaint against the peer producing the
conflicting commitment and share is logged in an array, which is
broadcast to everyone.

```
s = []
for i in 1..N
   msg = recv()
   pkt = recv_msg(9, i, peerid, ref_ts, peer_sign_pks[i], session_id, msg)
   final_noise_handshake, p_encrypted_share = pkt
   recv_session[i] = noise_session_decrypt(recv_session[i], final_noise_handshake)
   key=derive_key(recv_session[i], i)
   p_α[i,peerid],p_ρ[i,peerid] = share_decrypt(p_encrypted_share)

p_complaints = []
for i in 1..N
   if p_commitment[i,peerid] != g^(p_α[i,peerid])*h^(p_ρ[i,peerid])
      p_complaints = p_complaints | i

data = len(p_complaints) | p_complaints
msg = send_msg(10, peerid, 0xff, peer_sign_sk, session_id, data)
send(msg)

```

------<=[ 14. STP collects complaints                         ]=>-------

Another receive-verify-collect-sign-transcribe-broadcast
instantiation. The STP keeps a copy of all complaints.

If any peer complaints about more than t peers, that complaining peer
is a cheater, and must be disqualified. Furthermore if there are in
total more than t^2 complaints there are multiple cheaters and the
protocol must be aborted and new peers must be chosen in case a rerun
is initiated.

```
p_complaints = []
msgs = []
for i in 1..N
   msg_10 = recv(i)
   data = recv_msg(10, i, 0xff, ref_ts, peer_sign_pks[i], session_id, msg_10)
   p_complaints_i = data
   assert(len(p_complaints_i) < t)
   p_complaints = p_complaints | p_complaints_i
   msgs = msgs | msg_10

assert(len(complaints) < t^2)

msg_11 = send_msg(11, 0, 0xff, stp_sign_sk, session_id, msgs)

state = update_ts(state, msg_11)

broadcast(msg_11)
```

The next phase of the protocol depends on the number of complaints
received, if none then the next phase is finishing, otherwise the next
phase is complaint analysis.

If the next STP phase is complaint analysis (there are complaints) the
next input buffer size depends on the number of complaints against
each peer.

Each complaint is answered by the encrypted shares and the symmetric
encryption key used to encrypt these shares of the accused belonging to
the complainer. Each accused packs all answers into one message.

------<=[ 15. Each peer receives all complaints               ]=>-------

All complaint messages broadcast are received by each peer. If peer_i
is being complained about by peer_j, peer_i broadcasts the
corresponding encrypted shares and the symmetric encryption key that
was used to encrypt them.

If there are no complaints at all the peers skip over to the final
phase step 20., otherwise they engage in the complaint analysis phase.

```
msg_11 = recv()
msgs = recv_msg(11, 0, 0xff, ref_ts, stp_sign_pk, session_id, msg_11)
state = update_ts(state, msg_11)
defenses = []

for i in 1..N
   msg = msgs[i]
   data = recv_msg(10, i, 0xff, ref_ts, peers_sign_pks[i], session_id, msg)
   p_complaints_len, p_complaints = data

   for k in 0..p_complaints_len
      if p_complaints[k] == peerid
          # complaint about current peer, publish key used to encrypt α_i,j , ρ_i,j
          derive_key(send_session[i].key, "p", i)
          defenses = defenses | {i, key, p_encrypted_shares[i]}

if len(keys) > 0
   msg_12 = send_msg(12, peer, 0xff, peer_sign_sk, session_id, defenses)
   send(msg_12)
```

------<=[ Phase 3 - STP DKG cheater handling            ]=>-----------

If any complaints have been registered in the previous phase,
investigate and neutralize any possible cheaters.

------<=[ 16. STP collects all defenses, verifies&broadcasts them ]=>-------

STP checks if all complaints lodged earlier are answered by the
correct encrypted shares and their keys, by first checking if the
previously recorded MAC successfully verifies the encrypted share with
the disclosed key, and then decrypts the share with this key, and
checks if this satisfies the previously recorded commitment for this
share. If it does, the accuser is reported as a cheater, if the
commitment doesn't match the share, then the accused dealer is
disqualified from the protocol and its shares will not contribute to
the final shared secret.

```
msgs = []
for i in 1..N
    if len(complaints[i]) < 1
        continue

    msg = recv(i)
    p_defenses = recv_msg(12, i, 0xff, ref_ts, peers_sign_pks[i], session_id, msg)
    msgs = msgs | msg
    assert(len(p_defenses) == len(p_complaints[i]))
    for j, key, encrypted_share in p_defenses
       assert j==i
       if p_hmacs[i][peerid] == hmac(key, encrypted_share)
           report(i)
       s,r=decrypt(key, encrypted_share]) or report(i)
       if p_commitments[i][peerid] != g^s * h^r
           report(i)

msg_13 = send_msg(13, 0, 0xff, stp_sign_sk, session_id, msgs)
state = update_ts(state, msg_13)
broadcast(msg_13)
```

------<=[ 17. Peers receive and check all defenses            ]=>-------

Peers receive the encrypted shares, and their encryption keys, and
then run essentially the same step as the STP in the previous step,
then they directly skip to the final phase in the next step.

------<=[ 20. Peers VSPS check, calculate shares and finish   ]=>-------

Players verify the VSPS property of the sum of the shared secrets by
running VSPS-Check on 𝓐_i,..,𝓐_n for p where

           𝓐_j = Π 𝓐_i,j
                 i

If this check fails the players run VSPS-Check on each individual
sharing. Any player that fails this check is disqualified. The number
of all qualified peers (from this step, and the complaint analysis) is
checked that is greater than 1 and then number of disqualified peers
is less than t. If this fails the protocol aborts.

The shares dealt by the qualified peers are summed, creating the final
share. The commitment for this final share is calculated.

To finalize the 2nd phase before concluding the DKG of p, we compare
the transcript hashes of all peers. Thus each peer broadcasts their
own together with the final commitments to all parties.

```
p_C = []
for i in 1..n
   p_C[i] = sum(p_commitments[j][i] for j in 1..n if peer[i] is qualified)
if vsps(p_C) fails:
   for i in 1..n
      if vsps(p_commitments[i]) fails disqualify(p,i)

p_s = 0, p_r = 0
for i in 1..n
   if i is not disqualfied(p):
     p_s += p_shares[i]_s
     p_r += p_shares[i]_r

p_C = g^p_s * h^p_r

transcript = final_ts(state)
msg_20 = send_msg(20, peerid, 0, peer_sign_sk, session_id, {transcript, p_C})
send(msg_20)
```

------<=[ 21. STP receives and verifies all transcripts        ]=>-------

STP receives all transcripts, and asserts that they all match its own
transcript, it reports if any transcript mismatch is detected. It also
does a final VSPS check on the commitments seen.

```
transcript = final_ts(state)

msgs = []
p_commitments = []
for i in 1..N
    msg = recv(i)
    data = recv_msg(20, i, 0xff, ref_ts, peers_sign_pks[i], session_id, msg)
    ts, p_commitments[i] = data
    if ts != transcript
       report transcript mismatch
    msgs = msgs | msg

if vsps(p_commitments) fails:
    report failure

msg_14 = send_msg(14, 0, 0xff, stp_sign_sk, session_id, msgs)
broadcast(msg_14)

------<=[ 22. DKGs END, start FT_Mult                   ]=>-------

All peers receive the broadcasts transcripts and commitments, they run
the same check as the STP in the previous step and abort if any of
these fails. Otherwise the protocol continues with the FT-Mult phase
of calculating kc'=kc*p.

------<=[ Phase 4 - FT-Mult                             ]=>-----------

In this phase we calculate the product (kc') of the original key kc
with p.

All the peers pre-compute the inverted Vandermonde matrix based on the
indices of the dealers for the multiplications, and cache its first
row in their internal state.

Peers start their FT-MULT computation of kc*p. In the following
section we describe the steps for one FT-MULT calculation, we use the
following notation:

 - a share of α: α_i = 𝑓_α(i), one of the values to multiply
 - a share of β: β_i = 𝑓_β(i), the other value to multiply
 - a share of 𝑟: ρ_i = 𝑟(i), a blinding factor for the homomorphic
   commitment of α
 - a share of 𝑠: σ_i = 𝑠(i), blinding factor for the homomorphic
   commitment of β

public inputs, for i:=1..n

 - 𝓐_i = 𝓗(α_i,ρ_i) = g^(α_i)*h^(ρ_i) - the commitments to the
   shares of the value to multiply
 - 𝓑_i = 𝓗(β_i,σ_i) = g^(β_i)*h^(σ_i) - the commitments to the
   shares of the other value to multiply

We denote as a dealer all peers, whose index is smaller or equal to
2(t-1)+1. (we use t to denote the threshold, but we need to decrease
it by one to get the degree of the polynomial)

Each dealer P_i shares λ_iα_iβ_i, using VSS:

   c_ij = 𝑓_αβ,i(j),
   τ_ij = u_i(j),

where 𝑓_αβ,i and u_i, are random polynomials of degree t, such that

   𝑓_αβ,i(0) = λ_iα_iβ_i

(c_ij is a t-sharing of λ_iα_iβ_i, and τ_ij a t-sharing of a random value.)
λ_i is the first row of the inverted Vandermonde matrix, as defined by
GRR98 section 3.1. and pre-computed and cached in this step.

secret information of P_i: share c_ji, τ_ji of λ_jα_jβ_j
public information:
𝓒_ij = g^(c_ij) * h^(τ_ij) for i,j := 1..n
𝓒_i0 = g^(c_i0) * h^(τ_i0) for i := 1..n

Dealers broadcast their a hash of their 𝓒_i0, 𝓒_ij commitments for
each of their sharings for kc*p, and the HMACs for each of the shares
to all peers.

------<=[ 23. STP broadcasts commitment hashes and HMACs   ]=>-----------

STP does the regular broadcasting procedure. The STP keeps a copy of
all commitment hashes and of all share HMACs for later.

------<=[ 24. Peers receive commitments hashes and HMACs]=>-----------

Peers receive and store the commitment hashes and the share HMACs in
an internal state for later.

Dealers broadcast their commitments.

------<=[ 25. STP broadcasts 𝓒_i0, 𝓒_ij for kc*p           ]=>-----------

STP does the regular broadcasting procedure. STP verifies the
commitment hashes received in the previous step against commitments,
aborts if any of these fails. STP may also run VSPS checks on all of
the commitments, reports any failures, but otherwise doesn't react to
them and just continues.

------<=[ 26. Peers receive commitments, send shares    ]=>-----------

Peers receive all commitments and verify them against the commitment
hashes. If this fails, they abort.

Dealers send the shares c_ij, τ_ij for both kc*p to the corresponding
peers via noise protected channel.

------<=[ 27. STP standard p2p routing shares           ]=>-----------

In this step the STP simply distributes the incoming Noise protected
shares to their proper recipients.

------<=[ 28. Peers receive shares                      ]=>-----------

Peers receive shares, verify them against the previously broadcast
commitments. Peers broadcast complaints against any dealers failing
their commitments.

------<=[ 29. STP broadcasts complaints                 ]=>-----------

STP does the regular broadcasting procedure. If there are no
complaints registered the STP will continue with the regular protocol,
otherwise the next step will be conflict resolution.

------<=[ 30. Peers receive complaints                  ]=>-----------

In this step the peers decide whether to continue with the regular
protocol or they engage in conflict resolution.

If there is complaints, the accused dealer broadcasts the contested
encrypted shares together with their encryption keys.

If there is no complaints, the regular protocol continues with the
verification of the ZK proofs on the correctness of 𝓒_i0.

------<=[ Phase 5 - Recover from commitment failures    ]=>-----------

------<=[ 31. STP broadcasts dealer defenses            ]=>-----------

In case there was complaints, the STP checks for each disclosure if
the previously stored share HMACs equal the hmac(key, encrypted
share), and if the commitment matches the decrypted share. The STP
keeps track of these results to anticipate which dealer will send how
much data in the next step.

------<=[ 32. Peers receive dealer defenses             ]=>-----------

Each peer checks for each disclosure if the previously stored share
HMACs equal the hmac(key, encrypted share), and if the commitment
matches the decrypted share. If both of these checks succeed, then the
accused dealer is cleared and the accuser is reported, and the
complaint is cleared.

If there is no valid complaints, the regular protocol continues with
the next phase: verification of the ZK proofs on the correctness of 𝓒_i0.

For any valid remaining complaints, the peers reconstruct the accused
dealers secret by broadcasting their share to everyone.

------<=[ 33. STP broadcasts shares for reconstruction  ]=>-----------

STP does the regular broadcasting procedure. Based on the received
shares STP also reconstructs any shares and corrects any invalid
commitments it has stored.

Reconstruction is done as following:

0. we set the candidate threshold to the originally configured
   threshold.

1. all shares are checked against their commitments and any correct
   ones are selected for reconstructing the shared secret. If there is
   not enough correct shares to satisfy the threshold the
   reconstruction attempt fails.

2. the reconstructed secret is verified against the 𝓒_i0 commitment,
   if this succeeds the reconstruction attempt is successful and we
   continue with the next step. If the attempt fails we increment the
   threshold by one and abort if we have less shares than this new
   threshold, otherwise we try again with step 2.

3. If step 2 succeeded in reconstructing the secret with a candidate
   threshold, we reconstruct any contested shares and their
   commitments.

------<=[ 34. Peers receive shares for reconstruction   ]=>-----------

Peers reconstruct any shares that have been complained about - the
accuser replaces their previously possibly faulty share with the
reconstructed share - and calculate the correct commitment for this
share, if this is different than previously received, this is replaced
by the corrected one. See the previous STP step on how the
reconstruction process works.

This step has no output. Peers immediately continue with the next
step.

------<=[ Phase 6 - ZK proof of correctness of product  ]=>-----------

------<=[ 35. Dealers prove in ZK correctness of 𝓒_i0   ]=>-----------

This step has no input, we arrive here either because there was no
complaints, all complaints were invalid, or the valid complaints
were neutralized by reconstruction of the contested shares.

We now start the ZK proofs, in which P_i proves in zk that 𝓒_i0 is a
commitment of the product λ_iα_iβ_i. As per Appendix F: ZK Proof for
multiplication of committed values from GRR98

Note the paper GRR98 describes a ZK proof for C = g^αβ * h^τ
however the multiplication algorithms Mult and FT-Mult require a proof for

  C = g^αβλ * h^τ

Note the extra λ in the exponent of g. to make this work a few changes
are necessary, these are:

   z = (x+eαλ)
   w_1 = (s_1 + λeρ)
   w_2 =  (s_2 + e(τ - σαλ))

and in the 2nd equation of the last step instead of A^e we need A^eλ:

   g^z * h^w_1 == M_1 * A^e'_iλ

we have applied these changes in the following steps of the ZK proof
specification

We apply the optimization presented at the end of this Appendix F of
GRR98:

Each per chooses a challenge e_j,r_j ∈ Z_q, broadcasts a commitment

      𝓒_ej = g^e_j * h^r_j

------<=[ 36. STP broadcasts 𝓒_ej commitments           ]=>-----------

STP does the regular broadcasting procedure.

------<=[ 37. Peers receive 𝓒_ej commitments            ]=>-----------

The peers store the 𝓒_ej commitments for later usage.

Dealer P_i chooses d, s, x, s_1, s_2 ∈ Z_q.
Broadcasts the following messages:

      M   = g^d * h^s,
      M_1 = g^x * h^s_1,
      M_2 = B^x * h^s_2

------<=[ 38. STP broadcasts M,M_1,M_2 messages         ]=>-----------

STP does the regular broadcasting procedure. STP keeps a copy of all
the ZK commitments received.

------<=[ 39. Peers receive M,M_1,M_2 messages          ]=>-----------

Peers receive and store the M, M_1 and M_2 messages. Peers now
broadcast their previously chosen e_j,r_j values.

------<=[ 40. STP broadcasts e_j,r_j values             ]=>-----------

STP does the regular broadcasting procedure. STP computes e'_i for all
dealers P_i:

      e'_i = Σ e_j
           j!=i

and stores these for later.

------<=[ 41. Peers receive e_j,r_j values              ]=>-----------

Peers receive e_j,r_j values, verify then against the previously
received, 𝓒_ej commitments:

      𝓒_ej == g^e_j * h^r_j

      abort if this fails.

each peer computes e'_i for all dealers P_i:

      e'_i = Σ e_j
           j!=i

Each dealer P_i broadcasts the following values:

      y   = d   + e'_iβ,
      w   = s   + e'_iσ
      z   = x   + e'_iαλ
      w_1 = s_1 + e'_iρλ
      w_2 = s_2 + e'_i(τ - σαλ)

------<=[ 42. STP broadcasts proofs                     ]=>-----------

STP does the regular broadcasting procedure. Verifies all ZK proofs
and uses this information to decide with step to continue with in the
protocol.

------<=[ 43. Peers receive proofs checks them.         ]=>-----------

Each peer checks for each proof the following equations.

      g^y * h^w   == M * B^e'_i
      g^z * h^w_1 == M_1 * A^e'_iλ
      B^z * h^w_2 == M_2 * C^e'_i

If all the proofs are correct the protocol continues with completing
the FT-Mult results. This step has no output, the output is generated
by the next step which is immediately executed by the peers after this
one.

------<=[ Phase 7 - Recover from ZK proof failures      ]=>-----------

In this phase peers disclose the shares from the dealer that failed to
prove the correctness of C_i0 so that this C_i0 can be corrected.

------<=[ 44. Peers receive proofs checks them.         ]=>-----------

If any of the ZK proofs fail, the peers expose the shares of the
dealer P_i who failed the proof and engage in a reconstruction
phase. Peers broadcast the plaintext shares of the dealers who failed.

------<=[ 45. STP broadcasts shares for reconstruction  ]=>-----------

STP does the regular broadcasting procedure. STP also reconstructs the
secret of the sharing and verifies that it satisfies 𝓒_i0, if that
fails, the STP aborts the protocol.

------<=[ 46. Peers receive shares for reconstruction   ]=>-----------

Peers reconstruct the secret of any dealers failing their ZK proof,
the reconstructed secret is checked if it matches the corresponding
𝓒_i0 commitment, if this fails the peers abort.

This step has no output, peers immediately continue with the next
phase/step.

------<=[ Phase 8 - Finish FT-Mult                      ]=>-----------

In this phase the FT-Mult protocol concludes, one last check and if
needed reconstruction phase provide robustness.

------<=[ 47. Peers calculate FT-MULT results           ]=>-----------

Note this step has no input it follows directly if all ZK proofs were
correct or if the failing dealers secrets have been successfully
reconstructed.

Each peer P_i computes:

      2t+1
  γ_i = Σ c_ji
       j=1

   which is a share of γ = αβ, via random polynomial of degree t and

      2t+1
  τ_i = Σ τ_ji
       j=1

Each peer also computes

    𝓒_i = 𝓗(γ_i, τ_i)

        = g^(γ_i)*h^(τ_i)

and also:

         2t+1
   𝓒'_i = Π 𝓒_ji
          j=1

Then compares 𝓒_i == 𝓒'_i, and aborts if this fails.

Otherwise the peers broadcast their final 𝓒_i commitment.

------<=[ 48. STP broadcasts 𝓒_i commitment            ]=>-----------

STP does the regular broadcasting procedure. However STP keeps a copy
of each of the final commitments, for later verification of the final
reconstruction of p. STP also runs a fast-track VSPS check on all the
commitments, depending on the result of this deciding on the next step
of the protocol regular or reconstruction.

------<=[ 49. Peers receive 𝓒_i, run VSPS on them       ]=>-----------

players run a VSPS Check on 𝓒_i for both kc*p, if it fails peers run a
VSPS Check on every dealers sharing, identifying the one that fails
the VSPS check.

If the fast-track VSPS checks succeed on the final commitments the
protocol continues with the regular final phase, otherwise the
protocol for a last time engages in a reconstruction of secrets of
dealers who failed the VSPS check of their commitments.

This step has no output message, either of the two possible follow-up
steps will generate an output message.

------<=[ Phase 9 - Recover from failing VSPS-checks    ]=>-----------

In this phase any failing VSPS-checks are countered by reconstruction
of the secret of the dealer who failed the check, the secret is then
re-shared using a "deterministic" sharing.

------<=[ 51. Peers disclose shares of failed dealers  ]=>-----------

In case the VSPS checks failed in the previous step, all peers
disclose the shares of the dealer(s) who has failed the VSPS check.

------<=[ 52. STP broadcasts shares and re-shares       ]=>-----------

The STP broadcasts all the disclosed shares.

The STP also reconstructs the secrets associated with these shares,
and then creates a "deterministic" re-sharing of this secret and
updates the commitments it holds to these new shares and re-calculates
the final commitments based on these.

The "deterministic" re-sharing of the reconstructed shares is based on
a polynomial with the constant term being the secret and the other
coefficients being derived by using HKDF-expand(info, prk), where the
prk is the current sessionid and the info parameter is either

  "k0p lambda * a * b re-sharing"
or
  "k0p blind re-sharing"

for the secret and the blinding factor respectively.

This deterministic re-sharing is used so that all parties in the
protocol can create the same re-sharing without any party having
control over this and without needing to distribute extra information
to all parties.

------<=[ 53. Peers receive shares and re-share         ]=>-----------

Peers receive disclosed shares of all dealers who failed the VSPS
check, and re-share the reconstructed secrets in the same way as the
STP does using the same "deterministic" re-sharing procedure.

This step has no output message, it immediately followed by the next
step sending the results of both multiplications to the STP.

------<=[ Phase 10 - Finalize TOPRF Update              ]=>-----------

This phase concludes the update of the TOPRF secret.

------<=[ 54. Peers send their final shares to STP      ]=>-----------

The peers send their shares of p to the STP.

------<=[ 55. STP receives results and calculates delta ]=>-----------

The STP receives all shares from peers, runs a VSPS check on their
commitments, aborts if these fail. It also verifies the commitments of
these shares, again, aborts if these fail. Otherwise reconstructs from
them the value:

  ∆ = ρ

Finally the STP sends out a message of one byte of value 0 to all
peers indicating the success of the protocol.

The protocol finishes for the STP.

------<=[ 44. Peers complete the protocol               ]=>-----------

If the received message from STP is 0, they replace the share (and
commitment) for the old kc with the new share (and commitment) for
kc'=(ρ·kc).

Otherwise they keep the old kc.

The protocol finishes here for the peers.

------<=[ TODO verify transcript                        ]=>-----------

All parties broadcast their transcript, and verify that they all
match. If there is non-matching, abort. Maybe make the transcript a
rolling check, by for example using it as a continuously updated
sessionid.

------<=[ References                                    ]=>-----------

[GRR98] R. Gennaro, M. O. Rabin, and T. Rabin. "Simplified VSS and
fact-track multiparty computations with applications to threshold
cryptography" In B. A. Coan and Y. Afek, editors, 17th ACM PODC, pages
101–111. ACM, June / July 1998

[JKR19] "Updatable Oblivious Key Management for Storage Systems", by
Stanislaw Jarecki, Hugo Krawczyk, and Jason Resch.

[RFC9497] Oblivious Pseudorandom Functions (OPRFs) Using Prime-Order
Groups https://www.rfc-editor.org/rfc/rfc9497.html