search

Phoneword / phoneword

This is an application that interfaces metamask with webrtc to allow for tokens to be sent during a video call. This will later be bridged to IPFS. This is the nodejs implementation of web3js.
3 stars 0 forks source link

Look into bloom filters for ethereum #11

Closed jaycenhorton closed 7 years ago

jaycenhorton commented 7 years ago

Is there a way to store/register numbers in Ethereum blockchain using bloom filters

jaycenhorton commented 7 years ago

Closing in favor of storing the ipns lookup hash of the merkle patricia radix trie format in ipfs. @xioustic can you see any implementation path where bloom filters might be useful? The way I imagine this working, at least initially, is just storing the ipns hash in the smart contract as a callable (tx cost-free) lookup function that just returns the ipns hash of the phoneword ipfs master registry (or maybe an array of ipns hashes down the road).

For any later references to this issue, note the following was helpful when looking into bloom filter possibilities : https://github.com/ethereum/wiki/wiki/Design-Rationale#trie-usage https://www.youtube.com/watch?v=qBTdukbzc78

xioustic commented 7 years ago

My original idea was to create an empty bloom filter initially, or perhaps an array of them, inside the Ethereum smart contract state. This would allow the Ethereum smart contract state complete independence for the most basic phoneword "claim" functionality in the case the other blockchain is under maintenance or otherwise broken.

The bloom filter can only return a "definitely not" or a "maybe", so we could actually allow Ethereum accounts to change phone number state using a combination of bloom filters each representing the state of all numbers. In a failing scenario, the number is either invalid for the change per existence in the bloom filter or there's a statistical failure and the change is invalid incorrectly, but this can be rectified on the Phoneword chain since that will be the definitive source of truth. In a succesful scenario, the account making the claim would be effectively opening a sparse transaction owned by the Ethereum address which could later be referenced inside the Phoneword chain.

This would change the Ethereum chain interaction from "update IPNS hash" to "update IPNS hash and change/merge current number state into the bloom filter(s)".

This gives us a decent side-chain for almost binary state machines actually... I wonder if it has been thought of before? You couldn't track balances (integers) or individual ownership (ie accounts) or pointers (what the number should point at, since that requires knowing ownership), but you could track simple enumerable states (claimed,unclaimed,disputed,etc) for a near unlimited number of deterministic buckets with a definable statistical failure rate. That's probably why it isn't used; we have a unique situation where we have definable determinstic buckets in that there's a limited number (ie 15 digit numbers).

All things considered, this is probably needlessly complicated for a problem/solution that isn't that important to solve, especially in the early stages.

-------- Original Message -------- Subject: Re: [Phoneword/phoneword] Look into bloom filters for ethereum (#11) Local Time: August 19, 2017 9:42 PM UTC Time: August 20, 2017 4:42 AM From: notifications@github.com To: Phoneword/phoneword phoneword@noreply.github.com Christian Ferrier xioustic@gmail.com, Mention mention@noreply.github.com

Closing in favor of storing the ipns lookup hash of the merkle patricia radix trie format in ipfs. @xioustic can you see any implementation path where bloom filters might be useful? The way I imagine this working, at least initially, is just storing the ipns hash in the smart contract as a callable (tx cost-free) lookup function that just returns the ipns hash of the phoneword ipfs master registry (or maybe an array of ipns hashes down the road).

For any later references to this issue, note the following was helpful when looking into bloom filter possibilities : https://github.com/ethereum/wiki/wiki/Design-Rationale#trie-usage https://www.youtube.com/watch?v=qBTdukbzc78

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

jaycenhorton commented 7 years ago

The only case i know of where ethereum uses bloom filters is in the case of light clients. https://github.com/ethereum/wiki/wiki/Light-client-protocol#principles

What you're saying is a good idea, however it would reintroduce a tx cost (or additional tx cost) where the bloom filter in the smart contract would need to be updated. I think any bloom filter of reliable size of bits for a 15 digit number would be far too expensive to update. Thoughts? see here for example storage costs in a smart contract (256 bit = $0.18 for example )https://docs.google.com/spreadsheets/d/1KeWKkn0BYhOt1p6lM6BDQAWLin-2JQmGpwswU3kPw9c/edit#gid=0

https://hackernoon.com/ether-purchase-power-df40a38c5a2f

jaycenhorton commented 7 years ago

https://docs.google.com/spreadsheets/d/1n6mRqkBz3iWcOlRem_mO09GtSKEKrAsfO7Frgx18pNU/edit#gid=0

jaycenhorton commented 7 years ago

@xioustic Note on the above costs: any transaction invoking sendTransaction costs gas where the computation updates some state or performs some actual calculation inside the evm where all nodes necessarily execute all code always. You can however "call" functions existing within smart contracts where the execution costs no gas as it executes the functionality locally and does not store or broadcast any computation to be executed by other nodes. If you think there might be a way to update the bloom filter in a non cost-prohibitive way, it may be possible to use the bloom filter idea mentioned above.

I cannot, off the top of my head, think of a way which this could be done, unless the bloom filter is stored into the contract base state, then users who want to register a phoneword call a lookup function to get the bloomfilter, check availability of the phoneword (with whatever percentage of false positives), but only update the bloom filter at the time where they want to register their phoneword and sendTransaction(phonewordToRegister) where they are charged the fee to then update the bloomfilter. This may be quicker and more effective than traversing the ipfs trie when just looking up directly from the ipfs tire. I.E:

RegistryContract:

PhonewordApplication:

Flow: const PHONEWORD = "1-800-Hollywood"); const PHONEWORD_BLOOM = convertToBitsForBloom(PHONEWORD );

