Higher-Order Functions - Githubissues

After some discussion in #2, I've come to realize that higher-order functions and the beta-reduction problem in general may be a non-issue for Kindelia, because Kindelia does not measure work in terms of the number of beta-reductions.

Because the number of beta-reductions a transaction will take is not formalized as a part of Kindelia (in either the transaction orderer or evaluation engine), the abstract measure of beta-reductions does not impact how miners evaluate transactions in practice. Whether a transaction does 4 beta-reductions or 500 is of no interest to miners, in the sense that each miner is free to measure the work done and reward gained from a transaction in whichever way they see fit.

To determine work, some miners may decide to use the number of beta-reductions, as explained in the README. This, however, seems to contradict how fees are paid in practice:

Since Kindelia has no built-in token, what incentive miners of the underlying sequencer would have to include a transaction in a block? If the transaction is an eval() block, then an user can just include a payment to the miner on it.

What's important to note is that miner payment does not depend on the number of beta reductions included in the transaction.

Instead of counting beta-reductions, miners may instead decide to use the amount other measures of work. This could be space used during computation, the number of stateful bind operations produced, or even something crazy like "the time it takes for an asm-compiled version of the transaction to execute." There's no limit to the method used here, because the network does not enforce a standard gas-like medium to measure transaction work. It doesn't seem like there even is a mechanism for a bond to determine how many reductions have occurred while evaluating it.

I've formalized miner incentives a bit, but I'd like to bring it up again here:

@slightknack: In a sense, given a function that evaluates the wealth of a miner F(World[N]), where World[N] is the world state after N transactions, miners are trying to select a set of transactions T from the pool of all potential transactions so that F(World[N+1]) is maximized.

An optimal strategy for maximizing F for a set of black-box transactions T may be to evaluate all transactions in parallel (i.e. perform one beta-reduction per transaction, repeat), subtracting the number of reductions completed (times some operational cost with respect to F) from the amount of gas rewarded by the bond (as given by F). Evaluation continues until either completion, in which case the miner includes the transaction in the next block, or exhaustion, in which case the miner caches the partial result (in case the transaction is included in a block mined by another miner, to reduce time spend on verification), and stops working on it.

This would incentivize transaction submitters to include payment upfront.

Transactions that do not include enough up-front payment will not be evaluated until completion, and thus the miner is not incentivized to include them in the next block.

@MaiaVictor: The blockchain only includes a list of transactions. It doesn't include any result, cache, hash, receipt, nor anything like that.

From what it sounds like, the blockchain does not include the number of beta-reductions taken in for each transaction. Because there is no required way to measure the amount of work done during evaluation, miners are free to evaluate the transaction however they like, as long as the result is consistent with evaluation rules.

Higher order functions just make the amount of work done hard to evaluate, in terms of beta-reductions. But because reductions are not codified as the gas unit of the network, there are no penalties for using alternative evaluation strategies.

If the network charges 1000 beta reductions for certain evaluation, but that miner is able to evaluate it using only 50, then he/she is having a massive computational advantage over everyone else. That is good for the miner, but bad for the network.

On the contrary, allowing for alternate evaluation strategies is better for both miners and the network: although there is no optimal choice, faster evaluation strategies increase the speed at which transactions are processed, and incentivizes miners to create faster execution methods.

For the reasons outlined above, as long as Kindelia does not have a network-wide gas metric based on the number of beta-reductions, higher order functions can be included at no additional cost.

I understand that this repository is at a very early point in development, and that a lot of changes are being made. I'll stop opening issues for now \:P

I think higher-order functions would be something really convenient to include in the language (minimizing code reuse). If you have any questions, or need help with anything in general (from code to proofs to docs), I'd be happy to help.

Miners don't need to run Kindelia transactions

An important point to note is that miners, technically, don't even know Kindelia exists. After all, Ubilog operates independently from it. Kindelia just uses Ubilog as a sequencer, or transaction storage. What will happen, though, is that Ubilog miners will notice the value of Kindelia transactions, and start picking transactions that favor them in Kindelia. But yes, technically, miners don't need to run transactions nor validate them in the same way that Ethereum does it. Both concerns are separated.

Kindelia will probably have high-order functions

The current paper specifies Kindelia won't have high-order functions, but it probably will, since our runtime, LamRT, features these just fine. It will probably limit lambdas to be used either linearly, or elementarily, since the runtime assumes that. This is a class of functions for which measuring their reduction costs is simple. Note that I still believe measuring the precise costs of a beta-reduction is absolutely necessary if you want to have functions in a blockchain. Otherwise, it becomes an arbitrary metric that doesn't make any sense.

