Felföldi Zsolt zsfelfoldi

A pay-for-storage model for evolving tree hashed data structures

Author: Zsolt Felfoldi ([email protected])

This proposal describes a relatively lightweight and easy to maintain structure that is directly applicable for the implementation of a "storage fee" scheme on the EVM state and is also flexible enough to accomodate future storage schemes. It allows renting each account and contract storage entry separately, solving the problem of funding contracts with many user entries like ERC-20 tokens. Its economic model lets users know the exact expiration time of their entries when paying for rent. It does not need removal transactions, allows lazy garbage collection but still avoids "tree rot" (scenarios where it's not instantly clear whether a transaction is executable or not). The economic model can also be considered separately from the proposed data structure. It might require some more formal study but I believe it has good stability/fairness properties.

Data structure

We differentiate betw

@fjl @holiman and anyone who might be interested (whenever you have free time, not urgent) : this is a WIP PR (absolutely untested and partly unfinished) where I implemented a fairly simple (400 LOC total + utils.WeightedRandomSelect, does not use the NodeStateMachine :) ) DDoS protector. The reason I spent time with it at this early stage is that I think the token market interface really needs to be designed with this aspect in mind. Polling rates and unhealthy competition (arms race) can be a problem with markets, especially in a decentralized and uncontrolled, somewhat chaotic environment. The reason I am showing it to you is because I think something like this could be a recommendation (maybe even an EIP) for our entire DHT and I am interested in your opinons from both a security and DHT centric perspective. So basically what it does is

keeps request queues by both IP address (string) and enode.ID
has a single processing loop that even does time.Sleeps between serving them so that the DHT logic

Proposed NodeStateMachine specs

Persistence rules

a subset of the node state flags and fields can be persisted in a database
- a flag is persistent if NodeStateFlag.persistent is set
- a field is persistent if encode and decode are not nil
- persistent flags and fields are created with a separate constructor
stored states are loaded during startup
in-memory states that have been changed since loading the stored version or newly created ones with no stored version are considered "dirty" until they are saved (again)

General utilities

Weighted random selector

WeightedRandomSelect is a passive, not thread-safe data structure that holds a set of items with assigned selection weights and can quickly select one of them randomly. Weights are specified by a callback function but the last known weights are also stored in the data structure. If the weight increases compared to the last returned value then it should be explicitly updated. If it decreases then update happens automatically.

Node state machine

NodeStateMachine connects different system components operating on subsets of network nodes. It can be considered an enhanced version of les.clientPeerSet / les.serverPeerSet which it could probably replace over time. Node states are represented by uint64 bit vectors with each bit assigned to a state flag. Each state flag has a string name and the mapping is created automatically. It is possible to subscribe to subsets of state flags and receive a callback if one of the nodes has a relevant state flag c

A quick explanation of the `expiredValue` structure

Goal

The lesPay token sale model uses service tokens that continuously "expire" under certain conditions, meaning their value is reduced exponentially over time. Expiration happens when some amount of free connection is possible and therefore all existing tokens are spendable. Expiration can be interpreted as a kind of "spendability" fee that incentivizes clients to indeed spend their tokens in a limited time frame. This can be realized in two ways:

with "inflationary" units; if all prices rise exponentially then value of existing tokens is reduced inversely
with "stable tokens"; if the nominal value of each token is stable then the token balances should be reduced continuously

The second interpretation fits with the model better because service tokens (which are basically a promise from the server) are meant to have a more or less predictable purchasing power. With stable token nominations the client can expect the prices to not change qui

createDeposit(amount map[common.Address]uint64) depositID
- sends a transaction to create a new deposit with the given target allowances
subscribeDepositEvents(ch chan struct {id depositID, state int})
- sends an event to the given channel every time a deposit goes into pending, active or expired state
estimatedExpiry(id depositID) time.Duration
- returns the estimated remaining time while cheques can still be written using this deposit
allowancesLeft(id depositID) map[common.Address]uint64
lastCheque(id depositID, to common.Address) (totalSpent, allowanceLeft uint64)
writeCheque(id depositID, to common.Address, amount uint64) (totalSpent, allowanceLeft uint64, proofOfPayment []byte)
- creates a cheque if the deposit is in active state and there is enough allowance left (otherwise proofOfPayment should be nil)

	fefe@i7-6700 ~/go/src/github.com/ethereum/go-ethereum $ ./geth --datadir "/media/1TB/.ethereum" --cache 4096 --port 30304 --lightserv 50 console
	INFO [02-09\|11:37:19.499] Starting Geth on Ethereum mainnet...
	INFO [02-09\|11:37:19.500] Maximum peer count ETH=50 LES=100 total=150
	INFO [02-09\|11:37:19.500] Smartcard socket not found, disabling err="stat /run/pcscd/pcscd.comm: no such file or directory"
	WARN [02-09\|11:37:19.507] The flag --lightserv is deprecated and will be removed in the future, please use --light.serve
	INFO [02-09\|11:37:19.507] Set global gas cap cap=25000000
	INFO [02-09\|11:37:19.507] Allocated trie memory caches clean=614.00MiB dirty=1024.00MiB
	INFO [02-09\|11:37:19.507] Allocated cache and file handles database=/media/1TB/.ethereum/geth/chaindata cache=2.00GiB handles=32768
	INFO [02-09\|11:37:21.913] Opened ancient database database=/media/1TB/.ethereum/geth/chaindata/ancient
	INFO [02-09\|11:37:21.922] Initiali

	// NewMerkleTree constructs a merkle tree with given entries.
	func NewMerkleTree(entries []Entry) MerkleTree {
	if len(entries) == 0 {
	return nil
	}
	// Assign an unique salt for each entry. The hash
	// of entry is calculated by keccak256(value, salt)
	// so we can preserve the privacy of given value.
	for _, entry := range entries {
	entry.salt = rand.Uint64()

	INFO [06-03\|01:17:56.023] Imported new block headers count=1 elapsed=3.429ms number=10189345 hash="3560fb…8bbae5"
	INFO [06-03\|01:17:57.551] Looking for peers peercount=2 tried=8 static=0
	INFO [06-03\|01:18:06.389] Imported new block headers count=1 elapsed=10.590ms number=10189346 hash="0fc3d7…39d77d"
	INFO [06-03\|01:18:07.553] Looking for peers peercount=2 tried=11 static=0
	INFO [06-03\|01:18:17.556] Looking for peers peercount=2 tried=12 static=0
	INFO [06-03\|01:18:18.846] Imported new block headers count=1 elapsed=8.864ms number=10189347 hash="004ea0…1aa5e7"
	INFO [06-03\|01:18:27.559] Looking for peers peercount=2 tried=8 static=0
	INFO [06-03\|01:18:45.564] Imported new block headers count=1 elapsed=9.115ms number=10189348 hash="30b581…41ad96"
	INFO [06-03\|01:19:00.867] Imported new block headers count=1 elapsed=9.135ms number=101893

	package main

	import (
	"fmt"
	"math"
	"sort"
	)

	const (
	maxLevel = 10