Skip to content

Instantly share code, notes, and snippets.

@RobinLinus
Last active March 3, 2024 03:24
Show Gist options
  • Save RobinLinus/4035ced3fa04cc3745a30dcda09e2367 to your computer and use it in GitHub Desktop.
Save RobinLinus/4035ced3fa04cc3745a30dcda09e2367 to your computer and use it in GitHub Desktop.

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

  1. DH Key exchange
  2. ElGamal encryption
  3. Proof of DH tupel
  4. Proof of correct encryption
  5. Proof of correct encryption of dlog
  6. Verifiable encryption of a dlog
  7. OR operator
  8. Optimisations
  9. Boolean functions
  10. 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.

  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
Copy link

houten11 commented Dec 1, 2022

Thanks. I see now.

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