Here is a mental experiment, a pseudo-protocol that could work except that some of the pieces either don't exist (that I know of) or they are too inefficient at scale.

💡This builds on the proposal here by Hong-Sheng.

It focuses on faster finality exclusively. This is not tackling our other concerns, namely unpredictable lottery and further neutrality/censorship-resistance.

Background

• BFT consensus, ultra-simplified, is about: 1) ensuring that everyone (2/3) has seen a proposal; 2) ensuring that everyone (2/3) agrees on that proposal. That tends to yield a 1/3 honest threshold for liveness and 2/3 honest threshold for safety. Again, generalizing a lot here.
• The liveness part is a key divergence between BFT and Nakamoto type of consensus. In Nakamoto, progress is being made because you don't need to wait for the “has seen” information to continue, thus unlocking unlimited liveness at the expense of partitions: if you continue building on what you have seen, it might be the case that what you have seen is not sufficient.
• Of course we could here do what many chains do (Polkadot, Ethereum…): throw BFT on top of the longest-chain consensus and give it priority. What this yields is BFT properties for the most part, but when there is a network partition or BFT can't finalize for some reason (generally a bug, like has happened in Ethereum for 1h+), the underlying chain-building can continue (even though without guarantees of finalization).
• This doesn't work for us, because:
  • BFT has innate scale limitations. It's message complexity is naturally high (consequence of the strict rounds of communications required to get signatures).
  • If we limit BFT to a committee (classic solution, like Algorand, Polkadot…) then we are open to bribery attacks. In short, we are giving temporary superpowers to a small group of nodes, partially undoing the benefits of having a large validator set.
  • BFT network patters are incompatible with stake privacy. We know it's inviable to hide that traffic with reasonable bandwidth consumption via network mixing.
  • BFT forces us to have a registration (staking) mechanism. We have gone to great lengths to avoid this precisely to make participation really easy, as in, allowing laptops to participate intermittently.

Integrating Hong-Sheng's ideas into Ouroboros

Here I'm continuing the reasoning above, and picking up some of Hong-Sheng's ideas.

• Nakamoto-type consensus (ie Ouroboros) embeds both “have seen” and “have confirmed” and probabilistically ensures this by asking the nodes to:
  • Wait long enough (though it's technically never long enough, specially in the case of partitions)
  • Gain some measure of what the other nodes think, in the form of their attestations by building on the fork (ie block) that they deem “correct".
• Note that this is akin to what Avalanche does, but Avalanche “inverts it”, by making nodes ask others, instead of just waiting for their beliefs to be expressed explicitly with their block proposals.
• The culprit of finality slowness is that this information comes to the network as a slow drip: we don't know the opinion of others until they slowly release it, block by block. This fundamental limitation is always going to be there, it's a matter of information bandwidth: we get a single bit per 1/20 slots on average.
• What if we can somehow compress all that information in one go? How would that look like? In principle, the naive way would be to ask every node to attest it with their stake attached to it (let’s imagine this is efficient):
  • Every block that is in the network, has a “stake weight” in it.
  • If a block obtains >3/4 of stake attestations, it can be considered finalized.
  • Privacy: can we make this private?
    • If we can make each attestation private via ZK (the network identity of the attester and the stake are unlinkable).
    • Problem: this puts a heavy burden in Blend Network, which would require now substantially more hops.
  • Scalability: is this scalable? To have every single node attest every single block, seems like a heavy burden. But it also doesn't seem impossible as it is a single proof (note: verify this claim).
• Consecutive Committees. Possible solution (1) to mitigate this.

  • As Hong-Sheng claims, we can use a “committee" and wait for a sequence of fully-attested (>3/4 blocks). The key here to mitigate bribery attacks is to wait for a sequence long enough that the likelihood of supermajority (>1/2 or more ?) of the network being covered is provably significant. The problem with this solution is that it

  • Note that contrary to what Hong-Shen proposes, there is no BFT-like block proposal by the leader here, instead it leverages the proposals already present in the network.

  • Problem: it takes too long to cover the network sufficiently in the case of may nodes (it's actually much worse then native Ouroboros finality 😄 ). If we use only 100 nodes and the network has 100k nodes participating in consensus (in reality, that means 100k old-enough coins as participation is only expressed at the time of proposal): $k \approx \frac{\ln(1 - C)}{\ln\left(1 - \frac{1}{N}\right)}$

    

  • Problem 2: we don't really know N, and estimating it is a can of worms IMO.

  • Conclusion: I don't think this is a satisfactory path if we want to avoid the “privileged committee”.

• Network's Best-Effort Attestation: Everyone Participates. Possible solution (2):

  • Get everyone to attest blocks, and transitively accumulate them (to account for network latency). If we make attestation lightweight, it can work, as we are not imposing a synchrony assumption, it's fully on the network's best efforts to attest.

  • There is a cryptographic challenge here that I'm unaware of its difficulty. We need to make sure that these attestations correspond to unique new coins, or rather, a delta respect the blocks they are transitively adding. The key here is that they do signal votes from different coins, not the same coins voting! I haven't thought how to make this possible yet. My current intuition is that what we need to encode together with each attestation is when was the last time this coin voted (since you cannot just create a new coin to bypass this, by virtue of the coin age requirement).

  • Visual representation

    graph TD
        classDef attested fill:#bbbbbb;
        classDef finalized fill:#666666,stroke:#000000,color:#ffffff;
    
        subgraph Blockchain
            B1[Block 1]
            B2[Block 2]
            B3[Block 3]
            B4a[Block 4a]
            B4b[Block 4b]
            B5a[Block 5a]
            B5b[Block 5b]
            B6a[Block 6a]
            B6b[Block 6b]
            B7a[Block 7a]
            B1 --> B2 --> B3
            B3 --> B4a --> B5a --> B6a --> B7a
            B3 --> B4b --> B5b --> B6b
        end
    
        A1[20% stake attested] --> B2
        A2[35% of new stake attested => Block 2 finalized] --> B4a
        A3[15% of new stake attested] --> B5b
        A4[20% of new stake attested => Block 4a finalized] --> B7a
    
        class B2,B5b,B7a attested;
        class B2,B4a finalized;
    
    

The problem with this family of solutions

The main problem is that privacy is severely compromised by the fact that attestations carry the stake weight information in the open. Now a single deanonymization would directly deanonymize the stake of a node in a single compromised path. Intuitively we are multiplying the chances of discovery by N times, with N being the number of stake holders participating in consensus.

An idealized solution integrating everything

<aside> ⛔

After revisiting this, I realized it has an obvious liveness issue that is not easily solvable without staking. I will abandon this line of thinking for now.

</aside>