What is Addressable mean?

It means the leaf node in the tree can be found by an address. The address encoded the path to the leaf node, for example, a leaf node in a binary tree, which has 3 level. Its address may be encoded to 010, the corresponding path is: left->right->left:

	0    1     0
	+    +     +
	v    v     v
left right left


		 root
		 / \
	 H1   H2
	/\     /\
D1  D2 D3 D4

As we can see, the address 010 leads us to the leaf node D2.

This may explain what a colleague told me about the lower the address we got the lower gas we cost.

How does AMT work?

The main goal of AMT is to let a verifier V can verify a large data structure D without holding it, which D provided by an untrusted prover P, which holds D.

  • P computes \(f(D) \rightarrow r\) and \(\pi\) to the verifier.

    Both:

    • \(r\) the result of the computation of some function \(f\) on \(D\)(e.g. SHA1).
    • \(\pi\) a proof of the correct computation of the result.

  • V can run \(Verify(a, f, r, \pi)\), which returns true if and only if \(f(D) = r\).

    • \(a\) holds by V is a short authenticator, forms a binding commitment to the large data structure D.

As above shown, this is a Merkle tree stroing \(D = \{0: s0, 1: s1, 2: s2, 3: s3\}\). If we want to verify the third item(at the bottom of the tree, from left to right, shown with a dashed line), then \(r = s2\) and \(\pi = [h3, h4]\)(shown with a dotted line). \(Verify(a, f, r, \pi)\) returns if and only if the result of below equals to a:

\(hash(h4 || hash(hash(2 || r) || h3))\)