TE + MPC research

[PopcornPaws]

Description

The following topics should be researched:

• Threshold Encryption (TE)
• Multi-Party Computation (MPC)

We need to have a good understanding of the above topics, as our oracle nodes might use something like these to sign external payloads, should they agree on the result.

[PopcornPaws]

High-level overview

TE is a type of MPC where data is encrypted using a public key, whose private key is distributed among secure nodes. These nodes need to work together to decrypt the encrypted data and at least threshold number of nodes are required for decryption. Thus, an adversary with less than threshold pieces of the shared secret key cannot decrypt the encrypted data.

Two-party computation

The simplest MPC is when there are two participants executing the MPC (e.g. Yao's millionaires' problem: two millionaires want to decide who's richer without sharing their net worth). Yao formulated a protocol to solve such problems called Yao's garbled circuit. Here, the underlying problem has to be compiled to a boolean circuit (consisting of XOR and AND gates) which is a challenge in itself, especially if the problem contains loops, such as elliptic curve math.

According to some recent papers, however, an AES boolean circuit required approximately 20 minutes to compute, and more than 6million commitments had to be sent. This was improved to processing 75 million AES blocks per second with GPUs, circuit compiler optimization and somewhat lower security. However, this technology still seems to be in early stages and it might not have any advantage over zk-SNARKS, especially if we consider Spartan, which is a general purpose SNARK without the need for a trusted setup.

Multi-party computation

Generally, the most fundamental tool for MPC is Samir's secret sharing protocol. In essence, it encodes the secret as the constant part ($s = a_0$) of a polynomial $p(x)$.

$$p(x) = \sum_{i = 0}^n a_ix^i$$

where $n$ is the order of the polynomial. Then, $k > n$ different evaluations of $p(x)$ are calculated at $k$ random $x_i$ values and each participant receives a point and the corresponding evaluation: $x_i, p(x_i)$. Thus, when there are at least $n + 1$ participants that share their $x_i, p(x_i)$ pairs, the original $p(x)$ polynomial can be reconstructed using Lagrange interpolation, and the secret coefficient can be recovered. A nice feature of Samir's secret sharing is that refreshing shared secrets (point, evaluation) is easily done by assigning a new random (point, evaluation) pair computed from the same polynomial.

Verifiable secret sharing

Contrary to Samir's secret sharing method, Feldman's approach makes the private shares to be publicly verifiable by sharing the public keys respective to the private shares. A Rust implementation of verifiable secret sharing.

Misc

For a great deep-dive, check out Jens Groth's paper

[PopcornPaws]

Threshold signatures vs Multisig

Some nice articles:

• https://cryptologie.net/article/486/difference-between-shamir-secret-sharing-sss-vs-multisig-vs-aggregated-signatures-bls-vs-distributed-key-generation-dkg-vs-threshold-signatures/
• https://sepior.com/blog/top-5-reasons-threshold-signature-wallets-are-better-than-multisig
• https://www.atato.com/2021/08/24/5-great-reasons-to-choose-threshold-signatures-over-multisig/
• https://blog.unilaunch.app/what-is-a-threshold-signatures-explained-the-power-of-cryptography/

TLDR:

• Samir's secret sharing requires a single (trusted) point where secrets are split/aggregated
• Multisignatures need to verify signatures from all participants (if someone doesn't show up, they can veto the signature)
• aggregated signatures (BLS) can bundle up multiple signatures into a single signature (trade time for space, because it's slower than ECDSA)
• distributed key generation avoids single points of failure as they operate with a threshold

[PopcornPaws]

Programmable Keypairs (PKP)

Lit Protocol works on a smart contract system where each contract has a PKP and can make http requests and send transactions.

• Lit Actions are essentially smart contracts uploaded to IPFS which can be executed by the Lit Nodes
• users may generate PKPs for lit actions and give them the ability to sign stuff (e.g. grant access to something)
• consensus between Lit Nodes is achieved by threshold cryptography, i.e. 2/3rd of the nodes have to agree on the output of the lit actions

  Implementation details, examples

  For mor details, see #4

[PopcornPaws]

Torus Network/Auth Network

Torus network is built upon the Tendermint BFT consensus system. It essentially provides a special wallet that links on-chain identity to social OAuth tokens. It is the product of Web3Auth who recently partnered with StarkWare to provide a wallet that doesn't require secret seeds. Instead, the private key is distributed among nodes (?) and the user can reconstruct the private key using their social accounts to send transactions.

Torus DKG

Torus network also builds on distributed key generation. The process looks like this:

• alice, Bob and CJ want to set up a 2 out of 3 threshold signature system
• all three of them generate a linear polynomial (that requires 2 points to reconstruct) in the form $p(x) = a_0 + a_1x$
• they take $p(0)$, $p(r_1)$, $p(r_2)$ evaluations of their own $p(x)$ polynomial, keep $p(0)$ for themselves and send $p(r_1)$ and $p(r_2)$ to the other participants. Here $r_1$ and $r_2$ are random numbers from the domain of the polynomial
• care should be taken not to send multiple evaluations to the other participants as they could reconstruct the original polynomial by interpolation
• after the initial round, users should have three shares (their own, and the two shares received from the other participants)
• when everybody sums up their respective shares they get a point on a fourth linear polynomial: $p_a(x) + p_b(x) + p_c(x) = p_s(x)$
• then, every time at least two participants share their respective $p_x^i(x)$ point and $x$, the $p_s$ polynomial can be reconstructed: $p_s(x) = a_0 + a_1x$ where $a_0$ is the secret key that generates the distributed signature

Web3Auth structure

Key management is based on 2-out-of-3 threshold signature scheme, where the user holds one share, one recovery share (should they lose their primary share) and the node network holds another share. Thus, whenever the user wants to enter, they provide their share and the node network provides another share and they can enter.

[PopcornPaws]

Design considerations

We should focus mostly on scalability (even on the long term). Lit aims to handle scalability by building a load balancer between subnetworks. This means that for-example there could be 100 nodes in a network that has a single private key whose shares are distributed among the 100 participants. This subnetwork's private key can represent the share of another network one level higher that is actually a network of multiple 100 participant subnetworks.

Lit uses BLS instead of ECDSA which is probably a good idea to use for some cool features of BLS curves (i.e. signature aggregation).

Implementations

• Rust implementations
  • multiparty-ecdsa
  • multiparty-bls

The above implementations are both based on a round-based multiparty protocol implementation.

[PopcornPaws]

Closing this for now. Further research/implementation is tracked here