search

discreetlogcontracts / dlcspecs

Specification for Discreet Log Contracts
Creative Commons Attribution 4.0 International
239 stars 36 forks source link

Introduce first version of ECDSA adaptor signature spec #114

Closed LLFourn closed 3 years ago

LLFourn commented 4 years ago

This is a draft of the ECDSA adaptor signature spec.

Feel free to post an early review on structure, format and design decisions. See if you can find any mistakes in the algorithms.

TODO:

Fixes #50

LLFourn commented 4 years ago

@benthecarman That was intentional. I tried to put references in [ ]. I haven't put a list of references at the bottom yet. I find just putting links annoying because then you have to figure out what word to put them on. Perhaps now is the time to make a convention for how to do this?

NicolasDorier commented 4 years ago

@LLFourn trying to make your test pass:

First vector, I can't parse the adaptor sig,

036c2f34833942e6eebb9e01b71c1d5f6ea185e7af607805ab5a39a829ad7a30400220f57f812e043e0f5b5c8c22a5c6efe6f76cdaa71490f7b3a3adb7a39101bf7ad4ee4d049e573adee6647ab7d97445d87c4252d91a627935269e99703a7d4161a5b4e2675d09e0da65deb2ed6210e5e99244153e9600ed17d90f6f31853e2c5ff8680adcbd1393d1ae8eed5cd8a8e396275be95506bf40a20ac22f66ca875bf4

It seems to fail here

https://github.com/nkohen/secp256k1/commit/33834591c81616b2e4fde1b0c0a2ae7f88af1147#diff-af7e1bf67c999123aba5f3f14622539c6ac8eb6ce92676ccaa1f5c418bed6574R45

Basically the first FE seems to be too big?

NicolasDorier commented 4 years ago

What is the verification_key?

LLFourn commented 3 years ago

@NicolasDorier This code doesn't conform the spec yet.

From the spec:

So it can parsed like

036c2f34833942e6eebb9e01b71c1d5f6ea185e7af607805ab5a39a829ad7a3040  #R
0220f57f812e043e0f5b5c8c22a5c6efe6f76cdaa71490f7b3a3adb7a39101bf7a      #R_a
d4ee4d049e573adee6647ab7d97445d87c4252d91a627935269e99703a7d4161   #s_a
a5b4e2675d09e0da65deb2ed6210e5e99244153e9600ed17d90f6f31853e2c5ff8680adcbd1393d1ae8eed5cd8a8e396275be95506bf40a20ac22f66ca875bf4 # proof

To make the code conform I think there are only a few small changes:

needs to be instead:

    secp256k1_sha256_initialize_tagged(&sha, algo16, algo16_len(algo16)); # this needs to be the tag from the spec instead
    secp256k1_dleq_hash_point(&sha, p1);
    secp256k1_dleq_hash_point(&sha, gen2);
    secp256k1_dleq_hash_point(&sha, p2); 
    secp256k1_dleq_hash_point(&sha, r1);
    secp256k1_dleq_hash_point(&sha, r2);

I think that's all you'll need to change to get the verification test vectors to pass. After that I would go over the signing code and make sure the nonces are produced in a way that at least approximates the spec (everything that is recommended to be hashed to produce a nonce it hashed).

@jesseposner has offered to do the work to make the above happen.

What is the verification_key?

I meant the public signing key. I've changed the test vector to use this instead.

NicolasDorier commented 3 years ago

does that mean that all tests vectors that we finally all pass from @nkohen need to follow this new spec? If not, it should be same format, else we are testing different things.

LLFourn commented 3 years ago

@NicolasDorier Yes. Any end-to-end test vectors need to be updated. My main goal with this spec is to separate the DLEQ proof from the ECDSA adaptor (since it might be independently useful). Obviously another approach could be just to spec what's in the branch but I thought it would be better to come up with something a little more thought out and easy to justify (not that the all the justifications are in the document yet).

NicolasDorier commented 3 years ago

Not to say the spec is frozen, but at this stage several implementation follow it, and breaking it without good reason (like security fix/features) will just waste everybody's time.

Both those tests and the specs must be in sync. If somebody come to this repository, and implement DLC starting by this document, most of his effort won't help him to implement the DLC specification. (Formatting data correctly is as much time consuming as monkey porting the math)

So in the worst case: A developer come here, pass the tests, then find out that it is not following the spec, update his code to follow the spec, but then the unit tests he did to pass this vector won't pass anymore.

NicolasDorier commented 3 years ago 
036c2f34833942e6eebb9e01b71c1d5f6ea185e7af607805ab5a39a829ad7a3040  #R
0220f57f812e043e0f5b5c8c22a5c6efe6f76cdaa71490f7b3a3adb7a39101bf7a      #R_a
d4ee4d049e573adee6647ab7d97445d87c4252d91a627935269e99703a7d4161   #s_a
a5b4e2675d09e0da65deb2ed6210e5e99244153e9600ed17d90f6f31853e2c5ff8680adcbd1393d1ae8eed5cd8a8e396275be95506bf40a20ac22f66ca875bf4 # proof

