My self is steam

April 17, 2025

Proof of Nothing

Or, Inductive Reasoning Considered Harmful

I've always wondered what the ubiquitous word "proof" really means in the context of the blockchain industry. As originally intended in "Proof of work", formerly conceived as an anti-spam technique, the meaning of the word lies on the probabilistic assumption that it takes a certain amount of computation to find the correct pre-image that hashes to a specific "shape". This assumption is largely justified by the fact that the cryptographic hash functions involved are a good enough approximation of the random oracle model (and not viceversa). Furthermore, the probabilities involved only offer a bound whereby one could quantify the likelihood of finding such a preimage. There is no "inference" based on past data. In a sense, the conclusion is quite deductive, following from the premises of the model. In contrast, the form of probabilistic reasoning anchored in reality, which subscribes to the school of thought that sees the human brain inferring new facts from past observations with a certain probability, is known as Inductive Reasoning, and has been the subject of many philosophical arguments.

When it comes to "Proof of Stake", largely popularized by post-merge Ethereum and Tendermint, assigning the right meaning to the same word is not so straightforward. In such a setting, the proof relies on a majority of cryptographically-signed votes cast by specific network participants known as Validators. The majority presumes a tally, the count of votes, which is then checked against a quorum. This therefore suggests some kind of arithmetic logic and arithmetic, and mathematics itself, is not inductive; for instance, despite its name, the proof method known as mathematical induction is inherently deductive. As with "Proof of Work", at least in the narrower context of the consensus rules, there is no inductive step involved in Proof of Stake: given a block B at any given height H, the only proposition P on the validity of B is P(H, B), and the link with a coherent past H-1 is ensured by a cryptographic hash between B and the block at H-1, where the latter was subject to the same premises. In other words, there are no "gaps" in ascertaining the validity of any block, as every block is verified and linked to the past. So in this context, the word "proof" has the same deductive meaning as self-evident facts in arithmetic, such as Succ(1)=2.

When light clients follow the same principle, the verification is known as sequential. The idea behind light clients is that of a pure verifier that does not execute the block, and which does not need to store the full record of that coherent past but which starts operating from a trusted block, whose corresponding state represents the client's view of the network at that block's specific height H. New trusted states are then established after the verification of the blocks that follow the trusted one, and the previous ones could be safely forgotten. In this mode of operations, a new untrusted block at height, say, H+N, introduces the necessity to fetch and verify all intermediary blocks at H+1, H+2, ..., H+N-1, which makes the verification slow. And this is when the inductionist turkey appears on the scene.

The solution to this problem is to skip verification of the intermediary blocks, a mode of operation called "Non-adjacent block verification" which, at least in Tendermint, works as follows: if the validator set that reached the quorum for the untrusted block at height H+N has "enough" overlap with the validator set of the trusted block at H, then this is enough proof that the untrusted block can be trusted. How much is this "enough"? The Tendermint safety property is guaranteed to hold for as long as at least 1/3+ of the validator set is not malicious; so, based on the assumption that the trusted validator set is behaving honestly at height H, if 1/3+ of their voting power is represented in the votes of the block at height H+N, the latter is considered trusted. There is a caveat, though: given that we cannot trust the content of the untrusted block, the induction step here requires that this 1/3+ voting power needed for the untrusted block at H+N be tallied from the trusted set.

