zeke 0xekez

here i describe a design of a gas-efficent, ranked-choice voting system.

the problem

the most common form of ranked choice voting, instant run off, works like this:

voters submit a list of candidates sorted by their preference.
if there is an option with the majority of first-preference votes, that option is the winner.
otherwise, remove the option with the fewest first-preference votes from all preference lists and repeat.

Gas Free CosmWasm

Here we describe a simple system for interacting with CosmWasm contracts without paying gas. Instead of submitting transactions to a RPC node, addresses submit a signed ExecuteMsg to a third party and that party relays those messages to the appropriate smart contract. This third party may censor but not forge messages, and messages may be submitted as regular transactions to circumvent any censorship by the third party.

The System

Messages have the format:

Here I describe a CosmWasm key value store that allows incrementing and decrementing values at a times in the future. For example, using this map a staking contract may increment claimable balances at time $now + unbondingDuration$ during an unstake transaction. I analyze its runtime and show that the complexity of a load is $O(1)$ and the complexity of a store scales with the number of times the unbonding duration has changed.

Let $snapshots$ be a map where $snapshots[key, time]$ holds the value of a key at a given time. If a $(key, time)$ pair does not have a value, its value is the most recently stored value for that key.

$$ times(k) = \{t \mid \forall (k', t) \in snapshots,k=k'\} $$

Automatic payment for execution of Gas Free CosmWasm

In Gas Free CosmWasm there is a single web2 server that commits messages to the chain, call this piece of software an executor. This gives all the power over what messages get executed to whoever runs the executor. Here I describe a system that allows anyone to run an executor and automatically get paid for doing so.

We extend the Gas Free CosmWasm spec so that whenever a message is committed to the chain a tally for the message sender increases.
The DAO DAO validator votes to send their commission to a payment splitter contract.
This payment splitter sends a percentage of commission to another payment splitter contract that distributes payments proportional to the number of messages sent out of the total messages per block.

Vote delegation is DOSable without voting power update hooks

Say you want to implement vote delegation on top of the current DAO DAO voting module interface.

Let $E_t$ be the last time your voting module had a message executed on it. Let $state(t)$ be the complete state of the blockchain your voting module is running on at time $t$.

When queried at time $E_t + \Delta$ , for $\Delta \ne 0$, the maximum amount of state known to the contract without an additional query is $state(E_t)$. [^1]

This means that if any delegator's voting power has changed in $\Delta$, the contract will have to make an external query.

LCM and Congruence

Here I show that:

The least common multiple of two numbers divides all other multiples of those numbers, and
if $a \equiv b ;(\bmod{m})$ and $a \equiv b ;(\bmod{n} )$, for coprime integers $a$ and $b$, $a \equiv b ; (\bmod{mn})$.

The LCM divides all other multiples

The least common multiple of two numbers is the smallest number that they both divide. Let the least common multiple of two numbers $a$ and $b$ be denoted by $\operatorname{LCM}(a, b)$.

Tonic

Tonic makes transactions fee free. With tonic, there is no need to buy tokens to use DAO DAO.

To use Tonic, a user signs a message and submits that message to a third party, the executor. The executor then collects messages and, individually or in batches, submits them to Tonic. Tonic verifies each message's signature and creates an account for each user. If a message's signature is valid, Tonic forwards the message to the signer's account, and the account executes it.

This design means, Tonic's users have two addresses: one derived from their public key, and one account with Tonic. We plan to use Tonic only for accounts created with web3auth, in which case a new account is created per-app anyway. The DAO DAO UI will display a user's tonic account address, instead of their public-key derived one.

Tendermint consensus requires $\gt\frac{2}{3}$ of validators to sign a block for it to be included in the blockchain. Tendermint light clients are initialized with all the validators on their blockchain. To update a light client, a relayer submits a block. If enough known validators have signed the submitted block, the light client updates its validator set and merkle root to be the same as the submitted block's.

Because Tendermint only includes blocks if $\gt\frac{2}{3}$ of validators agree, $\frac{1}{3}$ of validators being honest will stop a malicious block from being included. Thus, Tendermint light clients can accept new blocks that $\geq \frac{1}{3}$ of validators they know have signed.

Accepting blocks that $\geq \frac{1}{3}$ of validators have signed creates the lightest possible light client, but comes with the tradeoff that the light client is unsafe if more than a third of a blockchain's validators are malicious. One can increase the [trust threshold](https://github.com/informalsystems/hermes/

A Simple Threshold Encryption Scheme

I have a secret number and want to construct a scheme where I can give away a "piece" of this number to my friends and any two of them can get together and reassemble the number. I also want to be sure that knowing only one piece of the secret, reveals nothing about its true value.

To do this, I construct a line who's y-intercept is my secret number. Say my number was $2$, the line would look like this:

The "pieces" of my secret are points along the line. I give each of my friends a point.

	#include <climits> // CHAR_BIT
	#include <iostream>
	#include <random>
	#include <vector>
	#include <chrono>

	void lsd_radix_sort(std::vector<int> &in) {
	// get the size in bits of the ints
	unsigned int width = sizeof(int)*CHAR_BIT;
	// how much we'll shift over at each step