This post is syndicated from rubin.io.
Welcome to day 25 of my Bitcoin Advent Calendar. You can see an index of all the posts here or subscribe at judica.org/join to get new posts in your inbox
The title of this article is a joke. Gotcha!
Decentralized Autonomous Organization is pretty much what’s called an orphan initialism. So while DAO doesn’t really mean anything is decentralized, autonomous, or an organization, but the term DAO has stuck around anyways. Even moreso than NFT! More or less, DAOs are just fancy multisigs. But they’ve been used for all sorts of things, ranging from attempting to buy the US Constitution as a group, investing in startups, buying Ross Ulbricht’s NFTs, or maybe even buying my undies.
This post has some required reading. You have to have read through at least up to payment pools in the advent calendar, but ideally you’d have read all the posts…
So how will fancy-multisigs save Bitcoin? In this post we’ll work through an example of building a DAO to fund Bitcoin Core Developers, like a Bitcoin native Gitcoin competitor.
What do we want from our DAO:
The DAO will serve three functions:
- To Add members who pay in
- To make Payments if a Majority of the payers by value vote
- To mint commemorative NFTs
Majority rules
DAOs are little democracies, and as such we need a voting scheme to do rule changes whereby a threshold (e.g., 51%) decides what happens next. We have two options, we can either count individuals as equal, or we can weight by amount of funds contributed. We can do any threshold we like, it’s just “this many people could steal the whole pot”.
For this post, we’ll do the weighted by funds contributed because that feels closer to what’s happening in Ethereum land. Unfortunately a couple components around generated arbitrary weighted signatures1 just “aren’t quite there” or have messy tradeoffs so we won’t consider those – yet. Instead we’ll just make a silly limit: we will allow at most 24 participants2.
Implementing a DAO
First let’s define the basics. A DAO should have Members who each are ID’d by a key and have an amount of votes.
#[derive(Deserialize, JsonSchema, Serialize, Clone)]
struct Member {
relative_votes: u64,
}
#[derive(Deserialize, JsonSchema, Clone)]
struct Dao {
/// # Pool Members
/// map of all initial balances as PK to BTC
members: BTreeMap<PublicKey, Member>,
/// The current sequence number (for authenticating state updates)
sequence: u64,
}
impl Contract for Dao {
declare! {updatable<Proposal>, Self::hold_vote}
}
Members can hold a vote on a proposal of some kind. Let’s do proposals that can make payments, mint NFTs, or add some noobs:
/// New Update message for generating a transaction from.
#[derive(Deserialize, JsonSchema, Serialize)]
enum Proposal {
/// # Payments
/// A mapping of public key in members to signed list of payouts with a fee rate.
Payments {
payments: BTreeMap<PublicKey, AmountU64>,
// Some purpose for this proposal, as a String.
reason: String,
},
/// # Mint
/// Make some NFTs
Mint {
minting_module: SapioHostAPI<Mint_NFT_Trait_Version_0_1_0>,
mint_data: Mint_NFT_Trait_Version_0_1_0,
},
/// # Add People
Add {
noobs: BTreeMap<PublicKey, Member>,
},
None,
}
/// required...
impl Default for Proposal {
fn default() -> Self {
Proposal::None
}
}
impl StatefulArgumentsTrait for Proposal {}
/// helper for rust type system issue
fn default_coerce(k: <Dao as Contract>::StatefulArguments) -> Result<Proposal, CompilationError> {
Ok(k)
}
Now we can implement the main logic of the DAO. We want it to compute keys for the majority to rule, and we want it to allow a majority to vote on a Proposal. Note how when we make a payment, unlike in the Payment Pool, we decrease all member’s proportional ownership in the pool3, so that new owners are not disadvantaged. But we could change that, to time-weight how long members have been part of the DAO as well, or give people ‘special voting weight’ disconnected from money added. It’s really up to whatever you want…
We’ll implement the logic for each type of proposal (minting, adding, or paying).
impl Dao {
/// Sum Up all the balances
fn total(&self) -> Amount {
Amount::from_sat(self.members.iter().map(|e| e.1.relative_votes).sum::<u64>())
}
/// all signed the transaction!
#[guard]
fn majority_rules(self, _ctx: Context) {
let ppl = self
.members
.iter()
.map(|(m, d)| (m.clone(), d.relative_votes))
.collect();
// TODO: we should probably make guards return Result...
key_groups_to_clause(
&compute_key_groups(self.total().as_sat() / 2, ppl).expect("Well Formed"),
)
}
/// This Function will create a proposed transaction that is safe to sign
/// given a list of data from participants.
#[continuation(
web_api,
guarded_by = "[Self::majority_rules]",
coerce_args = "default_coerce"
)]
fn hold_vote(self, ctx: Context, update: Proposal) {
// don't allow empty updates.
match update {
Proposal::None => empty(),
Proposal::Mint {
minting_module,
mint_data,
} => {
let key = minting_module.key;
// let's now compile a new 'mint' of the NFT
let new_nft_contract = Ok(CreateArgs {
context: ContextualArguments {
amount: ctx.funds(),
network: ctx.network,
effects: Default::default(),
},
arguments: mint_impl::Versions::Mint_NFT_Trait_Version_0_1_0(mint_data),
})
.and_then(serde_json::to_value)
.map(|args| create_contract_by_key(&key, args, Amount::from_sat(0)))
.map_err(|_| CompilationError::TerminateCompilation)?
.ok_or(CompilationError::TerminateCompilation)?;
let f = ctx.funds();
ctx.template()
.add_output(f, self, None)?
.add_output(Amount::from_sat(0), &new_nft_contract, None)?
.into()
}
Proposal::Add { mut noobs } => {
let adding = Amount::from_sat(noobs.values().map(|m| m.relative_votes).sum());
let mut new = self.clone();
noobs.iter_mut().for_each(|(pk, m)| {
new.members
.entry(*pk)
.and_modify(|e| e.relative_votes += m.relative_votes)
.or_insert(m.clone());
});
let f = ctx.funds();
ctx.template()
.add_sequence()
.add_amount(adding)
.add_output(f, self, None)?
.add_output(Amount::from_sat(0), &new, None)?
.into()
}
Proposal::Payments { payments } => {
if payments.is_empty() {
return empty();
}
// collect members with updated balances here
let spent = payments
.values()
.cloned()
.map(Amount::from)
.fold(Amount::from_sat(0), |a, b| a + b.into());
let balance = 1.0 - (spent.as_btc() / self.total().as_btc());
let mut new_members = self.members.clone();
new_members.values_mut().for_each(|m| {
m.relative_votes = (m.relative_votes as f64 * balance).round() as u64;
});
// for each payment...
// Send any leftover funds to a new pool
let change = Dao {
members: new_members,
sequence: self.sequence + 1,
};
let mut tmpl = ctx.template().add_output(change.total(), &change, None)?;
// optional: we could commit to the reason somewhere in metadata
// e.g. a tapleaf branch... we don't do this here because meh.
for (key, amount) in payments {
tmpl = tmpl.add_output(amount.try_into()?, &key, None)?;
}
tmpl.into()
}
}
}
}
REGISTER![Dao, "logo.png"];
Lastly, we need some super special sneaky algorithm fun to implement signing authorities based on majority value. As noted, special uses of FROST could replace this, or future research on better weighted key protocols.
For now, we limit ourselves to 25 keys so that compilation isn’t too slow. We can afford having hundreds of thousands or millions of groups because of Taproot :).
fn key_groups_to_clause<T>(v: &(Vec<(PublicKey, T)>, Vec<u32>)) -> Clause {
Clause::Threshold(
1,
v.1.iter()
.map(|m| {
Clause::And(
v.0.iter()
.enumerate()
.filter_map(|(i, (k, _))| {
if m & (1 << i) != 0 {
Some(k.clone())
} else {
None
}
})
.map(Clause::Key)
.collect(),
)
})
.collect(),
)
}
fn compute_key_groups(
threshold: u64,
mut el: Vec<(PublicKey, u64)>,
) -> Result<(Vec<(PublicKey, u64)>, Vec<u32>), CompilationError> {
if el.len() > 25 || el.is_empty() {
return Err(CompilationError::TerminateCompilation);
}
// sort for stable ordering
el.sort();
// The bitmasks for which keys to participate
let mut sets: Vec<u32> = vec![];
// BEGIN ALGORITHM:
// if we see a bit set out of range, we can stop.
let fail_if_set = ((!0) >> el.len()) << el.len();
// we know that 0 elements is invalid, we need up to el.len()
for i in 1u32..=el.len() as u32 {
// get the first member of our permutation
let mut ct = element_0(i);
// if any bits are set in the failure zone stop
while ct & fail_if_set == 0 {
// compute the sum of the elements in this mask
let sum: u64 = (0..el.len())
.map(|i| if ct & (1 << i) != 0 { el[i].1 } else { 0 })
.sum::<u64>();
// this set is a candidate!
if sum >= threshold {
// subtract the smallest value (this is why we sorted) -- if it
// fails it is not a minimal set because there exists a passing
// set without this element.
// note: trailing zeros is guaranteed to be in bounds
if sum - el[ct.trailing_zeros() as usize].1 < threshold {
// it did fail, so save it
sets.push(ct);
}
}
// get the next ct
ct = next_perm(ct);
}
}
Ok((el, sets))
}
/// Adapted from https://www.alexbowe.com/popcount-permutations/
///
/// Compute the lexicographically next bit permutation
/// Taken from http://graphics.stanford.edu/~seander/bithacks.html
fn next_perm(v: u32) -> u32 {
let t: u32 = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
let w: u32 = (t + 1) | (((!t & (!t).wrapping_neg()) - 1) >> (v.trailing_zeros() + 1));
w
}
/// Generates first permutation with a given amount of set bits, which is
/// used to generate the rest.
fn element_0(c: u32) -> u32 {
return (1 << c) - 1;
}
All done! Not too bad huh? I think you’re really getting the hang of this thing!
Using a DAO
Now that we have this DAO we can get together a group of people and share a UTXO.
With that shared balance, we can get everyone in some kind of chat room and ‘govern’ what proposals folks want to vote on.
In particular, I would be very excited to see DAOs emerge for funding Bitcoin Developers. This type of structure can potentially help folks communally allocate capital. Often times the biggest barrier is finding deals that make sense, and DAOs would enable you to share with a group of friends and they could make decisions for you.
It would even be possible to create DAOs on behalf of third parties and fund them. For example, let’s say I get PKs for 10 devs I like and put a 10 BTC into it and set the shares up so that there is a ’leader’ with 30%, and the rest split 70% of voting shares. The leader could just steal the money with another 21%, but would they? I hope not! Instead, they can vote on good things as intended. It’d also be possible for the DAO creator to embed an ‘oversight comittee’ that can yank the funds if not being used.
Minting NFTs is kind of a cool feature since anyone can see they came from the DAO if they track the DAO’s state updates (conceivably these get published for auditing). NFTs could be issued as medals of honor for devs who follow their grants. Or, if you really like NFTs, they could be used to issue software licenses in exchange for contributing funds to the DAO operators.
Does this need CTV?
Nope. Just a fancy multisig, right?
Where CTV is useful is if we want to vote on proposals to put things into CTV contracts, like subscriptions to developer grants, opening channels, etc. Imagine the developer gets a contract where they get paid out every week, but there is a auditing comittee that can be used to terminate the subscription and return funds to the DAO if misbehavior is detected.
While you don’t need CTV in the DAO backbone, it would help open up new use cases.
It would also be possible to add some ’liveness’ smooth degradations of the DAO, whereby half the majority (e.g., if majority is 50%, 25%) could vote that the DAO is dead, and after a period of time for the majority recovery, distribute the funds on a pre-comitted schedule.
We don’t show that here, but it wouldn’t be too hard now would it?
Generalizing
One could go ahead and implement a DAO trait that all DAOs could share and build a common UX for managing DAOs with a wide variety of custom logic…
It’d also be possible to have a DAO backbone which is a single UTXO, and have other UTXOs ‘owned’ by the DAO that can get merged in later as a proposal. This way contributions to the DAO don’t always require a state update from the DAO itself.
For future work :)
FROST allows n-M threshold Schnorr signatures, which can turn into a weighted solution by making M the total value and each party have W amount of keys for their contribution. But this scales poorly because you need to exchange keys and signatures linear in the Amount, which is up to a 51-bit number. ↩︎
We are going to brute force all the N-N key combinations, so we pick a low number like 24 and things stay ‘small’ enough. ↩︎
please please if you’re implementing this for real use rational types not floats. ↩︎