[dlc-dev] BLS and announcement free DLCs
Ichiro Kuwahara
kuwahara at cryptogarage.co.jp
Fri Nov 4 09:03:40 CET 2022
Hey Lloyd
>Sorry for the late reply. My email sometimes degenerates into a LIFO queue
when I'm busy.
Haha, no problem, I will ping you on twitter or something next time:)
>Actually, using the bit decomposition trick we're only doing 2*log_2(100)
= 14 encryptions. So 14*λ BF-ciphers sym-ciphers in the case we're *not*
batching the verifiable encryptions.
Thank you for the explanation.
I understood that the compression method is to use binary digit-by-digit
oracle signatures.
IIUC, my suggestions below allow for even more compression. To keep things
simple, let me explain without batching functions.
For λ=40 and m∈ {0,1,2,・・・100}, the number of encryptions decreases as
follows.
40*2*log_2(100)=560→3*log_2(100)=21
The security parameter λ is no longer required in my suggestion.
As you pointed out before, multiple values of m are being encrypted on
either side of the selection.
—------Encryption /Decryption scheme---------------
1.Commitment
Alice generates random integers r_m and creates sym-ciphers s_m=r_m+y_m.
For all m, Alice computes R_m = g・r_m.
At this point, Alice sends BF-r-ciphers(encrypted r_m) and
BF-s-ciphers(encrypted
s_m) , R_m and the statement Y_m to Bob.
2.Cut and choose
Bob select m∈ {0,1,2,・・・100}
• For all m not selected by Bob
-Alice sends sym-ciphers s_m and the random coins used to create
BF-s-ciphers(encrypted s_m*)* to Bob.
-Bob checks g・s_m =? g・r_m + g・y_m
-Bob recompute the BF-s-ciphers(encrypted s_m*)* with random coins and
verifies it.
• For all m chosen by Bob
-Alice exposes the corresponding values r_m and the random coins used to
create BF-r-cipher (encrypted r_m) to Bob.
-Bob recomputes the BF-r-ciphers (encrypted r_m) with random coins and
verifies it.
3.Extraction
・In case oracle attestates m which is not selected by Bob
Bob decrypt the BF ciphertext to compute ri, extract y = si −ri from it
・In case oracle attestates m which is chosen by Bob.
Bob decrypts the BF-r-ciphers and BF-s-cipher to compute r_m and s_m,
extract y_m = s_m −r_m
※Note that the random coins used to encrypt r_m and s_ in BF-ciphers should
not be the same.
If the random coins are the same, y_ will be extracted as follows:
y=BFcipher(si) - BFcipher(ri)
—------------------------—------------------------—------------------------—------------------------
Cheers,
Ichiro
2022年10月31日(月) 18:44 Lloyd Fournier <lloyd.fourn at gmail.com>:
> Hey Ichiro,
>
> Sorry for the late reply. My email sometimes degenerates into a LIFO queue
> when I'm busy.
>
> On Tue, 18 Oct 2022 at 10:14, Ichiro Kuwahara <kuwahara at cryptogarage.co.jp>
> wrote:
>
>> Hey Lloyd
>>
>> Thanks for the reply.
>> Let me check if my understanding below is correct.
>>
>> If 100 different oracle attestations are expected (i.e. m=1 or m=2,...
>> ,m=100) Alice needs to create 100 x λ BF-ciphers, sym-ciphers.
>>
>
> Actually, using the bit decomposition trick we're only doing 2*log_2(100)
> = 14 encryptions. So 14*λ BF-ciphers sym-ciphers in the case we're *not*
> batching the verifiable encryptions. Since we are using our batch
> verifiable encryption it's much less. e.g. if λ=40, we'd only need 236
> encryptions (instead of 560). After that you'd take your 100 signatures and
> one-time-pad them with a different combination of each bit value. When the
> attestation is made you can decrypt 7 of the 14 secrets and use them to
> decrypt one (and only one) of the 100 signatures.
>
>
>>
>> Let me additionally check if my understanding is correct.
>>
>> In the paper, Alice creates adaptor signatures with secret value y and
>> encrypts y, Bob verifies it. If we adapt this proposal to DLC, Bob also
>> needs to create adaptor signatures with the secret value (let's say x) and
>> encrypt x, and Alice needs to verify it.The adaptor signature is decrypted
>> with x and y.
>>
>
> I prefer not to explain things in terms of adaptor signatures. You don't
> really need them. We are just one-time padding signatures. That's what
> adaptor signatures do too of course. But usually the encryption key is a
> public key. The encryptor here knows the secret key so there's no need to
> use them. The paper uses them to save space explaining how Schnorr and
> ECDSA can be done together. You don't actually need them in practice.
>
> LL
>
>
>> Does it make sense?
>>
>> Cheers,
>> Ichiro
>>
>> 2022年10月17日(月) 12:30 Lloyd Fournier <lloyd.fourn at gmail.com>:
>>
>>> Hey Ichiro,
>>>
>>> Thanks for reading the paper and for the detailed question. My response
>>> below.
>>>
>>> On Fri, 14 Oct 2022 at 13:15, Ichiro Kuwahara <
>>> kuwahara at cryptogarage.co.jp> wrote:
>>>
>>>> Hi Lloyd, thank you for your interesting proposal,I really enjoyed
>>>> reading the paper:)
>>>>
>>>>
>>>> I have some suggestions for cut and choose techniques, please let me
>>>> know your thoughts.
>>>>
>>>> The following is a quote from *the "Verifiable Witness Encryption." *chapter
>>>> of the paper.
>>>>
>>>> *>If all these checks pass, Bob is guaranteed that there exists at
>>>> least one well-formed BF ciphertext among those λ/2 not opened by
>>>> Alice:meaning that it encrypts rk such that sk = rk+y for some k. Thus,
>>>> when Olivia attests m, Bob can decrypt the k-th BF ciphertext to compute
>>>> rk, extract y = sk −rk from it and then use it to get σ from the
>>>> pre-signature σˆ following the adaptor signature scheme.*
>>>>
>>>> IIUC, the following extraction is possible only if the olivia attest m
>>>> which is included in i ∈ [λ/2] not selected by Bob.
>>>>
>>>> * extract y = si −ri*
>>>>
>>>> If Olivia attests m which is included in j ∈ [λ/2] chosen by Bob, Bob
>>>> can’t extract y because he doesn't get sk(sym-cipher) from Alice.
>>>>
>>>
>>>
>>> I didn't understand the problem. The task of this section is to
>>> verifiably encrypt a scalar to a particular value of m e.g. m = 0 or m = 1
>>> or m = "hello world". All the ciphertexts are allegedly encrypting the same
>>> value to the revelation of a signature on that single value of m. Does this
>>> make sense? It seems like you are thinking that multiple values of m are
>>> being encrypted to on either side of the selection.
>>>
>>> Cheers,
>>>
>>> LL
>>>
>>>
>>>> 2022年8月19日(金) 12:15 Lloyd Fournier via dlc-dev <
>>>> dlc-dev at mailmanlists.org>:
>>>>
>>>>> Hi again,
>>>>>
>>>>> I've just made the benchmark repos for the paper public.
>>>>>
>>>>> Here's the one for the BLS:
>>>>> https://github.com/LLFourn/dlc-verifiable-encryption-bls
>>>>> Here's the one using a simpler non-pairng attestation scheme on
>>>>> ristretto:
>>>>> https://github.com/LLFourn/dlc-verifiable-encryption-non-pairing
>>>>>
>>>>> I don't think we used the ristretto one in the paper. What it shows is
>>>>> how fast things could be with a non-pairing attestation but using the same
>>>>> verifiable protocol. Of course, it is cheating a bit because it's using a
>>>>> heavily optimised curve and implementation. On the other hand there is no
>>>>> theoretical reason you couldn't have an oracle using a ristretto based
>>>>> attestation scheme and encrypt secp256k1 scalars to the anticipation points
>>>>> (other than it being bad taste).
>>>>>
>>>>> Let me know if there are any questions. Sorry in advance about the
>>>>> poor quality of the code. It is strictly for benchmarking only. I hope to
>>>>> build a more production ready API and implementation in the coming months.
>>>>> Hopefully I'll be able to make the curves themselves generic so it just
>>>>> handles the cut-and-choose verifiable encryption part of the thing and you
>>>>> can BYO your own points/scalars.
>>>>>
>>>>> Cheers,
>>>>>
>>>>> LL
>>>>>
>>>>> On Fri, 12 Aug 2022 at 11:46, Lloyd Fournier <lloyd.fourn at gmail.com>
>>>>> wrote:
>>>>>
>>>>>> I want to follow up on an idea.
>>>>>> During our last call Nadav mentioned the "smart contracts unchained"
>>>>>> idea https://zmnscpxj.github.io/bitcoin/unchained.html.
>>>>>>
>>>>>> This brings up an interesting point: if the users agree on the
>>>>>> outcome of the outsourced smart contract they don't even need to contact
>>>>>> the trusted service.
>>>>>> The same thing is true here. In the BLS scheme in the cooperative
>>>>>> case you would need zero requests to the oracle. This is great news for
>>>>>> privacy.
>>>>>>
>>>>>> To take an example, consider that we have a CFD style contract on
>>>>>> BXBT implemented using a WASM smart contract. When I want to settle the
>>>>>> contract I can first visit bitmex.com/api, get the relevant HTTP
>>>>>> response, run it through our WASM contract program locally and see what CET
>>>>>> gets activated. I then send a request to my counterpary to do the same. If
>>>>>> we agree we settle the contract without ever contacting the oracle at all.
>>>>>> This changes the privacy assessment for the scheme very favorably. In the
>>>>>> expected case the users now have perfect privacy from the oracle. Of course
>>>>>> now the users will now contact bitmex.com/api themselves which leaks
>>>>>> to bitmex that you are interested in BXBT at a certain time. This seems
>>>>>> like a much better situation though. Requesting stuff from an API endpoint
>>>>>> seems like a very innocus thing to do and does not imply you are doing any
>>>>>> kind of contract (at least in this example many apps gather data from these
>>>>>> APIs).
>>>>>>
>>>>>> This is really cool since it means the oracle cannot even ballpark
>>>>>> how many people are using their service!
>>>>>>
>>>>>> LL
>>>>>>
>>>>>> PS the paper has been updated now: https://eprint.iacr.org/2022/499
>>>>>>
>>>>>> On Mon, 8 Aug 2022 at 15:36, Lloyd Fournier <lloyd.fourn at gmail.com>
>>>>>> wrote:
>>>>>>
>>>>>>> Hi dlc-dev,
>>>>>>>
>>>>>>> As many of you know, we've been working on how to do DLCs with batch
>>>>>>> cut-and-choose verifiable encryption as opposed to adaptor signatures[1].
>>>>>>> The recent breakthrough we've had is to optimize the protocol sufficiently
>>>>>>> to bring Bitcoin DLCs with a BLS signature oracle into the realm of
>>>>>>> practicality. To ballpark the performance, to batch verifiably encrypt 2048
>>>>>>> schnorr signatures to the attestation of one 2048 outcomes attested via the
>>>>>>> revelation of 11 BLS signatures (one for each bit) takes around 2.57s on my
>>>>>>> laptop (1.7s with pre-processing) with 30bit statistical security.
>>>>>>>
>>>>>>> There's a lot more to say on performance and a few optimizations
>>>>>>> left to make but for the sake of argument let's call that "practical" or at
>>>>>>> least close to it. One optimization I'll ask you to keep in mind is that I
>>>>>>> think the protocol can get a roughly 50% speedup if the payout function is
>>>>>>> monotone because you only need to do verifiable encryption for either the 1
>>>>>>> or the 0 values (not both) in the bit decomposed attestation.
>>>>>>>
>>>>>>> What are the implications of BLS attestations being practical? The
>>>>>>> obvious thing is that we'd be able to get rid of the nonces in the oracle
>>>>>>> announcement because BLS signatures do not require randomness. Just by
>>>>>>> knowing the oracle's public key you'd be able to create a DLC on any event
>>>>>>> as long as you know the oracle will attest to it. Ok but so what? You'd
>>>>>>> still have to query the oracle to see if and how they're going to attest to
>>>>>>> that thing right? On the surface it seems like this wouldn't even save a
>>>>>>> single HTTP query.
>>>>>>>
>>>>>>> It turns out that getting rid of the nonces has huge implications.
>>>>>>> Consider a completely new kind of oracle that doesn't have announcements.
>>>>>>> It just has a single HTTP POST endpoint: "/attest".
>>>>>>> Let's say you want the oracle to attest to the price of BXBT on
>>>>>>> BitMEX at 2022-08-03T12:00:00.000Z. In the POST body you'd send something
>>>>>>> like:
>>>>>>>
>>>>>>> {
>>>>>>> "input" : {
>>>>>>> "url": "'
>>>>>>> https://www.bitmex.com/api/v1/instrument/compositeIndex?symbol=.BXBT&startTime=2022-08-03T12:00:00.000Z
>>>>>>> ",
>>>>>>> "kind" : "jq",
>>>>>>> "filter": ".[]|select(.timestamp ==
>>>>>>> \"2022-08-03T12:00:00.000Z\")|select(.symbol == \".BXBT\")|.lastPrice >
>>>>>>> 23000 | round",
>>>>>>> },
>>>>>>> "output" : {
>>>>>>> "kind" : "bit-decomposition",
>>>>>>> "n_bits" : 20
>>>>>>> }
>>>>>>> }
>>>>>>>
>>>>>>> The oracle -- at the time of your request -- would go to
>>>>>>> bitmex.com/api and fetch the JSON result and apply the jq filter to
>>>>>>> extract the desired value. If you're playing at home this would output:
>>>>>>>
>>>>>>> $ curl -sSL '
>>>>>>> https://www.bitmex.com/api/v1/instrument/compositeIndex?symbol=.BXBT&startTime=2022-08-03T12:00:00.000Z'
>>>>>>> | jq '.[]|select(.timestamp == "2022-08-03T12:00:00.000Z")|select(.symbol
>>>>>>> == ".BXBT")|.lastPrice | round'
>>>>>>> 23409
>>>>>>>
>>>>>>> And so the oracle would -- on the spot -- generate 20 BLS signatures
>>>>>>> for each of the 20 big-endian bits of 23409 i.e. 00000101101101110001.
>>>>>>> Each BLS signature would be made over the request, the bit position
>>>>>>> and the bit value. Having the request in there is key as it allows you to
>>>>>>> anticipate the BLS signature for either bit value ahead of making the query.
>>>>>>>
>>>>>>> I believe this is a huge improvement over the current oracle model.
>>>>>>> Let's look at how this would impact DLC developers and users.
>>>>>>>
>>>>>>> ### Oracles more powerful and much simpler
>>>>>>>
>>>>>>> The key thing to note is that in the above example the oracle
>>>>>>> doesn't need to know about BitMEX, BXBT ahead of time. It can attest to
>>>>>>> anything on the web. It could even attest to values in HTML pages using css
>>>>>>> selectors etc.
>>>>>>> Users could bet on literally any information that can be
>>>>>>> authoritatively sourced on the web (don't do wikipedia!)
>>>>>>>
>>>>>>> The main objection to this might be that oracles shouldn't just take
>>>>>>> whatever is on the web and attest to it: an oracle should be responsible
>>>>>>> for the correctness of its attestations and not pass the blame to a website.
>>>>>>> I don't think this makes sense because (1) grabbing stuff from the
>>>>>>> web is what oracles are doing in practice. (2) There is no primary source
>>>>>>> for BXBT (for example) other than that URL (3) there is no reason in the
>>>>>>> model that users couldn't request the oracle gather data from multiple
>>>>>>> sources and average them or check that at least 3 out of 5 agree etc (4) an
>>>>>>> oracle oracle publishing their own authoritative outcomes for specific
>>>>>>> events perfectly compatible with this model.
>>>>>>>
>>>>>>> The major benefit of this model for oracle implementation is that
>>>>>>> they can be completely stateless. Those of you that run oracles will
>>>>>>> understand what quality of life improvement this is. For users the main
>>>>>>> benefit is application developers being able to add new things to bet on
>>>>>>> without an oracle having to announce that event. I also like that the thing
>>>>>>> you are betting on is completely unambiguous so you can do away with the
>>>>>>> "bounded error" stuff in the current spec.
>>>>>>>
>>>>>>> ### Oracles can process the web data before attestation
>>>>>>>
>>>>>>> Imagine if instead of using jq as in the above example the oracle
>>>>>>> allowed specifying a WASM binary to process the HTTP response(s).
>>>>>>> User applications could then code powerful processing logic that
>>>>>>> would output a bit array. Consider that:
>>>>>>>
>>>>>>> 1. The WASM program could process data from multiple sources and
>>>>>>> apply totally custom logic before outputting the final value (thresholds,
>>>>>>> averages etc)
>>>>>>> 2. Rather than outputting an "outcome" value like 23409 (price of
>>>>>>> bitcoin) in the example, the WASM could map this price directly to CET
>>>>>>> values. So if you wanted to have 1024 different CETs for the range between
>>>>>>> Bitcoin 10k <-> 100k the WASM could map the value 23409 and simply output
>>>>>>> the interval. e.g. (23_409 - 10_000)/(100_000 - 10_000)/(1024 - 1)) ~ 152
>>>>>>> and so the oracle would attest to 152 instead of 23_409. This would mean
>>>>>>> that there's a 1-to-1 mapping between attestation and CET.
>>>>>>> 3. The "payout" function for the processed outcome could always be
>>>>>>> made monotone and therefore very simple to deal with (and the
>>>>>>> optimization I mentioned at the start always applies).
>>>>>>>
>>>>>>> Point (1) is really important for Itchysat's[2] use case where it
>>>>>>> needs to check that during the course of a DLC that the value never went
>>>>>>> above or below a certain value in addition to getting the settlement value.
>>>>>>> Right now (as I understand it) they create a new pre-signed transaction for
>>>>>>> every minute that the contract is alive to enforce this. It'd be great to
>>>>>>> remove this and let the oracle attest to a boolean based on whether the
>>>>>>> price went below at any interval by checking all the values in the BitMEX
>>>>>>> API used above.
>>>>>>>
>>>>>>> Point (2) would in my mind completely remove the need for the
>>>>>>> following specification documents. The logic contained within them would be
>>>>>>> in the domain of the WASM program that the oracle runs before outputting
>>>>>>> the attestation which is agreed by both parties at the application layer.
>>>>>>>
>>>>>>> 1.
>>>>>>> https://github.com/discreetlogcontracts/dlcspecs/blob/master/PayoutCurve.md
>>>>>>>
>>>>>>> 2.
>>>>>>> https://github.com/discreetlogcontracts/dlcspecs/blob/master/NumericOutcome.md
>>>>>>>
>>>>>>> 3.
>>>>>>> https://github.com/discreetlogcontracts/dlcspecs/blob/master/NumericOutcomeCompression.md
>>>>>>>
>>>>>>> There is a downside to this idea in that users are leaking the
>>>>>>> oracle more information about their contract than in the present model.
>>>>>>> Right now you are leaking at least the event but not what the combination
>>>>>>> of events are being used and not how you are mapping the outcomes to payout
>>>>>>> intervals. Leaking the payout intervals could be a bad mistake because if a
>>>>>>> related transaction goes on chain you could check that the value in CET
>>>>>>> output is divisible by the payput interval to attempt to link it. Three are
>>>>>>> simple ways to obfuscate this linkage in practice (an exercise I'll leave
>>>>>>> to the reader!). There might be others I haven't thought of.
>>>>>>>
>>>>>>> There is also a downside for oracles in that you have to attest to
>>>>>>> things as an anonymous user demands. You would need to take care to protect
>>>>>>> against DoS by not creating too many signatures and not letting the WASM
>>>>>>> programs run too long. For reference a BLS signature takes around 1ms to
>>>>>>> create on my laptop.
>>>>>>>
>>>>>>> ### BLS signatures can do non-interactive threshold attestation
>>>>>>>
>>>>>>> Our protocol [1] allows for doing t-of-n DLC protocol where the time
>>>>>>> complexity is roughly linear in n (in fact sublinear). So with 2048 CETs it
>>>>>>> takes 2.57s for one oracle but for a 5-out-of-10 it takes about 21s.
>>>>>>> This part of the protocol is also compatible with non-BLS
>>>>>>> attestations.
>>>>>>> However BLS allows for creating a threshold amongst committee
>>>>>>> members non-interactively. That is, if 10 oracles agreed to form a group
>>>>>>> with a threshold of 5 by generating their keys together using an
>>>>>>> interactive protocol it would be possible to use this committee as a single
>>>>>>> oracle and therefore not have any performance loss. Each oracle could also
>>>>>>> be used individually with the same key but if five signatures were fetched
>>>>>>> from the 10 oracles you could compute the signature from under the group's
>>>>>>> aggregate key.
>>>>>>> Technically this is possible with non-BLS schemes (i.e. FROST) but
>>>>>>> it would require the 5 oracles to interact during the attestation so not
>>>>>>> really practical in the same way.
>>>>>>>
>>>>>>> ---
>>>>>>>
>>>>>>> I am really excited about this but I'll leave the technical side
>>>>>>> there for now. I feel that this is the right way to link the external world
>>>>>>> to Bitcoin. Let me know what you think.
>>>>>>>
>>>>>>> Cheers,
>>>>>>>
>>>>>>> LL
>>>>>>>
>>>>>>> PS the code for the benchmarking isn't public rn because I couldn't
>>>>>>> change the visibility because of 2FA issues. Will fix soon. Also the paper
>>>>>>> at [1] is the the process of being updated to include the new performance
>>>>>>> gains.
>>>>>>>
>>>>>>> [1]: https://eprint.iacr.org/2022/499
>>>>>>> [2]: https://www.itchysats.network/
>>>>>>>
>>>>>>>
>>>>> dlc-dev mailing list
>>>>> dlc-dev at mailmanlists.org
>>>>> https://mailmanlists.org/mailman/listinfo/dlc-dev
>>>>>
>>>>
>>>>
>>>> --
>>>>
>>>> ----------------------------------------------------------------------
>>>> 桑原 一郎
>>>> Ichiro Kuwahara
>>>> Lead Researcher
>>>> Crypto Garage, Inc.
>>>>
>>>> Mail: kuwahara at cryptogarage.co.jp
>>>> Tel: +81-3-5656-2410
>>>> Mobile: +81-70-7469-8774
>>>> ----------------------------------------------------------------------
>>>> Address: DG Bldg., 3-5-7 Ebisu Minami, Shibuya-ku,
>>>> Tokyo 150-0022, Japan
>>>> Web: https://cryptogarage.co.jp/
>>>> ----------------------------------------------------------------------
>>>>
>>>
>>
>> --
>>
>> ----------------------------------------------------------------------
>> 桑原 一郎
>> Ichiro Kuwahara
>> Lead Researcher
>> Crypto Garage, Inc.
>>
>> Mail: kuwahara at cryptogarage.co.jp
>> Tel: +81-3-5656-2410
>> Mobile: +81-70-7469-8774
>> ----------------------------------------------------------------------
>> Address: DG Bldg., 3-5-7 Ebisu Minami, Shibuya-ku,
>> Tokyo 150-0022, Japan
>> Web: https://cryptogarage.co.jp/
>> ----------------------------------------------------------------------
>>
>
--
----------------------------------------------------------------------
桑原 一郎
Ichiro Kuwahara
Lead Researcher
Crypto Garage, Inc.
Mail: kuwahara at cryptogarage.co.jp
Tel: +81-3-5656-2410
Mobile: +81-70-7469-8774
----------------------------------------------------------------------
Address: DG Bldg., 3-5-7 Ebisu Minami, Shibuya-ku,
Tokyo 150-0022, Japan
Web: https://cryptogarage.co.jp/
----------------------------------------------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/pipermail/dlc-dev/attachments/20221104/af740ee2/attachment-0001.htm>
More information about the dlc-dev
mailing list