Defining algorithmic complexity of a blockchain protocol

zeuner

member

Activity: 189

Merit: 16

Quote from: tromp on February 27, 2021, 03:03:25 AM

Quote from: zeuner on February 26, 2021, 05:24:39 PM

Quote from: tromp on February 21, 2021, 05:25:00 AM

For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.

What if there is a program that can do the operation with less complexity using a SPV-based protocol?

SPV should be excluded, of course. We want the program to fully verify that it has been paid 1 coin,
even in the presence malicious miners with a majority of hashpower, that can make incorrect history
appear to be the most worked on branch.

You will need a formal definition of the payment being verified. It remains to be proven that there is a definition that is both sound and capable of distinguishing an SPV-based verification from a full verification.

tromp

legendary

Activity: 990

Merit: 1108

Quote from: oryhp on February 28, 2021, 06:27:21 AM

Quote from: ?? on ??

I think you're referring when smart contract is created. Ethereum also have gas cost when the contract is executed (either when receive transaction or executed by another smart contract).

I think this assumes that the gas prices measure complexity, but they likely don't.

According to e.g. https://ethereum.stackexchange.com/questions/35539/what-is-the-real-price-of-deploying-a-contract-on-the-mainnet, contract creation gas cost is roughly affine in contract size.

oryhp

member

Activity: 60

Merit: 89

Quote from: ?? on ??

I think you're referring when smart contract is created. Ethereum also have gas cost when the contract is executed (either when receive transaction or executed by another smart contract).

I think this assumes that the gas prices measure complexity, but they likely don't.

tromp

legendary

Activity: 990

Merit: 1108

Quote from: odolvlobo on February 27, 2021, 04:49:15 PM

Write the rules in Solidity and run them on Ethereum. The gas cost will tell you the complexity.

It would the contract size that defines the complexity.

odolvlobo

legendary

Activity: 4508

Merit: 3425

Here's an interesting idea:

Write the rules in Solidity and run them on Ethereum. The gas cost will tell you the complexity.

And a side benefit is that you now have a node running on Ethereum.

aliashraf

legendary

Activity: 1456

Merit: 1175

Always remember the cause!

Quote from: tromp on February 27, 2021, 03:06:59 AM

Quote from: aliashraf on February 26, 2021, 06:10:01 PM

To represent Bitcoin blockchain for instance

As I explained already, I'm not interested in describing the blockchain data.

I'm only interested in describing the rules for recognizing the longest (highest cumulative difficulty) valid chain,
and whether that includes a payment to me.

It was not how I read your op, but OK.

Firstly, the MLC problem is a trivial one as far as it is seen from an SPV perspective (which it should be, by the way) and I don't think it yields meaningfully different results for different protocols because they could simply adopt the best scheme without going through major changes.

As of the inclusion problem, I suppose it has also something to do with light clients/wallets (not necessarily SPVs) because we are now in the territory of state commitment, i.e. continuously committing to the total state of the blockchain in each block.
Again any blockchain protocol is capable of supporting state commitment almost trivially and seamlessly, so we are ending in the same situation as with the MLC problem.

tromp

legendary

Activity: 990

Merit: 1108

Quote from: aliashraf on February 26, 2021, 06:10:01 PM

To represent Bitcoin blockchain for instance

As I explained already, I'm not interested in describing the blockchain data.

I'm only interested in describing the rules for recognizing the longest (highest cumulative difficulty) valid chain,
and whether that includes a payment to me.

tromp

legendary

Activity: 990

Merit: 1108

Quote from: zeuner on February 26, 2021, 05:24:39 PM

Quote from: tromp on February 21, 2021, 05:25:00 AM

For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.

What if there is a program that can do the operation with less complexity using a SPV-based protocol?

SPV should be excluded, of course. We want the program to fully verify that it has been paid 1 coin,
even in the presence malicious miners with a majority of hashpower, that can make incorrect history
appear to be the most worked on branch.

aliashraf

legendary

Activity: 1456

Merit: 1175

Always remember the cause!

