Monthly Archives



Incentives and Trade-offs in Transaction Selection in DAG-based Protocols




文本 https://stanford2017.scalingbitcoin.org/transcript/stanford2017/incentives-tradeoffs-transaction-selection-in-dag-based-protocols

视频 https://stanford2017.scalingbitcoin.org/presentations

PPT https://stanford2017.scalingbitcoin.org/stanford2017/Day2/Sompolinsky_SB4.pdf

TranStudy https://github.com/DAGfans/TranStudy/blob/master/Blogs/Incentives%20and%20Trade-offs%20in%20Transaction%20Selection%20in%20DAG-based%20Protocols.md

Incentives and Trade-offs in Transaction Selection in DAG-based Protocols


Yonatan Sompolinsky (The Hebrew University) Yonatan Sompolinsky (希伯来大学)

My name is Yonatan Sompolinsky I’m a PhD student in Hebrew University under the supervision of Aviv Zohar which talked previously and also I’m a co-founder and scientist at DAGlabs which is a commercial effort to implement DAG based protocols and I feel comfortable here to say that we’re not doing an ICO —- it’s a regular company.

我名叫Yonatan Sompolinsky, 现在在希伯来大学就读博士学位, 之前的演讲嘉宾Aviv Zohar就是我的导师, 此外我还是DAGlabs的联合创始人兼科学家. DAGlabs是一家致力于实现基于DAG协议的商业机构, 在此我表示很放松因为我们不会进行ICO – 这就是家常规的公司.

A little bit of background about DAG based protocols. The background to this work is a line of works we’ve done in the Hebrew University with my colleagues, again, Yoad Lewenberg and Aviv Zohar, my supervisor. This idea of block DAG is a modification of the layer 1 of Bitcoin and so it’s a generalization of the chain structure of the blockchain. As such , it’s orthogonal to any layer 2 solutions - Lightning Network and all micropayment channels, etc.. So we’re scaling up layer 1, you are scaling up layer 2, these are complementary solutions.

稍微介绍下基于DAG协议的背景知识. 此项工作是基于一系列我们在希伯来大学和我的同事们的工作, 即Yoad Lewenberg 和我的导师 Aviv Zohar. 区块DAG(block DAG)的概念是对一层的比特币协议的改进, 所以对链式结构的区块链的泛化(generalization).(译注: 这里的泛化是指区块链是block DAG的一种特例, 所以区块链本质上也是DAG). 正因如此, 它对于任何二层解决方案 , 如闪电网络(Lightning Network)和所有的微支付通道等, 都是互不相关的. 所以说, 我们是在做一层扩容, 你们在做二层扩容, 这些都是可以补充进来的方案.

This talk will be focused on an idea that we develop in the Inclusive blockchain paper in 2015 and we kind of revisited these ideas now because we’re heading up to to scale up to implement these block DAG protocols.

本次讨论会聚焦在我们2015研究的Inclusive的区块链论文上, 我们算是在回顾这些想法, 因为我们已经在去实现区块DAG的协议了.

Blockchain vs BlockDAG

区块链 vs 区块链DAG

The first difference is that in a chain you would maintain a single chain. But in a DAG you have an entire graph of blocks. In a chain, we ignore anything that is off-chain and any data that was not in the chain. In the DAG, you use all of this information, you harvest all information from all blocks. The third implication that in a chain paradigm you are trying to suppress throughput so that spontaneous forks are rare in the system. In a blockDAG system, forks are a common phenomena of the system and many forks are created in parallel.

第一个区别在于在链式结构中你维护的是单一的链. 但在DAG中你拥有的是整个区块组成的图. 在链式结构中, 我们会丢弃掉不在链下和不在链上的数据. 在DAG结构中, 你可以使用所有的信息, 你可以从所有的区块从提取出所有的信息. 第三个影响是在链式模型中你会尝试抑制吞吐量所以并发的分叉在系统中是很少见的. 但是在区块DAG系统中, 分叉是非常普遍的现象而且会有很多分叉是并行创建的.