There are still limits in Kindelia

While miners don't need to run transactions, users still do! After all, you wouldn't be able to check your balances or NFTs if you couldn't compute Kindelia's current state. And if it imposed no limits, anyone could send a heavy transaction that made computing the final state impossible. That's why we need to measure the costs of beta-reduction, and why we must impose space and time limits.

The space limit is actually imposed by Ubilog. Right now, it targets 1 block per second, with a block size of 1280 bytes. That implies a blockchain growth size of 40gb/year. Different sequencers would lead to different numbers.

The time limit dictates how many computations per second Kindelia can perform. Currently, Ethereum limits are:

30,000,000 gas    / block
 2,500,000 gas    / second
   500,000 muls   / second
    12,500 λ-apps / second

Ethereum can perform 12500 beta-reductions (λ-apps), using my best attempt at compiling lambdas to it. That isn't great.

Our prototypal runtime, LamRT, is averaging about 160m rewrites/second per CPU core, on my Macbook Pro M1. All primitive operations take 1 graph rewrite, including beta-reductions. As such, if we let the network run at 1/8 of its peak capacity, Kindelia's limits would be:

10,000,000 rewrites / block
10,000,000 rewrites / second
10,000,000 muls     / second
10,000,000 λ-apps   / second

That's 40x more muls, and 1600x more beta-reductions (λ-apps), per second, than Ethereum, with the tech we have today, assuming LamRT isn't improved any further. It would also be much better at dealing with functional idioms in general, such as pattern-matching, recursive functions and so on.

I think 1/8 peak capacity is a reasonable number, since it would mean that, in the worst scenario, every 8 years running would add 1 year to the full sync time. But computers will get faster, LamRT will get faster, and most blocks won't use their full computation budgets. That's a ridiculous increase in layer 1 throughput.

An important point to note is that miners, technically, don't even know Kindelia exists. [... They will] start picking transactions that favor them in Kindelia. [...] Both concerns are separated.

I'm getting a mixed message here. On one hand, miners don't need to know Kindelia exists; on the other hand, you mention miners will be incentivized to include kindelia transactions. If they are incentivized to include transactions, miners should only publish valid transactions that benefit them. However, there is no way for them to do this without some form of transaction analysis or evaluation. To evaluate/analyze a transaction, miners have to maintain a correct World (e.g. to ensure payments go through); for this to happen, miners (at the least) have to evaluate the transitive closure of all transactions the current one depends on (with respect to their rewards).

Otherwise, [beta-reductions] becomes an arbitrary metric that doesn't make any sense.

That's what I'm saying: If the metric of beta-reductions is not enforced in some manner by Kindelia/Ubilog, these reductions become an arbitrary way to measure computational cost.

As the reward structure of transactions is not tied to the number of beta-reductions (reward can be arbitrary), nodes will measure computational cost in whichever manner most accurately allows them to estimate the economical cost of evaluating the transaction. As mentioned previously, this measurement could be about anything, as long as it is reasonable to the miner in question.

While miners don't need to run transactions, users still do!

In #2, you mentioned that the agents who evaluate transactions and the agents that mine transactions are the same. However here, you state that while miners don't need to run transactions, users do. I understand this means that if miners are users, they must evaluate transactions. Does this mean that each user has to run a full node? Hopefully not.

That's why we need to measure the costs of beta-reduction, and why we must impose space and time limits.

I may be blind, but I haven't seen any indication of how the network determines space and time limits. If I publish a hard work attack, who's to say that nobody has to evaluate it? If people don't evaluate every valid transaction, they may reach a world state that does not match the rest of the networks. (Additionally, no per-transaction receipts are filed in the block—in the case something goes wrong (their evaluator is not to spec, they have a bit flip, transmission error over the network, etc.), how are nodes supposed to know that their state is inconsistent?)

Different sequencers would lead to different numbers.

This does not take into account the size of the world. What If I publish a 40 byte transaction that writes 1,000,000 bytes to the World? This is why I say the cost of transactions is more complex than the number of graph rewrites.

Ethereum can perform 12500 beta-reductions (λ-apps), using my best attempt at compiling lambdas to it. That isn't great.

The basic unit of work in Ethereum is an opcode, rather than a beta-reduction which consists of multiple opcodes. I imagine that one could compile a scheme-like language down to EVM bytecode with similar performance to solidity. To put this into context, measuring the speed of the EVM this way would be like measuring the speed of LamRT in terms of how many ethereum opcodes it could execute per second. I'm not opposed to benchmarking or comparison, I just think it should be done in a fair manner (i.e. write a large contract/bond that does the same thing in both languages, say recursive fib 35 , and measure execution time).

