以太坊日志的bloom过滤器

发布时间:2019年05月07日 价值:20000.00 / 共识:25

最近研究以太坊的收据(Receipt),发现区块头中有一个Bloom字段,这个字段是个2048的字节数组:

  1. const (
  2. // BloomByteLength represents the number of bytes used in a header log bloom.
  3. BloomByteLength = 256
  4. // BloomBitLength represents the number of bits used in a header log bloom.
  5. BloomBitLength = 8 * BloomByteLength
  6. )
  7. // Bloom represents a 2048 bit bloom filter.
  8. type Bloom [BloomByteLength]byte

通过注释知道这是一个Bloom过滤器,但是这个过滤器是如何工作的。引起了我的兴趣,这一看相关代码,让我预闷了一周多的时间。各种通道和文件让我没有任何头绪来了解这个Bloom是如何起到过滤作用的。现在有了点头绪,想通过几篇文章做个分享。

一。Bloom是如何生成的

  1. ~~~
  2. b.header.Bloom = CreateBloom(receipts)
  3. ~~~
  4. func CreateBloom(receipts Receipts) Bloom {
  5. bin := new(big.Int)
  6. for _, receipt := range receipts {
  7. bin.Or(bin, LogsBloom(receipt.Logs))
  8. }
  9. return BytesToBloom(bin.Bytes())
  10. }
  11. func LogsBloom(logs []*Log) *big.Int {
  12. bin := new(big.Int)
  13. for _, log := range logs {
  14. bin.Or(bin, bloom9(log.Address.Bytes()))
  15. for _, b := range log.Topics {
  16. bin.Or(bin, bloom9(b[:]))
  17. }
  18. }
  19. return bin
  20. }
  21. func bloom9(b []byte) *big.Int {
  22. b = crypto.Keccak256(b)
  23. r := new(big.Int)
  24. for i := 0; i < 6; i += 2 {
  25. t := big.NewInt(1)
  26. b := (uint(b[i+1]) + (uint(b[i]) << 8)) & 2047
  27. r.Or(r, t.Lsh(t, b))
  28. }
  29. return r
  30. }

通过源码我们可以看到Bloom数组就是从收据(Receipt)中的Logs字段生成的。具体的内容是Logs中的Address和Topics字段,为了大家好理解,我简单介绍下Log中的Address和Topics字段所代表的内容:
>

type Log struct {
//以太坊智能合约的地址
Address common.Address json:"address" gencodec:"required"
// 以太坊智能合约转账过程中相关的转入转出方的地址hash
Topics []common.Hash json:"topics" gencodec:"required"
//以太坊智能合约转账的金额
Data []byte json:"data" gencodec:"required"

Address:代表合约,Topics代表地址,合起来就是某个合约Log的相关地址
为了大家了解就先这样了解上面的字段。如果想更深入,请查看其他文档。

所以看到这里我们就明白了区块头的Bloom字段其实就是根据一套算法(bloom9)将合约Address和Topics生成了一个2048字节的数组。

二。Bloom9算法

我们已经知道布隆过滤器里存储的是Log的合约地址(Address)和相关账户哈希(Topics)。布隆过滤器的一个特性就是不保证一个内容100%存在,但可以100%保证一个内容不存在过滤器中。了解了这个特性我们就介绍下布隆过滤器的生成算法Bloom9:

1.首先将传入的任何数据,进行Keccak256的运算,得到一个32字节的hash 。
2.循环取此hash值的前6字节,注意循环步进是i+=2,意思是每两个字节合为一个uint,并和2047进行位与运算(其实就是和2048求余),得到一个小于2048的值b,这个值b就是一个索引(index),表示在Bloom过滤器中的位置下标,也就是Bloom[b]的值为1。所以前6个字节生成了三个下标,共同表示此值是否在Bloom过滤器中。所以如果它生成的三个下标都不都为1。就能100%保证此值不在过滤器中,如果都为1,也不一定保证在这个过滤器中,但我们就认为在了。这就是过滤器的特性.
3.将生成的三个下标值进行左位移和位或运算,将相应的下标值值为1,,得到的这个bigInt就是传入参数的bloom过滤器的索引(index)值.

三。LogsBloom算法

这个方法就很简单了,该方法就是把Log的合约地址(Address)和Topics分别转为相应的下标值(bloom9值),然后分别将相应的下标值进行位或操作。这样就将他们的值都存在了一个数据里面。最后在函数CreateBloom()中将这个数据转为了2048位的Bloom类型的值。
所以此Bloom过滤器只是一个相应数据的标志器,用于判断某个数据是否存在里面的工具,本身不包括任何数据

四。如何判断一个数据(BloomLookup)

我们知道了Bloom中的内容并不包含相应的数据,所以判断一个数据的存在不存在,并不是查找相应的数据,而且将相应的数据索引化(bloom9)后的下标值在Bloom中的位置的值是否全为1。但以太坊的BloomLookup提供了另一个思路:

  1. func BloomLookup(bin Bloom, topic bytesBacked) bool {
  2. bloom := bin.Big()
  3. cmp := bloom9(topic.Bytes())
  4. return bloom.And(bloom, cmp).Cmp(cmp) == 0
  5. }

通过源码可以看到其判断流程为:

1.先将传入的数据转成bloom9值cmp
2.将Bloom过滤器转为Big.Int然后和cmp进行位与运算
3.将位与后的值和cmp比较是否相等,如果相等表示存在
  1. func bloomFilter(bloom types.Bloom, addresses []common.Address, topics [][]common.Hash) bool {
  2. if len(addresses) > 0 {
  3. var included bool
  4. for _, addr := range addresses {
  5. if types.BloomLookup(bloom, addr) {
  6. included = true
  7. break
  8. }
  9. }
  10. if !included {
  11. return false
  12. }
  13. }
  14. for _, sub := range topics {
  15. included := len(sub) == 0 // empty rule set == wildcard
  16. for _, topic := range sub {
  17. if types.BloomLookup(bloom, topic) {
  18. included = true
  19. break
  20. }
  21. }
  22. if !included {
  23. return false
  24. }
  25. }
  26. return true
  27. }

这个bloomFilter方法就是一个使用示例,这个函数的功能就是:

1.判断是否存在某些合约(addresses),如果不存在,直接返回false,就不用判断topics了。因为topics就是某个合约的转账过程的账户地址,没有合约,当然也就没有topics了
2.如果存在某些合约,就查找是否存在某些账户(topic)。

这就是布隆过滤器的使用方式和原理了 。

OK,这篇我们就先介绍到这里,让大家了解以太坊中区块头的Bloom字段的作用就是根据合约地址和账户地址过滤以太坊日志的功能。方便用户可以查看自己感兴趣的日志。下面我们会逐步将这些内容铺开来介绍。

  • 分享 收藏
0 条评论
  • 这篇文章暂无评论,赶紧评论一下吧~