solana-labs / solana

Web-Scale Blockchain for fast, secure, scalable, decentralized apps and marketplaces.
https://solanalabs.com
Apache License 2.0
13.37k stars 4.36k forks source link

Block vote aggregation #4809

Open t-nelson opened 5 years ago

t-nelson commented 5 years ago

This is a sub-issue of #4808 (SPV)

Since verifying PoH is a resource intensive activity, requiring light clients to perform this task should be avoided. As such, they will need an alternate means of confirming that the block Merkle Roots that their trusted fullnode provides are included in the ledger. This can be done by delivering the block's vote state along with its header and letting the light client verify that a sufficient number of their preferred validators have voted on it. In an effort to reduce network overhead the minimal vote state should be transmitted, either by sending only an interesting subset of votes or better, by using a signature aggregation scheme.

I'm still developing the plan of attack here it should come into focus as the first three items progress

Bold entries are in active development.

t-nelson commented 5 years ago

@aeyakovenko would there be any side effects to making this hash an actual sig?

https://github.com/solana-labs/solana/blob/af1c70f0323250bec2a94f37dd80014e97d26b2a/programs/vote_api/src/vote_state.rs#L28-L30

aeyakovenko commented 5 years ago

I think we only need 1 hash of the bank. Not 1 per validator

rob-solana commented 5 years ago

@aeyakovenko I'm not following

@t-nelson who'd sign? the node, the vote signer? side effects would be limited to vote verification, the signature would have to be decrypted before comparing against slot_hashes

aeyakovenko commented 5 years ago

@t-nelson are you trying to get the successful vote signatures from the bank to avoid looking through blocktree?

t-nelson commented 5 years ago

@rob-solana Yeah, the voter.

Alternative could be to add a signature.

@aeyakovenko Idea is to have an aggregat-able signature over the vote data somewhere that the bank can pluck out and add to an aggregate signature for the block.

Talking to @garious yesterday though, a separate vote transaction format would also do the trick. The goal being to isolate vote data from the instruction stream

aeyakovenko commented 5 years ago

@t-nelson what about looking for the vote program id through blocktree transactions?

t-nelson commented 5 years ago

@aeyakovenko that may be possible. We'll still need a signature over common vote message data (perhaps with a pubkey prefix) for aggregation. I was hoping to give @rob-solana his VoteEntrys and further embed the SPV proof in consensus.

Working mental model for that is currently something like

struct VoteEntryItem {
    height: u64,
    poh: Hash,
    sig: TBDAggregateSignature,
}

struct VoteEntry(Vec<VoteEntryItem>);
aeyakovenko commented 5 years ago

@t-nelson can we do the aggregation in post processing?

I think you might need to start recording the program error bit into blocktree as well.

t-nelson commented 5 years ago

@aeyakovenko I think we would have to define when post is first.

I'd like to use incremental aggregation. The leader tracks votes it sees during its slot and emits a single VoteEntry with all of the signatures that changed since the last VoteEntry

RE program error bit: I still need to look into how transaction failures are typically notified with SPV. AFAIK they aren't typically encoded in the ledger. A node that saw the TX may keep a failure report around for awhile, but eventually it'd be pruned and "Transaction not found" encodes the same info. I know storage is cheap on Solana, so diverging from the norm may be an acceptable solution. I'd like to better inform myself before drawing a conclusion though

aeyakovenko commented 5 years ago

@t-nelson a transaction that executed the program pays the fee, even if the program throws an error.

t-nelson commented 5 years ago

@aeyakovenko Yes and that's fine. I just haven't really considered this aspect as thoroughly as I'd like.

It seems like there's more to it than a little storage overhead. Encoding the result in the ledger means things like every validator needs to actually execute every failed TX before they can vote on the including block, which implies failed TXs need to be broadcast to every validator, etc

aeyakovenko commented 5 years ago

@t-nelson they are not “failed” since they payed a fee. Just the program decided to abort.

jon-chuang commented 4 years ago

I am interested in this issue. Specifically, BLS signature-aggregation. What's the current status?