MerkleWeb - statistical Godel-like secure-but-not-perfect global Turing Machine

[Gavin Andresen]

The only way to convince MerkleWeb to calculate anything different is with "choice bits" (as I wrote above), which are kind of like network ports mapped into certain global 320-bit addresses. Each choice bit can only be written by a certain private-key. Each group of choice bits has a public-key that everyone can see to verify the digitally-signed bits from the private-key.

Ok.  So who controls the private keys?

[1713869010]

1713869010

[1713869010]

1713869010

[BenRayfield]

MerkleWeb will be an open source tool that anyone can use to do whatever they want. There will be many competing MerkleWeb networks which will probably eventually converge into 1 big MerkleWeb network that runs all the others as software controlled by whatever democraticly chosen rules we globally agree on. The ability to create your own network if you don't like existing networks will keep the total value of each MerkleWeb positive, unlike existing governments and other organizations which are forced on us in a monopoly way. In this environment of many competing MerkleWebs, some will have private-keys associated with certificate-authorities (like those that web browsers come with built in), peer-to-peer "web of trust" systems of collectively agreeing on whose private-key is associated with identities or other things, optional USB identity sticks given out with government ID cards, or whatever other kinds of identity systems people come up with, or anonymous private-keys like Bitcoin uses. Private-key/public-key pairs are tools to build things with. As a general computer, MerkleWeb could use public-keys and the data published with the private-key like any other variable in software. All possible uses of private-keys.

[netrin]

Should we understand the MerkleWeb as a shared memory heap? Is each 'transaction' essentially a single memory space, or stack, and entire execution history recorded as a merkle tree since some earlier verified (fork) point in time/memory? Any node can voluntarily recreate any execution history? Does the MerkleWeb have 'blocks' a la bitcoin? Does each program/merkle tree run until exit, or can its entirely deterministic state and history be recorded in a block mid-execution? How do we reconcile multiple executions of the same 'program' with different inputs/race conditions? Have I processed an invalid path of confusion?

As for monetization/incentive: processing cycles, memory storage, and bandwidth are each quantifiable and valuable commodities.

[BenRayfield]

Should we understand the MerkleWeb as a shared memory heap?

Most software divides memory into mostly stack and heap. In MerkleWeb, there is no such division. Code, data, and control-flow are done through many http://en.wikipedia.org/wiki/Continuation implemented as acyclic forests of Merkle Trees where the leafs specify a subset of address ranges and their contents as 0s and 1s. Other data in the constants section includes NAND definitions of the logic to be implemented between snapshots of the bit states, or any other data you want to put in MerkleWeb.

Using this strategy, a large word doc, for example, would compress down to a little more than the buttons you pushed to create it, minus their similarity to the buttons other people push to create similar word docs.

The memory space is a 2d matrix 2^256 bits wide and 2^64 bits in the time dimension. The first 2^63 rows are time cycles. The first cycle of the network starts at row 0 and proceeds in units of "global heartbeats" (or many cycles inside each "global heartbeat" which is faster but harder to sync) which all computers in a MerkleWeb time synchronize on. The next 2^63 rows are for constant bit strings. Every bit in every constant bit string has its own address. Like strings in C (for byte addresses), the address of a constant bit string is the address of its first bit. The address of bit b in a bit string with SHA256 hash h is the bits of h then the bits of b as a 320 bit address. The addresses in the Turing Complete section and the constants section can each point into the complete address space.

Does the MerkleWeb have 'blocks' a la bitcoin?

All addresses are to a specific 1 of 2^320 virtual bits. Its not byte or int addressing like many hardwares do. In that system, blocks are addressed by their first bit and extend forward in the time dimension until they roll over to time 0.

