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.
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
- 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
Alice A = aG
and Bob B = bG
want to create a shared key S
.
- Alice knows
B
, so she can computeS = aB ( = abG )
- Bob knows
A
, so she can computeS = aA ( = baG = abG )
ElGamal encryption uses the DH key exchange to encrypt messages.
Bob wants to encrypt message M
for Alice A = aG
.
- Choose random nonce
e
. Set public nonceE = eG
. - Compute a shared secret
S
using DH key exchange:S = eA
- Encrypt
M
:D = M + S
Send the pair (D,E)
to Alice.
Alice wants to decrypt (D,E)
using her private key a
.
- Compute the shared secret:
S = aE
- Decrypt
M
:D - S = M
Given (G,xG,yG,xyG)
we want to prove the scalars x
and y
are indeed multiplied. We know x
. The verifier doesn't.
- Choose random nonce
r
- Set public nonces
R₁ = rG
andR₂ = 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.
- Compute challenge
c = 𝑯(R₁|R₂)
- Verify
s * G == R₁ + c * (xG)
- Verify
s * (yG) == R₂ + c * (xyG)
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
:
- Choose random nonces
r₁
andr₂
- Set public nonces
R₁ = r₁G
,R₂ = r₂A
,R₃ = r₂G
andR₄ = 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.
- Compute challenge
c = 𝑯(R₃,R₄)
- Verify
s₁G + s₂A == R₄ + cD
- Verify
s₂G == R₃ + c * E
Bob wants to prove that X = xG
, D = xG + eA
, and E = eG
. Bob knows x
and e
. The verifier doesn't.
- Choose random nonces
r₁
andr₂
- 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.
- 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)
Divide x
into equally small segments xₖ
of size l
(for example 8 bit).
- 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 smaller2^l
. - Create a proof of correct encryption for
(Dₖ, Eₖ)
- Encrypt
- Create a proof of correct encryption of dlog for
(wsum{Dₖ}, wsum{Eₖ})
. The weighted sumwsum
is s.t.wsum{xₖ} = x
.
- For each encrypted segment
(Dₖ, Eₖ)
:- Verify the range proof for
Dₖ
- Verify the proof of correct encryption for
(Dₖ, Eₖ)
- Verify the range proof for
- Compute the weighted sum
(wsum{Dₖ}, wsum{Eₖ})
- Verify the proof of correct encryption of dlog for
(wsum{Dₖ}, wsum{Eₖ})
- For each encrypted segment
(Dₖ, Eₖ)
:- Decrypt it
xₖG = Dₖ - aEₖ
- Find dlog
xₖ
ofxₖG
. E.g. by applying baby-step giant-step to the interval[1, 2^l]
- Decrypt it
- Compute
x
:x = wsum{xₖ}
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 pointX=xG
to Alice. - For each
Tᵢ
:- Bob encrypts
x
usingTᵢ
as public key. He sends the ciphertext to Alice. - Bob also proves that the ciphertext is indeed the dlog of
X
encrypted withTᵢ
.
- Bob encrypts
- Alice verifies the proofs for all ciphertexts to ensure she learns
x
if she learns the dlog of anyTᵢ
.
This combines all points Tᵢ
into a single point X
.
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 nonceE
when encryptingxₖ
. This is secure because the shared secretsSᵢ = eTᵢ
we use in our ElGamal encryption are identical to performing multiple DH key exchanges with the same public keyeG
. Additionally, the proof of knowledge forE = eG
is required only once. - Bob can aggregate the Bulletproofs into a single one. An aggregate of
n
Bulletproofs requires onlylog(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 tweakedTᵢ' = Tᵢ + 𝑯(i|T₁|...|Tₙ) * Tᵢ
instead of the plainTᵢ
.
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.
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.
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.
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.
Hi @RobinLinus. I'm struggling to understand how and where
Verifiable Encryption of a Dlog
is used inOR 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.