Proof of Transaction Existence

[crypto-perry]

I think you should expose some API that allows for generation of Merkle proofs for transactions inside a block.

[zeldovich]

Do you have a use case in mind?

Currently, validating the header requires knowing recent balances which requires processing all transactions to compute the balances.

[crypto-perry]

Hi,

Thanks for such a quick reply. I think I explained badly what I want. I just need a simple goal command so that users can easily create a merkle branch proof that shows that a certain transaction was included in the main network. I will only keep the block hashes in an ethereum smart contract and people can submit these merkle proofs to the smartcontract to inform it of payments on the algorand mainnet and the smart contract will consequently verify that the proof indeed leads to a correct block hash and then pay ether or take other actions. This can be used for cross chain trading, proof of existence for some document. Frankly this functionality seems so important that maybe you already have it but I couldnt find it. If so can you point me in the right direction pls?

Or am I misunderstanding something fundamental about the algorand network which makes my described use case not suitable? To be honest I dont have a very deep understanding because I just couldnt find enough info on in the whitepaper and it took me some time to navigate the go code comfortably. Sorry if my request doesnt make sense :))))

From what I see the merkle package has the functionality for creating a merkle branch. I guess it's just a matter of tying this together with the blockheader and serializing the data nicely so that proof verifiers written in smart contracts can decode this.

[zeldovich]

Interesting -- thanks for elaborating. What are your thoughts about how your Ethereum smart contract might verify the block hashes? Are you thinking the Ethereum smart contract has the key of some oracle (e.g., you) baked in, and this oracle is trusted by the smart contract to sign only the hashes of real Algorand blocks?

[crypto-perry]

Exactly yes and I am sure the code is simple if I would understand go. I think the proof just needs to contain: transaction (without any signature), merkle branch from transaction ID to txnRoot, and the blockheader which contains this txnRoot. I am just not sure where I would add this functionality. If you can describe a bit where do you think this would fit (goal command or something else?) I can do a PR.

[zeldovich]

If the Ethereum smart contract trusts the oracle supplying this information, then it seems like this can all be done without changing Algorand blocks themselves. The oracle can compute a Merkle tree containing transaction IDs, and submit the roots of that Merkle tree over time to the contract.

Algorand used to have code (probably pre-v1-release) for exactly the kind of Merkle tree you are describing, but we took it out, since it seems like most use cases (like the one you described) require trusting a third party (the oracle) anyway, and that oracle can construct a Merkle tree of its choosing, without having this be baked into the Algorand block format. It would make sense to add the Merkle tree back once Algorand supports more lightweight verification of block headers (i.e., roughly, if it's sensible to have the Ethereum smart contract verify the block headers directly without having to trust the oracle).

Adding a transaction Merkle root is a somewhat complex procedure because it changes the meaning of a block, so the participating nodes need to switch to a new protocol at the same time so that they can accept and verify the Merkle root hash in a block.

[crypto-perry]

Oh okay, I was under the impression that algorand block headers already have the merkle root of all transactions in the block. Is that wrong? What is this (

go-algorand/data/bookkeeping/block.go

Line 53 in c3edcdc

TxnRoot crypto.Digest `codec:"txn"`

) parameter then?

[zeldovich]

TxnRoot is the hash of all transaction IDs in the block: https://github.com/algorand/go-algorand/blob/master/data/transactions/aggregates.go#L40

So a proof of transaction existence would be the list of all transaction IDs from that transaction's block, so that the entire list can be verified against TxnRoot of that block (assuming that the verifier already knows the right block header for that round).

[crypto-perry]

but the comment directly above that field says: "More specifically, it's the root of a merkle tree whose leaves are the block's Txids." Is this comment incorrect or am I just very confused? :))))

[zeldovich]

Yup, that comment is incorrect.

[crypto-perry]

Ok I see, but still giving all the txids (plus the full contents of the transaction we care about) for an algorand block is not that much data as from what I can see in the algoexplorer blocks only have a few transactions. Or is this something that will change as the network scales?

I don't want to keep the txnRoots themselves because I want to make it very easy for users to cross check the block hash and on algoexplorer the txnRoot doesn't appear.

[crypto-perry]

Btw, why was this decision taken? I don't quite see the drawback of using merkle trees... Is it just because the blocks are very small so it's not needed?

[zeldovich]

Ok I see, but still giving all the txids (plus the full contents of the transaction we care about) for an algorand block is not that much data as from what I can see in the algoexplorer blocks only have a few transactions. Or is this something that will change as the network scales?

Certainly right now the proof size would be pretty small since there aren't very many transactions in blocks. If blocks were full, there would be about 5000 transactions in a block. Since each transaction ID is 32 bytes, that means the proof would be 32*5000=160KB in size in the worst case.

I don't want to keep the txnRoots themselves because I want to make it very easy for users to cross check the block hash and on algoexplorer the txnRoot doesn't appear.

I don't understand what you're saying. If you want users to check for transaction validity using algoexplorer, why not just look up the txid on algoexplorer?

[ian-algorand]

Thanks for the discussion! I'm going to close this unless we can find a specific use case in the support of near-term development.