Bloom Filter :: Extend bloom to inject a block

[darrenvechain]

As a developer, I want to pass an ExtendedBlock into bloom so that I can check for addresses

The current bloom filter is generic and hard to use. I would propose extending it to accept an expanded block (or the outputs of an expanded block) ie.:

const block = await blocks.getBlock("best", {expanded: true})

const bloom = new BlockBloom(block)

const isMembor = bloom.containsAddress("myAddress")

console.log(isMember)

[pierobassa]

@darrenvechain is the idea to construct a bloom filter looking at the outputs of each transaction?

Here is an example of the response of the block endpoint with expanded: true

{
  "number": 17229578,
  "id": "0x0106e70ac5e7a11f0d508a0f5dc5916e7e0bc837e4de4f79c9cfbef6a702ea32",
  "size": 1255,
  "parentID": "0x0106e7096f12cedd83f4922791599ac90fadc054d796e4a47581e8726cb4c369",
  "timestamp": 1702821970,
  "gasLimit": 30000000,
  "beneficiary": "0x1eef8963e1222417af4dac0d98553abddb4a76b5",
  "gasUsed": 290302,
  "totalScore": 1680196497,
  "txsRoot": "0xcbe8f25d8ef87a2d2664157d9df8872ec9840584423d2e327d7f31b697865164",
  "txsFeatures": 1,
  "stateRoot": "0xbe07b1207976cadcdaff95bf4bca52c7f856e13711be9dcc1f4804001b0ff58b",
  "receiptsRoot": "0x2a6f43d81cc422a6daf359b28c9e696c94b7246f9052c3ddbff523bc3ef4cbb7",
  "com": true,
  "signer": "0x6298c7a54720febdefd741d0899d287c70954c68",
  "isTrunk": true,
  "isFinalized": false,
  "transactions": [
    {
      "id": "0x9c2964962df2e2f9e6f378726d47df7c7a948dd98112043c838185f74c6a4e2f",
      "chainTag": 74,
      "blockRef": "0x0106e7096f12cedd",
      "expiration": 32,
      "clauses": [
        {
          "to": "0x576da7124c7bb65a692d95848276367e5a844d95",
          "value": "0x1043561a8829300000",
          "data": "0x7ff36ab50000000000000000000000000000000000000000000002394e270e08364000000000000000000000000000000000000000000000000000000000000000000080000000000000000000000000a416bdda32b00e218f08ace220bab512c863ff2f00000000000000000000000000000000000000000000000000000000657f0433000000000000000000000000000000000000000000000000000000000000000200000000000000000000000045429a2255e7248e57fce99e7239aed3f84b7a530000000000000000000000005db3c8a942333f6468176a870db36eef120a34dc"
        }
      ],
      "gasPriceCoef": 255,
      "gas": 253631,
      "origin": "0xa416bdda32b00e218f08ace220bab512c863ff2f",
      "delegator": null,
      "nonce": "0x2603c69707b46b55",
      "dependsOn": null,
      "size": 365,
      "gasUsed": 223631,
      "gasPayer": "0xa416bdda32b00e218f08ace220bab512c863ff2f",
      "paid": "0x3e11f0316b4ec000",
      "reward": "0x129efb420697a000",
      "reverted": false,
      "outputs": [
        {
          "contractAddress": null,
          "events": [
            {
              "address": "0x45429a2255e7248e57fce99e7239aed3f84b7a53",
              "topics": [
                "0xe1fffcc4923d04b559f4d29a8bfc6cda04eb5b0d3c460751c2402c5c5cc9109c",
                "0x000000000000000000000000576da7124c7bb65a692d95848276367e5a844d95"
              ],
              "data": "0x00000000000000000000000000000000000000000000001043561a8829300000"
            },
            {
              "address": "0x45429a2255e7248e57fce99e7239aed3f84b7a53",
              "topics": [
                "0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef",
                "0x000000000000000000000000576da7124c7bb65a692d95848276367e5a844d95",
                "0x0000000000000000000000001a8abd6d5627eb26ad71c0c7ae5224cdc640faf3"
              ],
              "data": "0x00000000000000000000000000000000000000000000001043561a8829300000"
            },
            {
              "address": "0x5db3c8a942333f6468176a870db36eef120a34dc",
              "topics": [
                "0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef",
                "0x0000000000000000000000001a8abd6d5627eb26ad71c0c7ae5224cdc640faf3",
                "0x000000000000000000000000a416bdda32b00e218f08ace220bab512c863ff2f"
              ],
              "data": "0x00000000000000000000000000000000000000000000023b04b1d40b515745aa"
            },
            {
              "address": "0x1a8abd6d5627eb26ad71c0c7ae5224cdc640faf3",
              "topics": [
                "0x1c411e9a96e071241c2f21f7726b17ae89e3cab4c78be50e062b03a9fffbbad1"
              ],
              "data": "0x000000000000000000000000000000000000000000002f87e3cb2aaf503b96140000000000000000000000000000000000000000000687a8d57a3a1d0de7f46c"
            },
            {
              "address": "0x1a8abd6d5627eb26ad71c0c7ae5224cdc640faf3",
              "topics": [
                "0xd78ad95fa46c994b6551d0da85fc275fe613ce37657fb8d5e3d130840159d822",
                "0x000000000000000000000000576da7124c7bb65a692d95848276367e5a844d95",
                "0x000000000000000000000000a416bdda32b00e218f08ace220bab512c863ff2f"
              ],
              "data": "0x00000000000000000000000000000000000000000000001043561a88293000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000023b04b1d40b515745aa"
            }
          ],
          "transfers": [
            {
              "sender": "0xa416bdda32b00e218f08ace220bab512c863ff2f",
              "recipient": "0x576da7124c7bb65a692d95848276367e5a844d95",
              "amount": "0x1043561a8829300000"
            },
            {
              "sender": "0x576da7124c7bb65a692d95848276367e5a844d95",
              "recipient": "0x45429a2255e7248e57fce99e7239aed3f84b7a53",
              "amount": "0x1043561a8829300000"
            }
          ]
        }
      ]
    },
    {
      "id": "0x3e15b509f2109a60c3f1cfdb198b59b46d4792b777333119e819e11b69a190d8",
      "chainTag": 74,
      "blockRef": "0x0106e7096f12cedd",
      "expiration": 720,
      "clauses": [
        {
          "to": "0x23a46368e4acc7bb2fe0afeb054def51ec56aa74",
          "value": "0xac576e2a31c35a0000",
          "data": "0x000000606060"
        }
      ],
      "gasPriceCoef": 128,
      "gas": 29000,
      "origin": "0xbeae4bef0121f11d269aedf6adb227259d4314ad",
      "delegator": "0xbeae4bef0121f11d269aedf6adb227259d4314ad",
      "nonce": "0x33f2b93",
      "dependsOn": null,
      "size": 200,
      "gasUsed": 21216,
      "gasPayer": "0xbeae4bef0121f11d269aedf6adb227259d4314ad",
      "paid": "0x46c17f1958beae0",
      "reward": "0x153a0c879a9f9a9",
      "reverted": false,
      "outputs": [
        {
          "contractAddress": null,
          "events": [],
          "transfers": [
            {
              "sender": "0xbeae4bef0121f11d269aedf6adb227259d4314ad",
              "recipient": "0x23a46368e4acc7bb2fe0afeb054def51ec56aa74",
              "amount": "0xac576e2a31c35a0000"
            }
          ]
        }
      ]
    },
    {
      "id": "0x09804e17727ca0bee6521ae50e15653a8770edade8ac0e36bdda646e09af9c13",
      "chainTag": 74,
      "blockRef": "0x0106e7096f12cedd",
      "expiration": 720,
      "clauses": [
        {
          "to": "0x0000000000000000000000000000456e65726779",
          "value": "0x0",
          "data": "0xa9059cbb00000000000000000000000031437d38b38a5cb28dacb0379dbf0b5185e10643000000000000000000000000000000000000000000fbf26224799870e5280000"
        }
      ],
      "gasPriceCoef": 10,
      "gas": 31990,
      "origin": "0x95fe74d1ae072ee45bdb09879a157364e5341565",
      "delegator": null,
      "nonce": "0x4b129bf90751676e",
      "dependsOn": null,
      "size": 193,
      "gasUsed": 24455,
      "gasPayer": "0x95fe74d1ae072ee45bdb09879a157364e5341565",
      "paid": "0x386e3296e67232f",
      "reward": "0x10eddbfa11ef0f4",
      "reverted": true,
      "outputs": []
    },
    {
      "id": "0xab4c2867d90f6ea27e8eac6b180ca43c267be82593ac15aa801bf70de7301354",
      "chainTag": 74,
      "blockRef": "0x0106e7096f12cedd",
      "expiration": 720,
      "clauses": [
        {
          "to": "0xb7591602c0c9d525bc3a7cf3c729fd91b8bf5bf6",
          "value": "0xe18cc1b1e0e8c20000",
          "data": "0x"
        }
      ],
      "gasPriceCoef": 0,
      "gas": 21000,
      "origin": "0x9a107a75cff525b033a3e53cadafe3d193b570ec",
      "delegator": null,
      "nonce": "0x7bced3146d8fb8fc",
      "dependsOn": null,
      "size": 131,
      "gasUsed": 21000,
      "gasPayer": "0x9a107a75cff525b033a3e53cadafe3d193b570ec",
      "paid": "0x2ea11e32ad50000",
      "reward": "0xdfd22a8cd98000",
      "reverted": false,
      "outputs": [
        {
          "contractAddress": null,
          "events": [],
          "transfers": [
            {
              "sender": "0x9a107a75cff525b033a3e53cadafe3d193b570ec",
              "recipient": "0xb7591602c0c9d525bc3a7cf3c729fd91b8bf5bf6",
              "amount": "0xe18cc1b1e0e8c20000"
            }
          ]
        }
      ]
    }
  ]
}

