Request for funding @gene (Adaptor signature atomic swaps GRN-BTC)

Governance
1

Who am I

My name is Gene Ferneau, and I’m a developer and cryptographic engineer. My focus is on privacy-enhancing technologies and cryptocurrencies.

I have been following Grin for a while, and want to become more involved with the project’s development.

What is the project

This project aims to create a no_std library for performing adaptor signature atomic swaps between Grin and Bitcoin.

Atomic swaps are a great way for the decentralized exchange of cryptocurrencies. They remove the need for arbitrage and custodial exchanges.

Recently, Aumayr et al. authored the paper “Generalized Bitcoin-Compatible Channels” which formalizes earlier work on adaptor signatures, introduced by Poelstra for use in scriptless scripts. The main focus of Aumayr’s paper is on generalized payment channels with application to Payment Channel Networks, like Bitcoin’s Lightning Network. Essentially, instead of Hash Time Lock Contracts, adaptor signatures are used to construct the contracts neccesary for payment channels.

Partial signatures are made on channel creation, revoke/punishment, state update, and closure contracts. If either party “adapts” the partial signatures into full signatures, the “witness” (private key) for the full signature is revealed to the other party. By revealing the secret, if either party breaks the contracts,
the other party is able to punish, or force close the contracts. The witnesses are also used by both parties in the update and “peaceful” closure of payment channels.

Codifying the rules with adaptor signatures allows for secure and private construction of payment channels. Removing the need for HTLCs also enhances privacy of on-chain transactions, since adaptor signatures are indistinguishable from normal signatures to outside observers.

Atomic swaps using adaptor signatures can be seen as a special case of payment channels, and can be performed between cryptocurrencies using Schnorr or ECDSA signatures.

The theoretical basis for ECDSA-Schnorr adaptor signatures comes from Hybrid Anonymous Multi-Hop Locks from Malavolta’s et al. work “Anonymous Multi-Hop Locks for Blockchain Scalability and Interoperability”.

In addition to adaptor signature contracts, online watchtowers are needed to constantly monitor the Grin and Bitcoin blockchains for on-chain transactions.

If either party attempts to break the contract of the Funding and/or Commit transaction(s), e.g. the transaction does not appear within a certain time threshold, the watchtower must notify the other party to cancel the swap.

On the Grin side of the swap, Schnorr signatures will be used, with ECDSA on the Bitcoin side. Schnorr signatures are currently being considered for activation on Bitcoin, so Schnorr-Schnorr adaptor signatures will also be possible in the future. For some time, ECDSA will still provide a larger anonymity set for Bitcoin transactions.

Providing a secure option to users for choosing Schnorr or ECDSA on the Bitcoin side is a future goal for the project, after implementing ECDSA-based atomic swaps.

The library should be able to be integrated into the main grin-wallet implementation, and other Rust wallets like Ironbelly.

With some work, C interfaces can also be exposed to enable integration with C/C++ wallets like Grin++ and Bitcoin Core.

Project milestones

  • Implement cryptographic primitives needed for adaptor signatures

    • use secp256k1 and/or secp256k1-zkp as much as possible
    • use bitcoin-hashes as much as possible
    • Pedersen commitments
    • SHA256
    • Fischlin transformation
    • NIZK proof of exponent using Fischlin transformation
    • NIZK proof of exponent for partial ECDSA signatures
    • Schnorr signatures
      • Partial Schnorr signatures
    • ECDSA signatures
      • Partial ECDSA signatures
    • Bulletproofs

  • Implement on-chain Grin transactions for atomic swap contracts

  • Implement on-chain Bitcoin transactions for atomic swap contracts

    • use rust-bitcoin as much as possible
    • Funding transaction
    • Commit transaction

  • Implement adaptor signatures for Grin-Bitcoin side of the swap

    • Schnorr-ECDSA adaptor signature multisigs

  • Implement adaptor signatures for Bitcoin-Grin side of the swap

    • ECDSA-Schnorr adaptor signature multisigs

  • Implement watchtowers for monitoring on-chain transactions

    • may or may not be no_std depending on need to interact with the OS
    • Ensure Funding transaction appears on chain within a certain blockheight delta threshold
    • Watch for Commit transactions being signed to claim funds on the opposing blockchain
      • If timeout occurs, reclaim own funds from the Commit transaction

  • Expose C interfaces for C/C++ Grin and Bitcoin wallets

    • Any wallet able to consume a C API should also be able to use these interfaces

  • Full documentation of the public API and details of the project

    • Documentation efforts will be ongoing throughout the life of the project

  • Test suite including unit and fuzz tests

  • Integration and functional tests using Grin and Bitcoin testnets

    • Testing efforts will be ongoing throughout the life of the project