Our prototypal runtime, LamRT, is averaging about 160m rewrites/second per CPU core, on my Macbook Pro M1. [...] If we let the network run at 1/8 of its peak capacity, Kindelia's limits would be...

I'm sure you're aware of this, but nodes are not required to use the LamRT runtime. If someone releases a faster runtime, or one that uses a different execution model (e.g. JITing transactions to native code), the 'limits' of Kindelia will increase. Therefore, there are no hard speed limits built into Kindelia, other than how quickly a node can process and evaluate transactions.

In other words, what's enforcing the 10,000,000 rewrites / block limit? If a node published a block with more than 10 million rewrites, what will happen? Will the block be dropped? Who/what mechanism sets the limit? If it's 'the compute power of the network,' then there is no formal limit. You mention that miners don't run transactions: if this is the case, who ensures any limits are met?

I think that there is a large disparity between how miners are incentivized in practice and how Kindelia is designed to operate.

That's a ridiculous increase in layer 1 throughput.

I totally agree, this would be a pretty nice increase in L1 throughput. I don't want this response to overshadow that. However, I'm not entirely convinced that some of the assumptions being made will ensure smooth network operation in practice. You have to assume that every node will act to rationally maximize their own self-interests.

Here are the issues I currently see:

This isn't a full list by any means, but to sum it up:

It is not clear:
1. Whether miners ensure that transactions are correct before submitting them.
2. Whether miners evaluate transactions.
3. How miners enforce work costs if they don't evaluate transactions.
I am worried that:
1. Bad actors will write garbage data to the world, increasing the size of the world for everyone.
2. Users will not be able to keep up with the chain.
3. Beta-reductions will not be used to determine work in practice as claimed.
4. It is stated that work limits are enforced, but now way to determine work limits is listed.
5. If a hard work attack is sequenced, it must be evaluated by all nodes.
I would like to point out:
1. Higher order functions do not have to be restricted if work cost is subjective.
2. Beta-reductions are not a part of the protocol in the protocol's current form; i.e. no messages about beta reductions are sent or acted upon between nodes, either in the blockchain or otherwise.

Hey, I started answering your question, but ended up dumping a lot of info on this comment, which I'll adapt to include on the paper soon. Don't feel obliged to read it all :p

I'm getting a mixed message here. On one hand, miners don't need to know Kindelia exists; on the other hand, you mention miners will be incentivized to include kindelia transactions. If they are incentivized to include transactions, miners should only publish valid transactions that benefit them. However, there is no way for them to do this without some form of transaction analysis or evaluation. To evaluate/analyze a transaction, miners have to maintain a correct World (e.g. to ensure payments go through); for this to happen, miners (at the least) have to evaluate the transitive closure of all transactions the current one depends on (with respect to their rewards).

Okay, suppose we use Bitcoin as Kindelia's sequencer. Initially, Kindelia users would just pay the usual BTC fees, and everything would work fine, even though Bitcoin miners do not know that Kindelia-Bitcoin exists. But if Kindelia eventually grows large enough that its on-chain token start having real value... then Bitcoin miners will be motivated to create a Kindelia wallet, download Kindelia, and select transactions that pay Kindelia rewards. At some point, these Kindelia-Bitcoin miners would start including Bitcoin-Kindelia transactions, even though the BTC fee is zero. Bitcoin users would find it strange that miners are including 0-fee transactions with weird DATA fields... but for the rest of the BTC network, nothing changes.

The relationship between Ubilog and Kindelia is that. Ubilog natively uses portable proof-of-work as a heuristic to include transactions. But if Kindelia grows large enough, some Ubilog miners will download Kindelia plugin and start including Kindelia transactions, and become "Kindelia-Ubilog" miners. A "Kindelia-Ubilog" miner essentially operates like an Ethereum node. But some can just still be pure Ubilog miners and not even know Kindelia exists.

That's what I'm saying: If the metric of beta-reductions is not enforced in some manner by Kindelia/Ubilog, these reductions become an arbitrary way to measure computational cost.

It IS enforced. Not sure why you get it wouldn't. There is a maximum rewrites per block limit on Kindelia, just like there is a gas per block limit on Ethereum. Beta-reductions are limited in the same way that MULs are limited on the EVM. It is no different. Perhaps it is better to just forget the section on beta-reduction. It was badly written, but the entire point of it was to say: "hey everyone, we will use a different version of beta-reduction that is an O(1) confluent operation, so that accounting for its cost is as easy as accounting for a MUL cost, saving us a lot of headache".

