BitShares Forum

Main => General Discussion => Topic started by: theoretical on September 10, 2014, 06:49:57 am

Title: drltc's analysis of various yield implementation issues
Post by: theoretical on September 10, 2014, 06:49:57 am

I have posted at https://github.com/drltc/bitbond-proposal/blob/master/interest-0.4.13.md an analysis of 0.4.13 yield changes, along with a few proposed modifications to the (approximate) 0.4.13 yield algorithm which should make it much less approximate without making the devs work too hard :)

My most important algorithmic insight, however, is that an implementation of "exact" yield need not be as resource-intensive as bytemaster currently believes.  So I'll copy-paste my explanation in its entirety as the opening post of this thread, in hopes that will make it less likely to be missed (as I can scarcely blame others for failing to read threads beyond the first three pages when I seldom do so myself):

Is this because it would take too much time to compute the factor to multiply the BitUSD value by for each transaction? Meaning if each block determines a factor f_i (representing e^y where y is the per block variable yield rate) for each BitAsset, then for each transaction with BitAsset inputs you would need to get all the BitAsset's f_i from block i = m where the transaction was created to block i = n which is the current block where the transaction was spent, and then multiply the BitAsset value by f_m * f_(m+1) * ... * f_n to get its new value with yield.

Yes.  It would greatly increase database size and transaction processing time.  I know how to "do it proper" from the original dividends design for BTSX.  It requires an accumulation table that must be updated every block for 1 years worth of blocks. 


I'm guessing bytemaster wants to save the product between b[m] and b[n] for all pairs of blocks m, n.  I posted how to avoid this earlier in this thread (four word answer: partial sum skip list), but I'll go into more detail since both of you apparently missed (or misunderstood) that post.

I propose using sums of logarithms instead of multiplying (so we can do many-block sequences without worrying too much about various approximation issues).  Then only save partial sums that are aligned power-of-two length.  So you save (in your notation):

Code: [Select]
run(m,  1) = f_m                                     # for all blocks
run(m,  2) = f_m + f_{m+1}                           # for every 2nd block
run(m,  4) = f_m + f_{m+1} + f_{m+2} + f_{m+3}       # for every 4th block
run(m,  8) = f_m + f_{m+1} + f_{m+2} + f_{m+3} + f_{m+4} + f_{m+5} + f_{m+6} + f_{m+7}
                                                     # for every 8th block, etc... for every power of 2

If total number of blocks is N, this data structure needs at most 2N-1 entries (hint: total size is a geometric series).

So if you want to find e.g. the sum of logs from 0x7159 (inclusive) to 0x1258a (exclusive), you can compute that as:

Code: [Select]
run(0x7159, 1) + run(0x715a, 2) + run(0x715c, 4) + run(0x7160, 0x20) + run(0x7180, 0x80) + run(0x7200, 0x200) + run(0x7400, 0x400) + run(0x7800, 0x800) + run(0x8000, 0x8000) + run(0x10000, 0x2000) + run(0x12000, 0x400) + run(0x12400, 0x100) + run(0x12500, 0x80) + run(0x12580, 8) + run(0x12588, 2)

The proper bit twiddling operations to implement this are left as an exercise to the reader.

Updating a block will usually be fast, requiring only the last few blocks.  Block heights divisible by large powers of 2 will happen and reach higher in the blockchain (on an exponentially rare basis), but in all cases at most log(N) values need be saved, each of which requires at most log(N) time.  (I think the actual bound is just log(N) instead of log(N)^2 because you re-use the tail part and only need to reach back one more entry, but log^2(N) is still fast enough.)

Title: Re: drltc's analysis of various yield implementation issues
Post by: theoretical on September 10, 2014, 06:59:31 am
Here's the TLDR version of my analysis:

AFAIK the current implementation assumes conservatively everyone will wait a year and then withdraw their balances because that makes the numbers easier.  This means the fund will tie up BitUSD unnecessarily because most balances will be nowhere near their 1-year anniversary most of the time (especially now, when BitUSD has just launched NOBODY will be able to have a BitUSD balance older than the launch date!)

If you think about it carefully, the 0.4.13 yield scheme can be interpreted like this:  Divide the yield fund into a number of "yield shares" equal to the network's total CYD (coin years destroyed).  Then each CYD in your balance is worth somewhere between 0.8 and 1.0 yield shares (it increases linearly from 0.8 to 1 over the course of a year).  So if we just look at total CYD and assume all those CYD are worth the worst-case number of shares, we only tie up at most 20% of the fund from over-estimation.

That's what I think it ought to do, but AFAIK what it does is sets the total number of yield shares based on a worst-case scenario of all coins being 1 year old.  Which ties up over 91% of the fund in overestimation if everyone's BitUSD balances are, on average, less than a month old, which seems like a pretty safe description of the current state of the blockchain :)

If you're willing to do bookkeeping on how many CYD there are of various ages to within, say, one day's precision, you can reduce the over-estimation amount to only a day's worth of interest in the worst case.

But the algorithm I outlined in my first post is better than any of these, basically being completely accurate; it will pretty much pay out transactions equally to everyone as they come in.
Title: Re: drltc's analysis of various yield implementation issues
Post by: tonyk on September 10, 2014, 07:39:05 am
But the algorithm I outlined in my first post is better than any of these, basically being completely accurate; it will pretty much pay out transactions equally to everyone as they come in.

One of my biggest struggles is that my post quite often convey totally different message(s) than the one intended by me. And I  am definitely trying to avoid this, with this particular post.

I do think you can make GREAT contributions to the future bond/interest market drltc.

Just leave the few off BTSX +/- in the current yield proposal as they are. My personal believe is that they will not make anybody rich or poor in the next 2-3 years.

And we will most likely  have pretty complicated bond/interest market in the not so distant future.
Title: Re: drltc's analysis of various yield implementation issues
Post by: theoretical on September 13, 2014, 06:49:10 am
Just leave the few off BTSX +/- in the current yield proposal as they are. My personal believe is that they will not make anybody rich or poor in the next 2-3 years.

My point was that we could be yielding perhaps 10x more now, and 2x more over the long term, without risking insolvency.

I agree that some yield is better than no yield, so getting the current yield implementation out the door as fast as possible was probably a good move in the long term.

But I think we can do much better.  While the yield payments themselves may not lead to riches for BitUSD holders, the demand for a USD-denominated interest-bearing decentralized cryptocurrency deposit account may greatly increase if the yield increases 10x.  Since those BitUSD must ultimately be backed by BTSX, this should lead to capital gains for BTSX holders and BitUSD shorters.  And the difference in demand for BitUSD between the current yield and 10x the current yield may indeed significantly change those returns from capital gains on BTSX!