Trustless data validation

An extremely important tool in achieving trustless data validation are Zero Knowledge proofs. They grant anonymity, conciseness and scalable trust while still leaving the control where it belongs to, namely close to the prover’s chest.

Other than the concept of Zero knowledge proofs, we need to dig deep into the challenge of trustless validation. In order to understand it, I dissected the issues into 5 tiers:

Result of an outside measurement cannot credibly be passed to a closed system without a trusted party. The essence of the Oracle problem is, there is no way to perfectly internalize data from an external source. It is totally irrelevant if we talk about databases, programming languages, smart-contracts or functions. As soon as a system needs data from external scope, it inherently trusts the validity (content, not syntax) of the data.

Once inside the system, we now - thanks to bitcoin - have ways to proof beyond reasonable doubt the data was not meddled with. This is the topic of our exercise.

Accepting there cannot be a solution to the Oracle problem, we seem to have two options:

I assume the reader of this document to be familiar with Hashing, so I’ll not go into details on the concept of it. A Hash function simply creates a fixed sized number as an output in a deterministic manner. Changing the input results in a seemingly random, unpredictable change in the output. Hash functions are one-way, meaning, it is easy to calculate forward, but infeasible to reverse.

In Bitcoin, and for that matter in our document, we use and refer to sha256() as the default Hash function. Bitcoin for most of the time uses double sha256: H(H(data)).

Use of words: Applying a hash function to a preimage results in the hash:

I assume the reader of this document to be familiar with signatures, so I’ll not go into details on the concept. A Signature consists of a Public key, a random number, a signature data and some meta-data representing what was signed in the first place. Signatures just as hashes are the result of one way functions, meaning you cannot reverse them. Neither the original data nor the signers Private key are accessible knowing a signature. (given the signer knows what he does) A common misconception is, that signatures were deterministic whereas they aren’t and shouldn’t. A given data can have godzillion different signatures, even using the same private key to sign. A validator can still see, if the data was tampered with.

Security model of Signature schemes we use in Bitcoin is based on the assumption of the reverse discrete log problem being hard. A clock arithmetic problem, underlying many cryptographic solutions. Bitcoin and Ethereum for that matter use ECDSA (EllipticCurve) algorithms, which aren’t linear, thus not being able to handle some multisig scheemes inherently. Schnorr-signatures on the other hand being linear, enable us to concoct multisig coding on signature level. Schorr signatures are also formally proven to be bulletproof. (ECDSA is only assumed to be) Bitcoin uses Schnorr since November 2021.

You usually do not sign the data itself, rather a hash of it.

We call something tamper-evident, if a verifier can be certain, if data was tampered with. Example: your average concert wrist-tape or the lid of your beverage. Tamper-evident storing of a data is nothing new, in fact the problem arises, when owners of a data do not even give a f.ck, if it is evident, they meddled with the data. It is useful up to a certain cost.

On the other hand, Tamper-evident might in many cases be just enough. For instance: if Validator’s inquiry ends at checking the data, well then Tamper evident is the actual goal. That goal of the Validator is by definition finding evidence. And for tamper evidence, you may not even need a blockchain.

You really need to pause here, and distinguish between these two concepts. Tamper-proof systems are necessary, if the data you check is further used in important calculations, functions, determining real life events, etc.
It is also important to understand: tamper evident - once tampered with - shows you a new state, out of which you can not necessarily recalculate the original state. Also, once tampered with sequence and timing info is also gone, even if the Verifier knows it happened. So in tamper-evident systems, if you need old data, you have to keep it!

Tamper-proof are data storing methods, where it is disproportionately costly or practically impossible to change the stored data. Now that is hard to achieve, in fact until Bitcoin, it was digitally not achievable. Not in a decentralized open manner anyway. In order to create a system of minimal trust, we need to achieve the lowest possible trust, when moving up between these points, while keeping scalability, usefulness and a practical architecture in mind.

In Bitcoin Tamper-proofness is probabilistic. The more time passes, the more certain you can be, data will not be changed. Neither data, nor discrete data’s sequence. So if your life depends on data, you only need to keep the youngest collection, as older data cannot possibly be changed.

It is hard to overstate, how important Tamper-proofness is, and how little use of trustlessness on lower levels mean, as long as Tamper-proofness isn’t achieved.

Once stored using the proposed protocol data will be immutable. Storage will have to be designed based on Business model and Architecture. The last chapter - documentation of a real-time demo - introduces an example: how to store, request, prove, validate data in such a system.

We listed two Oracle scenarios above. The two usecases implement the same basic logic: The first one asks an external Oracle, in the second one I am the Oracle myself. Does the Oracle return bundled data verified in a Merkle-Tree, we witness how the Oracle is put under pressure to behave according to the 'rules'. As more and more actors request data from the Oracle - being the trusted external information source - its stakes are raised to:

This applies to both an external Oracle and to me as well, if I take the role of one.

The same applies to my - the provers - data, if and when I prove something towards a validator (client). My software can in milliseconds on p2p basis prove validity of any data, once I checked if the request comes from the user with appropriate rights.

In a state - I want to document - I make x different measurements. The content, timing, frequency is arbitrary, as is the identity of the later verifier. These data, however big is ordered in a MerkleTree. Results, details, parameters can be stored by me, off-line, off-chain. Furthermore, lets be honest, whether logic of data they do not even belong anywhere else, as it unnecessarily bloats the system increasing its cost of use for me as well.

