search

EYBlockchain / timber

Construct a Merkle Tree database from Ethereum logs.
Other
67 stars 19 forks source link

Alternative solution for onchain proof recording #41

Closed chiro-hiro closed 3 years ago

chiro-hiro commented 3 years ago

I think, hash chain could do the same with cheaper gas cost.

I've a new proposal https://github.com/chiro-hiro/chainlink, please have look

Westlad commented 3 years ago

Hi @chiro-hiro Thanks for your interest! Remember that the purpose of Timber is to support ZKP proofs of set membership. To prove inclusion of the nth new leaf in your hash chain, I think you need to compute n hashes to get to the root. If n is (say) 1 million, that's quite a big proof. A Merkle tree proof is always just the height of the tree. Thus, while adding new leaves can be more efficient for a hash chain, the set membership proof size grows without limit. Thus, it may not be so well suited to our particular use case.

chiro-hiro commented 3 years ago

I think, you could calculate and store Merkel Tree off-chain. Meanwhile on-chain it has just been a hash chain. Just in case you failed to verify it off-chain you must fallback to hash chain computation. In the worst case, it's still O(n).

Westlad commented 3 years ago

The verification has to be on chain though otherwise the smart contract cannot verify that the proof is valid (unless you are taking an optimistic approach but that's a rather different scenario). I don't really understand how you can use a different accumulator on chain from the one you use in you proof.

chiro-hiro commented 3 years ago

In MerkleTreeSHA256, you can't verify any proof with your smart contract since it's only store most-right 'frontier' of the tree.

When you insert a new leaf, It will update all right frontier nodes and update the root. It cost you O(log2n) (height of Merkle Tree) to append a new leaf. In every step of computation MerkleTreeSHA256 will emit event with context of constructing Merkle Tree to outside of EVM.

The idea of Hash Chain just like blockchain, new node will contain previous node hash pointer that made Hash Chain immutable. It cost you O(1), to insert a new node (alternative to leaf definition). ChainLink is also emit context of constructing chain to outside of EVM.

In the worst case, both approach can't verify any proof on-chain. But Hash Chain cost less resource of EVM to archive the same thing that Merkle Tree is doing on-chain right now. It's maintenance "append only proof" that will be changed deterministically for each new leaf.

With the context from ChainLink smart contract you could verify n new nodes with the cost is O(n), since they were hashed by order.

In the off-chain side your could reconstruct a Merkle Tree from EVM's context.

Westlad commented 3 years ago

I'm talking about a Zero Knowledge proof, not a Merkle proof. You see, Timber is used with Nightfall. The Merkle path from leaf to root is an input to the ZK snark circuit and that proof, once computed, is verified on-chain. If you were to use a hash chain instead, then your ZK snark circuit would need to process a hash-chain path of increasing and large length, and would be much bigger in terms of constraints, to the point of impracticality. I don't dispute that you can add a leaf to a hash chain with less gas than a Merkle tree but that's not the only purpose of Timber.

iAmMichaelConnor commented 3 years ago

I'll close this issue, because of the compelling arguments to continue using a Merkle Tree. But please feel free to reopen, if there are further arguments in favour of this proposal.