A DAO using Schnorr signatures for all Reddit wallstreetbets members

[synctext]

Goal: proof-of-principle prototype of a DAO with 8.8 million members (number of people in this Reddit).

Ordinary Internet users have for the first time driven Wall Street professional speculators into a corner. We want to further strengthen their power. We will use Bitcoin to democratically control funds collectively owned by 8.8 million people. Future features would include: discover DAOs,join,leave, and vote on investment proposals.

Taproot inside Bitcoin will allow us to expand our existing Delft University DAO prototype with muti-sig aggregation: https://github.com/taprootactivation/Taproot-Activation The "key" problem is to facilitate 8.8 million signatures in a DAO, but not require full storage of each individual signature. This has been done for a 10million-out-of-10million multi-signature wallet, great accomplishment @jonasnick. As a proof-of-principle the issue is to:

• establish the computational time for a 4.4million-out-of-8.8million multi-signature wallet (simple majority voting for DAO governance)
• investigate if parallelism and even GPU acceleration is possible

Outcome: Python script for 4.4million-out-of-8.8million multi-signature transactions (50% as minimal threshold for democratic participation and legitimacy of vote)

https://www.coindesk.com/taproot-bitcoin-upgrade-improve-technology-software https://github.com/jonasnick/musig-benchmark

[devos50]

After a bit of research, it seems that getting Schnorr signatures up and running is not only a requirement for "large-scale collective money ownership" but can also be a step towards an efficient cross-chain liquidity pool where a group of stakeholders manage/co-sign transfers from/to wallets.

It seems that there are Python bindings available for the secp256k1 library (the crypto library used by Bitcoin core), but these bindings are heavily outdated. The activation of Taproot re-organized most of the Schnorr signature primitives. To play a bit around with this technology, and to integrate it in an IPv8 community with actual agents, a first step could be to update these bindings and test them against the reference test vectors.

[devos50]

Update: I've extended the Coincurve Python bindings with support for Schnorr signatures. In summary, I had to write a few additional CFFI bindings for methods related to Schnorr signatures and public key management but now I'm able to sign and verify digital signatures fully in Python, using the secp256k1 library. Changes: https://github.com/devos50/coincurve/commit/d21b94c713f3adce2b63a3ce3808c16db5cd9f3b. The next step would be to generate multi-signature transactions from Python, using the musig benchmark.

[jonasnick]

Hey everyone, chiming in since I got tagged in the OP. A 4.4million-out-of-8.8million spend would be a really nice benchmark which may perhaps even have applications in the real world.

If I understand correctly, what complicates the implementation of this idea is that MuSig only supports true multisignatures, i.e. n-of-n and therefore every signer must sign individually to produce a final signature. This is unfortunately easy to misunderstand, because in contrast to the applied crypto literature, "multisignature" in Bitcoin refers to the more general t-of-n constructions.

After activation of taproot, applications can emulate a t-of-n threshold signature using a disjunction of t-of-t multisignatures. This is due to the Merkle Tree of spending conditions in taproot. Take every t-combination of the n signers and append the corresponding t-of-t aggregate key to the Merkle Tree. But in your scenario, the number of leafs would be astronomically large (8 million choose 4 million).

The best bet is to build this application using FROST threshold signatures. Schnorr threshold signatures are similar to multisignatures, but have an interactive key setup process in order to split every signers key into shards that can be sent to every other signer. @jesseposner is working on an implementation of FROST in libsecp-zkp.

[devos50]

@jonasnick thanks for your comment! I decided to tackle the n-out-of-n signing as a first step, and to get some familiarity with the secp256k1 library.

My follow-up question was indeed how to convert this scheme to t-out-of-n, but you have answered that now :). I was not aware of FROST and I will check that out, thanks for linking! 👍

[devos50]

Update: I now have a fully functional implementation of FROST in Python, using the more mature frost-dalek RUST library. There is no networking support so far. To interface with this code from Python, I have written a bunch of Rust <-> Python bindings which can be found here. The output of the frost_test.py script gives the following:

Done generating distributed key, group key: f299b914eb262e27813529df2c0b8642ae2a8e38b20895926ba7740a440f3d5b
Partial signature of Alice: d2ba666bcda25c1bddb8193b3eb1397af11948827ca3875c6953ef75ff7a3205
Partial signature of Carol: dcf3b6232f0d237f55306a5c17263af921957ecb94786bcc99d3de1ebcdaa60b
Resulting threshold Schnorr signature: da8fe01ac4c60a69bf34a5407fbe95aba970c742f38b3e0166f016677b829778c1da2732e24c6d425c4c8cf476dd945e13afc64d111cf3280327ce94bb55d900
Signature valid :)

So the code seems to correctly generate a 64-byte Schnorr signature that could be embedded in a Bitcoin transaction.

A few notes:

