dao.md
1 # DAO Short Explainer 2 3 ## Prerequisites 4 5 There is a scheme called commit-and-reveal, where given an object $x$ 6 (or set of objects), you generate a random blind $b$, and construct the 7 commitment $C = \textrm{hash}(x, b)$. By publishing $C$, you are 8 committed to the value $x$. 9 10 Secondly, we may wish to publish long lived objects on the blockchain, 11 which are essentially commitments to several parameters that represent 12 an object defining its behaviour. In lieu of a better term, we call 13 these bullas. 14 15 ## `DAO::mint()`: Establishing the DAO 16 17 From `darkfi/src/contract/dao/proof/mint.zk`: 18 ```zkas 19 bulla = poseidon_hash( 20 proposer_limit, 21 quorum, 22 early_exec_quorum, 23 approval_ratio_quot, 24 approval_ratio_base, 25 gov_token_id, 26 notes_public_x, 27 notes_public_y, 28 proposer_public_x, 29 proposer_public_y, 30 proposals_public_x, 31 proposals_public_y, 32 votes_public_x, 33 votes_public_y, 34 exec_public_x, 35 exec_public_y, 36 early_exec_public_x, 37 early_exec_public_y, 38 bulla_blind, 39 ); 40 ``` 41 42 Brief description of the DAO bulla params: 43 44 * **proposer_limit**: the minimum amount of governance tokens needed to 45 open a proposal. 46 * **quorum**: minimal threshold of participating total tokens needed for 47 a proposal to pass. Normally this is implemented as min % of voting 48 power, but we do this in absolute value 49 * **early_exec_quorum**: minimal threshold of participating total 50 tokens needed for a proposal to be considered as strongly supported, 51 enabling early execution. Must be greater or equal to normal quorum. 52 * **approval_ratio**: the ratio of winning/total votes needed for a 53 proposal to pass. 54 * **gov_token_id**: DAO's governance token ID. 55 * **notes_public_key**: notes(coins) decryption public key 56 * **proposer_public_key**: proposals creator public key 57 * **proposals_public_key**: proposals viewer public key 58 * **votes_public_key**: votes viewer public key 59 * **exec_public_key**: proposals executor public key 60 * **early_exec_public_key**: strongly supported proposals executor 61 public key 62 * **bulla_blind**: bulla blind 63 64 DAO creators/founders have full control on how they want to configure 65 and share the actions keys, giving them the ability to veto if needed. 66 67 ## `DAO::propose()`: Propose the Vote 68 69 From `darkfi/src/contract/dao/proof/propose-main.zk`: 70 ```zkas 71 proposal_bulla = poseidon_hash( 72 proposal_auth_calls_commit, 73 proposal_creation_blockwindow, 74 proposal_duration_blockwindows, 75 proposal_user_data, 76 dao_bulla, 77 proposal_blind, 78 ); 79 ``` 80 81 Proposals are committed to a specific calls set, therefore they generic 82 and we can attach various calls to it. We will use a money transfer as 83 the example for rest sections. 84 85 ## `DAO::vote()`: Vote on a Proposal 86 87 Governance token holders each make an encrypted homomorphic commitment 88 to their vote. The homomorphism is additive so $f(u) + f(v) = f(u + v)$. 89 They also encrypt their vote to the DAO pubkey. 90 91 Finally once voting is completed, the holders of the DAO pubkey (which 92 is up to DAO policy) can decrypt the votes $f(v₁), …, f(vₙ)$, sum the 93 values $v₁ + ⋯ + vₙ$ and so have the value which can be used in ZK 94 proofs alongside publicly available commitment 95 $f(v₁ + ⋯ + vₙ) = f(v₁) + ⋯ + f(vₙ)$. 96 97 ## `DAO::exec()`: Execute Passed Proposal 98 99 This is the key part. We produce a tx which has two contract calls: 100 `[money::transfer(), DAO::exec()]`. The coins spent in 101 `money::transfer()` belong to the DAO and have the condition that they 102 can only be spent when combined with `DAO::exec()`. Here is what coins 103 in `money::transfer()` look like: 104 105 ```zkas 106 C = poseidon_hash( 107 pub_x, 108 pub_y, 109 value, 110 token, 111 serial, 112 spend_hook, 113 user_data, 114 ); 115 ``` 116 117 When we send coins to the DAO treasury, we set `spend_hook` to the DAO 118 contract, and `user_data` to the DAO bulla. 119 120 When spending the coins, they reveal the `spend_hook` publicly and 121 `user_data` (encrypted). `money::transfer()` enforces that the next 122 contract call must be the same as the `spend_hook`. 123 124 The contract invoked by `spend_hook` can then use the `user_data`. We 125 use this to store the DAO bulla. `DAO::exec()` will then use this as 126 our DAO, and check the proposal we are executing belongs to this DAO 127 through the reference to the DAO bulla in the proposal params. 128 129 `DAO::exec()` then encodes the rules that specify there has to be a 130 valid proposal where voting passed the threshold and so on. 131 132 Assuming both contracts validate successfully, the funds are 133 transferred out of the DAO treasury. 134 135 # Formalism 136 137 Let the $ℂ$ be the category for all sets of coins $C$ with one-way 138 arrows 139 $C → C'$ such that $C ⊆ C'$ and an initial object $C₀ = ∅ $. 140 We require that arrows with the same source and target commute. 141 $$ \begin{CD} 142 C @>c_b>> C_b \\ 143 @VcₐVV @Vc_a'VV \\ 144 Cₐ @>c_b'>> C_{ab} 145 \end{CD} $$ 146 147 We define the nullifier functor $N : ℂ^{\t{op}} → ℕ$ which is an 148 isomorphism of $ℂ$ that reverses arrows. 149 150 $$ \begin{CD} 151 C @>>> NC \\ 152 @VcVV @AANcA \\ 153 C' @>>> NC' 154 \end{CD} $$ 155 We can see the action of adding $c$ to $C$ (expressed as the left 156 downwards arrow) gets lifted to the arrow going backwards in the 157 nullifier category. The collection of arrows in $ℂ$ and $ℕ$ then 158 describes the coins and nullifier sets which are represented in Merkle 159 trees. 160 161 From the diagram we see that $C → C' → NC' → NC → C$ so that $Nc$ 162 cancels $c$. Pasting diagrams together, we get 163 164 $$ \begin{CD} 165 C₀ @>>> NC₀ \\ 166 @Vc₁VV @AANc₁A \\ 167 C₁ @>>> NC₁ \\ 168 @Vc₂VV @AANc₂A \\ 169 C₂ @>>> NC₂ \\ 170 \end{CD} $$ 171 172 where all squares commute. Since all paths in $ℂ$ are one way, proving 173 a coin $cₖ : Cₖ₋₁ → Cₖ$ exists is equivalent to being at any state 174 $Cₖ, Cₖ₊₁, Cₖ₊₂, …$. 175 176 **Lemma:** If our state is $Cₖ$ then our set must contain the coins 177 represented as arrows $c₁, …, cₖ$. 178 179 # Anon Voting Mechanics 180 181 When making a proposal, we need to prove ownership of a threshold of 182 coins. Likewise for voting. Essentially they are similar problems of 183 proving ownership of a coin $c$ that is still valid. As shown above 184 this reduces to the following statements: 185 186 * Is $c$ in the set of all coins $C$? 187 * If yes, then is $n(c)$ *not* in the set of nullifiers $N$? 188 189 Normally this logic is handled by transfers, but we need to 190 additionally check it without leaking info about $c$. Since $n(c)$ is 191 derived deterministically, leaking $n(c)$ also leaks info on $c$. 192 193 Nullifiers must be checked otherwise expired coins can be used. 194 195 ## Forking the Global State 196 197 The first method involves copying the coins state $C$. Every proof 198 makes use of $C$ while revealing $n(c)$ which is checked against the 199 current nullifier state. To avoid anonymity leaks from revealing 200 $n(c)$, we additionally move the coin using a `Money::transfer()` call. 201 202 The downside is that wallets need to: 203 204 * Keep track of the coins tree $C$. This will involve logic to 205 periodically checkpoint the incremental tree in a deterministic way. 206 * When doing any action, the wallet must move coins simultaneously. 207 Wallets must also keep track of the unspent coin since for example it 208 might be used in another vote (or the wallet makes a proposal and 209 wants to vote with the same coin). 210 211 Additionally you cannot obtain a coin then vote. You must own the coin 212 before the vote is proposed. 213 214 ## Forking the Global State (with SMT) 215 216 Instead of revealing the nullifier, we instead snapshot the nullifier 217 tree alongside $C$. 218 219 The downsides are: 220 221 * More expensive for voters since SMT is expensive in ZK. 222 * We're taking an older snapshot of the coins state. Spent coins spent 223 after the vote are proposed will still be able to vote. 224 225 ## Tracking Coins with Local State 226 227 Each coin's `user_data` contains an SMT of all proposals they voted in. 228 When transferring a coin, you must preserve this `user_data`. 229 The `spend_hook` only allows modifying it with a parent call that adds 230 proposals when voting to the SMT field in the coin. 231 232 The downside for wallets is that: 233 234 * The SMT committed to is large and needs to be transferred to 235 receivers when sending the coin. 236 * Alternatively coins could contain a special key (also in the 237 `user_data` field), which when voting you must make a verifiable 238 encryption. That way wallets can later scan all proposals for a 239 DAO to find where their particular governance token voted. 240 * It's very complex. For example, can DAOs own governance tokens? So 241 far DAO tokens must have the `spend_hook` set, but with this, we now 242 require another `spend_hook` which preserves the SMT when 243 transferring coins. The mechanics for two parents of a call aren't 244 specified, so we'd maybe have to add some concept of symlinks. 245 246 However while complex, it is the most accurate of all 3 methods 247 reflecting the current state. 248 249 # Tree States On Disk 250 251 This section is not specific to DAO or Money, but describes a generic 252 set abstraction which you can add or remove items from. 253 254 Requirements: 255 256 * Add and remove items, which is represented by two G-sets denoted 257 coins $Cₖ$ and nullifiers $Nₖ$. Let $Rₖ$ and $Sₖ$ be commitments to 258 them both respectively. 259 * Given any snapshot $(Rₖ, Sₖ)$, it's possible to definitively say 260 whether the set it represents contains an item $x$ or not. 261 * Be able to do this fully ZK. 262 * Wallets can easily take any snapshot, and using delta manipulation of 263 the state, be able to make inclusion and exclusion proofs easily. 264 * Verify in WASM that $Rₖ$ and $Sₖ$ correspond to the same $k$. 265 266 The proposal is as follows and involves a merkle tree $𝐂$, and a SMT $𝐍$. 267 268 For the sake of clarity, we will not detail the storing of the trees 269 themselves. For $𝐂$, the tree is stored in `db_info`, while $𝐍$ has a 270 full on-disk representation. Instead the info in this section concerns 271 the auxiliary data required for using the trees with snapshotted states. 272 273 ## DB Merkle Roots 274 275 This is used to quickly lookup a state commitment for $𝐂$ and figure 276 out when it occurred. 277 278 | Key or Value | Field Name | Size | Desc | 279 |--------------|--------------|------|----------------------------| 280 | k | Root | 32 | The current root hash $Rₖ$ | 281 | v | Tx hash | 32 | Current block height | 282 | v | Call index | 1 | Index of contract call | 283 284 We call `get_tx_location(tx_hash) -> (block_height, tx_index)`, and 285 then use the `(block_height, tx_index)` tuple to figure out all info 286 about this state change (such as when it occurred). 287 288 ## DB SMT Roots 289 290 Just like for the merkle case, we want to quickly see whether $Rₖ$ and 291 $Sₖ$ correspond to each other. 292 We just compare the tx hash and call index. 293 If they match, then they both exist in the same `update()` call. 294 295 | Key or Value | Field Name | Size | Desc | 296 |--------------|--------------|------|----------------------------| 297 | k | Root | 32 | The current root hash $Sₖ$ | 298 | v | Tx hash | 32 | Current block height | 299 | v | Call index | 1 | Index of contract call | 300 301 ## DB Coins (Wallets) 302 303 This DB is maintained by the user wallet, and periodic garbage 304 collection will remove values older than a cutoff. 305 306 Keeps track of values added to $𝐂$ or $𝐍$. 307 308 For $𝐂$ given an earlier tree checkpoint state, we can rewind, then 309 fast forward to have a valid Merkle tree for the given snapshot. 310 Wallets should additionally periodically copy the merkle tree $𝐂$. 311 312 In the case of $𝐍$, we construct an overlay for SMT, which allows 313 rewinding the tree so exclusion proofs can be constructed. 314 315 | Key or Value | Field Name | Size | Desc | 316 |--------------|--------------|------|---------------------------------------| 317 | k | Block height | 4 | Block height for coin | 318 | k | Tx index | 2 | Index in block for tx containing coin | 319 | k | Call index | 1 | Index of contract call | 320 | k | Val index | 2 | Index of this coin or nullifier | 321 | v | Value | 32 | Coin or nullifier | 322 | v | Type | 1 | Single byte indicating the type | 323 324 This structure for the keys in an ordered B-Tree, means it can be 325 iterated from any point. We can start from any location from our last 326 stored Merkle tree checkpoint, and iterate forwards adding coins until 327 we reach our desired snapshot $(Rₖ, Sₖ)$. We then have a valid Merkle 328 tree and SMT reconstructed and can create the desired inclusion or 329 exclusion proofs. 330 331 Q: should this be 2 databases or one? If we use 2 then we can remove 332 the type byte. Maybe more conceptually clearer? 333 334 ## OpenZeppelin Governance 335 336 https://docs.openzeppelin.com/contracts/4.x/governance 337 338 It uses modules when the code is deployed to customize functionality. 339 This includes: 340 341 * Timelock, users can exit if they disagree before decision is executed. 342 * Votes module which changes how voting power is determined 343 * Quorum module for how the quorum is defined. The options are 344 GovernorVotes and ERC721Votes. 345 * What options people have when casting a vote, and how those votes 346 are counted. 347 * GovernorCountingSimple offers For, Against and Abstain. Only For 348 and Abstain are counted towards quorum. 349 * AccessControl 350 * Clock management, whether to use block index or timestamps. 351 352 The Governor (which in DarkFi is the DAO params) has these params: 353 354 * Voting delay. How long after a proposal is created should voting 355 power be fixed. A large voting delay gives users time to unstake 356 tokens if needed. 357 * In DarkFi users will just pre-announce proposals. 358 * Voting period, typically 1 week 359 360 These params are specified in the unit defined in the token's clock. 361 This is the blockwindow in DarkFi. So the 'unit' should be a public DAO 362 param too. 363 364 AccessControl has several roles: 365 366 * Proposer, usually delegated to the Governor instance 367 * Executor. Can be assigned to the special zero address so anyone can 368 execute. 369 * Admin role which can be renounced. 370 371 OpenZeppelin is moving to timestamps instead of block index because: 372 373 > It is sometimes difficult to deal with durations expressed in number 374 > of blocks because of inconsistent or unpredictable time between 375 > blocks. This is particularly true of some L2 networks where blocks 376 > are produced based on blockchain usage. Using number of blocks can 377 > also lead to the governance rules being affected by network upgrades 378 > that modify the expected time between blocks. 379 380 ## Aragon 381 382 https://aragon.org/how-to/governance-ii-setting-dao-governance-thresholds 383 384 * Minimum participation, sometimes called quorum. 385 With large whales, you want a higher threshold. 386 Usual value is 5%. 387 * Support threshold, sometimes called pass rate. In DarkFi this is 388 called the approval ratio. The most typical value is 50%. 389 * Voting period. Most common is 7 days. 390 * Speed. You want a short period if DAO needs to make fast decisions. 391 * Participation. Longer period for higher participation. 392 * Safety. Too low can be a risk. 393 394 Params can also be set then changed later to adjust. 395 396 Delegation is a good feature to increase participation. 397 398 Early execution means that if the proposal meets the requirements then 399 it can be executed early. We should add this option to DarkFi DAO params. 400 401 ## Suggested Changes 402 403 ~~DAO params:~~ 404 405 * ~~Voting period (currently called duration) should be moved from 406 proposals to DAO params.~~ 407 * ~~upgrayedd: we should just have minimum allowed period in the 408 DAO, but keep this param in the proposal.~~ 409 * ~~Window (currently set at 4 hours of blocks) should be customizable. 410 We need a terminology for the unit of time. Maybe `time_units`.~~ 411 * ~~This should be switched from block index to using timestamps. 412 See the quoted paragraph in the OpenZeppelin section above for the 413 reasoning.~~ 414 * ~~upgrayedd: stick with block index.~~ 415 * ~~Early execution bool flag. If true, then passed proposals can be 416 `exec()`uted asap, otherwise the entire voting period must pass.~~ 417 418 ~~No changes to proposals, except moving duration to DAO params.~~ 419 420 > Resolution: 421 > The full voting period must pass in order to be able to execute a 422 > proposal. A new configuration parameter was introduced, called early 423 > exec quorum, where we can define the quorum for a proposal to be 424 > considered as strongly supported/voted on, which should always be 425 > greater or equal to normal quorum. With this addition, we can execute 426 > proposals before the voting period has passed, if they were accepted. 427 428 ~~Currently the DAO public key is used for:~~ 429 430 * ~~Encrypting votes.~~ 431 * ~~Calling exec.~~ 432 433 ~~We should introduce a new key:~~ 434 435 * ~~Proposer role, which is needed to make proposals. This can be 436 shared openly amongst DAO members if they wish to remove the 437 restriction on who can make proposals.~~ 438 * ~~OZ does this with a canceller role that has the ability to 439 cancel proposals.~~ 440 * ~~In the future allow multiple keys for this so you can see who 441 makes proposals.~~ 442 443 > Resolution: 444 > DAO public key was split into six other keys, providing maximum 445 > control over each DAO action. Now the DAO creator can define who can 446 > view the coin notes, create proposals, view proposals, view votes, 447 > execute proposals and early execute proposals. They can configure the 448 > keys however they like like reusing keys if they want some actions to 449 > have same key. 450 451 Optional: many DAOs these days implement Abstain, which increases the 452 quorum without voting yes. This is for when you want to weak support 453 a measure, allowing it to reach quorum faster. This could be 454 implemented in DarkFi, by allowing the vote yes to optionally be 0.