Skip to content

Instantly share code, notes, and snippets.

# RobinLinus/or-operator.md

Last active May 18, 2023 15:03
Star You must be signed in to star a gist

# OR Operator for DLCs and PTLCs

We construct an OR operator for adaptor points:

If Alice learns the dlog of T₁, or T₂, ..., or Tₙ, then she also learns the dlog of X.

This is possible using verifiable encryption (see "Juggling" by Shlomovits et al.). An OR operator allows to condense complex spending conditions into a single point. This prevents the combinatorial explosions which usually occur when using multi-oracles. An OR operator makes spending conditions easily composable. In theory, it even enables arbitrary computations on values provided by oracles.

## Motivation

Applications for the OR operator include Discreet Log Contracts (DLCs), adaptor signatures, and Point Time Locked Contracts (PTLCs):

• Order relations for numeric outcomes of events provided by oracles
• Arithmetic on numeric outcomes
• Multi-oracles
• Complex spending conditions on the Lightning network
• Escrows, non-interactive threshold escrows, and weighted threshold escrows
• Logic gates and Boolean functions
• Non-interactive t-of-n threshold gates
• Any combination of all of the above. Every payment condition is expressible in a single adaptor point, which you can again freely recombine with other conditions.
• Ideally, a scriptless VM which lets you express any Bitcoin script and more. For example, validation of a SPV inclusion proof for some other Bitcoin transaction.

We use the terms adaptor points and payment points synonymously from here on in this work.

## DH Key Exchange

Alice `A = aG` and Bob `B = bG` want to create a shared key `S`.

• Alice knows `B`, so she can compute `S = aB ( = abG )`
• Bob knows `A`, so she can compute `S = aA ( = baG = abG )`

## ElGamal Encryption

ElGamal encryption uses the DH key exchange to encrypt messages.

### Encryption

Bob wants to encrypt message `M` for Alice `A = aG`.

1. Choose random nonce `e`. Set public nonce `E = eG`.
2. Compute a shared secret `S` using DH key exchange: `S = eA`
3. Encrypt `M`: `D = M + S`

Send the pair `(D,E)` to Alice.

### Decryption

Alice wants to decrypt `(D,E)` using her private key `a`.

1. Compute the shared secret: `S = aE`
2. Decrypt `M`: `D - S = M`

## Proof of DH Tupel

Given `(G,xG,yG,xyG)` we want to prove the scalars `x` and `y` are indeed multiplied. We know `x`. The verifier doesn't.

### Prove

1. Choose random nonce `r`
2. Set public nonces `R₁ = rG` and `R₂ = r(yG)`
3. Compute challenge `c = 𝑯(R₁|R₂)`
4. Compute proof of knowledge for `x`: `s = r + c * x`

Send `R₁`,`R₂`, and `s` to the verifier.

### Verify

1. Compute challenge `c = 𝑯(R₁|R₂)`
2. Verify `s * G == R₁ + c * (xG)`
3. Verify `s * (yG) == R₂ + c * (xyG)`

## Proof of Correct Encryption

Bob wants to prove that `(D,E)` is some message `X = xG` encrypted for Alice `A = aG`. Bob knows `x` and `e`. The verifier doesn't. Bob wants to show that `D = xG + eA` and `E = eG`:

### Prove

1. Choose random nonces `r₁` and `r₂`
2. Set public nonces `R₁ = r₁G`, `R₂ = r₂A`, `R₃ = r₂G` and `R₄ = R₁ + R₂`
3. Compute challenge `c = 𝑯(R₃,R₄)`
4. Prove knowledge of `x`: `s₁ = r₁ + c * x`
5. Prove knowledge of `e`: `s₂ = r₂ + c * e`

Send `R₃`, `R₄`, `s₁` and `s₂` to the verifier.

### Verify

1. Compute challenge `c = 𝑯(R₃,R₄)`
2. Verify `s₁G + s₂A == R₄ + cD`
3. Verify `s₂G == R₃ + c * E`

## Proof of Correct Encryption of a Dlog

Bob wants to prove that `X = xG`, `D = xG + eA`, and `E = eG`. Bob knows `x` and `e`. The verifier doesn't.

### Prove