• The frost-dalek library has a nice interface and is relatively easy to work with. Given that the FROST implementation in the secp256k1-zkp is still highly WIP, I recommend to use the Rust library for now.
• FROST requires an interactive key setup (based on the Pedersen DKG), which requires two rounds. In the first round, participants broadcast their commitments to each other and in the second round, participants send personalized secret shares to all other users. I suspect that this two-round protocol will become a bottleneck since it requires O(n^2) messages if avoiding a central share manager. As such, maintenance of the DAO (joining/leaving members) is relatively expensive since it requires a re-run of the DKG protocol.
• The group key resulting from the DKG protocol should be used as (Bitcoin) wallet address.
• I used the preprocessing stage (Figure 2 in the FROST paper). I think this is practical since the initiator of a particular transaction can act as aggregator.
• I believe it is possible to integrate this stuff in the superapp. I see the following two approaches, both would require some work with JNI:
  • Writing Java/Kotlin <-> Rust bindings, e.g., using jni-rs.
  • Since BitcoinJ has experimental support for the secp256k1 library, one could also choose to use the (WIP) FROST implementation in secp256k1-zkp.

[jonasnick]

Is the frost-dalek library able to produce BIP-340 compatible signatures, i.e., the specification of Schnorr signatures that is going to activate on Bitcoin?

[devos50]

@jonasnick the frost-dalek library does not seem to produce BIP-340 signatures, so that's an oversight from my side 😁

[devos50]

I also completed the Python bindings to the FROST implementation in the secp256k1-zkp library, which is able to produce BIP-340 compatible signatures:

/usr/local/bin/python3 /Users/martijndevos/Documents/coincurve/frost.py
Participants: 4, threshold: 2, #signers:  3
Group public key: ee7df62661ee73668c09b9e38694ed6da836b3078359a1be286dcca2386c3a59d046391a243bc64cbc4de79c89d8a368a60ef530dbbc4f2b2ecf8b9a98c71cef
Nonce pubkey of participant 1: eef31dbc60e889b698d39d47de21a3d653e0936181d02af28fbaa5c531934cf9b7a172a8157a10c65b66cc95619e6f5c22e4918d5a79fa78e978f2aa1f9b082f
Nonce pubkey of participant 2: 299c6bd7a5a17c8ac629a281a6c8933dca7175f39bd6fec2bce82ad63980664ab4170fad2dbe36455801e45a1c7fb635a5e0133a06a5a6df126a6288ad343d40
Nonce pubkey of participant 3: a712468f05070b69d0d7a409e19d17cfbf9359a61ae64e9fd682228355a227431d7e85b8bd32cc392c990b05d92bbd26b08911ea24a32ec99f0d92fdbf5a7c76
Combined key: 633b04d9c89ba42d1a873b873138dea34150a904ea3656f0aeb1331b5f6dc1e4fe1403bacaeeab5448bc34750b4a4e4c0436ac5e37dad8421ec079024bcac816
Partial signature of participant 1: 202033b28895c57c3f85a8a8d0e66782ca1924b8380d14fdbb9bbadf14863d5d
Partial signature of participant 2: 562fa2d5536f0e593ac57c48374e8fbf3b60d9df1d7941c008378cc3b3706f68
Partial signature of participant 3: dd42916d31af4bf46679d649abf6e89beef9965b3f6d9983b74901a844751ff6
Resulting Schnorr signature: e4c16d5f1b33b1aef05636ea04a95041a3de3831873b871a2da49bc8d9043b63539267f50db41fc9e0c4fb3ab42bdfdf39c4b80be5ab5005bb49eabe3c358b7a
SCHNORR SIGNATURE VALID

Python code can be found here.

[synctext]

Very impressive work people!
@awrgold is as of today committed to working full time on this topic also. His master thesis+survey spans a full 12 months nominally of effort. Thesis assignment: a production DAO on Android devices with 1TByte of storage https://github.com/Tribler/tribler/issues/5313#issuecomment-913407262 Any FROST implementation ready for production usage? {btw You're very welcome @jonasnick to fly into Amsterdam airport and give a research talk on this stuff at our university Lab (Corona-permitting, we'll refund the trip+stay)}

[devos50]

@synctext since the FROST algorithm is quite new, there are no matured implementation as far as I'm aware. The most mature implementation seems to be frost-dalek, written in RUST, but that implementation does not produce Bitcoin-compatible Schnorr signatures. For compatibility with Bitcoin, the only available implementation seems to be this (WIP) PR to the secp256k1 library. Since the goal seems to integrate this into the Android superapp, one approach could be to explore the experimental support for secp256k1 in BitcoinJ and use JNI to invoke the necessary FROST functions. One warning though: generating Schnorr signatures seems to depend on some private APIs so I had to modify the secp256k1 source code here and there...

@awrgold I would be happy to discuss more technical details if you're interested in that 👍

[devos50]

Another user working on FROST scalability posted some performance results in the FROST code repository.

The system I am implementing assumes a hive of signers where each one contributes to a large number of different signing sub-hives. Reducing signers' node memory consumption is critical to allow a signer to contribute to as many sub-hives as possible.