A suggestion for a light-client wallet (like the BTC SPV wallet with Merkle tree)

We suggest that the team or volunteers create a light client wallet, because the data volume will explosively increase after the ASA is adapted, as a result more and more users will not run a full-data node.

A possible solution might be a SPV wallet, which is being used in BTC, based on Merkle tree. I do not know if there is a merkle tree included in the ALGO block header. If there is, we may refer to BTC wallet.

The advance of such a SPV wallet is that, the wallet owner can control their own private keys, sign locally and have the source code.

For example, https://bitcoin.org/en/wallets/desktop/windows/electrum/?step=5&platform=windows

In algorand network, the biggest relay nodes are trustable, so the light-client SPV wallets may refer to these relay nodes. It is even better than the case of BTC, where the referred full nodes need to be located randomly.

To do this we need to know whether there is a merkle tree in the block header or not. However, I have not found the documents about the block structure. It is said that maybe we have to wait for vaucet, which will implement a data storage layer for algorand.

If anyone know the how the data is organized in the block, please kindly paste the link here, and then maybe some professional people will create such a light-client wallet if there is a merkle tree.

Currently, block headers contain a flat hash (not a Merkle tree) of the transactions that appear in that block, but switching this to a Merkle tree would not be sufficient to allow for SPV.

For a precise (but rather dense) description of the structure of a block, you can check out the ledger specification at https://github.com/algorandfoundation/specs/tree/master/dev/ledger.md. Relevant to your question are sections 1.3 and 10.2.
(Here’s a compiled PDF version of the ledger spec, current as of 2019-11-21.)
It’s also worth looking at data/bookkeeping/block.go where Block is defined in the code.

Unfortunately SPV for Algorand is somewhat more complicated than it is for Bitcoin because of how the proof-of-stake works.
With Bitcoin, a full node can send an SPV node all the block headers, and the SPV node can check the proof of work to ensure that these are (probably) the correct block headers. Then the full node can send the SPV node a Merkle proof that a transaction appeared in a particular block, and the SPV node can check the proof against the block header it already has and knows is correct.

Algorand doesn’t use proof of work – if I send you all the block headers, that on its own isn’t enough for you to know whether any of the block headers are correct. Algorand agrees on blocks via a Byzantine consensus protocol – with each block, there’s a set of votes (called a certificate) that proves that that block is correct.

This on its own isn’t a problem – the full node can just send certificates along with the block headers. And this would be enough if Algorand voters weren’t weighted by stake but instead came from some fixed list known in advance. But Algorand is permissionless and weighted by stake – in order to verify a vote, you need to know the voter’s balance as of some round shortly before the vote. (For technical reasons, votes for round R are weighted by stake as of round R - 320)

In particular, a certificate for round R I send you can’t be verified unless you know the balances as of round R-320 and to know the correct balances in round R-320 you’d at the very least need to have block R-320. But to make sure you have the correct block R-320 you’ll need to verify its certificate, which requires knowing the balances in round R-640, and so on.

Since an SPV client wouldn’t want to download all the balances, we could make every block commit to that round’s balances in, say, a giant Merkle tree and put the commitment in the block header. (The balance tree needs to be efficiently updatable because recomputing a Merkle root of all balances in the system from scratch every block would be too slow, but there are ways of structuring the tree to make this possible.) Then we can include with every certificate the Merkle paths to the balances of the voters in that certificate.

This would help, but the bandwidth cost for the SPV client is still considerable – if the system has many accounts and Merkle paths are long, the added overhead of sending a Merkle path for every voter in a certificate is significant.