Logic, data, details: all stored / run offchain: Close to ones chest, centralized.
The Merkle root of the arbitrarly sized data however is stored on the only really immutable Blockchain. Or depending on scaling requirements is as-good-as stored on the blockchain:

--Does everybody really need to see it all?
--Is it really necessary to save even the one root on the chain, if I guarantee the Verifier can make my fraud as costly as possible?
--Even if necessary, does it have to happen all the time?

The answer is probably: NO. It may all happen on a 2nd layer. In Bitcoins case on the Lightning Network. Once we realize this, and combine it with the bundled Merkle-Proof, we have a fully scalable absolutelly bulletproof system. See also: Scaling

Let’s go one step further, if for some (subjective) reason we’re not keen on Bitcoin, we can build or own blockchain. It’s 10 lines approximatelly. I can give nodes to my clients. There is a short code to run a demo-chain shown in a real-time presentation.

…​to consider, when scaling trustless building blocks of your development:

Without diving too deep into each of these factors, let us touch on some basic concepts, and discuss which abstraction level to tackle these on: The system is by-large a centralized one, under our full control up to the point when data-to-be-validated is published. As introduced in detail, data can and should be bundled into larger chunks. The more data we can fit into one M-tree, the better. We can include the data from multiple sources, for multiple users, with user of different rights. We can even include external provers data as a service. (serve as an Oracle) And the Merkle-root’s size is still the same. So the issue of what to store in one given unit is not an issue when talking scalability.

Another question is the frequency with which we want to set our measurements in stone. Well, frequency can also be bundled. You can use a milestone approach, by sending different 'immutable' - level data on different channels, to different users. Let’s say, you publish your trees once a day over your preferred blockchain. In the meantime, you can send your trees to your client via …​ whatever you like, email, smokesignals, doves, or simply put it on your homepage.

Then - as mentioned above - there is the "if a tree falls in the forest, and no one hears it, does in make a sound" approach: Use Layer-2!

Your scaling opportunities are endless, really.

But most importantly: why would we use or need ANY of our logic to RUN on a Turing-complete or incomplete Blockchain? All we need is - for whichever usecase - data to be Tamper-proof. Other than that, scaling is best achieved, if your code runs on a small number of dedicated machines rather than on a world computer. Running complex logic on a myriad of machines - that do not even grant perfect immutability - is a receipt for un-scalability. Instead: limit the tamper-proof storage of only necessary data to a trully immutable DB, while delegating every other task to dedicated servers under your controll.

I assume the reader of this document to be familiar with the LN, so I’ll not go into details on the concept. We refer to the Layer-2 solution of Bitcoin as the Lightning Network as we presuppose an existing network. In Bitcoin - being pier-to-pier - no one can forbid you to implement Layer-2 without even touching the 2nd Layer network. In this document we use Layer-2 and LN interchangeably, but most of the time you can think of Layer-2 as a basic messaging system between two piers once they’ve anchored a SmartContract on the Bitcoin Blockchain. This way, you can spare having your keys in a LightningNode hot wallet, spare running an LN Node.

Back to the top: Trustless data validation

We have a database of which we keep different, sequential, timestamped states on many adversarial Nodes (computers). Adversarial means, they have incentives to retroactively alter said database to include data more advantageous to them. The problem is, how all these Nodes consider the same state "valid".

Proof of Stake disregards these principles on many levels. The main motivation behind any alternative to PoW is…​

Depending on the implementation, there are specific actors, who validate new incoming information and write the db. These actors are picked (not necessarily actively) based on how much internal(!) value they are ready to bet, to risk, to stake, to lock. Did the Validator of a new entry - Block - not behave in accordance with the protocol, an internal rule (depending on the implementation) punishes them by cutting said stake.

In other words, cheating on such a system is NEWER punished with real life consequences.

Back to the top: Trustless data validation

slide 1
An Oracle - under either Our or ThirdParty control - creates a collection of measurements, (possibly for multiple clients, different times, with arbitrary timing…​. etc.) we store, and from which we can - on request - select and provide proofs for the ones our given Client - the Verifyer - asks for. Stored data - measurement documentation - can be in any format as long as standardized.

slide 2
Data is then simply turned into bytes, and is extended in order to have the necessary lenght for us to be able to derive a Merkle root from. It has to be size of an integer power of 2. We call these the leaves of the tree.

slide 3
All 'leaves' are now Hashed using the function we pick to set up the entire tree. Topmost branches of the tree are first created.

slide 4

slide 5
Preparation is over. Prover initiates a MerkleTree manager, using the <last_branch> and the agreed upon <hashfunction()>, to create the entire tree, and the Merkle Root.

slide 6

slide 7
Setup basic VERIFYER data: He creates a Verifyer instance to use it for several proofs. The verifyer might be interested in a couple of data in the current tree. He already has the data he wants to doublecheck. For reasons outlined before, his data MUST be labeled (fraud, tree-building).

…​and using this data, updates his Validator engine.

slide 8
Setup VERIFYER’s request Validator now creates a request containing data addresses he wants to check, and sends said list to the Prover.

slide 9
The prover takes each request data, and coughs up a merkle-proof for these.

slide 10
Verifyer now builds he’s own Root version for each of the data he wants to validate using the Merkle Proof provided by the Prover - us

slide 11
We provided an optimal solution for both sides:

Back to the top: Trustless data validation