--- Log opened Tue Feb 25 00:00:05 2020
05:20 -!- belcher [~belcher@unaffiliated/belcher] has joined #braidpool
07:27 -!- nsh [~lol@wikipedia/nsh] has quit [Remote host closed the connection]
07:46 -!- nsh [~lol@wikipedia/nsh] has joined #braidpool
11:41 < bsm117532> https://twitter.com/braidpool needs followers
11:41 < bsm117532> So I was playing with conflict resolution rules last night. I've mused a few times about the relationship between combining PoW in a DAG and Kirchhoff rules for electric circuits (adding resistors and capacitors in series and parallel)
11:42 < bsm117532> I decided last night that this is the wrong approach, because (among other reasons) an electric circuit is not "directed".
11:43 < bsm117532> https://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws
11:44 < bsm117532> A DAG is a simplification of what you can do with electric circuits. e.g. current can flow *both* directions through a wire. But the directionality of a cryptographic DAG is forced to be directed by hash relationships. Some electric circuits would imply a hash cycle, and are not possible.
11:45 < bsm117532> So then I considered some simple rules to sum work of parents, all of which reduce to the "heaviest chain" rule in the blockchain limit:
11:46 < bsm117532> I looked at the Pythagorean means: https://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws
11:46 < bsm117532> As well as their generalization in "power means": https://en.wikipedia.org/wiki/Generalized_mean
11:47 < bsm117532> of which the RMS (root mean square) is one.
11:48 < bsm117532> The work-sum rule is W = M_p(w_1, ..., w_n) where p is the power mean exponent (p=2: RMS, p=1: arithmetic mean, p=-1: harmonic mean), and w_i are the work of each parent.
11:49 < bsm117532> IOW the work of any given bead is the appropriate *average* of its parents.
11:49 < bsm117532> The means I tested explicitly (harmonic, RMS, arithmetic) all have the interesting property that resulting work is *independent* of graph structure.
11:50 < bsm117532> I suspect this is true for the entire class of power means p.
11:50 < bsm117532> At first I thought that was bad: we should incentivize adding parents and tying different tips up into a single chain.
11:50 < bsm117532> But then I realized that *any* mechanism that rewards adding parents can be abused by an attacker.
11:51 < kanzure> soft followed
11:51 < bsm117532> An attacker can always create a more-connected sub-diagram. He observes the main chain, withholds his own blocks, but names the main chain as parents as well as his own withheld blocks.
11:51 < bsm117532> If this procedure results in "more work" by the work-adding algorithm, this gives the attacker an advantage.
11:52 < bsm117532> IOW the attacker can create a block withholding attack, and with the same work or less than the main chain, his sub-diagram would be considered "more work".
11:52 < bsm117532> Therefore, we MUST NOT incentivize in any way adding more parents, since it can be abused.
11:53 < bsm117532> Therefore I land on the algorithm for summing work in a DAG (same as above): W = M_p(w_1, ..., w_n) for one of the generalized power means p.
11:53 < kanzure> https://twitter.com/kanzure/status/1232392795006042112
11:54 < bsm117532> Thanks!
11:55 < bsm117532> So all of the above is interesting because one thing I've been worrying about is: does the work-summing algorithm need to know about "cohorts"?
11:56 < bsm117532> And the answer is: No, as long as the work-summing algorithm is a "generalized mean" as described above.
11:56 < bsm117532> Summing work by identifying cohorts, and just summing work by adding parent work results in the same answer.
12:00 < bsm117532> So I land on the following rules for conflict resolution (tx selection/double-spend): txs in beads with more work are selected first. If a tie, use "luck" (smaller hash value).
12:01 < bsm117532> Left to do: show 51% attack rules still hold with this selection. Select p (harmonic? average? RMS?)
14:16 -!- belcher [~belcher@unaffiliated/belcher] has quit [Quit: Leaving]
14:16 < bsm117532> Another question remains: does p != -1 offer any advantage? p=-1 is the Harmonic mean, which picks the max work among parents, and is resistant to adding small amounts of extra work in parents.
14:16 < bsm117532> Is there any reason to use the RMS mean for instance?
14:19 < bsm117532> (Harmonic mean and algebraic mean are reciprocal duals -- algebraic mean of work is harmonic mean of targets)
14:19 < bsm117532> Which makes it seem like the algebraic mean of work is the natural choice.
--- Log closed Wed Feb 26 00:00:06 2020