There are a few further optimizations that can further reduce the bandwidth cost; there are also a few complications that I’m ignoring in the above description. If you’re interested, this is what the Vault paper is about. (https://eprint.iacr.org/2018/269, see also slides at https://www.ndss-symposium.org/wp-content/uploads/ndss2019_09-2_Leung_slides.pdf) Vault goes a little bit further and also describes how to allow full participating nodes to store less than the full set of balances (“sharding”), but that part isn’t needed for SPV.

Again, because of the way we do proof-of-stake, some sort of bootstrapping process like this is fundamentally necessary – there’s no escaping the fact that you can’t trust a block header without already being able to trust a recent set of balances, and you can’t trust those balances without at least a trustworthy block header. So an SPV client needs to download and validate lots of certificates, and certificates are way larger than block headers. For Bitcoin, which is proof-of-work, it suffices to look only at block headers – no certificates, no efficiently-updatable commitments to the entire set of balances.

So yes, we definitely want to have an Electrum-like SPV client, but for us it’s inherently more complicated than for Bitcoin, so implementing it is going to be a decent amount of work.

2 Likes

@adam, Thank you very much. Your professional analysis help me much. I am going to read these documents and try to use them.

You can also use wallet.myalgo.com which is light weight and relays on Algoexplorer API, and it supports Ledger Nano S.

1 Like

/var/lib/algorand# ls -l
total 3082292
-rw-r–r-- 1 algorand algorand 935810534 Jan 1 11:17 agreement.cdv
-rw-r–r-- 1 algorand algorand 1073742650 Jan 1 10:00 agreement.cdv.archive
-rw------- 1 algorand algorand 0 Dec 17 09:06 algod.lock
-rw-r–r-- 1 algorand algorand 15 Dec 31 20:20 algod.net
-rw-r–r-- 1 algorand algorand 4 Dec 31 20:20 algod.pid
-rw-r–r-- 1 algorand algorand 64 Dec 17 09:06 algod.token
drwxr-xr-x 4 root root 4096 Dec 19 22:18 betanetdata
-rw-r–r-- 1 algorand algorand 1634 Dec 13 04:47 config.json.example
drwxrwxr-x 6 algorand algorand 4096 Dec 17 09:06 genesis
-rw-r–r-- 1 algorand algorand 24972 Dec 13 04:47 genesis.json
drwx------ 2 algorand algorand 4096 Dec 17 09:06 mainnet-v1.0
-rw-r–r-- 1 algorand algorand 1073741718 Jan 1 10:08 node.archive.log
-rw-r–r-- 1 algorand algorand 72881820 Jan 1 11:17 node.log
-rw-r–r-- 1 algorand algorand 23 Dec 13 04:47 system.json
drwxr-xr-x 4 root root 4096 Dec 19 22:18 testnetdata

~:/var/lib/algorand# ls mainnet-v1.0 -l
total 30516
-rw-r–r-- 1 algorand algorand 4096 Dec 17 09:06 crash.sqlite
-rw-r–r-- 1 algorand algorand 32768 Dec 31 20:20 crash.sqlite-shm
-rw-r–r-- 1 algorand algorand 8272 Dec 17 09:06 crash.sqlite-wal
-rw-r–r-- 1 algorand algorand 18640896 Jan 1 11:15 ledger.block.sqlite
-rw-r–r-- 1 algorand algorand 32768 Jan 1 11:19 ledger.block.sqlite-shm
-rw-r–r-- 1 algorand algorand 4350752 Jan 1 11:19 ledger.block.sqlite-wal
-rw-r–r-- 1 algorand algorand 3350528 Jan 1 10:59 ledger.tracker.sqlite
-rw-r–r-- 1 algorand algorand 32768 Jan 1 11:19 ledger.tracker.sqlite-shm
-rw-r–r-- 1 algorand algorand 4770992 Jan 1 11:19 ledger.tracker.sqlite-wal

The biggest files are agreement.cdv, agreement.cdv.archive,node.archive.log,node.log
and they increase as the time goes.

I guess, if the *.log files are deleted, it does not affect the algorand server.
Not sure agreement.cdv and agreement.cdv.archive. agreeemtn.cdv.archive seems a backup of agreement.cdv.

Now testing

(1) delete the file node.log and then reboot, the system generate node.log again, without node.log.archive which might be a backup of node.log

(2)backup the file agreement.cdv and agreement.cdv.archive, then delete them then reboot, the system generate agreement.cdv , without agreement.cdv.archive which might be generated later.

Thinking, maybe it is good to optionally download the log files, or prune them periodically.

@studyres @Richard @adam Hello guys, just wanted to hop on to this conversation, also hoping if the Algorand Team or any Algorand-based project considered this proposal and is working on something to make it possible. Any updates? It seems their is yet a light client feature and it is really troubling especially if you want to build any products on Algorand that work for users who predominantly use smartphones, microcontrollers etc., as well as hardcore crypto users who prefer something like a self-custody Bitcoin-like SPV-like wallet. So far building any wallet on Algorand needs you to use a centralized service provider, or using the walletconnect feature to assure your users of security, but this light client feature will open up other inclusive, innovative apps for niche users and grow the ecosystem.