Truebit
Outline
- Cryptography & Intro
Matteo - Economics
Bradley - Governance
Teemo - Blockchain Structure
German
- Blockchain Guarantees
German - Threat Models
André - Conclusion
All
Introduction
1. Cryptography
What are the main cryptographic primitives used in this blockchain project?
Merkle Trees
- Used to store solutions to computation in an \(O(log\space n)\) contestable format
Does this project use any exotic primitives? If so, which ones?
- Built for simplicity
- avoids probabilistically checkable proofs (PCP), succinct non-interactive arguments of knowledge (SNARKs), and exotic primitives (e.g. zk) entirely
- Relies on standard cryptography provided by the underlying chain
- (hash functions, digital signatures, …)
How does this project use digital signatures for security?
Extends the hash functions & digital signatures provided by underlying Blockchain
“Participants do not need to manage cryptographic keys
beyond those used in Ethereum.” (Teutsch, Reitwießner, 8)
- The protocol relies on financial deposits to provide Sybil Resistance
How does this project use hashing and hash-based data structures to ensure security?
TrueBit uses Merkle Co-paths ensure computations are valid.
The Verification Game:
- The Solver calculates the hash of their state: the Merkle Root.
- If a Verifier calculates a different root they can choose to challenge the Solver.
- Following images from: https://medium.com/truebit/truebit-the-marketplace-for-verifiable-computation-f51d1726798f
- Each square is a leaf of the Merkle Tree (a computational step in the solution)
- So far, we know only that the inputs are equivalent and the outputs disagree
- We need a method to search for the point of contention.
- We recursively check midpoints until the computational difference is isolated
- This method ensures that challenges can be processed in O(log n) time
- Once the first point of disagreement is found, the TrueBit contract initializes a virtual machine with the pre-state and runs the fragment on chain to determine computational “truth”
Summary:
- A Solver and Verifier disagree on the Merkle Root
- Binary Search for disputed step
- Run instruction on chain to establish finality
2. Economics
Does this project have a native coin or currency?
Yes and No
Supply and Demand Dynamics
Fixed Pricing (Regulation)
In section 4.2 the white paper states that,
“in practice the verification tax requires a substantial cushion. We estimate the necessary verification tax to be 500% – 5000% of the cost of performing the given task.”
High fees relative to the computing price are undesirable, but they are still far lower than the gas fees Ethereum would charge for an equivalent computation on chain. This is analogous to benevolent price fixing in TrueBit’s governance system.
Real time response
Unlike many historical examples of price fixing, TrueBit prices could still implement a measure of real time responsiveness to supply and demand. Instead of voting on a singular price per computation unit, participants would vote on a pricing function \(f\) so that:
\[ f(V,S) = T \]
Where
-
\(V\) = the average number of verifiers per task on the network
-
\(S\) = the proportion of solver computation speed to task volume (throughput/demand)
-
\(T\) = the tax or fee rate relative to the price of cpu cycles for the underlying computation
Incentivizing Good Behavior
Task Giver Incentives
Task Solver Incentives
Task Verifier Incentives
Disincentivizing Misbehavior
Nash Equilibrium
Gaming Payouts
Economics Conclusion
- Price fixing, not so good
- VRF integration
- Potential improvement: Unified work pool from which solvers and verifiers are randomly assigned
3. Governance
“the user community can democratically update the interpreter as needed”
But lacks any specification and is not further elaborated in the paper.
The Truebit governance is led by the original founding team. The team has not communicated about how it envisions the future of its governance and if part or all of the authority will be transferred to the community.
The authors claim to “introduce a governance layer whose lifecycles culminates with permanent dissolution into utility tokens, thereby tending the network towards autonomous decentralization.”
The upgradability of the smart contract
- a new contract is deployed (by anyone)
- contract issues new TRU and CPU and DAO tokens, but accepts legacy ones
- users migrate to new contract, old tokens will gradually phase out
Upgradability
4. Blockchain Guarantees
Liveness
- Relies on parent chain
minDepositandtimeOutensure termination
However
- Storage problem
- Possible to stale the chain
- Sybil attack
Fairness
Censorship-resistance
Protocols make an assumptions about the calling chain. It claims that censorships are not possible on Ethereum, because users can obfuscate the function of their transaction. That means that “miners cannot easily see where an Ethereum transaction might call without executing it”.
Safety
The general concept of safety is build around the incentive for network participant to build truthful. It is more profitable to receive a fair compensation that to break the safety. More of this is discussed in section 6.
It is also worth mentioning that the protocol properties defined in the whitepaper align with the implementation of a protocol.
5. Blockchain Structure
Truebit is built around the goal of linking web 2 computational resources to web 3 in a trustless way. This is necessary on chains looking to handle either rich data formats or lots of traffic. Off chain actors are tied into the core smart contract via existential deposits which act as levers to ensure the contribution of compute resources without malicious behavior.
What is the state transition function of this blockchain/project?
The state transition consists of three layers:
- Incentive Layer
- Dispute Layer
- Computation Layer
What are the core elements of the application stack?
The protocol relies on the Layer 1 solution that can correctly perform small computation tasks in order to verify the correctness of the computations. The paper gives Ethereum as an example.
- Off-chain interpreter which enumerates a list of states for a given computation
- On-chain stepper which, given a state, can compute the next state.
The computation tasks can be stored either on IPFS or blockchain directly.
However, the storage still remains an open problem for the project. Storing data on blockchain is way too expensive whereas IPFS can not guarantee the persistency of data without an incentive.
What is the anatomy of a block in this system?
- initHash: initial hash of the task, so there is a deterministic starting point of the task. We are working on making this easier to do.
- codeType: 0 is WAST, 1 is WASM. You’ll know by your file extension of the task.
- storageType: 0 is Blockchain, 1 is IPFS. IPFS is cheaper.
- storageAddress: Contract Address or IPFS hash
- maxDifficulty: Determines the difficulty of the task (1 is okay for testing)
- reward: The amount of TRU tokens offered as a reward
What is the consensus algorithm that is used? How does it work?
Overview
- No challenge -> no challenge game -> result is published
- Challenge -> challenge game -> judges make decision
Game
Both challenger and solver start at first computation step (i.e. 0 )
The challenger submits index i of the step that differs from its own and then submit it to the network. If i is outside the boundaries ( i < 1 || i > (n-1)), the challenger loses the game and deposit immediately.
Otherwise, the challenger selects the configuration to challenge at position between the first step 0 and the first indicated wrong computation at i.
The solver submit the hash of the computation (or state snapshot) and submits it as a proof of the correctness of the solution. The challenger then computes its own merkle tree and compares the value with its own.
If they are correct, the challenger advances and selects the configuration indexed between i - index_of_first_incorrect_configuration and i
The game eventually runs for \(O(log(n))\) steps and converged to the first (initial) disputed step.
The configuration is then submitted back to the calling blockchain where validators of the network (e.g. Ethereum nodes) can verify it quickly on-chain.
Evaluation
Positives
- WASM
- Dispute Layer
Negatives
- Storage
- Ecosystem
6. Threat Models and Security
Byzantine Generals Problem
Sybil Attack
How does this project provide secure transactions?
7. Conclusion
How do the cryptographic elements, the economic incentives and the blockchain parameters all contribute to the core goals of this blockchain?
- Merkle Tree of computation steps allows for minimal on chain computation when establishinng finality
- All truthful partivipants are approptiately inventivized
- All byzantine participants are properly disincentivized
- Pricing is chosen in a way guaranteed to cultivate security vs throughput.
- This project isn’t a blockchain
- Parent chains such as Ethereum guarantee the liveness and termination of Truebit contract instances.
From 2.2 Assumptions - “There exists a trusted network (i.e. Ethereum) that correctly performs very small computation tasks.” (Teutsch, Reitwießner 9)
Of the things that you identified you liked the most, what were the top two things you would highlight?
- Verification Game
- Merkle Tree for storing computations
Of the things that you identified you liked the least, what were the two top things you would highlight?
- The power is concentrated in the hands of creators
- Price fixing
Describe a way you would devise an attack on this system.
- Truebit is not Sybil-proof
- Register multiple verifiers
- Decrease the economic incentives for honest verifiers to participate
- Hence, reduce number of verifiers and hijack the protocol
- The protocol becomes the weekest part of security of blockchains using it
- Truebit relies on external storage provider
- Increases the attack surface
- Unavailability of program data results in breaking the dispute game
Where we would take this project?
General improvements
- More randomness so selection of verifiers
- Currently, verifiers chose challenges
- Random assignment verifiers -> attacks more costly
- TrueBit has been dead for a few years
- Arbitrum and Polygon are better solutions for increasing throughput
Proof of Computation
-
TrueBit's ideas could be repurposed to create a new consensus mechanism
-
Fix two problems with one solution
- Dominant cloud computing solutions require the user to trust the provider
- PoW consensus mechanisms waste a lot of compute power
-
Fundamentally: runs batched computations to underlie PoW
-
What we theoretically get:
- Decentralize cloud computing
- Economical use of PoW computations