Hello all. I have a bit of a crazy idea, and I'd like to assess its feasibility.

In case you're not familiar with the concept of "proof-of-work":
https://en.wikipedia.org/wiki/Proof_of_work

What I'm hoping to find is some kind of "proof-of-6502" - some kind of algorithm that will either:

- provide a verifiable result only if run on a 6502 or
- work more quickly on a 1mhz 6502 than other CPUs at higher clock rate.

Any ideas? Any quirks of the way math is done on an 8-bit that's hard to reproduce on a 32- or 64-bit processor running 10,000 times faster?

Welcome! Emulators are pretty accurate these days, and very fast too. Even 300MHz on a Raspberry Pi. So you can't outpace an emulator: the only question is if you can trick it into doing the wrong thing.
- wrapping the stack
- wrapping a pointer fetch in zero page
- wrapping the program counter at the top of memory
- wrapping an indexed access at the top of memory
- checking decimal arithmetic, including for non-decimal inputs

As testsuites are incrementally improved, emulators improve, so anything which works today might not work next week...

I'm more focused on finding something that's easy for a 6502 to do, even an emulated one, but that's difficult for an x86 native program to do. Or a result that's unique to the hardware. Like adding 2+2 on some calculator and getting 3.9999999997, and knowing, internally, it's doing the math a particular way, while any other calculator would just give you 4.

I know it's probably impossible, but that's the kind of puzzle I like

Getting the overflow flag right, and getting decimal mode right, are the most common stumbling blocks, so that might be in the area you're looking for.
http://6502.org/tutorials/vflag.html
http://www.6502.org/tutorials/decimal_mode.html

Proof-of-work works only because certain problems take a lot of time even on the fastest computers and even specialized machinery. Simulating a 6502 is an easy problem; there is nothing a 6502 can do that an x86 can't do (and much faster). Slowness is not a provable 6502 characteristic either (easily faked). A Turing machine is a Turing machine, and if the problem is computational, any computer can compute it. But it is the most unusual 6502 topic I've come across lately!

_________________
In theory, there is no difference between theory and practice. In practice, there is. ...Jan van de Snepscheut

Possibly in the spirit of the question is to seek particular challenges, or algorithms, where the 6502 - with a given memory speed - outshines the other sort.

It's necessary to specify the memory speed and not the clock speed because memory was the dominant cost and the limiting factor of 70s computers. Broadly, there's a very approximate 3x multiplier between 6502 and z80 clock speeds, because of internal details of the way the two microprocessors are put together.

So, a typical 6502 computer of the day would run at 1MHz and a typical z80 computer at 3.5MHz, very approximately.

I think there are things which advantage the 6502, but I'm not sure what they are. It has been said that the 6502 is much better at chess and the z80 at floating point.

One of the difficulties is that you need excellent speed-optimised code for both processors: if a 6502 expert writes z80 code, they might not get the best out the machine, and vice versa.

I wrote some notes on the topic here
viewtopic.php?p=19248#p19248

I guess what I'm after isn't as much a proof of work as a proof of 8-bit. For instance:
http://imgur.com/RiAbF6d

Based on the specific glitch in the results, you can determine what the calculator app is doing under the hood, as far as floating point precision, and how it represents numbers internally.

Take that result and feed it back into a function that compounds the glitch, and you'll eventually get a result that's unique for each "species" of calculator.

I think what I'm looking for is like this:
Start with a given value.
Insert that value into a lossy/glitchy function.
Iterate n times.
Compare results with the same function run on an 8-bit machine, and modern machine. The cumulative glitches will be different.

The letter of the question is:

The idea is to prove that someone has an 8-bit machine and is not cheating, much like proof of work provides guarantees that someone does not have an unfair advantage. This is provably impossible: a simulated simple CPU is indistinguishable from a real one in a trustless situation.

A glitch you describe, option8, will be faithfully simulated by correct software. Relying on mistakes in simulation is of very limited use - someone will notice and fix it. In a 'security by obscurity' situation you may have a small window of being able to identify a glitch. I find it hard to imagine such a situation, but it may give you a small window of time until they figure out you are exploiting it (much like malware today).