As the reward structure of transactions is not tied to the number of beta-reductions (reward can be arbitrary), nodes will measure computational cost in whichever manner most accurately allows them to estimate the economical cost of evaluating the transaction.

No, that makes no sense. The subset of Ubilog miners that are interested in Kindelia (let's call them Kindelia-Ubilog miners, which are the equivalent of Ethereum miners) will need to measure the computation cost following our cost table, exactly like on Ethereum, because they need to select transactions that don't pass the block gas limit (ex: 10m rewrites). That cost table will have a "BETAREDUCE" opcode, unlike Ethereum, which allows us to have cheap functional smart-contracts (the whole section about beta-reduction is just explaining how it is possible for us to have such "BETAREDUCE" opcode).

In #2, you mentioned that the agents who evaluate transactions and the agents that mine transactions are the same. However here, you state that while miners don't need to run transactions, users do. I understand this means that if miners are users, they must evaluate transactions. Does this mean that each user has to run a full node? Hopefully not.

Okay, sorry. What I was trying to say is that, at the network level, everyone is the same. Politically, different kinds of users will emerge. I've separated them in categories based on what will probably happen in practice, and posted on the following gist:

https://gist.github.com/MaiaVictor/5138f913208724b068050ea992f2905b

I may be blind, but I haven't seen any indication of how the network determines space and time limits. If I publish a hard work attack, who's to say that nobody has to evaluate it?

I hope that is clear by now. Just to be double clear: Kindelia-Ubilog miners operate exact the same as Ethereum miners. There is no difference. We're just separating Ubilog's network, for people that don't like Kindelia's design, but still want its data/consensus aspects. But, for these that do Kindelia, it is the same. Makes sense?

The basic unit of work in Ethereum is an opcode, rather than a beta-reduction which consists of multiple opcodes. I imagine that one could compile a scheme-like language down to EVM bytecode with similar performance to solidity.

That is exactly what LamRT is! LamRT is an EVM-like machine, except it features BETA-REDUCTION as an opcode, and a constant-time operation. Specifically, this line evaluates a beta-reduction:

https://github.com/Kindelia/LamRT/blob/a0aec932b7dbf7915c19c30b219981179d4d599f/src/Runtime/Runtime.c#L311

We call that opcode APP_LAM. LamRT features other opcodes. Here is a rough table of the current design:

OPCODE	effect
APP_LAM	applies a lambda (beta-reduction)
APP_PAR	applies a sobreposition
DUP_LAM	lazily copies a lambda
DUP_PAR	lazily copies or collapses a sobreposition
DUP_CTR	lazily copies a constructor
OP2_U32	performs a native uint32 operation
REWRITE	performs an user-defined rewrite rule
SSTORE	stores a term permanently
SREAD	reads a term from storage

Yes, I'm just making an approximation when I talk about rewrites/second, because, in practice, all our "opcodes" have almost the same cost. We'll assign costs to these operations soon, but they'll probably end up very similar.

I'm sure you're aware of this, but nodes are not required to use the LamRT runtime.

Yes, they are, just like Ethereum nodes are required to use the EVM. I now understand your confusion, but I hope I clarified it above. I think the whole confusion comes from the separation of Kindelia and Ubilog.

In short:

Kindelia is just simplified Ethereum with a functional EVM.
A functional VM requires a BETA-REDUCTION opcode, and that's awkward, but we got it.

(Being technical: the problem is that counting beta reductions depends on the evaluation order. In the last design, avoided this problem by avoiding high-order functions (but still allowing datatypes and recursive functions). In the current design, we avoid it by using a subset λ-calculus which is "strongly confluent", so that the count of beta reductions is always the same, no matter the evaluation order! That subset allows high-order functions, datatypes, recursion, but forbits non elementary affine lambdas, which are weird programs that never happen in practice (like the Ackerman function implemented with λ-encoded nats).
Kindelia is split, code-wise, in two modules. One is responsible for data, networking and consensus (Ubilog). The other is responsible for computation, state and logic (Kindelia). Ubilog can operate independent of Kindelia, without involving tokens, computations, gas fees, opcodes. Kindelia-Ubilog together, though, operates exactly the same as Ethereum.

Hope all is clear for you and future readers.

kindelia-archive / Kindelia

Higher-Order Functions #3

Miners don't need to run Kindelia transactions

Kindelia will probably have high-order functions

There are still limits in Kindelia