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 balance 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)