We are therefore in the presence of two strong induction "leaps": (1) any validator holding 1/3+ of the voting power at H continues to behave honestly for N blocks, so that they could provide the basis for the proof of the block at H+N; (2) we believe that the validator of (1) is still behaving honestly but we cannot trust its voting power at H+N, for some unknown reason that escapes my comprehension (given that the voting power is signed by the trusted validator, so if they lie about their new voting power, I don't see the point of trusting them at all.)

Tendermint Rust's implementation of the above idea can be found here. The first_tally in voting_power_in_sets takes the votes from the signed_header (of the untrusted block), then accumulates the voting power from the trusted set. The second_tally only ensures that the new untrusted validators reach the regular quorum needed for any block.

As an argument to prove the fallacy of these induction steps, consider the following situation: the light client verifier is bootstrapped with a trusted block at H whose validator set is:

    let validators = [
        Validator::new("GOOD_A").voting_power(50),
        Validator::new("GOOD_B").voting_power(50),
    ];

The light client must verify a non-adjacent block at H+N, for which the declared validator set is:

    let validators_other = [
        Validator::new("EVIL_A").voting_power(50),
        Validator::new("EVIL_B").voting_power(50),
        Validator::new("GOOD_B").voting_power(1),
    ];

In its current view of the network, the light-client, due to the weak subjectivity, has no means to ascertain whether validator "GOOD_B" has kept with the induced promise to behave honestly. So it might be the case that "GOOD_B" fell in disgrace between H and H+N, and was slashed accordingly, reason for which its voting power is way less than it used to be at height H. However, by virtue of its past good behavior in the trusted state, "GOOD_B" exercises more than its current power, and the new block passes the validation. In another similar scenario, "GOOD_B" at height H+N could also be outside of the "bonding period", they might have as well retired from the network and their stake no longer active, but they are still exercising voting power to make such a block pass validation. In such a scenario, any a-posteriori fork-detection would be ineffective, for the simple reason that "GOOD_B" could not suffer any penalty, given that its stake is no longer active. Furthermore, for certain applications like cross-chain bridges, once the new trusted block is propagated to the destination chain, the matter of whether or not to use it right away relies on the chain's block finality assumptions, which might disregard misbehaving indications altogether.

The following simple test "proves" the argument:

    fn test_verify_inductive_voting_power() {
        use tendermint_testgen::{Header, Validator};

        let now = Time::now();

        // Create options with reasonable values
        let options = Options {
            trust_threshold: Default::default(),      // 2/3
            trusting_period: Duration::from_secs(60), // 60 seconds
            clock_drift: Duration::from_secs(5),      // 5 seconds
        };

        // Create verifier
        let verifier = ProdVerifier::default();

        let validators_trusted = [
            Validator::new("GOOD_A").voting_power(50),
            Validator::new("GOOD_B").voting_power(50),
        ];

        let validators_untrusted = [
            Validator::new("EVIL_A").voting_power(50),
            Validator::new("EVIL_B").voting_power(50),
            Validator::new("GOOD_B").voting_power(1),
        ];

        let header = Header::new(&validators_trusted.clone())
            .height(1u64)
            .chain_id("test-chain")
            .next_validators(&validators_trusted)
            .time(now.sub(Duration::from_secs(20)).unwrap());

        let trusted_block: LightBlock = TestgenLightBlock::new_default_with_header(header)
            .generate()
            .unwrap()
            .into();

        let header2 = Header::new(&validators_untrusted.clone())
            .height(10u64)               // triggers the non-adjacent block verification
            .chain_id("test-chain")
            .next_validators(&validators_untrusted)
            .time(now.sub(Duration::from_secs(10)).unwrap());

        let untrusted_block: LightBlock = TestgenLightBlock::new_default_with_header(header2)
            .generate()
            .unwrap()
            .into();

        let verdict = verifier.verify_update_header(
            untrusted_block.as_untrusted_state(),
            trusted_block.as_trusted_state(),
            &options,
            now,
        );

        // Test that verification fails
        assert_ne!(verdict, Verdict::Success, "Verification should fail");
    }

It should be clear at this point that there is no way to ensure trust based on inductive reasoning, even if the light client followed the bisection algorithm to reduce its subjectivity period. Statistical inference techniques might help the verifier to take better decisions but in all their forms, either classical or Bayesian, they still belong in the inductivist domain. Skipping verification for non-adjacent blocks might very well be named "Proof of Faith" or, better, "Proof of Nothing".