pcdinh/Cuckoo Cycle

## Cuckoo Cycle
https://blog.aeternity.com/q-a-at-reddit-with-john-tromp-inventor-of-the-cuckoo-cycle-mining-algorithm-c316119c07e9

Trong Cuckoo Cycle, chứng cứ xử lý có dạng một chu trình 42 cạnh (khép kín) nằm trong 1 đồ thị lớn ngẫu nhiên hình thành trên một vài con số dùng một lần (nonce) nào đó. Thử tưởng tượng 2 quốc gia, mỗi quốc gia có 1 tỉ thành phố, và thử tưởng tượng chọn 1 tỉ con đường chạy cắt qua biên giới kết nối 1 thành phố ngẫu nhiên ở một quốc gia này với 1 thành phố ngẫu nhiên của một quốc gia khác (PoW này thật ra là dùng một hàm băm không dùng nhiều tài nguyên để ánh xạ 1 con số dùng một lần, số của con đường, và quốc gia đến một thành phố). Câu hỏi ở đây là liệu có tồn tại 1 chu trình gồm 42 con đường kết nối 42 thành phố khác nhau hay không. Nếu một ai đó trao cho bạn một con số dùng một lần và con số của 42 con đường thì bạn sẽ thấy là cực kì dễ kiểm chứng (verify) trong thời gian và bộ nhớ rất nhỏ. Nhưng để tìm ra được 1 chu trình như vậy thì lại không hề là một bài toán dễ giải. Tuy nhiên lưu ý ở đây là, một thành phố kết nối đến duy nhất 1 con đường mà thôi không phải là đáp án của bài toán, và con đường đó cũng vậy. David Andersen chỉ ra rằng những con đường đi vào ngõ cụt như vậy có thể bị loại bỏ trong quá trình thử lại, mà chỉ dùng 1 bit bộ nhớ mỗi con đường để ghi nhận con đường đó có phù hợp hay không, và 2 bit cho mỗi thành phố để đếm xem có hay không, 1 hay nhiều con đường phù hợp kết nối đến thành phố đó.

Quá trình tính toán để đếm cho các thành phố này và đánh dấu các con đường dẫn đến một thành phố có một số đếm là không phù hợp, là cốt lõi của bài toán khai thác Cuckoo Cycle và chiếm đến 98% nỗ lực xử lý. Nó cần đến hàng tỉ truy cập vào bộ nhớ toàn cục ngẫu nhiên để đọc và ghi các số đếm. Kết quả là, khoảng 2/3 số thời gian xử lý là liên quan đến độ trễ của bộ nhớ, làm cho thuật toán này tiêu tốn ít năng lượng và máy tính sẽ mát.

Sau khi tính được đủ số đếm và các vòng đánh dấu, chúng ta sẽ chỉ còn lại 1 vài con đường phù hợp cho một thuật toán khác, dựa trên Cuckoo Hashing, can quickly identify cycles (re-using the memory for the no longer needed counters).
Cuckoo Cycle has some downsides as well. First, proofs are large and will roughly triple the size of block headers. Second, it is very slow, taking the better part of a minute on a high end CPU (or GPU, which offer roughly the same speed) to look for a cycle among a billion roads.

In order to give slower CPUs a (somewhat) fair chance to win, the block interval should be much longer than a single proof attempt, so the amount of memory Cuckoo Cycle can use is constrained by the choice of block interval length.

These seem like reasonable compromises for an instantly verifiable memory bound PoW that is unique in being dominated by latency rather than computation. In that sense, mining Cuckoo Cycle is a form of ASIC mining where DRAM chips serve the application of randomly reading and writing billions of bits.

When even phones charging overnight can mine without orders of magnitude loss in efficiency, not with a mindset of profitability but of playing the lottery, the mining hardware landscape will see vast expansion, benefiting adoption as well as decentralization.
	https://blog.aeternity.com/q-a-at-reddit-with-john-tromp-inventor-of-the-cuckoo-cycle-mining-algorithm-c316119c07e9

	Trong Cuckoo Cycle, chứng cứ xử lý có dạng một chu trình 42 cạnh (khép kín) nằm trong 1 đồ thị lớn ngẫu nhiên hình thành trên một vài con số dùng một lần (nonce) nào đó. Thử tưởng tượng 2 quốc gia, mỗi quốc gia có 1 tỉ thành phố, và thử tưởng tượng chọn 1 tỉ con đường chạy cắt qua biên giới kết nối 1 thành phố ngẫu nhiên ở một quốc gia này với 1 thành phố ngẫu nhiên của một quốc gia khác (PoW này thật ra là dùng một hàm băm không dùng nhiều tài nguyên để ánh xạ 1 con số dùng một lần, số của con đường, và quốc gia đến một thành phố). Câu hỏi ở đây là liệu có tồn tại 1 chu trình gồm 42 con đường kết nối 42 thành phố khác nhau hay không. Nếu một ai đó trao cho bạn một con số dùng một lần và con số của 42 con đường thì bạn sẽ thấy là cực kì dễ kiểm chứng (verify) trong thời gian và bộ nhớ rất nhỏ. Nhưng để tìm ra được 1 chu trình như vậy thì lại không hề là một bài toán dễ giải. Tuy nhiên lưu ý ở đây là, một thành phố kết nối đến duy nhất 1 con đường mà thôi không phải là đáp án của bài toán, và con đường đó cũng vậy. David Andersen chỉ ra rằng những con đường đi vào ngõ cụt như vậy có thể bị loại bỏ trong quá trình thử lại, mà chỉ dùng 1 bit bộ nhớ mỗi con đường để ghi nhận con đường đó có phù hợp hay không, và 2 bit cho mỗi thành phố để đếm xem có hay không, 1 hay nhiều con đường phù hợp kết nối đến thành phố đó.

	Quá trình tính toán để đếm cho các thành phố này và đánh dấu các con đường dẫn đến một thành phố có một số đếm là không phù hợp, là cốt lõi của bài toán khai thác Cuckoo Cycle và chiếm đến 98% nỗ lực xử lý. Nó cần đến hàng tỉ truy cập vào bộ nhớ toàn cục ngẫu nhiên để đọc và ghi các số đếm. Kết quả là, khoảng 2/3 số thời gian xử lý là liên quan đến độ trễ của bộ nhớ, làm cho thuật toán này tiêu tốn ít năng lượng và máy tính sẽ mát.

	Sau khi tính được đủ số đếm và các vòng đánh dấu, chúng ta sẽ chỉ còn lại 1 vài con đường phù hợp cho một thuật toán khác, dựa trên Cuckoo Hashing, can quickly identify cycles (re-using the memory for the no longer needed counters).
	Cuckoo Cycle has some downsides as well. First, proofs are large and will roughly triple the size of block headers. Second, it is very slow, taking the better part of a minute on a high end CPU (or GPU, which offer roughly the same speed) to look for a cycle among a billion roads.

	In order to give slower CPUs a (somewhat) fair chance to win, the block interval should be much longer than a single proof attempt, so the amount of memory Cuckoo Cycle can use is constrained by the choice of block interval length.

	These seem like reasonable compromises for an instantly verifiable memory bound PoW that is unique in being dominated by latency rather than computation. In that sense, mining Cuckoo Cycle is a form of ASIC mining where DRAM chips serve the application of randomly reading and writing billions of bits.

	When even phones charging overnight can mine without orders of magnitude loss in efficiency, not with a mindset of profitability but of playing the lottery, the mining hardware landscape will see vast expansion, benefiting adoption as well as decentralization.