As you can imagine, this is essentially a matter of information. In a chain paradigm you ignore everything that’s off chain. In a DAG paradigm you use in this entire information and this information can be used for more scalability more security more fairness. But the fact that is it can be used to these stuff doesn’t mean that every blockDAG uses, so just to drop a name, Ethereum’s GHOST is mostly about fairness not scalability.

正如你可以想象的, 这本质上是个信息的问题. 在链式模型中你会丢弃所有的离线信息. 而DAG会利用这个完整的信息来增强可扩容性, 安全性和公平性. 不过事实上, 可以利用这些信息并不代表所有的区块DAG会利用, 随便说个例子, 以太坊的GHOST就主要是用于增强公平性而非可扩容性.

Scaling up layer 1 using DAGs


The first step would be to speed up block rate. Instead of 1 block every 10 minutes or 1 block every 21 seconds, imagine 50 blocks per second or maybe more. That’s step one. So we need spontaneous forks of the chain.
The second step is to modifying the mining protocol where instead of extending a chain, you want to reference previous blocks and all the tips that it sees, and integrating the forks into one graph so that you have this massive cool graph which his directed acyclic graph. Seems so simple so far.


The third step is the most crucial, though. Which is extracting a consistent set of transactions from this graph. The graph might contain conflicts and you want to extract from it and order it and make it work.
This is the main challenge of a blockDAG effort. We developed the SPECTRE method to deal with this as discussed 2 years ago in Hong Kong. The consistency rule is the main challenge.


2018-07-12 4 09 31

I want to clarify that blockDAG is not a solution, it’s merely a framework on top of which someone can develop on top of.
Consequently, not all blockDAGs are that are created equal I mentioned etheruem ues some notion of a DAG partially. You can design other variants.
I like to think of DAG vs chain as chain is slow single one lane road in a small town and a DAG is a highway and the first implicaiton of this is that if you don’t know what you’re doing, you’ll have a mess and you have to think carefully about what you are doing with your DAG.
So you want an ordered highway, everything is clear, and high throughput.
If you are very lucky, or very thoughtful, you can evolve a protocol with fast confirmations at least for some transactions, which is the topic of this talk.

因此,并非所有的blockDAG都是相同的,我提到过以太坊部分地使用了一些DAG的概念。你可以设计其他变形。 我认为DAG VS 区块链,就好像区块链是一个小镇的单一低速的车道,而DAG是一条高速公路,这首先意味着如果你不知道你在做什么, 你会弄得一团糟,然后你必须仔细考虑你要在你的DAG上做些什么。

To scale up blockchains using DAGs opens up various challenges. The first challenge is the consistency rule. You also have to address confirmations time, how much storage you want miners or full nodes to store and for how long, so think of 1000 tx/second, at least 86 gigabytes per day, do you want to store this forever or not? These are challenges that need to be addressed. Fee structure, fairness, how to maintain decentralization, etc.


How do you utilize the DAG fully so that the entire throughput or at least we’re close to the entire throughput that the DAG can supply? I will show you why this is not a trivial challenge. We have two scenarios for a DAG.
Imagine many blocks per second But for simplicity just say two miners. You’re mining 1 and you are mining 2. We are mining 4 transactions. We both create blocks because it’s real time and there’s no time to coordinate and there are two scenarios.
The less optimistic scenario is where you select tx 1, tx 2, and I select tx 1, tx 2 from the mempool and what happens in this case is that bcause these transactions are not conflicting, then no harm was done in the sense that both transactions were approved by the system.
However you wasted space. So tx 1 and tx 2 took the space of 4 transactions. So this is just a very simple example and of course the optimistic scenario or the green scenario on your left hand side would be that you somehow selected tx 1, 2, and the other miner picked tx 3, and tx 4. So this is a good outcome.

