Homomorphic Threshold Encryption

The core of the flow encryption system requires a partially homomorphic encryption scheme, which allows for users to publish transactions that contain encrypted values. These encrypted values are then aggregated, using the homomorphism, by validators. The aggregate value (the “batched flow”) is then decrypted using the threshold decryption scheme described here.

Desired Properties

For our threshold encryption scheme, we require three important properties:

  • Homomorphism: we must be able to operate over ciphertexts, by combining value commitments from many participants into a batched value.
  • Verifiability: we must be able to verify that a given value was encrypted correctly to a given ciphertext
  • Robustness: up to validators must be permitted to either fail to provide a decryption share or provide in invalid decryption share.

Concrete Instantiation: Homomorphic ElGamal

Setup

Compute a lookup table for every by setting where is the basepoint of decaf377. Store for later use in value decryption.

Value Encryption

                                  ┌───────────────────┐                           
                                  │DKG Public Key (D) │                           
                                  │                   │                           
                                  └───────────────────┘                           
                                            │                                     
                                  ┌─────────▼─────────┐    ┌──────────────┐       
                                  │                   │    │     v_e      │       
                                  │                   │    │  (encrypted  │       
                                  │                   │    │    value)    │       
                  ┌──────────┐    │ElGamal Encryption │    │ ┌──────────┐ │       
               ┌─▶│v_0 (u16) │────▶   D: DKG Pubkey   ├────┼▶│   c_0    │ │       
               │  └──────────┘    │     M = v_i*G     │    │ └──────────┘ │       
               │  ┌──────────┐    │     e <- F_q      │    │ ┌──────────┐ │       
┌────────────┐ ├─▶│v_1 (u16) │────▶ c_i = (e*G, M+eD) ├────┼▶│   c_1    │ │       
│            │ │  └──────────┘    │                   │    │ └──────────┘ │       
│v [0, 2^64) │─┤  ┌──────────┐    │                   │    │ ┌──────────┐ │       
│            │ ├─▶│v_2 (u16) │────▶ Correctness Proof ├────┼▶│   c_2    │ │       
└────────────┘ │  └──────────┘    │         σ         │    │ └──────────┘ │       
               │  ┌──────────┐    │                   │    │ ┌──────────┐ │       
               └─▶│v_3 (u16) │────▶                   ├────┼▶│   c_3    │ │       
                  └──────────┘    │                   │    │ └──────────┘ │       
                                  │                   │    │              │       
                                  │                   │    │              │       
                                  └───────────────────┘    └──────────────┘       
                                            │                                     
                                            │           ┌────────────────────────┐
                                            └──────────▶│proofs σ_ci = (r, s, t) │
                                                        └────────────────────────┘

A value is given by an unsigned 64-bit integer . Split into four 16-bit limbs

with .

Then, perform ElGamal encryption to form the ciphertext by taking (for each )

Where is the basepoint generator for decaf377, is the large prime-order scalar field for decaf377, and is the public key output from DKG.

Next, compute a proof of correctness of the ElGamal encryption by executing the following sigma protocol:

The proof is then . The encryption of value is given as .

Upon receiving an encrypted value with proofs , a validator or validating full node should verify each proof by checking

Considering the value invalid if the proof fails to verify.

This protocol proves, in NIZK, the relation

Showing that the ciphertext is an actual encryption of for the DKG pubkey , and using the hash transcript to bind the proof of knowledge of to each .

Each ciphertext is two group elements, accompanied by a proof which is three scalars. decaf377 group elements and scalars are encoded as 32-byte values, thus every encrypted value combined with its proof is = 640 bytes.

Value Aggregation

                          n (batch size)                         
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
│┌──────────────┐   ┌──────────────┐            ┌──────────────┐│
 │              │   │              │            │              │ 
 │   v_{e0}     │   │    v_{e1}    │            │    v_{ek}    │ 
 │              │   │              │            │              │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │            │ ┌──────────┐ │ 
 │ │   c_0    │ │   │ │   c_0    │ │            │ │   c_0    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │            │ ┌──────────┐ │ 
 │ │   c_1    │ │   │ │   c_1    │ │            │ │   c_1    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │    ...     │ ┌──────────┐ │ 
 │ │   c_2    │ │   │ │   c_2    │ │            │ │   c_2    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │            │ ┌──────────┐ │ 
 │ │   c_3    │ │   │ │   c_3    │ │            │ │   c_3    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │              │   │              │            │              │ 
 │              │   │              │            │              │ 
 └──────────────┘   └──────────────┘            └──────────────┘ 
         │                  │             │             │        
         │                  │             │             │        
         └──────────────────┴─────┬───────┴─────────────┘        
                                  │             ┌──────────────┐ 
                                  ▼             │              │ 
                                ┌───┐           │   v_{agg}    │ 
                                │ + │───────────▶              │ 
                                └───┘           │ ┌──────────┐ │ 
                                                │ │   c_0    │ │ 
                                                │ └──────────┘ │ 
                                                │ ┌──────────┐ │ 
                                                │ │   c_1    │ │ 
                                                │ └──────────┘ │ 
                                                │ ┌──────────┐ │ 
                                                │ │   c_2    │ │ 
                                                │ └──────────┘ │ 
                                                │ ┌──────────┐ │ 
                                                │ │   c_3    │ │ 
                                                │ └──────────┘ │ 
                                                │              │ 
                                                │              │ 
                                                └──────────────┘  