Outline of atomic swap transaction flow

GRN fnd -> <- rcv BTC fnd -> <- rcv GRN

2-of-2 multisig on funding and commit transactions

Gary is the Grin funder

Blair is the Bitcoin funder

  • Gary sends Blair their proof of ownership for outputs used in the swap
    • Gary’s proof also includes a bulletproof proving the output is at least as large as the agreed swap amount + fees
  • Blair sends Gary their proof of ownership for outputs used in the swap
  • Each party verifies the other party’s proof of ownership
  • Gary creates a (unsigned) funding transaction with the outputs in the proof
    • Blair completes their half of the interactive transaction, and sends to Gary
  • Blair creates a (unsigned) funding transaction with the outputs in the proof
    • Blair sends the transaction to Gary
  • Each party verifies the other’s unsigned funding transaction
  • Each party creates their half of the multisig on the other party’s funding transaction
  • Each party verifies the other’s multisig on the funding transaction
  • Each party creates a commit transaction sending coin to the other party
  • Gary creates a partial signature on their half of the BTC-GRN commit transaction
  • Blair creates a partial signature on their half of the GRN-BTC commit transaction
  • Each party verifies the other party’s partial signature
  • Gary signs their half of the multisig on the GRN-BTC commit transaction
  • Blair signs their half of the multisig on the BTC-GRN commit transaction
  • Each party verifies the other’s signature on the commit transactions
  • Each party completes their half of the multisig on their own funding transaction, and posts to the respective blockchain
  • After the height lock expires on the commit transaction, each party adapts their partial signatures
    • Adapted signatures reveal the spending secret for the other party to claim their funds

Commit transactions will use a lock height to ensure sufficient time for funding transactions to appear on their respective blockchains. Aumayr et al. use a value of 3 blocks. Since Grin’s block schedule is shorter than Bitcoin’s, a lock height equal to 3 Bitcoin blocks should be used on the Grin side (i.e. 30 blocks).

The funding transaction needs a conditional lock height on the Grin side to ensure Gary can retrieve their coins after a certain time (e.g. Blair fails to post their funding transaction). Similarly, the Bitcoin funding transaction should have a conditional lock height. The lock height should be higher than the time expected for an honest completion of the swap protocol.

If, at any stage, verification of signatures and/or proofs fail, the protocol must be stopped. Any timelocked funds should allow the lock to expire, and reclaim the funds.

Bitcoin multisignatures may either be implemented using multisig contracts, or 2P-ECDSA threshold signatures.

Potential issues

Further research is needed to fully implement the atomic swap protocol, and the protocol outlined above may change during implementation.

I have done my best to perform due dilligence in my research so far, but some details only come up during implementation.

The future is uncertain, and for any number of reasons, I may be unable to finish the project.

My plan is to provide in-depth documentation, and clearly understandable code.

Good documentation will be beneficial by making it easier:

  • for review / feedback
  • for other projects to integrate the library
  • in case I need to hand off work to another person / team.

Project timeline

Timelines are difficult for research-intensive projects. The best estimate I can give for an optimistic timeline is ~3-4 months for a minimum-viable-product.