MerkleWeb doesn't have a specific block data format. It supports all possible kinds of Merkle Trees in the constants section, where they are made of some combination of 320 bit addresses (or compression of them?) and each have a constant 320 bit address. Bitcoin's existing blocks could be mapped into this address space using a map of the kinds of secure-hash addressing Bitcoin uses to SHA256 secure-hash addressing. The simplest kind of Merkle Tree would be 640 bits, 2 pointers of 320 bits each, and its leafs would be a different data format to each specify an address range (often partially overlapping other Merkle Trees' address ranges) and its contents as 0s and 1s.

Is each 'transaction' essentially a single memory space, or stack, and entire execution history recorded as a merkle tree since some earlier verified (fork) point in time/memory?

Yes, like a simplified version of http://en.wikipedia.org/wiki/Apache_Subversion that versions and branches the whole memory and computing state and virtual hardware design at the NAND level. All that is a state of the program, and since its all virtual, MerkleWeb is completely stateless. Even the hardware it runs on (whatever it is) must be defined in terms of NANDs in a constant bit string (whose address is used as the name of that calculation), so the specific kind of hardware(s) is part of the state and will sometimes change between 2 "global heartbeat" cycles, like if an evolvable hardware system printed new NAND gates onto itself in the middle of adding 2 numbers, or if MerkleWeb is told how to use your CPU's native ability to add numbers, so the last half of calculating that math is done more efficiently. All these things are transactions and can be done in hardware if its there or fall back to software emulation if the hardware fails in the middle of the transaction.

Any node can voluntarily recreate any execution history?

Yes, on the condition that the network is still storing the Merkle Trees whose leafs are that part of the history. Which MerkleTrees exist at a certain time are also part of the history, so they can point at eachother in many overlapping ways (sometimes and mostly for older more important parts of the history, to add more reliability to handle the possibility of SHA256 being cracked) and into the Turing Complete section.

Does each program/merkle tree run until exit, or can its entirely deterministic state and history be recorded in a block mid-execution?

Mid-execution. MerkleWeb will handle programs that do not halt (including infinite loops) by running them 1 cycle at a time. Each MerkleWeb network will have a constant integer number of cycles to run each Global Heartbeat. Example: if MerkleWeb is running mostly on grids of GPUs (like many people use for mining Bitcoins), then that number of cycles would be the approximate number of graphics card cycles done in the time it takes to do an average network hop, minus a little extra time for the slower hops to catch up and to rollback and recalculate any who do not stay in sync.

It doesn't just store the previous state. It stores many previous states, knowing some part of some states and filling in the gaps from the NAND definitions of how calculations must proceed, except for "choice bits" which have no deterministic definition since they are for user interaction. Theres still some things to figure out about how to rollback "choice bits" (does it erase to unknown, stay the same, predict what the user would do in the new state, or some combination?). Every state is actually many states at different times and addresses. Continuing from a state "mid-execution" or an overlapping combination of many states is a http://en.wikipedia.org/wiki/Continuation MerkleWeb is a debugger of MerkleWeb. There is no production or normal mode. It always runs in debug mode.

How do we reconcile multiple executions of the same 'program' with different inputs/race conditions?

If any 2 MerkleTrees are both thought to be probably correct by the local computer (or wireless Turing Complete router), then it must trace the contradiction back, on a path of NAND calculations and previous snapshots of parts of the address space, to a state of MerkleWeb where no contradictions existed. Any parts of the program needed to do that which it doesn't have can be requested by their addresses and verified with SHA256 and their bit length to be at the requested 320 bit address if they are in the constants section, and if they are in the Turing Complete section they are calculated from the smaller amount of information given in the constants section about the NAND calculations and previous states. Rollbacks will flow through the network until all contradictions are eventually solved, except there will always be many new contradictions in the last few seconds.

This is the part that's similar to quantum physics. http://en.wikipedia.org/wiki/Delayed_choice_quantum_eraser is a more complex form of the quantum double-slit experiment where observing which of some future paths a particle/wave takes causes a wave-interference pattern (after an earlier double-slit) to change to more like the sum of 2 bell-curves (no wave interference). How could what happens in the future determine the past of a different branch? One of my theories is reality operates a little like MerkleWeb, rolling back changes on mostly the same path (of network hops in MerkleWeb or in physics I'd say networks of peer-to-peer associated "virtual particles") they proceeded when a contradiction is observed. Since Internet wires or wireless routers have some maximum speed (which is the speed of light in the case of wireless routers since they transmit light), accessing "choice bits" or other unknown information that are written farther away than information could travel there in time, causes a "race condition", which causes global rollbacks and recalculations of all affected calculations (but not of anything which wasn't affected, so it scales up well), which would appear to a simulated life form in such calculations that the other simulated thing which is moving faster than light is moving backward in time, and when it moves near the speed of light it gets time-dilated toward not experiencing time at all. Also similar to relativity, mass increases toward infinity as speed approaches light speed, if we define number of calculations needed to rollback and recalculate in the whole network as mass. That is only statistically true since going faster than light tends to create contradictions which would have to be rolled back to whatever created them (which would be the rule in the program that allows you to communicate faster than light in a way that creates contradictions) and we'd have to take a different Continuation path. This suggests that in real physics, depending on how similar to physics MerkleWeb really is, that we can move some things faster than light as long as we don't create any contradictions. Therefore MerkleWeb is similar to relativistic quantum physics. That's how MerkleWeb deals with "different inputs/race conditions".

[netrin]

I believe you would need 'big heartbeats' of arbitrary (though constrained) duration. I should be able to set some data and code in time and space, and then after sufficient validation, to share that data and code as a library. Using the (three?) axioms: BIT, NAND, and a 320-bit POINTER, I begin by defining a basic assembly language with XOR, IOR, AND, NOT, multiplication, bit shifts, loops, comparisons, etc. This would require enormous amounts of data (because each address is 1/3 KiB - I think you need much smaller relative address 'words'). I would expect its inclusion in the MerkelWeb to be atomic (like your version control analogies).

Each heartbeat is synonymous with a verified bitcoin-esque block consisting of numerous cycles. Inclusion in a block asserts valid code execution and resultant state. However, unlike bitcoin, I don't think the MerkelWeb needs to verify the ENTIRE address space. Perhaps you might add a third dimension, addressing isolated MerkelBranches, each with its own manageable blockchain. Personally, I don't want to spend a single one of my local cycles thrashing on some idiot's infinite loop. I prefer a DVCS analogy. I can arbitrarily clone and pull from any MerkleBranch (repo). MerkleBranches can reference across other MerkleBranches.

Is each 'transaction' essentially a single memory space, or stack, and entire execution history recorded as a merkle tree since some earlier verified (fork) point in time/memory?

Yes, like a simplified version of http://en.wikipedia.org/wiki/Apache_Subversion that versions and branches the whole memory and computing state and virtual hardware design at the NAND level.

I imagine a transaction as a single node's assertion of code and data. I might allocate 100n merkleBits of a fibonacci calculator and submit that code as a single atomic transaction to the MerkleWeb. Since it is static code/data, it should have no trouble getting verified and included in a MerkleBlock by peer miner nodes. Next, I set a 'thread pointer' to the top of my routine and calculate twenty iterations of the series and submit the state and output register as my second transaction. Now a peer miner would need to re-execute my code and verify that yes indeed, he agrees with the state, before including the data, code, and execution state into another block.

In theory my fibonacci routine, once executed will run forever, unless it segfaults on pre-allocated finite memory. However, I rather think that some node must actively execute the code and submit the state as a transaction, otherwise if no node applies cycles, a program halts indefinitely.

What's the incentive? Verification of code and execution state included in a block is undeniable proof of local resource allocation. The miner can be rewarded with computational and storage credit, which like bitcoin can be used as fee, to inject new code and state into the MerkleWeb.

MerkleWeb will handle programs that do not halt (including infinite loops) by running them 1 cycle at a time.

I disagree with this. As written above, I believe execution should be every node's prerogative. A thread is indefinitely halted if no node bothers to continue executing it (or pays credits for other nodes to execute it). Each transaction is an assertion of an arbitrary number of cycles and/or injection of data/code.

Theres still some things to figure out about how to rollback [...] It always runs in debug mode.

How do we reconcile multiple executions of the same 'program' with different inputs/race conditions?

If any 2 MerkleTrees are both thought to be probably correct by the local computer (or wireless Turing Complete router), then it must trace the contradiction back [...] This is the part that's similar to quantum physics. [...] "different inputs/race conditions".

This is perfectly analogous to a double-spend, mining blocks, and reorg. There is only one longest chain of events, but it takes a few blocks to unambiguously confirm global state. It would require enormous computational power to change reality, "deja vu" Matrix-style.

[BenRayfield]

I believe you would need 'big heartbeats' of arbitrary (though constrained) duration.

Not duration. It has to be a predictable number of cycles per global heartbeat so the computers can align each of the 2^63 possible time rows, or in the 1024 bit version, each of the 2^511 possible time rows (no year-2000 type bugs here to fix, and we get to have constant bit strings or files exceeding 1 googolbit, which can be derived at runtime instead of stored). We would obsolete the 320 bit MerkleWeb, but the 1024 bit version will last us all the way up to a technology singularity since its address space is big enough to represent every particle/wave in the entire part of the universe we've seen so far which is billions of lightyears wide, and SVN-like branching of all that, if we knew how to program that into it and if we had enough hardware to run all those calculations and data storage on. Let's plan ahead.

Also, I extend my theory that physics may operate similar to MerkleWeb with the following: http://en.wikipedia.org/wiki/Parity_%28physics%29 parity like one direction of rotating electricity causes perpendicular electricity through the circle one direction instead of the other, may be caused by something like the bit rotations and other nonsymmetric math in http://en.wikipedia.org/wiki/Sha512 or other secure-hash algorithms, but in a more analog way like we observe in qubits.

Back to practical technical stuff...

I should be able to set some data and code in time and space, and then after sufficient validation, to share that data and code as a library.

Such libraries would be stored the same way as emulated hardware definitions, as bit strings in the constants section. We need some way to apply its 320 bit address to another 320 bit address like a function call, and it needs to be defined in terms of NAND. We can't use any high level programming abilities without building them first. It is circular-logic, and that's why the requirement is that we build the first layer as a quine. http://en.wikipedia.org/wiki/Quine_(computing)

Using the (three?) axioms: BIT, NAND, and a 320-bit POINTER, I begin by defining a basic assembly language with XOR, IOR, AND, NOT, multiplication, bit shifts, loops, comparisons, etc.

Ok. The standard low level calculations from programming languages.

This would require enormous amounts of data (because each address is 1/3 KiB - I think you need much smaller relative address 'words').

No. You only spend the data to create each operator as a function once. Then you create more complex functions using those simpler functions. Each function can cost many bits to create, but once they're created, calling a huge function to do many calculations is very cheap at some small multiple of 320 bits. If it was run completely in emulated mode, it would be that slow, but more frequently used parts of MerkleWeb could, for example, compile down to Java bytecode at runtime, so they use 32 or 64 bit native addresses and native integer and floating point math. There are many possible optimizations.

I would expect its inclusion in the MerkelWeb to be atomic (like your version control analogies).

Yes. The whole system will have the concurrency ability of a database, by default, unless its tuned toward lower accuracy for more speed.

Each heartbeat is synonymous with a verified bitcoin-esque block consisting of numerous cycles.

...

it takes a few blocks to unambiguously confirm global state.

Yes. The number of heartbeats in the time it takes information to travel from all computers in the network to all other computers is the average verification window.

Inclusion in a block asserts valid code execution and resultant state. However, unlike bitcoin, I don't think the MerkelWeb needs to verify the ENTIRE address space.

Each computer in MerkleWeb will only verify a small part of the address space by broadcasting their best knowledge of the correct state of part of the address space and other times broadcasting that same state but with some incorrect bits. As the 2 versions (1 true and 1 deceptive) flow through the network and eventually come back, statistically new data containing the locally-true-broadcast will come back more often than new data containing the locally-deceptive-broadcast. This is because contradictions get rolled back, and deception causes contradictions, so the correctness of calculations can be measured by how well they survive as they flow through long paths in the network. We don't need to know what paths they took through the network, just that they come back in many different Merkle Trees that each cover a different subset (overlapping eachother in many ways) of the address space. You're right that the entire address space doesn't need to be verified. Its verified indirectly.

Using this strategy, it may be practical to only verify 1 in every million bits, as long as they're randomly chosen in many different ways by many different computers and verifying many different SVN-like branches of the network to cover cases where certain code does and does not run.

I said earlier "the algorithm is nonlocal, exponentially error tolerant, and scale-free." That's true if every bit is verified and all computers run the whole program, like all computers in a Bitcoin network (at least in earlier versions, did they change that yet?), so any number of computers can agree on a shared calculation that way, but I'm not sure what the scaling cost is for each computer running only a small fraction of the program and still guaranteeing no bit or NAND calculation will ever be done wrong and assuming most of the network may be hostile computers. If we relax some of these constraints, it will scale better. There's lots of tradeoffs to tune. For a global voting system, its a small enough number of calculations we can verify all the bits, and that was the original use case.

Perhaps you might add a third dimension, addressing isolated MerkelBranches, each with its own manageable blockchain. Personally, I don't want to spend a single one of my local cycles thrashing on some idiot's infinite loop.

Each MerkleWeb network can have its own way of allocating computing resources. Supply and demand will push it toward you get as much as you put in, so that won't be a problem.

I prefer a DVCS analogy. I can arbitrarily clone and pull from any MerkleBranch (repo). MerkleBranches can reference across other MerkleBranches.

Yes. That's a core feature of MerkleWeb.

In theory my fibonacci routine, once executed will run forever, unless it segfaults on pre-allocated finite memory. However, I rather think that some node must actively execute the code and submit the state as a transaction, otherwise if no node applies cycles, a program halts indefinitely.

...

execution should be every node's prerogative.

In an open source system, nobody can force computers to continue calculating anything they don't want to. Of course they could all agree to calculate something else, but if breaks the rules defined in the NANDs and previous bit states, that would not be a MerkleWeb. Only "choice bits" can change the path of calculations. If you're worried about not having a preferred future available, build in a MerkleWeb-kill-switch made of choice bits that a majority-agreement of public-keys (as defined in the NAND logic) can activate to change the path. That way, when all those people and their computers choose to calculate something different, its still a MerkleWeb and is just another branch.

What's the incentive? https://bitcointalk.org/index.php?topic=49029.0 Verification of code and execution state included in a block is undeniable proof of local resource allocation. The miner can be rewarded with computational and storage credit, which like bitcoin can be used as fee, to inject new code and state into the MerkleWeb.

It would be useful to have a lower level similarity to Bitcoin than a "driver" (as I wrote above) written on top of the NAND level. Allocation of computing resources is important enough that we maybe should make an exception and put it at the core parallel to the importance of NAND and bits, but only if it can be done without complicating the design much. As a driver, it would add the complexity as the need for more optimizations, but the core would be simpler which is very valuable.

I read that thread. Its good strategy to boot up this system as a way to buy and sell (or for purposes of avoiding the obligation to pay taxes, the moneyless trading of) anonymous computing power and network storage. Lets do it.

How should we get started?

[netrin]

I believe you would need 'big heartbeats' of arbitrary (though constrained) duration.

Not duration. It has to be a predictable number of cycles per global heartbeat so the computers can align each of the 2^63 possible time rows. ... ... ... unless its tuned toward lower accuracy for more speed.

I believe trying to synchronize each individual cycle of all threads to a unique sequential index will be prohibitively slow, hardly useful for even highly specialized scenarios. You can't seriously expect 'real-time' interrupts anyway.

Instead, I propose a much larger sequence of cycles per block, perhaps hundreds (or millions) of cycles. Then exactly like bitcoin, each node atomically submits a pre-computed bunch of bits as a transaction, which other nodes can verify. Bundled with other transactions, blocks are added to the public blockchain. Only the blocks are synchronized and only blocks increment the 2^63 time rows. And just like bitcoin, blocks can not confirm much faster than a few minutes otherwise your latency is greater than your error/synchronization rate, and the network will spend most of its resources thrashing.

We can't use any high level programming abilities without building them first. It is circular-logic, and that's why the requirement is that we build the first layer as a quine.

You've sold me on the elegance of the absolute fewest axioms. Nearly all applications will first shebang some interpreter (or decompressor) followed by a script and data. How you get from NANDs and BITs to registers, addresses, words, gotos, loops, comparisons, stacks, and arithmetic is beyond me, but I trust self-hosting/bootstrapping has been done for decades and can be done again.

Inclusion in a block asserts valid code execution and resultant state. However, unlike bitcoin, I don't think the MerkelWeb needs to verify the ENTIRE address space.

Each computer in MerkleWeb will only verify a small part of the address space by broadcasting their best knowledge of the correct state of part of the address space and other times broadcasting that same state but with some incorrect bits.

I posit that you can not have both synchronized cycles and voluntary execution.

If every submitted transaction represents some execution performed by a node voluntarily, and a block represents a collection of transactions verified by some miner voluntarily, then you can synchronize only those voluntarily executed blocks of cycles.

On the other hand, if you expect all cycles to be synchronized, then you must require that for each delta bit in the entire address space, at least some node actually executes/verifies it (which is probably impossible).

I don't see any way around it: Unloved code can not be synchronized. If no node bothers to execute a thread, it is a cryogenic zombie and can not be retro-actively executed.

Using this strategy, it may be practical to only verify 1 in every million bits, as long as they're randomly

Verifying data (with hash checksums) is trivial. Verifying x inputs, y algorithms, and z results is not trivial.

but I'm not sure what the scaling cost is for each computer running only a small fraction of the program and still guaranteeing no bit or NAND calculation will ever be done wrong and assuming most of the network may be hostile computers. If we relax some of these constraints, it will scale better. There's lots of tradeoffs to tune.

It seems to me that each block (time slice) must be verifiable in its entirety by any single node (just like all bitcoin transactions in a single block need to be verified by the rewarded miner). It's the past history that we can relax. We can assume that since no one has complained thus far, then we can be confident that the cumulative hash value of the previous ten years up to last month is probably true, but we still need to hash each current state in its entirety and hash it again against the previous cumulative state.

[BenRayfield]

I believe trying to synchronize each individual cycle of all threads to a unique sequential index will be prohibitively slow, hardly useful for even highly specialized scenarios. You can't seriously expect 'real-time' interrupts anyway.

Instead, I propose a much larger sequence of cycles per block, perhaps hundreds (or millions) of cycles. Then exactly like bitcoin, each node atomically submits a pre-computed bunch of bits as a transaction, which other nodes can verify. Bundled with other transactions, blocks are added to the public blockchain. Only the blocks are synchronized and only blocks increment the 2^63 time rows. And just like bitcoin, blocks can not confirm much faster than a few minutes otherwise your latency is greater than your error/synchronization rate, and the network will spend most of its resources thrashing.

We're thinking mostly the same thing, except I want to count 1 million time rows if there are 1 million cycles per global heartbeat, so if an error is found it can be rolled back and recalculated at the cycle granularity instead of the global heartbeat granularity. Its important to be able to roll back 1 level of parallel NANDs at a time. Rolling back NANDs normally has exponential complexity, but since we have snapshots of the past we can do it like a binary-search in Merkle Tree space and actually do it as jumping back and rolling forward, which has linear complexity, as I explained in the first post as "bloom filter".

How you get from NANDs and BITs to registers, addresses, words, gotos, loops, comparisons, stacks, and arithmetic is beyond me, but I trust self-hosting/bootstrapping has been done for decades and can be done again.

I can build that, but I don't know when I'll finish. I got this far by designing it like a work of art and will continue that way. Maybe somebody with massively parallel computer hardware design skills will help later. I'm more of a software and math person, but I can figure it out. There's alot of overlap.

I posit that you can not have both synchronized cycles and voluntary execution.

...

On the other hand, if you expect all cycles to be synchronized, then you must require that for each delta bit in the entire address space, at least some node actually executes/verifies it (which is probably impossible).

You're right, but I don't mean it that way. When I say 1 of 2^63 possible time cycles, each 1 row of up to 2^256 virtual bits, I mean simulated time which can be calculated later as long as such delayed calculation has no effect on the timeline. Example: There may be a variable x which is set to 5 at time cycle 1000, but you don't know its 5. You set variable y to x+1 at time cycle 2000. You know you're going to read the variable y at time cycle 2010, so you have 10 more cycles to calculate x and what happens in the next 1010 cycles just before you read y. This is http://en.wikipedia.org/wiki/Lazy_evaluation and is a common optimization that allows things to be calculated only when or if needed. Other parts of the system may have read and written x and y, and that may depend on some permissions system we would build on top of the public-key system which is built on top of the NAND system, so network communications are part of the lazy-evaluation and may push the evaluation farther into the future before the true state of the system can be known, but it will converge because of the "bloom filter" as explained in the first post of this thread.

As the technical documents and this thread already describe how to build these parts, MerkleWeb is Turing Complete http://en.wikipedia.org/wiki/Turing_complete and massively multithreaded http://en.wikipedia.org/wiki/Parallel_computing and database-strength concurrent integrity of data http://en.wikipedia.org/wiki/Database but can't Deadlock http://en.wikipedia.org/wiki/Deadlock because at the time of deadlocking it will roll back to a previous state (as close to the deadlocked state as possible) and try absolutely every possible permutation of the system until it finds one that does not deadlock, with optimizations for which paths to search first so it runs fast. It may run incredibly slow if you try to deadlock it, but it will never get stuck.

The rule for avoiding deadlocks is very simple. Any state of the system that can possibly lead to a deadlock is an error. Therefore all previous states of a deadlocked state are errors and must be rolled back until an incorrect NAND calculation is found, and then recalculate that NAND and proceed on the correct path (while this does leave the "choice bits" in an uncertain state and I'm not sure what to do about that, but in the worst case we leave them as unchosen).

Verifying data (with hash checksums) is trivial. Verifying x inputs, y algorithms, and z results is not trivial.

Changing the world is rarely easy, but MerkleWeb is worth the effort.

It seems to me that each block (time slice) must be verifiable in its entirety by any single node (just like all bitcoin transactions in a single block need to be verified by the rewarded miner).

It will be. Any part of the system, including past states and SVN-like branches with their own past states that branch and merge, can be requested by any computer as the 320 bit address of a Merkle Tree root whose leafs represent that state of MerkleWeb. That is exponentially optimized by each computer remembering things about many Merkle Trees between the roots and leafs of the many Merkle Trees (a merkle forest).

But that's not the difficulty. We need a way to make sure every part of the network is verified, directly or indirectly (as I explained above with the "deceptive" bits), by enough computers that we can be certain at least 1 of them is not an attacker.

It's the past history that we can relax. We can assume that since no one has complained thus far, then we can be confident that the cumulative hash value of the previous ten years up to last month is probably true, but we still need to hash each current state in its entirety and hash it again against the previous cumulative state.

Yes, like in Bitcoin.

[netrin]

Using this strategy, it may be practical to only verify 1 in every million bits, as long as they're randomly...

Verifying data (with hash checksums) is trivial. Verifying x inputs, y algorithms, and z results is not trivial.

Changing the world is rarely easy, but MerkleWeb is worth the effort.

A bitcoin reorg occurs because of rare race conditions or expensive malicious attack. But shouldn't lazy evaluation produce situations that will make rollback likely, more frequent, and to unpredictable depth?. Intensionally producing inconsistent state (Gödel) would be an obvious DDoS attack vector, no?

[BenRayfield]

Speculative evaluation (prediction and rollback if wrong) is needed if cycles run faster than it takes electricity to move from one side of Earth to the other.

I wrote in the first post:

here's the rule that makes it practical for realtime speeds: Since we only store MerkleTrees that, proven to exponential certainty, have no contradictions between their child MerkleTrees recursively, we only need to keep track of which child MerkleTrees are compatible with which other MerkleTrees, and search any MerkleTrees we receive from the peer to peer network recursively comparing their childs to the childs we already have, and use only the parts of them we can prove, to exponential certainty, do not contradict eachother.

That's how it works if all computers calculate the whole network. Loosening that constraint, and adding more reliability by continuously trying to deceive the network to make sure the network can handle it, we can have each computer only run a small fraction of MerkleWeb's calculations. I later wrote:

Since my design requirement is that MerkleWeb will still be secure even if 99% of the computers have been hacked into, I add the following to the MerkleWeb specification: All computers will lie in half of their broadcasts. Half will be what each computer honestly thinks is accurately part of the next state of MerkleWeb. The other half will be very close to that except it will have some bit, or multiple bits, set incorrectly, in a way that is very deceptive and hard to verify is wrong. That way, when a hacker gets into MerkleWeb, its no big deal, since all of MerkleWeb is already doing the same thing, has been expecting it and learned to overcome it.

Why would that work? Each contradiction added to a branch (like SVN has recursive branching) of MerkleWeb causes that branch to run anywhere between normal speed and half speed. On average, as the number of contradictions in a branch of MerkleWeb increases linearly, the speed of that branch will decrease exponentially.

So its simple to figure out which branches of MerkleWeb have contradictions... broadcast half of your communications honestly and the other half having some hard-to-detect error, and see which of your communications come back to you after they've flowed around the network for some time. Statistically more often, trust the communications that come back with your honest broadcasts, and distrust communications that come back with your dishonest broadcasts, because dishonesty will be exponentially time-dilated until it falls into a black-hole of contradictions that can't be calculated at any practical speed. In MerkleWeb, hackers fall into black-holes of time-dilation.

So yes the design does allow Denial of Service attacks in some branches, but other branches where such DoS attacks do not happen will also exist and will be much faster so most of the network will continue on those paths. To allow that, I add to the MerkleWeb design: Any state of the system where a DoS attack is possible in the future is an error state, therefore all previous states of a DoS state are errors and must be traced back to an incorrect NAND calculation. This will require that the "driver" of each MerkleWeb be written in a way that does not allow DoS attacks, else that driver will be automatically rolled back and force programmers to write a better driver that does not allow DoS attacks or "deadlocks" (as I originally wrote this strategy for).


In general, the cost of dealing with these things is MerkleWeb will run approximately log(number of bits in MerkleWeb) times slower, the cost of a binary search through Merkle Trees to find which trees are compatible with which other trees using local caches of the chances of such compatibility per Merkle Tree node. It's not exactly a binary search, but the calculation is something like that which compares the compatibility with each Merkle Tree and recurses to subsets of childs sometimes. For example, if there are 10^15 bits (amount of information in a Human brain) in a MerkleWeb network, it would run approximately 50 times slower than the normal way of running programs, since 2^50 is approximately 10^15. That 50x slowdown will be far more than paid for by new kinds of optimizations and the ability to scale up to any number of computers in the same peer to peer network, including grids of GPUs (in graphics cards) and wireless mesh networks and cell phones and other devices. That's the cost of protecting MerkleWeb from DoS attacks and keeping the network state globally consistent.

MerkleWeb is very different from how the Internet works today. Its other protection against DoS attacks, which so far have all been at a certain Internet address or part of the Internet, is that MerkleWeb has no addresses for specific hardware. There is 1 global 320 bit address space that represents CPU registers, memory, hard drive, network storage, packets flowing through routers, and all other patterns of information. There is no way to target a certain part of MerkleWeb with a DoS attack. Only the content on MerkleWeb can be targeted, and it's all spread across the Earth.

[RodeoX]

This is an idea worth watching. One can envision many uses for such a system. Great job man!

[BenRayfield]

Reminds me of something MerkleWeb is partially a continuation of, "An Idea Worth Spreading - The Future Is Networks", and the idea is spreading.
http://emergentbydesign.com/2010/03/16/an-idea-worth-spreading-the-future-is-networks

Social networks of people. Merkle Tree networks of calculations and data storage. Open source networks of software. Mind maps linking ideas together. MerkleWeb could bring it all together in a public-domain unbiased way.

[netrin]

I trust you have a grasp on these low-level implementation details, which if possible might as well be magic to me until I can sink my teeth into some tech specs. Now, for higher level concerns:

Suppose someone decides to upload their smut collection into the address space. What incentive does anyone else have to host the data? What means do they have to remove this data locally? Can nodes hold incomplete portions to be recreated by the requester? If every node purged specific data, would the network become invalidated?

Suppose someone uploaded a service. Would its availability be proportional to its popularity? (something like reinforced weighting of paths within a neural network [each node hop adds data to a leaky bucket proxy cache]).

Suppose someone uploaded false slanderous material. Could it be removed, modified? How could we address the 'latest' version of some material? (I assume data does not change in time and space)

Do you have thoughts on purely off-network code execution? Rather than defining an interpreter build up from MerkleAxioms (NAND, 321-bit addresses), a block of data could declare "this is an ambiguous version of javascript" followed by code including predictable public global variables (same address space, sequential time space). As long as some node runs the code locally and writes the outputs, there isn't much to verify. We can argue about whether it is truthy, but it's no longer deterministic as far as MerkleWeb. Would that be a problem? What prevents MerkleWeb from becoming primarily a global public copy-on-write versioned filesystem? Could that swamp the benefits or would it only make the network more robust?

If I recall from ZFS, addressing the full 128-bit address space would require more energy than required to boil the oceans. Does MerkleWeb require vastly more space to minimize random allocation collisions? Furthermore, if you expect the time component to represent cycles (rather than seconds or blocks), perhaps 64-bits is not sufficient? Running a trillion calculations per second is less than a year, or a few hundred years at a billion calcs per second.

[BenRayfield]

Suppose someone decides to upload their smut collection into the address space. What incentive does anyone else have to host the data? What means do they have to remove this data locally?

Like quantum physics, there is no concept of "local" in MerkleWeb. Each MerkleWeb network acts as 1 computer which many people and other technology can use at the same time.

Can nodes hold incomplete portions to be recreated by the requester?

Yes. Theoretically every bit could come from a different node, or more extreme than that, every bit could be compressed and be the result of some calculation that is spread across many nodes, so the bits don't have to exist directly anywhere in MerkleWeb as long as they can be quickly recalculated in any part of the network.

If every node purged specific data, would the network become invalidated?

...

Suppose someone uploaded false slanderous material. Could it be removed, modified?

The rules of any specific MerkleWeb network could be set up to allow deletions. As long as the state of a MerkleWeb is the result of a previous state of that MerkleWeb as defined by the rules encoded into its starting state, it will be a valid MerkleWeb. The rules can be anything since its a general computer. The deletion would become permanent if the network is set up to only store previous state of the last few minutes or years or whatever time range, with SVN-like compression only storing the "choice bits" and partial and overlapping snapshots of the calculations less often.

Suppose someone uploaded a service. Would its availability be proportional to its popularity? (something like reinforced weighting of paths within a neural network [each node hop adds data to a leaky bucket proxy cache]).

Yes. Self-Tuning Load Balancing at all levels is a core feature of MerkleWeb.

How could we address the 'latest' version of some material? (I assume data does not change in time and space)

In the 320 bit version of MerkleWeb, there are up to 2^256 virtual bits and up to 2^63 time rows of them. One way to do it would be to use each public key as a variable name and put its updated values at the current 64 bit time row and the same 256 bit address of the key. The data would always be a 320 bit address pointing at the "latest version of some material". Those 320 bits could extend 319 more bits into the space of "2^256 virtual bits" (allowing new broadcasts each cycle but possibly risking overlap with rare adjacent public keys) or the other direction up 319 more time rows (allowing new broadcasts every 320 cycles). Or some sections of the "2^256 virtual bits" could be allocated for such new material and optionally deallocated later when the sequence of "material" is deleted or moved. There's many ways to do it. Can anyone offer some ideas?

Do you have thoughts on purely off-network code execution? Rather than defining an interpreter build up from MerkleAxioms (NAND, 321-bit addresses), a block of data could declare "this is an ambiguous version of javascript" followed by code including predictable public global variables (same address space, sequential time space). As long as some node runs the code locally and writes the outputs, there isn't much to verify. We can argue about whether it is truthy, but it's no longer deterministic as far as MerkleWeb.

If something runs inside or outside of MerkleWeb does not affect if it can be mapped into the 320 bit address space and used as a part of MerkleWeb.

Example: Bitcoin's existing user accounts (public keys) and history of blocks could be used as a part of MerkleWeb's address space and seamlessly work with existing Bitcoin software and networks. That's because Bitcoin's behaviors are well-defined.

If something is not deterministic, it can only connect through a public-key which is used as the name of its input and output bits, called "choice bits", as it interacts with MerkleWeb. Example: People are often unpredictable, but they still need a way to interact with MerkleWeb.

Its not a problem. MerkleWeb wouldn't be useful if it couldn't interact with our chaotic world.

What prevents MerkleWeb from becoming primarily a global public copy-on-write versioned filesystem? Could that swamp the benefits or would it only make the network more robust?

http://en.wikipedia.org/wiki/Apache_Subversion (SVN) acts like a copy-on-write versioned filesystem but does it much more efficiently by only storing the changes and a little extra information for how to assemble all the changes into whole files again when an old version is requested. MerkleWeb is like SVN for the states of a general computer, while SVN is only for states of files and not the calculations.

If I recall from ZFS, addressing the full 128-bit address space would require more energy than required to boil the oceans. Does MerkleWeb require vastly more space to minimize random allocation collisions?

The most practical size for MerkleWeb to fit with today's technology is 320 bits because 256 are for the SHA256 algorithm (which is done reasonably fast in normal computers and there is some hardware designed specificly for SHA256) and 64 are for a 64 bit integer (which most programming languages and hardware calculate efficiently). As explained here http://en.wikipedia.org/wiki/SHA-2 is 1 of a few industry standards (each a different bit size and strength) for secure-hashing arbitrary bits.

224 is the smallest bit size which has no known security vulnerabilities. If SHA256 is cracked, it doesn't break MerkleWeb, just makes it have weaker security, since if 2 data that have the same SHA256 hashcode ever meet eachother on the same computer (which has a calculation cost of the square root of the whole calculation cost of the system) then the contradiction would ripple out causing recursive rollbacks until the cause was found and fixed. It could be done more efficiently than the square root of total network cost by making Merkle Trees refer to eachother in the constants section in many overlapping ways, so even if SHA256 is cracked, it would have to crack it from many Continuation states at once, which is an exponentially harder problem. If the security is tuned up that high, at the cost of efficiency, MerkleWeb's data-integrity (not secrecy) would be exponentially more secure than Bitcoin.

If that kind of security is used, it could theoretically be done with a 64+64 (instead of 256+64) bit address space since collisions would have selection-pressure against their continued existence by the extra layer of security, and the first data to be created would usually win and prevent the use of any data whose hashcode collides with it. I don't want to get into that complication yet (leave it for when or if SHA256 is cracked and if we don't upgrade to SHA512 at that time), so I recommend 256+64 bit addresses.

Furthermore, if you expect the time component to represent cycles (rather than seconds or blocks), perhaps 64-bits is not sufficient? Running a trillion calculations per second is less than a year, or a few hundred years at a billion calcs per second.

Right. But most people don't want to pay more now and think ahead, so lets go for the 320 bit version and upgrade to "the 1024 bit version" (as I wrote above) later which has an address space big enough to fit an entire 320 bit MerkleWeb in 1 of its constant bit strings.

If "the full 128-bit address space would require more energy than required to boil the oceans", then the full use of a 1024 bit address space would take more energy than a "big bang".

Optional possible use of MerkleWeb on more advanced hardware later: If infinitely manyworlds multiverse theory is true, then Schrodinger's Cat is both alive and dead at the same time, in different branches of reality, and we would have enough computers (on parallel mostly overlapping Earths) to use the full address space. This is supported by empirical observations in quantum experiments where objects big enough to see by the naked eye are in 2 or more places at once. The fact that Humans evolved to understand Newtonian physics does not change the fact that physics only appears to be Newtonian until you use physics with enough accuracy. This is relevant to MerkleWeb because if manyworlds multiverse theory is true, then an infinite number of Earths, each running variations of the same MerkleWeb calculations, will always calculate the same 320 bit address for the same calculation because SHA256 is consistent that way, so if a way to communicate between these parallel mostly overlapping Earths was later found, MerkleWeb would already be designed to take full advantage of an Internet where packets are routed statistically in wave-interference patterns between parallel Earths. I wrote about "wave interference" in MerkleWeb's network routing behaviors being similar to quantum physics. If that theory and manyworlds multiverse theory are both true, and if MerkleWeb is run on a grid of wireless routers (because they transmit light and all light is quantum), then MerkleWeb would literally be a quantum computer. If any of those theories are not true, then MerkleWeb would only change the world with "unity mode" for the whole Internet. Its important that MerkleWeb not depend on any of these unproven theories, just have the potential to use them in more advanced hardware later. I'm a Mad-Scientist, but I'm still a scientist and go about things in a logical way.

When I say MerkleWeb would be a 320 or 1024 bit global computer, I don't mean we have to have hardware at the whole address space. Its mostly for avoiding collisions of hashcodes and future expansion as technology continues advancing at exponential speed. It doesn't cost much to use a bigger address space with the same hardware, but it is very expensive to fix old systems. How much money was spent fixing the 2-digit numbers in year-2000 upgrades?



To everyone...

I could use some help in creating some example uses of MerkleWeb, and the technical details of what makes those examples work, of how MerkleWeb could be used to do each "design pattern" in http://en.wikipedia.org/wiki/Software_design_pattern Those "design patterns" are the most common patterns observed in software designs. If we can explain how MerkleWeb can do these patterns better than existing systems, it will be taken much more seriously.

That doesn't include simple data structures, but we need some examples of that too.

A list is easy. In the constant bit string section, a list could be n bits where n is a multiple of 320, and each group of 320 bits is a pointer to the thing in the list. The list would be at the 320 address of the first bit of the first pointer in the list.

A set is an unordered list. It can be done to allow binary-searches by ordering all pointers in the set as 320 bit unsigned integers. To check if a certain pointer is in the list, do the binary search. To combine 2 sets, do 1 cycle of the mergesort algorithm which is very fast.

A map/hashtable is like a set except 2 times as big. Each entry would be 2 pointers. The first pointer works the same as in the set. The second is the value for that key.

Lists, sets, and maps can contain eachother. Since SHA256 is a SECURE-hash algorithm, there is no direct way to have a map, set, or list that contains itself or has any path back to itself. Its an acyclic network of these programming objects. Example: Java's list, set, and map objects don't allow cycles either since it causes errors in the Object.hashCode() and Object.equals(Object) functions. Java allows you to design lists, sets, and maps that can have cycles of containing themself, but normally its considered an error and can result in an infinite loop when hashCode() or equals(Object) is called. MerkleWeb could allow cycles of objects containing themself by using Public Keys as variables, a list set or map containing the Public Key, and the Public Key later broadcasting a pointer to that list set or map. That doesn't interfere with the secure-hashing so it works.

We could create a JVM on top of MerkleWeb, but it would be very complex. Instead, implementing the Scheme language is closer to what MerkleWeb naturally does. But before integration with other languages, we should create a new language from the bit and NAND level up, using lists, sets, maps, and other simple data-structures and calculations, as a proof-of-concept. Then on top of that, create the examples of how to use MerkleWeb to do http://en.wikipedia.org/wiki/Software_design_pattern

Why help? Bitcoin, at its best so far, was a 100 million dollar economy, created out of nothing, taking value from all dollars and moving that value into bitcoins. 100 million dollars is small compared to the trillions in the total Earth economy. I mean no disrespect to Bitcoin since its a very innovative and useful program, but at its core Bitcoin is a calculator that does plus and minus and a spread out way of creating the numbers based on "proof of work". Bitcoin is a calculator. MerkleWeb will be a computer. MerkleWeb is based on the Bitcoin security model and other similarities, but far more generally useful. If Bitcoin can move 100 million dollars, then MerkleWeb can move trillions of dollars. If you or your business helps develop the MerkleWeb prototypes and/or ideas, or any other way you know to help, then when it gets big your investment will pay off as people know you helped create it and will be very interested to work with you on other big projects. All the MerkleWeb design documents I've written at http://sourceforge.net/projects/merkleweb and here in this thread are public-domain, which means I'm not taking a cut and nobody owns it and everyone has the right to use it, but still its an investment that is likely to indirectly move money toward anyone who helps in a big way, and will improve the world overall. "Unity mode" for the whole Internet, like VMWare did for programs of different operating systems on 1 computer at a time, is a game-changer. Will you help?

[phillipsjk]

I find the idea impressive, but I don't think it will actually work. As far as I can tell, the proposal is technically sound, but abstracts away real-world concerns like bandwidth and CPU time. It is like you took Computing Science to its logical conclusion.

I think Scalabilty has the potential to be a real problem for bitcoin. In the example given, a "VISA" level of transaction processing (2000 transactions per second) is expected to have blocks over 1GB in size. I expect this will force many miners on home or even business Internet connections off the network (Colocation with fiber access would be needed instead).

Even with the incredible compression you expect to achieve, I doubt a global turing machine will need less than 2000 transactions per second. This implies a huge amount of bandwidth usage and local storage demands (for saving every fork).

I also don't think confidential processing (such as generating vanity bitcoin addresses) will be possible without Fully Homomorphic encryption. Found out about that concept reading this very forum

[BenRayfield]

The core design of MerkleWeb does not support privacy or encryption, but since its a general computer those things can be layered on top.

http://en.wikipedia.org/wiki/Homomorphic_encryption

Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another (possibly different) algebraic operation performed on the ciphertext.

The Wikipedia page also says that a proof-of-concept of homomorphic encryption exists.

Craig Gentry[4] using lattice-based cryptography showed the first fully homomorphic encryption scheme as announced by IBM on June 25, 2009.[5][6] His scheme supports evaluations of arbitrary depth circuits. His construction starts from a somewhat homomorphic encryption scheme using ideal lattices that is limited to evaluating low-degree polynomials over encrypted data. (It is limited because each ciphertext is noisy in some sense, and this noise grows as one adds and multiplies ciphertexts, until ultimately the noise makes the resulting ciphertext indecipherable.) He then shows how to modify this scheme to make it bootstrappable—in particular, he shows that by modifying the somewhat homomorphic scheme slightly, it can actually evaluate its own decryption circuit, a self-referential property. Finally, he shows that any bootstrappable somewhat homomorphic encryption scheme can be converted into a fully homomorphic encryption through a recursive self-embedding. In the particular case of Gentry's ideal-lattice-based somewhat homomorphic scheme, this bootstrapping procedure effectively "refreshes" the ciphertext by reducing its associated noise so that it can be used thereafter in more additions and multiplications without resulting in an indecipherable ciphertext. Gentry based the security of his scheme on the assumed hardness of two problems: certain worst-case problems over ideal lattices, and the sparse (or low-weight) subset sum problem.
Regarding performance, ciphertexts in Gentry's scheme remain compact insofar as their lengths do not depend at all on the complexity of the function that is evaluated over the encrypted data. The computational time only depends linearly on the number of operations performed. However, the scheme is impractical for many applications, because ciphertext size and computation time increase sharply as one increases the security level. To obtain 2^k security against known attacks, the computation time and ciphertext size are high-degree polynomials in k. Recently, Stehle and Steinfeld reduced the dependence on k substantially.[7] They presented optimizations that permit the computation to be only quasi-k^3.5 per boolean gate of the function being evaluated.

Do you have a reason to think faster kinds of homomorphic encryption won't be found later?

Also, the binary form of software can be done in such a confusing way that its similar to encryption. That's why its usually impractical to modify a software without having the source-code, especially C code and other low-level languages. Some ways of doing it make it easy to translate the binary to readable form, while obfuscators are more like encryption. Combining that with just a little homomorphic encryption (which is practical speed for lower security levels) may be enough for practical privacy while the bottom layer of MerkleWeb is publicly visible and searchable.

Also, I wrote a few things about "privacy" earlier in this thread.

The idea for MerkleWeb started as a way to have reliable calculations in a global network. Privacy was the afterthought. Its not a core feature and would need to be built as a higher layer, like we can still have privacy on the Internet today while the lower layers of http://en.wikipedia.org/wiki/OSI_model are not secure.

I know the first (and maybe the newest?) version of Bitcoin isn't scalable, but the math design of Bitcoin is scale-free since each computer could do only a small part of the calculations and store only some of the blocks, making sure it all overlaps correctly.

Quote from Bitcoin's design doc http://bitcoin.org/bitcoin.pdf

If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first.  In that case, they work on the first one they received, but save the other branch in case it becomes longer.  The tie will be broken when the next proof-of-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.

New transaction broadcasts do not necessarily need to reach all nodes.  As long as they reach many nodes, they will get into a block before long.  Block broadcasts are also tolerant of dropped messages

...

7. Reclaiming Disk Space
Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space.  To facilitate this without breaking the block's hash, transactions are hashed in a Merkle Tree [7][2][5], with only the root included in the block's hash. Old blocks can then be compacted by stubbing off branches of the tree.  The interior hashes do not need to be stored.

...

8. Simplified Payment Verification
It is possible to verify payments without running a full network node.  A user only needs to keep a copy of the block headers of the longest proof-of-work chain, which he can get by querying network nodes until he's convinced he has the longest chain, and obtain the Merkle branch linking the transaction to the block it's timestamped in.  He can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it.

As such, the verification is reliable as long as honest nodes control the network, but is more vulnerable if the network is overpowered by an attacker.  While network nodes can verify transactions for themselves, the simplified method can be fooled by an attacker's fabricated transactions for as long as the attacker can continue to overpower the network.  One strategy to protect against this would be to accept alerts from network nodes when they detect an invalid block, prompting the user's software to download the full block and alerted transactions to confirm the inconsistency.  Businesses that receive frequent payments will probably still want to run their own nodes for more independent security and quicker verification.

Those parts of Bitcoin's design doc describe paths of expanding Bitcoin's design so each computer only needs to use a small part of the network. MerkleWeb will be a continuation of those ideas optimized for most calculations being deterministic and a very small fraction of calculations being digitally-signed nondeterministic "choice bits".

I'll have to think about this some more, but so far I'm very confident that MerkleWeb's design ranges from scale-free to the square-root of the efficiency you'd expect, depending on how much reliability you need and how much of the network is run in each computer and what fraction of the computers can be hacked and you still need MerkleWeb to work reliably with the remaining parts, and other things to tune.

When they created http://en.wikipedia.org/wiki/Arpanet it was slower than a dial-up-modem, but its purpose was reliable communications even if much of the communications grid goes down. Since then, the Internet has come under centralized control, has become a hierarchy of servers and mostly client connections, where no 2 normal Internet connections can contact eachother without going through a server computer which are mostly owned by businesses. Regardless of how slow it may be, MerkleWeb would be what Arpanet was supposed to become, a decentralized reliable communication grid that works even in severe battle conditions. In MerkleWeb, if half the Earth is nuked, the other half of the computers would experience a few seconds delay and lose the last few seconds of clicks and button presses but mostly continue without interruption at half speed. In general, but not taken to that extreme, that's what Arpanet was supposed to become.

I find the idea impressive, but I don't think it will actually work. As far as I can tell, the proposal is technically sound, but abstracts away real-world concerns like bandwidth and CPU time. It is like you took Computing Science to its logical conclusion.

Most digital technology is designed for use with brute-force computing strategies. MerkleWeb's design sacrifices brute-force speed for unlimited abstraction potential. An analogy: Scheme is to Common Lisp as MerkleWeb is to VMWare. Scheme supports unlimited levels of recursion through http://en.wikipedia.org/wiki/Tail-call_optimization as the normal way to do control-flow, a style that would crash languages like Java with a StackOverflowException. You can run operating systems inside other operating systems inside operating systems... through VMWare, for example, but it gets slower each time. Because of its potential for unlimited NAND level abstraction of the whole network as 1 system, MerkleWeb has the potential to run virtual/emulated systems inside eachother to any depth without losing any speed, like recursive functions don't get slower at deeper recursion levels. It comes down to a choice between brute-force speed and the potential for more intelligent programming. Without using the Internet as a Universal Turing Machine, that potential is not available. Example: Billions of dollars could be used to "rage against the machine" about how the Internet is centrally controlled, or we could offer a much better way to organize it public-domain and free to everyone as MerkleWeb. Which strategy is more effective in that case, brute-force or slower but more intelligent abstractions? Humans can think more abstractly than Monkeys and Tigers and Elephants is why we are the dominant species. We're certainly not the strongest or fastest. So why continue using brute-force strategies in technology?

[netrin]

Like quantum physics, there is no concept of "local" in MerkleWeb. Each MerkleWeb network acts as 1 computer which many people and other technology can use at the same time.

As long as we are not using quantum computers, data is stored (or its XOR RAID-5 like difference can be calculated from data stored) somewhere, no? If enough data is missing (if enough RAID-5 disks catch on fire) is the entire address space corrupted?

The rules of any specific MerkleWeb network could be set up to allow deletions.

Merkle-tree-pruning, yes. But if some code today addresses data that later 'disappears', doesn't the result of the computation become invalidated (not possible to be validated) at some point in the future?

How could we address the 'latest' version of some material? (I assume data does not change in time and space)

... There's many ways to do it. Can anyone offer some ideas?

What prevents MerkleWeb from becoming primarily a global public copy-on-write versioned filesystem? Could that swamp the benefits or would it only make the network more robust?

... (SVN) acts like a copy-on-write versioned filesystem but does it much more efficiently by only storing the changes and a little extra information for how to assemble all the changes into whole

If every address bit is { 1 | 0 | null }, then like SVN, ZFS, Btrfs, CoW, every bit in time is a cumulative difference of all historical changes from its preceding past, then 'now' is the same as TIME = ( MAX_64_BIT_INT - 1 ). I don't think this will scale at all, but it's theoretically solid.

addressing the full 128-bit address space would require more energy than required to boil the oceans.

I would not think that the hash space should impact your address space size. I should think 128-bit address in 128-bit time is sufficient for binary bits (not quibits) during the lifetime of humans on Earth.

I find the idea impressive, but I don't think it will actually work. ... Even with the incredible compression you expect to achieve, I doubt a global turing machine will need less than 2000 transactions per second. ... (such as generating vanity bitcoin addresses) will be possible without Fully Homomorphic encryption.

Some types of verified work, particularly when you wish to keep secrets from the worker, may require cutting edge encryption, but I would think most repetitive tasks can be verified through random reprocessing checks.

Many of BenRayfield's abstractions are beyond me, though fascinating. As far as I am concerned, a truly distributed generic computer(s) is very useful and would work. It would be very nice to be able to store data in the network (unlocked by local private keys) as well as distribute processing and pay only for cycles used. In fact, the user of services, rather than the producer of services, may actually pay.

I would be more than willing to offer my local processing time, storage space, and bandwidth in exchange for credits for future distributed computation, storage, and bandwidth. I don't particularly care if those data and services are within one single MerkleWeb, or one of numerous addressible distributed grid computers. Those credits could either replace bitcoin, give it inherent value, or compliment bitcoin nicely.

[FreddyFender]

What would the time frame be for full implementation to alpha and are there any precursors or valid test cases that we can implement prior to a full product being available? Is the light version of this idea just as valid or does it need to meet any threshold value between inception and full run?

FF

[phillipsjk]

Testing on a LAN should be possible, but there will be so much overhead that it would only work as a proof-of-concept.

One thing that needs to be clarified is how do you force poeple to write using "intelligent programming" rather than "brute force"? I think it is obvious that injecting "choice bits" into the system will be more expensive than spending bitcoin. Brute-force algorithms may even involve fewer "choice bits" than a much faster algorithms. Though, you pointed out, the faster algorithm only has to be written once (unless encrypted).

I have no opinion about the viability of Homomorphic encryption. I expect for many public-interest calculations, keeping them public may be a good thing. For example, climate modeling: Critics would be able to see exactly how much the data was "fudged."

[jtimon]

...the faster algorithm only has to be written once (unless encrypted).

Wait a minute...You mean the network can run programs without knowing what they do?
I don't get it. Can you explain it?