DAG与区块链简介（从零开始学区块链 184）
DAG与区块链简介（从零开始学区块链 184）
文章来源：区块链大师
DAG,区块链简介,学区块链
最近有人问DAG相关的东西，今天就来说说关于DAG的话题，DAG是一个数据结构名词，有项目用了这种复杂的结构来存储交易数据，本文只能粗略探讨一下
如果你还记得大学开设的《数据结构》科目，DAG出现在那本书的最后一章“图论”中，图应该是最复杂的数据结构了，所以当时我们学校并没有教最后一章，只是让感兴趣的人自学，由于后来的工作中最多用到B+树，对于图的学习只是停留在表面，只是记得存储图最好的方式是采用“邻接多重表”这种结构。
图和树一样，是一种数据结构，在计算机科学中往往为了避免复杂的数据结构影响开发和数学建模会将结构进行简化或者约束，比如“树”这种结构其实根据定义也是很复杂的，当时真正用的时候“二叉树”用的最广泛，二叉树就是规定一个根只能有两个叶子。
所以在图论中，为了简化这种结构，分为有向图和无向图两大类，在无向图中进一步进行约束形成了DAG（有向无环图），所谓无环是指它是由集合的顶点和有向边构成，每条边连接一个顶点到另一个，这样，在一些顶点v开始，沿着有序的边，最终循环回再次到V是不可能的，其实图是树的一种泛化，真正在用的时候一般会通过深度优先或者广度优先规则把图拆成“森林”就是多颗“树”，而DAG图由于规则的定义更容易拆成一颗“树”，这也就是为什么图有很多种，而DAG应用最为广泛的原因。
上图从左到右分别是二叉树、DAG图、和普通有向图的图例，可以在最右侧的图明显看到存在一个“环”，此图可以非常容易的理解什么叫DAG图了。
DAG与区块链
目前采用DAG作为存储结构的代表项目有dagcoin、Byteball、Iota，我看过前两个的白皮书，dagcoin和byteball白皮书在DAG部分完全一致看其中一个即可，很多人说采用了DAG已经不属于区块链了，因为传统区块链采用“链”式结构，其实传统区块链中存在多条链的分支更类似一棵树，而最终确认的是最长链，也就是在树的结构中找到一条合法的链而已。
而采用了DAG结构的项目，为了避免双花问题，还是有所谓的”主链“概念，其实就是经过见证人认定的最短路径了，所以我认为DAG还是应该归类到区块链范畴，其本质没有大的改变，只是采用了DAG结构，效率更好，对于没有”异议“的交易，可以采用DAG进行打包，Byteball将其定义为”球“，图论中有详细的描述，也是为了减少复杂度，如下图：
相比传统链式结构，采用DAG面临的双花问题会非常复杂，根据Byteball的描述，采用了见证人主链概念，维持一条公认的主链作为凭证，而其他分支只要不和主链冲突都可以视为有效交易，我个人认为采用DAG并不能减少目前区块链面临的存储空间问题，当然DAG可以提升效率，由于其数据结构非常复杂，对编码要求更高，安全性有待观察，对于算力攻击问题，我有个担忧，希望与DAG研究深入的人交流，就是传统链式结构，你必须保持持续的算力优势才能更改交易，否则最终长链可以将短期算力优势形成的链废掉，但是采用DAG分块的方式，你只需要在一定时间内的算力保持优先形成一个DAG块，那么是不是今后所有的交易都会继承这个错误呢？
区块链最让人感兴趣的地方就是不断的创新和敢于利用新技术，当然就数据结构理论从70年代以来基本上没有什么变化，只是传统的软件项目很少利用到这些理论，计算机图形学是我看到的利用复杂数据结构最多的地方，而且商业项目能用到B+树已经是极限了，而区块链的发展让人惊喜，理论联系实际的好榜样！
最后说一句，区块链技术终究是计算机技术的一种，没有必要将其神话，所有的结构和实现都可以在《数据结构》本科教材中找到，但是要灵活运用在业务场景中，需要取舍和经过实践检验，另外我会持续关注DAG结构在新型项目的应用，有机会和大家进一步交流
来源：区块链大师 & 微信号 ：DACMaster
比特币多空调查
最新数字货币
扫一扫关注我们
郑重声明：本站主要用于区块链行业信息的传播，促进行业健康发展，部分信息均搜集转载自互联网 版权归原作者所有 如作者信息标记有误 请第一时间联系我们修改或删除 谢谢！QQ群： @2017qukuaiwang.com.cn 区块网 闽ICP备号-5客户端下载
发送验证码
未注册的用户手机验证后自动登录
30天内免登录
社交账号登录
绑定手机号
发送验证码
从零开始，创建自己的区块链
本文内容主要翻译自Learn Blockchains by Building One。最快的学习区块链的方式是自己创建一个。我们都对比特币的崛起感到惊讶惊奇，并且想知道其背后的技术——区块链是如何实现的。但是完全搞懂区块链并非易事，至少对我来讲是这样。我喜欢在实践中学习，通过写代码来学习技术会掌握得更牢固。通过构建一个区块链可以加深对区块链的理解。准备工作我们知道区块链是由区块的记录构成的不可变、有序的链结构，记录可以是交易、文件或任何你想要的数据，重要的是它们是通过哈希值（hashes）链接起来的。阅读这篇文章，要求读者对Python有基本的了解，能编写基本的Python代码，并且需要对HTTP请求有基本的理解。环境准备确保已经安装Python3.6+, pip , Flask, requests。安装方法：pip install Flask==0.12.2 requests==2.18.4同时还需要一个HTTP客户端，比如Postman，cURL或其它客户端。一、开始创建BlockChain打开你最喜欢的文本编辑器或者IDE，比如PyCharm，新建一个文件 blockchain.py，本文所有的代码都写在这一个文件中。BlockChain类首先创建一个Blockchain类，在构造函数中创建了两个列表，一个用于储存区块链，一个用于储存交易。以下是BlockChain类的框架：class Blockchain(object):def __init__(self): self.chain = [] self.current_transactions = [] def new_block(self): # Creates a new Block and adds it to the chainpass def new_transaction(self): # Adds a new transaction to the list of transactionspass@staticmethod def hash(block): # Hashes a Blockpass@property def last_block(self): # Returns the last Block in the chainpass从零开始区块链：如何证明计算机的工作量？——比特币经典论文研读 (3)
这一节我们会涉及到比特币一个很关键的问题，工作量证明。这部分的内容偏多，我会拆分成几个小块分析。
本系列历史文章列表
6.时间戳服务器
在邮政领域里，有一个概念叫“邮戳”， 一般标明邮件寄出或者收到的时间地点。时间戳就是服务器给数据块加上时间标记，用于标识数据和时间的关系。时间戳服务器把当前数据块的哈希值打上时间戳后，发布到网络中。这就证明了在标识的时间刻度下，这个数据是存在的。每一个时间戳对应的数据块中，包括了前一个数据块的时间戳哈希，于是这样可以形成数据链。
关于这一部分作者并未作详细论述，我们接着往下走。
7.工作量证明（1）
这一段讲的是工作量证明的问题，有几个知识点需要储备：
(1) 设计原型 HashCash
作者提到了一个叫HashCash（哈希现金）的工作[12]。HashCash最初设计的目的是为了防止DoS（拒绝服务攻击）。
拒绝服务攻击的意思就是，如果你要攻击一个服务，就发起虚假的服务请求，让服务不得不响应，消耗了资源，让真正需要服务的人得不到服务，于是“拒绝服务”了。比如，如果你开了一家小卖部，有一天来了很多人，挤满你的店，只询问不购买，你忙着招呼这些人，那真正要买东西的人就进不来，于是对他们而言，店面就瘫痪了。
但是你开店的目的就是为了接客卖货赚钱，所以你还不能把店给关了。就像网络上的服务一样，服务设立的目的就是为了接收请求的，而当你受到DoS攻击干扰的时候怎么办？于是你只能想大致检查一下，这个请求是不是真正的请求，客户是不是真的要买东西，还是在捣乱。
那要怎么检查？在网络上，就让请求者做一些事情，这些事情要有这样的特征：做到这件事情要付出一些代价，检查有没有做到，只要很少量的代价。因为攻击者的资源也有限，所以发起的攻击也不能完全模拟成像真的一样，有很多虚假的攻击可以通过一些方法过滤掉。我们生活中的验证码其实也是这个思路，你把在一堆乱花丛中的文字挑选出来，需要花费功夫，服务器只要对个答案就好了。
HashCash设计了一个“代价函数(cost-function)”，这个函数的特点就是，要计算出结果工作量较大，但是要验证起来很容易。具体而言，就是代价函数让发起请求的人，算出一个“token”出来。这里的token取了双关的含义：一方面，这是一个符号或者标识，另外一方面这个和区块链里的“代币/通证”对应一个英文。下文如无特殊注明，我统一用“通证”代表token。
HashCash把计算这个通证的函数取名叫作Mint()，记得比特币论文前面作者也用了mint这个词么？这个词有造币厂的含义，在第2篇文章的第5部分里，我先没有译出，而是选用了“权威机构”来表示。到这里就能串起来，因为在HashCash中，采用了“造币厂”的隐喻，来代表“代价函数”生成一个通证。你想一下，在生活中，造出一枚硬币，或者印出一张钞票，是不是也是一件不容易的事情？但是验证钞票的真伪，其实要比造出钞票，容易许多。密码学家忙活半天，本质就是为了在网络上，构建出和现实世界想同属性的数学结构。
于是HashCash就可以总结出如下模式：
对应到防止拒绝服务攻击的场景下，就这样用。如果我要验证客户的身份，我就让客户通过Mint()函数给我一个通证T，这个通证的参数w就代表了工作量的大小，s可以理解为自定义的参数，这里先不考虑。然后我就可以通过Value()函数检查一下，到底是不是正确的，也就是，到底有没有包括这么多的工作量。
这个“做到困难，验证容易”的现象，在我们生活中其实很常见。
(1) 你高中刻苦三年，最后拿到了一张清华录取通知书，这个很难；但是拿着你的通知书编号去检查一下真假，这个很容易。
(2) 你辛辛苦苦地解出一道数学方程，这个很难；但是拿着你的答案，代入验算一下，这个很容易。
(3) 你经历各种磨难，做了很多事情，最后领悟到成长的几条真谛，这个很难；别人看了你的文章，感觉很有道理，这个很容易。
你有没有发现，生活有很多类似的“非对称”的结构，从一头到另一头，其实挺难的，但是反过来看，却容易许多。我们在网络空间构建信任，其实就是要利用这样的“非对称”的数学现象。
(2) 哈希函数 Hash Function
哈希函数又称为散列函数。在我大一接触这个概念的时候，其实很喜欢“散列函数”这个译法，感觉有。学到后面发现，在科技领域里“有技术、没文化”是普遍现象，于是也随波逐流地用“哈希函数”了。
哈希函数在密码学里有广泛的作用，甚至可以说是密码系统安全性的基石。简单的理解，哈希函数具备一个功能，可以把任意长度的数据（字符串、文件、数字、内存区块），归一到一个相同的长度。因为在计算机里，即使是文件，也是二进制，也是可以最终转换成数字的。经过哈希函数算出的结果，我们称为哈希值，也会叫作消息摘要（digest）。
图7：哈希函数示例
如果是初次接触这个概念，就把握好这么几个要点：
(a) 把变长转换为定长。不管是什么数据，经过哈希函数处理后，长度都是一样的。
(b) 计算容易倒推难。给定一串字符，算出一个哈希值很容易，但是根据哈希值反推字符内容，很难。
(c) 哈希值对细节敏感。如果把字符串修改一个字母，算出的哈希值都完全不一样。这个再延伸一下，你可以认为哈希的结果近乎是随机数。
如果你是一个会思考的读者，你可能会有一个问题：任意长度的数据可以有无限多个，但是转换到固定长度，却是只有有限个，那会不会出现两个不同的字符串算出来是一个哈希值？
的确是会有的，这个叫作哈希函数冲突或者哈希碰撞。在密码学里面，这个需要通过分析并且将概率严格控制到一定比例以下，以至于用现有的计算条件无法轻易地找到相同的哈希值。这就像你家里的钥匙，其他人的钥匙一般不能打开你的锁，如果两个人分别买两把锁，钥匙却能通用，那说明锁有问题，安全性就得不到保证了。
哈希函数是一种数学上的构想，现在有很多不同的实现，有的因为年代久远，安全性已经不能保证，已经不建议采用，例如MD5；但是有的现在仍然会使用，比如比特币就SHA-256来做工作量证明。至于具体这些函数是怎么算出来的，有相关的文档，如果有兴趣，在互联网上可以找到算法，读完以后你会更加怀疑自己的智商。
(3) 通过哈希碰撞难度，控制计算机工作量
有了以上知识的铺垫，下面要讲到怎么利用哈希函数来控制工作量了。
我们已经知道，可以通过让某个程序来计算出一个通证的方式，来验证工作量。这就是HashCash做的设计（HashCash也不是首创，只是比特币的参考），现在简单梳理一下HashCash怎么通过参数的方式来控制工作量。
这个公式看上去有点复杂，其实本质比较简单。
Mint()函数就是计算能代表w工作量的通证，这里表示成一个哈希函数，要求结果左边有w个零比特。前文已经说了，哈希函数算出的结果几乎可以看成一个随机数，现在要求这个随机数的二进制，前w位都是0。
那有什么办法可以快速算出通证T来么？没有。只能一个一个试。这就叫暴力破解。在密码学，暴力破解几乎算一种最管用但是也是最笨的方法。如果你把需要遍历的空间搞得很大，那猜到的概率就很小。
这就像生活中的密码是一样的，如果密码是四位数字，那我平均试1万次就够了，多加一位，次数多10倍。这个道理可以迁移，我在自己的《刻意学习[13]》这本书里也讲了“暴力破解”攻破你的成长问题。
好，那么到现在，我们就可以用这个参数w来控制Mint()函数算出通证T的工作量了。
比如，假如我把w设置成1，那任意一个哈希值，第1位要么就是0，要么就是1，最多试两次就搞定了，这是一个简单工作。
假如我把w设置成2，那任意一个哈希值，前两位最多有00、01、10、11四种情况，平均要试四次，工作量翻番。
如果我把w设置成k，那就是要从个可能结果里，找出一个全部是0的结果。
如果k就等于哈希值的全部长度，就变成前面说的哈希碰撞了。
计算结果的难度可以通过上述的示例展示，但是计算结果的验证呢？
假设我们的计算机拿出一个通证，这个通证代表着前6位都是0的工作量。那我要验证到底是不是有这么多的工作量，怎么办呢？我就只要算一次哈希，看一下结果是不是前6位都是0，就搞定了，对吧？这就是Value(T)做的事情了。
于是你可以看到，计算出一个通证，和验证一个通证的难度是不一样的。而计算通证的难度，通过一个参数，就可以控制。
这有没有点像在小学的时候，班主任布置作业，“课文抄5遍并背诵全文，家长签字”，然后你要做很长的时间，才能拿到家长签字的通证。所以你当天晚上能不能睡觉，就取决于老师让你抄5遍还是抄50遍。
在工作岗位中，我们往往会通过产出量、加班时间来看一个员工的工作量。在马克思的《资本论》里，建立了剩余价值的理论体系，揭露了资本对于劳动的压榨剥削；在这一节，我们发现了一种虐待计算机的方法，通过让计算机去算通证，用来作为计算机的工作量证明。假如有一天，机器之间也存在价值剥削与等级关系，工作量证明可以不失为一项有效的衡量手段。
下一节我们继续讨论比特币的工作量证明。
[12] Back A, Others. Hashcash-a denial of service counter-measure[J]. 2002.
[13] Scalers. 刻意学习[M]. 北京联合出版社, 2017.
★★★★★
★★★★★
本文原文：http://www.scalerstalk.com/1307-Mint
责任编辑：
声明：本文由入驻搜狐号的作者撰写，除搜狐官方账号外，观点仅代表作者本人，不代表搜狐立场。
今日搜狐热点他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)