For R, in the spec, the first byte seems to have meaning. https://github.com/nkohen/secp256k1/commit/33834591c81616b2e4fde1b0c0a2ae7f88af1147#diff-af7e1bf67c999123aba5f3f14622539c6ac8eb6ce92676ccaa1f5c418bed6574R48

LLFourn commented 3 years ago

Not to say the spec is frozen, but at this stage several implementation follow it, and breaking it without good reason (like security fix/features) will just waste everybody's time.

My feeling was when I was asked to do this specification the expectation was that there would be breaking changes to what exists in the branch.

The purpose of this spec is to do the DLEQ proof something like how it a generalized framework for expressing these kinds of proofs would specify it (I am working on such a framework). Perhaps this is premature but I think it's better to be as close as possible to "textbook". The time waste may additionally come when someone wants to use a DLEQ proof for their protocol but does want to use the branch as it has some rough edges to it -- so they re-write an incompatible one.

For R, in the spec, the first byte seems to have meaning. nkohen/secp256k1@3383459#diff-af7e1bf67c999123aba5f3f14622539c6ac8eb6ce92676ccaa1f5c418bed6574R48

Well spotted. It seems that points are not being SECG encoded but rather being prefixed with a 0 or a 1 instead of the usual 2 or 3.

nkohen commented 3 years ago

I think breaking changes here are okay/good to have, but I will note that I do not plan to actually make any other part of the DLC spec or implementations conform to this new ECDSA adaptor spec until there is a stable branch on secp256k1-zkp that we can all use. Once such a branch exists, it should be significantly easier for everyone to switch to using that branch instead of my temporary one and I have code to auto-regenerate the test vectors (which other impls should be able to pass, simply by using the new crypto library)

jesseposner commented 3 years ago

I implemented the spec in Python here and it runs and passes all the test vectors.

jesseposner commented 3 years ago

Here's my secp branch that updates the implementation to match the spec: https://github.com/jesseposner/secp256k1/tree/jp/ecdsa-adaptor-sigs

This commit has the diff showing the changes that are required to match the spec: https://github.com/bitcoin-core/secp256k1/commit/3246e15f9cb5aceefc6a16be5362928ff83ff463

I've also added the first test vector and it passes: https://github.com/bitcoin-core/secp256k1/commit/a8ae2126a41f24bc100a76e7deb00e0e8c21c2f0

I will be continuing to work on that branch to finish the TODO items and add more test coverage.

draft PR: https://github.com/ElementsProject/secp256k1-zkp/pull/117

NicolasDorier commented 3 years ago

I think breaking changes here are okay/good to have, but I will note that I do not plan to actually make any other part of the DLC spec or implementations conform to this new ECDSA adaptor spec until there is a stable branch on secp256k1-zkp

In this case, this spec should conform to the current spec, then we should just change this spec and the old spec later. If we merge this we start having different spec inside the same repo, this is confusing as hell.

LLFourn commented 3 years ago

@NicolasDorier I think there's no reason why @nkohen couldn't push changes to the other spec tests to this branch so they are both merged at the same time.

NicolasDorier commented 3 years ago

I am pausing work on DLC until the protocol is settling, this is quite depressing to write code, take time to follow test vectors, only to get them regenerated to follow a different spec that does the same thing later on, it feels like running in a treadmill. Wake me up when things stop moving and the test vectors stop moving.

LLFourn commented 3 years ago

@jesseposner I've updated the spec to just use the tag "DLEQ". I've also added another kind of test vector that just tests recovery. Let me know when you've done the implementation :)

jesseposner commented 3 years ago

@LLFourn I've updated https://github.com/ElementsProject/secp256k1-zkp/pull/117 with the new changes and test vectors.

LLFourn commented 3 years ago

@jesseposner Thanks. Will review soon.

jesseposner commented 3 years ago

@LLFourn I'm going to be rebasing to clean up the commits soon in the PR, which should make it much easier to review as a whole (but more difficult to isolate the changes from the original branch).

jesseposner commented 3 years ago

I've cleaned up the commits and it should be a lot easier to review now by proceeding commit by commit. I'm giving it one last round of polish today and then I will fill out the PR description and move it out of draft mode.

jesseposner commented 3 years ago

@LLFourn The PR is now stable and out of draft mode. The only thing that should change at this point is updates to respond to comments and potentially adding some additional test cases.

jesseposner commented 3 years ago

@LLFourn Any thoughts on including a warning about the leakage of the DH key between the signing key and encryption key? I was thinking some guidance might be warranted here, for example suggesting that DH protocols not be used for these keys.

LLFourn commented 3 years ago

This document is ready. As I said before I think it would be good if all spectests were updated to align with this one so all the documents are consistent.

NicolasDorier commented 3 years ago

A reminder that this should be merged (or not). I am waiting for the spec to be stable before continuing any work on DLC, so as long as this is in "maybe merge, maybe not", I am on the sideline. :/