If you are compiling a list of 'real 8-bitters', for instance, it will become unreliable as soon as your methodology is disclosed, or even when the existence of your data-gathering becomes known. This will happen even if nothing of value is at stake: given enough time someone will find it worth their while to sabotage your effort.

Ed, are you suggesting we go off-topic and benchmark the 6502 against other CPUs of the day at identical clock speeds? This discussion is full of surprises!

_________________
In theory, there is no difference between theory and practice. In practice, there is. ...Jan van de Snepscheut

Reply to option8:

(Image is of a calculator app managing only a close approximation to 778.79-778.34. I just tried two apps on different phones and they both get it right. They also manage to produce zero for (((4/3)-1)*3-1) which on conventional calculators usually gives a telling non-zero value.)

The difference here, I think, is that floating point libraries are a very complex thing with a deceptively simple apparent behaviour: the complexities can come to the surface with careful prodding. Whereas the 8 bit operations of 70s microprocessors are simple things. While you might compare Basics with a torture test, I can't quite see how you could do the same for the base instruction set.

There might be a way, but I can't presently see it.

Reply to enso:
I was indeed wondering if comparing 8 bit micros would be interesting and sufficiently close to the spirit of the enquiry. However, I see option8 has clarified their interest, and it isn't that. But we've had previous threads on the topic which we could perhaps reinvigorate, if we have new thoughts.

I suppose there is a species of test, but I can't say it feels satisfactory:

Compute 64+64+64+64 and compare to zero

Take 1 and shift left 8 times, compare to zero

Add 5 to 5, add the result to itself 10 times, compare to zero

Add 1 to 1 and rotate left 9 times, subtract 2 and compare to zero

Which is to say, all arithmetic on 6502 is byte-sized, and there's a possibility of being in decimal mode. And rotations include the carry bit.

BigEd, I think you are missing the point: any computation a 6502 can do, a simulated 6502 can do identically.

While the general answer is 'no', there are situations where 'fingerprinting' of some sort is possible.

Could you describe your scenario in more detail?

For instance, are you passively observing some computation and are trying to extract statistics? Or can you request that some specific code be executed at your direction and results provided back? Perhaps you could request specific hardware observations - how many nanoseconds after a particular bus cycle do address lines change state? In what sequence? Although hardware can be simulated as easily...

'Security by obscurity' can work if your system is big and computations are forced down your throat by a hostile party. Consider how your browser can be identified by fingerprinting. There are maybe 5 browsers you can choose from, created by corporations to collect data and allow web-site providers to collect data while distracting you with pretty pictures. They make sure that enough data is leaking from each request that you are easily and generally uniquely identifiable. Any attempt to anonymize yourself - by blocking cookies, faking your browser version, etc. is a joke http://amiunique.org, or worse yet, can make you even more identifiable. In my case my tracking blockers leaked even more data than they were blocking!

So at least if you design an '8-bit internet', gain cooperation with network providers and dominant software vendors, and force each user to broadcast a fingerprint without them being able to do anything about it, maybe yes.

_________________
In theory, there is no difference between theory and practice. In practice, there is. ...Jan van de Snepscheut

(I think the ground has shifted a little since the first post in the thread - we're not, I think, any longer concerned with the fact that a 32 bit machine can emulate a 6502.)

Edit: I suppose my inclination here, in contributing at all, is in drawing out some interesting train of thought. Answering the question I might have asked if I'd been in the same frame of mind, perhaps. Rather than trying to dissect a question which doesn't quite seem well-framed.)

We are not?

The question is perfectly framed, and is not at all vague or unreasonable.

_________________
In theory, there is no difference between theory and practice. In practice, there is. ...Jan van de Snepscheut

Hmm, I'm trying to find a way to enjoy this thread, as are you, but they seem to be different ways. The fact that our recent contributions crossed in the post hasn't helped, I'm sure.

I am just answering the original question - is it possible to prove that a computation is performed on a 6502 or another 8-bit machine.

I am not sure why you want to moderate this (and every other) discussion. There is no hostility here, and I actually find this topic pretty interesting - and others may too.

_________________
In theory, there is no difference between theory and practice. In practice, there is. ...Jan van de Snepscheut