OP,
Besides that I'm suspicious about the original problem you put forward here as being a fruitful one because I tried but didn't find any application, I oppose the strategy you suggest.

As @zeuner correctly reminded above, a blockchain is not just an algorithm or a protocol, you can't represent it by any form of abstraction because it holds and preserves events from the real world. To represent Bitcoin blockchain for instance, the most efficient way would be expressing the state of the system which could be efficiently summarized in a canonical form of the UTXO, period.

On the other hand, if supposedly you are concerned about formalizing the protocol, I don't think programming language and code base would yield anything significant. Protocols are efficiently representable as finite state machines, this technique is applicable both for the p2p network and the consensus protocols while we have the notorious relational theory that gives an excellent notation of FSM.

I may have missed something here, otherwise I think what you are looking for should be viewed from such perspectives.

zeuner

member

Activity: 189

Merit: 16

Quote from: tromp on February 21, 2021, 05:25:00 AM

In Algorithmic Information Theory [1] one studies the minimal number of bits needed to describe objects.
Normally the objects studied are just binary strings. For instance, the first million bits of pi in binary.

For a static binary string, you are looking at programs that compute something with no input involved.

For a blockchain protocol, it seems unlikely that a static binary string would be representative for what constitutes the protocol. Most likely, you'll want to look at at least one protocol operation that involves an input (say, from another node).

After deciding what exactly to study here, it may be easier to determine a good definition for the complexity measure.

Quote from: tromp on February 21, 2021, 05:25:00 AM

For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.

What if there is a program that can do the operation with less complexity using a SPV-based protocol? We will probably agree that this cannot cover all the complexity of the blockchain protocol since the protocol could not work with only SPV nodes being present. If so, the definition should be designed in a way so that this is not considered as valid.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: odolvlobo on February 22, 2021, 05:28:51 PM

1. I wouldn't pick a general purpose programming language. These languages would come with a lot of baggage making actual measurement infeasible if not impossible.
2. What do you mean by the complexity of a block chain protocol? I would measure the validation rules, since those are what ultimately determine the output.

It's better to avoid any Turing complete language to represent state, so you don't have to deal with invalid states which are inventible in languages that let you use unlimited loops.

Amazon States Language looks like a good way to represent protocol intrinsics and consensus rules (maybe the number of these is what OP means by 2.)

There is also ASML by Microsoft but I couldn't find any specification for it.

odolvlobo

legendary

Activity: 4508

Merit: 3425

I'm not an expert in Algorithmic Information Theory, but I understand the premise.

First I want to point out a misconception. The term "random" describes a process and not the individual values generated by that process. The fact that the first million digits of pi can be compressed does not make the digits of pi not random. The value 2²⁵⁶-1 might not seem random, but if it is generated by SHA-256, then it is because SHA-256 is random.

Anyway, ...

1. I wouldn't pick a general purpose programming language. These languages would come with a lot of baggage making actual measurement infeasible if not impossible.
2. What do you mean by the complexity of a block chain protocol? I would measure the validation rules, since those are what ultimately determine the output.

tromp

legendary

Activity: 990

Merit: 1108

In Algorithmic Information Theory [1] one studies the minimal number of bits needed to describe objects.
Normally the objects studied are just binary strings. For instance, the first million bits of pi in binary.
Random as they may look, the fact that they can be generated by a small program shows that they are anything but.
A truly random string of n bits would take a program of length at least n bits to describe it. With only 1+2+...2^{n-1}
= 2^n - 1 possible descriptions/programs shorter than n bits, it's clear that such a random bitstring must exist.
What if we want to extend this notion of descriptional complexity to blockchain protocols?
This would allow us to quantitatively compare the complexity of different coins.

It remains to answer two questions.
1) What programming language do we use to encode the protocol?
2) What is it that the program would do?

For 1) we could pick a common popular language like C99.
For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.

Does this seem like a reasonable definition? Does it capture all the complexity of a blockchain protocol? Could it be further simplified?

[1] https://en.wikipedia.org/wiki/Algorithmic_information_theory

Topic: Defining algorithmic complexity of a blockchain protocol (Read 210 times)