Максим Мосейчук

1) Как ни странно - операция хеширования. Это функция. На вход принимает массив байтов произвольной длинны (+ закодированная длинна массива) дополненного нулями при необходимости до кратного размера. На выходе - массив байтов фиксированного размера.
С точки зрения математики это сюръективное отображение бесконечного счётного множества в конечное.
2) Один хеш CPU посчитает намного быстрее GPU. Вот только современные десктопные 4 ядерные процессоры одновременно могут вычислять только 4 хеша (по количеству ядер). А в видеокартах тысячи вычислительных блоков, и каждый может независимо считать хеш. Поэтому когда нужно миллионы хешей вычислить, видеокарты выигрывают.
3) Only-CPU алгоритмы отличаются в первую очередь требуемым объёмом памяти. Для каждой итерации требуется свой кусок памяти. Если хеш для вычисления требует 2 гигабайта памяти, то видеокарта с 4 гигабайтами может за раз считать только 2 хеша (а то и вообще один - не забываем про накладные расходы). И CPU с таким объёмом памяти может считать то же количество хешей. Только CPU это сделает намного быстрее.
Сделали это в первую очередь не против видеокарт, а против ASIC.

Транзакция просто посылается в сеть. Читать про p2p протоколы, в частности про DHT.
Затем кучка транзакций объединяется в блок, в котором есть изменяемое поле nonce. Так же туда добавляется транзакция с наградой майнера, в которой нет входов. И начинается процесс майнинга - перебор значений в поле nonce. Необходимо подобрать такое значение, что бы хеш от блока (читать про хеш-функции) был меньше определённого числа (грубо говоря, что бы в начале хеша было N нулей). Значение высчитывается на основе сложности, которая меняется каждые k-блоков.

Это на примере bitcoin и производных. Никаких мудрёных алгоритмов тут нет. Всё это было придумано десятки лет назад. Просто нужно было собрать в кучу.

Блок может не содержать транзакций. В начале сложность 0. Т.е. по сути любой пустой блок будет валидным. Ну а дальше уже сложность будет подстраиваться сама.