For VET transfers it's easily checked for the transfers array. For Token Transfers or any address involved in a smart contract function we need to decode the events emitted against known Event signatures (like VIP180 transfers, UniswapV2/V3 swaps, VIP180 approvals...etc)

[darrenvechain]

Ya if you look at the thor code base, you can see which parts of txs / blocks get added to the beat2 bloom

[darrenvechain]

[pierobassa]

Nice! Makes sense @darrenvechain

[lucanicoladebiasi]

Working on branch at
https://github.com/vechain/vechain-sdk-js/tree/369-bloom-filter-extend-bloom-to-inject-a-block

Hash functions secured in

• packages/core/src/hash/blake2b256.ts
• packages/core/src/hash/keccak256.ts
• packages/core/src/hash/sha256.ts

[lucanicoladebiasi]

The logic is to derive the Bloom's filter from the addresses described in the properties of ExpandedBlockDetail in packages/network/src/thor-client/blocks/types.d.ts.

The SDK should provide two methods in packages/core/src/utils/bloom/bloom.ts or packages/core/src/bloom/bloom.ts

• accepting `ExpandedBlockDetail`` and returning the Bloom's filter expression,
• accepting a Bloom's filter expression and an address returning if the address possibly belongs to the set of addresses (partially done in packages/core/src/utils/bloom/bloom.ts).

[lucanicoladebiasi]

For ExpandedBlockDetail, the properties referring addresses are

• beneficiary: string;
• signer: string;
• transactions: TransactionsExpandedBlockDetail[];
  • clauses: Clause[];
    • to: string | null;
  • delegator: string;
  • gasPayer: string;
  • origin: string;
  • outputs: Output[];
    • contractAddress: string | null;
    • events: Event[];
      • address: string;
    • transfers: Transfer[];
      • recipient: string;
      • sender: string;

---

IMPORTANT

Since addresses are hexadecimal expressions but those can be expressed in the checksummed format described in ethereum/EIPs#55, its is mandatory the Bloom's filter is build on the base of the byte array of the hexadecimal expression of addresses.

[lucanicoladebiasi]

Pure and secure code.

The packages/core/src/utils/bloom/bloom.ts provides the filterOf method to build the Bloom filter from any array of Thor addresses, filtering out strings those are Thor addresses (like empty strings) and duplicates to let the bloom filters to be consistent the same addresses shared by different blocks using where the addresses are values of different properties.
However I suspect it is limiting to provide the functionality to build the Bloom filter just from a block instance, hence I extended the concept, filterOf accepts any array of addresses in any form, to easily combine multiple blocks in one filter.

The method addressesOf scans the (extended) block for addresses, this is the helper function used to provide what required by the ticket because the solution provided is

bloomUtils.filterOf(bloomUtils.addressesOf(expandedBlockDetail));

assuming some default parameters are set, see below.

Unfortunately two Bloom filters derived by blocks are useless if the k (hash functions) or m (bits per keys) are different, those are not comparable. In our SDK the Bloom filter is just an array of bytes, it hasn't the k or m properties.
I didn't take the decision to include them to make filters to be comparable, albeit this is something is worth to think if important (and trivial) to introduce.

To test the same address against different filters from different blocks - those must have k and m in common - I introduced in packages/core/src/bloom/bloom.ts the function calculateBitsPerKey reciprocal of calculateK to help.

Because what above, after some mathematic experimentation, I derived k = 5 as default parameter for filterOf to allow the filter to compress the set of represented addresses of 20 times with a probability of collision far smaller than 1%, in average all addresses in a block of Thor solo are encoded in 14 bytes with no false positive experienced. However this assumption is related with the real number of addresses per block typical of the real Thor and I have no guess about.

However since we do not provides any mean to derive k and m from Thor addresses, and the Filter class do not represent them, to make bloomUtil.filterOf practically usable without math mumbling, I introduced the constant 'BLOOM_DEFAULT_K = 5` to let users to build comparable Blom filters from extended block without any knowledge of the backing math.