然而,你浪费了空间。因此交易1和交易2占用了四4个交易的空间。这仅仅是一个非常简单的例子,当然以你的角度,乐观一些的情况或者是绿色的情况是你以某种方式选择了交易1,交易2,而另一个矿工选择了交易3和交易4。 所以这是一个很好的结果。

The main question of our research here is how do we make sure that we are closer to the green area than the red area? Assume we have a good consistency rule and a good blockDAG protocol. How can we make sure that transactions are not duplicated across chains?


If you don’t do anything and let miners mine greedily the top transactions in their mempool, then the DAG gains nothing in terms of throughput.
We did a simple solution generated by my colleague. The green curve is this throughput of a DAG. By using a greedy mining policy where every miner selects the top transactions from the mempool.
The yellow curve represents a chain structure with the same parameters. The chain throughput and the DAG throughput are almost identical. So DAG gains us nothing in terms of throughput, but it does gain us something in terms of confirmation time. These curves are very far from optimal.
We can ain much more– DAG has more capacity if we were more wise and used a better scheme to coordinate between miners.


2018-07-13 11 47 27

So here’s the good news and perhaps the main thing I want to message to convey to you. The miners are incentivized to some extent to avoid collisions and avoid tx duplication and contribute unique transactions and increase throughput.
So this is a natural incentive of miners to contribute to the healthiness of the system.The reason is simple. If we collide in th same system, if we choose the same tx for our blocks, then we need to split the fee, you will get half of the fee or some other portion I will get the other portion but we can’t pay the fee twice.
And we both embedded the tx in our block. Only one of us will get the fee or maybe we will split it but we won’t be able to extract the entire fee twice. So there’s incentive to coordinate and avoid collisions.


Chicken game


And now we’re headed to a more formal treatment of this problem. I hope the chicken game is known to most of you. It’s a famous game to model conflicts.
You have two parties driving towards each other and heading to collision. And the first one to swerve and chicken out is the chicken and the one to stay the course is the winner and daredevil.
And of course, if either you chicken out then the other party wins. And if we both dare then there’s a collision. The transaction selection game in blockDAG is quite similar.

而现在我们正在对这个问题进行更形式化的处理。我猜大多数人知道胆小鬼博弈。这是一个模拟冲突的著名游戏。 你有两队,都朝着对方行驶并即将碰撞。第一个转向并胆怯的人是胆小鬼,另一个继续行驶的人是胜利者并且是胆大妄为的。

We have tx1, tx2 in the mem pool and one of the transactions is more expensive (tx1) let’s say it pays 2 millibitcoins and tx2 pays 50% as much. So now we have to decide how to let numbers should be different I’d say tx1, 3 millibitcoin and tx2 would be 2 millibitcoin. If we both select tx1, the most high paying transaction, we will collide and need to divide the fee between us. But if we both select tx2, we need to divide a lower fee between us. So we need to coordinate and select the transactions. This would be the optimal setup.


Strategies in this game is the important point you have in game theory. Pure strategies which is simply which transaction to select, and you have mixed strategies which is using randomness to select.
In a mixed strategy setup I can toss a coin and then decide which transactions to select. In game theory, using randomness you can achieve much better results for all players.
In practical terms, we are looking at setup in a DAG where miners will randomize over the mempool to select transactions. In bitcoin, a miner selects the top transactions. But in a DAG, the best thing for you to do is to randomize over the mempool according to some distribution and then use this to maximize your throughput.

在博弈论中, 博弈策略是非常重要的, 纯策略只是简单地选择交易, 而你也可以使用混合策略来随机选择。在混合策略方案中,我可以掷硬币,然后决定选择哪些交易。在博弈论中,使用随机性可以为所有玩家获得更好的结果。

