A Pack of Watchdogs is Cheaper than Gas

An engineering shortcut for some blockchains

Blockchains that run general programs use gas to abort runaway computations, and to charge for costs of execution. When the only requirement is to abort runaways, the pack of watchdogs mechanism proposed here can serve that purpose with less effort.

Background

Blockchain computations consume “gas”, decrementing a remaining gas budget until it hits zero. The essential purpose of gas is to abort runaways — computations that take too long. An important, but often inessential, purpose of gas is to approximate the costs of computation, to compensate validators and incentivize efficiency. For both of these purposes, blockchains require gas to be deterministic, so all honest validators agree on whether a transaction completed first or ran out of gas first, and of how much gas it spent.

This determinism requirement makes gas expensive to implement. We either instrument our virtual machines, alter our compilers, or do source-to-source or bytecode-to-bytecode translations. Any of these techniques ensure that the gas budget is decremented at least on every function call and backwards branch. This also makes gas expensive to execute.

Embedded devices abort runaways with a cheaper technique: A watchdog timer is started at the beginning of each transaction, and reset at the end. If the watchdog barks before the transaction completes, the transaction is aborted. Such devices are non-replicated, non-byzantine, resource limited, uninterested in differential pricing to charge costs or encourage efficiency, and tolerant of non-determinism.

So-called permissioned blockchains, as well as early testnet prototypes of public blockchains, may have requirements somewhere between public blockchains and devices.

• Replicated byzantine computation, assuming only k-of-n validators are honest, where k > 1/2n. Classic byzantine-fault-tolerance, for example, assumes that k = 2/3n+1 validators are honest.
• General purpose computation, but needing to abort runaways.
• No pricing needed.
• Require unambiguously agreed outcomes.
• Tolerant of non-deterministic outcomes.

The Idea: A Pack of Watchdogs

Say that each validator runs each transaction under its own watchdog timer set approximately to duration T. This is not a time oracle — the validators do not coordinate their time sources. One honest validator might see a transaction complete before its watchdog barks. Another might hear its watchdog bark first. Each honest validator eventually reports one of these two outcomes.

If k validators (e.g., 2/3n+1) report that their watchdog barked first, each honest validator concludes that the transaction took too long, exhausting its time budget, and is to be aborted — even if their copy had already completed. If instead n-k+1 validators (e.g., 1/3n) report that the computation completed within approximately duration T, then at least one honest validator observed the computation complete in time. Each honest validator concludes that the transaction is not a runaway and so must run it to completion — even if it had earlier reported that its own watchdog had barked.

An honest validator whose watchdog barks before the transaction completes should report the bark, but should continue running the transaction anyway until it observes one of the above two conditions.

Caveat: A Pack of Watchdogs increases latency

At https://twitter.com/mappum/status/1192110050547863552 Matt Bell writes:

Interesting mechanism. Does this now increase latency since after broadcasting a tx, validators now each have to broadcast their watchdog result and wait for 2/3+ before actually committing the tx’s state changes?

This is correct and a great point. As a result, the pack of watchdogs technique will often cost more than it saves. Beware of this tradeoff when evaluating whether this technique is suitable for you.

See that twitter thread for Matt’s further thoughts.