To batch flows, we must use the homomorphic property of ElGamal ciphertexts. Aggregation should be done component-wise, that is, on each limb of the ciphertext (). To aggregate a given , simply add each limb:

This holds due to the homomorphic property of ElGamal ciphertexts.

The block producer aggregates every , producing a public transcript of the aggregation. The transcript can then be publicly validated by any validator or full node by adding together each in the transcript and verifying that the correct was committed by the block producer.

Value Decryption

┌──────────────┐                                                                        
│     v_e      │                                                                        
│  (encrypted  │                                                                        
│    value)    │                                                                        
│ ┌──────────┐ │     ┌─────────────────────────┐                                        
│ │   c_0    │─┼────▶│                         │    ┌─────────────────────────────────┐ 
│ └──────────┘ │     │                         │    │       Gossip (ABCI++ Vote       │ 
│ ┌──────────┐ │     │                         │    │           Extensions)           │ 
│ │   c_1    │─┼────▶│Decryption Shares + Proof│    │                                 │ 
│ └──────────┘ │     │                         │    │        verify share proof       │ 
│ ┌──────────┐ │     │  s_{pi} = d_{p}c_{i0}   │───▶│          σ_pi for s_pi          │ 
│ │   c_2    │─┼────▶│   σ_{pi} = (r, α, γ)    │    │                                 │ 
│ └──────────┘ │     │                         │    │      d = sum(s_pi*λ_{0,i})      │ 
│ ┌──────────┐ │     │                         │    │        v_mi = -d + c_{i1}       │ 
│ │   c_3    │─┼────▶│                         │    │                                 │ 
│ └──────────┘ │     └─────────────────────────┘    └─────────────────────────────────┘ 
│              │                                                     │    ┌───────┐     
│              │                                                    ┌┘    │  LUT  │     
└──────────────┘                                                    │     └───┬───┘     
                   ┌─────────────────────────┐       ┌──────────────▼─────────▼────────┐
                   │                         │       │       Reverse dLog Lookup       │
                   │ Reconstruct from Limbs  │       │                                 │
                   │                         │◀──────│v_q = [LUT[v_mi], ..., LUT[v_mn]]│
                   │                         │       │                                 │
                   └─────────────────────────┘       └─────────────────────────────────┘
                                │                                                       
                                ▼                                                       
                           ┌─────────┐                                                  
                           │         │                                                  
                           │v (u128) │                                                  
                           │         │                                                  
                           └─────────┘                                                   

To decrypt the aggregate , take each ciphertext component and perform threshold ElGamal decryption using the participant’s DKG private key share to produce decryption share :

Next, each participant must compute a proof that their decryption share is well formed relative to the commitment to their secret share . This is accomplished by adopting the Chaum-Pedersen sigma protocol for proving DH-triples.

With , , and as inputs, each participant computes their proof by taking

The proof is the tuple .

Every participant then broadcasts their proof of knowledge along with their decryption share to every other participant.

After receiving from each participant, each participant verifies that is valid by checking

and aborting if verification fails. (TODO: should we ignore this participant’s share, or report/slash them?)

This protocol is the Chaum-Pedersen sigma protocol which here proves the relation

Showing that the validator’s decryption share is correctly formed for their key share which was committed to during DKG.

Now each participant can sum their received and validated decryption shares by taking

where is the lagrange coefficient (for x=0) at , defined by

where is the set of all participant indices.

Then, compute the resulting decryption by taking

Now we have the output . Each is a decaf377 group element. Use our lookup table from the setup phase to transform each value to its discrete log relative to the basepoint: Now we have the decrypted value

where each is bounded in .

To recombine the value, iterate over each , packing each into a u16 value , performing carries if necessary. This yields the final value

This value is bounded by , assuming that the coefficients in the previous step were correctly bounded.

Note

On verifiability, this scheme must include some snark proof that coefficients were correctly created from input values. This can be accomplished by providing a SNARK proof that accompanies each value. It may also be desirable to SNARK the sigma protocol given in the value encryption phase in order to save on chain space.

Acknowledgements

Thanks to samczsun for his discussion and review of this spec, and for finding a flaw with an earlier instantiation of the encryption proof.

TODO: end-to-end complexity analysis (number of scalar mults per block, LUT size, etc)