How do we solve this chicken game? In game theory, there are several approaches.
The top left, scenario is that there’s adversarial setup.
You are a mining pool, you are paranoid, you think everyone is going to sabotage your profits and they want your revenue to drop.
In that scenario, your safe solution is that you just want to guarantee yourself the best response against everyone else that wants to sabotage me and lower my profits.
This is quite adversarial and does not fit loving bitcoin community so we might consider more cooperative setups.
The selfish setup is a more common one, which is more similar to the Nash equilibrium model where every party pursues their own interest but somehow the invisible hand brings us to equilibrium under which nobody gains from deviating.
This is a common concept.


There’s also an interesting equilibrium concept invented by Robert Oman he’s a novelist from the Hebrew University and this is coordinated equilibrium where everyone is selfish but we have signal for some coordination and in mining the signal could be the randomness from previous blocks.
Perhaps we can use some randomness from previous blocks to select more wisely transactions to our mempool.
And then most optimistic, everyone is playing just for the sake of the health of the system.
You can think of bitcoin’s early day as a setup as where the only concern of everyone was to maximize social welfare, and miners were confirming zero-fee transactions and there were less incentives back then. block.

你可以设想下早期比特币的情景, 每个人唯一关心的就是最大限度地提高社区福利, 并且矿工也会去确认零手续费的交易。尽管当时的激励措施较少。

Max social welfare


We can visit several of these ideas but let’s begin with max social welfare. This is the simplest and most optimistic. What would be the solution here?
All the miners are cooperating, they just ask us, we don’t know how they coordinate, there’s a design mechanism undre which the DAG is utilized and we won’t collide and the throughput is at maximum. The solution in this case is rather simple.


The construction to the miners would be just select a transaction in random uniform distribution from your mempool, so let’s say you have 6 transactions or thousands, you do this by tossing a fair coin between them until some threshold, and you accept all transactions uniformy.
The threshold is what’s the capacity of the DAG, you can’t overcome this capacity, and it’s very famous and simple result from queueing theory that says that you won’t have any collisions in the system.
The buckets of transactions would be sparse enough that collisions will be negligible. This setup of course is a bit naive. There’s two catches.

阈值是DAG的容量,你不能超过这个容量。这是一个非常着名且非常简单的排队理论结果,它说这实际上意味着你不会在系统中发生任何冲突。 交易分组足够稀疏时碰撞可以忽略不计。当然,这个方法有点幼稚。这个方法有两个缺点。

This is strategically unstable. We’re assuming that everyone is maximizing social welfare and this is not always the case.
There’s a more inherent problem with this approach which is that it does not allow for differential service to urgent transactions. You can’t prioritize transactions by fees.
So I am not able to signal to miners that I need this tx faster, I am willing to pay more. So if they are not picking transactions by fees, then everyone waits about the same time.


And some transactions will never be approved. You can think of this as the highway where everyone is stuck in the same traffic.
As a system designer, is that really what you want to achieve? You want a system that has express lanes, where people are willing to pay more.
Assume there’s a payment for the express lane, of course. They are willing to pay more to get to their destination faster.
And then you will have this curve that says the larger you pay, the faster you get inside. So this is one thing you want to design the system according to.


Other strategies


If you have high utilization of the DAG with collision avoidance, then you can’t serve the express lane and can’t have prioritized transactions.
Because you need signal to miners to back off from expensive transactions so that they don’t collide. And on the other extreme, if you allow for fast confirmation times, then you will inevitably suffer from collisions.
So what you see here is simply the function of how long have the numbers of collisions of a transaction as a function of the of the of its waiting time. Only transactions that allow themselves to wait a long time the buffer suffer no collisions. Transactions that want to be confirmed fast will suffer collisions and would need a higher fee.


In the chicken dare situation, what happens in the real world?
The problem here is intractable. Usually in these games, nash equilibrium is hard to find.
But the spirit of Nash equilibrium is something in the form of if I see you cooperating, then I will cooperat.
But if you are greedy and you are always picking the highest transactions for your block, then I will also be greedy and pick the highest paying transactions.
I apologize for the militaristic tone, but this is tit-for-tat strategy. And it helps understand how mining pools will behave.