(Register PHONEWORD )->{ existsInBloom(getPhonewordBloom(), PHONEWORD_BLOOM ) }-false?->[ updatePhonewordTrie(getIPNSOfRegistry(),PHONEWORD, 2100, 1000000) ]->[ updatePhonewordBloom(PHONEWORD_BLOOM) ]->[ ipfs.object.patch(PHONEWORD) ]->[forwardFeeToRegistrar(1000000, registrar[0])

Result: Updated trie, updated bloom, user charged gas fee for updating bloom, user forwards fee to registrar account, registrar gets fee

xioustic commented 7 years ago

You've got the right idea with your last comment.

As to whether we need a lot of bits, I'm not sure. I know Redis does something like (for hyperloglog, which I think is a more heavyweight bloom filter that tracks cardinality?) 12kB for arbitrary inputs with less than 1% of error: "In the Redis implementation it only uses 12kbytes per key to count with a standard error of 0.81%, and there is no limit to the number of items you can count, unless you approach 2^64 items (which seems quite unlikely)." I have no idea if 12kb is expensive in the Ethereum chain, but if we do math on the figure you give: 12kB / 256 bit = 375; 375 * $.18 = $67.50. This implies cost prohibitive.

To implement this native to the Ethereum we need the ability to hash an input (ie a phone number) and then XOR the result with the bloom filter. If the XOR has an effect (ie some bit has flipped), then the number has not yet been added to the filter, we can give them a "receipt"/"token"/"ticket" for the action, and then we replace the bloom byte array with the new XOR'd one. The "receipt"/"token"/"ticket" could give them "first-dibs" on the IPFS chain. So we incur a cost when someone registers a number this way or we push an update, and we incur no cost when a register via bloom filter check fails (since this is discovered locally).

Note that the IPFS chain would thus be dependent on having current state of the Ethereum chain before pushing a new state; it would want to know any-and-all unfulfilled "tickets" issued via this method before making any assumption about incoming transactions. I think it becomes important that the Ethereum "tickets" take precedence.

It would be nice to do the entire system like this save for the statistical error introduced and the cost.

Whether or not this is useful now or in the future I am not sure, so it's probably a good idea to close it for now.

Sent from ProtonMail, encrypted email based in Switzerland.

-------- Original Message -------- Subject: Re: [Phoneword/phoneword] Look into bloom filters for ethereum (#11) Local Time: August 20, 2017 5:02 PM UTC Time: August 21, 2017 12:02 AM From: notifications@github.com To: Phoneword/phoneword phoneword@noreply.github.com Christian Ferrier xioustic@gmail.com, Mention mention@noreply.github.com

@xioustic Note on the above costs: any transaction invoking sendTransaction costs gas where the computation updates some state or performs some actual calculation inside the evm where all nodes necessarily execute all code always. You can however "call" functions existing within smart contracts where the execution costs no gas as it executes the functionality locally and does not store or broadcast any computation to be executed by other nodes. If you think there might be a way to update the bloom filter in a non cost-prohibitive way, it may be possible to use the bloom filter idea mentioned above.

I cannot, off the top of my head, think of a way which this could be done, unless the bloom filter is stored into the contract base state, then users who want to register a phoneword call a lookup function to get the bloomfilter, check availability of the phoneword (with whatever percentage of false positives), but only update the bloom filter at the time where they want to register their phoneword and sendTransaction(phonewordToRegister) where they are charged the fee to then update the bloomfilter. This may be quicker and more effective than traversing the ipfs trie when just looking up directly from the ipfs tire. I.E:

RegistryContract:

  • IPNS_HASH: Hex

phonewordBloom: bits[]

  • getIPNSOfRegistry(): (Hex : IPNS_HASH) : callable
  • getPhonewordBloom(): (bits[]: phonewordBloom): callable
  • existsInBloom( phonewordBloom: bits[], phoneword: string ): Boolean : callable
  • updatePhonewordBloom(phoneword: String): Boolean : tx-required

PhonewordApplication:

  • convertToBitsForBloom( phoneword: String): bits[]
  • updatePhonewordTrie( getIPNSOfRegistry: Hex, phoneword: String, gas: Wei, registrationFee: Wei ): Boolean : updates ipns registry (off-chain, ipfs), updates phonewordBloom (with gas), gives registrar the registrationFee (eth in Wei)

Flow: const PHONEWORD = "1-800-Hollywood"); const PHONEWORD_BLOOM = convertToBitsForBloom(PHONEWORD );

(Register PHONEWORD )->{ existsInBloom(getPhonewordBloom(), PHONEWORD_BLOOM ) }-false?->[ updatePhonewordTrie(getIPNSOfRegistry(),PHONEWORD, 2100, 1000000) ]->[ updatePhonewordBloom(PHONEWORD_BLOOM) ]->[ ipfs.object.patch(PHONEWORD) ]

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

jaycenhorton commented 7 years ago

Right, let's discuss possibilities of implementing this in the future when we meet next in person, and then we can clear it from the board.