RobinLinus/or-operator.md

## or-operator.md

      
    Raw
  

              or-operator.md
            
          
    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.
Overview


DH Key exchange
ElGamal encryption
Proof of DH tupel
Proof of correct encryption
Proof of correct encryption of dlog
Verifiable encryption of a dlog
OR operator
Optimisations
Boolean functions
Multi-party OR operator

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.

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

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

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

Compute the shared secret: S = aE
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


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

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


Compute challenge c = 𝑯(R₁|R₂)
Verify s * G == R₁ + c * (xG)
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


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

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


Compute challenge c = 𝑯(R₃,R₄)
Verify s₁G + s₂A == R₄ + cD
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


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

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


Compute challenge c = 𝑯(R₁, R₂, R₃)
Verify s₁G == R₁ + c * X
Verify s₂G == R₃ + c * E
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


For each segment xₖ:

Encrypt xₖ: (Dₖ, Eₖ) = (xₖG + eₖA, eₖG)
Create a Bulletproof range proof which proves that Dₖ is a Pedersen commitment with value smaller 2^l.
Create a proof of correct encryption for (Dₖ, Eₖ)


Create a proof of correct encryption of dlog for (wsum{Dₖ}, wsum{Eₖ}). The weighted sum wsum is s.t. wsum{xₖ} = x.

Verify


For each encrypted segment (Dₖ, Eₖ):

Verify the range proof for Dₖ
Verify the proof of correct encryption for (Dₖ, Eₖ)


Compute the weighted sum (wsum{Dₖ}, wsum{Eₖ})
Verify the proof of correct encryption of dlog for (wsum{Dₖ}, wsum{Eₖ})

Decrypt


For each encrypted segment (Dₖ, Eₖ):

Decrypt it xₖG  = Dₖ - aEₖ
Find dlog xₖ of xₖG. E.g. by applying baby-step giant-step to the interval [1, 2^l]


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.

Bob chooses a random secret x and sends the corresponding point X=xG to Alice.
For each Tᵢ:

Bob encrypts x using Tᵢ as public key. He sends the ciphertext to Alice.
Bob also proves that the ciphertext is indeed the dlog of X encrypted with Tᵢ.


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.