There could also be unknown problems that come up, that may mildly or drastically extend the timeline.

Funds requested

I am requesting 40.000 EUR equivalent in BTC, based on the 60-day rolling average at the time of payout.

I would prefer payouts based on milestones achieved to prevent an all-or-nothing situation.

I am open to suggestions on funding amount, and payout schedule.

Being new to the Grin community, I would understand hesitance over my competence to complete a long-term project. So, I am very open to discussion about possibilities for increasing funders’ confidence in my abilities.

26 Likes
2

give a man his money :+1: :+1:

3 Likes
3

cool, just go ahead !

4

@gene would you also consider being payed for 25% in GRIN instead of BITCOIN only?

5

Absolutely love it! @tromp what would the next steps be to see this realized? TY

1 Like
6

Funding request are discussed and decided on in the next governance meeting after the request has been up for a week.

3 Likes
7

relevant rust btc/grin atomic swap

mw-btc-swap (github.com)

@jabfalter

3 Likes
8 
relevant rust btc/grin atomic swap

mw-btc-swap (github.com) 5

@jabfalter

Thanks for posting this @gringineer, I wasn’t aware of @jabfalter’s work.

@jabfalter nice work on the atomic swap tool. It looks like you’re using adaptor signatures, too.

What state would you say your tool is in? Do you have a working PoC swap on testnets already? I would hate to duplicate any more work, and waste people’s time and money if Grin-Bitcoin atomic swaps using adaptor signatures is already implemented.

I see that you use a function grin_core::ext_witness for adapting signatures to reveal the witness, were you planning to make a PR upstream? AFAICT, this function doesn’t exist on your fork of the grin repo, nor on the main repo. Is it local only?

Also, I would be very interested to read your master’s thesis, is it online anywhere?

2 Likes
10

Hi @gene

First of all thanks @gringineer for mentioning my project. :slight_smile:

I am currently working on my master’s thesis in which I am formalizing Bitcoin Mimblewimble atomic swaps and proving security of the two-party adaptor signature used during the swap, as well as proving security of the different kinds of Mimblewimble transactions used during the swap. As part of the thesis, I implemented a POC in Rust jafalter (Jakob Abfalter) · GitHub .
The implementation is already working on the testnets, it is using fixed witness adaptor signatures on the grin side. (which are aumayrs adaptor signatures, but adjusted to the two-party signature protocol used in mimblewimble)
Some parts of the implementation (for instance the MP Bulletproof computation) were taken from Jaspers GitHub - vault713/grinswap: Cross-chain Atomic Swaps in Grin that was done by him some time ago.
On Bitcoin side I am using a CHECKMULTISIG with CHECKTIMELOCK_VERIFY P2SH script to allow refunding the funds if the swap fail after a timeout.
In my repo I am using my own forked version of grin-wallet, however the changes I did, I also posted as PRs to the repo, one of them is already merged, the second one will probably be soon as well.
Other then that I don’t use anything special. (I also have a module inside the repo called grin_core which might be what you have seen, but it has nothing to do with the actual grin core repository, I admit that was some bad naming from my side :slight_smile: )

Notice that this was my first ever Rust project, so I am not an expert in this language, also some of the code is not suitable for production, for instance, I am storing private keys etc. simply in an unencrypted file, also the inputs used on bitcoin as well as on grin side have to be first imported before the swap can start.

Communication between the two parties currently happens via TCP Socket, one also needs to have access to a running bitcoin core and grin node to send JRPC requests via HTTP. I have provided some docker-compose configuration such that it can be tested rather easily.

My thesis document is almost finished, I will probably be able to finalize it in April, if you want I can send you the current version.

Anyway, I think it would be really cool if you build a production-grade version of the Atomic Swap. I believe you can reuse large parts of my implementation and if you build the protocol as it is specified in my thesis you can point to my formalization and security proofs.

