--- Log opened Thu Feb 13 00:00:39 2020
07:03 < bsm117532> Would anyone here like to get paid to work on braidpool?
20:34 -!- hodlwave [~znc-admin@68.183.145.179] has joined #braidpool
20:46 < hodlwave> me :D
21:08 < bsm117532> HE MADE IT!!!!
21:08 < hodlwave> lol
21:10 < bsm117532> I've been waiting all day to answer your question from twitter
21:10 < bsm117532> hodlwave question: Sorry how does the longest chain generalize to a DAG? I would've thought your "parallel bead" example would be rejected on that basis.
21:10 -!- zfnmxt [~zfnmxt@unaffiliated/zfnmxt] has joined #braidpool
21:10 < bsm117532> o/ zfnmxt, who is you?
21:11 < bsm117532> hodlwave: Basically the task is to create a total order on beads (blocks) and transactions.
21:11 < bsm117532> "longest chain" is one form of total order.
21:11 < bsm117532> And obviously not applicable to a DAG.
21:12 < bsm117532> In a DAG, you can actually *allow* conflicting transactions. Instead of a fork, some future block names two parent blocks, containing conflicting transactions.
21:12 < bsm117532> For simplicity, consider a diamond graph.
21:12 < bsm117532> With the conflicting transactions on either side of the diamond.
21:13 < bsm117532> The "winning" transaction is the one in the block (bead) with the smaller hash (assuming both beads have the same target difficulty)
21:14 < zfnmxt> bsm117532: Just testing a script that joins random channels on Freenode. I'll leave now :D
21:14 -!- zfnmxt [~zfnmxt@unaffiliated/zfnmxt] has left #braidpool ["WeeChat 2.7"]
21:15 < bsm117532> This can be reversed by a 51% attack (same as bitcoin). Assuming the non-confirmed transaction is in the top of the diamond graph: an attacker must name that bead as his parent, mine a bead, publish it, have someone mine a subsequent block naming his block and whatever is the latest chain tip as parents.
21:16 < bsm117532> If the attacker has sufficient hashpower (51%) this will cause the previously conflicting transaction to change and be "confirmed" as far as the work-weighting goes.
21:16 < bsm117532> Now we started with a diamond graph. In a diamond, the two sides of the diamond are a cohort. (they have the same ancestors and children)
21:17 < hodlwave> ok wait lemme see if i understand you
21:17 < bsm117532> Once an attacker adds a new bead as described above, this causes the cohort to be much larger, subsuming the previous cohort up to the point the attacker's bead is merged with some other bead naming it as a parent (and being a cohort itself).
21:18 < hodlwave> so diamond graph. top and bottom beads can either have the same Txs or conflicting ones
21:18 < bsm117532> yes
21:18 < bsm117532> They're produced asynchronously, possibly on opposite sides of the world. They may contain duplicate or double-spend transactions.
21:18 < hodlwave> if they have the same Txs, next bead names both top & bottom as parent
21:18 < bsm117532> No, next bead may name them both regardless.
21:18 < hodlwave> so both hashers of top & bottom receive a share
21:19 < bsm117532> (I'm ignoring coinbase rewards to answer your question, but we can get to that after)
21:19 < hodlwave> ok. so in the case where they have conflicting Txs why is the child naming both of them as parents? why not just the bead with the lower hash?
21:20 < bsm117532> It's not necessary. We're not using the longest chain rule.
21:20 < bsm117532> In principle a DAG need not have forks.
21:20 < hodlwave> ah gotcha. but the purpose of naming both is to reward both, right?
21:21 < bsm117532> The purpose of naming both is to ensure a complete history of all mining and transactions. In bitcoin, orphans are "forgotten" and the source of a latency-based race condition.
21:21 < bsm117532> Idea is to eliminate that race condition.
21:22 < bsm117532> If one side is forked away (as in bitcoin), someone isn't compensated for their mining, generating a race condition to get your block to everyone as fast as possible.
21:24 < bsm117532> The DAG allows latency (up to a necessary extent), eliminating the race condition (miners on both side of the diamond are compensated appropriately) but leaving the which-tx-is-accepted question, which is what I was trying to answer.
21:25 < hodlwave> Ok I think I understand the motivation. But the child must see both TOP and BOTTOM beads before being mined so I'm wondering how this fixes the latency issue
21:26 < hodlwave> is that the necessary extent?
21:28 < hodlwave> e.g. you're mining a share based on the TOP bead, then see the BOTTOM bead, and mine a bead that references both
22:01 < bsm117532> No problem, create a pentagon.
22:02 < bsm117532> "heaviest chain" algorithm is a bit more complicated, but fairly straightforward. I can elaborate if you're interested.
22:10  * bsm117532 elaborates. Asynchronicity is a bitch. (pun intended)
22:18 < bsm117532> First, define difficulty which is difficulty=1/target (d=1/t)
22:18 < bsm117532> For beads that form a blockchain, the effective difficulty of a pair of sequential blocks is d = d_1 + d_2. e.g. total difficulty is the sum of the two difficulties, and this is compared to any other fork ("longest chain" = "sum of difficulties")
22:20 < bsm117532> For the diamond graph, we add difficulty as d = 2/(1/d_1+1/d_2). If d_1 = d_2, then d = d_1 = d_2.
22:20 < bsm117532> In other words, a diamond graph contributes the same difficulty as a single block.
22:21 < bsm117532> They're asynchronous, so neither is "extending the longest chain". If both are combined, their sum "extends the longest chain" by the equivalent of one block.
22:22 < bsm117532> The point of this math is that it's used to decide which "side" of the diamond has higher weight, so that transactions within the cohort "win" over others.
22:22 < bsm117532> In a pentagon diagram for instance, one side has two beads in comparison with the single bead on the other side.
22:23 < bsm117532> If all difficulties are equal, there is no way to decide which side has "higher weight"
22:24 < bsm117532> So you fall to luck, which is l = 1/h with h being the actual hash discovered, instead of the target.
22:25 < bsm117532> That lets you unambiguously decide which side of the pentagon has the transactions that come first.
22:25 < bsm117532> (A pentagon has 3 transactions in the middle cohort, 2 on one side 1 on the other)
22:26 < bsm117532> The above math has an analog in electric circuits, specifically Kirchoff's rules for adding resistors or capacitors in series or parallel.
22:28 < bsm117532> Given a cohort graph, one can deterministically derive a set of equations for the effective "resistance" or "capacitance" of beads. This is a basic graph theory or electronics problem for which there exist O(n) solutions.
22:30 < bsm117532> So, big picture, I think I have "ordering of transactions" solved for a braid, with the same guarantees/attacks as bitcoin (51%).
22:31 < bsm117532> Next we can get into coinbase rewards and incentives.
22:32 < bsm117532> One consequence of the above is that regardless of your coinbase reward algorithm, you can't calculate it until the cohorts are known (if coinbase rewards are proportional to "effective difficulty" -- they don't have to be).
22:33 < bsm117532> You can do funny things with the coinbase reward, but tx fees DO have to be allocated according to effective difficulty, because some tx's that are in the graph may be double spends, and not confirmed long-term.
22:34 < bsm117532> Bitcoin has the 100-block rule (you can't spend coinbase coins until 100 blocks after they're mined). A braid has a similar restriction, and what it's really doing is waiting for cohorts to form, deciding tx-fee rewards ex-post-facto, delayed by a time that should be large compared to the measured latency of the network.
22:35 < bsm117532> (Network latency can be directly be measured from the fraction of diamond/non-chain blocks in the DAG)
22:36 < bsm117532> That study (network latency from DAG structure) is what's on my github, linked in the MOTD.
22:40 < bsm117532> Correction: in a pentagon diagram, one side has 2 blocks in a blockchain formation which has 2*difficulty relative to the single block on the other side. So any txs on the 2-block side "win" over the other for the purpose of deciding double-spends (and you don't have to fall to luck in that example)
22:41 < bsm117532> the single-block side could be an attacker with < 51% hashpower, for instance, and his transactions are not confirmed (though recorded).
22:44 < bsm117532> If an even longer chain appeared naming the single-block side of the pentagon as a parent (but not the 2-block side), it would "confirm" the 1-block side and reverse the total order of transactions. (It's a 51% attack -- and a bigger cohort)
22:44 < bsm117532> So, you need a general algorithm to evaluate complex diagrams. Hence, Kirchoff's rules.
22:50 < bsm117532> Finally: rewards and incentives.
22:51 < bsm117532> The reward is a "share", as the term is used by mining pools. It's directly proportional to the difficulty.
22:52 < bsm117532> Call it a share-coin.
22:52 < bsm117532> The coinbase consumes share-coins and creates BTC (if and only if it's a successful bitcoin block) in proportion to bitcoin's difficulty.
22:53 < bsm117532> Hashers would earn share-coins and place offers to swap them for BTC in the next available coinbase (these are txs on the braidpool network).
22:54 < bsm117532> This is the basis for derivative instruments like forwards/futures/options which fundamentally are d(sharecoins)/d(BTC) derivatives.
22:54 < bsm117532> See my MCC talk (and Jack Mallers' talk) on why every miner wants this.
22:55 < bsm117532> <phew> going to bed...
--- Log closed Fri Feb 14 00:00:40 2020