1. Choose random nonces `r₁` and `r₂`
2. Set public nonces `R₁ = r₁G`, `R₂ = r₂A`, `R₃ = r₂G`
3. Compute challenge `c = 𝑯(R₁, R₂, R₃)`
4. Prove knowledge of `x`: `s₁ = r₁ + c * x`
5. Prove knowledge of `e`: `s₂ = r₂ + c * e`

Send `R₁`, `R₂`, `R₃`, `s₁` and `s₂` to the verifier.

### Verify

1. Compute challenge `c = 𝑯(R₁, R₂, R₃)`
2. Verify `s₁G == R₁ + c * X`
3. Verify `s₂G == R₃ + c * E`
4. Verify `s₂A == R₂ + c * (D-X)`

## Verifiable Encryption of a Dlog

Divide `x` into equally small segments `xₖ` of size `l` (for example 8 bit).

### Encrypt

1. For each segment `xₖ`:
1. Encrypt `xₖ`: `(Dₖ, Eₖ) = (xₖG + eₖA, eₖG)`
2. Create a Bulletproof range proof which proves that `Dₖ` is a Pedersen commitment with value smaller `2^l`.
3. Create a proof of correct encryption for `(Dₖ, Eₖ)`
2. Create a proof of correct encryption of dlog for `(wsum{Dₖ}, wsum{Eₖ})`. The weighted sum `wsum` is s.t. `wsum{xₖ} = x`.

### Verify

1. For each encrypted segment `(Dₖ, Eₖ)`:
1. Verify the range proof for `Dₖ`
2. Verify the proof of correct encryption for `(Dₖ, Eₖ)`
2. Compute the weighted sum `(wsum{Dₖ}, wsum{Eₖ})`
3. Verify the proof of correct encryption of dlog for `(wsum{Dₖ}, wsum{Eₖ})`

### Decrypt

1. For each encrypted segment `(Dₖ, Eₖ)`:
1. Decrypt it `xₖG = Dₖ - aEₖ`
2. Find dlog `xₖ` of `xₖG`. E.g. by applying baby-step giant-step to the interval `[1, 2^l]`
2. Compute `x`: `x = wsum{xₖ}`

## OR Operator

Finally, we construct an OR operator for adaptor points. We want to express:

If Alice learns the dlog of `T₁`, or `T₂`, ..., or `Tₙ`, then she also learns the dlog of `X`.

Alice and Bob can agree on such a `X` by using verifiable encryption.

1. Bob chooses a random secret `x` and sends the corresponding point `X=xG` to Alice.
2. For each `Tᵢ`:
1. Bob encrypts `x` using `Tᵢ` as public key. He sends the ciphertext to Alice.
2. Bob also proves that the ciphertext is indeed the dlog of `X` encrypted with `Tᵢ`.
3. Alice verifies the proofs for all ciphertexts to ensure she learns `x` if she learns the dlog of any `Tᵢ`.

This combines all points `Tᵢ` into a single point `X`.

## Optimisations

Numerous optimisations are possible in our specific use case for verifiable encryption.

• Bob could reduce the size of `x` to e.g. 20 bytes such that only 20 Bulletproofs are required. However, that reduces security from 128 bits to 80 bits. This might be practical for short-lived DLCs.
• Bob can use larger segments. That leads to longer decryption times for Alice, though. However, when decrypting multiple dlogs (also for multiple OR operators) she has to traverse the interval `[1, 2^l]` only once. Using 16 bits instead of 8 would reduce the number of Bulletproofs by another factor of 2. So, in total, about 65000 point additions would be required to decrypt all the dlogs used in all OR operators occurring in a DLC.
• Bob can use for each `Tᵢ` the same public nonce `E` when encrypting `xₖ`. This is secure because the shared secrets `Sᵢ = eTᵢ` we use in our ElGamal encryption are identical to performing multiple DH key exchanges with the same public key `eG`. Additionally, the proof of knowledge for `E = eG` is required only once.
• Bob can aggregate the Bulletproofs into a single one. An aggregate of `n` Bulletproofs requires only `log(n)` more group elements than a single proof. However, the prover's work is still linear in the number of proofs.
• The newer Bulletproofs+ are more efficient.
• We must mitigate rouge key attacks. So, we must delinearise all `Tᵢ` because in some situations they can be chosen freely by an attacker. A solution is to apply the OR operator to tweaked `Tᵢ' = Tᵢ + 𝑯(i|T₁|...|Tₙ) * Tᵢ` instead of the plain `Tᵢ`.