If you want to receive my thesis document or have any more questions about my code please reach out to me via jakobabfalter@gmail DOT com

6 Likes
11

In my repo I am using my own forked version of grin-wallet, however the changes I did, I also posted as PRs to the repo, one of them is already merged, the second one will probably be soon as well.
Other then that I don’t use anything special. (I also have a module inside the repo called grin_core which might be what you have seen, but it has nothing to do with the actual grin core repository, I admit that was some bad naming from my side :slight_smile: )

Ok, I must have been looking in the wrong places, thanks for clarifying. No worries about the naming. For a first Rust project, your work is really impressive.

My thesis document is almost finished, I will probably be able to finalize it in April, if you want I can send you the current version.

Awesome, good luck on it! I wasn’t sure if you were already done is why I asked. I can wait to read the finished product :wink:

Anyway, I think it would be really cool if you build a production-grade version of the Atomic Swap. I believe you can reuse large parts of my implementation and if you build the protocol as it is specified in my thesis you can point to my formalization and security proofs.

Definitely, as I progress with the project I was planning to also look at @jaspervdm’s work more closely, as well. (Have done a basic review, but nothing in-depth). Having more work as a reference would be great.

Our approaches and goals are different, but there is definitely enough overlap for the projects to be beneficial to each other.

Thanks for choosing to do academic research on Grin :heart:

5 Likes
12

Added to the agenda: Agenda: Governance Mar 30 2021 · Issue #410 · mimblewimble/grin-pm · GitHub

4 Likes
13

I’m not sure how to edit the original post, but have a small update on the zk-PoK of exponent used for partial signatures.

In Aumayr et al. they describe using a Fischlin transformation style proof to prove knowledge of exponent used in the partial signature public key:

y in Zp ^ Y in G ^ g in G ^ Y = y*g

A separate proof (not necessarily needing Fischlin proof with an extractor), is needed for proving knowledge of an additional exponent and relationship:

k in Zp ^ K~ in G ^ g in G ^ K~ = k*g ^ Y in G ^ K in G ^ K = k*Y

In the Bulletproofs paper by Bünz et al. there is a section dedicated to proofs of generalized arithmetic circuits. This section seems to directly apply for both of the above proofs.

The second proof might be achieved with a more simple Schnorr-style proof using the Fiat-Shamir heuristic to make it non-interactive. However, the first proof explicitly cannot use Schnorr proofs due to the need for what Fischlin calls an “online extractor.” Bulletproofs seem to fulfill the need, though they also use the Fiat-Shamir heuristic.

Do more experienced cryptographers think this is a good line of research to pursue? Without having implemented yet, my impression is that Bulletproofs would be more efficient than Fischlin. Since Bulletproofs are similar in structure, they seem to carry similar security properties. Bulletproofs also solve for communication inefficiency of sending t hash queries + responses from the prover to the verifier.

Would one of the more experienced cryptographers be interested in working on a proof construction with me (even if it is just providing guidance)?

Will likely begin by implementing Fischlin proofs anyway, since I will need them for performance benchmark comparison. The theoretical work is also already there, so the work will go quicker. However, I think for future implementation, a Bulletproof construction will be much more efficient.

14

Request for continued funding for June 2021

Over the past couple weeks, a couple road blocks have come up in the atomic swap implementation. I made some incorrect assumptions about parts of Succinct Atomic Swaps I could replace with current Grin documentation atomic swaps, and didn’t realise the need for mutlitparty outputs.

Multiparty outputs are similar to multisignatures in other blockchains, where multiple parties control UTXO(s). For atomic swaps, these will be equivalent to 2-of-2 multisignatures over the output(s) produced by Grin Fund, and used by Grin Success, Grin Revoke, Grin Refund, and Grin Timeout transactions.

Originally, I thought Grin’s mutlisignature kernels were sufficient for a secure protocol, but multiparty outputs are needed to ensure shared control of outputs in both the Grin docs atomic swaps and SAS.