在胆小鬼博弈的场景下,在现实世界中会发生什么?这个问题是棘手的。通常在这些博弈中,很难找到纳什均衡。 但是纳什均衡的精髓就是如果我看到你打算合作,那么我就会合作。

In a world where mining pools don’t hide their identity, if a mining pool really will be greedy, then other mining pools will start sabotaging that pool by colliding with their transactions. It’s an interesting game theoretic framework. Chicken dare is not unique to two mining a blockDAG transactions.


We did a more modest goal– namely, we computed the nash equilibrium for the single shot game. We only played once, what would be the nash equilibrium?
The qualitative message of the nash you can see here that we picked high paying fees with high probability.
So if a use wants to embed his transaction fast, he will put a large fee, but then we will all sort of collide. The curve does not reach probability 1.
Even if I am paying a high fee nobody will be greedy enough to pick it with certain probability. More good news for you is that nash performs quite well.
The utilization of the DAG under nash equilibrium even if everyone is selfish, it wouldn’t be so bad. It’s around 72% on this graph. So 70% of the graph obtains unique content and unique transactions.
It’s a surprising result. If everyone was selfish then we would revert back to the greedy scenario, you wouldn’t be greedy even if you’re selifhs because you want to randomize over your mempool to avoid collisions.


2018-07-13 12 00 38

Quality of service


Can we improve utilization a bit more? Another interesting graph we must talk about is the quality of service level. As I said, the problem with the maximum social welfare solution is that you can’t prioritize transactions. Here the tall grey bars represent max social welfare strategy. Everyone waits the same time.


And then the blue bars represent the nash equilibrium where you approve less transactions- only those that have 3 millibitcoin and those exact numbers do not matter of course, it’s a dummy model.
As you increase the fee, you wait less. We want this feature. We want high-paying transactions to wait less. And we have other strategies like exponential strategy. If everyone is greedy, then you would only approve a small set of transactions.
This is a good illustration of the challenge.


2018-07-13 1 11 12

Correlated equilibrium


Perhaps with coordination between miners we can achive better results than nash. We could use previous block’s randomness. Preliminary results show that we are able to utilize the DAG better. Needs further investigation.


Scaling and incentives


In bitcoin selfish mining is a known attack and deviation on the protocol. It’s risky, it only works in a long term after two weeks at least. And so arguably the reason why we didn’t see selfish mining until now or at least not in notable amounts was that playing with your mining node just to withhold your blocks and risk losing it all is too risky and miners wont engage in such behaior.


Unforotunately in a DAG, deviating from the mining protocol is much more available to you, you just need to select transactions in a certain way or hold your blocks for a few seconds. So if I am withholding my block for 2 bloks, that’s not going to hurt me.
It’s a much more granular decision for how to optimize my mining, and the risks for the miner are less. The harm to the system is relatively marginal.

不幸的是,在DAG中,违反挖矿协议是更容易的,你只需要以某种方式选择交易或者将块扣留几秒钟。因此,如果我扣留了我的块中2个,那不会对我造成损失。 如何优化我的挖矿行为, 并让矿工承担较少的风险, 同时对系统的伤害也相对较小, 需要细致地研究.

Also lazy selfish mining is another concern- it might not have communication infrastructure either deliberately or by laziness and doesn’t propagate blocks to the network.
This pool might not lose too much profit and other miners might be harmed, this is an interesting topic for us so we’re investigating it.


When implementing blockDAG protocols, the incentives really matter.
Bitcoin has 1 block every 10 minutes.
Things are are pretty robust at least in the mining at least as you stay in the same chain but in DAG things are very sensitive.

比特币每10分钟产生1个块,是非常健壮的, 至少是在挖矿方面, 至少你还在同一条链上, 但是在DAG上, 问题会变得非常复杂.

Related Posts