### Reuse the Bulletproofs

Bob would like to prove the ranges of the segments of `x` only once per set. Suppose there are two cyphertexts `D₁` and `D₂` both encrypting `xₖ`. The first is encrypted for public key `T₁` the second for `T₂`:

``````D₁ = xₖG + eT₁
D₂ = xₖG + eT₂
``````

How can Bob prove they both commit to `xₖ`?

``````D₁-D₂ = e(T₁-T₂)
``````

So, if he signs any message using

``````generator:  H = T₁-T₂, and
public key: P = e(T₁-T₂) = D₁-D₂
``````

then he proves that `D₁` and `D₂` commit to the same value. Thus, a range proof for `D₁` also proves the range for `D₂`.

So, in total, to apply the OR operator to a set of `n` points, we need 10 Bulletproofs plus some `O(n)` signatures.

## Boolean Functions

Suppose our oracle signs only two bits. As shown below, we can construct a NAND gate from the four adaptor points. NAND is a universal gate and thus, DLCs can compute any Boolean function. Furthermore, it is possible to perform complex computations efficiently by condensing the adaptor points recursively - as described above. Thus, we can express payment conditions that perform arbitrary computations on oracle values.

For example, oracle1 signs the BTC/USD price and oracle2 signs USD/EUR. Using those values a DLC can compute a price for BTC/EUR.

### NAND Gate

Our oracle signs two bits: bit "A" and bit "B". So, we have 4 adaptor points `A0, A1` and `B0, B1`. We can express a NAND like:

``````C₁ = A0 + B0   →  "result is 1"
C₂ = A0 + B1   →  "result is 1"
C₃ = A1 + B0   →  "result is 1"
C₄ = A1 + B1   →  "result is 0"
``````

We map the two possible outcomes `0` and `1` to two points `D0` and `D1`:

``````D0 = C₄                →   "result is 0"
D1 = C₁ or C₂ or C₃    →   "result is 1"
``````

This gives us composable NAND gates. They can express any Boolean function in a DLC.

A somewhat crazy idea is to use bitcoin as time oracle and validate a block header in an adaptor point.

## Multi-Party OR Operator

Until here, we have discussed only contracts with two parties Alice and Bob. Now, we want to generalise the OR operator to multiple parties. Fortunately, this is easy. Suppose there is Alice and `n` Bobs `Bob₁, ..., Bobₙ`. Each `Bobᵢ` encrypts an `Xᵢ` for Alice. If Alice learns the dlog of `X = X₁ + ... + Xₙ` then all `n` Bobs agree that the OR operator was correctly applied. However, they do not necessarily agree on which of the inputs to their OR operators was true. In theory, for example, Alice could "solve" `X₁` by learning `T₁`, but solve `X₂` by learning `T₂`. However, that implies Alice could have solved both of them also the other way around and that should not matter for the correctness of the result of the OR operator.

Every Bob has to ensure his `Xᵢ` is indeed included in the sum `X`. Thus, he has to mitigate key cancelation attacks. Therefore, he has to check all other `Xⱼ` in the sum and the proof of knowledge for each them. Those proofs are included in the corresponding proof of correct encryption of dlog which they have to send to Alice.

The Bobs have to create a joined adaptor signature for each possible payout transaction (e.g. with MuSig2). However, they have to sign every potential BTC value only once. We can condense all conditions under which a particular value can be withdrawn into a single adaptor point by using the OR operator. Thus, the Bobs do not have to interact with each other but only with Alice.

### houten11 commented Nov 30, 2022

Hi @RobinLinus. I'm struggling to understand how and where `Verifiable Encryption of a Dlog` is used in `OR Operator`.
Is there a need to split x into segments? Because if Alice finds out dlog of `Ti` she can decrypt cyphertext and retrieve the whole x.

### RobinLinus commented Nov 30, 2022 • edited

We want to express that if Alice learns the dlog of any `Tᵢ` then she also learns the dlog of `X = xG`. That's why Bob verifiably encrypts `x` with each `Tᵢ`. He encrypts `x` in small segments such that Alice can break the dlog efficiently. However, she can do that only after she learned a dlog of a `Tᵢ`.

### houten11 commented Dec 1, 2022

Thanks. I see now.

to join this conversation on GitHub. Already have an account? Sign in to comment