So how are the ptrace functions implemented? Is the "hack" of inserting invalid instructions used even for single stepping? (Though hardware breakpoints are probably easier?)
I think "hack" is a little too strong a word. CPUs, historically, have had too little state to usefully track all the execution breakpoints you might want to set. So they normally have a nice short instruction that the OS can trap. On x86, it's INT 3, aka interrupt 3, encoded in a single byte, 0xCC. Interrupts are handled by entries in the interrupt vector table (IVT), normally in a region of memory only the OS can write to (if you're not doing something like running DOS in real mode). So when the CPU tries to execute 0xCC, it instead calls code located in the fourth entry (3 counted from 0) in the IVT. This will be filled by the OS, for modern values of OS.
(Single stepping CPU instructions is done with mode flags on the CPU for x86; this let's the CPU single-step things like REPNZ prefix used with string instructions).
Other CPUs don't have that. So on a 6502, to do single stepping, you write BRK (software interrupt) over the first byte of the next instruction. When handling the BRK, you write the original instruction back into memory, then insert BRK at the next instruction. The hard part in all this is finding the next instruction. Not only do you have to decode the instructions to find it, but you also have to handle conditional branches, which either involves figuring out which path with be taken and inserting the BRK in the appropriate location, or inserting the BRK into both paths (and having to restore both later). This also precludes single stepping through ROM.
[1] https://en.wikipedia.org/wiki/Trap_flag [2] https://en.wikipedia.org/wiki/X86_debug_register