To implement multiparty outputs, multiparty range proofs (bulletproofs) need to be exposed to the rust-secp256k1-zkp library. Thankfully, the implementation is already present in the C secp256k1-zkp used by Grin. The rest of the implementation will consist of adding CLI/RPC APIs to allow grin-wallet users to construct an aggregate commitment and rangeproof over an output.

The Grin Refund and Grin Timeout transactions also need to be added, along with verification of the correct ouputs being used (i.e. Grin Success + Grin Revoke spend the output from Grin Fund, and Grin Refund + Grin Timeout spend the output from Grin Revoke).

Hopefully, I should be able to get a MVP implementation done by the end of June, and have something ready for the community to review.

I’m open to any questions and/or concerns the community has, so please feel free.

I am requesting continued funding for June 2021 at the same rate of 10k euro in Bitcoin (using 60-day rolling average).

Thank you for all the support the community has shown for my work so far, I look foward to contributing to the Grin ecosystem.

PRs of current work:

11 Likes
15

I’m glad to see progress on Atomic Swaps, I think this is something that a lot of people are asking for a long time. The work done and the commitment to delivery Atomic Swaps is undeniable.

I do remember that the funding request was discussed and approved during the past March 30th meeting, but the request changed a bit during the meeting, would you mind to clarify how was approved, please? it was approved as 10k monthly month by month?

Thanks.

8 Likes
16

The original request estimated 3-4 months for completion, which is looking more like 3 months now (by end of June). Time estimates are hard, and I’m trying to adjust expectations the deeper I get into implementation.

We agreed to work on month-to-month funding approval and payouts. Partly due to me being new to the community, partly due to the uncertainty of the timeline. The next month of funding is considered for approval at the beginning of the month, payout approval/denial comes at the end of the month.

3 Likes
17

After a conversation with @joltz. I am posting to request a payout for May and June of 2021.

Logs approving May and June funding:

keybase://chat/grincoin#general/34895
2021-06-08 joltz: Does anyone have any opposition or concern related to Gene's request that they'd like to share here?

keybase://chat/grincoin#general/34905
2021-06-08 dburkett: It's good to have @geneferneau around. I've been reading his updates, but haven't been following the RFCs & code as closely as @tromp and @phyro. If they are happy with his progress, then I am on board with continuing his funding :+1:

keybase://chat/grincoin#general/34919
2021-06-08 tromp: i'm ok with continued funding but do want to see more work on the RFC that are still lacking in detail

keybase://chat/grincoin#general/34915
2021-06-08 joltz: Ok it sounds like we will complete Gene's payment for May and continue funding for June :+1:

I never received funding for May or June, the only payout I have received was for April.

We were supposed to have a meeting at the beginning of July to discuss my funding for that month. No main governance meeting happened, and I can only find logs for community council meetings after the June meeting.

I still continued to work into July, without guarantee/expectation of pay Grin-Bitcoin Adaptor Signature Atomic Swap update thread - #36 by gene.

Over the few months working on atomic swaps, I did my best to go above and beyond for Grin. Please pay me for the work I have completed, and the Grin council agreed to fund.

10 Likes
18

Definitely! I thought this was solved.

@stakerV would you mind to add this to today’s meeting? We need to find a resolution to this ASAP.

2 Likes
19

I have added this to today’s agenda.

20

May to October. it is almost 5 months.

21

I agree payment is overdue.

Regarding the deliverables, I was under the impression that funding was for an implementation of Succinct Atomic Swap, with the distinct advantage of needing only 1 tx on the bitcoin side. You abandoned that approach and went with the inferior non-succinct atomic swap.

I didn’t have time to review the new RFC until recently, but found its protocol description rather unclear. Could you address my comment on Atomic Swaps by GeneFerneau · Pull Request #83 · mimblewimble/grin-rfcs · GitHub ?

3 Likes